QuantumCore

Lesson 36 · 80 min · core

Amplitude Encoding & State Preparation

Loading progress…

Amplitude encoding stores a vector x∈RNx\in\mathbb R^N in the amplitudes of n=⌈log⁡2N⌉n=\lceil\log_2N\rceil qubits, ∣x⟩=∥x∥−1∑ixi∣i⟩\lvert x\rangle=\lVert x\rVert^{-1}\sum_ix_i\lvert i\rangle. This lesson derives the binary-tree state-preparation circuit: a cascade of uniformly controlled RYR_Y rotations whose angles are ratios of partial norms, compiled into RYR_Y and CNOT gates with the Gray-code angle transform. It extends the construction to signed and complex amplitudes, counts 2n−12^n-1 rotations and 2n−22^n-2 CNOTs, proves by parameter counting that generic states need Ω(2n)\Omega(2^n) CNOTs, and explains why this O(N)O(N) loading cost can cancel claimed exponential speedups.

Prerequisites: Basis Encoding, Controlled Gates: CNOT, CZ, SWAP

Objectives and key results

  • Write the amplitude encoding ∣x⟩=∥x∥−1∑i=0N−1xi∣i⟩\lvert x\rangle=\lVert x\rVert^{-1}\sum_{i=0}^{N-1}x_i\lvert i\rangle of x∈RNx\in\mathbb R^N on n=⌈log⁡2N⌉n=\lceil\log_2N\rceil qubits, including zero padding and normalisation.

  • Derive the binary-tree angles θs,p=2arccos⁡N(p0)/N(p)\theta_{s,p}=2\arccos\sqrt{N(p0)/N(p)} and prove by induction that the cascade of uniformly controlled RYR_Y rotations prepares ∣x⟩\lvert x\rangle.

  • Compile a uniformly controlled rotation with kk controls into 2k2^k rotations and 2k2^k CNOTs with the Gray-code transform a=2−kMTθ\mathbf a=2^{-k}M^{\mathsf T}\boldsymbol\theta, and prove MTM=2kIM^{\mathsf T}M=2^kI.

  • Handle signed amplitudes with θ=2 atan2(xp1,xp0)\theta=2\,\mathrm{atan2}(x_{p1},x_{p0}) and complex amplitudes with a uniformly controlled RZR_Z cascade.

  • Count 2n−12^n-1 rotations and 2n−22^n-2 CNOTs, and prove the parameter-counting lower bound c≥(2n+1−2−3n)/6=Ω(2n)c\ge(2^{n+1}-2-3n)/6=\Omega(2^n) for generic states.

  • Explain why an O(N)O(N) state-preparation cost can erase an exponential quantum speedup.

definition · Amplitude encoding
x∈RN ⟼ ∣x⟩=1∥x∥∑i=0N−1xi∣i⟩∈C2n,n=⌈log⁡2N⌉x\in\mathbb R^N\ \longmapsto\ \lvert x\rangle=\frac1{\lVert x\rVert}\sum_{i=0}^{N-1}x_i\lvert i\rangle\in\mathbb C^{2^n},\qquad n=\lceil\log_2N\rceil
formula · Binary-tree angles
θs,p=2arccos⁡∑i∈L(s,p)xi2∑i∈T(s,p)xi2,θn−1,p=2 atan2(xp1,xp0) (signed leaves)\theta_{s,p}=2\arccos\sqrt{\frac{\sum_{i\in L(s,p)}x_i^2}{\sum_{i\in T(s,p)}x_i^2}},\qquad\theta_{n-1,p}=2\,\mathrm{atan2}(x_{p1},x_{p0})\ \text{(signed leaves)}
identity · Uniformly controlled R_Y with one control
CNOT (I⊗RY(b)) CNOT (I⊗RY(a))=∣0⟩⟨0∣⊗RY(θ0)+∣1⟩⟨1∣⊗RY(θ1),a=θ0+θ12, b=θ0−θ12\mathrm{CNOT}\,(I\otimes R_Y(b))\,\mathrm{CNOT}\,(I\otimes R_Y(a))=\lvert0\rangle\langle0\rvert\otimes R_Y(\theta_0)+\lvert1\rangle\langle1\rvert\otimes R_Y(\theta_1),\quad a=\tfrac{\theta_0+\theta_1}2,\ b=\tfrac{\theta_0-\theta_1}2
algorithm · Gray-code angle transform
a=2−kMTθ,Mcj=(−1)c⋅gj,gj=j⊕⌊j/2⌋,MTM=2kI\mathbf a=2^{-k}M^{\mathsf T}\boldsymbol\theta,\qquad M_{cj}=(-1)^{c\cdot g_j},\quad g_j=j\oplus\lfloor j/2\rfloor,\qquad M^{\mathsf T}M=2^kI
theorem · Cost and lower bound
#RY=2n−1,#CNOT=2n−2;generic states: c≥2n+1−2−3n6=Ω(2n)\#R_Y=2^n-1,\quad\#\mathrm{CNOT}=2^n-2;\qquad\text{generic states: }c\ge\frac{2^{n+1}-2-3n}{6}=\Omega(2^n)

Amplitude encoding of a real vector#

Basis encoding spends one qubit per bit of data and induces the kernel δxx′\delta_{xx'}. Amplitude encoding takes the opposite extreme: the NN components of a real vector become the NN amplitudes of a quantum state, so only ⌈log⁡2N⌉\lceil\log_2N\rceil qubits are needed. This exponential compression is the starting point of many proposed quantum linear-algebra and machine-learning algorithms. In this lesson we construct an explicit circuit that prepares the encoded state, prove that it is correct, count its gates, and prove that no circuit can do essentially better for generic data.

Definition

Amplitude encoding

Let x=(x0,…,xN−1)∈RNx=(x_0,\dots,x_{N-1})\in\mathbb R^N with N≥2N\ge2 and x≠0x\ne0, and let n=⌈log⁡2N⌉n=\lceil\log_2N\rceil. Extend xx by zeros to length 2n2^n, i.e. set xi:=0x_i:=0 for N≤i<2nN\le i<2^n. The amplitude encoding of xx is the nn-qubit state ∣x⟩:=1∥x∥∑i=02n−1xi∣i⟩,∥x∥=(∑i=0N−1xi2)1/2,\lvert x\rangle:=\frac{1}{\lVert x\rVert}\sum_{i=0}^{2^n-1}x_i\lvert i\rangle,\qquad\lVert x\rVert=\Big(\sum_{i=0}^{N-1}x_i^2\Big)^{1/2}, where ∣i⟩\lvert i\rangle is the computational basis state whose big-endian index is ii. A state-preparation circuit for xx is a unitary UxU_x with Ux∣0n⟩=∣x⟩U_x\lvert0^n\rangle=\lvert x\rangle, possibly up to a global phase.

Derivation

Register size, padding and normalisation

  1. Step 1:
    2n≥N  ⟺  n≥log⁡2N⟹nmin⁡=⌈log⁡2N⌉2^n\ge N\iff n\ge\log_2N\quad\Longrightarrow\quad n_{\min}=\lceil\log_2N\rceil
    An nn-qubit register has 2n2^n amplitudes; the smallest integer nn with 2n≥N2^n\ge N is the ceiling of log⁡2N\log_2N.
  2. Step 2:
    N=5: n=⌈log⁡25⌉=⌈2.3219…⌉=3,(x0,x1,x2,x3,x4)↦(x0,x1,x2,x3,x4,0,0,0)N=5:\ n=\lceil\log_25\rceil=\lceil2.3219\ldots\rceil=3,\qquad(x_0,x_1,x_2,x_3,x_4)\mapsto(x_0,x_1,x_2,x_3,x_4,0,0,0)
    Example: five features need three qubits and three padding zeros.
  3. Step 3:
    ∑i=02n−1xi2=∑i=0N−1xi2+∑i=N2n−102=∥x∥2\sum_{i=0}^{2^n-1}x_i^2=\sum_{i=0}^{N-1}x_i^2+\sum_{i=N}^{2^n-1}0^2=\lVert x\rVert^2
    Zero padding does not change the Euclidean norm.
  4. Step 4:
    ⟨x∣x⟩=1∥x∥2∑i,jxixj⟨i∣j⟩=1∥x∥2∑i,jxixjδij=1∥x∥2∑ixi2=1\langle x\vert x\rangle=\frac{1}{\lVert x\rVert^2}\sum_{i,j}x_ix_j\langle i\vert j\rangle=\frac{1}{\lVert x\rVert^2}\sum_{i,j}x_ix_j\delta_{ij}=\frac{1}{\lVert x\rVert^2}\sum_ix_i^2=1
    Expand the inner product bilinearly (xix_i are real) and use the orthonormality ⟨i∣j⟩=δij\langle i\vert j\rangle=\delta_{ij} of the computational basis.
  5. Step 5:
    ∣λx⟩=λ∣λ∣∣x⟩(λ∈R∖{0})\lvert\lambda x\rangle=\frac{\lambda}{\lvert\lambda\rvert}\lvert x\rangle\quad(\lambda\in\mathbb R\setminus\{0\})
    ∥λx∥=∣λ∣∥x∥\lVert\lambda x\rVert=\lvert\lambda\rvert\lVert x\rVert, so rescaling the data changes the state at most by the global sign sgn⁡λ\operatorname{sgn}\lambda: the norm of xx is not stored and must be supplied separately if it matters.
  6. Step 6:
    P(i)=∣⟨i∣x⟩∣2=xi2∥x∥2P(i)=\lvert\langle i\vert x\rangle\rvert^2=\frac{x_i^2}{\lVert x\rVert^2}
    Born rule: measuring in the computational basis returns index ii with probability xi2/∥x∥2x_i^2/\lVert x\rVert^2, so the data cannot be read out by a single measurement.

Result

∣x⟩=1∥x∥∑i=02n−1xi∣i⟩,⟨x∣x⟩=1,n=⌈log⁡2N⌉\boxed{\lvert x\rangle=\frac{1}{\lVert x\rVert}\sum_{i=0}^{2^n-1}x_i\lvert i\rangle,\qquad\langle x\vert x\rangle=1,\qquad n=\lceil\log_2N\rceil}
Proposition

Fidelity kernel of amplitude encoding

For nonzero x,x′∈RNx,x'\in\mathbb R^N, k(x,x′):=∣⟨x∣x′⟩∣2=(x⋅x′)2∥x∥2∥x′∥2=cos⁡2∠(x,x′).k(x,x'):=\lvert\langle x\vert x'\rangle\rvert^2=\frac{(x\cdot x')^2}{\lVert x\rVert^2\lVert x'\rVert^2}=\cos^2\angle(x,x'). The kernel is a smooth function of the data and equals 11 if and only if x′x' is a nonzero multiple of xx.

