Source-linked AI summary
Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis
Xiaoming Sun, Guojing Tian, Shuai Yang, Pei Yuan, Shengyu Zhang
TL;DR
Quantum state preparation requires efficient circuits for important quantum algorithms, while depth–space tradeoffs remain central as qubit resources grow. This paper constructs precise, deterministic circuits that tightly characterize state-preparation complexity and extend the results to general unitary synthesis.
Problem
Efficiently preparing starting states is a challenge for quantum algorithms, and circuit depth, size, and qubit count motivate studying their tradeoffs.
Method
The paper constructs precise state-preparation circuits using arbitrary single-qubit gates and CNOT gates, with constructions adapting to available ancillary-qubit space.
Results
The constructions achieve O(2^n) size, depth O(2^n/n) without ancillas, and optimal depth bounds across the stated ancillary-qubit regimes; they also yield optimal general-unitary depth when m = O(2^n/n).
Takeaways & Limitations
The results establish tight time–space tradeoffs for quantum state preparation and provide corresponding depth bounds for general unitary synthesis.
Takeaways & Limitations
The exact constructions use arbitrary single-qubit gates and CNOT gates; approximate preparation with Clifford+T is stated only as an extension.
Abstract
from arXiv · showhide
The Quantum State Preparation problem aims to prepare an $n$-qubit quantum state $|ψ_v\rangle =\sum_{k=0}^{2^n-1}v_k|k\rangle$ from the initial state $|0\rangle^{\otimes n}$, for a given unit vector $v=(v_0,v_1,v_2,\ldots,v_{2^n-1})^T\in \mathbb{C}^{2^n}$ with $\|v\|_2 = 1$. The problem is of fundamental importance in quantum algorithm design, Hamiltonian simulation and quantum machine learning, yet its circuit depth and size complexity remain open when ancillary qubits are available. In this paper, we study efficient constructions of quantum circuits with $m$ ancillary qubits that can prepare $|ψ_v\rangle$ in depth $\tilde O\left(\frac{2^n}{m+n}+n\right)$and size $O(2^n)$, achieving the optimal value for both measures simultaneously. These results also imply a depth complexity of $Θ(4^n/(m+n))$ for quantum circuits implementing a general $n$-qubit unitary using $m = O(2^n/n)$ ancillary qubits. This resolves the depth complexity for circuits without ancillary qubits, and for circuits with exponentially many ancillary qubits, this gives a quadratic saving from $O(4^n)$ to $\tilde Θ(2^n)$. Our circuits are deterministic, prepare the state and carry out the unitary precisely, utilize the ancillary qubits tightly and the depths are optimal in a wide range of parameter regime. The results can be viewed as (optimal) time-space tradeoff bounds, which is not only theoretically interesting, but also practically relevant in the current trend that the number of qubits starts to take off, by showing a way to use a large number of qubits to compensate the short qubit lifetime.
1 Introduction
The paper studies exact quantum state preparation with ancillary qubits, characterizing optimal depth–size tradeoffs and applying them to general unitary synthesis. Its deterministic circuits achieve asymptotically optimal size and depth across broad ancillary-qubit regimes.
- Quantum state preparation is a fundamental first step for quantum algorithms, including quantum machine learning and Hamiltonian simulation.
- The circuit model uses arbitrary single-qubit gates and CNOT gates to prepare arbitrary states precisely and with certainty.
- Theorem 1 gives size O(2^n) and depth bounds that decrease as the number m of ancillary qubits increases, reaching O(n) when m = Ω(2^n).The bounds improve prior O(2^n) depth by a factor depending on m in the stated regime, while using only CNOT gates as two-qubit gates.
- Without ancillary qubits, arbitrary n-qubit states can be prepared with depth O(2^n/n) and size O(2^n).
- The upper and lower bounds establish minimum size Θ(2^n) and tightly characterize depth, with at most a logarithmic gap in a small m regime.
- The state-preparation results yield general unitary circuits of size O(4^n) and depth O(4^n/(m+n)) in the stated ancillary-qubit range.They close the previous depth gap without ancillas and extend the time–space tradeoff to unitary synthesis.
2 Preliminaries
This section establishes notation for binary-vector arithmetic, elementary quantum gates, Gray codes, and the circuit concepts used later.
- Notation: The paper uses F2 arithmetic, including bitwise XOR and inner products, to describe binary vectors and phase-control conditions.
- Elementary gates: The elementary gate set includes Y- and Z-axis rotations, phase shifts, T, S, H, and CNOT gates.
- Elementary gates: A CNOT flips its target qubit conditional on the control qubit being in state |1⟩.
- Gray code: Gray codes order all n-bit strings so adjacent strings differ in exactly one bit, forming Hamiltonian paths or cycles on the Boolean hypercube.
- Gray code: Reflected binary code is a Gray-code cycle whose bit-change frequencies can be rearranged by circularly shifting the bits.
3 Quantum state preparation with O(2n/n2) ancillary qubits
The paper builds quantum state preparation from uniformly controlled gates and reduces their implementation to diagonal unitaries, enabling depth reductions with ancillary qubits while retaining O(2^n) size.
- Quantum state preparation: State preparation uses n uniformly controlled gates V_j, each applying a single-qubit unitary conditioned on the preceding qubits.
- Quantum state preparation: The circuit depth is the sum of the depths of the uniformly controlled gates, so efficient V_j implementations determine the overall preparation depth.
- Diagonal-unitary reduction: Each uniformly controlled gate is reduced to diagonal unitary matrices and single-qubit gates, making diagonal-unitary synthesis the central subproblem.
- Diagonal-unitary reduction: Diagonal-unitary implementations use O(2^n) size with ancillary qubits and separate constructions for ranges with and without ancillas.
- Quantum state preparation: O(2^n) size and depth O(2^n/n) are obtained for state preparation without ancillary qubits, while the construction extends to ancillary-qubit regimes.
- Diagonal-unitary reduction: The method avoids sequential basis-state phase shifts by using Fourier-basis rotations and carefully structured phase-shift tasks.
4 Diagonal unitary implementation with ancillary qubits
The section implements diagonal n-qubit unitaries with ancillary qubits by parallelizing linear-function generation across copy and phase registers. Gray-code traversal reduces updates between phases, yielding depth O(log m + 2^n/m) and size O(2^n) in the stated regime.
- Framework: The framework divides ancillas into copy and phase registers to generate linear functions of the input bits in parallel.The input register holds x, while the copy register replicates input bits and the phase register stores the generated functions and applies rotations.
- Gray-code traversal: Gray-code ordering changes one suffix bit between consecutive phases, so each phase updates the previous linear functions rather than regenerating them.The Gray Path Stage uses controlled-NOT updates on the differing bit.
- Stage costs: The Gray Initial Stage has depth at most 2 log m, while the Gray Path Stage has depth at most 2 · 2^n/ℓ and size 2^(n+1).The initial stage constructs the first family of functions; subsequent phases traverse the remaining families.
- Cost and correctness: The inverse stage uncomputes copied information, completing the diagonal-unitary circuit with depth O(log m + 2^n/m).Its size is bounded by m before the full-circuit cost is combined.
- Cost and correctness: Depth O(log m + 2^n/m) and size O(2^n) implement any diagonal unitary with m ancillary qubits in the range m ∈ [2^n, 2^n/n].The construction uses single-qubit and CNOT gates.
5 Diagonal unitary implementation without ancillary qubits
Without ancillary qubits, the paper recursively implements diagonal unitaries by splitting control and target registers and enumerating suffixes in structured stages. The resulting circuit has depth O(2^n/n) and size O(2^n).
- Framework: The circuit splits the work register into approximately equal control and target registers, with r_t = floor(n/2), r_c = ceil(n/2), and ℓ ≤ 2^(r_t+2).The target register enumerates suffixes while the control register supports recursive diagonal implementation.
- Operator roles: Each G_k both applies phases and transitions between suffix-enumeration stages, while R resets the target register to the input suffix.The operators are composed recursively with the smaller diagonal unitary Λ_{r_c}.
- Operator implementation: The transition operator R is an invertible linear transformation over F2 and is implemented by a CNOT circuit without ancillas.Its depth is O(r_t/log r_t) and its size is O(r_t^2/log r_t).
- Depth and size: Any diagonal n-qubit unitary can be implemented without ancillary qubits in depth O(2^n/n) and size O(2^n).The construction recursively applies operators G_k, R, and a smaller diagonal unitary.
- Operator implementation: The Gray Path Stage realizes G_k in depth O(2^(r_c)) and size O(r_c 2^(r_c+1)) without ancillary qubits.This stage is the main cost component in the recursive construction.
6 Quantum state preparation with Ω(2n/n2) ancillary qubits
For at least Ω(2^n/n^2) ancillary qubits, the paper replaces an initial portion of standard state preparation with unary preparation followed by unary-to-binary encoding. A hybrid prefix–suffix construction achieves the stated depth ranges with size O(2^n).
- New framework: The new framework first prepares a unary-encoded state and then transforms |e_i⟩ to the binary encoding |i⟩.This replaces the first t uniformly controlled gates while retaining the standard construction for the suffix.
- Hybrid construction: The hybrid method chooses a prefix length supported by m ancillas, prepares that prefix with unary state preparation and encoding, and handles the suffix with the earlier method.This addresses the need for Θ(2^n) workspace in a full unary construction when fewer ancillas are available.
- Implementation: Unary state preparation uses depth O(n) and size O(2^n) without ancillas, while the unary-to-binary transform has depth O(n), size O(2^n), and needs 2^(t+1) ancillas.Together these stages fit within the available workspace when 2^t + 2^(t+1) ≤ m.
- Depth bounds: When m = 3 · 2^n, the depth bound becomes O(n); additional ancillas need not be used.The construction can restrict itself to 3 · 2^n ancillas when more are available.
- Depth bounds: The minimum state-preparation depth is O(2^n/m), O(n log n), or O(n) across increasing ancillary-qubit regimes, with size O(2^n).The regimes are m ∈ [Ω(2^n/n^2), O(2^n/(n log n))], m ∈ [ω(2^n/(n log n)), o(2^n)], and m = Ω(2^n), respectively.
7 Extensions and implications
The state-preparation constructions extend to general unitary synthesis and approximate Clifford+T implementations. The paper also relates the resulting depth bounds to lower bounds and states approximate versions for state preparation and unitary synthesis.
- General unitary synthesis: Any n-qubit unitary can be implemented with size O(4^n) and the paper’s ancillary-qubit-dependent depth bound.The theorem allows m ≤ 2^n ancillary qubits.
- Optimality: A parameter-counting lower bound shows that arbitrary n-qubit unitaries require Ω(4^n) CNOT gates without ancillas, supporting asymptotic optimality of the construction in the stated regime.The argument counts circuit parameters against the dimension of the set of n-qubit states.
- Approximate implementations: The Clifford+T gate set is used because it is universal for approximate implementation and its gates have fault-tolerant implementations.The paper treats this gate set separately from exact arbitrary single-qubit gates and CNOT circuits.
- Approximate implementations: The exact constructions extend to approximate implementations, including Clifford+T circuits for target states and general unitaries.The approximation notion is defined by operator action on every unit vector.
- Approximate implementations: For approximate state preparation, the Clifford+T depth includes logarithmic dependence on the inverse error and varies with the ancillary-qubit regime.The reported bounds include O(n log n log(2^n/ε)) in the intermediate regime and O(n log(2^n/ε)) when m = Ω(2^n).
8 Conclusion
The paper establishes near-optimal depth and size bounds for exact quantum state preparation with ancillary qubits, and derives corresponding unitary-synthesis results. It also identifies open directions involving connectivity, noise, and large-ancilla unitary synthesis.
- 8 Conclusion: O(2^n) size and O(n log n + 2^n) depth suffice for arbitrary exact n-qubit state preparation with m = O(2^n) ancillary qubits.The depth improves to O(n) with more ancillary qubits, and the bounds are tight up to a logarithmic factor in a small range of m.
- 8 Conclusion: The construction also reduces general-unitary circuit depth while retaining O(2^n) size, with optimality when m = O(2^n/n).The supplied conclusion states that the state-preparation results apply to general unitary synthesis and are optimal in this ancillary-qubit regime.
- 8 Conclusion: Future work includes closing the large-m unitary-synthesis gap, restricting interactions to nearest neighbors, and analyzing noise.The current framework assumes all-to-all two-qubit connectivity.
- A Circuit depth lower bound: Almost all n-qubit states require depth at least n − log n − O(1), even with arbitrary single- and double-qubit gates and unlimited ancillary qubits.The lower bound follows from parameter counting over the circuit’s light cone.
C Implementations of tasks in Eq. (5) and Eq. (6)
The implementation decomposes state-preparation tasks into diagonal-unitary transformations whose parameters are computed classically and realized through structured copy, Gray-code, and uncomputation stages. The construction uses binary trees, Walsh-Hadamard transforms, and ancillary registers to organize these operations.
- Classical parameter computation: The inverse matrix for determining α_s is 2^(1−n)(2A − J), making the parameter system efficiently solvable.The matrix A is invertible, and the resulting transform is identified with a Walsh-Hadamard transform.
- Classical parameter computation: O(n2^n) time and O(n2^n) space suffice to compute all phase parameters α_s for quantum state preparation.The parameters are obtained through a three-step procedure using binary-tree preprocessing, gate decomposition, and a fast Walsh-Hadamard transform.
- Warm-up example: Figure 9 implements Λ4 with 8 ancillary qubits using input, copy, and phase registers followed by prefix-copy, Gray-code, and inverse stages.The inverse stage restores the copy and phase registers to their initial states.
- Warm-up example: Gray-code traversal generates phase-register strings while changing one bit between adjacent strings, enabling parallel circuit construction.Two 2-bit Gray codes are used in parallel for the phase-register portions.
- General construction: For the general construction, strings are partitioned into rows sharing prefixes, with adjacent row entries differing by one bit and bounded transition multiplicity.The partition supports parallel generation of the required strings.
F Proof of Lemma 19
The inverse stage uncomputes the auxiliary registers after the preceding construction stages. Its depth and size are bounded by aggregating the corresponding CNOT operations.
- F Proof of Lemma 19: O(log m + 2^n/m) depth and m·2^n size bound the inverse stage.The depth is obtained by summing the CNOT depths of the first four stages, with size analyzed analogously.
G Proof of Lemma 20
The proof constructs a bounded collection of linearly independent Boolean-vector sets and uses them to organize the generate stage. Combining the five stages yields the operation’s overall depth and size bounds, while the circuit identities establish correctness.
- G Proof of Lemma 20: The complete operation has O(log m + 2^n/m) depth and size 3·2^n + nm + 7.The overall bounds follow by adding the depth and size contributions of the five stages.
- Construction of the generate-stage sets: A collection of at most 2^(n+2)−1 sets partitions all nonzero n-bit vectors into sets of n linearly independent vectors.This construction supplies the sets T^(1), …, T^(ℓ) used by the generate stage.
- Construction of the generate-stage sets: The covering construction starts from a set L and its one-bit neighborhoods, then extends associated vector sets to linearly independent collections.The proof uses rank properties over F2 to select independent vectors.
- Correctness: The circuit framework applies successive transformations G_k, R, and Λ_rc to produce the target operation for any input state.The proof attributes each transformation to the corresponding defining equations and disjointness properties.
J Proof of Lemma 26
Lemma 26 establishes that the Gray Path Stage is implemented correctly with depth O(2^r c) and size r c 2^r c+1. The depth analysis uses parallel CNOTs and rotations across distinct qubits.
- The Gray Path Stage UGrayPath is implemented with depth O(2^r c) and size r c 2^r c+1.The lemma states both the resource bounds and correctness of the implementation.
- Phase 1 and the final phase each require one depth because their rotations act on different target qubits.
- Each intermediate phase uses parallel CNOTs and parallel rotations, so its operations fit within constant depth per phase.Distinct control-qubit indices allow the CNOT gates in each step to run simultaneously.
K Proof of Lemma 28
The construction implements the required transformations using Toffoli and compressed-CNOT subroutines, with ancillas enabling parallel execution. It obtains O(n)-depth, O(2^n)-size implementations for the key transformations and supports general-unitary synthesis through UCG decomposition.
- CNOT cascades with one target and distinct controls compress to O(log n) depth and O(n) size without ancillas.
- The key 2^n-qubit transformation is implemented with 2^n+1 ancillas, depth O(n), and size O(2^n).Lemma 28 summarizes the resource bound for the transformation built from three steps.
- Step 2 has depth O(n) and size O(n2^(n/2)) with O(n2^(n/2)) ancillas, combining compressed CNOTs, controlled operations, and swaps.Its substeps have O(k)-depth and O(k2^k)-size implementations before substitution of the relevant parameter.
- General n-qubit unitaries are decomposed into O(2^n) UCGs, yielding an O(4^n)-size synthesis bound under the stated ancilla regime.Theorem 31 and its proof obtain the bound by sequentially implementing the UCG factors.
M Decomposition with Clifford + T gate set
The paper converts exact circuits into Clifford+T circuits by approximating single-qubit rotations and propagating the resulting error through diagonal unitaries, UCGs, state preparation, and general-unitary synthesis.
- Each single-qubit rotation is approximated with O(log(2^n/ε)) Clifford+T gates, increasing circuit depth by this multiplicative factor.The approximation allocates error ε/(c2^n) per single-qubit gate.
- The same approximation procedure extends from diagonal unitaries to UCGs, state preparation, and general unitary operations.
- Approximate diagonal unitaries use depth O(n + 2^n log(2^n/ε)/m) when m is sufficiently large, with a separate bound for smaller m.
- Approximate state preparation uses Clifford+T circuits with depth O(n log n log(2^n/ε)) to O(n log(2^n/ε)), depending on ancilla count.The smaller bound applies when m = Ω(2^n), while the intermediate regime has the additional log n factor.
- Approximate general unitaries are synthesized using the Clifford+T gate set with depth bounds inherited from the approximated UCG decomposition.The construction distributes the total error across the 2^n−1 UCG factors.
N Sparse quantum state preparation
For s-sparse states, the paper combines a sparse-support encoding with ancilla-assisted reversible mappings and parallel subroutines. The resulting depth decreases with available ancillas while retaining a no-ancilla baseline.
- The support mapping is implemented through reversible transformations that compute output bits sequentially, with each bit computation using parallelized subroutines.The construction computes all n^2 bits of the mapped strings by applying U1 through Un^2.
- A key subroutine computes each output bit in depth O(log(m)) using ancilla preparation, a reversible transformation, and ancilla restoration.
- Any n-qubit s-sparse state can be prepared with depth O(n log(sn) + s log(s)n^2/(n+m)) using m ancillas.This is the main sparse-state preparation bound.
- The construction represents the sparse state through a bijection between log(s)-bit indices and the s-element support set.
- For m < 3n, the method uses no ancillas and prepares the state in depth O(ns).