QuantumCore

Lesson 38 · 95 min · advanced

Hamiltonian-Evolution Encoding & Trotterisation

Loading progress…

Hamiltonian-evolution encoding writes a data point xx into the generator of a time evolution, ∣ϕ(x)⟩=e−iH(x)t∣ψ0⟩\lvert\phi(x)\rangle=e^{-iH(x)t}\lvert\psi_0\rangle. This lesson proves that a Hamiltonian built from products of Pauli-ZZ operators is diagonal and that its evolution factorises exactly into commuting pieces, compiles every piece with the identity e−iθ2Z⊗Z=CNOT01(I⊗RZ(θ))CNOT01e^{-i\frac\theta2Z\otimes Z}=\mathrm{CNOT}_{01}(I\otimes R_Z(\theta))\mathrm{CNOT}_{01}, its CNOT-ladder generalisation and the basis changes X=HZHX=HZH, Y=RX(−π2)ZRX(π2)Y=R_X(-\tfrac\pi2)ZR_X(\tfrac\pi2), proves the first-order Trotter bound ∥E∥≤t22r∥[A,B]∥\lVert E\rVert\le\frac{t^2}{2r}\lVert[A,B]\rVert and the second-order bound O(t3/r2)O(t^3/r^2) from the variation-of-parameters formula, and derives the ZZ feature map of Havlíček et al. together with an honest account of its conjectured classical hardness.

Prerequisites: Angle & Phase Encoding, Postulate 2: Unitary Evolution & the Schrödinger Equation

Objectives and key results

  • Define Hamiltonian-evolution encoding x↦e−iH(x)t∣ψ0⟩x\mapsto e^{-iH(x)t}\lvert\psi_0\rangle and show that angle encoding is its special case H(x)=12∑jxjXjH(x)=\tfrac12\sum_jx_jX_j.

  • Prove that commuting exponentials multiply, eA+B=eAeBe^{A+B}=e^Ae^B for AB=BAAB=BA, and that H(x)=∑SϕS(x)∏j∈SZjH(x)=\sum_S\phi_S(x)\prod_{j\in S}Z_j generates a diagonal evolution with phases e−it∑SϕS(x)(−1)∑j∈Sbje^{-it\sum_S\phi_S(x)(-1)^{\sum_{j\in S}b_j}}.

  • Prove the exact compilation e−iθ2Z⊗Z=CNOT01(I⊗RZ(θ))CNOT01e^{-i\frac\theta2Z\otimes Z}=\mathrm{CNOT}_{01}(I\otimes R_Z(\theta))\mathrm{CNOT}_{01}, extend it to Z⊗kZ^{\otimes k} by induction, and handle XX and YY factors by basis change with the correct time order.

  • Prove the first-order Trotter–Suzuki bound ∥e−i(A+B)t−(e−iAt/re−iBt/r)r∥≤t22r∥[A,B]∥\big\lVert e^{-i(A+B)t}-(e^{-iAt/r}e^{-iBt/r})^r\big\rVert\le\frac{t^2}{2r}\lVert[A,B]\rVert via the variation-of-parameters (Duhamel) formula and the telescoping lemma.

  • Prove the second-order (symmetric) bound t312r2∥[B,[B,A]]∥+t324r2∥[A,[A,B]]∥\frac{t^3}{12r^2}\lVert[B,[B,A]]\rVert+\frac{t^3}{24r^2}\lVert[A,[A,B]]\rVert and explain why the second-order term cancels.

  • Write the ZZ feature map in the Qiskit convention, relate P(2φ)=eiφRZ(2φ)P(2\varphi)=e^{i\varphi}R_Z(2\varphi), and state precisely what is and is not known about the classical hardness of its kernel.

definition · Hamiltonian-evolution encoding
∣ϕ(x)⟩=e−iH(x)t∣ψ0⟩,H(x)=∑SϕS(x)∏j∈SZj ⇒ e−iH(x)t∣b⟩=e−it∑SϕS(x)(−1)∑j∈Sbj∣b⟩\lvert\phi(x)\rangle=e^{-iH(x)t}\lvert\psi_0\rangle,\qquad H(x)=\sum_{S}\phi_S(x)\prod_{j\in S}Z_j\ \Rightarrow\ e^{-iH(x)t}\lvert b\rangle=e^{-it\sum_S\phi_S(x)(-1)^{\sum_{j\in S}b_j}}\lvert b\rangle
identity · ZZ rotation
e−iθ2Z⊗Z=CNOT01 (I⊗RZ(θ)) CNOT01=diag(e−iθ/2,eiθ/2,eiθ/2,e−iθ/2)e^{-i\frac{\theta}{2}Z\otimes Z}=\mathrm{CNOT}_{01}\,\big(I\otimes R_Z(\theta)\big)\,\mathrm{CNOT}_{01}=\mathrm{diag}\big(e^{-i\theta/2},e^{i\theta/2},e^{i\theta/2},e^{-i\theta/2}\big)
identity · Basis changes
X=HZH,Y=RX(−π2) Z RX(π2),e−iθY/2=RX(−π2) RZ(θ) RX(π2)X=HZH,\qquad Y=R_X(-\tfrac\pi2)\,Z\,R_X(\tfrac\pi2),\qquad e^{-i\theta Y/2}=R_X(-\tfrac\pi2)\,R_Z(\theta)\,R_X(\tfrac\pi2)
theorem · First-order Trotter bound
∥e−i(A+B)t−(e−iAt/re−iBt/r)r∥≤t22r ∥[A,B]∥\Big\lVert e^{-i(A+B)t}-\big(e^{-iAt/r}e^{-iBt/r}\big)^r\Big\rVert\le\frac{t^2}{2r}\,\lVert[A,B]\rVert
theorem · Second-order Trotter bound
∥e−i(A+B)t−(e−iAt/2re−iBt/re−iAt/2r)r∥≤t312r2∥[B,[B,A]]∥+t324r2∥[A,[A,B]]∥\Big\lVert e^{-i(A+B)t}-\big(e^{-iAt/2r}e^{-iBt/r}e^{-iAt/2r}\big)^r\Big\rVert\le\frac{t^3}{12r^2}\lVert[B,[B,A]]\rVert+\frac{t^3}{24r^2}\lVert[A,[A,B]]\rVert
formula · ZZ feature map (Qiskit convention)
UΦ(x)=[∏j<kCNOTjkPk(2(π−xj)(π−xk))CNOTjk][∏jPj(2xj)]H⊗nU_\Phi(x)=\Big[\prod_{j<k}\mathrm{CNOT}_{jk}P_k\big(2(\pi-x_j)(\pi-x_k)\big)\mathrm{CNOT}_{jk}\Big]\Big[\prod_jP_j(2x_j)\Big]H^{\otimes n}

Data in the generator of a time evolution#

The encodings of the previous lessons place data directly into amplitudes or rotation angles. A more general and physically natural idea is to let the data define a Hamiltonian and to prepare the state reached after evolving under it for some time. By the unitary-evolution postulate, a closed system with Hamiltonian HH evolves as ∣ψ(t)⟩=e−iHt∣ψ(0)⟩\lvert\psi(t)\rangle=e^{-iHt}\lvert\psi(0)\rangle (with ℏ=1\hbar=1); if H=H(x)H=H(x) depends on a data point xx, the final state is a feature vector of xx. This is the encoding behind the IQP and ZZ feature maps used in quantum-kernel methods, behind quantum reservoir computing (which drives a spin system with the input signal), and behind the simulation algorithms that motivate quantum computers in the first place.

Definition

Hamiltonian-evolution encoding

Let X\mathcal X be a data domain and x↦H(x)x\mapsto H(x) a map into the Hermitian operators on nn qubits, the feature Hamiltonian. For an evolution time t>0t>0 and a fixed initial state ∣ψ0⟩\lvert\psi_0\rangle the Hamiltonian-evolution encoding is ∣ϕ(x)⟩=U(x)∣ψ0⟩,U(x)=e−iH(x)t=∑ke−iλk(x)t ∣vk(x)⟩⟨vk(x)∣,\lvert\phi(x)\rangle=U(x)\lvert\psi_0\rangle,\qquad U(x)=e^{-iH(x)t}=\sum_k e^{-i\lambda_k(x)t}\,\lvert v_k(x)\rangle\langle v_k(x)\rvert, where H(x)=∑kλk(x)∣vk(x)⟩⟨vk(x)∣H(x)=\sum_k\lambda_k(x)\lvert v_k(x)\rangle\langle v_k(x)\rvert is a spectral decomposition. U(x)U(x) is unitary because every e−iλkte^{-i\lambda_k t} has modulus 11. Typically H(x)=∑mfm(x)PmH(x)=\sum_m f_m(x)P_m is a real combination of Pauli strings PmP_m with data-dependent coefficients fm(x)f_m(x).

Two examples. (i) Angle encoding is the simplest case. For H(x)=12∑j=0n−1xjXjH(x)=\tfrac12\sum_{j=0}^{n-1}x_jX_j and t=1t=1, the terms act on different qubits and commute, so (by the theorem below) e−iH(x)=∏je−ixjXj/2=⨂jRX(xj)e^{-iH(x)}=\prod_je^{-ix_jX_j/2}=\bigotimes_jR_X(x_j), the product encoding of the previous lesson. (ii) Covariance-matrix exponentiation. For a data matrix with covariance Σ⪰0\Sigma\succeq0 one may take the normalised operator ρ=Σ/Tr Σ\rho=\Sigma/\mathrm{Tr}\,\Sigma (positive semi-definite, trace 11) as a Hamiltonian; then e−iρt=∑ke−iσkt∣uk⟩⟨uk∣e^{-i\rho t}=\sum_ke^{-i\sigma_kt}\lvert u_k\rangle\langle u_k\rvert imprints the principal components uku_k and variances σk\sigma_k as phases, which phase estimation can read out. Lloyd, Mohseni and Rebentrost showed that e−iρte^{-i\rho t} can be applied to a register using copies of the state ρ\rho itself (density-matrix exponentiation), the basis of quantum principal component analysis. In both cases the task is the same: compile e−iH(x)te^{-iH(x)t} into gates. This lesson solves it exactly for commuting Pauli-ZZ Hamiltonians and approximately, with proven error bounds, for non-commuting ones.

Definition

Z-type (diagonal) feature Hamiltonian

For a subset S⊆{0,…,n−1}S\subseteq\{0,\dots,n-1\} write ZS:=∏j∈SZjZ_S:=\prod_{j\in S}Z_j, the Pauli string with ZZ on the qubits of SS and II elsewhere (Z∅=IZ_\emptyset=I). A Z-type feature Hamiltonian is H(x)=∑S∈SϕS(x) ZS,H(x)=\sum_{S\in\mathcal S}\phi_S(x)\,Z_S, with a family S\mathcal S of subsets and real coefficient functions ϕS\phi_S. The interaction order is max⁡S∈S∣S∣\max_{S\in\mathcal S}\lvert S\rvert; order 22 (single-qubit fields ϕj\phi_j and pair couplings ϕjk\phi_{jk}) gives the ZZ feature map.

Theorem

Commuting exponentials multiply

Let A,BA,B be complex d×dd\times d matrices with AB=BAAB=BA. Then eA+B=eAeB=eBeAe^{A+B}=e^Ae^B=e^Be^A. In particular, if H=∑mHmH=\sum_mH_m with pairwise commuting Hermitian HmH_m, then e−iHt=∏me−iHmte^{-iHt}=\prod_me^{-iH_mt} in any order. The hypothesis cannot be dropped: for A=−iXA=-iX, B=−iZB=-iZ one has eA+B≠eAeBe^{A+B}\ne e^Ae^B.

