Month: July 2005

Quantiki, a wiki based around quantum information. Could be very useful, with enough content. Maybe the quantum bloggers should look to see if any of their old content is useful, and perhaps look into a Creative Commons license.

If you haven’t seen it yet, I strongly suggest taking a look at Cosmic Variance, which is a really terrific new group blog on things physical and cosmological.

Here’s Scott Aaronson’s list. The problems are certainly all very good ones. Here’s a quick list of five questions I like, off the top of my head:

• How can we build a quantum computer?
• How quickly can we simulate a desired physical operation on a quantum computer? An exact formula would be nice, or at least good bounds, preferably completely general, and both upper and lower bounds. I’d guess most computer scientists think this is a hopelessly optimistic goal; I’m nothing if not optimistic.
• What makes quantum computers powerful?
• How powerful are they, relative to classical computer?
• What physical resources are necessary and sufficient to do quantum computation? This is interesting in both the noise-free and noisy cases. Even in the noise-free case we currently know very little, for example, about when measurement-based quantum computation is possible. The problem is much harder in the noisy case (and includes determining the threshold).

Update: After posting that, I’ve decided I have fairly serious reservations about how I express the second hope. Can we really hope for a formula for the number of quantum gates required to synthesize a quantum operation? Although I haven’t thought it through in detail, it seems highly unlikely that there is any reasonably general computable formula for the time complexity of some specifed (but arbitrary) family of operations. However, this doesn’t mean that we can’t obtain a lot more general insight into this question than we currently have.

The last post! A single pdf will follow in a day or so.

Today’s post discusses a surprising connection between the Fermionic ideas we’ve been discussing up to now, and one-dimensional spin systems. In particular, 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.

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 Jordan-Wigner transform

In this post we describe the Jordan-Wigner transform, explaining how it can be used to map a system of qubits (i.e., spin-[tex]\frac 12[/tex] systems) to a system of Fermions, and vice versa. We also explain a nice applications of these ideas, to solving one-dimensional quantum spin systems.

Suppose we have an [tex]n[/tex]-qubit system, with the usual state space [tex]C^{2^n}[/tex], and Pauli operators [tex]X_j, Y_j,Z_j[/tex] acting on qubit [tex]j[/tex]. We are going to use these operators to define a set of [tex]a_j[/tex] operators acting on [tex]C^{2^n}[/tex], and satisfying the Fermionic CCRs.

To begin, suppose for the sake of argument that we have found such a set of operators. Then from our earlier discussion the action of the [tex]a_j[/tex] operators in the occupation number representation [tex]|\alpha\rangle = |\alpha_1,\ldots,\alpha_n\rangle[/tex] must be as follows:

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

If we identify the occupation number state [tex]|\alpha\rangle[/tex] with the corresponding computational basis state [tex]|\alpha\rangle[/tex], then this suggests taking as our definition

[tex] a_j \equiv -\left( \otimes_{k=1}^{j-1} Z_k \right) \otimes \sigma_j, [/tex]

where [tex]\sigma_j[/tex] is used to denote the matrix [tex]\sigma \equiv |0\rangle \langle 1|[/tex] acting on the [tex]j[/tex]th qubit. It is easily verified that these operators satisfy the Fermionic CCRs. This definition of the [tex]a_j[/tex] is known as the Jordan-Wigner transform. It allows us to define a set of operators [tex]a_j[/tex] satisfying the Fermionic CCRs in terms of the usual operators we use to describe qubits, or spin-[tex]\frac 12[/tex] systems.

The Jordan-Wigner transform can be inverted, allowing us to express the Pauli operators in terms of the Fermionic operators [tex]a_1,\ldots,a_n[/tex]. In particular, we have

[tex] Z_j = a_ja_j^\dagger-a_j^\dagger a_j. [/tex]

This observation may also be used to obtain an expression for [tex]X_j[/tex] by noting that [tex]X_j = \sigma_j +\sigma_j^\dagger[/tex], and thus:

[tex] X_j = -(Z_1 \ldots Z_{j-1}) (a_j+a_j^\dagger). [/tex]

Substituting in the expressions for [tex]Z_1,\ldots,Z_{j-1}[/tex] in terms of the Fermionic operators gives the desired expression for [tex]X_j[/tex] in terms of the Fermionic operators. Similarly, we have

[tex] Y_j = i (Z_1 \ldots Z_{j-1}) (a_{j}^\dagger-a_{j}), [/tex]

which, together with the expression for the [tex]Z_j[/tex] operators, enables us to express [tex]Y_j[/tex] solely in terms of the Fermionic operators.

These expressions for [tex]X_j[/tex] and [tex]Y_j[/tex] are rather inconvenient, involving as they do products of large numbers of Fermi operators. Remarkably, however, for certain simple products of Pauli operators it is possible to obtain quite simple expressions in terms of the Fermi operators. In particular, with a little algebra we see that:

[tex] Z_j = a_ja_j^\dagger – a_j^\dagger a_j [/tex]

[tex] X_jX_{j+1} = (a_j^\dagger-a_j)(a_{j+1}+a_{j+1}^\dagger ) [/tex]

[tex] Y_jY_{j+1} = -(a_j^\dagger+a_j)(a_{j+1}^\dagger-a_{j+1}) [/tex]

[tex] X_jY_{j+1} = i(a_j^\dagger-a_j) (a_{j+1}^\dagger-a_{j+1}) [/tex]

[tex] Y_jX_{j+1} = i(a_j^\dagger+a_j) (a_{j+1}^\dagger+a_{j+1}). [/tex]

Suppose now that we have an [tex]n[/tex]-qubit Hamiltonian [tex]H[/tex] that can be expressed as a sum over operators from the set [tex]Z_j, X_jX_{j+1},Y_jY_{j+1},X_jY_{j+1}[/tex] and [tex]Y_{j}X_{j+1}[/tex]. An example of such a Hamiltonian is the transverse Ising model,

[tex] H = \alpha \sum_j Z_j + \beta \sum_j X_j X_{j+1}, [/tex]

which describes a system of magnetic spins with nearest neighbour couplings of strength [tex]\beta[/tex] along their [tex]\hat x[/tex] axes, and in an external magnetic field of strength [tex]\alpha[/tex] along the [tex]\hat z[/tex] axis.

For any such Hamiltonian, we see that it is possible to re-express the Hamiltonian as a Fermi quadratic Hamiltonian. As we saw in an earlier post, determining the energy levels is then a simple matter of finding the eigenvalues of a [tex]2n \times 2n[/tex] matrix, which can be done very quickly. In particular, finding the ground state energy is simply a matter of finding the smallest eigenvalue of that matrix, which is often particularly easy. In the case of models like the transverse Ising model, it is even possible to do this diagonalization analytically, giving rise to exact expressions for the energy spectrum. Details can be found in the paper by Lieb, Schulz and Mattis mentioned earlier, or books such as the well-known book by Sachdev on quantum phase transitions.

Exercise: What other products of Pauli operators can be expressed as quadratics in Fermi operators?

Problem: I’ve made some pretty vague statements about finding the spectrum of a matrix being “easy”. However, I must admit that I’m speaking empirically here, in the sense that in practice I know this is easily done on a computer, but I don’t know a whole lot about the computational complexity of the problem. One obvious observation is that finding the spectrum is equivalent to finding the roots of the characteristic equation, which is easily computed, so the problem may be viewed as being about the computational complexity of root-finding.

Finis

Google is amazing: google print; and google earth. I’ve taken the liberty of picking a good sample application of google print in the link.