Michael Nielsen

Archive for June, 2005

Fermions and the Jordan-Wigner transform V: Diagonalization Continued

June 29, 2005 at 1:58 pm · Filed under General

In today’s post we continue with the train of thought begun in the last post, learning how to find the energy spectrum of any Hamiltonian quadratic in Fermi operators. Although we don’t dwell in this post on the connection to specific physical models, this class of Hamiltonians covers an enormous number of models of relevance in condensed matter physics. In later posts we’ll apply these results (together with the Jordan-Wigner transform) to understand the energy spectrum of some models of interacting spins in one dimension, which are prototypes for an understanding of quantum magnets and many, many other phenomena, including many systems which undergo quantum phase transitions.

Update: Thanks to Steve Mayer for fixing a bug in the way matrices are displayed.

Note: This post is one in a series describing fermi algebras, and a powerful tool known as the Jordan-Wigner transform, which allows one to move back and forth between describing a system as a collection of qubits, and as a collection of fermions. The posts assume familiarity with elementary quantum mechanics, comfort with elementary linear algebra (but not advanced techniques), and a little familiarity with the basic nomenclature of quantum information science (qubits, the Pauli matrices).

The Hamiltonian $H = \sum_{jk} \alpha_{jk} a_j^\dagger a_k$ we diagonalized in the last post can be generalized to any Hamiltonian which is quadratic in Fermi operators, by which we mean it may contain terms of the form $a^\dagger_j a_k, a_j a_k^\dagger, a_j a_k$ and $a_j^\dagger a_k$ . We will not allow linear terms like $a_j+a_j^\dagger$ . Additive constant terms $\gamma I$ are easily incorporated, since they simply displace all elements of the spectrum by an amount $\gamma$ . There are several ways one can write such a Hamiltonian, but the following form turns out to be especially convenient for our purposes:

$H = \sum_{jk} \left( \alpha_{jk} a_j^\dagger a_k -\alpha^*_{jk} a_j a_k^\dagger + \beta_{jk} a_j a_k – \beta^*_{jk} a_j^\dagger a_k^\dagger \right).$

The reader should spend a little time convincing themselves that for the class of Hamiltonians we have described, it is always possible to write the Hamiltonian in this form, up to an additive constant $\gamma I$ , and with $\alpha$ hermitian and $\beta$ antisymmetric.

This class of Hamiltonian appears to have first been diagonalized in an appendix to a famous Annals of Physics paper by Lieb, Schultz and Mattis, dating to 1961 (volume 16, pages 407-466), and the procedure we follow is inspired by theirs. We begin by defining operators $b_1,\ldots,b_n$ :

$b_j \equiv \sum_k \left( \gamma_{jk} a_k + \mu_{jk} a_k^\dagger \right).$

We will try to choose the complex numbers $\gamma_{jk}$ and $\mu_{jk}$ to ensure that: (1) the operators b_j satisfy Fermionic CCRs; and (2) when expressed in terms of the b_j , has the same form as $H_{\rm free}$ , and so can be diagonalized.

A calculation shows that the condition $\{ b_j, b_k^\dagger \} = \delta_{jk} I$ is equivalent to the condition

$\gamma \gamma^\dagger + \mu \mu^\dagger = I,$

while the condition $\{ b_j, b_k \} = 0$ is equivalent to the condition

$\gamma \mu^T+\mu \gamma^T = 0.$

These are straightforward enough equations, but their meaning is perhaps a little mysterious. More insight into their structure is obtained by rewriting the connection between the a_j s and the b_j s in an equivalent form using vectors whose individual entries are not numbers, but rather are operators such as a_j and b_j , and using a block matrix with blocks $\gamma, \mu, \mu^*$ and $\gamma^*$ :

$\left[ \begin{array}{c} b_1 \\ \vdots \\ b_n \\ b_1^\dagger \\ \vdots \\ b_n^\dagger \end{array} \right] = \left[ \begin{array}{cc} \gamma & \mu \\ \mu^* & \gamma^* \end{array} \right] \left[ \begin{array}{c} a_1 \\ \vdots \\ a_n \\ a_1^\dagger \\ \vdots \\ a_n^\dagger \end{array} \right].$

The conditions derived above for the b_j s to satisfy the CCRs are equivalent to the condition that the transformation matrix

$T \equiv \left[ \begin{array}{cc} \gamma & \mu \\ \mu^* & \gamma^* \end{array} \right]$

is unitary, which is perhaps a somewhat less mysterious condition than the earlier equations involving $\gamma$ and $\mu$ . One advantage of this representation is that it makes it easy to find an expression for the a_j in terms of the b_j , simply by inverting this unitary transformation, to obtain:

$\left[ \begin{array}{c} a_1 \\ \vdots \\ a_n \\ a_1^\dagger \\ \vdots \\ a_n^\dagger \end{array} \right] = T^\dagger \left[ \begin{array}{c} b_1 \\ \vdots \\ b_n \\ b_1^\dagger \\ \vdots \\ b_n^\dagger \end{array} \right].$

The next step is to rewrite the Hamiltonian in terms of the b_j operators. To do this, observe that:

$H = [ a_1^\dagger \ldots a_n^\dagger a_1 \ldots a_n ] \left[ \begin{array}{cc} \alpha & -\beta^* \ \beta & -\alpha^* \end{array} \right] \left[ \begin{array}{c} a_1 \\ \vdots \\ a_n \\ a_1^\dagger \\ \vdots \\ a_n^\dagger \end{array} \right].$

It is actually this expression for which motivated the original special form which we chose for . The expression is convenient, for it allows us to easily transform back and forth between expressed in terms of the a_j and in terms of the b_j . We already have an expression in terms of the b_j operators for the column vector containing the and $a^\dagger$ terms. With a little algebra this gives rise to a corresponding expression for the row vector containing the $a^\dagger$ and terms:

$[a_1^\dagger \ldots a_n^\dagger a_1 \ldots a_n] = [b_1^\dagger \ldots b_n^\dagger b_1 \ldots b_n] T.$

This allows us to rewrite the Hamiltonian as

$H = [b^\dagger b] T M T^\dagger \left[ \begin{array}{c} b \\ b^\dagger \end{array} \right],$

where we have used the shorthand $[b^\dagger b]$ to denote the vector with entries $b_1^\dagger, \ldots, b_n^\dagger,b_1,\ldots,b_n$ , and

