Quantum algorithms often begin with a deceptively short instruction: “prepare |b⟩,” “load the probability distribution,” or “encode the classical vector into amplitudes.” State preparation is the mathematical and engineering work hidden inside that sentence.
A quantum register of n qubits can represent 2n complex amplitudes, but a generic vector contains exponentially many independent numbers. Unless those amplitudes have structure or arrive through a strong data-access oracle, preparing an arbitrary amplitude-encoded state generally requires resources proportional to the vector length. This is why state loading repeatedly appears as the boundary condition in Guides 19, 57, 62, 63 and 68.
This guide develops basis encoding, angle encoding, amplitude encoding, exact arbitrary-state synthesis, probability-tree rotations, phase loading, uniformly controlled rotations, QROM lookup, coherent data-to-rotation patterns, QRAM assumptions, sparse/structured preparation, uncomputation and end-to-end complexity accounting.
Specify amplitudes → exploit structure if available → compute conditional probabilities/phases → apply controlled rotations or coherent lookup → uncompute work registers → verify normalisation, phase and preparation cost.
1. What state preparation means
Given target amplitudes αx satisfying
Σ_x |α_x|²=1,
the state-preparation problem is to implement a unitary U such that
U|0^n⟩=Σ_{x=0}^{2^n−1} α_x|x⟩.
Only the action of U on |0n⟩ is prescribed. Its action on the remaining basis states can be chosen for circuit convenience.
Global phase is physically irrelevant, so one phase degree of freedom can be fixed.
2. A generic n-qubit pure state has exponentially many parameters
A normalised vector in complex dimension D=2n has 2D real numbers before constraints.
Normalisation removes one real degree of freedom and global phase removes another, leaving
2D−2=2^{n+1}−2
independent real parameters for a generic pure state.
Any exact universal state-synthesis method must somehow receive and encode this exponential information. A circuit with only polynomially many continuously parameterised elementary gates cannot exactly reach every possible n-qubit state from |0…0⟩.
3. Basis encoding
Classical bit string x=x1…xn can be loaded as the computational basis state
|x⟩=|x_1⟩⊗…⊗|x_n⟩.
Starting from |0n⟩, apply X to every qubit whose corresponding bit is one.
This costs O(n) gates and is easy because n classical bits contain only n bits of information.
4. Angle encoding
Real features xj can be encoded into single-qubit rotations such as
⊗_j R_y(x_j)|0⟩.
This uses one qubit per encoded feature in the simplest version and O(n) rotations.
The representation is efficient but does not compress D arbitrary classical numbers into log D qubits. Guide 62 uses angle encoding as a machine-learning feature map.
5. Amplitude encoding
Given classical vector v∈ℂD, define
|v⟩=(1/||v||₂)Σ_{j=0}^{D−1}v_j|j⟩.
Only n=⌈log₂D⌉ qubits are required to represent the index space.
The compression is representational, not automatically computational. If all D amplitudes arrive as an ordinary unsorted classical array, reading them already costs Ω(D).
6. Separate magnitude and phase
Write
v_j=|v_j|e^{iφ_j}.
Amplitude preparation can be split conceptually into:
- prepare probabilities
p_j=|v_j|²/||v||²so amplitudes are √pj; - apply diagonal phases
e^{iφ_j}.
For real nonnegative vectors only the probability tree is needed.
7. Binary probability tree
Suppose D=2n and target probabilities are p0,…,pD−1.
At the first qubit, aggregate all probabilities whose most significant bit is zero:
P_0=Σ_{x:x_1=0}p_x.
Set the first-qubit rotation θ so
cos²(θ/2)=P_0, sin²(θ/2)=1−P_0.
Then, conditioned on the first bit, rotate the second qubit according to conditional probabilities inside each branch. Continue recursively.
8. Worked two-qubit probability tree
Prepare
|ψ⟩=√0.4|00⟩+√0.3|01⟩+√0.2|10⟩+√0.1|11⟩.
The first-bit totals are
P(x_1=0)=0.4+0.3=0.7;P(x_1=1)=0.2+0.1=0.3.
Choose θ₁ satisfying
cos²(θ₁/2)=0.7
so θ₁=2arcsin√0.3≈1.15928 radians.
Conditioned on x₁=0, the second-bit probability of one is
0.3/0.7=3/7.
Choose θ_{2|0}=2arcsin√(3/7)≈1.42745.
Conditioned on x₁=1, the second-bit probability of one is
0.1/0.3=1/3,
so θ_{2|1}=2arcsin√(1/3)≈1.23096.
One unconditional Ry plus one uniformly controlled second-qubit Ry prepares the four magnitudes exactly.
9. Uniformly controlled rotations
A uniformly controlled rotation applies a different target rotation for every computational-basis setting of several control qubits.
For k controls there are 2k angles.
Gray-code decompositions implement the multiplexor as a sequence of single-qubit rotations and CNOTs. Recursive arbitrary-state-preparation methods use one layer of such multiplexed rotations per tree depth.
Möttönen and collaborators developed efficient uniformly controlled rotation constructions for arbitrary state transformation. [1]
10. Generic exact gate count is exponential
At tree level k there are 2k conditional branches.
Summing over n levels gives
1+2+4+…+2^{n−1}=2^n−1.
Thus arbitrary magnitude synthesis needs Θ(2n) independent rotation information. Generic phases add another comparable family of controls.
This matches the parameter-count lower-bound intuition: exact arbitrary state loading is generically exponential in qubit number.
11. Phase preparation
After magnitude loading, apply a diagonal unitary
D_φ=Σ_x e^{iφ_x}|x⟩⟨x|.
A generic diagonal unitary also contains exponentially many independent phases.
When φx is generated by a simple arithmetic formula, however, one can compute φ(x) reversibly into a work register, apply phase kickback, and uncompute. Structured phase functions can therefore be exponentially cheaper than arbitrary phase tables.
12. Grover–Rudolph structured distributions
Grover and Rudolph showed that certain probability distributions can be prepared efficiently when interval integrals of the underlying density can be computed efficiently. [2]
At each binary split, compute the probability mass in the left and right half and rotate according to their ratio.
The method avoids reading an arbitrary D-entry table because branch probabilities come from a succinct integrable model.
The speedup comes from structure in the data source, not from amplitude encoding alone.
13. Sparse states
If only s amplitudes are nonzero and their indices/values are efficiently listable, preparation can scale with s and log D rather than D.
One strategy prepares a superposition over the s active labels and then reversibly maps compressed labels to their D-dimensional indices.
Complexity depends on whether the active values themselves are arbitrary and on the reversible lookup cost.
14. Product states
If the target factorises
|ψ⟩=⊗_{j=1}^n (cos(θ_j/2)|0⟩+e^{iφ_j}sin(θ_j/2)|1⟩),
only O(n) single-qubit rotations are required.
The exponentially large amplitude table is generated implicitly as products of n local factors.
This illustrates the governing principle: low-description-complexity states can have low-preparation complexity even when their amplitude vector is exponentially long.
15. Tensor-network states
Matrix-product states with bounded bond dimension can often be prepared sequentially using ancillas/isometries whose size depends on the bond dimension rather than on 2n.
Guide 16 owns tensor-network compression. For state preparation, the point is that a compact tensor-network description can be compiled into a circuit with polynomial resources when bond dimensions remain polynomially bounded.
16. QROM: coherent lookup from a classical table
Quantum read-only memory (QROM) is a reversible circuit abstraction for applying a classical lookup table coherently:
Σ_j α_j|j⟩|0⟩ → Σ_j α_j|j⟩|d_j⟩.
The address register can be in superposition, but the stored data dj are fixed classical constants compiled into the circuit.
QROM is not the same as assuming a physically random-access quantum memory that answers arbitrary memory queries at unit cost. Circuit QROM has explicit Toffoli/T-depth/ancilla trade-offs.
17. Lookup does not yet create amplitudes
QROM can load a value dj into a work register, but amplitude encoding requires converting that value into a rotation or acceptance amplitude.
A common pattern is:
- prepare index superposition;
- QROM-load dj;
- compute an angle or threshold from dj;
- rotate/compare an ancilla coherently;
- uncompute dj and arithmetic workspace;
- use postselection or amplitude amplification if necessary.
Every stage contributes to cost.
18. Rejection-sampling preparation
Suppose an easy proposal distribution qj dominates target pj so
p_j≤Cq_j.
Prepare √qj amplitudes, load/compute the acceptance ratio pj/(Cqj), and rotate an ancilla.
Conditioned on acceptance, the index register has the target distribution.
The success probability is about 1/C. Amplitude amplification reduces O(C) repeated trials toward O(√C) coherent iterations.
19. Alias sampling and table methods
Classical alias tables rewrite a discrete distribution so sampling uses one uniform bucket choice plus one biased binary decision.
Quantum chemistry resource constructions adapt coherent alias/QROM ideas to load coefficient distributions for linear-combination-of-unitaries algorithms.
The preprocessing table may be O(D) classically, while repeated coherent queries thereafter become cheap enough to amortise that cost across long algorithms.
20. QRAM assumption
An idealised QRAM oracle is often written
O_d: |j⟩|0⟩→|j⟩|d_j⟩
with polylogarithmic address cost.
If a quantum algorithm’s exponential speedup depends on treating Od as unit cost, the physical construction, update cost, fault tolerance and data-loading path into that memory must be stated.
QRAM is an input model, not a theorem that arbitrary classical data can be loaded exponentially fast.
21. Block encoding from state preparation
State-preparation pairs can be used to block-encode matrices.
If one unitary prepares row-dependent amplitudes and another prepares column/value information, their overlap can make a desired matrix appear as a sub-block of a larger unitary.
This is why state-loading complexity propagates into QSVT, linear-system, SDP and Hamiltonian-simulation algorithms: the “input oracle” may itself be a sophisticated state-preparation circuit.
22. Uncomputation
Suppose a work register contains f(j) entangled with the desired index amplitudes.
If the work data are no longer needed, apply the reversible computation backward:
|j⟩|f(j)⟩→|j⟩|0⟩.
Without uncomputation, garbage states can remain entangled with the target and turn its reduced state into an unintended mixture.
“Clean ancillas” are a mathematical resource because they preserve interference.
23. Approximate preparation
Exact synthesis is rarely necessary.
If target |ψ⟩ and prepared |ψ̃⟩ satisfy
|| |ψ⟩−|ψ̃⟩ ||₂≤ε,
then measurement probabilities and expectation values are close, with bounds determined by trace distance/operator norm.
Finite rotation synthesis, truncated small amplitudes and approximate arithmetic can dramatically reduce gate count if their errors are budgeted against the downstream algorithm tolerance.
24. Rotation-synthesis cost
On a fault-tolerant Clifford+T computer, arbitrary rotations are not elementary.
A single Rz(θ) must be approximated by a discrete fault-tolerant gate sequence or implemented through magic-state techniques.
Preparing thousands or millions of independent arbitrary angles can therefore dominate T count even when the logical circuit diagram looks simple.
25. State preparation for amplitude estimation
Guide 57 assumes a unitary A preparing
A|0⟩=√(1−a)|bad⟩+√a|good⟩.
QAE query complexity counts repeated A and A† applications.
If A itself requires O(D) gates to load a D-entry classical distribution, the quadratic 1/ε advantage can remain useful for very high precision, but it does not create an exponential D advantage automatically.
26. State preparation for HHL and PDE algorithms
Guide 19 assumes |b⟩ can be prepared efficiently. Guide 63 assumes initial states/right-hand sides can be loaded efficiently.
If b is generated by a simple analytic function, sparse source or previous quantum computation, this may be realistic.
If b is an arbitrary dense classical vector, loading can cost Θ(D) and dominate a solver whose internal dependence on D is only polylogarithmic.
27. State preparation for quantum machine learning
Amplitude-encoded machine-learning proposals often advertise log D qubits for D features.
That is meaningful only when data arise from efficient quantum access, sparse/structured generative models, or amortised QRAM/QROM assumptions.
Angle/re-uploading encodings may use more qubits/gates per feature but avoid the hidden arbitrary-vector loading assumption.
28. Verification
For small systems, full tomography can verify prepared amplitudes.
For large systems, verification should target properties relevant to the algorithm:
- normalisation;
- known symmetries;
- overlap with a reference;
- selected marginals;
- classical shadows for many observables;
- cross-entropy or likelihood tests when sampling distributions are classically tractable.
One should not require exponentially expensive tomography merely to certify a state intended for one compressed downstream observable.
29. Common misconception: log D qubits means O(log D) loading time
Qubit capacity and preparation complexity are different resources. A generic D-amplitude state contains Θ(D) independent classical information.
30. Common misconception: QROM and QRAM are the same
QROM is often a compiled reversible circuit for a fixed classical table with explicit gate/ancilla trade-offs. QRAM usually denotes a stronger coherent random-access memory abstraction whose physical implementation cost must be specified.
31. Common misconception: arbitrary state preparation can be polynomial because every state fits in n qubits
The state vector fits mathematically, but specifying a generic state requires exponentially many parameters. Efficient preparation requires structure, approximation or a strong input oracle.
32. Worked synthesis problem
Prepare probabilities {0.4,0.3,0.2,0.1} on two qubits.
Step 1: Root split. First-bit probability is 0.7 for 0 and 0.3 for 1, so use θ₁=2arcsin√0.3≈1.15928.
Step 2: Left branch. Conditional probability of second bit 1 is 3/7, so θ_{2|0}=2arcsin√(3/7)≈1.42745.
Step 3: Right branch. Conditional probability is 1/3, so θ_{2|1}=2arcsin√(1/3)≈1.23096.
Step 4: Apply multiplexed second rotation. Control on the first qubit to select the correct branch angle.
Step 5: Verify. Squared output amplitudes are exactly 0.4,0.3,0.2,0.1 under ideal rotations.
Step 6: Generalise. For n qubits, the same probability-tree method requires exponentially many branch probabilities for a generic table, revealing the state-loading bottleneck explicitly.
33. Practice set
- Define exact state preparation.
- How many real parameters describe a generic n-qubit pure state up to normalisation/global phase?
- What is amplitude encoding?
- Why does amplitude encoding not imply fast arbitrary data loading?
- How does a binary probability tree determine rotations?
- What is a uniformly controlled rotation?
- What property makes Grover–Rudolph preparation efficient?
- What is QROM?
- Why must work registers be uncomputed?
- How can amplitude amplification help rejection-based preparation?
- Why are arbitrary rotations costly fault tolerantly?
- What should a quantum algorithm report when its speedup assumes efficient state preparation?
Answers
- Construct U with
U|0^n⟩=Σ_xα_x|x⟩for the target amplitudes. 2^{n+1}−2.- Normalise a D-dimensional classical vector and use its entries as amplitudes of log₂D index qubits.
- A generic D-entry vector contains Θ(D) information and must be read/compiled unless structure or a strong oracle is available.
- Each node aggregates probability mass of its two child branches and chooses a conditional Ry angle matching their ratio.
- A multiplexed rotation whose angle depends on the computational-basis value of control qubits.
- Branch probability integrals can be computed efficiently from a succinct distribution model.
- A coherent reversible lookup circuit for a fixed classical table, with explicit gate/ancilla cost.
- Garbage entangled with the target can destroy intended interference and leave a mixed reduced state.
- It can reduce O(1/p) repeated postselection trials toward O(1/√p) coherent iterations for success probability p.
- Clifford+T hardware must approximate continuous rotations using non-Clifford resources/magic states.
- The construction and complexity of A/|b⟩/data-loading oracle, not only the downstream query count.
Sources and further study
[1] Mikko Möttönen, Juha J. Vartiainen, Ville Bergholm and Martti M. Salomaa, Transformation of quantum states using uniformly controlled rotations, Quantum Information and Computation 5, 467–473 (2005). A standard arbitrary-state synthesis construction.
[2] Lov Grover and Terry Rudolph, Creating superpositions that correspond to efficiently integrable probability distributions. A foundational structured probability-loading method.
[3] Vivek V. Shende, Stephen S. Bullock and Igor L. Markov, Synthesis of Quantum Logic Circuits, IEEE Transactions on CAD 25, 1000–1010 (2006). General circuit synthesis and lower/upper-bound context for arbitrary quantum transformations.
[4] Craig Gidney, Halving the cost of quantum addition and related fault-tolerant QROM arithmetic work. Practical reversible lookup/arithmetic techniques illustrate time–space trade-offs in compiled data access.
Continue through Quantum Mathematics
Guide 70: Quantum Hamiltonian Learning, System Identification, Bayesian Estimation and Spectroscopy asks how unknown dynamics are inferred from experiments. Guide 71: Quantum Graph Algorithms, Connectivity, Triangle Finding, Shortest Paths and Quantum-Walk Search develops graph-query algorithms. Guide 72: Quantum Reference Frames, Superselection Rules, Asymmetry and Relational Quantum States develops relational encodings and symmetry resources.