Simple Algorithm
Quantum Computing · Rydberg State · 30 min

Fermion-to-Qubit Mappings

Jordan–Wigner, Bravyi–Kitaev and second quantization.

Electrons anticommute; qubits on different sites commute. Every quantum simulation of fermions must bridge that gap, and the bridge you pick sets the Pauli weight of every term, the circuit depth, the qubit count, and which symmetries you can exploit. Jordan–Wigner pays with strings of length O(M)\order{M}, Bravyi–Kitaev with O(log⁡M)\order{\log M}, and nothing ancilla-free does better than logarithmic.

What you’ll learn

  • Prove that representing MM fermionic modes with Pauli operators requires at least MM qubits, via the Majorana (Clifford-algebra) picture.
  • Prove the canonical anticommutation relations for the Jordan–Wigner transformation and compute the Pauli images of hopping terms.
  • Construct the parity and Bravyi–Kitaev encodings as linear maps on occupation vectors, and derive their update, parity and flip sets.
  • Taper qubits using Z2\Z_2 symmetries with an explicit Clifford transformation, and avoid the wrong-particle-number pitfall.

Anticommuting modes on commuting qubits

MM fermionic modes carry operators aja_j obeying {aj,ak†}=δjk\acomm{a_j}{a_k^\dagger}=\delta_{jk} and {aj,ak}=0\acomm{a_j}{a_k}=0. It is cleanest to trade them for 2M2M Hermitian Majorana operators

γ2j=aj+aj†,γ2j+1=i (aj†−aj),{γμ,γν}=2δμνI,\gamma_{2j}=a_j+a_j^\dagger,\qquad\gamma_{2j+1}=i\,(a_j^\dagger-a_j),\qquad\acomm{\gamma_\mu}{\gamma_\nu}=2\delta_{\mu\nu}\id,

so that aj=12(γ2j+iγ2j+1)a_j=\tfrac12(\gamma_{2j}+i\gamma_{2j+1}). A fermion-to-qubit mapping (without ancillas) is a choice of 2M2M pairwise anticommuting Pauli strings on nn qubits to play the role of the γμ\gamma_\mu, together with the identification of the vacuum.

Jordan–Wigner, precisely

Jordan–Wigner stores occupations directly, ∣n0⋯nM−1⟩↦∣n0⟩⊗⋯⊗∣nM−1⟩\ket{n_0\cdots n_{M-1}}\mapsto\ket{n_0}\otimes\cdots\otimes\ket{n_{M-1}}, and sets

aj=Z<j σj−,aj†=Z<j σj+,σ+=∣1⟩ ⁣⟨0∣=12(X−iY),σ−=∣0⟩ ⁣⟨1∣,a_j=Z_{<j}\,\sigma^-_j,\qquad a_j^\dagger=Z_{<j}\,\sigma^+_j,\qquad\sigma^+=\ketbra10=\tfrac12(X-iY),\quad\sigma^-=\ketbra01,

with Z<j:=Z0Z1⋯Zj−1Z_{<j}:=Z_0Z_1\cdots Z_{j-1}. In Majorana form, γ2j=Z<jXj\gamma_{2j}=Z_{<j}X_j and γ2j+1=Z<jYj\gamma_{2j+1}=Z_{<j}Y_j: weight j+1j+1, average (M+1)/2(M+1)/2.

DerivationProof of the anticommutation relations
  1. {Z,σ±}=0,{σ−,σ+}=I,(σ±)2=0\acomm{Z}{\sigma^\pm}=0,\qquad\acomm{\sigma^-}{\sigma^+}=\id,\qquad(\sigma^\pm)^2=0

    Single-qubit facts: Zσ+=−σ+=−σ+ZZ\sigma^+=-\sigma^+=-\sigma^+Z, and similarly for σ−\sigma^-.

  2. j<k:ajak†=σj−Zj Z(j,k) σk+,ak†aj=Zjσj− Z(j,k) σk+j<k:\qquad a_ja_k^\dagger=\sigma^-_jZ_j\,Z_{(j,k)}\,\sigma^+_k,\qquad a_k^\dagger a_j=Z_j\sigma^-_j\,Z_{(j,k)}\,\sigma^+_k

    Write Z<k=Z<jZjZ(j,k)Z_{<k}=Z_{<j}Z_jZ_{(j,k)}, where Z(j,k)Z_{(j,k)} is the string strictly between jj and kk. The two copies of Z<jZ_{<j} square to I\id, and operators on different sites commute. The products differ only in the order of σj−\sigma_j^- and ZjZ_j.

  3. {aj,ak†}={σj−,Zj} Z(j,k) σk+=0\acomm{a_j}{a_k^\dagger}=\acomm{\sigma^-_j}{Z_j}\,Z_{(j,k)}\,\sigma^+_k=0

    Site jj supplies the relative minus sign. The same computation gives {aj,ak}=0\acomm{a_j}{a_k}=0.

  4. {aj,aj†}=Z<j2 {σj−,σj+}=I■\acomm{a_j}{a_j^\dagger}=Z_{<j}^2\,\acomm{\sigma^-_j}{\sigma^+_j}=\id\qquad\blacksquare

    On a single mode the strings cancel and the qubit algebra does the rest.