Proof (7 steps)
  1. Step 1:
    eA:=∑k=0∞Akk!,∥Akk!∥≤∥A∥kk!,∑k∥A∥kk!=e∥A∥<∞e^{A}:=\sum_{k=0}^{\infty}\frac{A^k}{k!},\qquad\Big\lVert\frac{A^k}{k!}\Big\rVert\le\frac{\lVert A\rVert^k}{k!},\qquad\sum_k\frac{\lVert A\rVert^k}{k!}=e^{\lVert A\rVert}<\infty
    The exponential series converges absolutely in the operator norm, because the norm is submultiplicative (∥Ak∥≤∥A∥k\lVert A^k\rVert\le\lVert A\rVert^k) and the scalar exponential series converges.
  2. Step 2:
    AB=BA ⇒ (A+B)m=∑k=0m(mk)AkBm−kAB=BA\ \Rightarrow\ (A+B)^m=\sum_{k=0}^{m}\binom mk A^kB^{m-k}
    The binomial theorem holds for commuting matrices: expanding (A+B)m(A+B)^m gives all words in AA and BB of length mm, and commutation lets each word with kk letters AA be reordered to AkBm−kA^kB^{m-k}; there are (mk)\binom mk such words.
  3. Step 3:
    eA+B=∑m=0∞1m!∑k=0mm!k! (m−k)!AkBm−k=∑m=0∞∑k+l=mAkk! Bll!e^{A+B}=\sum_{m=0}^{\infty}\frac{1}{m!}\sum_{k=0}^{m}\frac{m!}{k!\,(m-k)!}A^kB^{m-k}=\sum_{m=0}^{\infty}\sum_{k+l=m}\frac{A^k}{k!}\,\frac{B^l}{l!}
    Insert the binomial expansion into the series of eA+Be^{A+B} and cancel m!m!.
  4. Step 4:
    ∑m=0∞∑k+l=mAkk!Bll!=(∑k=0∞Akk!)(∑l=0∞Bll!)=eAeB\sum_{m=0}^{\infty}\sum_{k+l=m}\frac{A^k}{k!}\frac{B^l}{l!}=\Big(\sum_{k=0}^\infty\frac{A^k}{k!}\Big)\Big(\sum_{l=0}^\infty\frac{B^l}{l!}\Big)=e^Ae^B
    The right-hand side is the Cauchy product of two absolutely convergent series (Mertens' theorem, valid in any Banach algebra), whose sum is the product of the sums.
  5. Step 5:
    eAeB=eA+B=eB+A=eBeAe^Ae^B=e^{A+B}=e^{B+A}=e^Be^A
    Exchanging the roles of AA and BB gives the same matrix.
  6. Step 6:
    [Hm,Hm′]=0 ∀m,m′ ⇒ e−iHt=e−iH1t e−i(H2+⋯+HM)t=⋯=∏m=1Me−iHmt[H_m,H_{m'}]=0\ \forall m,m'\ \Rightarrow\ e^{-iHt}=e^{-iH_1t}\,e^{-i(H_2+\dots+H_M)t}=\dots=\prod_{m=1}^{M}e^{-iH_mt}
    Induction on the number of terms: −iH1t-iH_1t commutes with −i(H2+⋯+HM)t-i(H_2+\dots+H_M)t, so the theorem splits off one factor at a time; the order is arbitrary because all factors commute.
  7. Step 7:
    ∥e−iXe−iZ−e−i(X+Z)∥≈0.799≠0(XZ≠ZX)\big\lVert e^{-iX}e^{-iZ}-e^{-i(X+Z)}\big\rVert\approx0.799\ne0\quad(XZ\ne ZX)
    Counterexample: the worked example of the Trotter section evaluates this norm exactly. The source of the discrepancy is visible in the expansion in a time parameter δ\delta: e−iXδe−iZδ−e−i(X+Z)δ=12[−iXδ,−iZδ]+O(δ3)=iδ2Y+O(δ3)e^{-iX\delta}e^{-iZ\delta}-e^{-i(X+Z)\delta}=\tfrac12[-iX\delta,-iZ\delta]+O(\delta^3)=i\delta^2Y+O(\delta^3), since [X,Z]=−2iY[X,Z]=-2iY.

∎

Theorem

Z-type Hamiltonians generate diagonal evolutions

For every bit string b=b0⋯bn−1b=b_0\cdots b_{n-1} and every Z-type feature Hamiltonian, ZS∣b⟩=(−1)∑j∈Sbj∣b⟩,e−iH(x)t∣b⟩=exp⁡(−it∑S∈SϕS(x)(−1)∑j∈Sbj)∣b⟩.Z_S\lvert b\rangle=(-1)^{\sum_{j\in S}b_j}\lvert b\rangle,\qquad e^{-iH(x)t}\lvert b\rangle=\exp\Big(-it\sum_{S\in\mathcal S}\phi_S(x)(-1)^{\sum_{j\in S}b_j}\Big)\lvert b\rangle . Hence e−iH(x)te^{-iH(x)t} is diagonal in the computational basis, and it factorises exactly as e−iH(x)t=∏S∈Se−itϕS(x)ZSe^{-iH(x)t}=\prod_{S\in\mathcal S}e^{-it\phi_S(x)Z_S} in any order.

Proof (6 steps)
  1. Step 1:
    Z∣0⟩=∣0⟩,Z∣1⟩=−∣1⟩ ⇒ Z∣bj⟩=(−1)bj∣bj⟩Z\lvert0\rangle=\lvert0\rangle,\quad Z\lvert1\rangle=-\lvert1\rangle\ \Rightarrow\ Z\lvert b_j\rangle=(-1)^{b_j}\lvert b_j\rangle
    Z=diag(1,−1)Z=\mathrm{diag}(1,-1) in the basis ∣0⟩,∣1⟩\lvert0\rangle,\lvert1\rangle.
  2. Step 2:
    ZS∣b⟩=⨂jZ[j∈S]∣bj⟩=∏j∈S(−1)bj ∣b⟩=(−1)∑j∈Sbj∣b⟩Z_S\lvert b\rangle=\bigotimes_{j}Z^{[j\in S]}\lvert b_j\rangle=\prod_{j\in S}(-1)^{b_j}\,\lvert b\rangle=(-1)^{\sum_{j\in S}b_j}\lvert b\rangle
    Mixed-product rule on the product state ∣b⟩=⨂j∣bj⟩\lvert b\rangle=\bigotimes_j\lvert b_j\rangle: the factors with j∉Sj\notin S are identities.
  3. Step 3:
    H(x)∣b⟩=λb(x)∣b⟩,λb(x):=∑S∈SϕS(x)(−1)∑j∈Sbj∈RH(x)\lvert b\rangle=\lambda_b(x)\lvert b\rangle,\qquad\lambda_b(x):=\sum_{S\in\mathcal S}\phi_S(x)(-1)^{\sum_{j\in S}b_j}\in\mathbb R
    Linearity: every computational basis state is an eigenvector of every ZSZ_S, hence of their real linear combination.
  4. Step 4:
    H(x)=∑bλb(x)∣b⟩⟨b∣ ⇒ e−iH(x)t=∑be−iλb(x)t∣b⟩⟨b∣H(x)=\sum_{b}\lambda_b(x)\lvert b\rangle\langle b\rvert\ \Rightarrow\ e^{-iH(x)t}=\sum_be^{-i\lambda_b(x)t}\lvert b\rangle\langle b\rvert
    The computational basis is an orthonormal eigenbasis, so this is a spectral decomposition; a function of a Hermitian operator acts on each eigenvector by the function of its eigenvalue.
  5. Step 5:
    ZSZS′∣b⟩=(−1)∑j∈Sbj+∑j∈S′bj∣b⟩=ZS′ZS∣b⟩ ⇒ [ZS,ZS′]=0Z_SZ_{S'}\lvert b\rangle=(-1)^{\sum_{j\in S}b_j+\sum_{j\in S'}b_j}\lvert b\rangle=Z_{S'}Z_S\lvert b\rangle\ \Rightarrow\ [Z_S,Z_{S'}]=0
    Diagonal matrices commute: both orders multiply every basis state by the same sign.
  6. Step 6:
    e−iH(x)t=∏S∈Se−itϕS(x)ZS,e−itϕSZS∣b⟩=e−itϕS(−1)∑j∈Sbj∣b⟩e^{-iH(x)t}=\prod_{S\in\mathcal S}e^{-it\phi_S(x)Z_S},\qquad e^{-it\phi_SZ_S}\lvert b\rangle=e^{-it\phi_S(-1)^{\sum_{j\in S}b_j}}\lvert b\rangle
    Apply the commuting-exponentials theorem to the pairwise commuting terms ϕS(x)ZS\phi_S(x)Z_S; each factor is itself diagonal, and multiplying the phases of all factors reproduces e−iλb(x)te^{-i\lambda_b(x)t}.

∎

Quick check

For H=0.3 Z0Z1H=0.3\,Z_0Z_1 on two qubits and t=1t=1, the evolution maps ∣01⟩↦eiα∣01⟩\lvert01\rangle\mapsto e^{i\alpha}\lvert01\rangle. What is α\alpha?

tolerance ±0.000001

Compiling Pauli exponentials exactly#

Theorem

The ZZ rotation identity

For every θ∈R\theta\in\mathbb R, e−iθ2Z⊗Z=CNOT01 (I⊗RZ(θ)) CNOT01=diag(e−iθ/2,eiθ/2,eiθ/2,e−iθ/2).e^{-i\frac{\theta}{2}Z\otimes Z}=\mathrm{CNOT}_{01}\,\big(I\otimes R_Z(\theta)\big)\,\mathrm{CNOT}_{01}=\mathrm{diag}\big(e^{-i\theta/2},e^{i\theta/2},e^{i\theta/2},e^{-i\theta/2}\big). Equivalently, CNOT01(I⊗Z)CNOT01=Z⊗Z\mathrm{CNOT}_{01}(I\otimes Z)\mathrm{CNOT}_{01}=Z\otimes Z: after the CNOT, the Z1Z_1 eigenvalue of qubit 11 is the Z0Z1Z_0Z_1 eigenvalue of the original state.

Proof (8 steps)
  1. Step 1:
    CNOT01∣a,b⟩=∣a,a⊕b⟩,CNOT012=I\mathrm{CNOT}_{01}\lvert a,b\rangle=\lvert a,a\oplus b\rangle,\qquad\mathrm{CNOT}_{01}^2=I
    Definition of CNOT with control 00 and target 11; applying it twice adds aa twice modulo 22.
  2. Step 2:
    (Z⊗Z)∣a,b⟩=(−1)a(−1)b∣a,b⟩=(−1)a⊕b∣a,b⟩(Z\otimes Z)\lvert a,b\rangle=(-1)^{a}(-1)^{b}\lvert a,b\rangle=(-1)^{a\oplus b}\lvert a,b\rangle
    Diagonal-evolution theorem with S={0,1}S=\{0,1\}; a+ba+b and a⊕ba\oplus b have the same parity, so (−1)a+b=(−1)a⊕b(-1)^{a+b}=(-1)^{a\oplus b}.
  3. Step 3:
    e−iθ2Z⊗Z∣a,b⟩=e−iθ2(−1)a⊕b∣a,b⟩e^{-i\frac\theta2Z\otimes Z}\lvert a,b\rangle=e^{-i\frac\theta2(-1)^{a\oplus b}}\lvert a,b\rangle
    The evolution acts on each eigenvector by the exponential of its eigenvalue.
  4. Step 4:
    RZ(θ)∣c⟩=e−iθ2(−1)c∣c⟩(c∈{0,1})R_Z(\theta)\lvert c\rangle=e^{-i\frac\theta2(-1)^{c}}\lvert c\rangle\qquad(c\in\{0,1\})
    RZ(θ)=e−iθZ/2=diag(e−iθ/2,eiθ/2)R_Z(\theta)=e^{-i\theta Z/2}=\mathrm{diag}(e^{-i\theta/2},e^{i\theta/2}), the same formula with one qubit.
  5. Step 5:
    CNOT01(I⊗RZ(θ))CNOT01∣a,b⟩=CNOT01(I⊗RZ(θ))∣a,a⊕b⟩=e−iθ2(−1)a⊕b CNOT01∣a,a⊕b⟩\mathrm{CNOT}_{01}(I\otimes R_Z(\theta))\mathrm{CNOT}_{01}\lvert a,b\rangle=\mathrm{CNOT}_{01}(I\otimes R_Z(\theta))\lvert a,a\oplus b\rangle=e^{-i\frac\theta2(-1)^{a\oplus b}}\,\mathrm{CNOT}_{01}\lvert a,a\oplus b\rangle
    The first CNOT writes the parity a⊕ba\oplus b onto qubit 11; RZR_Z on qubit 11 multiplies by the phase of the bit c=a⊕bc=a\oplus b.
  6. Step 6:
    =e−iθ2(−1)a⊕b∣a,a⊕a⊕b⟩=e−iθ2(−1)a⊕b∣a,b⟩=e^{-i\frac\theta2(-1)^{a\oplus b}}\lvert a,a\oplus a\oplus b\rangle=e^{-i\frac\theta2(-1)^{a\oplus b}}\lvert a,b\rangle
    The second CNOT restores qubit 11, since a⊕a=0a\oplus a=0.
  7. Step 7:
    both sides agree on ∣00⟩,∣01⟩,∣10⟩,∣11⟩ ⇒ equal operators\text{both sides agree on }\lvert00\rangle,\lvert01\rangle,\lvert10\rangle,\lvert11\rangle\ \Rightarrow\ \text{equal operators}
    Two linear maps that agree on a basis are equal. Reading off (−1)a⊕b=+1,−1,−1,+1(-1)^{a\oplus b}=+1,-1,-1,+1 gives the diagonal (e−iθ/2,eiθ/2,eiθ/2,e−iθ/2)(e^{-i\theta/2},e^{i\theta/2},e^{i\theta/2},e^{-i\theta/2}).
  8. Step 8:
    CNOT01(I⊗Z)CNOT01∣a,b⟩=(−1)a⊕b∣a,b⟩=(Z⊗Z)∣a,b⟩\mathrm{CNOT}_{01}(I\otimes Z)\mathrm{CNOT}_{01}\lvert a,b\rangle=(-1)^{a\oplus b}\lvert a,b\rangle=(Z\otimes Z)\lvert a,b\rangle
    The same computation with ZZ in place of RZ(θ)R_Z(\theta) gives the operator identity; exponentiating it with V(eM)V†=eVMV†V(e^{M})V^\dagger=e^{VMV^\dagger} (proved in the basis-change corollary) is a second proof of the theorem.

∎

e−i0.72Z⊗Z=(e−0.35i0000e0.35i0000e0.35i0000e−0.35i)≈(0.9394−0.3429i00000.9394+0.3429i00000.9394+0.3429i00000.9394−0.3429i)e^{-i\frac{0.7}{2}Z\otimes Z}=\begin{pmatrix}e^{-0.35i}&0&0&0\\0&e^{0.35i}&0&0\\0&0&e^{0.35i}&0\\0&0&0&e^{-0.35i}\end{pmatrix}\approx\begin{pmatrix}0.9394-0.3429i&0&0&0\\0&0.9394+0.3429i&0&0\\0&0&0.9394+0.3429i&0\\0&0&0&0.9394-0.3429i\end{pmatrix}
e^{-0.35i Z⊗Z} = CNOT₀₁ (I ⊗ R_Z(0.7)) CNOT₀₁4×4

Unitary verified: U†U=IU^\dagger U = I (max deviation 0.0e+0)

Derivation

Numerical check of the ZZ identity at θ = 0.7

  1. Step 1:
    I⊗RZ(0.7)=diag(e−0.35i,e0.35i,e−0.35i,e0.35i)I\otimes R_Z(0.7)=\mathrm{diag}\big(e^{-0.35i},e^{0.35i},e^{-0.35i},e^{0.35i}\big)
    I⊗DI\otimes D repeats the diagonal D=diag(e−0.35i,e0.35i)D=\mathrm{diag}(e^{-0.35i},e^{0.35i}) once for each value of qubit 00.
  2. Step 2:
    CNOT01=(1000010000010010)=Π(10 11)\mathrm{CNOT}_{01}=\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{pmatrix}=\Pi_{(10\ 11)}
    The permutation matrix that exchanges the basis vectors ∣10⟩\lvert10\rangle and ∣11⟩\lvert11\rangle (indices 22 and 33).
  3. Step 3:
    Π diag(d0,d1,d2,d3) Π=diag(d0,d1,d3,d2)\Pi\,\mathrm{diag}(d_0,d_1,d_2,d_3)\,\Pi=\mathrm{diag}(d_0,d_1,d_3,d_2)
    Conjugating a diagonal matrix by a permutation permutes its diagonal entries: entries 22 and 33 are exchanged.
  4. Step 4:
    CNOT01(I⊗RZ(0.7))CNOT01=diag(e−0.35i,e0.35i,e0.35i,e−0.35i)\mathrm{CNOT}_{01}(I\otimes R_Z(0.7))\mathrm{CNOT}_{01}=\mathrm{diag}\big(e^{-0.35i},e^{0.35i},e^{0.35i},e^{-0.35i}\big)
    Apply the exchange to (e−0.35i,e0.35i,e−0.35i,e0.35i)(e^{-0.35i},e^{0.35i},e^{-0.35i},e^{0.35i}).
  5. Step 5:
    e∓0.35i=cos⁡0.35∓isin⁡0.35≈0.939373∓0.342898 ie^{\mp0.35i}=\cos0.35\mp i\sin0.35\approx0.939373\mp0.342898\,i
    Euler's formula; this is the matrix displayed above, and the lesson tests confirm it against exp⁡(−0.35i Z⊗Z)\exp(-0.35i\,Z\otimes Z) computed by the spectral theorem to 10−1210^{-12}.

Result

CNOT01(I⊗RZ(0.7))CNOT01=e−0.35i Z⊗Z\boxed{\mathrm{CNOT}_{01}\big(I\otimes R_Z(0.7)\big)\mathrm{CNOT}_{01}=e^{-0.35i\,Z\otimes Z}}

Circuit · 2 qubits

Quantum circuit on 2 qubitsX on q1 controlled by q0; RZ(0.70) on q1; X on q1 controlled by q0q0q1RZ(0.70)

The exact ZZ gadget CNOT(0,1); RZ(0.7)\mathrm{CNOT}(0,1);\ R_Z(0.7) on qubit 11; CNOT(0,1)\mathrm{CNOT}(0,1). Its unitary is diag(e−0.35i,e0.35i,e0.35i,e−0.35i)=e−0.35i Z⊗Z\mathrm{diag}(e^{-0.35i},e^{0.35i},e^{0.35i},e^{-0.35i})=e^{-0.35i\,Z\otimes Z}, the target of the lab.

U=(0.9394−0.3429i00000.9394+0.3429i00000.9394+0.3429i00000.9394−0.3429i)U = \begin{pmatrix} 0.9394 - 0.3429i & 0 & 0 & 0 \\ 0 & 0.9394 + 0.3429i & 0 & 0 \\ 0 & 0 & 0.9394 + 0.3429i & 0 \\ 0 & 0 & 0 & 0.9394 - 0.3429i \end{pmatrix}
Theorem

Exponentials of Z⊗k by a CNOT ladder

For k≥2k\ge2 let Lk:=CNOTk−2,k−1⋯CNOT1,2 CNOT0,1L_k:=\mathrm{CNOT}_{k-2,k-1}\cdots\mathrm{CNOT}_{1,2}\,\mathrm{CNOT}_{0,1} (so CNOT0,1\mathrm{CNOT}_{0,1} acts first). Then Lk∣b0⋯bk−1⟩=∣p0p1⋯pk−1⟩L_k\lvert b_0\cdots b_{k-1}\rangle=\lvert p_0p_1\cdots p_{k-1}\rangle with prefix parities pj=b0⊕⋯⊕bjp_j=b_0\oplus\cdots\oplus b_j, and e−iθ2Z⊗k=Lk† (I⊗(k−1)⊗RZ(θ)) Lk,Lk†=CNOT0,1 CNOT1,2⋯CNOTk−2,k−1.e^{-i\frac\theta2Z^{\otimes k}}=L_k^\dagger\,\big(I^{\otimes(k-1)}\otimes R_Z(\theta)\big)\,L_k,\qquad L_k^\dagger=\mathrm{CNOT}_{0,1}\,\mathrm{CNOT}_{1,2}\cdots\mathrm{CNOT}_{k-2,k-1}. The circuit uses 2(k−1)2(k-1) CNOTs and one RZR_Z; the same construction applies to ZSZ_S for any subset SS, laddering only over the qubits of SS.

Proof (7 steps)
  1. Step 1:
    k=2:L2∣b0b1⟩=CNOT01∣b0b1⟩=∣b0, b0⊕b1⟩=∣p0p1⟩k=2:\quad L_2\lvert b_0b_1\rangle=\mathrm{CNOT}_{01}\lvert b_0b_1\rangle=\lvert b_0,\,b_0\oplus b_1\rangle=\lvert p_0p_1\rangle
    Base case of the prefix-parity claim (the ZZ theorem).
  2. Step 2:
    Lk+1=CNOTk−1,k (Lk⊗I)L_{k+1}=\mathrm{CNOT}_{k-1,k}\,(L_k\otimes I)
    The ladder on k+1k+1 qubits is the ladder on the first kk qubits followed by one more CNOT from qubit k−1k-1 to the new qubit kk.
  3. Step 3:
    Lk+1∣b0⋯bk⟩=CNOTk−1,k∣p0⋯pk−1,bk⟩=∣p0⋯pk−1, pk−1⊕bk⟩=∣p0⋯pk⟩L_{k+1}\lvert b_0\cdots b_k\rangle=\mathrm{CNOT}_{k-1,k}\lvert p_0\cdots p_{k-1},b_k\rangle=\lvert p_0\cdots p_{k-1},\,p_{k-1}\oplus b_k\rangle=\lvert p_0\cdots p_k\rangle
    Induction hypothesis for LkL_k, then the CNOT adds the parity pk−1p_{k-1} held by qubit k−1k-1 to bkb_k; pk−1⊕bk=pkp_{k-1}\oplus b_k=p_k. By induction the claim holds for all k≥2k\ge2.
  4. Step 4:
    Z⊗k∣b⟩=(−1)b0+⋯+bk−1∣b⟩=(−1)pk−1∣b⟩Z^{\otimes k}\lvert b\rangle=(-1)^{b_0+\cdots+b_{k-1}}\lvert b\rangle=(-1)^{p_{k-1}}\lvert b\rangle
    Diagonal-evolution theorem with S={0,…,k−1}S=\{0,\dots,k-1\}; the last prefix parity is the parity of the whole string.
  5. Step 5:
    Lk†(I⊗(k−1)⊗RZ(θ))Lk∣b⟩=e−iθ2(−1)pk−1Lk†Lk∣b⟩=e−iθ2(−1)pk−1∣b⟩L_k^\dagger\big(I^{\otimes(k-1)}\otimes R_Z(\theta)\big)L_k\lvert b\rangle=e^{-i\frac\theta2(-1)^{p_{k-1}}}L_k^\dagger L_k\lvert b\rangle=e^{-i\frac\theta2(-1)^{p_{k-1}}}\lvert b\rangle
    LkL_k maps ∣b⟩\lvert b\rangle to a basis state whose last bit is pk−1p_{k-1}; RZ(θ)R_Z(\theta) on the last qubit contributes the phase of that bit; Lk†Lk=IL_k^\dagger L_k=I because LkL_k is unitary.
  6. Step 6:
    e−iθ2Z⊗k∣b⟩=e−iθ2(−1)pk−1∣b⟩  ∀b ⇒ e−iθ2Z⊗k=Lk†(I⊗RZ(θ))Lke^{-i\frac\theta2Z^{\otimes k}}\lvert b\rangle=e^{-i\frac\theta2(-1)^{p_{k-1}}}\lvert b\rangle\ \ \forall b\ \Rightarrow\ e^{-i\frac\theta2Z^{\otimes k}}=L_k^\dagger(I\otimes R_Z(\theta))L_k
    Both operators agree on the computational basis.
  7. Step 7:
    (G1G2⋯Gm)†=Gm†⋯G1†,CNOT†=CNOT(G_1G_2\cdots G_m)^\dagger=G_m^\dagger\cdots G_1^\dagger,\qquad\mathrm{CNOT}^\dagger=\mathrm{CNOT}
    The adjoint reverses products and every CNOT is Hermitian and unitary, so the "unladder" is the ladder in reverse order. Counting gates: k−1k-1 CNOTs in LkL_k, k−1k-1 in Lk†L_k^\dagger, one RZR_Z.

∎

Circuit · 3 qubits

Quantum circuit on 3 qubitsX on q1 controlled by q0; X on q2 controlled by q1; RZ(0.70) on q2; X on q2 controlled by q1; X on q1 controlled by q0q0q1q2RZ(0.70)

Parity ladder for three qubits: CNOT(0,1); CNOT(1,2); RZ(0.7)\mathrm{CNOT}(0,1);\ \mathrm{CNOT}(1,2);\ R_Z(0.7) on qubit 22; CNOT(1,2); CNOT(0,1)\mathrm{CNOT}(1,2);\ \mathrm{CNOT}(0,1). Its unitary is e−0.35i Z⊗Z⊗Ze^{-0.35i\,Z\otimes Z\otimes Z}, with diagonal phase e−0.35ie^{-0.35i} on even-parity and e0.35ie^{0.35i} on odd-parity basis states.

U=(0.9394−0.3429i000000000.9394+0.3429i000000000.9394+0.3429i000000000.9394−0.3429i000000000.9394+0.3429i000000000.9394−0.3429i000000000.9394−0.3429i000000000.9394+0.3429i)U = \begin{pmatrix} 0.9394 - 0.3429i & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0.9394 + 0.3429i & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0.9394 + 0.3429i & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0.9394 - 0.3429i & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0.9394 + 0.3429i & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0.9394 - 0.3429i & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0.9394 - 0.3429i & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0.9394 + 0.3429i \end{pmatrix}
Lemma

Rotating Z about the x-axis

For every α∈R\alpha\in\mathbb R, RX(α) Z RX(α)†=cos⁡α Z−sin⁡α Y.R_X(\alpha)\,Z\,R_X(\alpha)^\dagger=\cos\alpha\,Z-\sin\alpha\,Y . In particular RX(−π2) Z RX(π2)=YR_X(-\tfrac\pi2)\,Z\,R_X(\tfrac\pi2)=Y and RX(π2) Z RX(−π2)=−YR_X(\tfrac\pi2)\,Z\,R_X(-\tfrac\pi2)=-Y. Moreover HZH=XHZH=X.

Proof (6 steps)
  1. Step 1:
    RX(α)=e−iαX/2=cos⁡α2 I−isin⁡α2 X,RX(α)†=RX(−α)R_X(\alpha)=e^{-i\alpha X/2}=\cos\tfrac\alpha2\,I-i\sin\tfrac\alpha2\,X,\qquad R_X(\alpha)^\dagger=R_X(-\alpha)
    Split the exponential series into even and odd powers using X2=IX^2=I; the adjoint conjugates the coefficients, which flips the sign of α\alpha.
  2. Step 2:
    XZ=−ZX ⇒ RX(α) Z=(cos⁡α2−isin⁡α2X)Z=Z(cos⁡α2+isin⁡α2X)=Z RX(−α)XZ=-ZX\ \Rightarrow\ R_X(\alpha)\,Z=\big(\cos\tfrac\alpha2-i\sin\tfrac\alpha2X\big)Z=Z\big(\cos\tfrac\alpha2+i\sin\tfrac\alpha2X\big)=Z\,R_X(-\alpha)
    Move ZZ to the left through each term; anticommutation flips the sign of the XX term.
  3. Step 3:
    RX(α)ZRX(α)†=Z RX(−α)RX(−α)=Z RX(−2α)=Z(cos⁡α I+isin⁡α X)R_X(\alpha)ZR_X(\alpha)^\dagger=Z\,R_X(-\alpha)R_X(-\alpha)=Z\,R_X(-2\alpha)=Z\big(\cos\alpha\,I+i\sin\alpha\,X\big)
    Rotations about the same axis compose by adding angles (commuting exponentials), and the formula of the first step with angle −2α-2\alpha.
  4. Step 4:
    ZX=iY ⇒ Z(cos⁡α I+isin⁡α X)=cos⁡α Z+isin⁡α (iY)=cos⁡α Z−sin⁡α YZX=iY\ \Rightarrow\ Z\big(\cos\alpha\,I+i\sin\alpha\,X\big)=\cos\alpha\,Z+i\sin\alpha\,(iY)=\cos\alpha\,Z-\sin\alpha\,Y
    Pauli product rule: ZX=(100−1)(0110)=(01−10)=i(0−ii0)=iYZX=\begin{pmatrix}1&0\\0&-1\end{pmatrix}\begin{pmatrix}0&1\\1&0\end{pmatrix}=\begin{pmatrix}0&1\\-1&0\end{pmatrix}=i\begin{pmatrix}0&-i\\i&0\end{pmatrix}=iY.
  5. Step 5:
    α=−π2: RX(−π2)ZRX(π2)=0⋅Z+1⋅Y=Y;α=π2: RX(π2)ZRX(−π2)=−Y\alpha=-\tfrac\pi2:\ R_X(-\tfrac\pi2)ZR_X(\tfrac\pi2)=0\cdot Z+1\cdot Y=Y;\qquad\alpha=\tfrac\pi2:\ R_X(\tfrac\pi2)ZR_X(-\tfrac\pi2)=-Y
    cos⁡(∓π2)=0\cos(\mp\tfrac\pi2)=0 and sin⁡(∓π2)=∓1\sin(\mp\tfrac\pi2)=\mp1.
  6. Step 6:
    HZH=12(X+Z)Z(X+Z)=12(XZX+XZZ+ZZX+ZZZ)=12(−Z+X+X+Z)=XHZH=\tfrac12(X+Z)Z(X+Z)=\tfrac12\big(XZX+XZZ+ZZX+ZZZ\big)=\tfrac12(-Z+X+X+Z)=X
    H=(X+Z)/2H=(X+Z)/\sqrt2, Z2=IZ^2=I and XZX=−ZXX=−ZXZX=-ZXX=-Z.

∎

Corollary

Exponentials of X, Y and arbitrary Pauli strings

For a unitary VV and a Hermitian PP, V e−iθP/2 V†=e−iθ(VPV†)/2V\,e^{-i\theta P/2}\,V^\dagger=e^{-i\theta(VPV^\dagger)/2}. Consequently e−iθX/2=H RZ(θ) H,e−iθY/2=RX(−π2) RZ(θ) RX(π2),e^{-i\theta X/2}=H\,R_Z(\theta)\,H,\qquad e^{-i\theta Y/2}=R_X(-\tfrac\pi2)\,R_Z(\theta)\,R_X(\tfrac\pi2), i.e. in time order the YY rotation is RX(π2)R_X(\tfrac\pi2), then RZ(θ)R_Z(\theta), then RX(−π2)R_X(-\tfrac\pi2). For a Pauli string P=⨂j∈SσjP=\bigotimes_{j\in S}\sigma_j with σj∈{X,Y,Z}\sigma_j\in\{X,Y,Z\}, let Vj=I,H,RX(−π2)V_j=I,H,R_X(-\tfrac\pi2) for σj=Z,X,Y\sigma_j=Z,X,Y and V=⨂jVjV=\bigotimes_jV_j; then e−iθP/2=V L†RZ(θ)L V†e^{-i\theta P/2}=V\,L^\dagger R_Z(\theta)L\,V^\dagger with the parity ladder LL over SS.

Proof (6 steps)
  1. Step 1:
    (VPV†)k=VP (V†V) P⋯P V†=VPkV†(VPV^\dagger)^k=VP\,(V^\dagger V)\,P\cdots P\,V^\dagger=VP^kV^\dagger
    Inner factors V†V=IV^\dagger V=I cancel.
  2. Step 2:
    e−iθ(VPV†)/2=∑k(−iθ/2)kk!VPkV†=V(∑k(−iθ/2)kPkk!)V†=Ve−iθP/2V†e^{-i\theta(VPV^\dagger)/2}=\sum_k\frac{(-i\theta/2)^k}{k!}VP^kV^\dagger=V\Big(\sum_k\frac{(-i\theta/2)^kP^k}{k!}\Big)V^\dagger=Ve^{-i\theta P/2}V^\dagger
    Insert into the exponential series; multiplication by fixed matrices is continuous, so VV and V†V^\dagger pass through the convergent sum.
  3. Step 3:
    X=HZH=HZH† ⇒ e−iθX/2=H e−iθZ/2 H=H RZ(θ) HX=HZH=HZH^\dagger\ \Rightarrow\ e^{-i\theta X/2}=H\,e^{-i\theta Z/2}\,H=H\,R_Z(\theta)\,H
    Lemma with V=H=H†V=H=H^\dagger.
  4. Step 4:
    Y=RX(−π2) Z RX(−π2)† ⇒ e−iθY/2=RX(−π2) RZ(θ) RX(π2)Y=R_X(-\tfrac\pi2)\,Z\,R_X(-\tfrac\pi2)^\dagger\ \Rightarrow\ e^{-i\theta Y/2}=R_X(-\tfrac\pi2)\,R_Z(\theta)\,R_X(\tfrac\pi2)
    Lemma with V=RX(−π2)V=R_X(-\tfrac\pi2) and V†=RX(π2)V^\dagger=R_X(\tfrac\pi2). The rightmost factor RX(π2)R_X(\tfrac\pi2) acts first.
  5. Step 5:
    P=⨂j∈Sσj=⨂j∈SVjZVj†=V ZS V†P=\bigotimes_{j\in S}\sigma_j=\bigotimes_{j\in S}V_jZV_j^\dagger=V\,Z_S\,V^\dagger
    Each factor is rotated separately (mixed-product rule); Vj=IV_j=I off SS and for σj=Z\sigma_j=Z.
  6. Step 6:
    e−iθP/2=V e−iθZS/2 V†=V L†RZ(θ)L V†e^{-i\theta P/2}=V\,e^{-i\theta Z_S/2}\,V^\dagger=V\,L^\dagger R_Z(\theta)L\,V^\dagger
    Lemma, then the parity-ladder theorem for ZSZ_S (with RZR_Z on the last qubit of SS). In time order: basis change V†V^\dagger, ladder, RZ(θ)R_Z(\theta), unladder, basis change back VV.

∎

Derivation

The Y rotation as an explicit 2×2 product

  1. Step 1:
    RX(π2)=12(1−i−i1),RZ(θ)=(e−iθ/200eiθ/2),RX(−π2)=12(1ii1)R_X(\tfrac\pi2)=\tfrac1{\sqrt2}\begin{pmatrix}1&-i\\-i&1\end{pmatrix},\quad R_Z(\theta)=\begin{pmatrix}e^{-i\theta/2}&0\\0&e^{i\theta/2}\end{pmatrix},\quad R_X(-\tfrac\pi2)=\tfrac1{\sqrt2}\begin{pmatrix}1&i\\i&1\end{pmatrix}
    cos⁡π4=sin⁡π4=12\cos\tfrac\pi4=\sin\tfrac\pi4=\tfrac1{\sqrt2} in RX(α)=cos⁡α2I−isin⁡α2XR_X(\alpha)=\cos\tfrac\alpha2I-i\sin\tfrac\alpha2X.
  2. Step 2:
    RZ(θ)RX(π2)=12(e−iθ/2−ie−iθ/2−ieiθ/2eiθ/2)R_Z(\theta)R_X(\tfrac\pi2)=\tfrac1{\sqrt2}\begin{pmatrix}e^{-i\theta/2}&-ie^{-i\theta/2}\\-ie^{i\theta/2}&e^{i\theta/2}\end{pmatrix}
    A diagonal matrix on the left scales the rows.
  3. Step 3:
    RX(−π2)RZ(θ)RX(π2)=12(e−iθ/2+eiθ/2−ie−iθ/2+ieiθ/2ie−iθ/2−ieiθ/2e−iθ/2+eiθ/2)R_X(-\tfrac\pi2)R_Z(\theta)R_X(\tfrac\pi2)=\tfrac12\begin{pmatrix}e^{-i\theta/2}+e^{i\theta/2}&-ie^{-i\theta/2}+ie^{i\theta/2}\\ie^{-i\theta/2}-ie^{i\theta/2}&e^{-i\theta/2}+e^{i\theta/2}\end{pmatrix}
    Row-by-column products, e.g. entry (1,1)(1,1): 1⋅e−iθ/2+i⋅(−ieiθ/2)=e−iθ/2+eiθ/21\cdot e^{-i\theta/2}+i\cdot(-ie^{i\theta/2})=e^{-i\theta/2}+e^{i\theta/2}.
  4. Step 4:
    =(cos⁡θ2−sin⁡θ2sin⁡θ2cos⁡θ2)=\begin{pmatrix}\cos\frac\theta2&-\sin\frac\theta2\\\sin\frac\theta2&\cos\frac\theta2\end{pmatrix}
    eiθ/2+e−iθ/2=2cos⁡θ2e^{i\theta/2}+e^{-i\theta/2}=2\cos\tfrac\theta2 and i(eiθ/2−e−iθ/2)=i⋅2isin⁡θ2=−2sin⁡θ2i(e^{i\theta/2}-e^{-i\theta/2})=i\cdot2i\sin\tfrac\theta2=-2\sin\tfrac\theta2.
  5. Step 5:
    e−iθY/2=cos⁡θ2 I−isin⁡θ2 Y=(cos⁡θ2−sin⁡θ2sin⁡θ2cos⁡θ2)=RY(θ)e^{-i\theta Y/2}=\cos\tfrac\theta2\,I-i\sin\tfrac\theta2\,Y=\begin{pmatrix}\cos\frac\theta2&-\sin\frac\theta2\\\sin\frac\theta2&\cos\frac\theta2\end{pmatrix}=R_Y(\theta)
    −iY=(0−110)-iY=\begin{pmatrix}0&-1\\1&0\end{pmatrix}; the two matrices coincide exactly, with no global phase.
  6. Step 6:
    RX(π2)RZ(θ)RX(−π2)=e−iθ(−Y)/2=RY(−θ)R_X(\tfrac\pi2)R_Z(\theta)R_X(-\tfrac\pi2)=e^{-i\theta(-Y)/2}=R_Y(-\theta)
    The opposite sandwich conjugates ZZ to −Y-Y (lemma with α=π2\alpha=\tfrac\pi2) and rotates the wrong way.

Result

e−iθY/2=RX(−π2) RZ(θ) RX(π2)(time order: RX(π2), RZ(θ), RX(−π2))\boxed{e^{-i\theta Y/2}=R_X(-\tfrac\pi2)\,R_Z(\theta)\,R_X(\tfrac\pi2)\qquad(\text{time order: }R_X(\tfrac\pi2),\ R_Z(\theta),\ R_X(-\tfrac\pi2))}

Circuit · 2 qubits

Quantum circuit on 2 qubitsH on q0; RX(π/2) on q1; X on q1 controlled by q0; RZ(0.70) on q1; X on q1 controlled by q0; H on q0; RX(-π/2) on q1q0q1HRX(π/2)RZ(0.70)HRX(-π/2)

e−0.35i X⊗Ye^{-0.35i\,X\otimes Y} by basis change: HH on qubit 00 and RX(π2)R_X(\tfrac\pi2) on qubit 11 map the eigenbases of XX and YY to the computational basis, the ZZ gadget applies the phase, and HH, RX(−π2)R_X(-\tfrac\pi2) map back.

U=(0.939400−0.342900.93940.342900−0.34290.939400.3429000.9394)U = \begin{pmatrix} 0.9394 & 0 & 0 & -0.3429 \\ 0 & 0.9394 & 0.3429 & 0 \\ 0 & -0.3429 & 0.9394 & 0 \\ 0.3429 & 0 & 0 & 0.9394 \end{pmatrix}

Quick check

Which gate sequence, listed in time order (first gate applied first), implements e−iθY/2e^{-i\theta Y/2} exactly?

Select one answer

Non-commuting terms: Trotter–Suzuki product formulas#

When the feature Hamiltonian contains non-commuting terms, for example a Z⊗ZZ\otimes Z coupling together with transverse fields XjX_j, the exponential no longer factorises, and each factor can only be compiled separately. The idea of Trotter (1959) and Suzuki (1976, 1991), used by Lloyd (1996) to show that quantum computers can efficiently simulate local Hamiltonians, is to alternate short evolutions under each term. We now prove how large the resulting error is.

Definition

First- and second-order product formulas

Let A,BA,B be Hermitian, H=A+BH=A+B, U(δ)=e−iHδU(\delta)=e^{-iH\delta}. The first-order (Lie–Trotter) step and the second-order (symmetric, Strang) step are V(δ)=e−iAδe−iBδ,S(δ)=e−iAδ/2 e−iBδ e−iAδ/2.V(\delta)=e^{-iA\delta}e^{-iB\delta},\qquad S(\delta)=e^{-iA\delta/2}\,e^{-iB\delta}\,e^{-iA\delta/2}. With rr steps of size δ=t/r\delta=t/r the approximations of U(t)U(t) are V(t/r)rV(t/r)^r and S(t/r)rS(t/r)^r. The Trotter error is E=U(t)−V(t/r)rE=U(t)-V(t/r)^r, measured in the operator norm, which bounds the error on every input state: ∥(U−U~)∣ψ⟩∥≤∥U−U~∥\lVert(U-\tilde U)\lvert\psi\rangle\rVert\le\lVert U-\tilde U\rVert for unit ∣ψ⟩\lvert\psi\rangle.

Lemma

Variation of parameters (Duhamel formula)

Let HH be Hermitian, U(s)=e−iHsU(s)=e^{-iHs}, and let W:[0,δ]→Cd×dW:[0,\delta]\to\mathbb C^{d\times d} be continuously differentiable with W(0)=IW(0)=I and W′(s)=−i(H+Δ(s))W(s)W'(s)=-i\big(H+\Delta(s)\big)W(s) for a continuous Δ\Delta. Then W(δ)−U(δ)=−i∫0δU(δ−s) Δ(s) W(s) ds,W(\delta)-U(\delta)=-i\int_0^\delta U(\delta-s)\,\Delta(s)\,W(s)\,ds, and if every W(s)W(s) is unitary, ∥W(δ)−U(δ)∥≤∫0δ∥Δ(s)∥ ds\lVert W(\delta)-U(\delta)\rVert\le\int_0^\delta\lVert\Delta(s)\rVert\,ds.

Proof (6 steps)
  1. Step 1:
    F(s):=U(δ−s) W(s),F(0)=U(δ),F(δ)=W(δ)F(s):=U(\delta-s)\,W(s),\qquad F(0)=U(\delta),\quad F(\delta)=W(\delta)
    Interpolate between the exact and the approximate evolution.
  2. Step 2:
    ddsU(δ−s)=iH U(δ−s)=U(δ−s) iH\frac{d}{ds}U(\delta-s)=iH\,U(\delta-s)=U(\delta-s)\,iH
    Differentiate the exponential series term by term; HH commutes with every power of itself.
  3. Step 3:
    F′(s)=U(δ−s) iH W(s)+U(δ−s)(−i(H+Δ(s)))W(s)=−i U(δ−s) Δ(s) W(s)F'(s)=U(\delta-s)\,iH\,W(s)+U(\delta-s)\big(-i(H+\Delta(s))\big)W(s)=-i\,U(\delta-s)\,\Delta(s)\,W(s)
    Product rule; the terms with HH cancel.
  4. Step 4:
    W(δ)−U(δ)=F(δ)−F(0)=∫0δF′(s) ds=−i∫0δU(δ−s)Δ(s)W(s) dsW(\delta)-U(\delta)=F(\delta)-F(0)=\int_0^\delta F'(s)\,ds=-i\int_0^\delta U(\delta-s)\Delta(s)W(s)\,ds
    Fundamental theorem of calculus, applied entry by entry.
  5. Step 5:
    ∥∫0δG(s) ds∥≤∫0δ∥G(s)∥ ds\Big\lVert\int_0^\delta G(s)\,ds\Big\rVert\le\int_0^\delta\lVert G(s)\rVert\,ds
    The integral is a limit of Riemann sums, and the triangle inequality holds for every sum; the norm is continuous.
  6. Step 6:
    ∥U(δ−s)Δ(s)W(s)∥≤∥U(δ−s)∥ ∥Δ(s)∥ ∥W(s)∥=∥Δ(s)∥\lVert U(\delta-s)\Delta(s)W(s)\rVert\le\lVert U(\delta-s)\rVert\,\lVert\Delta(s)\rVert\,\lVert W(s)\rVert=\lVert\Delta(s)\rVert
    Submultiplicativity of the operator norm and ∥U∥=1\lVert U\rVert=1 for unitary UU.

∎

Lemma

Taylor expansion of a conjugated operator

For Hermitian AA, any matrix BB and real uu, let g(u)=eiAuBe−iAug(u)=e^{iAu}Be^{-iAu}. Then (i) ∥g(u)−B∥≤∣u∣ ∥[A,B]∥\lVert g(u)-B\rVert\le\lvert u\rvert\,\lVert[A,B]\rVert, and (ii) g(u)=B+iu[A,B]+R(u)g(u)=B+iu[A,B]+R(u) with ∥R(u)∥≤u22∥[A,[A,B]]∥\lVert R(u)\rVert\le\frac{u^2}{2}\lVert[A,[A,B]]\rVert.

Proof (6 steps)
  1. Step 1:
    g′(u)=eiAu(iAB−iBA)e−iAu=i eiAu[A,B] e−iAug'(u)=e^{iAu}\big(iAB-iBA\big)e^{-iAu}=i\,e^{iAu}[A,B]\,e^{-iAu}
    Product rule with ddue±iAu=±iAe±iAu=±ie±iAuA\frac{d}{du}e^{\pm iAu}=\pm iAe^{\pm iAu}=\pm ie^{\pm iAu}A.
  2. Step 2:
    g(u)−B=∫0ug′(v) dv,∥eiAvCe−iAv∥=∥C∥g(u)-B=\int_0^ug'(v)\,dv,\qquad\lVert e^{iAv}Ce^{-iAv}\rVert=\lVert C\rVert
    Fundamental theorem of calculus; the operator norm is invariant under unitary conjugation.
  3. Step 3:
    ∥g(u)−B∥≤∣∫0u∥[A,B]∥ dv∣=∣u∣ ∥[A,B]∥\lVert g(u)-B\rVert\le\Big\lvert\int_0^u\lVert[A,B]\rVert\,dv\Big\rvert=\lvert u\rvert\,\lVert[A,B]\rVert
    Statement (i).
  4. Step 4:
    g′′(u)=i⋅i eiAu[A,[A,B]] e−iAu=−eiAu[A,[A,B]] e−iAug''(u)=i\cdot i\,e^{iAu}[A,[A,B]]\,e^{-iAu}=-e^{iAu}[A,[A,B]]\,e^{-iAu}
    Apply the first step to [A,B][A,B] in place of BB.
  5. Step 5:
    g(u)=g(0)+u g′(0)+∫0u(u−v) g′′(v) dv=B+iu[A,B]+R(u)g(u)=g(0)+u\,g'(0)+\int_0^u(u-v)\,g''(v)\,dv=B+iu[A,B]+R(u)
    Taylor's formula with integral remainder, obtained by integrating ∫0u(u−v)g′′(v)dv\int_0^u(u-v)g''(v)dv by parts.
  6. Step 6:
    ∥R(u)∥≤∣∫0u∣u−v∣ dv∣ ∥[A,[A,B]]∥=u22∥[A,[A,B]]∥\lVert R(u)\rVert\le\Big\lvert\int_0^u\lvert u-v\rvert\,dv\Big\rvert\,\lVert[A,[A,B]]\rVert=\frac{u^2}{2}\lVert[A,[A,B]]\rVert
    Statement (ii), again by unitary invariance of the norm.

∎

Theorem

One-step error of the first-order formula

For Hermitian A,BA,B and δ≥0\delta\ge0, ∥e−i(A+B)δ−e−iAδe−iBδ∥≤δ22 ∥[A,B]∥.\big\lVert e^{-i(A+B)\delta}-e^{-iA\delta}e^{-iB\delta}\big\rVert\le\frac{\delta^2}{2}\,\lVert[A,B]\rVert .

Proof (5 steps)
  1. Step 1:
    V(s)=e−iAse−iBs,V′(s)=−iA V(s)+e−iAs(−iB)e−iBsV(s)=e^{-iAs}e^{-iBs},\qquad V'(s)=-iA\,V(s)+e^{-iAs}(-iB)e^{-iBs}
    Product rule.
  2. Step 2:
    e−iAsBe−iBs=(e−iAsBeiAs)V(s) ⇒ V′(s)=−i(A+B+Δ1(s))V(s),Δ1(s)=e−iAsBeiAs−Be^{-iAs}Be^{-iBs}=\big(e^{-iAs}Be^{iAs}\big)V(s)\ \Rightarrow\ V'(s)=-i\big(A+B+\Delta_1(s)\big)V(s),\quad\Delta_1(s)=e^{-iAs}Be^{iAs}-B
    Insert I=eiAse−iAsI=e^{iAs}e^{-iAs} between BB and e−iBse^{-iBs}, then add and subtract BB.
  3. Step 3:
    ∥V(δ)−U(δ)∥≤∫0δ∥Δ1(s)∥ ds\lVert V(\delta)-U(\delta)\rVert\le\int_0^\delta\lVert\Delta_1(s)\rVert\,ds
    Duhamel lemma with W=VW=V, which is unitary.
  4. Step 4:
    Δ1(s)=g(−s)−B ⇒ ∥Δ1(s)∥≤s ∥[A,B]∥\Delta_1(s)=g(-s)-B\ \Rightarrow\ \lVert\Delta_1(s)\rVert\le s\,\lVert[A,B]\rVert
    Conjugation lemma (i) with u=−su=-s.
  5. Step 5:
    ∥V(δ)−U(δ)∥≤∥[A,B]∥∫0δs ds=δ22∥[A,B]∥\lVert V(\delta)-U(\delta)\rVert\le\lVert[A,B]\rVert\int_0^\delta s\,ds=\frac{\delta^2}{2}\lVert[A,B]\rVert
    Integrate. For commuting A,BA,B the bound is 00, in agreement with the commuting-exponentials theorem.

∎

Derivation

The leading error term −(δ²/2)[A,B] (Baker–Campbell–Hausdorff)

  1. Step 1:
    e−iAδe−iBδ=(I−iAδ−δ22A2)(I−iBδ−δ22B2)+O(δ3)=I−i(A+B)δ−δ22(A2+2AB+B2)+O(δ3)e^{-iA\delta}e^{-iB\delta}=\big(I-iA\delta-\tfrac{\delta^2}2A^2\big)\big(I-iB\delta-\tfrac{\delta^2}2B^2\big)+O(\delta^3)=I-i(A+B)\delta-\tfrac{\delta^2}{2}\big(A^2+2AB+B^2\big)+O(\delta^3)
    Multiply the second-order Taylor polynomials; the cross term is (−iAδ)(−iBδ)=−ABδ2(-iA\delta)(-iB\delta)=-AB\delta^2.
  2. Step 2:
    e−i(A+B)δ=I−i(A+B)δ−δ22(A2+AB+BA+B2)+O(δ3)e^{-i(A+B)\delta}=I-i(A+B)\delta-\tfrac{\delta^2}{2}\big(A^2+AB+BA+B^2\big)+O(\delta^3)
    Expand (A+B)2(A+B)^2 without commuting AA and BB.
  3. Step 3:
    V(δ)−U(δ)=−δ22(AB−BA)+O(δ3)=−δ22[A,B]+O(δ3)V(\delta)-U(\delta)=-\tfrac{\delta^2}{2}\big(AB-BA\big)+O(\delta^3)=-\tfrac{\delta^2}{2}[A,B]+O(\delta^3)
    Subtract: everything up to first order agrees.
  4. Step 4:
    eXeY=exp⁡(X+Y+12[X,Y]+O(∥X∥3+∥Y∥3)),12[−iAδ,−iBδ]=−δ22[A,B]e^{X}e^{Y}=\exp\big(X+Y+\tfrac12[X,Y]+O(\lVert X\rVert^3+\lVert Y\rVert^3)\big),\qquad\tfrac12[-iA\delta,-iB\delta]=-\tfrac{\delta^2}{2}[A,B]
    Baker–Campbell–Hausdorff formula with X=−iAδX=-iA\delta, Y=−iBδY=-iB\delta: the same term appears as the first correction to the exponent.
  5. Step 5:
    ∥V(δ)−U(δ)∥=δ22∥[A,B]∥+O(δ3)\lVert V(\delta)-U(\delta)\rVert=\tfrac{\delta^2}{2}\lVert[A,B]\rVert+O(\delta^3)
    The rigorous bound of the theorem is attained to leading order, so the constant 12\tfrac12 cannot be improved. The lesson tests confirm ∥(V−U)/δ2+12[A,B]∥=O(δ)\lVert(V-U)/\delta^2+\tfrac12[A,B]\rVert=O(\delta) numerically at δ=10−3\delta=10^{-3}.
Lemma

Telescoping lemma

For unitaries U,VU,V and every integer r≥1r\ge1, Ur−Vr=∑k=0r−1Ur−1−k (U−V) Vk,∥Ur−Vr∥≤r ∥U−V∥.U^r-V^r=\sum_{k=0}^{r-1}U^{r-1-k}\,(U-V)\,V^k,\qquad\lVert U^r-V^r\rVert\le r\,\lVert U-V\rVert .

Proof (4 steps)
  1. Step 1:
    Ur−1−k(U−V)Vk=Ur−kVk−Ur−1−kVk+1=ak−ak+1,ak:=Ur−kVkU^{r-1-k}(U-V)V^k=U^{r-k}V^k-U^{r-1-k}V^{k+1}=a_k-a_{k+1},\qquad a_k:=U^{r-k}V^k
    Distribute the product.
  2. Step 2:
    ∑k=0r−1(ak−ak+1)=a0−ar=Ur−Vr\sum_{k=0}^{r-1}(a_k-a_{k+1})=a_0-a_r=U^r-V^r
    Telescoping sum: all intermediate terms cancel.
  3. Step 3:
    ∥Ur−Vr∥≤∑k=0r−1∥Ur−1−k∥ ∥U−V∥ ∥Vk∥\lVert U^r-V^r\rVert\le\sum_{k=0}^{r-1}\lVert U^{r-1-k}\rVert\,\lVert U-V\rVert\,\lVert V^k\rVert
    Triangle inequality and submultiplicativity.
  4. Step 4:
    ∥Uj∥=∥Vj∥=1 ⇒ ∥Ur−Vr∥≤r ∥U−V∥\lVert U^{j}\rVert=\lVert V^{j}\rVert=1\ \Rightarrow\ \lVert U^r-V^r\rVert\le r\,\lVert U-V\rVert
    Powers of unitaries are unitary; there are rr terms. Errors of the individual steps can at worst add up.

∎

Theorem

First-order Trotter–Suzuki bound

For Hermitian A,BA,B, t≥0t\ge0 and r≥1r\ge1, e−i(A+B)t=(e−iAt/re−iBt/r)r+E,∥E∥≤t22r ∥[A,B]∥.e^{-i(A+B)t}=\big(e^{-iAt/r}e^{-iBt/r}\big)^r+E,\qquad\lVert E\rVert\le\frac{t^2}{2r}\,\lVert[A,B]\rVert . Hence r≥t2∥[A,B]∥2εr\ge\frac{t^2\lVert[A,B]\rVert}{2\varepsilon} steps guarantee ∥E∥≤ε\lVert E\rVert\le\varepsilon, and the gate count grows as O(t2/ε)O(t^2/\varepsilon).

Proof (5 steps)
  1. Step 1:
    e−i(A+B)t=(e−i(A+B)t/r)r=U(t/r)re^{-i(A+B)t}=\big(e^{-i(A+B)t/r}\big)^r=U(t/r)^r
    e−iHte^{-iHt} is a product of rr copies of e−iHt/re^{-iHt/r} by the commuting-exponentials theorem (HH commutes with itself).
  2. Step 2:
    ∥E∥=∥U(t/r)r−V(t/r)r∥≤r ∥U(t/r)−V(t/r)∥\lVert E\rVert=\lVert U(t/r)^r-V(t/r)^r\rVert\le r\,\lVert U(t/r)-V(t/r)\rVert
    Telescoping lemma.
  3. Step 3:
    ∥U(t/r)−V(t/r)∥≤(t/r)22∥[A,B]∥\lVert U(t/r)-V(t/r)\rVert\le\frac{(t/r)^2}{2}\lVert[A,B]\rVert
    One-step theorem with δ=t/r\delta=t/r.
  4. Step 4:
    ∥E∥≤r⋅t22r2∥[A,B]∥=t22r∥[A,B]∥\lVert E\rVert\le r\cdot\frac{t^2}{2r^2}\lVert[A,B]\rVert=\frac{t^2}{2r}\lVert[A,B]\rVert
    Combine.
  5. Step 5:
    t22r∥[A,B]∥≤ε  ⟺  r≥t2∥[A,B]∥2ε\frac{t^2}{2r}\lVert[A,B]\rVert\le\varepsilon\iff r\ge\frac{t^2\lVert[A,B]\rVert}{2\varepsilon}
    Solve for rr. Each step costs a fixed number of gates (two compiled exponentials), so the total is proportional to r=O(t2/ε)r=O(t^2/\varepsilon).

∎

Derivation

Worked example: A = X⊗I, B = Z⊗I at t = 1

  1. Step 1:
    [A,B]=[X,Z]⊗I=−2iY⊗I,∥[A,B]∥=2,bound=t22r⋅2=1r[A,B]=[X,Z]\otimes I=-2iY\otimes I,\qquad\lVert[A,B]\rVert=2,\qquad\text{bound}=\frac{t^2}{2r}\cdot2=\frac1r
    XZ=−iYXZ=-iY, ZX=iYZX=iY; ∥Y∥=1\lVert Y\rVert=1. Both terms act on qubit 00 only, so the computation reduces to 2×22\times2 matrices tensored with II.
  2. Step 2:
    U(1)=e−i(X+Z)=cos⁡2 I−isin⁡2 X+Z2U(1)=e^{-i(X+Z)}=\cos\sqrt2\,I-i\sin\sqrt2\,\frac{X+Z}{\sqrt2}
    N=(X+Z)/2N=(X+Z)/\sqrt2 satisfies N2=IN^2=I, so e−i2N=cos⁡2 I−isin⁡2 Ne^{-i\sqrt2N}=\cos\sqrt2\,I-i\sin\sqrt2\,N.
  3. Step 3:
    V(1)=e−iXe−iZ=(cos⁡1−isin⁡1X)(cos⁡1−isin⁡1Z)=cos⁡21 I−isin⁡1cos⁡1 (X+Z)+isin⁡21 YV(1)=e^{-iX}e^{-iZ}=(\cos1-i\sin1X)(\cos1-i\sin1Z)=\cos^21\,I-i\sin1\cos1\,(X+Z)+i\sin^21\,Y
    The last term is −sin⁡21 XZ=−sin⁡21(−iY)-\sin^21\,XZ=-\sin^21(-iY).
  4. Step 4:
    12Tr(U(1)†V(1))=cos⁡2cos⁡21+2sin⁡2 sin⁡1cos⁡1≈0.680628=:cos⁡γ\tfrac12\mathrm{Tr}\big(U(1)^\dagger V(1)\big)=\cos\sqrt2\cos^21+\sqrt2\sin\sqrt2\,\sin1\cos1\approx0.680628=:\cos\gamma
    U†=cos⁡2I+isin⁡2NU^\dagger=\cos\sqrt2I+i\sin\sqrt2N; XX, YY, ZZ and the products XY=iZXY=iZ, ZY=−iXZY=-iX are traceless and 12Tr((X+Z)2)=2\tfrac12\mathrm{Tr}\big((X+Z)^2\big)=2, so only two products survive.
  5. Step 5:
    W=U†V∈SU(2),  spec(W)={e±iγ} ⇒ ∥U−V∥=∥I−W∥=∣1−eiγ∣=2−2cos⁡γ≈0.799214W=U^\dagger V\in SU(2),\ \ \mathrm{spec}(W)=\{e^{\pm i\gamma}\}\ \Rightarrow\ \lVert U-V\rVert=\lVert I-W\rVert=\lvert1-e^{i\gamma}\rvert=\sqrt{2-2\cos\gamma}\approx0.799214
    ∥U−V∥=∥U(I−W)∥=∥I−W∥\lVert U-V\rVert=\lVert U(I-W)\rVert=\lVert I-W\rVert; WW has determinant 11 and trace 2cos⁡γ2\cos\gamma, so its eigenvalues are e±iγe^{\pm i\gamma}, and I−WI-W is normal with eigenvalues 1−e±iγ1-e^{\pm i\gamma}.
  6. Step 6:
    r=1: 0.799214≤1,r=2: 0.362410≤0.5,r=4: 0.176261≤0.25r=1:\ 0.799214\le1,\qquad r=2:\ 0.362410\le0.5,\qquad r=4:\ 0.176261\le0.25
    The values for r=2,4r=2,4 are computed from ∥U(1)−V(1r)r∥\lVert U(1)-V(\tfrac1r)^r\rVert in the lesson tests; each doubling of rr roughly halves the error, the 1/r1/r scaling predicted by the theorem.

Result

∥e−i(X+Z)−(e−iX/re−iZ/r)r∥≤1r,attained values 0.799, 0.362, 0.176 (r=1,2,4)\boxed{\big\lVert e^{-i(X+Z)}-\big(e^{-iX/r}e^{-iZ/r}\big)^r\big\rVert\le\frac1r,\qquad\text{attained values }0.799,\ 0.362,\ 0.176\ (r=1,2,4)}

The widget evaluates ∥e−i(A+B)t−V(t/r)r∥\lVert e^{-i(A+B)t}-V(t/r)^r\rVert and ∥e−i(A+B)t−S(t/r)r∥\lVert e^{-i(A+B)t}-S(t/r)^r\rVert for r=1,…,r=1,\dots, maxSteps on log–log axes, together with the two bounds. For the transverse-field Ising pair A=Z⊗ZA=Z\otimes Z, B=12(X⊗I+I⊗X)B=\tfrac12(X\otimes I+I\otimes X) one computes ∥[A,B]∥=2\lVert[A,B]\rVert=2 and ∥[A,[A,B]]∥=∥[B,[B,A]]∥=4\lVert[A,[A,B]]\rVert=\lVert[B,[B,A]]\rVert=4: the first-order curve has slope −1-1, the second-order curve slope −2-2, both below their bounds.

Theorem

Second-order (symmetric) Trotter–Suzuki bound

For Hermitian A,BA,B and δ≥0\delta\ge0, ∥e−i(A+B)δ−e−iAδ/2e−iBδe−iAδ/2∥≤δ312∥[B,[B,A]]∥+δ324∥[A,[A,B]]∥,\big\lVert e^{-i(A+B)\delta}-e^{-iA\delta/2}e^{-iB\delta}e^{-iA\delta/2}\big\rVert\le\frac{\delta^3}{12}\lVert[B,[B,A]]\rVert+\frac{\delta^3}{24}\lVert[A,[A,B]]\rVert, and therefore ∥e−i(A+B)t−S(t/r)r∥≤t312r2∥[B,[B,A]]∥+t324r2∥[A,[A,B]]∥=O(t3/r2).\big\lVert e^{-i(A+B)t}-S(t/r)^r\big\rVert\le\frac{t^3}{12r^2}\lVert[B,[B,A]]\rVert+\frac{t^3}{24r^2}\lVert[A,[A,B]]\rVert=O\big(t^3/r^2\big). These are the commutator constants of Childs, Su, Tran, Wiebe and Zhu (2021).

Proof (9 steps)
  1. Step 1:
    S′(s)=−i2A S−i e−iAs/2Be−iBse−iAs/2−i2 S A=−i(A2+e−iAs/2BeiAs/2+12SAS†)SS'(s)=-\tfrac i2A\,S-i\,e^{-iAs/2}Be^{-iBs}e^{-iAs/2}-\tfrac i2\,S\,A=-i\Big(\tfrac A2+e^{-iAs/2}Be^{iAs/2}+\tfrac12SAS^\dagger\Big)S
    Product rule on the three factors of S(s)S(s); insert eiAs/2e−iAs/2e^{iAs/2}e^{-iAs/2} in the middle term and write SA=(SAS†)SSA=(SAS^\dagger)S in the last one.
  2. Step 2:
    S′(s)=−i(A+B+Δ2(s))S(s),Δ2(s)=(e−iAs/2BeiAs/2−B)+12(SAS†−A)S'(s)=-i\big(A+B+\Delta_2(s)\big)S(s),\qquad\Delta_2(s)=\big(e^{-iAs/2}Be^{iAs/2}-B\big)+\tfrac12\big(SAS^\dagger-A\big)
    Add and subtract BB and A2\tfrac A2.
  3. Step 3:
    SAS†=e−iAs/2C(s)eiAs/2,  C(s):=e−iBsAeiBs ⇒ ∥Δ2(s)∥=∥B−eiAs/2Be−iAs/2+12(C(s)−A)∥SAS^\dagger=e^{-iAs/2}C(s)e^{iAs/2},\ \ C(s):=e^{-iBs}Ae^{iBs}\ \Rightarrow\ \lVert\Delta_2(s)\rVert=\big\lVert B-e^{iAs/2}Be^{-iAs/2}+\tfrac12\big(C(s)-A\big)\big\rVert
    The outer factors e∓iAs/2e^{\mp iAs/2} of SS commute with AA; factor e−iAs/2(⋅)eiAs/2e^{-iAs/2}(\cdot)e^{iAs/2} out of both brackets, using e−iAs/2AeiAs/2=Ae^{-iAs/2}Ae^{iAs/2}=A, and drop it by unitary invariance.
  4. Step 4:
    B−eiAs/2Be−iAs/2=−is2[A,B]+R1,∥R1∥≤s28∥[A,[A,B]]∥B-e^{iAs/2}Be^{-iAs/2}=-\tfrac{is}{2}[A,B]+R_1,\qquad\lVert R_1\rVert\le\tfrac{s^2}{8}\lVert[A,[A,B]]\rVert
    Conjugation lemma (ii) with u=s/2u=s/2: (s/2)2/2=s2/8(s/2)^2/2=s^2/8.
  5. Step 5:
    C(s)=A−is[B,A]+R2=A+is[A,B]+R2,∥R2∥≤s22∥[B,[B,A]]∥C(s)=A-is[B,A]+R_2=A+is[A,B]+R_2,\qquad\lVert R_2\rVert\le\tfrac{s^2}{2}\lVert[B,[B,A]]\rVert
    Conjugation lemma (ii) with the roles of AA and BB exchanged and u=−su=-s.
  6. Step 6:
    Δ2-bracket=−is2[A,B]+is2[A,B]+R1+12R2=R1+12R2\Delta_2\text{-bracket}=-\tfrac{is}{2}[A,B]+\tfrac{is}{2}[A,B]+R_1+\tfrac12R_2=R_1+\tfrac12R_2
    The first-order terms cancel: the half step of AA before and after BB contributes ±is2[A,B]\pm\tfrac{is}2[A,B] symmetrically. This is the source of the extra order.
  7. Step 7:
    ∥Δ2(s)∥≤s28∥[A,[A,B]]∥+s24∥[B,[B,A]]∥\lVert\Delta_2(s)\rVert\le\tfrac{s^2}{8}\lVert[A,[A,B]]\rVert+\tfrac{s^2}{4}\lVert[B,[B,A]]\rVert
    Triangle inequality.
  8. Step 8:
    ∥S(δ)−U(δ)∥≤∫0δ(s28∥[A,[A,B]]∥+s24∥[B,[B,A]]∥)ds=δ324∥[A,[A,B]]∥+δ312∥[B,[B,A]]∥\lVert S(\delta)-U(\delta)\rVert\le\int_0^\delta\Big(\tfrac{s^2}{8}\lVert[A,[A,B]]\rVert+\tfrac{s^2}{4}\lVert[B,[B,A]]\rVert\Big)ds=\tfrac{\delta^3}{24}\lVert[A,[A,B]]\rVert+\tfrac{\delta^3}{12}\lVert[B,[B,A]]\rVert
    Duhamel lemma with W=SW=S (unitary) and ∫0δs2ds=δ3/3\int_0^\delta s^2ds=\delta^3/3.
  9. Step 9:
    ∥U(t)−S(t/r)r∥≤r ∥U(t/r)−S(t/r)∥≤r(tr)3(112∥[B,[B,A]]∥+124∥[A,[A,B]]∥)\lVert U(t)-S(t/r)^r\rVert\le r\,\lVert U(t/r)-S(t/r)\rVert\le r\Big(\frac tr\Big)^3\Big(\tfrac1{12}\lVert[B,[B,A]]\rVert+\tfrac1{24}\lVert[A,[A,B]]\rVert\Big)
    Telescoping lemma with δ=t/r\delta=t/r; r(t/r)3=t3/r2r(t/r)^3=t^3/r^2.

∎

Derivation

Why the second-order term cancels

  1. Step 1:
    e−iAδ/2=I−iδ2A−δ28A2+O(δ3),e−iBδ=I−iδB−δ22B2+O(δ3)e^{-iA\delta/2}=I-\tfrac{i\delta}2A-\tfrac{\delta^2}8A^2+O(\delta^3),\qquad e^{-iB\delta}=I-i\delta B-\tfrac{\delta^2}2B^2+O(\delta^3)
    Second-order Taylor polynomials of the three factors.
  2. Step 2:
    [δ2] S(δ)=−18A2−12B2−18A2+(−12AB)+(−14A2)+(−12BA)[\delta^2]\,S(\delta)=-\tfrac18A^2-\tfrac12B^2-\tfrac18A^2+\big(-\tfrac12AB\big)+\big(-\tfrac14A^2\big)+\big(-\tfrac12BA\big)
    Second-order terms of single factors, plus the three products of first-order terms (first·second, first·third, second·third factor), e.g. (−iδ2A)(−iδB)=−δ22AB(-\tfrac{i\delta}2A)(-i\delta B)=-\tfrac{\delta^2}2AB.
  3. Step 3:
    [δ2] S(δ)=−12(A2+AB+BA+B2)=−12(A+B)2=[δ2] e−i(A+B)δ[\delta^2]\,S(\delta)=-\tfrac12\big(A^2+AB+BA+B^2\big)=-\tfrac12(A+B)^2=[\delta^2]\,e^{-i(A+B)\delta}
    Collect terms: the δ2\delta^2 coefficients agree, so S(δ)−U(δ)=O(δ3)S(\delta)-U(\delta)=O(\delta^3), whereas for VV they differ by −12[A,B]-\tfrac12[A,B].
  4. Step 4:
    S(δ)S(−δ)=e−iAδ/2e−iBδe−iAδ/2eiAδ/2eiBδeiAδ/2=IS(\delta)S(-\delta)=e^{-iA\delta/2}e^{-iB\delta}e^{-iA\delta/2}e^{iA\delta/2}e^{iB\delta}e^{iA\delta/2}=I
    Symmetry: the inner factors cancel pairwise, so S(−δ)=S(δ)−1S(-\delta)=S(\delta)^{-1}.
  5. Step 5:
    S(δ)=eΩ(δ),  Ω(−δ)=−Ω(δ) ⇒ Ω(δ)=−i(A+B)δ+δ3Ω3+O(δ5)S(\delta)=e^{\Omega(\delta)},\ \ \Omega(-\delta)=-\Omega(\delta)\ \Rightarrow\ \Omega(\delta)=-i(A+B)\delta+\delta^3\Omega_3+O(\delta^5)
    For small δ\delta, S(δ)S(\delta) is near II and has a unique logarithm Ω(δ)\Omega(\delta) near 00; S(−δ)=S(δ)−1S(-\delta)=S(\delta)^{-1} forces Ω\Omega to be odd, so all even orders vanish.
  6. Step 6:
    δ3Ω3=iδ3(112[B,[B,A]]−124[A,[A,B]]) ⇒ S(δ)−U(δ)=δ3Ω3+O(δ4)\delta^3\Omega_3=i\delta^3\Big(\tfrac1{12}[B,[B,A]]-\tfrac1{24}[A,[A,B]]\Big)\ \Rightarrow\ S(\delta)-U(\delta)=\delta^3\Omega_3+O(\delta^4)
    Symmetric BCH formula log⁡(eX/2eYeX/2)=X+Y+112[Y,[Y,X]]−124[X,[X,Y]]+…\log(e^{X/2}e^Ye^{X/2})=X+Y+\tfrac1{12}[Y,[Y,X]]-\tfrac1{24}[X,[X,Y]]+\dots with X=−iAδX=-iA\delta, Y=−iBδY=-iB\delta; the constants 112\tfrac1{12}, 124\tfrac1{24} of the theorem are exactly those of the leading term (checked numerically in the lesson tests at δ=10−3\delta=10^{-3}).

In the commuting preset, A=X⊗X+Y⊗YA=X\otimes X+Y\otimes Y and B=Z⊗ZB=Z\otimes Z commute (each of X⊗XX\otimes X and Y⊗YY\otimes Y commutes with Z⊗ZZ\otimes Z, since the two anticommuting factors give two signs that cancel), so both errors and both bounds vanish identically for every rr: product formulas are only needed for genuinely non-commuting terms. The Z-type feature Hamiltonians of the next section are of this commuting kind, which is why they can be compiled exactly.

Quick check

For the Ising pair A=Z⊗ZA=Z\otimes Z, B=12(X⊗I+I⊗X)B=\tfrac12(X\otimes I+I\otimes X) with ∥[A,B]∥=2\lVert[A,B]\rVert=2 and t=1t=1, what is the smallest number of first-order steps rr for which the bound t22r∥[A,B]∥\frac{t^2}{2r}\lVert[A,B]\rVert guarantees an error of at most 0.010.01?

tolerance ±1e-9

The ZZ feature map#

Definition

ZZ feature map (Havlíček et al. 2019; Qiskit convention)

For x∈Rnx\in\mathbb R^n let ϕj(x)=xj\phi_j(x)=x_j and ϕjk(x)=(π−xj)(π−xk)\phi_{jk}(x)=(\pi-x_j)(\pi-x_k). One repetition of the ZZ feature map is UΦ(x)=[∏j<kCNOTjk Pk(2ϕjk(x)) CNOTjk][∏jPj(2ϕj(x))]H⊗n,U_\Phi(x)=\Big[\prod_{j<k}\mathrm{CNOT}_{jk}\,P_k\big(2\phi_{jk}(x)\big)\,\mathrm{CNOT}_{jk}\Big]\Big[\prod_{j}P_j\big(2\phi_j(x)\big)\Big]H^{\otimes n}, and the map with reps =r=r repetitions prepares ∣ϕ(x)⟩=UΦ(x)r∣0n⟩\lvert\phi(x)\rangle=U_\Phi(x)^r\lvert0^n\rangle. Qiskit's ZZFeatureMap uses r=2r=2 and all pairs j<kj<k by default. The fidelity kernel is K(x,x′)=∣⟨ϕ(x)∣ϕ(x′)⟩∣2K(x,x')=\lvert\langle\phi(x)\vert\phi(x')\rangle\rvert^2.

Proposition

The ZZ feature map is an exact Hamiltonian evolution

(i) P(λ)=eiλ/2RZ(λ)P(\lambda)=e^{i\lambda/2}R_Z(\lambda); in particular P(2φ)=eiφRZ(2φ)=eiφe−iφZP(2\varphi)=e^{i\varphi}R_Z(2\varphi)=e^{i\varphi}e^{-i\varphi Z}. (ii) The diagonal part of UΦ(x)U_\Phi(x) equals eiγ(x)e−iHΦ(x)e^{i\gamma(x)}e^{-iH_\Phi(x)} with HΦ(x)=∑jxj Zj+∑j<k(π−xj)(π−xk) ZjZk,γ(x)=∑jϕj(x)+∑j<kϕjk(x),H_\Phi(x)=\sum_jx_j\,Z_j+\sum_{j<k}(\pi-x_j)(\pi-x_k)\,Z_jZ_k,\qquad\gamma(x)=\sum_j\phi_j(x)+\sum_{j<k}\phi_{jk}(x), exactly, with no Trotter error. (iii) The fidelity kernel does not depend on the global phase eiγ(x)e^{i\gamma(x)}, nor on the sign convention exp⁡(+i∑SϕS(x)ZS)\exp\big(+i\sum_S\phi_S(x)Z_S\big) used by Havlíček et al.

Proof (6 steps)
  1. Step 1:
    P(λ)=(100eiλ)=eiλ/2(e−iλ/200eiλ/2)=eiλ/2RZ(λ)P(\lambda)=\begin{pmatrix}1&0\\0&e^{i\lambda}\end{pmatrix}=e^{i\lambda/2}\begin{pmatrix}e^{-i\lambda/2}&0\\0&e^{i\lambda/2}\end{pmatrix}=e^{i\lambda/2}R_Z(\lambda)
    Factor eiλ/2e^{i\lambda/2} out of both diagonal entries. With λ=2φ\lambda=2\varphi: P(2φ)=eiφRZ(2φ)=eiφe−iφZP(2\varphi)=e^{i\varphi}R_Z(2\varphi)=e^{i\varphi}e^{-i\varphi Z}.
  2. Step 2:
    CNOTjkPk(2φ)CNOTjk=eiφ CNOTjkRZ(k)(2φ)CNOTjk=eiφe−iφZjZk\mathrm{CNOT}_{jk}P_k(2\varphi)\mathrm{CNOT}_{jk}=e^{i\varphi}\,\mathrm{CNOT}_{jk}R_Z^{(k)}(2\varphi)\mathrm{CNOT}_{jk}=e^{i\varphi}e^{-i\varphi Z_jZ_k}
    Pull the scalar out and apply the ZZ rotation identity with θ=2φ\theta=2\varphi on the qubit pair (j,k)(j,k) (identity on the other qubits).
  3. Step 3:
    ∏jPj(2xj)=∏jeixje−ixjZj\prod_jP_j(2x_j)=\prod_je^{ix_j}e^{-ix_jZ_j}
    Part (i) on every qubit.
  4. Step 4:
    [∏j<keiϕjke−iϕjkZjZk][∏jeiϕje−iϕjZj]=eiγ(x)exp⁡(−i∑jϕjZj−i∑j<kϕjkZjZk)\Big[\prod_{j<k}e^{i\phi_{jk}}e^{-i\phi_{jk}Z_jZ_k}\Big]\Big[\prod_je^{i\phi_j}e^{-i\phi_jZ_j}\Big]=e^{i\gamma(x)}\exp\Big(-i\sum_j\phi_jZ_j-i\sum_{j<k}\phi_{jk}Z_jZ_k\Big)
    All factors are diagonal and commute (diagonal-evolution theorem), so the commuting-exponentials theorem merges them into a single exponential of −iHΦ(x)-iH_\Phi(x), exactly.
  5. Step 5:
    ∣⟨eiαϕ(x)∣eiβϕ(x′)⟩∣2=∣ei(β−α)∣2∣⟨ϕ(x)∣ϕ(x′)⟩∣2=∣⟨ϕ(x)∣ϕ(x′)⟩∣2\big\lvert\langle e^{i\alpha}\phi(x)\vert e^{i\beta}\phi(x')\rangle\big\rvert^2=\big\lvert e^{i(\beta-\alpha)}\big\rvert^2\lvert\langle\phi(x)\vert\phi(x')\rangle\rvert^2=\lvert\langle\phi(x)\vert\phi(x')\rangle\rvert^2
    With rr repetitions the phase becomes eirγ(x)e^{ir\gamma(x)}, still a global phase of the state; it drops out of the squared modulus.
  6. Step 6:
    D±(x)=e±iHΦ(x)=D∓(x)‾,  H=H‾ ⇒ ∣ϕ+(x)⟩=∣ϕ−(x)⟩‾,  ⟨ϕ+(x)∣ϕ+(x′)⟩=⟨ϕ−(x)∣ϕ−(x′)⟩‾D_\pm(x)=e^{\pm iH_\Phi(x)}=\overline{D_\mp(x)},\ \ H=\overline H\ \Rightarrow\ \lvert\phi_+(x)\rangle=\overline{\lvert\phi_-(x)\rangle},\ \ \langle\phi_+(x)\vert\phi_+(x')\rangle=\overline{\langle\phi_-(x)\vert\phi_-(x')\rangle}
    A real diagonal exponent makes D+D_+ the entrywise complex conjugate of D−D_-; Hadamard matrices and ∣0n⟩\lvert0^n\rangle are real, so the whole state is conjugated, and conjugation preserves the modulus of the overlap.

∎

Circuit · 2 qubits

Quantum circuit on 2 qubitsH on q0; H on q1; P(0.80) on q0; P(2.20) on q1; X on q1 controlled by q0; P(11.19) on q1; X on q1 controlled by q0q0q1HHP(0.80)P(2.20)P(11.19)

Two-qubit ZZ feature map (one repetition, Qiskit convention) at x=(0.4,1.1)x=(0.4,1.1): H⊗HH\otimes H, then P(0.8)P(0.8) on qubit 00 and P(2.2)P(2.2) on qubit 11, then CNOT(0,1)\mathrm{CNOT}(0,1), P(2(π−0.4)(π−1.1))≈P(11.1944)P\big(2(\pi-0.4)(\pi-1.1)\big)\approx P(11.1944) on qubit 11, CNOT(0,1)\mathrm{CNOT}(0,1).

∣ψ⟩=12∣00⟩+(0.3382+0.3683i)∣01⟩+(0.4204−0.2706i)∣10⟩+(−0.495+0.0706i)∣11⟩\lvert\psi\rangle = \tfrac{1}{2}\lvert 00\rangle + \left(0.3382 + 0.3683i\right)\lvert 01\rangle + \left(0.4204 - 0.2706i\right)\lvert 10\rangle + \left(-0.495 + 0.0706i\right)\lvert 11\rangle

The platform's implementation. The function zzFeatureMap in the QML library builds the same circuit with RZ(2xj)R_Z(2x_j) in place of P(2xj)P(2x_j) and CNOTjkRZ(k)(2ϕjk)CNOTjk\mathrm{CNOT}_{jk}R_Z^{(k)}(2\phi_{jk})\mathrm{CNOT}_{jk} in place of the phase-gate sandwich, that is, exactly e−iHΦ(x)H⊗ne^{-iH_\Phi(x)}H^{\otimes n} per repetition, without the global phase. Its defaults are reps =2=2 and entanglement == linear (pairs (j,j+1)(j,j+1) only), whereas Qiskit's default is all pairs; for n=2n=2 the two coincide. By part (ii) the two circuits differ by the global phase eirγ(x)e^{ir\gamma(x)}, and by part (iii) they define the same kernel. The lesson tests verify this statevector identity for the example above.

Proposition

With one repetition the kernel is classically estimable

For reps =1=1 write θx(b)=∑SϕS(x)(−1)∑j∈Sbj\theta_x(b)=\sum_S\phi_S(x)(-1)^{\sum_{j\in S}b_j}. Then ⟨ϕ(x′)∣ϕ(x)⟩=ei(γ(x)−γ(x′)) Eb[e−i(θx(b)−θx′(b))]\langle\phi(x')\vert\phi(x)\rangle=e^{i(\gamma(x)-\gamma(x'))}\,\mathbb E_b\big[e^{-i(\theta_x(b)-\theta_{x'}(b))}\big] with bb uniform on {0,1}n\{0,1\}^n. Averaging m≥2ε2ln⁡4ηm\ge\frac{2}{\varepsilon^2}\ln\frac4\eta independent samples gives an estimate K^\hat K with ∣K^−K(x,x′)∣≤22 ε\lvert\hat K-K(x,x')\rvert\le2\sqrt2\,\varepsilon with probability at least 1−η1-\eta, in classical time O(mn2)O(mn^2).

Proof (6 steps)
  1. Step 1:
    H⊗n∣0n⟩=2−n/2∑b∣b⟩ ⇒ ∣ϕ(x)⟩=eiγ(x) 2−n/2∑be−iθx(b)∣b⟩H^{\otimes n}\lvert0^n\rangle=2^{-n/2}\sum_b\lvert b\rangle\ \Rightarrow\ \lvert\phi(x)\rangle=e^{i\gamma(x)}\,2^{-n/2}\sum_be^{-i\theta_x(b)}\lvert b\rangle
    Part (ii) of the proposition and the diagonal-evolution theorem with t=1t=1.
  2. Step 2:
    ⟨ϕ(x′)∣ϕ(x)⟩=ei(γ(x)−γ(x′)) 2−n∑be−i(θx(b)−θx′(b))=ei(γ(x)−γ(x′)) Eb[Zb]\langle\phi(x')\vert\phi(x)\rangle=e^{i(\gamma(x)-\gamma(x'))}\,2^{-n}\sum_be^{-i(\theta_x(b)-\theta_{x'}(b))}=e^{i(\gamma(x)-\gamma(x'))}\,\mathbb E_b\big[Z_b\big]
    Orthonormality of the basis; Zb:=e−i(θx(b)−θx′(b))Z_b:=e^{-i(\theta_x(b)-\theta_{x'}(b))} is a bounded random variable when bb is uniform.
  3. Step 3:
    Pr⁡[∣ReZ‾−E ReZ∣≥ε]≤2e−mε2/2\Pr\big[\lvert\overline{\mathrm{Re}Z}-\mathbb E\,\mathrm{Re}Z\rvert\ge\varepsilon\big]\le2e^{-m\varepsilon^2/2}
    Hoeffding's inequality for mm i.i.d. samples with values in [−1,1][-1,1] (range 22): the bound is 2exp⁡(−2mε2/22)2\exp(-2m\varepsilon^2/2^2). The same holds for the imaginary part.
  4. Step 4:
    4e−mε2/2≤η  ⟺  m≥2ε2ln⁡4η ⇒ ∣z^−z∣≤2 ε w.p. ≥1−η4e^{-m\varepsilon^2/2}\le\eta\iff m\ge\tfrac2{\varepsilon^2}\ln\tfrac4\eta\ \Rightarrow\ \lvert\hat z-z\rvert\le\sqrt2\,\varepsilon\ \text{w.p.}\ \ge1-\eta
    Union bound over the two parts; both errors at most ε\varepsilon give a complex error at most 2ε\sqrt2\varepsilon.
  5. Step 5:
    ∣∣z^∣2−∣z∣2∣=∣∣z^∣−∣z∣∣ (∣z^∣+∣z∣)≤2 ε⋅2\big\lvert\lvert\hat z\rvert^2-\lvert z\rvert^2\big\rvert=\big\lvert\lvert\hat z\rvert-\lvert z\rvert\big\rvert\,\big(\lvert\hat z\rvert+\lvert z\rvert\big)\le\sqrt2\,\varepsilon\cdot2
    K=∣z∣2K=\lvert z\rvert^2 and the sample mean z^\hat z both lie in the unit disc; reverse triangle inequality.
  6. Step 6:
    cost per sample=O(∣S∣)=O(n2)\text{cost per sample}=O\big(\lvert\mathcal S\rvert\big)=O(n^2)
    Evaluating θx(b)\theta_x(b) sums one signed term per subset in S\mathcal S: nn fields and at most (n2)\binom n2 pairs.

∎

Quick check

Why does the circuit of the ZZ feature map implement eiγ(x)e−iHΦ(x)e^{i\gamma(x)}e^{-iH_\Phi(x)} exactly, with no Trotter error, although HΦ(x)H_\Phi(x) has n+(n2)n+\binom n2 terms?

Select one answer

The following TypeScript cell uses only the simulator library: it checks the ZZ gadget and the YY basis change against matrix exponentials computed by the spectral theorem, and evaluates the first-order Trotter error of the worked example against its bound.

TypeScriptrunnable
import { circuitUnitary, expmIHermitian, hamiltonianToMatrix, eigvalsh, matrix } from '@/lib/quantum-simulator';

const gate = (name, targets, params) => (params ? { kind: 'gate', gate: name, targets, params } : { kind: 'gate', gate: name, targets });
const unitaryOf = (n, ops) => circuitUnitary({ version: 1, numQubits: n, numClbits: 0, ops });

// (1) ZZ gadget: CNOT(0,1); RZ(1, 0.7); CNOT(0,1) equals exp(-i (0.7/2) Z x Z) exactly.
const theta = 0.7;
const gadget = unitaryOf(2, [gate('CNOT', [0, 1]), gate('RZ', [1], [theta]), gate('CNOT', [0, 1])]);
const ZZ = hamiltonianToMatrix([{ coeff: 1, ops: 'ZZ' }], 2);
console.log('ZZ gadget = exp(-0.35i ZZ): ' + (matrix.maxAbsDiff(gadget, expmIHermitian(ZZ, theta / 2)) < 1e-12));
const phases = [0, 1, 2, 3].map((k) => matrix.get(gadget, k, k)).map((z) => Math.atan2(z.im, z.re).toFixed(2));
console.log('diagonal phases: ' + phases.join(' '));

// (2) Y by basis change: time order RX(pi/2), RZ(theta), RX(-pi/2) gives exp(-i theta Y / 2).
const yRot = unitaryOf(1, [gate('RX', [0], [Math.PI / 2]), gate('RZ', [0], [theta]), gate('RX', [0], [-Math.PI / 2])]);
const Y = hamiltonianToMatrix([{ coeff: 1, ops: 'Y' }], 1);
console.log('RX(pi/2), RZ(0.7), RX(-pi/2) = exp(-0.35i Y): ' + (matrix.maxAbsDiff(yRot, expmIHermitian(Y, theta / 2)) < 1e-12));

// (3) First-order Trotter error for A = X x I, B = Z x I at t = 1 against the bound t^2 ||[A,B]|| / (2r).
const opNorm = (M) => Math.sqrt(Math.max(0, ...eigvalsh(matrix.mul(matrix.adjoint(M), M))));
const A = hamiltonianToMatrix([{ coeff: 1, ops: 'XI' }], 2);
const B = hamiltonianToMatrix([{ coeff: 1, ops: 'ZI' }], 2);
const t = 1;
const exact = expmIHermitian(matrix.add(A, B), t);
const commNorm = opNorm(matrix.sub(matrix.mul(A, B), matrix.mul(B, A)));
console.log('||[A,B]|| = ' + commNorm.toFixed(6));
for (const r of [1, 2, 4]) {
  const step = matrix.mul(expmIHermitian(A, t / r), expmIHermitian(B, t / r));
  let product = matrix.identity(4);
  for (let k = 0; k < r; k++) product = matrix.mul(step, product);
  const err = opNorm(matrix.sub(exact, product));
  const bound = ((t * t) / (2 * r)) * commNorm;
  console.log('r = ' + r + ': error ' + err.toFixed(6) + ' <= bound ' + bound.toFixed(6) + ': ' + (err <= bound));
}

Expected output

ZZ gadget = exp(-0.35i ZZ): true
diagonal phases: -0.35 0.35 0.35 -0.35
RX(pi/2), RZ(0.7), RX(-pi/2) = exp(-0.35i Y): true
||[A,B]|| = 2.000000
r = 1: error 0.799214 <= bound 1.000000: true
r = 2: error 0.362410 <= bound 0.500000: true
r = 4: error 0.176261 <= bound 0.250000: true

The NumPy cell repeats the gadget check and tabulates the first- and second-order errors of the Ising pair for r=1,2,4,8,16r=1,2,4,8,16: the first-order error halves and the second-order error quarters with each doubling of rr, always below the proven bounds.

Pythonrunnable
import numpy as np

I2 = np.eye(2)
X = np.array([[0, 1], [1, 0]], dtype=complex)
Z = np.diag([1.0, -1.0]).astype(complex)

def evolve(H, t):
    """exp(-iHt) for Hermitian H via the spectral theorem."""
    w, V = np.linalg.eigh(H)
    return V @ np.diag(np.exp(-1j * w * t)) @ V.conj().T

def comm(P, Q):
    return P @ Q - Q @ P

# ZZ gadget: CNOT (I x RZ(0.7)) CNOT = exp(-0.35i Z x Z)
CNOT = np.array([[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0]], dtype=complex)
RZ = np.diag(np.exp([-0.35j, 0.35j]))
gadget = CNOT @ np.kron(I2, RZ) @ CNOT
print(bool(np.allclose(gadget, evolve(np.kron(Z, Z), 0.35))), np.round(np.angle(np.diag(gadget)), 2))

# Transverse-field Ising pair: A = Z x Z, B = (X x I + I x X)/2
A = np.kron(Z, Z)
B = (np.kron(X, I2) + np.kron(I2, X)) / 2
c1 = np.linalg.norm(comm(A, B), 2)
cAAB = np.linalg.norm(comm(A, comm(A, B)), 2)
cBBA = np.linalg.norm(comm(B, comm(B, A)), 2)
print(f"||[A,B]|| = {c1:.6f}, ||[A,[A,B]]|| = {cAAB:.6f}, ||[B,[B,A]]|| = {cBBA:.6f}")
t = 1.0
exact = evolve(A + B, t)
for r in [1, 2, 4, 8, 16]:
    d = t / r
    first = np.linalg.matrix_power(evolve(A, d) @ evolve(B, d), r)
    second = np.linalg.matrix_power(evolve(A, d / 2) @ evolve(B, d) @ evolve(A, d / 2), r)
    e1 = np.linalg.norm(exact - first, 2)
    e2 = np.linalg.norm(exact - second, 2)
    b1 = t**2 / (2 * r) * c1
    b2 = t**3 / (12 * r**2) * cBBA + t**3 / (24 * r**2) * cAAB
    print(f"r={r:2d}  first {e1:.6f} <= {b1:.6f}  second {e2:.6f} <= {b2:.6f}")

Expected output

True [-0.35  0.35  0.35 -0.35]
||[A,B]|| = 2.000000, ||[A,[A,B]]|| = 4.000000, ||[B,[B,A]]|| = 4.000000
r= 1  first 0.799214 <= 1.000000  second 0.313666 <= 0.500000
r= 2  first 0.362410 <= 0.500000  second 0.071130 <= 0.125000
r= 4  first 0.176261 <= 0.250000  second 0.017273 <= 0.031250
r= 8  first 0.087513 <= 0.125000  second 0.004286 <= 0.007812
r=16  first 0.043679 <= 0.062500  second 0.001070 <= 0.001953

References

  1. V. Havlíček, A. D. Córcoles, K. Temme, A. W. Harrow, A. Kandala, J. M. Chow and J. M. Gambetta, Supervised learning with quantum-enhanced feature spaces, Nature 567, 209–212 (2019).doi:10.1038/s41586-019-0980-2
  2. H. F. Trotter, On the product of semi-groups of operators, Proceedings of the American Mathematical Society 10, 545–551 (1959).doi:10.1090/S0002-9939-1959-0108732-6
  3. M. Suzuki, Generalized Trotter's formula and systematic approximants of exponential operators and inner derivations with applications to many-body problems, Communications in Mathematical Physics 51, 183–190 (1976).doi:10.1007/BF01609348
  4. M. Suzuki, General theory of fractal path integrals with applications to many-body theories and statistical physics, Journal of Mathematical Physics 32, 400–407 (1991).doi:10.1063/1.529425
  5. S. Lloyd, Universal quantum simulators, Science 273, 1073–1078 (1996).doi:10.1126/science.273.5278.1073
  6. A. M. Childs, Y. Su, M. C. Tran, N. Wiebe and S. Zhu, Theory of Trotter error with commutator scaling, Physical Review X 11, 011020 (2021).doi:10.1103/PhysRevX.11.011020
  7. M. J. Bremner, R. Jozsa and D. J. Shepherd, Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy, Proceedings of the Royal Society A 467, 459–472 (2011).doi:10.1098/rspa.2010.0301
  8. M. J. Bremner, A. Montanaro and D. J. Shepherd, Average-case complexity versus approximate simulation of commuting quantum computations, Physical Review Letters 117, 080501 (2016).doi:10.1103/PhysRevLett.117.080501
  9. S. Lloyd, M. Mohseni and P. Rebentrost, Quantum principal component analysis, Nature Physics 10, 631–633 (2014).doi:10.1038/nphys3029
  10. M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th anniversary ed., Cambridge University Press (2010), §4.7 "Simulation of quantum systems".doi:10.1017/CBO9780511976667

Hands-on labs

  • Compile the ZZ evolution from CNOT and RZ

    1 step · auto-graded

    Implement the two-qubit evolution e−i0.72Z⊗Z=diag(e−0.35i,e0.35i,e0.35i,e−0.35i)e^{-i\frac{0.7}{2}Z\otimes Z}=\mathrm{diag}(e^{-0.35i},e^{0.35i},e^{0.35i},e^{-0.35i}) exactly, using at most three gates from {CNOT,RZ}\{\mathrm{CNOT},R_Z\}. This is the elementary building block of every diagonal (IQP-type) feature map, including the ZZ feature map of Havlíček et al.

    Open lab