$M = \left[ \begin{array}{cc} \alpha & -\beta^* \\ \beta & -\alpha^* \end{array} \right].$

Supposing we can choose such that $TMT^\dagger$ is diagonal, we see that the Hamiltonian can be expressed in the form of $H_{\rm free}$ , and the energy spectrum found, following our earlier methods.

Since $\alpha$ is hermitian and $\beta$ antisymmetric it follows that also is hermitian, and so can be diagonalized for some choice of unitary . However, the fact that the b_j s must satisfy the CCRs constrains the class of s available to us. We need to show that such a can be used to do the diagonalization.

We will give a heuristic and somewhat incomplete proof that this is possible, before making some brief remarks about what is required for a rigorous proof. I’ve omitted the rigorous proof, since the way I understand it is uses a result from linear algebra that, while beautiful, I don’t want to explain in full detail here.

Suppose is any unitary such that

$T M T^\dagger = \left[ \begin{array}{cc} d & 0 \\ 0 & -d \end{array} \right],$

where is diagonal, and we used the special form of to deduce that the eigenvalues are real and appear in matched pairs $\pm \lambda$ . We’d like to show that can be chosen to be of the desired special form. To see that this is plausible, consider the map $X \rightarrow S X^* S^\dagger$ , where is a block matrix:

$S = \left[ \begin{array}{cc} 0 & I \\ I & 0 \end{array} \right].$

Applying this map to both sides of the earlier equation we obtain

$ST^* M^* T^T S^\dagger = \left[ \begin{array}{cc} -d & 0 \\ 0 & d \end{array} \right] = -TMT^\dagger.$

But $M^* = -S^\dagger M S$ , and so we obtain:

$-ST^* S^\dagger M S T^T S^\dagger = -TMT^\dagger.$

It is at least plausible that we can choose such that $ST^*S^\dagger = T$ , which would imply that has the required form. What this actually shows is, of course, somewhat weaker, namely that $T^\dagger ST^* S^\dagger$ commutes with .

One way of obtaining a rigorous proof is to find a satisfying

$T M T^\dagger = \left[ \begin{array}{cc} d & 0 \\ 0 & -d \end{array} \right],$

and then to apply the cosine-sine (or CS) decomposition from linear algebra, which provides a beautiful way of representing block unitary matrices, and which, in this instance, allows us to obtain a of the desired form with just a little more work. The CS decomposition may be found, for example, as Theorem VII.1.6 on page 196 of Bhatia’s book “Matrix Analysis” (Springer-Verlag, New York, 1997).

Problem: Can we extend these results to allow terms in the Hamiltonian which are linear in the Fermi operators?

In this post we’ve seen how to diagonalize a general Fermi quadratic Hamiltonian. We’ve treated this as a purely mathematical problem, although most physicists will probably have little trouble believing that these techniques are useful in a wide range of physical problems. In the next post we’ll explain a surprising connection between these ideas and one-dimensional spin systems: a tool known as the Jordan-Wigner transform can be used to establish an equivalence between a large class of one-dimensional spin systems and the type of Fermi systems we have been considering. This is interesting because included in this class of one-dimensional spin systems are important models such as the transverse Ising model, which serve as a general prototype for quantum magnetism, are a good basis for understanding some naturally occurring physical systems, and which also serve as prototypes for the understanding of quantum phase transitions.

Permalink Comments (3)

Fermions and the Jordan-Wigner transform IV: Diagonalizing Fermi Quadratic Hamiltonians

June 26, 2005 at 7:50 am · Filed under General

I’ve finally had a chance to get back to Fermions. Today’s post explains how to diagonalize a Hamiltonian which is quadratic in operators satisfying the Fermionic CCRs. Remarkably, we’ll do this using only the CCRs: the operators could arise in many different ways physically, but, as we shall see, it is only the CCRs that matter for determining the spectrum! This class of Hamiltonians arises in a lot of realistic physical systems, and we’ll see an explicit example later on, when we show that a particular spin model (the X-Y model) is equivalent to a Fermi quadratic Hamiltonian.

(Unfortunately, there seems to be a bug in WordPress that required me to strip most of the tags denoting emphasis (e.g. bold or italics) out of this post. Weird.)

Diagonalizing a Fermi quadratic Hamiltonian

Suppose $a_1,\ldots,a_n$ satisfy the Fermionic CCRs, and we have a system with Hamiltonian

$H_{\rm free} = \sum_j \alpha_j a_j^\dagger a_j,$

where $\alpha_j \geq 0$ for each value of . In physical terms, this is the Hamiltonian used to describe a system of free, i.e., non-interacting, Fermions.

Such Hamiltonians are used, for example, in the simplest possible quantum mechanical model of a metal, the Drude-Sommerfeld model, which treats the conduction electrons as free Fermions. Such a model may appear pretty simplistic (especially after we solve it, below), but actually there’s an amazing amount of physics one can get out of such simple models. I won’t dwell on these physical consequences here, but if you’re unfamiliar with the Drude-Sommerfeld theory, you could profitably spend a couple of hours looking at the first couple of chapters in a good book on condensed matter physics, like Ashcroft and Mermin’s “Solid State Physics”, which explains the Drude-Sommerfeld model and its consequences in detail. (Why such a simplistic model does such a great job of describing metals is another long story, which I may come back to in a future post.)

Returning to the abstract Hamiltonian $H_{\rm free}$ , the positivity of the operators $a_j^\dagger a_j$ implies that $\langle \psi |H_{\rm free} |\psi\rangle \geq 0$ for any state $|\psi\rangle$ , and thus the ground state energy of $H_{\rm free}$ is non-negative. However, our earlier construction also shows that we can find at least one state $|\mbox{vac}\rangle$ such that $a_j^\dagger a_j|\mbox{vac}\rangle = 0$ for all , and thus $H_{\rm free}|\mbox{vac}\rangle = 0$ . It follows that the ground state energy of $H_{\rm free}$ is exactly .

This result is easily generalized to the case where the $\alpha_j$ have any sign, with the result that the ground state energy is $\sum_j \min(0,\alpha_j)$ , and the ground state $|\psi\rangle$ is obtained from $|\mbox{vac}\rangle$ by applying the raising operator a_j for all with $\alpha_j < 0$ . More generally, the allowed energies of the excited states of this system correspond to sums over subsets of the $\alpha_j$ .

Exercise: Express the excited states of the system in terms of $|\mbox{vac}\rangle$ .