ap†aq+aq†ap=12(XpXq+YpYq)Zp+1⋯Zq−1,np=12(I−Zp)a_p^\dagger a_q+a_q^\dagger a_p=\tfrac12\left(X_pX_q+Y_pY_q\right)Z_{p+1}\cdots Z_{q-1},\qquad n_p=\tfrac12(\id-Z_p)
Hopping (p<qp<q) has weight q−p+1q-p+1; number and Coulomb terms are local. A double excitation plus its conjugate, ap†aq†aras+h.c.a_p^\dagger a_q^\dagger a_ra_s+\text{h.c.} with distinct indices, expands into 8 Pauli strings carrying ZZ strings over the intervening index ranges.
Check your understanding

Under Jordan–Wigner, what is a2†a5+a5†a2a_2^\dagger a_5+a_5^\dagger a_2?

  1. 12(X2X5+Y2Y5)\tfrac12(X_2X_5+Y_2Y_5)
  2. 12(X2X5+Y2Y5) Z3Z4\tfrac12(X_2X_5+Y_2Y_5)\,Z_3Z_4
  3. 12(X2X5+Y2Y5) Z0Z1\tfrac12(X_2X_5+Y_2Y_5)\,Z_0Z_1
  4. 12(X2X5−Y2Y5) Z3Z4\tfrac12(X_2X_5-Y_2Y_5)\,Z_3Z_4
Show the answer

B. 12(X2X5+Y2Y5) Z3Z4\tfrac12(X_2X_5+Y_2Y_5)\,Z_3Z_4

The strings Z<2Z_{<2} are common to both operators and cancel; the modes strictly between, 3 and 4, remain, and σ2+σ5−+σ2−σ5+=12(X2X5+Y2Y5)\sigma_2^+\sigma_5^-+\sigma_2^-\sigma_5^+=\tfrac12(X_2X_5+Y_2Y_5).

Parity and Bravyi–Kitaev encodings

Jordan–Wigner, parity and Bravyi–Kitaev are all linear encodings: the occupation vector n∈F2M\mathbf n\in\mathbb F_2^M is stored as b=An(mod2)\mathbf b=A\mathbf n\pmod2 for an invertible binary matrix AA. To implement aj†a_j^\dagger you need three pieces of information, each a set of qubits:

  • the update set U(j)U(j): qubits whose stored value contains njn_j and must flip with it;
  • the parity set P(j)P(j): qubits whose sum is n0+⋯+nj−1n_0+\cdots+n_{j-1}, giving the fermionic sign;
  • the flip set F(j)F(j): qubits that, with qubit jj, determine njn_j.

The Pauli weight of aj†a_j^\dagger is about ∣U(j)∣+∣P(j)∣+1\abs{U(j)}+\abs{P(j)}+1.

AJW=I,Apar=(1000110011101111),ABK=(1000110000101111)A_{\text{JW}}=\id,\qquad A_{\text{par}}=\begin{pmatrix}1&0&0&0\\1&1&0&0\\1&1&1&0\\1&1&1&1\end{pmatrix},\qquad A_{\text{BK}}=\begin{pmatrix}1&0&0&0\\1&1&0&0\\0&0&1&0\\1&1&1&1\end{pmatrix}
The three encodings for M=4M=4. Jordan–Wigner stores occupations, the parity encoding stores prefix parities bj=n0+⋯+njb_j=n_0+\cdots+n_j, and Bravyi–Kitaev stores parities of dyadic blocks (a Fenwick tree).

