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
I suspect that would have something to do with the form of the matrices whose eigenvalues you want, probably because they represent a physical system. In general it’s so hard that you have to do something other than just solve a system of equations (and my applied math and optimization profs were explicit about how hard it is in general). Perhaps n is small enough that the matrices just aren’t that big, relative to our currently available computer power?
I didn’t state the problem very clearly. Here’s a better version.
I’m just asking what the running time of an algorithm to find the eigenvalues is, given the size of the matrix (n), and the desired accuracy (epsilon). Ideally it’d be low degree polynomial in n and in 1/epsilon. I know this is true as a function of n, and think it’s true as a function of 1/epsilon, but I don’t know the full picture.
Of course, given the size of the starting matrix – a 2^n by 2^n Hamiltonian – this is incredibly fast! The only place physics enters the picture is in the transformation allowing us to go from the 2^n by 2^n matrix to an n by n matrix.
The complexity of finding eigenvectors and their corresponding eigenvalues for general d-dimensional matrices to accuracy epsilon is, if I recall correctly, O(log(epsilon^(-1) d^2). However the constant in this case is huge and most people prefer an algorithm with O(log(epsilon^(-1)d^3)).
Thanks Dave. That polylog behaviour is pretty amazing! I presume you’re missing a power in the logarithm? Or is it really just log(1/epsilon)?
Oops. Those should be O(log(epsilon^(-1))d^2) and O(log(epsilon^(-1))d^3). Darned right “)”.
Any chance of that PDF coming out sometime soon? The posts are very interesting (and it is so hard to find advanced physics articles written in a didactic style … so I really should say thanks!), but a nice PDF print out is so much more convenient for reading.
Hi Marcus — I’ve just added the pdf notes. Thanks for the kind words about the notes!