Just by the way, readers with an interest in computational complexity theory may find it interesting to note a connection between the spectrum of $H_{\rm free}$ and the Subset-Sum problem from computer science. The Subset-Sum problem is this: given a set of integers $x_1,\ldots,x_n$ , with repetition allowed, is there a subset of those integers which adds up to a desired target, ? Obviously, the problem of determining whether $H_{\rm free}$ has a particular energy is equivalent to the Subset-Sum problem, at least in the case where the $\alpha_j$ are integers. What is interesting is that the Subset-Sum problem is known to be NP-Complete, in the language of computational complexity theory, and thus is regarded as computationally intractable. As a consequence, we deduce that the problem of determining whether a particular value for energy is in the spectrum of $H_{\rm free}$ is in general NP-Hard, i.e., at least as difficult as the NP-Complete problems. Similar results hold for the more general Fermi Hamiltonians considered below. Furthermore, this observation suggests the possibility of an interesting link between the physical problem of estimating the density of states, and classes of problems in computational complexity theory, such as the counting classes (e.g., #P), and also to approximation problems.

Let’s generalize our results about the spectrum of $H_{\rm free}$ . Suppose now that we have the Hamiltonian

$H = \sum_{jk} \alpha_{jk} a_j^\dagger a_k.$

Taking the adjoint of this equation we see that in order for to be hermitian, we must have $\alpha_{jk}^* = \alpha_{kj}$ , i.e., the matrix $\alpha$ whose entries are the $\alpha_{jk}$ is itself hermitian.

Suppose we introduce new operators $b_1,\ldots,b_n$ defined by

$b_j \equiv \sum_{k=1}^n \beta_{jk} a_k,$

where $\beta_{jk}$ are complex numbers. We are going to try to choose the $\beta_{jk}$ so that (1) the operators b_j satisfy the Fermionic CCRs, and (2) when expressed in terms of the b_j , the Hamiltonian takes on the same form as $H_{\rm free}$ , and thus can be diagonalized.

We begin by looking for conditions on the complex numbers $\beta_{jk}$ such that the b_j operators satisfy Fermionic CCRs. Computing anticommutators we find

$\{ b_j, b_k^\dagger \} = \sum_{lm} \beta_{jl} \beta_{km}^* \{ a_l,a_m^\dagger \}.$

Substituting the CCR $\{ a_l,a_m^\dagger \} = \delta_{lm} I$ and writing $\beta_{km}^* = \beta_{mk}^\dagger$ gives

$\{ b_j, b_k^\dagger \} = \sum_{lm} \beta_{jl} \delta_{lm} \beta_{mk}^\dagger I= (\beta \beta^\dagger)_{jk} I$

where $\beta \beta^\dagger$ denotes the matrix product of the matrix $\beta$ with entries $\beta_{jl}$ and its adjoint $\beta^\dagger$ . To compute $\{b_j,b_k\}$ we use the linearity of the anticommutator bracket in each term to express $\{b_j,b_k\}$ as a sum over terms of the form $\{ a_l,a_m \}$ , each of which is , by the CCRs. As a result, we have:

$\{ b_j,b_k \} = 0.$

It follows that provided $\beta \beta^\dagger = I$ , i.e., provided $\beta$ is unitary, the operators b_j satisfy the Fermionic CCRs.

Let’s assume that $\beta$ is unitary, and change our notation, writing $u_{jk} \equiv \beta_{jk}$ in order to emphasize the unitarity of this matrix. We now have

$b_j = \sum_k u_{jk} a_k.$

Using the unitarity of we can invert this equation to obtain

$a_j = \sum_k u^\dagger_{jk} b_k.$

Substituting this expression and its adjoint into and doing some simplification gives us

$H = \sum_{lm} (u \alpha u^\dagger)_{lm} b_l^\dagger b_m.$

Since $\alpha$ is hermitian, we can choose so that $u \alpha u^\dagger$ is diagonal, with entries $\lambda_j$ , the eigenvalues of $\alpha$ , giving us

$H = \sum_j \lambda_j b_j^\dagger b_j.$

This is of the same form as $H_{\rm free}$ , and thus the ground state energy and excitation energies may be computed in the same way as we described earlier.

What about the ground state of ? Assuming that all the $\lambda_j$ are non-negative, it turns out that a state $|\psi\rangle$ satisfies $a_j^\dagger a_j |\psi\rangle = 0$ for all if and only if $b_j^\dagger b_j|\psi\rangle = 0$ for all , and so the ground state for the two sets of Fermi operators is the same.

This follows from a more general observation, namely, that $a_j^\dagger a_j |\psi\rangle = 0$ if and only if $a_j|\psi\rangle = 0$ . In one direction, this is trivial: just multiply $a_j|\psi\rangle = 0$ on the left by $a_j^\dagger$ . In the other direction, we multiply $a_j^\dagger a_j |\psi\rangle = 0$ on the left by a_j to obtain $a_j a_j^\dagger a_j |\psi\rangle = 0$ . Substituting the CCR $a_j a_j^\dagger = -a_j^\dagger a_j + I$ , we obtain

$(-a_j^\dagger a_j^2+a_j)|\psi\rangle = 0.$

But a_j^2 = 0 , so this simplifies to $a_j|\psi\rangle = 0$ , as desired.

Returning to the question of determining the ground state, supposing $a_j^\dagger a_j|\psi\rangle = 0$ for all , we immediately have $a_j|\psi\rangle = 0$ for all , and thus $b_j|\psi\rangle = 0$ for all , since the b_j are linear functions of the a_j , and thus $b_j^\dagger b_j|\psi\rangle = 0$ for all . This shows that the ground state for the two sets of Fermi operators, a_j and b_j , is in fact the same. The excitations for may be obtained by applying raising operators $b_j^\dagger$ to the ground state.

Exercise: Suppose some of the $\lambda_j$ are negative. Express the ground state of in terms of the simultaneous eigenstates of the $a_j^\dagger a_j$ .

Okay, that’s enough for one day! We’ve learnt how to diagonalize a fairly general class of Hamiltonians quadratic in Fermi operators. In the next post we’ll go further, learning how to cope with additional terms like a_j a_j and $a_j^\dagger a_k^\dagger$ .

Permalink Comments off

Expander graphs: the complete notes

June 22, 2005 at 4:48 pm · Filed under Favourite posts, General, Technical, Technical notes

The full pdf text of my series of posts about expander graphs. Thankyou very much to all the people who commented on the posts; if you’re reading this text, and haven’t seen the comments on earlier posts, I recommend you look through them to see all the alternate proofs, generalizations and so on that people have offered.

Permalink Comments off

Expander graphs VI: reducing randomness

June 19, 2005 at 7:21 am · Filed under General

Back from Boston! This is the final installment in my series about expanders. I’ll post a pdf containing the whole text in the next day or two. Thanks to everyone who’s contributed in the comments!

Today’s post explains how expander graphs can be used to reduce the number of random bits needed by a randomized algorithm in order to achieve a desired success probability. This post is the culmination of the series: we make use of the fact, proved in the last post, that random walks on an expander are exponentially unlikely to remain localized in any sufficiently large subset of vertices, a fact that relies in turn on the connection, developed in earlier posts, between the eigenavlue gap and the expansion parameter.

Note: This post is one in a series introducing one of the deepest ideas in modern computer science, expander graphs. Expanders are one of those powerful ideas that crop up in many apparently unrelated contexts, and that have a phenomenally wide range of uses. The goal of the posts is to explain what an expander is, and to learn just enough about them that we can start to understand some of their amazing uses. The posts require a little background in graph theory, computer science, linear algebra and Markov chains (all at about the level of a first course) to be comprehensible. I am not an expert on expanders, and the posts are just an introduction. They are are mostly based on some very nice 2003 lecture notes by Nati Linial and Avi Wigderson, available on the web at http://www.math.ias.edu/~boaz/ExpanderCourse/.

Reducing the number of random bits required by an algorithm

One surprising application of expanders is that they can be used to reduce the number of random bits needed by a randomized algorithm in order to achieve a desired success probability.

Suppose, for example, that we are trying to compute a function f(x) that can take the values f(x) = 0 or f(x) = 1 . Suppose we have a randomized algorithm A(x,Y) which takes as input and an -bit uniformly distributed random variable , and outputs either or . We assume that:

implies with certainty.
implies with probability at least .

That is, p_f is the maximal probability that the algorithm fails, in the case when f(x) = 1 , but A(x,Y) = 0 is output by the algorithm.

An algorithm of this type is called a one-sided randomized algorithm, since it can only fail when f(x) = 1 , not when f(x) = 0 . I won’t give any concrete examples of one-sided randomized algorithms here, but the reader unfamiliar with them should rest assured that they are useful and important – see, e.g., the book of Motwani and Raghavan (Cambridge University Press, 1995) for examples.

As an aside, the discussion of one-sided algorithms in this post can be extended to the case of randomized algorithms which can fail when either f(x) = 0 or f(x) = 1 . The details are a little more complicated, but the basic ideas are the same. This is described in Linial and Wigderson’s lecture notes. Alternately, extending the discussion to this case is a good problem.

How can we descrease the probability of failure for a one-sided randomized algoerithm? One obvious way of decreasing the failure probability is to run the algorithm times, computing $A(x,Y_0),A(x,Y_1),\ldots,A(x,Y_{k-1})$ . If we get A(x,Y_j) = 0 for all then we output , while if A(x,Y_j) = 1 for at least one value of , then we output f(x) = 1 . This algorithm makes use of bits, and reduces the failure probability to at most p_f^k .

Expanders can be used to substantially decrease the number of random bits required to achieve such a reduction in the failure probability. We define a new algorithm $\tilde A$ as follows. It requires a -regular expander graph whose vertex set contains 2^m vertices, each of which can represent a possible -bit input to A(x,y) . The modified algorithm $\tilde A$ works as follows:

Input .
Sample uniformly at random from to generate .
Now do a step random walk on the expander, generating random variables $Y_1,\ldots, Y_{k-1}$ .
Compute $A(x,Y_0),\ldots,A(x,Y_{k-1})$ . If any of these are , output , otherwise output .

We see that the basic idea of the algorithm is similar to the earlier proposal for running A(x,Y) repeatedly, but the sequence of independent and uniformly distributed samples $Y_0,\ldots,Y_{k-1}$ is replaced by a random walk on the expander. The advantage of doing this is that only $m+k \log(d)$ random bits are required – to sample from the initial uniform distribution, and then $\log(d)$ for each step in the random walk. When is a small constant this is far fewer than the bits used when we simply repeatedly run the algorithm A(x,Y_j) with uniform and independently generated random bits Y_j .

With what probability does this algorithm fail? Define B_x to be the set of values of such that A(x,y) = 0 , yet f(x) = 1 . This is the “bad” set, which we hope our algorithm will avoid. The algorithm will fail only if the steps in the random walk $Y_0,Y_1,\ldots,Y_{k-1}$ all fall within B_x . From our earlier theorem we see that this occurs with probability at most:

$\left( \frac{|B_x|}{2^m} + \frac{\lambda_2(G)}{d} \right)^{k-1}.$

But we know that $|B_x|/2^m \leq p_f$ , and so the failure probability is at most

$\left( p_f + \frac{\lambda_2(G)}{d} \right)^{k-1}.$

Thus, provided $p_f+\lambda_2(G)/d < 1$ , we again get an exponential decrease in the failure probability as the number of repetitions is increased.

Conclusion

These notes have given a pretty basic introduction to expanders, and there’s much we haven’t covered. More detail and more applications can be found in the online notes of Linial and Wigderson, or in the research literature. Still, I hope that these notes have given some idea of why these families of graphs are useful, and of some of the powerful connections between graph theory, linear algebra, and random walks.

Permalink Comments (1)

Adios

June 9, 2005 at 1:13 pm · Filed under General

I’m off to Boston for a few days, so blogging will be on hold until the middle of next week.

Permalink Comments (1)

New paper: Operator quantum error correction

June 9, 2005 at 1:01 pm · Filed under General

A new paper (postscript), joint with David Poulin, all about operator quantum error correction, a clever way (alas, not my idea!) of protecting quantum states against the effects of noise. The paper provides several sets of easily checkable conditions (both algebraic and information-theoretic) characterizing when operator error-correction is feasible.

Postscript: Dave Bacon has a just put out a nice paper related to operator quantum error-correction, constructing some physically motivated examples of self-correcting quantum memories. This idea – that a quantum system can correct itself – is absolutely fascinating, and runs completely counter to the standard folk “wisdom” about quantum mechanics, namely that quantum states are delicate objects that are easily (and irreversibly) destroyed.

Permalink Comments off

Appendix to my posts on Fermions and the Jordan-Wigner transform

June 9, 2005 at 11:06 am · Filed under General

This is a little appendix to my post about the consequences of the fermionic CCRs. The results described in the appendix are very well-known – they are taught in any undergrad quantum course – but I’m rather fond of the little proof given, and so am indulging myself by including it here. The results are used in the previous post.

Appendix on mutually commuting observables

Any undergraduate quantum mechanics course covers the fact that a mutually commuting set of Hermitian operators possesses a common eigenbasis. Unfortunately, in my experience this fact is usually proved rather early on, and suffers from being presented in a slightly too elementary fashion, with inductive constructions of explicit basis sets and so on. The following proof is still elementary, but from a slightly more sophisticated perspective. It is, I like to imagine, rather more like what would be given in an advanced course in linear algebra, were linear algebraists to actually cover this kind of material. (They don’t, so far as I know, having other fish to fry.)

Suppose $H_1,\ldots,H_n$ are commuting Hermitian (indeed, normal suffices) operators with spectral decompositions:

$H_j = \sum_{jk} E_{jk} P_{jk},$

where $E_{jk}$ are the eigenvalues of H_j , and $P_{jk}$ are the corresponding projectors. Since the H_j commute, it is not difficult to verify that for any quadruple j,k,l,m the operators $P_{jk}$ and $P_{lm}$ also commute. For a vector $\vec k = (k_1,\ldots,k_n)$ define the operator

$P_{\vec k} \equiv P_{1 k_1} P_{2 k_2} \ldots P_{n k_n}.$

Note that the order of the operators on the right-hand side does not matter, since they all commute with one another. The following equations all follow easily by direct computation, the mutual commutativity of the $P_{jk}$ operators, and standard properties of the spectral decomposition:

$P_{\vec k}^\dagger = P_{\vec k}; \,\,\,\, \sum_{\vec k} P_{\vec k} = I; \,\,\,\, P_{\vec k} P_{\vec l} = \delta_{\vec k \vec l} P_{\vec k}.$

Thus, the operators $P_{\vec k}$ form a complete set of orthonormal projectors. Furthermore, suppose we have $P_{\vec k} |\psi\rangle = |\psi\rangle$ . Then we will show that for any we have $P_{jk_j} |\psi\rangle = |\psi\rangle$ , so $|\psi\rangle$ is an eigenstate of H_j with eigenvalue k_j . This shows that the operators $P_{\vec k}$ project onto a complete orthonormal set of simultaneous eigenspaces for the H_j , and will complete the proof.

Our goal is to show that if $P_{\vec k} |\psi\rangle = |\psi\rangle$ then for any we have $P_{jk_j} |\psi\rangle = |\psi\rangle$ . To see this, simply multiply both sides of $P_{\vec k} |\psi\rangle = |\psi\rangle$ by $P_{jk_j}$ , and observe that $P_{jk_j} P_{\vec k} = P_{\vec k}$ . This gives $P_{\vec k}|\psi\rangle = P_{jk_j}|\psi\rangle$ . But $P_{\vec k}|\psi\rangle = |\psi\rangle$ , so we obtain $|\psi\rangle = P_{j k_j}|\psi\rangle$ , which completes the proof.

Permalink Comments off

Fermions and the Jordan-Wigner transform III: Consequences of the Canonical Commutation Relations

June 9, 2005 at 10:58 am · Filed under General

Back to Fermions again! In today’s post we’ll show that the CCRs uniquely determine the action of the fermionic operators a_j , up to a choice of basis. Mathematically, the argument is somewhat detailed, but it’s also the kind of argument that rewards detailed study, especially if studied in conjunction with related topics, such as the representation theory of su(2) . You’ll need to look elsewhere for that, however!

Consequences of the fermionic CCRs

We will assume that the vector space is finite dimensional, and that there are operators $a_1,\ldots,a_n$ acting on and satisfying the Fermionic CCRs. At the end of this paragraph we’re going to give a broad outline of the steps we go through. Upon a first read, some of these steps may appear a little mysterious to the reader not familiar with representation theory. In particular, please don’t worry if you get a little stuck in your understanding of the outline at some points, as the exposition is very much at the bird’s-eye level, and not all detail is visible at that level. Nonetheless, the reason for including this broad outline is the belief that repeated study will pay substantial dividends, if it is read in conjunction with the more detailed exposition to follow, or similar material on, e.g., representations of the Lie algebra su(2) . Indeed, the advantage of operating at the bird’s-eye level is that it makes it easier to see the connections between these ideas, and the use of similar ideas in other branches of representation theory.

We’ll start by showing that the operators $a_j^\dagger a_j$ are positive Hermitian operators with eigenvalues and .
We’ll show that acts as a lowering operator for $a_j^\dagger a_j$ , in the sense that if $|\psi\rangle$ is a normalized eigenstate of $a_j^\dagger a_j$ with eigenvalue , then $a_j |\psi\rangle$ is a normalized eigenstate of $a_j^\dagger a_j$ with eigenvalue . If $|\psi\rangle$ is a normalized eigenstate of $a_j^\dagger a_j$ with eigenvalue , then $a_j |\psi\rangle$ vanishes.
Similarly, $a_j^\dagger$ acts as a raising operator for $a_j^\dagger a_j$ , in the sense that if $|\psi\rangle$ is a normalized eigenstate of $a_j^\dagger a_j$ with eigenvalue , then $a_j^\dagger |\psi\rangle$ is a normalized eigenstate of $a_j^\dagger a_j$ with eigenvalue . If $|\psi\rangle$ is a normalized eigenstate of $a_j^\dagger a_j$ with eigenvalue , then $a_j^\dagger |\psi\rangle$ vanishes.
We prove that the operators $a_j^\dagger a_j$ form a mutually commuting set of Hermitian matrices, and thus there exists a state $|\psi\rangle$ which is a simultaneous eigenstate of $a_j^\dagger a_j$ for all values $j=1,\ldots,n$ .
By raising and lowering the state $|\psi\rangle$ in all possible combinations, we’ll construct a set of orthonormal states which are simultaneous eigenstates of the $a_j^\dagger a_j$ . The corresponding vector of eigenvalues uniquely labels each state in this orthonormal basis.
Suppose the vector space spanned by these simultaneous eigenstates is . At this point, we know that and $a_j^\dagger$ map into , and, indeed, we know everything about the action and $a_j^\dagger$ have on .
Suppose we define $W_\perp$ to be the orthocomplement of in . Then we’ll show that the and $a_j^\dagger$ map $W_\perp$ into itself, and their restrictions to $W_\perp$ satisfy the Fermionic CCRs. We can then repeat the above procedure, and identify a -dimensional subspace of $W_\perp$ on which we know the action of the and $a_j^\dagger$ exactly.
We iterate this procedure until $W_\perp$ is the trivial vector space, at which point it is no longer possible to continue. At this point we have established an orthonormal basis for the whole of with respect to which we can explicilty write down the action of both and $a_j^\dagger$ .

Let’s go through each of these steps in more detail.

The $a_j^\dagger a_j$ are positive Hermitian with eigenvalues and : Observe that the $a_j^\dagger a_j$ are positive (and thus Hermitian) matrices. We will show that $(a_j^\dagger a_j)^2 = a_j^\dagger a_j$ , and thus the eigenvalues of $a_j^\dagger a_j$ are all or .

To see this, observe that $(a_j^\dagger a_j)^2 = a_j^\dagger a_j a_j^\dagger a_j = -(a_j^\dagger)^2 a_j^2 + a_j^\dagger a_j$ , where we used the CCR $\{a_j,a_j^\dagger \} = I$ . Note also that a_j^2 = 0 by the CCR $\{a_j,a_j\} = 0$ . It follows that $(a_j^\dagger a_j)^2 = a_j^\dagger a_j$ , as claimed.

The are lowering operators: Suppose $|\psi\rangle$ is a normalized eigenstate of $a_j^\dagger a_j$ with eigenvalue . Then we claim that $a_j|\psi\rangle$ is a normalized eigenstate of $a_j^\dagger a_j$ with eigenvalue . To see that $a_j|\psi\rangle$ is normalized, note that $\langle \psi|a_j^\dagger a_j |\psi\rangle = \langle \psi|\psi\rangle = 1$ , where we used the fact that $|\psi\rangle$ is an eigenstate of $a_j^\dagger a_j$ with eigenvalue to establish the first equality. To see that it has eigenvalue , note that $a_j^\dagger a_j a_j|\psi\rangle = 0$ , since $\{ a_j,a_j \} = 0$ .

Exercise: Suppose $|\psi\rangle$ is a normalized eigenstate of $a_j^\dagger a_j$ with eigenvalue . Show that $a_j |\psi\rangle = 0$ .

The are raising operators: Suppose $|\psi\rangle$ is a normalized eigenstate of $a_j^\dagger a_j$ with eigenvalue . Then we claimed that $a_j^\dagger|\psi\rangle$ is a normalized eigenstate of $a_j^\dagger a_j$ with eigenvalue .

To see the normalization, we use the CCR $\{ a_j,a_j^\dagger \} = I$ to deduce $\langle \psi|a_j a_j^\dagger |\psi\rangle = -\langle \psi|a_j^\dagger a_j|\psi\rangle + \langle \psi|\psi\rangle$ . But $a_j^\dagger a_j|\psi\rangle = 0$ , by the eigenvalue assumption, and $\langle \psi|\psi\rangle = 1$ , whence $\langle \psi|a_j a_j^\dagger |\psi\rangle = 1$ , which is the desired normalization condition.

To see that $a_j^\dagger |\psi\rangle$ is an eigenstate with eigenvalue , use the CCR $\{a_j,a_j^\dagger \} = I$ to deduce that $a_j^\dagger a_j a_j^\dagger |\psi\rangle = – a_j^\dagger a_j^\dagger a_j|\psi\rangle + a_j^\dagger|\psi\rangle = a_j^\dagger |\psi\rangle$ , where the final equality can be deduced either from the assumption that $a_j^\dagger a_j |\psi\rangle = 0$ , or from the CCR $\{ a_j^\dagger,a_j^\dagger \} = 0$ . This is the desired eigenvalue equation for $a_j^\dagger|\psi\rangle$ .

Exercise: Suppose $|\psi\rangle$ is a normalized eigenstate of $a_j^\dagger a_j$ with eigenvalue . Show that $a_j^\dagger |\psi\rangle = 0$ .

The $a_j^\dagger a_j$ form a mutually commuting set of observables: To see this, let $j \neq k$ , and apply the CCRs repeatedly to obtain $a_j^\dagger a_j a_k^\dagger a_k = a_k^\dagger a_k a_j^\dagger a_j$ , which is the desired commutativity.

Existence of a common eigenstate: It is well known that a mutually commuting set of Hermitian operators possesses a common eigenbasis. This fact is usually taught in undergraduate quantum mechanics courses; for completeness, I’ve included a simple proof in an appendix to these notes. We won’t make use of the full power of this result here, but instead simply use the fact that there exists a normalized state $|\psi\rangle$ which is a simultaneous eigenstate of all the $a_j^\dagger a_j$ operators. In particular, for all we have:

$a_j^\dagger a_j |\psi\rangle = \alpha_j |\psi\rangle,$

where for each either $\alpha_j = 0$ or $\alpha_j = 1$ . It will be convenient to assume that $\alpha_j = 0$ for all . This assumption can be made without loss of generality, by applying lowering operators to the $|\psi\rangle$ for each such that $\alpha_j = 1$ , resulting in a normalized state $|\mbox{vac}\rangle$ such that $a_j^\dagger a_j |\mbox{vac}\rangle = 0$ for all .

Defining an orthonormal basis: For any vector $\alpha = (\alpha_1,\ldots,\alpha_n)$ , where each $\alpha_j = 0$ or , define a corresponding state:

$|\alpha \rangle \equiv (a_1^\dagger)^{\alpha_1} \ldots (a_n^\dagger)^{\alpha_n}|\mbox{vac}\rangle.$

It is clear that there are 2^n such states $|\alpha\rangle$ , and that they form an orthonormal set spanning a subspace of that we shall call .

The action of the and $a_j^\dagger$ on : How do a_j and $a_j^\dagger$ act on ? Stated another way, how do they act on the orthonormal basis we have constructed for , the states $|\alpha\rangle$ ? Applying the CCRs and the definition of the states $|\alpha\rangle$ it is easy to verify that the action of a_j is as follows:

Suppose $\alpha_j = 0$ . Then $a_j|\alpha\rangle = 0$ .
Suppose $\alpha_j = 1$ . Let $\tilde \alpha$ be that vector which results when the th entry of $\alpha$ is changed to . Then $a_j|\alpha\rangle = -(-1)^{s_\alpha^j} |\tilde \alpha\rangle$ , where $s_\alpha^j \equiv \sum_{k=1}^{j-1} \alpha_k$ .

The action of $a_j^\dagger$ on is similar:

Suppose $\alpha_j = 0$ . Let $\tilde \alpha$ be that vector which results when the th entry of $\alpha$ is changed to . Then $a_j^\dagger|\alpha\rangle = -(-1)^{s_\alpha^j}|\tilde \alpha\rangle$ , where $s_\alpha^j \equiv \sum_{k=1}^{j-1} \alpha_k$ .
Suppose $\alpha_j = 1$ . Then $a_j^\dagger |\alpha\rangle = 0$ .

Action of and $a_j^\dagger$ on $W_\perp$ : We have described the action of the a_j and the $a_j^\dagger$ on the subspace . What of the action of these operators on the remainder of ? To answer that question, we first show that a_j and $a_j^\dagger$ map the orthocomplement $W_\perp$ into itself.

Consider now the operators $\tilde a_j$ obtained by restricting a_j to $W_\perp$ . Provided $W_\perp$ is nontrivial it is clear that these operators satisfy the CCRs on $W_\perp$ . Repeating the above argument, we can therefore identify a 2^n -dimensional subspace of $W_\perp$ on which we can compute the action of $\tilde a_j$ and $\tilde a_j^\dagger$ , and thus of a_j and $a_j^\dagger$ .

We may iterate this procedure many times, but the fact that is finite dimensional means that the process must eventually terminate. At the point of termination we will have broken up as a direct sum of some finite number of orthonormal 2^n -dimensional vector spaces, $W_1,W_2,\ldots,W_d$ , and on each vector space we will have an orthonormal basis with respect to which the action of a_j and $a_j^\dagger$ is known precisely.

Stated another way, we can introduce an orthonormal basis $|\alpha,k\rangle$ for , where $\alpha$ runs over all -bit vectors, and $k = 1,\ldots,d$ , and such that the action of the a_j and $a_j^\dagger$ is to leave invariant, and to act on $|\alpha\rangle$ as described above. In this representation it is clear that can be regarded as a tensor product $C^{2^n} \otimes C^d$ , with the action of a_j and $a_j^\dagger$ trivial on the C^d component. We will call this the occupation number representation for the Fermi algebra a_j .

It’s worth pausing to appreciate what has been achieved here: starting only from the CCRs for $a_1,\ldots,a_n$ we have proved that can be broken down into a tensor product of a 2^n -dimensional vector space and a -dimensional vector space, with the a_j s acting nontrivially only on the 2^n -dimensional component. Furthermore, the action of the a_j s is completely known. I think it’s quite remarkable that we can say so much: at the outset it wasn’t even obvious that the dimension of should be a multiple of 2^n !

When d=1 we will call this the fundamental representation for the Fermionic CCRs. (This is the terminology I use, but I don’t know if it is standard or not.) Up to a change of basis it is clear that all other representations can be obtained by taking a tensor product of the fundamental representation with the trivial action on a -dimensional vector space.

We’ve now understood the fundamental mathematical fact about fermions: the mere existence of operators satisfying Fermionic canonical commutation relations completely determines the action of those operators with respect to some suitable orthonormal occuptation number basis. That’s a very strong statement! In the next post we’ll use this technology to study a problem of direct physical interest: finding the energy spectrum and eigenstates of a Hamiltonian which is quadratic in terms of Fermi operators.

Permalink Comments off

Expander graphs V: random walks on expanders

June 6, 2005 at 12:37 pm · Filed under General

Back to expanders again. Today’s post looks at a simple application of expanders, showing that a random walk on an expander graph is likely to quickly escape from any sufficiently small subset of vertices. Intuitively, of course, this result is not surprising, but the exact quantitative form of the result turns out to be extremely useful in the next post, which is about decreasing the number of random bits used by a randomized algorithm.

Random walks on expanders

Many applications of expanders involve doing a random walk on the expander. We start at some chosen vertex, and then repeatedly move to any one of the neighbours, each time choosing a neighbour uniformly at random, and independently of prior choices.

To describe this random walk, suppose at some given time we have a probability distribution describing the probability of being at any given vertex in the graph . We then apply one step of the random walk procedure described above, i.e., selecting a neighbour of the current vertex uniformly at random. The updated probability distribution is easily verified to be:

$\tilde p = \frac{A(G)}{d} p.$

That is, the Markov transition matrix describing this random walk is just $\hat A(G) \equiv A(G)/d$ , i.e., up to a constant of proportionality the transition matrix is just the adjacency matrix. This relationship between the adjacency matrix and random walks opens up a whole new world of connections between graphs and Markov chains.

One of the most important connections is between the eigenvalues of Markov transition matrices and the rate at which the Markov chain converges to its stationary distribution. In particular, the following beautiful theorem tells us that when the uniform distribution is a stationary distribution for the chain, then the Markov chain converges to the uniform distribution exponentially quickly, at a rate determined by the second largest eigenvalue of .

Exercise: Show that if is a normal transition matrix for a Markov chain then $1 = \lambda_1(M) \geq \lambda_2(M) \geq \ldots$ .

Theorem: Suppose is a normal transition matrix for a Markov chain on states, with the uniform distribution $u = \vec 1/n$ as a stationary point, M u = u . Then for any starting distribution ,

$\| M^t p – u \|_1 \leq \sqrt{n} \lambda_2(M)^t,$

where $\| \cdot \|_1$ denotes the l_1 norm.

The normality condition in this theorem may appear a little surprising. The reason it’s there is to ensure that can be diagonalized. The theorem can be made to work for general , with the second largest eigenvalue replaced by the second largest singular value. However, in our situation is symmetric, and thus automatically normal, and we prefer the statement in terms of eigenvalues, since it allows us to make a connection to the expansion parameter of a graph. In particular, when $M = \hat A(G)$ we obtain:

$\| \hat A(G)^t p-u\|_1 \leq \sqrt{n} \left(\frac{\lambda_2(G)}{d}\right)^t.$

Combining this with our earlier results connecting the gap to the expansion parameter, we deduce that

$\| \hat A(G)^t p-u\|_1 \leq \sqrt{n} \left(1-\frac{h(G)^2}{2d^2}\right)^t.$

Thus, for a family of expander graphs, the rate of convergence of the Markov chain is exponentially fast in the number of time steps .

Exercise: Suppose is a transition matrix for a Markov chain. Show that the uniform distribution is a stationary point point for the chain, i.e., Mu = u , if and only if is doubly stochastic, i.e., has non-zero entries, and all rows and columns of the matrix sum to .

Proof: We start by working with the l_2 norm $\| \cdot \|_2$ . Since Mu = u we have M^t u = u , and so:

$\|M^t p – u \|_2 = \|M^t(p-u) \|_2.$

A computation shows that p-u is orthogonal to . But is an eigenvector of with the maximum eigenvalue, , and thus p-u must lie in the span of the eigenspaces with eigenvalues $\lambda_2(M),\lambda_3(M),\ldots$ . It follows that

$\|M^t(p-u)\|_2 \leq \lambda_2(M)^t \|p-u\|_2 \leq \lambda_2(M)^t,$

where we used the fact that $\| p-u\|_2 \leq 1$ , easily established by observing that $\|p-u\|_2$ is convex in , and thus must be maximized at an extreme point in the space of probability distributions; the symmetry of ensures that without loss of generality we may take $p = (1,0,\ldots,0)$ . To convert this into a result about the l_1 norm, we use the fact that in dimensions $\|v\|_1 \leq \sqrt{n} \|v\|_2$ , and thus we obtain

$\|M^t(p-u)\|_1 \leq \sqrt{n} \lambda_2(M)^t,$

which was the desired result. QED

What other properties do random walks on expanders have? We now prove another beautiful theorem which tells us that they “move around quickly”, in the sense that they are exponentially unlikely to stay for long within a given subset of vertices, , unless is very large.

More precisely, suppose is a subset of vertices, and we choose some vertex X_0 uniformly at random from the graph. Suppose we use X_0 as the starting point for a random walk, $X_0,\ldots,X_t$ , where X_t is the vertex after the th step. Let B(t) be the event that $X_j \in B$ for all in the range $0,\ldots,t$ . Then we will prove that:

$\mbox{Pr}(B(t)) \leq \left( \frac{\lambda_2(G)}{d} + \frac{|B|}{n} \right)^t$

Provided $\lambda_2(G)/d + |B|/n < 1$ , we get the desired exponential decrease in probability. For a family of expander graphs it follows that there is some constant $\epsilon > 0$ such that we get an exponential decrease for any such that $|B|/n < \epsilon$ . These results are special cases of the following more general theorem about Markov chains.

Theorem: Let X_0 be uniformly distributed on states, and let $X_0,\ldots,X_t$ be a time-homogeneous Markov chain with transition matrix . Suppose the uniform distribution is a stationary point of , i.e., Mu = u . Let be a subset of the states, and let B(t) be the event that $X_j \in B$ for all $j \in 0,\ldots,t$ . Then

$\mbox{Pr}(B(t)) \leq \left( \lambda_2(M) + \frac{|B|}{n} \right)^t.$

Proof: The first step in the proof is to observe that:

$\mbox{Pr}(B(t)) = \|(PMP)^t P u \|_1,$

where the operator projects onto the vector space spanned by those basis vectors corresponding to elements of . This equation is not entirely obvious, and proving it is a good exercise for the reader.

The next step is to prove that $\| PMP \| \leq \lambda_2(M)+|B|/n$ , where the norm here is the operator norm. We will do this below, but note first that once this is done, the result follows, for we have

$\mbox{Pr}(B(t)) = \| (PMP)^t P u \|_1 \leq \sqrt{n} \| (PMP)^t P u \|_2$

by the standard inequality relating l_1 and l_2 norms, and thus

$\mbox{Pr}(B(t)) \leq \sqrt{n} \| PMP \|^t \| P u \|_2,$

by definition of the operator norm, and finally

$\mbox{Pr}(B(t)) \leq \left( \lambda_2(M)+\frac{|B|}{n} \right)^t,$

where we used the assumed inequality for the operator norm, and the observation that $\| P u \|_2 = \sqrt{|B|}/n \leq 1/\sqrt{n}$ .

To prove the desired operator norm inequality, $\| PMP \| \leq \lambda_2(M)+|B|/n$ , suppose is a normalized state such that $\| PMP \| = |v^T PMP v|$ . Decompose $Pv = \alpha u + \beta u_\perp$ , where $u_\perp$ is a normalized state orthogonal to . Since $\|P v \|_2 \leq \|v \|_2 = 1$ we must have $|\beta| \leq 1$ . Furthermore, multiplying $Pv = \alpha u + \beta u_\perp$ on the left by nu^T shows that $\alpha = n u^T P v$ . It follows that $|\alpha|$ is maximized by choosing to be uniformly distributed over , from which it follows that $|\alpha| \leq \sqrt{|B|}$ . A little algebra shows that

$v^T PMP v = \alpha^2 u^T M u + \beta^2 u_\perp^T M u_\perp.$

Applying $|\alpha| \leq \sqrt{|B|}$ , u^T M u = u^Tu = 1/n , $|\beta| \leq 1$ , and $u_\perp^T M u_\perp \leq \lambda_2(M)$ gives

$v^T P M P v \leq \frac{|B|}{n} + \lambda_2(M),$

which completes the proof. QED

The results in today’s post are elegant, but qualitatively unsurprising. (Of course, having elegant quantitative statements of results that are qualitatively clear is worthwhile in its own right!) In the next post we’ll use these ideas to develop a genuinely surprising application of expanders, to reducing the number of random bits required by a probabilistic algorithm in order to achieve a desired success probability.

Archive for June, 2005

Fermions and the Jordan-Wigner transform V: Diagonalization Continued

Fermions and the Jordan-Wigner transform IV: Diagonalizing Fermi Quadratic Hamiltonians

Diagonalizing a Fermi quadratic Hamiltonian

Expander graphs: the complete notes

Expander graphs VI: reducing randomness

Reducing the number of random bits required by an algorithm

Adios

New paper: Operator quantum error correction

Appendix to my posts on Fermions and the Jordan-Wigner transform

Appendix on mutually commuting observables

Fermions and the Jordan-Wigner transform III: Consequences of the Canonical Commutation Relations

Consequences of the fermionic CCRs

Expander graphs V: random walks on expanders

Random walks on expanders

Quote

General

Favourite Posts

Active Projects

Past Projects

Online Communities

Archives

Meta