In the parity encoding the sign is local (P(j)={j−1}P(j)=\{j-1\}) but the update set is everything above jj:

aj†=12(Zj−1Xj−iYj)Xj+1⋯XM−1.a_j^\dagger=\tfrac12\left(Z_{j-1}X_j-iY_j\right)X_{j+1}\cdots X_{M-1}.

Jordan–Wigner has the opposite profile. Bravyi–Kitaev balances them: for M=2mM=2^m, qubit jj stores nkn_k summed over the dyadic block ending at jj (for M=8M=8: b0=n0b_0=n_0, b1=n0+n1b_1=n_0+n_1, b2=n2b_2=n_2, b3=n0+⋯+n3b_3=n_0+\cdots+n_3, b4=n4b_4=n_4, b5=n4+n5b_5=n_4+n_5, b6=n6b_6=n_6, b7=n0+⋯+n7b_7=n_0+\cdots+n_7).

DerivationWorked example: a₅† in the Bravyi–Kitaev encoding (M = 8)
  1. U(5)={7},P(5)={3,4},F(5)={4}U(5)=\{7\},\qquad P(5)=\{3,4\},\qquad F(5)=\{4\}

    n5n_5 is contained in b5b_5 and b7b_7; the prefix n0+⋯+n4=b3+b4n_0+\cdots+n_4=b_3+b_4; and n5=b5⊕b4n_5=b_5\oplus b_4.

  2. a5†=12 X7(X5Z4Z3−iY5Z3)=12 X7Z3(X5Z4−iY5)a_5^\dagger=\tfrac12\,X_7\left(X_5Z_4Z_3-iY_5Z_3\right)=\tfrac12\,X_7Z_3\left(X_5Z_4-iY_5\right)

    The Seeley–Richard–Love form for odd jj: XX on the update set, ZZ on the parity set for the XjX_j part and on P(j)∖F(j)P(j)\setminus F(j) for the YjY_j part.

  3. b4=0:  X5−iY5=2∣1⟩ ⁣⟨0∣5,b4=1:  −X5−iY5=−2∣0⟩ ⁣⟨1∣5b_4=0:\ \ X_5-iY_5=2\ketbra10_5,\qquad b_4=1:\ \ -X_5-iY_5=-2\ketbra01_5

    Check: if b4=0b_4=0 the operator needs b5=0b_5=0 (so n5=0n_5=0) and sets b5=1b_5=1; if b4=1b_4=1 it needs b5=1b_5=1 (again n5=0n_5=0) and sets b5=0b_5=0. Either way n5n_5 goes 0→10\to1.

  4. sign=(−1)b3⋅(−1)b4=(−1)n0+⋯+n4,X7: b7↦b7⊕1\text{sign}=(-1)^{b_3}\cdot(-1)^{b_4}=(-1)^{n_0+\cdots+n_4},\qquad X_7:\ b_7\mapsto b_7\oplus1

    The Z3Z_3 factor and the ±\pm from the b4b_4 branch give exactly the Jordan–Wigner sign, and X7X_7 updates the total parity. Weight 4, versus 6 under Jordan–Wigner; the gap grows to O(log⁡M)\order{\log M} versus O(M)\order{M}.

MappingQubitsWorst-case weight of aja_jNotes
Jordan–WignerMMO(M)\order{M}simplest; local for 1D chains
ParityMMO(M)\order{M}two qubits removable for free (spin-sector parities)
Bravyi–KitaevMMO(log⁡M)\order{\log M}Fenwick-tree bookkeeping
Ternary treeMM⌈log⁡3(2M+1)⌉\lceil\log_3(2M+1)\rceil per Majoranaoptimal on average (Jiang et al. 2020)
Verstraete–Cirac, BK superfast, compact>M>MO(1)\order{1} for lattice hoppingancillas plus stabilizer constraints
Lower Pauli weight means shallower circuits for each Pauli exponential: e−iθP/2e^{-i\theta P/2} for a weight-ww string costs 2(w−1)2(w-1) CNOTs as a parity ladder.

Symmetries and qubit tapering