Proof (5 steps)
  1. Step 1:
    ⟨x∣x′⟩=1∥x∥∥x′∥∑i,jxixj′⟨i∣j⟩=1∥x∥∥x′∥∑ixixi′=x⋅x′∥x∥∥x′∥\langle x\vert x'\rangle=\frac{1}{\lVert x\rVert\lVert x'\rVert}\sum_{i,j}x_ix'_j\langle i\vert j\rangle=\frac{1}{\lVert x\rVert\lVert x'\rVert}\sum_ix_ix'_i=\frac{x\cdot x'}{\lVert x\rVert\lVert x'\rVert}
    Bilinear expansion with orthonormal basis states, exactly as in the normalisation computation.
  2. Step 2:
    x⋅x′∥x∥∥x′∥=cos⁡∠(x,x′)∈[−1,1]\frac{x\cdot x'}{\lVert x\rVert\lVert x'\rVert}=\cos\angle(x,x')\in[-1,1]
    Definition of the angle between two nonzero vectors of RN\mathbb R^N; the bound is the Cauchy–Schwarz inequality.
  3. Step 3:
    k(x,x′)=cos⁡2∠(x,x′)k(x,x')=\cos^2\angle(x,x')
    Square the modulus of the real number above.
  4. Step 4:
    k(x,x′)=1  ⟺  ∣x⋅x′∣=∥x∥∥x′∥  ⟺  x′=λx, λ≠0k(x,x')=1\iff\lvert x\cdot x'\rvert=\lVert x\rVert\lVert x'\rVert\iff x'=\lambda x,\ \lambda\ne0
    Equality in Cauchy–Schwarz holds exactly for linearly dependent vectors.
  5. Step 5:
    k(x,x′)=0  ⟺  x⊥x′k(x,x')=0\iff x\perp x'
    The kernel vanishes only for orthogonal data vectors, in contrast to basis encoding, where every pair of distinct inputs has kernel 00.

∎

Quick check

How many qubits does the amplitude encoding of a vector x∈R1000x\in\mathbb R^{1000} require?

tolerance ±1e-9

The binary-tree state-preparation circuit#

The construction prepares ∣x⟩\lvert x\rangle one qubit at a time, from the most significant to the least significant. Qubit 00 decides between the first and the second half of the index range, so it must receive the share of the norm that lies in each half. Qubit 11 then splits each half into quarters, with a rotation that depends on the value of qubit 00, and so on. The bookkeeping is done with prefix sets.

Definition

Prefix sets and partial norms

Fix nn and a padded vector x∈R2nx\in\mathbb R^{2^n}. For 0≤s≤n0\le s\le n and a bit string q∈{0,1}sq\in\{0,1\}^s (a prefix of length ss; the empty prefix is written ∅\varnothing) let T(q)T(q) be the set of indices i∈{0,…,2n−1}i\in\{0,\dots,2^n-1\} whose first ss bits i0i1⋯is−1i_0i_1\cdots i_{s-1} equal qq. For a prefix pp of length s<ns<n we write T(s,p):=T(p)T(s,p):=T(p) and L(s,p):=T(p0)L(s,p):=T(p0), the indices whose bit ss is 00. The partial norm of qq is N(q):=∑i∈T(q)xi2N(q):=\sum_{i\in T(q)}x_i^2. Since T(p)T(p) is the disjoint union of T(p0)T(p0) and T(p1)T(p1), N(p)=N(p0)+N(p1),N(∅)=∥x∥2,N(i0⋯in−1)=xi2.N(p)=N(p0)+N(p1),\qquad N(\varnothing)=\lVert x\rVert^2,\qquad N(i_0\cdots i_{n-1})=x_i^2.

Definition

Uniformly controlled rotation

Let G∈{RY,RZ}G\in\{R_Y,R_Z\}, let k≥0k\ge0, and let θ=(θc)c=02k−1\boldsymbol\theta=(\theta_c)_{c=0}^{2^k-1} be real angles. The uniformly controlled rotation with kk control qubits and one target qubit is UCRG(θ):=∑c=02k−1∣c⟩⟨c∣⊗G(θc),\mathrm{UCR}_G(\boldsymbol\theta):=\sum_{c=0}^{2^k-1}\lvert c\rangle\langle c\rvert\otimes G(\theta_c), where ∣c⟩\lvert c\rangle runs over the computational basis of the controls (first control = most significant bit of cc). It applies G(θc)G(\theta_c) to the target whenever the controls are in state ∣c⟩\lvert c\rangle; for k=0k=0 it is the single rotation G(θ0)G(\theta_0). It is unitary because it is block diagonal with unitary blocks.

Definition

Binary-tree angles and circuit

For a nonzero x∈R2nx\in\mathbb R^{2^n} with non-negative entries, level s∈{0,…,n−1}s\in\{0,\dots,n-1\} and prefix p∈{0,1}sp\in\{0,1\}^s define θs,p:=2arccos⁡∑i∈L(s,p)xi2∑i∈T(s,p)xi2=2arccos⁡N(p0)N(p)∈[0,π],\theta_{s,p}:=2\arccos\sqrt{\frac{\sum_{i\in L(s,p)}x_i^2}{\sum_{i\in T(s,p)}x_i^2}}=2\arccos\sqrt{\frac{N(p0)}{N(p)}}\in[0,\pi], and θs,p:=0\theta_{s,p}:=0 when N(p)=0N(p)=0. The tree circuit is Vx:=Wn−1⋯W1W0V_x:=W_{n-1}\cdots W_1W_0, where WsW_s is the uniformly controlled RYR_Y with controls 0,…,s−10,\dots,s-1, target ss and angles (θs,p)p(\theta_{s,p})_p, acting as the identity on qubits s+1,…,n−1s+1,\dots,n-1.

Theorem

The binary-tree cascade prepares the amplitude encoding

Let x∈R2nx\in\mathbb R^{2^n} be nonzero with non-negative entries, and let ∣ψs⟩:=Ws−1⋯W0∣0n⟩\lvert\psi_s\rangle:=W_{s-1}\cdots W_0\lvert0^n\rangle. Then for every s∈{0,…,n}s\in\{0,\dots,n\} ∣ψs⟩=∑q∈{0,1}sN(q)∥x∥2  ∣q⟩⊗∣0n−s⟩,\lvert\psi_s\rangle=\sum_{q\in\{0,1\}^s}\sqrt{\frac{N(q)}{\lVert x\rVert^2}}\;\lvert q\rangle\otimes\lvert0^{n-s}\rangle, and in particular Vx∣0n⟩=∣ψn⟩=∑ixi∣i⟩/∥x∥=∣x⟩V_x\lvert0^n\rangle=\lvert\psi_n\rangle=\sum_ix_i\lvert i\rangle/\lVert x\rVert=\lvert x\rangle.

Proof (8 steps)
  1. Step 1:
    s=0:∣ψ0⟩=∣0n⟩=N(∅)∥x∥2 ∣∅⟩⊗∣0n⟩s=0:\quad\lvert\psi_0\rangle=\lvert0^n\rangle=\sqrt{\frac{N(\varnothing)}{\lVert x\rVert^2}}\,\lvert\varnothing\rangle\otimes\lvert0^n\rangle
    Base case: no gate has acted, the only prefix of length 00 is ∅\varnothing, and N(∅)=∥x∥2N(\varnothing)=\lVert x\rVert^2.
  2. Step 2:
    Ws(∣p⟩⊗∣0⟩⊗∣0n−s−1⟩)=∣p⟩⊗RY(θs,p)∣0⟩⊗∣0n−s−1⟩W_s\big(\lvert p\rangle\otimes\lvert0\rangle\otimes\lvert0^{n-s-1}\rangle\big)=\lvert p\rangle\otimes R_Y(\theta_{s,p})\lvert0\rangle\otimes\lvert0^{n-s-1}\rangle
    Induction step, assuming the claim for s<ns<n: by definition of the uniformly controlled rotation, WsW_s applies RY(θs,p)R_Y(\theta_{s,p}) to qubit ss when qubits 0,…,s−10,\dots,s-1 are in ∣p⟩\lvert p\rangle.
  3. Step 3:
    RY(θ)∣0⟩=(cos⁡θ2−sin⁡θ2sin⁡θ2cos⁡θ2)(10)=cos⁡θ2∣0⟩+sin⁡θ2∣1⟩R_Y(\theta)\lvert0\rangle=\begin{pmatrix}\cos\frac\theta2&-\sin\frac\theta2\\\sin\frac\theta2&\cos\frac\theta2\end{pmatrix}\begin{pmatrix}1\\0\end{pmatrix}=\cos\tfrac\theta2\lvert0\rangle+\sin\tfrac\theta2\lvert1\rangle
    First column of the RYR_Y matrix.
  4. Step 4:
    N(p)>0:cos⁡θs,p2=N(p0)N(p),sin⁡θs,p2=1−N(p0)N(p)=N(p1)N(p)N(p)>0:\quad\cos\tfrac{\theta_{s,p}}2=\sqrt{\frac{N(p0)}{N(p)}},\qquad\sin\tfrac{\theta_{s,p}}2=\sqrt{1-\frac{N(p0)}{N(p)}}=\sqrt{\frac{N(p1)}{N(p)}}
    θs,p/2=arccos⁡(⋅)∈[0,π/2]\theta_{s,p}/2=\arccos(\cdot)\in[0,\pi/2], where the sine is non-negative, and N(p)−N(p0)=N(p1)N(p)-N(p0)=N(p1).
  5. Step 5:
    N(p)∥x∥2⋅N(pb)N(p)=N(pb)∥x∥2(b∈{0,1})\sqrt{\frac{N(p)}{\lVert x\rVert^2}}\cdot\sqrt{\frac{N(pb)}{N(p)}}=\sqrt{\frac{N(pb)}{\lVert x\rVert^2}}\qquad(b\in\{0,1\})
    Multiply the amplitude of ∣p⟩\lvert p\rangle from the hypothesis by the amplitude of ∣b⟩\lvert b\rangle produced by the rotation; N(p)N(p) cancels.
  6. Step 6:
    N(p)=0:N(p0)=N(p1)=0,0⋅RY(0)∣0⟩=0=N(p0)∣0⟩+N(p1)∣1⟩N(p)=0:\quad N(p0)=N(p1)=0,\qquad0\cdot R_Y(0)\lvert0\rangle=0=\sqrt{N(p0)}\lvert0\rangle+\sqrt{N(p1)}\lvert1\rangle
    A prefix with zero partial norm has zero amplitude, and both children have zero partial norm because N(p)=N(p0)+N(p1)N(p)=N(p0)+N(p1) with non-negative terms; the convention θ=0\theta=0 is therefore harmless.
  7. Step 7:
    ∣ψs+1⟩=Ws∣ψs⟩=∑p∈{0,1}s∑b∈{0,1}N(pb)∥x∥2 ∣pb⟩⊗∣0n−s−1⟩=∑q∈{0,1}s+1N(q)∥x∥2 ∣q⟩⊗∣0n−s−1⟩\lvert\psi_{s+1}\rangle=W_s\lvert\psi_s\rangle=\sum_{p\in\{0,1\}^s}\sum_{b\in\{0,1\}}\sqrt{\frac{N(pb)}{\lVert x\rVert^2}}\,\lvert pb\rangle\otimes\lvert0^{n-s-1}\rangle=\sum_{q\in\{0,1\}^{s+1}}\sqrt{\frac{N(q)}{\lVert x\rVert^2}}\,\lvert q\rangle\otimes\lvert0^{n-s-1}\rangle
    Linearity of WsW_s applied to the hypothesis; every prefix of length s+1s+1 is uniquely of the form q=pbq=pb. This completes the induction.
  8. Step 8:
    ∣ψn⟩=∑iN(i0⋯in−1)∥x∥2∣i⟩=∑i∣xi∣∥x∥∣i⟩=∑ixi∥x∥∣i⟩=∣x⟩\lvert\psi_n\rangle=\sum_{i}\sqrt{\frac{N(i_0\cdots i_{n-1})}{\lVert x\rVert^2}}\lvert i\rangle=\sum_i\frac{\lvert x_i\rvert}{\lVert x\rVert}\lvert i\rangle=\sum_i\frac{x_i}{\lVert x\rVert}\lvert i\rangle=\lvert x\rangle
    At s=ns=n the prefixes are complete indices with N(i)=xi2N(i)=x_i^2, and xi2=xi\sqrt{x_i^2}=x_i because the entries are non-negative.

∎

Compiling uniformly controlled rotations#

Lemma

Conjugation of rotations by X

For all real α,β\alpha,\beta: RY(α)RY(β)=RY(α+β)R_Y(\alpha)R_Y(\beta)=R_Y(\alpha+\beta), XRY(β)X=RY(−β)XR_Y(\beta)X=R_Y(-\beta), and likewise RZ(α)RZ(β)=RZ(α+β)R_Z(\alpha)R_Z(\beta)=R_Z(\alpha+\beta), XRZ(β)X=RZ(−β)XR_Z(\beta)X=R_Z(-\beta).

Proof (6 steps)
  1. Step 1:
    RY(α)RY(β)=e−iαY/2e−iβY/2=e−i(α+β)Y/2=RY(α+β)R_Y(\alpha)R_Y(\beta)=e^{-i\alpha Y/2}e^{-i\beta Y/2}=e^{-i(\alpha+\beta)Y/2}=R_Y(\alpha+\beta)
    αY/2\alpha Y/2 and βY/2\beta Y/2 commute, and eAeB=eA+Be^Ae^B=e^{A+B} for commuting matrices. The same argument with ZZ gives the RZR_Z identity.
  2. Step 2:
    XY=(0110)(0−ii0)=(i00−i)=iZ,XYX=iZX=i(01−10)=(0i−i0)=−YXY=\begin{pmatrix}0&1\\1&0\end{pmatrix}\begin{pmatrix}0&-i\\i&0\end{pmatrix}=\begin{pmatrix}i&0\\0&-i\end{pmatrix}=iZ,\qquad XYX=iZX=i\begin{pmatrix}0&1\\-1&0\end{pmatrix}=\begin{pmatrix}0&i\\-i&0\end{pmatrix}=-Y
    Direct matrix multiplication.
  3. Step 3:
    XZX=(0110)(100−1)(0110)=(−1001)=−ZXZX=\begin{pmatrix}0&1\\1&0\end{pmatrix}\begin{pmatrix}1&0\\0&-1\end{pmatrix}\begin{pmatrix}0&1\\1&0\end{pmatrix}=\begin{pmatrix}-1&0\\0&1\end{pmatrix}=-Z
    Direct matrix multiplication.
  4. Step 4:
    RY(β)=cos⁡β2 I−isin⁡β2 Y ⇒ XRY(β)X=cos⁡β2 I+isin⁡β2 Y=RY(−β)R_Y(\beta)=\cos\tfrac\beta2\,I-i\sin\tfrac\beta2\,Y\ \Rightarrow\ XR_Y(\beta)X=\cos\tfrac\beta2\,I+i\sin\tfrac\beta2\,Y=R_Y(-\beta)
    Since Y2=IY^2=I, the exponential series gives e−iβY/2=cos⁡β2I−isin⁡β2Ye^{-i\beta Y/2}=\cos\frac\beta2I-i\sin\frac\beta2Y; conjugation by XX fixes II (X2=IX^2=I) and flips YY; cosine is even and sine is odd.
  5. Step 5:
    XRZ(β)X=cos⁡β2 I+isin⁡β2 Z=RZ(−β)XR_Z(\beta)X=\cos\tfrac\beta2\,I+i\sin\tfrac\beta2\,Z=R_Z(-\beta)
    Same computation with XZX=−ZXZX=-Z.
  6. Step 6:
    X(cos⁡β2−sin⁡β2sin⁡β2cos⁡β2)X=(cos⁡β2sin⁡β2−sin⁡β2cos⁡β2)=RY(−β)X\begin{pmatrix}\cos\frac\beta2&-\sin\frac\beta2\\\sin\frac\beta2&\cos\frac\beta2\end{pmatrix}X=\begin{pmatrix}\cos\frac\beta2&\sin\frac\beta2\\-\sin\frac\beta2&\cos\frac\beta2\end{pmatrix}=R_Y(-\beta)
    Matrix check of the RYR_Y case: conjugation by XX swaps both the rows and the columns.

∎

Theorem

Uniformly controlled R_Y with one control

Let θ0,θ1∈R\theta_0,\theta_1\in\mathbb R, a=θ0+θ12a=\frac{\theta_0+\theta_1}2 and b=θ0−θ12b=\frac{\theta_0-\theta_1}2. On a control qubit cc and a target qubit tt, the circuit RY(a)R_Y(a) on tt, then CNOTc→t\mathrm{CNOT}_{c\to t}, then RY(b)R_Y(b) on tt, then CNOTc→t\mathrm{CNOT}_{c\to t} implements UCRY(θ0,θ1)=∣0⟩⟨0∣⊗RY(θ0)+∣1⟩⟨1∣⊗RY(θ1).\mathrm{UCR}_Y(\theta_0,\theta_1)=\lvert0\rangle\langle0\rvert\otimes R_Y(\theta_0)+\lvert1\rangle\langle1\rvert\otimes R_Y(\theta_1). The same holds with RZR_Z in place of RYR_Y.

Proof (6 steps)
  1. Step 1:
    U=CNOT (I⊗RY(b)) CNOT (I⊗RY(a)),CNOT=∣0⟩⟨0∣⊗I+∣1⟩⟨1∣⊗XU=\mathrm{CNOT}\,(I\otimes R_Y(b))\,\mathrm{CNOT}\,(I\otimes R_Y(a)),\qquad\mathrm{CNOT}=\lvert0\rangle\langle0\rvert\otimes I+\lvert1\rangle\langle1\rvert\otimes X
    The operator of a circuit is the product of its gates in reverse order; CNOT is written in block form with respect to the control.
  2. Step 2:
    CNOT (I⊗RY(b)) CNOT=∑u,v∈{0,1}∣u⟩⟨u∣v⟩⟨v∣⊗XuRY(b)Xv=∑u∈{0,1}∣u⟩⟨u∣⊗XuRY(b)Xu\mathrm{CNOT}\,(I\otimes R_Y(b))\,\mathrm{CNOT}=\sum_{u,v\in\{0,1\}}\lvert u\rangle\langle u\vert v\rangle\langle v\rvert\otimes X^uR_Y(b)X^v=\sum_{u\in\{0,1\}}\lvert u\rangle\langle u\rvert\otimes X^uR_Y(b)X^u
    Mixed-product rule; the cross terms vanish because ⟨u∣v⟩=δuv\langle u\vert v\rangle=\delta_{uv}.
  3. Step 3:
    U=∣0⟩⟨0∣⊗RY(b)RY(a)+∣1⟩⟨1∣⊗XRY(b)XRY(a)U=\lvert0\rangle\langle0\rvert\otimes R_Y(b)R_Y(a)+\lvert1\rangle\langle1\rvert\otimes XR_Y(b)XR_Y(a)
    Multiply on the right by I⊗RY(a)=∑u∣u⟩⟨u∣⊗RY(a)I\otimes R_Y(a)=\sum_u\lvert u\rangle\langle u\rvert\otimes R_Y(a).
  4. Step 4:
    RY(b)RY(a)=RY(a+b)=RY(θ0)R_Y(b)R_Y(a)=R_Y(a+b)=R_Y(\theta_0)
    Additivity of RYR_Y angles (lemma) and a+b=θ0a+b=\theta_0.
  5. Step 5:
    XRY(b)XRY(a)=RY(−b)RY(a)=RY(a−b)=RY(θ1)XR_Y(b)XR_Y(a)=R_Y(-b)R_Y(a)=R_Y(a-b)=R_Y(\theta_1)
    XRY(b)X=RY(−b)XR_Y(b)X=R_Y(-b) (lemma), additivity, and a−b=θ1a-b=\theta_1.
  6. Step 6:
    U=∣0⟩⟨0∣⊗RY(θ0)+∣1⟩⟨1∣⊗RY(θ1)=UCRY(θ0,θ1)U=\lvert0\rangle\langle0\rvert\otimes R_Y(\theta_0)+\lvert1\rangle\langle1\rvert\otimes R_Y(\theta_1)=\mathrm{UCR}_Y(\theta_0,\theta_1)
    Substitute the two blocks. The RZR_Z version is identical because the lemma holds for RZR_Z as well.

∎

Definition

Gray code and the Walsh–Gray matrix

The binary-reflected Gray code of j∈{0,…,2k−1}j\in\{0,\dots,2^k-1\} is gj:=j⊕⌊j/2⌋g_j:=j\oplus\lfloor j/2\rfloor (bitwise XOR). For k=2k=2: (g0,g1,g2,g3)=(00,01,11,10)(g_0,g_1,g_2,g_3)=(00,01,11,10). Consecutive codes differ in exactly one bit, including the cyclic pair g2k−1=10⋯0g_{2^k-1}=10\cdots0 and g0=0⋯0g_0=0\cdots0, and j↦gjj\mapsto g_j is a bijection of {0,…,2k−1}\{0,\dots,2^k-1\}. For bit strings c,gc,g write c⋅g:=∑mcmgm mod 2c\cdot g:=\sum_mc_mg_m\bmod2. The Walsh–Gray matrix is the 2k×2k2^k\times2^k matrix Mcj:=(−1)c⋅gj,c,j∈{0,…,2k−1},M_{cj}:=(-1)^{c\cdot g_j},\qquad c,j\in\{0,\dots,2^k-1\}, with rows indexed by control states cc (in binary) and columns by rotation slots jj.

Lemma

Orthogonality of the Walsh–Gray matrix

MTM=2kIM^{\mathsf T}M=2^kI. Consequently MM is invertible with M−1=2−kMTM^{-1}=2^{-k}M^{\mathsf T}, and the linear system Ma=θM\mathbf a=\boldsymbol\theta has the unique solution a=2−kMTθ\mathbf a=2^{-k}M^{\mathsf T}\boldsymbol\theta.

Proof (6 steps)
  1. Step 1:
    (MTM)jl=∑c=02k−1McjMcl=∑c(−1)c⋅gj+c⋅gl=∑c(−1)c⋅(gj⊕gl)(M^{\mathsf T}M)_{jl}=\sum_{c=0}^{2^k-1}M_{cj}M_{cl}=\sum_c(-1)^{c\cdot g_j+c\cdot g_l}=\sum_c(-1)^{c\cdot(g_j\oplus g_l)}
    Definition of the matrix product; the dot product modulo 22 is linear in its second argument over GF(2)\mathrm{GF}(2).
  2. Step 2:
    ∑c∈{0,1}k(−1)c⋅y=∏m=0k−1∑cm∈{0,1}(−1)cmym=∏m=0k−1(1+(−1)ym)\sum_{c\in\{0,1\}^k}(-1)^{c\cdot y}=\prod_{m=0}^{k-1}\sum_{c_m\in\{0,1\}}(-1)^{c_my_m}=\prod_{m=0}^{k-1}\big(1+(-1)^{y_m}\big)
    The sum over cc factorises over the bits of cc because (−1)c⋅y=∏m(−1)cmym(-1)^{c\cdot y}=\prod_m(-1)^{c_my_m}.
  3. Step 3:
    ∏m(1+(−1)ym)={2k,y=0⋯00,otherwise\prod_{m}\big(1+(-1)^{y_m}\big)=\begin{cases}2^k,&y=0\cdots0\\0,&\text{otherwise}\end{cases}
    Each factor is 22 if ym=0y_m=0 and 00 if ym=1y_m=1.
  4. Step 4:
    gj⊕gl=0  ⟺  gj=gl  ⟺  j=lg_j\oplus g_l=0\iff g_j=g_l\iff j=l
    The Gray code is a bijection.
  5. Step 5:
    (MTM)jl=2kδjl ⇒ MTM=2kI(M^{\mathsf T}M)_{jl}=2^k\delta_{jl}\ \Rightarrow\ M^{\mathsf T}M=2^kI
    Combine the previous steps with y=gj⊕gly=g_j\oplus g_l.
  6. Step 6:
    M(2−kMT)=I ⇒ M−1=2−kMT,Ma=θ  ⟺  a=2−kMTθM\big(2^{-k}M^{\mathsf T}\big)=I\ \Rightarrow\ M^{-1}=2^{-k}M^{\mathsf T},\qquad M\mathbf a=\boldsymbol\theta\iff\mathbf a=2^{-k}M^{\mathsf T}\boldsymbol\theta
    For square matrices a left inverse 2−kMT2^{-k}M^{\mathsf T} is also a right inverse; multiply Ma=θM\mathbf a=\boldsymbol\theta by M−1M^{-1}.

∎

Theorem

Gray-code compilation of a uniformly controlled rotation

Let G∈{RY,RZ}G\in\{R_Y,R_Z\}, k≥1k\ge1, and target angles θ∈R2k\boldsymbol\theta\in\mathbb R^{2^k}. Put a=2−kMTθ\mathbf a=2^{-k}M^{\mathsf T}\boldsymbol\theta. For j=0,…,2k−1j=0,\dots,2^k-1 apply G(aj)G(a_j) to the target, followed by a CNOT onto the target whose control is the control qubit of the unique bit in which gjg_j and g(j+1) mod 2kg_{(j+1)\bmod2^k} differ. This circuit of 2k2^k rotations and 2k2^k CNOTs equals UCRG(θ)\mathrm{UCR}_G(\boldsymbol\theta).

Proof (9 steps)
  1. Step 1:
    dj:=gj⊕g(j+1) mod 2k,CNOTj acts on ∣c⟩⊗∣ϕ⟩ as ∣c⟩⊗Xc⋅dj∣ϕ⟩d_j:=g_j\oplus g_{(j+1)\bmod2^k},\qquad\text{CNOT}_j\ \text{acts on }\lvert c\rangle\otimes\lvert\phi\rangle\ \text{as}\ \lvert c\rangle\otimes X^{c\cdot d_j}\lvert\phi\rangle
    djd_j has a single bit set; CNOT number jj is controlled by the qubit carrying that bit of cc, so it flips the target exactly when c⋅dj=1c\cdot d_j=1.
  2. Step 2:
    circuit=∑c∣c⟩⟨c∣⊗Vc,Vc=Xc⋅d2k−1G(a2k−1)⋯Xc⋅d1G(a1) Xc⋅d0G(a0)\text{circuit}=\sum_{c}\lvert c\rangle\langle c\rvert\otimes V_c,\qquad V_c=X^{c\cdot d_{2^k-1}}G(a_{2^k-1})\cdots X^{c\cdot d_1}G(a_1)\,X^{c\cdot d_0}G(a_0)
    No gate changes the control qubits, so the circuit is block diagonal in the control basis; the target block is the ordered product of its gates.
  3. Step 3:
    Pj:=c⋅gj (mod 2),c⋅dj=Pj⊕Pj+1,P0=P2k=0P_j:=c\cdot g_j\ (\mathrm{mod}\ 2),\qquad c\cdot d_j=P_j\oplus P_{j+1},\qquad P_0=P_{2^k}=0
    Linearity of the dot product modulo 22; g0=0g_0=0, and we set P2k:=c⋅g0=0P_{2^k}:=c\cdot g_0=0 for the cyclic last step.
  4. Step 4:
    Xc⋅dj=XPj+1XPjX^{c\cdot d_j}=X^{P_{j+1}}X^{P_j}
    X2=IX^2=I, so Xu⊕v=XuXvX^{u\oplus v}=X^uX^v for bits u,vu,v.
  5. Step 5:
    Vc=XP2k[XP2k−1G(a2k−1)XP2k−1]⋯[XP1G(a1)XP1][XP0G(a0)XP0]V_c=X^{P_{2^k}}\big[X^{P_{2^k-1}}G(a_{2^k-1})X^{P_{2^k-1}}\big]\cdots\big[X^{P_1}G(a_1)X^{P_1}\big]\big[X^{P_0}G(a_0)X^{P_0}\big]
    Substitute Xc⋅dj=XPj+1XPjX^{c\cdot d_j}=X^{P_{j+1}}X^{P_j}, which stands between G(aj)G(a_j) and G(aj+1)G(a_{j+1}): the factor XPjX^{P_j} joins the bracket of G(aj)G(a_j) and XPj+1X^{P_{j+1}} joins the bracket of G(aj+1)G(a_{j+1}). The two outermost factors are XP2k=IX^{P_{2^k}}=I and XP0=IX^{P_0}=I.
  6. Step 6:
    XPG(a)XP=G((−1)Pa) ⇒ Vc=G((−1)P2k−1a2k−1)⋯G((−1)P0a0)X^{P}G(a)X^{P}=G\big((-1)^{P}a\big)\ \Rightarrow\ V_c=G\big((-1)^{P_{2^k-1}}a_{2^k-1}\big)\cdots G\big((-1)^{P_0}a_0\big)
    Conjugation lemma for P=1P=1; trivial for P=0P=0.
  7. Step 7:
    Vc=G(∑j=02k−1(−1)c⋅gjaj)=G((Ma)c)V_c=G\Big(\sum_{j=0}^{2^k-1}(-1)^{c\cdot g_j}a_j\Big)=G\big((M\mathbf a)_c\big)
    Additivity of rotation angles about a fixed axis and the definition Mcj=(−1)c⋅gjM_{cj}=(-1)^{c\cdot g_j}.
  8. Step 8:
    Ma=M 2−kMTθ=θ ⇒ Vc=G(θc)  ∀cM\mathbf a=M\,2^{-k}M^{\mathsf T}\boldsymbol\theta=\boldsymbol\theta\ \Rightarrow\ V_c=G(\theta_c)\ \ \forall c
    Orthogonality lemma: MMT=2kIMM^{\mathsf T}=2^kI as well, since M−1=2−kMTM^{-1}=2^{-k}M^{\mathsf T}.
  9. Step 9:
    circuit=∑c∣c⟩⟨c∣⊗G(θc)=UCRG(θ),2k rotations, 2k CNOTs\text{circuit}=\sum_c\lvert c\rangle\langle c\rvert\otimes G(\theta_c)=\mathrm{UCR}_G(\boldsymbol\theta),\qquad2^k\ \text{rotations},\ 2^k\ \text{CNOTs}
    Insert into the block form. Each slot contributes one rotation and one CNOT. For k=1k=1 this reproduces a0=θ0+θ12a_0=\frac{\theta_0+\theta_1}2, a1=θ0−θ12a_1=\frac{\theta_0-\theta_1}2.

∎

Derivation

The case k = 2: four rotations and four CNOTs

  1. Step 1:
    (g0,g1,g2,g3)=(00,01,11,10),(d0,d1,d2,d3)=(01,10,01,10)(g_0,g_1,g_2,g_3)=(00,01,11,10),\qquad(d_0,d_1,d_2,d_3)=(01,10,01,10)
    Gray codes and their cyclic differences; dj=01d_j=01 selects the second control c1c_1, dj=10d_j=10 the first control c0c_0.
  2. Step 2:
    M=(11111−1−1111−1−11−11−1)(rows c=00,01,10,11)M=\begin{pmatrix}1&1&1&1\\1&-1&-1&1\\1&1&-1&-1\\1&-1&1&-1\end{pmatrix}\qquad(\text{rows }c=00,01,10,11)
    Entry (c,j)(c,j) is (−1)c⋅gj(-1)^{c\cdot g_j}; for example c=01c=01 meets g1=01g_1=01 and g2=11g_2=11 in one bit, giving the signs (+,−,−,+)(+,-,-,+).
  3. Step 3:
    MTM=(4000040000400004)=4IM^{\mathsf T}M=\begin{pmatrix}4&0&0&0\\0&4&0&0\\0&0&4&0\\0&0&0&4\end{pmatrix}=4I
    Distinct columns of MM are orthogonal and each has squared norm 44, as the lemma predicts.
  4. Step 4:
    a0=14(θ00+θ01+θ10+θ11),a1=14(θ00−θ01+θ10−θ11),a2=14(θ00−θ01−θ10+θ11),a3=14(θ00+θ01−θ10−θ11)\begin{aligned}a_0&=\tfrac14(\theta_{00}+\theta_{01}+\theta_{10}+\theta_{11}),&a_1&=\tfrac14(\theta_{00}-\theta_{01}+\theta_{10}-\theta_{11}),\\a_2&=\tfrac14(\theta_{00}-\theta_{01}-\theta_{10}+\theta_{11}),&a_3&=\tfrac14(\theta_{00}+\theta_{01}-\theta_{10}-\theta_{11})\end{aligned}
    The rows of 14MT\tfrac14M^{\mathsf T} are the columns of MM divided by 44.
  5. Step 5:
    RY(a0)→CNOTc1→t→RY(a1)→CNOTc0→t→RY(a2)→CNOTc1→t→RY(a3)→CNOTc0→tR_Y(a_0)\to\mathrm{CNOT}_{c_1\to t}\to R_Y(a_1)\to\mathrm{CNOT}_{c_0\to t}\to R_Y(a_2)\to\mathrm{CNOT}_{c_1\to t}\to R_Y(a_3)\to\mathrm{CNOT}_{c_0\to t}
    The compiled circuit in time order: four rotations and four CNOTs.
  6. Step 6:
    c=01: (P0,P1,P2,P3)=(0,1,1,0) ⇒ V01=RY(a0−a1−a2+a3)=RY(14⋅4θ01)=RY(θ01)c=01:\ (P_0,P_1,P_2,P_3)=(0,1,1,0)\ \Rightarrow\ V_{01}=R_Y(a_0-a_1-a_2+a_3)=R_Y\big(\tfrac14\cdot4\theta_{01}\big)=R_Y(\theta_{01})
    Check for one control state: only the CNOTs controlled by c1=1c_1=1 flip the target. Summing the four aja_j with these signs cancels every angle except θ01\theta_{01}; the states 0000, 1010, 1111 follow in the same way from the other rows of MM.

Result

UCRY(θ00,θ01,θ10,θ11)=CNOTc0→tRY(a3) CNOTc1→tRY(a2) CNOTc0→tRY(a1) CNOTc1→tRY(a0)\boxed{\mathrm{UCR}_Y(\theta_{00},\theta_{01},\theta_{10},\theta_{11})=\mathrm{CNOT}_{c_0\to t}R_Y(a_3)\,\mathrm{CNOT}_{c_1\to t}R_Y(a_2)\,\mathrm{CNOT}_{c_0\to t}R_Y(a_1)\,\mathrm{CNOT}_{c_1\to t}R_Y(a_0)}
M=(11111−1−1111−1−11−11−1),12M is orthogonalM=\begin{pmatrix}1&1&1&1\\1&-1&-1&1\\1&1&-1&-1\\1&-1&1&-1\end{pmatrix},\qquad\tfrac12M\ \text{is orthogonal}
Walsh–Gray matrix M for k = 2 (rows: control states 00, 01, 10, 11; columns: slots j = 0, 1, 2, 3)4×4

Worked example: x = (1, 2, 3, 4)#

Derivation

Tree angles of x = (1, 2, 3, 4)

  1. Step 1:
    ∥x∥2=1+4+9+16=30,N(0)=x02+x12=5,N(1)=x22+x32=25\lVert x\rVert^2=1+4+9+16=30,\qquad N(0)=x_0^2+x_1^2=5,\qquad N(1)=x_2^2+x_3^2=25
    N=4N=4, so n=2n=2 and no padding is needed. Qubit 00 separates (x0,x1)(x_0,x_1) from (x2,x3)(x_2,x_3).
  2. Step 2:
    θ0=2arccos⁡530=2arccos⁡16=2.300523983021863\theta_0=2\arccos\sqrt{\tfrac{5}{30}}=2\arccos\tfrac1{\sqrt6}=2.300523983021863
    Level 00 (empty prefix): cos⁡θ02=N(0)/N(∅)\cos\frac{\theta_0}2=\sqrt{N(0)/N(\varnothing)}.
  3. Step 3:
    θ1,0=2arccos⁡15=2arctan⁡2=2.214297435588181\theta_{1,0}=2\arccos\tfrac{1}{\sqrt5}=2\arctan2=2.214297435588181
    Prefix q0=0q_0=0: N(00)/N(0)=1/5N(00)/N(0)=1/5. An angle φ∈(0,π2)\varphi\in(0,\frac\pi2) with cos⁡φ=1/5\cos\varphi=1/\sqrt5 has sin⁡φ=2/5\sin\varphi=2/\sqrt5, hence tan⁡φ=2\tan\varphi=2.
  4. Step 4:
    θ1,1=2arccos⁡35=2arctan⁡43=1.8545904360032244\theta_{1,1}=2\arccos\tfrac35=2\arctan\tfrac43=1.8545904360032244
    Prefix q0=1q_0=1: N(10)/N(1)=9/25N(10)/N(1)=9/25, so cos⁡φ=3/5\cos\varphi=3/5, sin⁡φ=4/5\sin\varphi=4/5.
  5. Step 5:
    a=θ1,0+θ1,12=arctan⁡2+arctan⁡43=π−arctan⁡2=2.0344439357957027a=\frac{\theta_{1,0}+\theta_{1,1}}2=\arctan2+\arctan\tfrac43=\pi-\arctan2=2.0344439357957027
    tan⁡(α+β)=2+4/31−8/3=−2\tan(\alpha+\beta)=\frac{2+4/3}{1-8/3}=-2 and α+β∈(π2,π)\alpha+\beta\in(\frac\pi2,\pi) because both angles exceed π4\frac\pi4; the angle in (π2,π)(\frac\pi2,\pi) with tangent −2-2 is π−arctan⁡2\pi-\arctan2.
  6. Step 6:
    b=θ1,0−θ1,12=arctan⁡2−arctan⁡43=arctan⁡2−4/31+8/3=arctan⁡211=0.17985349979247822b=\frac{\theta_{1,0}-\theta_{1,1}}2=\arctan2-\arctan\tfrac43=\arctan\frac{2-4/3}{1+8/3}=\arctan\tfrac{2}{11}=0.17985349979247822
    Subtraction formula for the tangent; the difference lies in (−π2,π2)(-\frac\pi2,\frac\pi2), where arctan⁡\arctan inverts tan⁡\tan.

Result

RY(θ0) on qubit 0;RY(a) on qubit 1;CNOT0→1;RY(b) on qubit 1;CNOT0→1\boxed{R_Y(\theta_0)\ \text{on qubit }0;\quad R_Y(a)\ \text{on qubit }1;\quad\mathrm{CNOT}_{0\to1};\quad R_Y(b)\ \text{on qubit }1;\quad\mathrm{CNOT}_{0\to1}}
Derivation

State evolution through the five gates

  1. Step 1:
    ∣ψ1⟩=(RY(θ0)⊗I)∣00⟩=16∣00⟩+56∣10⟩=130(5∣00⟩+5∣10⟩)\lvert\psi_1\rangle=(R_Y(\theta_0)\otimes I)\lvert00\rangle=\tfrac1{\sqrt6}\lvert00\rangle+\sqrt{\tfrac56}\lvert10\rangle=\tfrac{1}{\sqrt{30}}\big(\sqrt5\lvert00\rangle+5\lvert10\rangle\big)
    cos⁡θ02=5/30\cos\frac{\theta_0}2=\sqrt{5/30} and sin⁡θ02=25/30\sin\frac{\theta_0}2=\sqrt{25/30}: the two halves carry the partial norms 55 and 2525.
  2. Step 2:
    ∣ψ2⟩=(I⊗RY(a))∣ψ1⟩≈0.214629∣00⟩+0.347277∣01⟩+0.479925∣10⟩+0.776534∣11⟩\lvert\psi_2\rangle=(I\otimes R_Y(a))\lvert\psi_1\rangle\approx0.214629\lvert00\rangle+0.347277\lvert01\rangle+0.479925\lvert10\rangle+0.776534\lvert11\rangle
    Both branches are multiplied by (cos⁡a2,sin⁡a2)≈(0.525731,0.850651)(\cos\frac a2,\sin\frac a2)\approx(0.525731,0.850651).
  3. Step 3:
    ∣ψ3⟩=CNOT0→1∣ψ2⟩≈0.214629∣00⟩+0.347277∣01⟩+0.776534∣10⟩+0.479925∣11⟩\lvert\psi_3\rangle=\mathrm{CNOT}_{0\to1}\lvert\psi_2\rangle\approx0.214629\lvert00\rangle+0.347277\lvert01\rangle+0.776534\lvert10\rangle+0.479925\lvert11\rangle
    The CNOT exchanges the amplitudes of ∣10⟩\lvert10\rangle and ∣11⟩\lvert11\rangle.
  4. Step 4:
    q0=0: RY(b)RY(a)∣0⟩=RY(θ1,0)∣0⟩=15(∣0⟩+2∣1⟩)q_0=0:\ R_Y(b)R_Y(a)\lvert0\rangle=R_Y(\theta_{1,0})\lvert0\rangle=\tfrac1{\sqrt5}\big(\lvert0\rangle+2\lvert1\rangle\big)
    In the branch q0=0q_0=0 qubit 11 has seen RY(a)R_Y(a) then RY(b)R_Y(b), and a+b=θ1,0=2arctan⁡2a+b=\theta_{1,0}=2\arctan2.
  5. Step 5:
    q0=1: RY(b)XRY(a)∣0⟩=X RY(−b)RY(a)∣0⟩=XRY(θ1,1)∣0⟩=X15(3∣0⟩+4∣1⟩)=15(4∣0⟩+3∣1⟩)q_0=1:\ R_Y(b)XR_Y(a)\lvert0\rangle=X\,R_Y(-b)R_Y(a)\lvert0\rangle=XR_Y(\theta_{1,1})\lvert0\rangle=X\tfrac15\big(3\lvert0\rangle+4\lvert1\rangle\big)=\tfrac15\big(4\lvert0\rangle+3\lvert1\rangle\big)
    RY(b)X=X XRY(b)X=XRY(−b)R_Y(b)X=X\,XR_Y(b)X=XR_Y(-b) and a−b=θ1,1a-b=\theta_{1,1}.
  6. Step 6:
    ∣ψ4⟩=(I⊗RY(b))∣ψ3⟩=130(∣00⟩+2∣01⟩+4∣10⟩+3∣11⟩)\lvert\psi_4\rangle=(I\otimes R_Y(b))\lvert\psi_3\rangle=\tfrac{1}{\sqrt{30}}\big(\lvert00\rangle+2\lvert01\rangle+4\lvert10\rangle+3\lvert11\rangle\big)
    Multiply the branch weights 5/30\sqrt5/\sqrt{30} and 5/305/\sqrt{30} by the two branch states.
  7. Step 7:
    ∣ψ5⟩=CNOT0→1∣ψ4⟩=130(∣00⟩+2∣01⟩+3∣10⟩+4∣11⟩)=∣x⟩\lvert\psi_5\rangle=\mathrm{CNOT}_{0\to1}\lvert\psi_4\rangle=\tfrac{1}{\sqrt{30}}\big(\lvert00\rangle+2\lvert01\rangle+3\lvert10\rangle+4\lvert11\rangle\big)=\lvert x\rangle
    The second CNOT removes the XX in the branch q0=1q_0=1. Without it the state stays (1,2,4,3)/30(1,2,4,3)/\sqrt{30}.

Result

CNOT0→1(I⊗RY(b)) CNOT0→1(I⊗RY(a))(RY(θ0)⊗I)∣00⟩=130(1,2,3,4)T\boxed{\mathrm{CNOT}_{0\to1}(I\otimes R_Y(b))\,\mathrm{CNOT}_{0\to1}(I\otimes R_Y(a))(R_Y(\theta_0)\otimes I)\lvert00\rangle=\tfrac1{\sqrt{30}}(1,2,3,4)^{\mathsf T}}

Circuit · 2 qubits

Quantum circuit on 2 qubitsRY(2.30) on q0; RY(2.03) on q1; X on q1 controlled by q0; RY(0.18) on q1; X on q1 controlled by q0q0q1RY(2.30)RY(2.03)RY(0.18)

Amplitude encoding of x=(1,2,3,4)x=(1,2,3,4): RY(2.300524)R_Y(2.300524) on qubit 00, then the uniformly controlled rotation RY(2.034444)R_Y(2.034444), CNOT\mathrm{CNOT}, RY(0.179853)R_Y(0.179853), CNOT\mathrm{CNOT} on qubit 11. The statevector is (1,2,3,4)/30≈(0.182574,0.365148,0.547723,0.730297)(1,2,3,4)/\sqrt{30}\approx(0.182574,0.365148,0.547723,0.730297).

∣ψ⟩=0.1826∣00⟩+0.3651∣01⟩+0.5477∣10⟩+0.7303∣11⟩\lvert\psi\rangle = 0.1826\lvert 00\rangle + 0.3651\lvert 01\rangle + 0.5477\lvert 10\rangle + 0.7303\lvert 11\rangle

Quick check

For the uniform vector x=(1,1,1,1)x=(1,1,1,1), what is the angle bb of the second RYR_Y slot on qubit 11?

tolerance ±1e-9

The TypeScript program below implements the complete construction for any real vector of length 2n2^n: it computes the tree angles level by level, applies the Gray-code transform, and runs the resulting RYR_Y and CNOT gates on the platform simulator. It encodes the example vector and the signed three-qubit vector treated in the next section.

TypeScriptrunnable
import { Statevector } from '@/lib/quantum-simulator';

// Binary-tree amplitude encoding (qubit 0 = most significant bit, RY(t) = exp(-i t Y / 2)).
// Level s rotates qubit s by theta[p] for every prefix p of qubits 0..s-1 (a uniformly controlled RY),
// compiled into 2^s RY gates and 2^s CNOTs with the Gray-code angle transform a = 2^-s M^T theta.
const parity = (v) => {
  let p = 0;
  for (let m = v; m !== 0; m &= m - 1) p ^= 1;
  return p;
};
const fmt = (v) => (Math.abs(v) < 1e-12 ? 0 : v).toFixed(10);
for (const x of [[1, 2, 3, 4], [0.5, -0.5, 0.5, 0.5, 0, 0, 0, 0.5]]) {
  const n = Math.log2(x.length);
  const sv = Statevector.zero(n);
  let rotations = 0;
  let cnots = 0;
  console.log('x = (' + x.join(', ') + ')');
  for (let s = 0; s < n; s++) {
    const size = 2 ** (n - s);
    const theta = [];
    for (let p = 0; p < 2 ** s; p++) {
      const lo = p * size;
      const mid = lo + size / 2;
      if (s === n - 1) {
        theta.push(2 * Math.atan2(x[mid], x[lo])); // leaf level: the signed angle
      } else {
        let left = 0;
        let total = 0;
        for (let i = lo; i < lo + size; i++) {
          total += x[i] * x[i];
          if (i < mid) left += x[i] * x[i];
        }
        theta.push(total === 0 ? 0 : 2 * Math.acos(Math.sqrt(left / total)));
      }
    }
    console.log('  level ' + s + ' angles: ' + theta.map(fmt).join(' '));
    const d = theta.length;
    for (let j = 0; j < d; j++) {
      const g = j ^ (j >> 1);
      let a = 0;
      for (let c = 0; c < d; c++) a += (parity(c & g) ? -1 : 1) * theta[c];
      sv.applyGate('RY', [s], [a / d]);
      rotations++;
      if (s > 0) {
        const next = ((j + 1) % d) ^ (((j + 1) % d) >> 1);
        sv.applyGate('X', [s], [], [s - 1 - Math.log2(g ^ next)]); // CNOT: control qubit, target s
        cnots++;
      }
    }
  }
  const norm = Math.sqrt(x.reduce((acc, v) => acc + v * v, 0));
  console.log('  gates: ' + rotations + ' RY + ' + cnots + ' CNOT');
  console.log('  amplitudes * ||x||: ' + sv.amplitudes().map((z) => fmt(z.re * norm)).join(' '));
}

Expected output

x = (1, 2, 3, 4)
  level 0 angles: 2.3005239830
  level 1 angles: 2.2142974356 1.8545904360
  gates: 3 RY + 2 CNOT
  amplitudes * ||x||: 1.0000000000 2.0000000000 3.0000000000 4.0000000000
x = (0.5, -0.5, 0.5, 0.5, 0, 0, 0, 0.5)
  level 0 angles: 0.9272952180
  level 1 angles: 1.5707963268 3.1415926536
  level 2 angles: -1.5707963268 1.5707963268 0.0000000000 3.1415926536
  gates: 7 RY + 6 CNOT
  amplitudes * ||x||: 0.5000000000 -0.5000000000 0.5000000000 0.5000000000 0.0000000000 0.0000000000 0.0000000000 0.5000000000

The NumPy version builds the two-qubit circuit as explicit 4×44\times4 matrices, checks that the compiled rotation is block diagonal with blocks RY(θ1,0)R_Y(\theta_{1,0}) and RY(θ1,1)R_Y(\theta_{1,1}), and confirms that the output is (1,2,3,4)/30(1,2,3,4)/\sqrt{30}.

Pythonrunnable
import numpy as np

def ry(t):
    c, s = np.cos(t / 2), np.sin(t / 2)
    return np.array([[c, -s], [s, c]])

I2 = np.eye(2)
CNOT01 = np.array([[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0]])
x = np.array([1.0, 2.0, 3.0, 4.0])
theta0 = 2 * np.arccos(np.sqrt((x[0] ** 2 + x[1] ** 2) / np.sum(x ** 2)))
theta10 = 2 * np.arctan2(x[1], x[0])
theta11 = 2 * np.arctan2(x[3], x[2])
a, b = (theta10 + theta11) / 2, (theta10 - theta11) / 2
ucr = CNOT01 @ np.kron(I2, ry(b)) @ CNOT01 @ np.kron(I2, ry(a))
psi = ucr @ np.kron(ry(theta0), I2) @ np.array([1.0, 0.0, 0.0, 0.0])
print(f"theta0 = {theta0:.12f}  a = {a:.12f}  b = {b:.12f}")
print(np.allclose(ucr[:2, :2], ry(theta10)), np.allclose(ucr[2:, 2:], ry(theta11)), np.allclose(ucr[:2, 2:], 0))
print(np.round(psi * np.sqrt(30), 10))
print(np.allclose(psi, x / np.linalg.norm(x)))

Expected output

theta0 = 2.300523983022  a = 2.034443935796  b = 0.179853499792
True True True
[1. 2. 3. 4.]
True

Signed and complex amplitudes#

The angles θs,p∈[0,π]\theta_{s,p}\in[0,\pi] only produce non-negative amplitudes. Signs are obtained by changing the leaf level alone, because RYR_Y can rotate ∣0⟩\lvert0\rangle to any real unit vector. General complex amplitudes need an additional cascade of RZR_Z rotations.

Theorem

Signed real amplitudes

Let x∈R2nx\in\mathbb R^{2^n} be nonzero with entries of arbitrary sign. Use the angles θs,p\theta_{s,p} of the tree definition for the levels s<n−1s<n-1, computed from the squares xi2x_i^2, and at the leaf level set θn−1,p:=2 atan2(xp1,xp0),\theta_{n-1,p}:=2\,\mathrm{atan2}(x_{p1},x_{p0}), where xpbx_{pb} is the entry with index pbpb and atan2(0,0):=0\mathrm{atan2}(0,0):=0. Then the tree circuit prepares exactly ∣x⟩=∑ixi∣i⟩/∥x∥\lvert x\rangle=\sum_ix_i\lvert i\rangle/\lVert x\rVert, signs included.

Proof (6 steps)
  1. Step 1:
    ∣ψn−1⟩=∑p∈{0,1}n−1ρp∥x∥∣p⟩⊗∣0⟩,ρp:=N(p)=xp02+xp12\lvert\psi_{n-1}\rangle=\sum_{p\in\{0,1\}^{n-1}}\frac{\rho_p}{\lVert x\rVert}\lvert p\rangle\otimes\lvert0\rangle,\qquad\rho_p:=\sqrt{N(p)}=\sqrt{x_{p0}^2+x_{p1}^2}
    The levels s<n−1s<n-1 use only the partial norms, which depend on the squares xi2x_i^2; the induction of the tree theorem applies verbatim up to s=n−1s=n-1.
  2. Step 2:
    ρp>0:φ:=atan2(xp1,xp0) is the unique φ∈(−π,π] with (xp0,xp1)=ρp(cos⁡φ,sin⁡φ)\rho_p>0:\quad\varphi:=\mathrm{atan2}(x_{p1},x_{p0})\ \text{is the unique}\ \varphi\in(-\pi,\pi]\ \text{with}\ (x_{p0},x_{p1})=\rho_p(\cos\varphi,\sin\varphi)
    Definition of the two-argument arctangent: the polar angle of the point (xp0,xp1)(x_{p0},x_{p1}) of the plane.
  3. Step 3:
    cos⁡θn−1,p2=cos⁡φ=xp0ρp,sin⁡θn−1,p2=sin⁡φ=xp1ρp\cos\tfrac{\theta_{n-1,p}}2=\cos\varphi=\frac{x_{p0}}{\rho_p},\qquad\sin\tfrac{\theta_{n-1,p}}2=\sin\varphi=\frac{x_{p1}}{\rho_p}
    θn−1,p/2=φ\theta_{n-1,p}/2=\varphi; cosine and sine carry the signs of the coordinates, unlike the arccos formula, which returns an angle in [0,π][0,\pi] with non-negative sine of the half angle.
  4. Step 4:
    ρp∥x∥ RY(θn−1,p)∣0⟩=ρp∥x∥(xp0ρp∣0⟩+xp1ρp∣1⟩)=xp0∣0⟩+xp1∣1⟩∥x∥\frac{\rho_p}{\lVert x\rVert}\,R_Y(\theta_{n-1,p})\lvert0\rangle=\frac{\rho_p}{\lVert x\rVert}\Big(\frac{x_{p0}}{\rho_p}\lvert0\rangle+\frac{x_{p1}}{\rho_p}\lvert1\rangle\Big)=\frac{x_{p0}\lvert0\rangle+x_{p1}\lvert1\rangle}{\lVert x\rVert}
    Apply the leaf rotation in the branch ∣p⟩\lvert p\rangle; ρp\rho_p cancels.
  5. Step 5:
    ρp=0:xp0=xp1=0,θn−1,p=2 atan2(0,0)=0\rho_p=0:\quad x_{p0}=x_{p1}=0,\qquad\theta_{n-1,p}=2\,\mathrm{atan2}(0,0)=0
    The branch has amplitude 00 and the target entries are 00, so any angle is correct.
  6. Step 6:
    ∣ψn⟩=∑pxp0∣p0⟩+xp1∣p1⟩∥x∥=1∥x∥∑ixi∣i⟩=∣x⟩\lvert\psi_n\rangle=\sum_p\frac{x_{p0}\lvert p0\rangle+x_{p1}\lvert p1\rangle}{\lVert x\rVert}=\frac{1}{\lVert x\rVert}\sum_ix_i\lvert i\rangle=\lvert x\rangle
    Every index ii is uniquely i=pbi=pb with pp of length n−1n-1. For non-negative entries φ∈[0,π2]\varphi\in[0,\frac\pi2] and 2φ=2arccos⁡(xp0/ρp)2\varphi=2\arccos(x_{p0}/\rho_p), so the leaf rule agrees with the arccos rule.

∎

Derivation

Signed example x = (0.5, −0.5, 0.5, 0.5, 0, 0, 0, 0.5)

  1. Step 1:
    ∥x∥2=5⋅0.25=1.25,N(0)=1,N(1)=0.25,n=3\lVert x\rVert^2=5\cdot0.25=1.25,\qquad N(0)=1,\quad N(1)=0.25,\qquad n=3
    Five entries of modulus 12\frac12; the half q0=0q_0=0 holds four of them.
  2. Step 2:
    θ0=2arccos⁡11.25=2arccos⁡25=2arctan⁡12=0.9272952180016122\theta_0=2\arccos\sqrt{\tfrac{1}{1.25}}=2\arccos\tfrac{2}{\sqrt5}=2\arctan\tfrac12=0.9272952180016122
    Level 00: cos⁡φ=2/5\cos\varphi=2/\sqrt5 gives tan⁡φ=12\tan\varphi=\frac12.
  3. Step 3:
    θ1,0=2arccos⁡0.51=π2,θ1,1=2arccos⁡00.25=π\theta_{1,0}=2\arccos\sqrt{\tfrac{0.5}{1}}=\tfrac\pi2,\qquad\theta_{1,1}=2\arccos\sqrt{\tfrac{0}{0.25}}=\pi
    Level 11: the prefix 00 splits its norm 11 equally between 0000 and 0101; the prefix 11 has N(10)=0N(10)=0, so all of its norm goes to 1111.
  4. Step 4:
    θ2,00=2 atan2(−0.5,0.5)=−π2,θ2,01=2 atan2(0.5,0.5)=π2,θ2,10=0,θ2,11=2 atan2(0.5,0)=π\theta_{2,00}=2\,\mathrm{atan2}(-0.5,0.5)=-\tfrac\pi2,\quad\theta_{2,01}=2\,\mathrm{atan2}(0.5,0.5)=\tfrac\pi2,\quad\theta_{2,10}=0,\quad\theta_{2,11}=2\,\mathrm{atan2}(0.5,0)=\pi
    Leaf level with signs: the negative entry x1=−0.5x_1=-0.5 produces the negative angle −π2-\frac\pi2.
  5. Step 5:
    #RY=1+2+4=7,#CNOT=0+2+4=6\#R_Y=1+2+4=7,\qquad\#\mathrm{CNOT}=0+2+4=6
    Levels 00, 11, 22 compile into uniformly controlled rotations with 00, 11, 22 controls.

Result

Vx∣000⟩=15(∣000⟩−∣001⟩+∣010⟩+∣011⟩+∣111⟩)\boxed{V_x\lvert000\rangle=\tfrac{1}{\sqrt5}\big(\lvert000\rangle-\lvert001\rangle+\lvert010\rangle+\lvert011\rangle+\lvert111\rangle\big)}

Circuit · 3 qubits

Quantum circuit on 3 qubitsRY(0.93) on q0; RY(3π/4) on q1; X on q1 controlled by q0; RY(-π/4) on q1; X on q1 controlled by q0; RY(π/4) on q2; X on q2 controlled by q1; RY(-π/2) on q2; X on q2 controlled by q0; RY(0) on q2; X on q2 controlled by q1; RY(-π/4) on q2; X on q2 controlled by q0q0q1q2RY(0.93)RY(3π/4)RY(-π/4)RY(π/4)RY(-π/2)RY(0)RY(-π/4)

Tree circuit of the signed vector (0.5,−0.5,0.5,0.5,0,0,0,0.5)(0.5,-0.5,0.5,0.5,0,0,0,0.5): one rotation on qubit 00, a one-control rotation on qubit 11 (two RYR_Y, two CNOTs) and a two-control rotation on qubit 22 (four RYR_Y, four CNOTs). The statevector is (1,−1,1,1,0,0,0,1)/5(1,-1,1,1,0,0,0,1)/\sqrt5.

∣ψ⟩=0.4472∣000⟩−0.4472∣001⟩+0.4472∣010⟩+0.4472∣011⟩+0.4472∣111⟩\lvert\psi\rangle = 0.4472\lvert 000\rangle - 0.4472\lvert 001\rangle + 0.4472\lvert 010\rangle + 0.4472\lvert 011\rangle + 0.4472\lvert 111\rangle

Definition

Mean phase of a prefix

Let z∈C2nz\in\mathbb C^{2^n} have entries zi=rieiωiz_i=r_ie^{i\omega_i} with ri=∣zi∣r_i=\lvert z_i\rvert and ωi∈R\omega_i\in\mathbb R (ωi\omega_i arbitrary when ri=0r_i=0). For a prefix qq of length s≤ns\le n the mean phase is ωˉ(q):=1∣T(q)∣∑i∈T(q)ωi,∣T(q)∣=2n−s,\bar\omega(q):=\frac{1}{\lvert T(q)\rvert}\sum_{i\in T(q)}\omega_i,\qquad\lvert T(q)\rvert=2^{n-s}, so ωˉ(i0⋯in−1)=ωi\bar\omega(i_0\cdots i_{n-1})=\omega_i and ωˉ(∅)\bar\omega(\varnothing) is the mean of all phases. The phase angles are φs,p:=ωˉ(p1)−ωˉ(p0)\varphi_{s,p}:=\bar\omega(p1)-\bar\omega(p0) for s<ns<n and p∈{0,1}sp\in\{0,1\}^s.

Theorem

The R_Z phase cascade

Prepare the magnitudes ∑i(ri/∥r∥)∣i⟩\sum_i(r_i/\lVert r\rVert)\lvert i\rangle with the RYR_Y tree, then apply for s=0,…,n−1s=0,\dots,n-1 the uniformly controlled RZR_Z with controls 0,…,s−10,\dots,s-1, target ss and angles (φs,p)p(\varphi_{s,p})_p. The result is ∑iri∥r∥ei(ωi−ωˉ(∅))∣i⟩=e−iωˉ(∅) z∥z∥,\sum_i\frac{r_i}{\lVert r\rVert}e^{i(\omega_i-\bar\omega(\varnothing))}\lvert i\rangle=e^{-i\bar\omega(\varnothing)}\,\frac{z}{\lVert z\rVert}, the amplitude encoding of zz up to the global phase e−iωˉ(∅)e^{-i\bar\omega(\varnothing)}. The RZR_Z cascades are diagonal and commute with each other.

Proof (6 steps)
  1. Step 1:
    UCRZ(φ)=∑c∣c⟩⟨c∣⊗diag(e−iφc/2,eiφc/2) is diagonal\mathrm{UCR}_Z(\boldsymbol\varphi)=\sum_c\lvert c\rangle\langle c\rvert\otimes\mathrm{diag}\big(e^{-i\varphi_c/2},e^{i\varphi_c/2}\big)\ \text{is diagonal}
    Each block RZ(φc)R_Z(\varphi_c) is diagonal and the projectors ∣c⟩⟨c∣\lvert c\rangle\langle c\rvert are diagonal in the computational basis. Diagonal matrices commute, so the order of the levels is irrelevant.
  2. Step 2:
    level s: ∣i⟩↦e i(2is−1)φs,p/2∣i⟩,p=i0⋯is−1\text{level }s:\ \lvert i\rangle\mapsto e^{\,i(2i_s-1)\varphi_{s,p}/2}\lvert i\rangle,\qquad p=i_0\cdots i_{s-1}
    The control state is the prefix pp of ii, and RZ(φ)R_Z(\varphi) multiplies ∣0⟩\lvert0\rangle by e−iφ/2e^{-i\varphi/2} and ∣1⟩\lvert1\rangle by e+iφ/2e^{+i\varphi/2}.
  3. Step 3:
    ωˉ(p)=12n−s(∑i∈T(p0)ωi+∑i∈T(p1)ωi)=2n−s−1ωˉ(p0)+2n−s−1ωˉ(p1)2n−s=ωˉ(p0)+ωˉ(p1)2\bar\omega(p)=\frac{1}{2^{n-s}}\Big(\sum_{i\in T(p0)}\omega_i+\sum_{i\in T(p1)}\omega_i\Big)=\frac{2^{n-s-1}\bar\omega(p0)+2^{n-s-1}\bar\omega(p1)}{2^{n-s}}=\frac{\bar\omega(p0)+\bar\omega(p1)}{2}
    T(p)T(p) is the disjoint union of T(p0)T(p0) and T(p1)T(p1), which have equal size 2n−s−12^{n-s-1}: the mean over a prefix is the average of the means of its two children.
  4. Step 4:
    (2is−1) φs,p2={ωˉ(p0)−ωˉ(p1)2=ωˉ(p0)−ωˉ(p),is=0ωˉ(p1)−ωˉ(p0)2=ωˉ(p1)−ωˉ(p),is=1 = ωˉ(p is)−ωˉ(p)\frac{(2i_s-1)\,\varphi_{s,p}}{2}=\begin{cases}\frac{\bar\omega(p0)-\bar\omega(p1)}{2}=\bar\omega(p0)-\bar\omega(p),&i_s=0\\[2pt]\frac{\bar\omega(p1)-\bar\omega(p0)}{2}=\bar\omega(p1)-\bar\omega(p),&i_s=1\end{cases}\ =\ \bar\omega(p\,i_s)-\bar\omega(p)
    Insert φs,p=ωˉ(p1)−ωˉ(p0)\varphi_{s,p}=\bar\omega(p1)-\bar\omega(p0) and the averaging identity.
  5. Step 5:
    ∑s=0n−1(ωˉ(i0⋯is)−ωˉ(i0⋯is−1))=ωˉ(i0⋯in−1)−ωˉ(∅)=ωi−ωˉ(∅)\sum_{s=0}^{n-1}\Big(\bar\omega(i_0\cdots i_s)-\bar\omega(i_0\cdots i_{s-1})\Big)=\bar\omega(i_0\cdots i_{n-1})-\bar\omega(\varnothing)=\omega_i-\bar\omega(\varnothing)
    The total phase of ∣i⟩\lvert i\rangle is the sum over the levels; the sum telescopes.
  6. Step 6:
    ∑iri∥r∥∣i⟩ ⟼ ∑iri∥r∥ei(ωi−ωˉ(∅))∣i⟩=e−iωˉ(∅)∑izi∥z∥∣i⟩\sum_i\frac{r_i}{\lVert r\rVert}\lvert i\rangle\ \longmapsto\ \sum_i\frac{r_i}{\lVert r\rVert}e^{i(\omega_i-\bar\omega(\varnothing))}\lvert i\rangle=e^{-i\bar\omega(\varnothing)}\sum_i\frac{z_i}{\lVert z\rVert}\lvert i\rangle
    ∥r∥=∥z∥\lVert r\rVert=\lVert z\rVert and rieiωi=zir_ie^{i\omega_i}=z_i. The common factor e−iωˉ(∅)e^{-i\bar\omega(\varnothing)} is a global phase, which no measurement can detect.

∎

Quick check

A leaf pair has entries (xp0,xp1)=(0.5,−0.5)(x_{p0},x_{p1})=(0.5,-0.5). What leaf angle θ=2 atan2(xp1,xp0)\theta=2\,\mathrm{atan2}(x_{p1},x_{p0}) (in radians) does the signed construction use?

tolerance ±0.000001

Resource count, lower bound and the input problem#

Proposition

Gate count of the tree construction

For N=2nN=2^n real amplitudes the tree circuit uses 2n−12^n-1 rotations RYR_Y and 2n−22^n-2 CNOTs. For complex amplitudes the RZR_Z cascade doubles both numbers, to 2(2n−1)2(2^n-1) rotations and 2(2n−2)2(2^n-2) CNOTs. Hence state preparation costs O(N)O(N) gates, and the depth is also O(N)O(N) because consecutive gates of a level share the target qubit.

Proof (5 steps)
  1. Step 1:
    level s (k=s controls):2s rotations,{0 CNOTs,s=02s CNOTs,s≥1\text{level }s\ (k=s\ \text{controls}):\quad2^s\ \text{rotations},\qquad\begin{cases}0\ \text{CNOTs},&s=0\\2^s\ \text{CNOTs},&s\ge1\end{cases}
    Compilation theorem for k≥1k\ge1; the level s=0s=0 is a single uncontrolled rotation.
  2. Step 2:
    #RY=∑s=0n−12s=2n−12−1=2n−1\#R_Y=\sum_{s=0}^{n-1}2^s=\frac{2^n-1}{2-1}=2^n-1
    Geometric series.
  3. Step 3:
    #CNOT=∑s=1n−12s=(2n−1)−20=2n−2\#\mathrm{CNOT}=\sum_{s=1}^{n-1}2^s=(2^n-1)-2^0=2^n-2
    The same series without the term s=0s=0.
  4. Step 4:
    complex: #RY+#RZ=2(2n−1),#CNOT=2(2n−2)\text{complex: }\#R_Y+\#R_Z=2(2^n-1),\qquad\#\mathrm{CNOT}=2(2^n-2)
    The phase cascade has the same level structure as the magnitude cascade.
  5. Step 5:
    2n−1<N,2(2n−1)<2N ⇒ gates=O(N),depth≥#gates on qubit n−1≥2n−12^n-1<N,\quad2(2^n-1)<2N\ \Rightarrow\ \text{gates}=O(N),\qquad\text{depth}\ge\#\text{gates on qubit }n-1\ge2^{n-1}
    N=2nN=2^n. Every gate of level n−1n-1 acts on qubit n−1n-1, so these 2n−12^{n-1} rotations run one after another and the depth is Θ(N)\Theta(N) as well.

∎

Theorem

Parameter-counting lower bound

Let n≥1n\ge1, c≥0c\ge0, and let ScS_c be the set of nn-qubit states (modulo global phase) that can be prepared exactly from ∣0n⟩\lvert0^n\rangle by circuits with at most cc CNOT gates and arbitrarily many one-qubit gates. If 3(n+2c)<2n+1−23(n+2c)<2^{n+1}-2, then ScS_c has measure zero in the state space. Consequently almost every nn-qubit state requires c ≥ 2n+1−2−3n6c\ \ge\ \frac{2^{n+1}-2-3n}{6} CNOTs, and for n≥4n\ge4 this is at least 2n/62^n/6, i.e. Ω(2n)=Ω(N)\Omega(2^n)=\Omega(N). The measure-zero step uses Sard's theorem (cited, not proved here).

Proof (11 steps)
  1. Step 1:
    dim⁡RC2n=2n+1,dim⁡R{ψ:∥ψ∥=1}/U(1)=2n+1−1−1=2n+1−2\dim_{\mathbb R}\mathbb C^{2^n}=2^{n+1},\qquad\dim_{\mathbb R}\big\{\psi:\lVert\psi\rVert=1\big\}/U(1)=2^{n+1}-1-1=2^{n+1}-2
    States modulo normalisation and global phase form the complex projective space CP2n−1\mathbb{CP}^{2^n-1}, a smooth manifold of real dimension 2n+1−22^{n+1}-2: the unit sphere removes one real parameter and the phase another.
  2. Step 2:
    fix a layout Λ=((u1,v1),…,(uc′,vc′)),c′≤c,ur≠vr\text{fix a layout }\Lambda=\big((u_1,v_1),\dots,(u_{c'},v_{c'})\big),\quad c'\le c,\quad u_r\ne v_r
    A layout is the ordered list of CNOT (control, target) pairs; between the CNOTs only one-qubit gates occur.
  3. Step 3:
    #slots=n+2c′≤n+2c\#\text{slots}=n+2c'\le n+2c
    All one-qubit gates on a wire between two consecutive CNOTs touching that wire multiply to one element of U(2)U(2). Each wire starts with one such segment, and each CNOT ends one segment on each of its two wires and starts two new ones.
  4. Step 4:
    U(2)={eiγV: V∈SU(2)},dim⁡RSU(2)=3U(2)=\{e^{i\gamma}V:\ V\in SU(2)\},\qquad\dim_{\mathbb R}SU(2)=3
    SU(2)SU(2) is diffeomorphic to the unit sphere S3S^3 of quaternions. The phases eiγe^{i\gamma} of all slots multiply to one global phase of the output state, which is invisible in CP2n−1\mathbb{CP}^{2^n-1}.
  5. Step 5:
    FΛ:SU(2)n+2c′→CP2n−1,(V1,…,Vn+2c′)↦[CΛ(V)∣0n⟩]F_\Lambda:SU(2)^{n+2c'}\to\mathbb{CP}^{2^n-1},\qquad(V_1,\dots,V_{n+2c'})\mapsto\big[C_\Lambda(V)\lvert0^n\rangle\big]
    The entries of CΛ(V)∣0n⟩C_\Lambda(V)\lvert0^n\rangle are polynomials in the entries of the VrV_r, the output is never the zero vector, and the projection to CP2n−1\mathbb{CP}^{2^n-1} is smooth on nonzero vectors, so FΛF_\Lambda is smooth.
  6. Step 6:
    rank⁡dFΛ≤3(n+2c′)≤3(n+2c)<2n+1−2=dim⁡CP2n−1\operatorname{rank}dF_\Lambda\le3(n+2c')\le3(n+2c)<2^{n+1}-2=\dim\mathbb{CP}^{2^n-1}
    The rank of the differential is bounded by the dimension of the domain. Under the hypothesis every point of the domain is critical.
  7. Step 7:
    μ(FΛ(SU(2)n+2c′))=0\mu\big(F_\Lambda(SU(2)^{n+2c'})\big)=0
    Sard's theorem: the set of critical values of a smooth map between manifolds has measure zero. Here every value is critical, so the whole image is a null set.
  8. Step 8:
    Sc=⋃c′=0c ⋃Λ with c′ CNOTsFΛ(SU(2)n+2c′),#{Λ}=∑c′=0c(n(n−1))c′<∞S_c=\bigcup_{c'=0}^{c}\ \bigcup_{\Lambda\ \text{with}\ c'\ \text{CNOTs}}F_\Lambda\big(SU(2)^{n+2c'}\big),\qquad\#\{\Lambda\}=\sum_{c'=0}^{c}\big(n(n-1)\big)^{c'}<\infty
    Every circuit with at most cc CNOTs has some layout, and each CNOT has n(n−1)n(n-1) ordered (control, target) choices.
  9. Step 9:
    μ(Sc)≤∑Λμ(FΛ(⋅))=0\mu(S_c)\le\sum_\Lambda\mu\big(F_\Lambda(\cdot)\big)=0
    A finite union of null sets is a null set.
  10. Step 10:
    ψ∉Sc for almost every ψ ⇒ 3(n+2c)≥2n+1−2  ⟺  c≥2n+1−2−3n6\psi\notin S_c\ \text{for almost every }\psi\ \Rightarrow\ 3(n+2c)\ge2^{n+1}-2\iff c\ge\frac{2^{n+1}-2-3n}{6}
    If a generic state could be prepared with cc CNOTs violating the inequality, it would lie in the null set ScS_c. Solving the inequality for cc gives the bound.
  11. Step 11:
    n≥4: 2n≥3n+2 ⇒ 2n+1−2−3n6≥2n+1−2n6=2n6n\ge4:\ 2^n\ge3n+2\ \Rightarrow\ \frac{2^{n+1}-2-3n}{6}\ge\frac{2^{n+1}-2^n}{6}=\frac{2^n}{6}
    24=16≥142^4=16\ge14, and the left side doubles while the right side grows by 33 per step. Hence c=Ω(2n)=Ω(N)c=\Omega(2^n)=\Omega(N).

∎

Corollary

Sharper count: two parameters per gate

Under the hypotheses of the previous theorem, almost every nn-qubit state requires c ≥ ⌈2n+1−2n−24⌉=⌈2n−n−12⌉c\ \ge\ \Big\lceil\frac{2^{n+1}-2n-2}{4}\Big\rceil=\Big\lceil\frac{2^n-n-1}{2}\Big\rceil CNOTs (Shende–Bullock–Markov counting). This bound is at least the previous one for every n≥1n\ge1, takes the values 0,1,2,6,130,1,2,6,13 for n=1,…,5n=1,\dots,5, and is the value the AmplitudeTree widget displays. Both bounds are valid; the previous one is simply weaker.

Proof (7 steps)
  1. Step 1:
    V=RZ(α)RY(β)RZ(γ)=RX(α′)RY(β′)RX(γ′)(up to phase), every V∈U(2)V=R_Z(\alpha)R_Y(\beta)R_Z(\gamma)=R_X(\alpha')R_Y(\beta')R_X(\gamma')\quad\text{(up to phase), every }V\in U(2)
    The ZYZZYZ Euler decomposition of lesson L20, and its XYXXYX analogue obtained by conjugating with HH (which swaps XX and ZZ and maps YY to −Y-Y).
  2. Step 2:
    CNOTu→v (RZ(γ)⊗I)=(RZ(γ)⊗I) CNOTu→v,CNOTu→v (I⊗RX(γ))=(I⊗RX(γ)) CNOTu→v\mathrm{CNOT}_{u\to v}\,(R_Z(\gamma)\otimes I)=(R_Z(\gamma)\otimes I)\,\mathrm{CNOT}_{u\to v},\qquad\mathrm{CNOT}_{u\to v}\,(I\otimes R_X(\gamma))=(I\otimes R_X(\gamma))\,\mathrm{CNOT}_{u\to v}
    CNOT=∣0⟩⟨0∣⊗I+∣1⟩⟨1∣⊗X\mathrm{CNOT}=\lvert0\rangle\langle0\rvert\otimes I+\lvert1\rangle\langle1\rvert\otimes X: a diagonal gate on the control commutes with both projectors, and RX(γ)=e−iγX/2R_X(\gamma)=e^{-i\gamma X/2} commutes with II and XX on the target.
  3. Step 3:
    ⋯ CNOT (RZ(γ)⊗I)  ⟶  ⋯ (RZ(γ)⊗I) CNOT\cdots\,\mathrm{CNOT}\,(R_Z(\gamma)\otimes I)\;\longrightarrow\;\cdots\,(R_Z(\gamma)\otimes I)\,\mathrm{CNOT}
    Process the CNOTs from the last to the first. For each CNOT, write the one-qubit gate that follows it on the control wire as RZ(α)RY(β)⋅RZ(γ)R_Z(\alpha)R_Y(\beta)\cdot R_Z(\gamma) and on the target wire as RX(α′)RY(β′)⋅RX(γ′)R_X(\alpha')R_Y(\beta')\cdot R_X(\gamma'), and move the right-most factor through the CNOT into the gate that precedes it on the same wire. That gate stays an arbitrary element of U(2)U(2), so it is decomposed in the same way when its own CNOT is processed.
  4. Step 4:
    V∣0⟩=RZ(α)RY(β)RZ(γ)∣0⟩=e−iγ/2RZ(α)RY(β)∣0⟩V\lvert0\rangle=R_Z(\alpha)R_Y(\beta)R_Z(\gamma)\lvert0\rangle=e^{-i\gamma/2}R_Z(\alpha)R_Y(\beta)\lvert0\rangle
    After the sweep, the first gate on each wire still acts on ∣0⟩\lvert0\rangle, an eigenvector of RZ(γ)R_Z(\gamma). Its state is fixed by the two Bloch angles (β,α)(\beta,\alpha) and a phase that joins the invisible global phase.
  5. Step 5:
    dim⁡(parameter space) ≤ 2n+(2+2)c\dim(\text{parameter space})\ \le\ 2n+(2+2)c
    22 parameters per wire for the first layer and 2+22+2 for the two gates after each CNOT. As in the theorem, each layout gives a smooth map from this parameter space into CP2n−1\mathbb{CP}^{2^n-1}, and there are finitely many layouts.
  6. Step 6:
    2n+4c<2n+1−2 ⇒ μ(Sc)=0⟹c≥2n+1−2n−24=2n−n−12 for almost every ψ2n+4c<2^{n+1}-2\ \Rightarrow\ \mu(S_c)=0\qquad\Longrightarrow\qquad c\ge\frac{2^{n+1}-2n-2}{4}=\frac{2^n-n-1}{2}\ \text{for almost every }\psi
    Sard's theorem, exactly as in the previous proof, with 3(n+2c)3(n+2c) replaced by 2n+4c2n+4c.
  7. Step 7:
    2n+1−2n−24−2n+1−2−3n6=3(2n+1−2n−2)−2(2n+1−2−3n)12=2n+1−212 ≥ 0\frac{2^{n+1}-2n-2}{4}-\frac{2^{n+1}-2-3n}{6}=\frac{3(2^{n+1}-2n-2)-2(2^{n+1}-2-3n)}{12}=\frac{2^{n+1}-2}{12}\ \ge\ 0
    So the sharper count dominates the previous bound for every n≥1n\ge1. Rounding up gives n=3: ⌈4/2⌉=2n=3:\ \lceil 4/2\rceil=2 and n=5: ⌈26/2⌉=13n=5:\ \lceil 26/2\rceil=13.

∎

Derivation

Lower bound versus construction

  1. Step 1:
    n=3: 16−2−96=56 ⇒ c≥1,complex tree: 2(23−2)=12n=3:\ \frac{16-2-9}{6}=\frac56\ \Rightarrow\ c\ge1,\qquad\text{complex tree: }2(2^3-2)=12
    Round the bound up to an integer.
  2. Step 2:
    n=5: 64−2−156=476≈7.83 ⇒ c≥8,complex tree: 2(25−2)=60n=5:\ \frac{64-2-15}{6}=\frac{47}{6}\approx7.83\ \Rightarrow\ c\ge8,\qquad\text{complex tree: }2(2^5-2)=60
    The bound and the construction both grow like 2n2^n.
  3. Step 3:
    n=10: 2048−2−306=336,complex tree: 2(210−2)=2044n=10:\ \frac{2048-2-30}{6}=336,\qquad\text{complex tree: }2(2^{10}-2)=2044
    For large nn the ratio of the construction to the bound tends to 2n+12n+1/6=6\frac{2^{n+1}}{2^{n+1}/6}=6.
  4. Step 4:
    sharper count: n=3⇒c≥2,n=5⇒c≥13,n=10⇒c≥⌈10132⌉=507\text{sharper count: }n=3\Rightarrow c\ge2,\quad n=5\Rightarrow c\ge13,\quad n=10\Rightarrow c\ge\Big\lceil\frac{1013}{2}\Big\rceil=507
    The corollary improves the constant: the ratio of the complex construction 2(2n−2)2(2^n-2) to (2n−n−1)/2(2^n-n-1)/2 tends to 44, and for real vectors the 2n−22^n-2 CNOTs of the tree are within a factor 22 of the bound.

Result

2n+1−2−3n6 ≤ cmin⁡(ψ) ≤ 2n+1−4for almost every n-qubit state ψ\boxed{\frac{2^{n+1}-2-3n}{6}\ \le\ c_{\min}(\psi)\ \le\ 2^{n+1}-4\qquad\text{for almost every }n\text{-qubit state }\psi}

Quick check

How many CNOTs does the tree construction use to amplitude-encode a real vector with N=32N=32 entries?

tolerance ±1e-9

Quick check

A quantum algorithm processes ∣x⟩\lvert x\rangle for a generic x∈RNx\in\mathbb R^N in time O(log⁡N)O(\log N). What is the end-to-end cost when xx is given as a classical list and loaded with a gate-based state-preparation circuit?

Select one answer

Summary. Amplitude encoding stores NN numbers in ⌈log⁡2N⌉\lceil\log_2N\rceil qubits, and its fidelity kernel cos⁡2∠(x,x′)\cos^2\angle(x,x') varies smoothly with the data. Preparing the state costs Θ(N)\Theta(N) gates for generic inputs: the binary tree of uniformly controlled rotations achieves O(N)O(N), and parameter counting shows that Ω(N)\Omega(N) CNOTs are necessary. The next lesson, Angle & Phase Encoding, uses one rotation per feature. It needs more qubits, but only one layer of gates, and its kernel has a product form.

References

  1. M. Möttönen, J. J. Vartiainen, V. Bergholm and M. M. Salomaa, Transformation of quantum states using uniformly controlled rotations, Quantum Information and Computation 5, 467–473 (2005).arxiv.org
  2. L. Grover and T. Rudolph, Creating superpositions that correspond to efficiently integrable probability distributions (2002).arxiv.org
  3. V. V. Shende, S. S. Bullock and I. L. Markov, Synthesis of quantum-logic circuits, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 25, 1000–1010 (2006).doi:10.1109/TCAD.2005.855930
  4. M. Plesch and Č. Brukner, Quantum-state preparation with universal gate decompositions, Physical Review A 83, 032302 (2011).doi:10.1103/PhysRevA.83.032302
  5. M. Schuld and F. Petruccione, Machine Learning with Quantum Computers, 2nd ed., Springer (2021), Ch. 4 "Representing Data on a Quantum Computer" (amplitude encoding and state preparation).doi:10.1007/978-3-030-83098-4
  6. S. Aaronson, Read the fine print, Nature Physics 11, 291–293 (2015).doi:10.1038/nphys3272
  7. V. Giovannetti, S. Lloyd and L. Maccone, Quantum random access memory, Physical Review Letters 100, 160501 (2008).doi:10.1103/PhysRevLett.100.160501
  8. A. Sard, The measure of the critical values of differentiable maps, Bulletin of the American Mathematical Society 48, 883–890 (1942).doi:10.1090/S0002-9904-1942-07811-6

Hands-on labs

  • Amplitude-encode the vector (1, 2, 3, 4)

    1 step · auto-graded

    Prepare the amplitude encoding ∣x⟩=130(∣00⟩+2∣01⟩+3∣10⟩+4∣11⟩)\lvert x\rangle=\tfrac1{\sqrt{30}}\big(\lvert00\rangle+2\lvert01\rangle+3\lvert10\rangle+4\lvert11\rangle\big) of x=(1,2,3,4)x=(1,2,3,4) on two qubits with at most five gates from {RY,CNOT}\{R_Y,\mathrm{CNOT}\}: one rotation for the split on qubit 00 and a uniformly controlled RYR_Y on qubit 11, compiled into two rotations and two CNOTs.

    Open lab