Molecular Hamiltonians conserve the electron numbers N↑N_\uparrow and N↓N_\downarrow, hence their parities, and often point-group symmetries. After mapping, such a symmetry is a Pauli string τ\tau with [H,τ]=0\comm{H}{\tau}=0. Since H=∑jcjPjH=\sum_jc_jP_j and τPjτ=±Pj\tau P_j\tau=\pm P_j, commuting with HH forces every term to commute with τ\tau.

DerivationThe Clifford behind tapering
  1. Ui=12(Xq(i)+τi),{Xq(i),τi}=0,[Xq(i),τl]=0 (l≠i)U_i=\tfrac{1}{\sqrt2}\left(X_{q(i)}+\tau_i\right),\qquad\acomm{X_{q(i)}}{\tau_i}=0,\quad\comm{X_{q(i)}}{\tau_{l}}=0\ (l\ne i)

    For ZZ-type symmetries (the usual case for parities), Gaussian elimination over F2\mathbb F_2 yields generators and pivot qubits q(i)q(i) where τi\tau_i acts as ZZ and every other generator acts trivially. General Pauli symmetries are first rotated to ZZ-type by a Clifford.

  2. Ui2=12(2 I+{Xq(i),τi})=IU_i^2=\tfrac12\left(2\,\id+\acomm{X_{q(i)}}{\tau_i}\right)=\id

    UiU_i is Hermitian and squares to the identity, so it is unitary (and a Clifford: it maps Paulis to Paulis).

  3. Ui τi Ui=12(XτX+Xττ+ττX+τττ)=12(−τ+2X+τ)=Xq(i)U_i\,\tau_i\,U_i=\tfrac12\left(X\tau X+X\tau\tau+\tau\tau X+\tau\tau\tau\right)=\tfrac12\left(-\tau+2X+\tau\right)=X_{q(i)}

    Abbreviating X=Xq(i)X=X_{q(i)} and τ=τi\tau=\tau_i, and using XτX=−τX\tau X=-\tau and τ2=I\tau^2=\id.

  4. [Pj,τi]=0 ⇒ [UPjU†,Xq(i)]=0\comm{P_j}{\tau_i}=0\ \Rightarrow\ \comm{U P_jU^\dagger}{X_{q(i)}}=0

    Conjugation preserves commutation, so every transformed term acts on qubit q(i)q(i) as I\id or XX. In each symmetry sector Xq(i)=±1X_{q(i)}=\pm1, and the qubit drops out.

With the parity encoding the Clifford is unnecessary. Order spin-orbitals as all spin-up, then all spin-down. Then bM/2−1=N↑ mod 2b_{M/2-1}=N_\uparrow\bmod2 and bM−1=N mod 2b_{M-1}=N\bmod2, and no term ever flips them: they appear only as ZZ's, and two qubits disappear at once. Try it on a two-electron state of H₂ in this ordering (modes: bonding↑, antibonding↑, bonding↓, antibonding↓), prepared as an equal superposition of the Hartree–Fock determinant ∣1010⟩\ket{1010} and the double excitation ∣0101⟩\ket{0101}.

Check your understanding

A 12-qubit Hamiltonian commutes with 3 independent, pairwise commuting Pauli strings (none of them ±I\pm\id, and −I-\id not in the group they generate). What does tapering produce?

  1. One Hamiltonian on 9 qubits
  2. Three Hamiltonians on 9 qubits
  3. Eight Hamiltonians on 9 qubits, one per symmetry sector
  4. Eight Hamiltonians on 6 qubits
Show the answer

C. Eight Hamiltonians on 9 qubits, one per symmetry sector

Each independent Z2\Z_2 symmetry removes one qubit and splits the problem into two sectors: 12−3=912-3=9 qubits and 23=82^3=8 sectors. You then pick the sector containing the state you want (the right electron-number parities).

Key takeaways

  • 2M2M Majoranas must map to pairwise anticommuting Pauli strings; the Clifford-algebra argument forces at least MM qubits and makes some nonlocality unavoidable.
  • Jordan–Wigner is exact and simple, with ZZ strings of length O(M)\order{M} (local in 1D, O(N)\order{\sqrt N} in 2D snake order).
  • Linear encodings b=An\mathbf b=A\mathbf n trade update sets against parity sets: parity has local signs but long updates; Bravyi–Kitaev achieves O(log⁡M)\order{\log M}, and ternary trees reach the optimal ≈log⁡3(2M)\approx\log_3(2M).
  • Z2\Z_2 symmetries of HH can be rotated onto single-qubit XX's by a Clifford and removed, one qubit per symmetry; the parity encoding removes two for free.
  • The qubit Hamiltonian lives on all of Fock space: always fix the particle-number sector you mean.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

Why can't aja_j be represented by an operator acting only on qubit jj?

  1. Because aja_j is not Hermitian
  2. Because a single qubit has only two states, while a mode has more
  3. Because for j≠kj\ne k, aja_j and aka_k must anticommute, while operators on different qubits commute
  4. It can: aj=σj−a_j=\sigma_j^- works because the signs cancel in the Hamiltonian
Show the answer

C. Because for j≠kj\ne k, aja_j and aka_k must anticommute, while operators on different qubits commute

The algebra forces nonlocality. Local operators on disjoint qubits commute, so {aj,ak}=0\acomm{a_j}{a_k}=0 with ajak≠0a_j a_k\ne0 is impossible for them; strings (or ancillas) are needed.

Question 2

For M=1024M=1024 modes, roughly what Pauli weight does a1023†a_{1023}^\dagger (the last mode) have under Jordan–Wigner and under Bravyi–Kitaev?

  1. About 1024 and about 10
  2. About 10 and about 1024
  3. About 1024 under both
  4. 1 under both
Show the answer

A. About 1024 and about 10

Jordan–Wigner needs Z0⋯Z1022Z_0\cdots Z_{1022} plus XX or YY on qubit 1023: weight 1024. Bravyi–Kitaev's update, parity and flip sets are each of size at most log⁡21024=10\log_21024=10, so the weight is O(10)\order{10}.

Question 3

You diagonalize the 4-qubit Jordan–Wigner Hamiltonian of H₂ exactly. Is its smallest eigenvalue guaranteed to be the energy of the neutral two-electron ground state?

  1. Yes, by the variational principle
  2. No: the qubit Hamiltonian acts on every electron number from 0 to 4, so the lowest eigenvalue may belong to a different NN
  3. Yes, because Jordan–Wigner conserves particle number
  4. No, because Jordan–Wigner introduces approximation errors
Show the answer

B. No: the qubit Hamiltonian acts on every electron number from 0 to 4, so the lowest eigenvalue may belong to a different NN

Second-quantized Hamiltonians conserve NN but act on all sectors. You must restrict to the N=2N=2 sector (and the desired spin), for example by tapering parities plus number-conserving states or penalty terms.

Question 4

In the parity encoding with spin-orbitals ordered all spin-up then all spin-down, why can qubits M/2−1M/2-1 and M−1M-1 be removed without any Clifford transformation?

  1. They store N↑ mod 2N_\uparrow\bmod2 and N mod 2N\bmod2, which no term changes, so they appear only as I\id or ZZ
  2. They are never used by the Hartree–Fock state
  3. They store occupations of the highest orbitals, which are always empty
  4. Because the parity encoding has O(log⁡M)\order{\log M} weight
Show the answer

A. They store N↑ mod 2N_\uparrow\bmod2 and N mod 2N\bmod2, which no term changes, so they appear only as I\id or ZZ

bM/2−1=n0+⋯+nM/2−1=N↑ mod 2b_{M/2-1}=n_0+\cdots+n_{M/2-1}=N_\uparrow\bmod2 and bM−1=N mod 2b_{M-1}=N\bmod2. Number- and spin-conserving terms never flip them, so they act diagonally and can be replaced by their eigenvalues.

Further reading

  • P. Jordan & E. Wigner, "Über das Paulische Äquivalenzverbot", Z. Phys. 47, 631 (1928).
  • S. B. Bravyi & A. Yu. Kitaev, "Fermionic quantum computation", Ann. Phys. 298, 210 (2002).
  • J. T. Seeley, M. J. Richard & P. J. Love, "The Bravyi–Kitaev transformation for quantum computation of electronic structure", J. Chem. Phys. 137, 224109 (2012).
  • S. Bravyi, J. M. Gambetta, A. Mezzacapo & K. Temme, "Tapering off qubits to simulate fermionic Hamiltonians", arXiv:1701.08213 (2017).
  • Z. Jiang, A. Kalev, W. Mruczkiewicz & H. Neven, "Optimal fermion-to-qubit mapping via ternary trees with applications to reduced quantum states learning", Quantum 4, 276 (2020).