PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications

Xiao-Ming Zhang, Tongyang Li, Xiao Yuan

arXiv:2201.11495v4quant-ph

TL;DR

The paper addresses the depth and space costs of preparing arbitrary and sparse quantum states, a subroutine needed for quantum algorithms. It introduces binary-tree and memory-based constructions, obtaining optimal Θ(n) depth for arbitrary states and Θ(log(nd)) depth for d-sparse states, with applications that include Hamiltonian simulation, linear-system solving, and QRAM.

  • Problem

    Quantum state preparation has exponential depth without ancillas, while sparse-state methods previously used O(dn) depth and had unresolved depth-space tradeoffs.

  • Method

    The paper uses binary-tree circuits for arbitrary states and product-unitary and sparse Boolean memory structures for sparse-state preparation and related applications.

  • Results

    The constructions achieve Θ(n) depth for arbitrary states and Θ(log(nd)) depth for d-sparse states, with O(2^n) and O(nd log d) ancillary qubits, respectively.

  • Takeaways & Limitations

    The results provide nearly optimal space-depth scaling for sparse preparation and support applications with reported exponential circuit-depth reductions.

Abstract

from arXiv · show

Quantum state preparation is an important subroutine for quantum computing. We show that any $n$-qubit quantum state can be prepared with a $Θ(n)$-depth circuit using only single- and two-qubit gates, although with a cost of an exponential amount of ancillary qubits. On the other hand, for sparse quantum states with $d\geqslant2$ non-zero entries, we can reduce the circuit depth to $Θ(\log(nd))$ with $O(nd\log d)$ ancillary qubits. The algorithm for sparse states is exponentially faster than best-known results and the number of ancillary qubits is nearly optimal and only increases polynomially with the system size. We discuss applications of the results in different quantum computing tasks, such as Hamiltonian simulation, solving linear systems of equations, and realizing quantum random access memories, and find cases with exponential reductions of the circuit depth for all these three tasks. In particular, using our algorithm, we find a family of linear system solving problems enjoying exponential speedups, even compared to the best-known quantum and classical dequantization algorithms.

I. ARBITRARY QUANTUM STATE PREPARATION

The protocol prepares arbitrary n-qubit states using binary-tree layouts, parallel CNOT/fanout operations, and staged uncomputation. Its total depth is Θ(n), reaching the lower bound with O(2^n) ancillary qubits.

  • Algorithm: The five-stage algorithm encodes amplitudes and phases, propagates information through fanout, uncomputes H, and retains the target-state digits in V_l roots.Stages 1–2 create the encoded structure; stages 3–5 uncompute auxiliary information and leave the prepared state.
  • Depth: O(n) depth is achieved because each stage uses parallel operations across binary trees.Stage-specific analyses give O(n) depth for encoding, fanout, and uncomputation.

II. CIRCUIT DEPTH LOWER BOUND FOR SPARSE STATE PREPARATION

For d-sparse states, the paper establishes a logarithmic circuit-depth lower bound and develops memory-based constructions that target this regime. The associated space requirements remain constrained by the information needed to represent nonzero entries and indexes.

  • Lower bound: Ω(log(nd)) is a lower bound for preparing arbitrary d-sparse states with single- and two-qubit gates, even with unlimited ancillas.The proof combines GHZ-correlation requirements with parameter-counting arguments.
  • Space requirement: Ω(nd) total space is required when ancillary qubits and storage for the values and indexes of all nonzero entries are counted.Reaching the depth regime alone requires at least Ω(d−n) ancillary qubits.
  • Memory primitives: The PUM implements indexed product unitaries in O(log(nd)) depth using O(nd) ancillary qubits.It routes index, word, and pointer information through a binary-tree memory structure and applies the selected unitary locally.
  • Memory primitives: The PUM routing operation transfers an incident state to the left or right child according to the routing qubit.The router is built from controlled swaps and NOT operations, enabling reversible route-in and route-out stages.

B. Single-word sparse Boolean memory (SBM)

Single-word sparse Boolean memory uses layered index, memory, and word trees to select sparse Boolean outputs in parallel. Its circuit depth is O(log(sn)).

  • Structure: The SBM layout contains s memory trees, one for each index where the sparse Boolean function is nonzero, together with index and word trees.Memory and index trees share leaves, while the word tree connects memory-tree roots to the word register.
  • Procedure: The first SBM step fanouts the index-register state to the leaves of the index trees.This prepares parallel routing toward the memory cells associated with sparse function entries.
  • Procedure: The second step applies n-Toffoli gates, the third performs parallel CNOTs from the activated word-tree leaf, and the fourth uncomputes the cell trees.Together these steps implement the sparse Boolean lookup while restoring auxiliary structures.
  • Complexity: O(log(sn)) is the total circuit depth of single-word SBM.Steps 1 and 3 cost O(log s), step 2 costs O(log n), and step 4 costs O(log s + log n).

C. Multi-word cases for PUM and SBM

Multi-word PUM and SBM queries are parallelized by fanning out the index register, querying word-specific oracles concurrently, and uncomputing the copies. This yields logarithmic depth with ancillary-qubit costs proportional to the number of words and sparsity.

  • C. Multi-word cases for PUM and SBM: Parallel multi-word queries fan out the index register, query single-word PUM oracles concurrently, then repeat fanout for uncomputation.The same construction extends from PUM to SBM.
  • C. Multi-word cases for PUM and SBM: Each single-word PUM oracle acts on an index register I_l and a word register O_l in the multi-word decomposition.The figure caption identifies these as the index and word-register parts of select(U_l).
  • C. Multi-word cases for PUM and SBM: O(log(nd)) circuit depth and O(nd) ancillary qubits realize multi-word PUM.Fanout contributes O(log n) depth, while parallel single-word queries contribute O(log d) depth and O(nd) total ancillary qubits.
  • C. Multi-word cases for PUM and SBM: O(log(nŝn)) circuit depth and O(ns˜n) ancillary qubits realize the generalized multi-word SBM.The construction applies the same parallel-query idea when the word register has more than one qubit.

IV. HAMILTONIAN SIMULATION BASED ON QUBITIZAITON

The section combines block-encoding, state preparation, and qubitization to simulate Hamiltonian evolution. Its total depth and space depend on the costs of querying the state-preparation and select oracles.

  • IV. HAMILTONIAN SIMULATION BASED ON QUBITIZAITON: Hamiltonian simulation can be realized with block-encoding, using queries to controlled state-preparation and oracle unitaries.The simulation uses at most Θ(αt + log(1/ε)) such queries, plus additional gates and qubits.
  • IV. HAMILTONIAN SIMULATION BASED ON QUBITIZAITON: The total circuit depth and space complexity are determined by the costs of querying the state-preparation unitary G and the oracle U.The theorem follows by substituting these query costs into the block-encoding simulation result.
  • IV. HAMILTONIAN SIMULATION BASED ON QUBITIZAITON: O(log P) depth and O(P) ancillary qubits implement G, while O(log(nP)) depth and O(nP) ancillary qubits implement select(V).These constructions provide the oracle costs used in the Hamiltonian-simulation theorem.

V. PARALLEL HAMILTONIAN SIMULATION BASED ON QUANTUM WALK

This section compares a parallel quantum-walk Hamiltonian-simulation protocol with a prior method whose state-preparation depth scales as O(log^3 γ). The paper’s optimal state preparation reduces that contribution to O(log γ) without increasing space complexity.

  • V. PARALLEL HAMILTONIAN SIMULATION BASED ON QUANTUM WALK: The prior protocol uses two Hamiltonian-access oracles, a quantum state-preparation unitary, and additional single- and two-qubit gates.Its query depth depends on τlog(γ), with γ = log(τ/ε).
  • V. PARALLEL HAMILTONIAN SIMULATION BASED ON QUANTUM WALK: O(nb) and O(n) circuit depths implement the two Hamiltonian-access oracles in the Pauli-operator example.The section defines i and j as row and column indices and L(i,k) as the column index of the kth nonzero element in row i.
  • V. PARALLEL HAMILTONIAN SIMULATION BASED ON QUANTUM WALK: O(log^3 γ) state-preparation depth in the prior method is improved to O(log γ) using the paper’s optimal protocol.The stated improvement does not increase space complexity.

VI. SOLVING LINEAR SYSTEM

The linear-system section applies the paper’s state-preparation and Hamiltonian-simulation constructions to prepare H^-1|b⟩, then compares sequential, parallel, and quantum-inspired approaches. It also connects the preparation framework to continuous-amplitude QRAM.

  • VI. SOLVING LINEAR SYSTEM: The construction uses Hamiltonian simulation for evolution and sparse state preparation for the input state, with their costs combined in the linear-system procedure.The state-preparation contribution is ˜O(log(nd)κ) depth and O(ndlog d) ancillary qubits.
  • VI. SOLVING LINEAR SYSTEM: ˜O(log(nP)ακ^2 + log(nd)κ) circuit depth and O(n(P + dlog d)) qubits prepare |x⟩ proportional to H^-1|b⟩ to precision ε.Here |b⟩ is d-sparse and κ is the condition number; logarithmic dependence on κ and 1/ε is suppressed.
  • VI. SOLVING LINEAR SYSTEM: For P, α, d = O(1), the linear-system method uses ˜O(log(n)poly(κ)) circuit depth and O(n) qubits.This is the constant-sparsity specialization of the stated theorem.
  • VI. SOLVING LINEAR SYSTEM: The quantum-parallel method has ˜O(log(nP)αpoly(κ)) time and O(Ppoly(n)) space, versus quantum-sequential ˜O(nPαpoly(κ)) time and O(log P + poly(n)) space.For O(1) sparse inputs, the corresponding times are ˜O(log(n)poly(κ)) and ˜O(npoly(κ)), with O(n) space for both.
  • VI. SOLVING LINEAR SYSTEM: Continuous-amplitude QRAM generalizes binary QRAM for known classical descriptions of single-qubit states, despite the noncloning restriction on unknown quantum states.The PUM construction realizes this QRAM with O(n) circuit depth and O(N) ancillary qubits.
  • VI. SOLVING LINEAR SYSTEM: The proposed QRAM uses tree-like connectivity in which each qubit connects to no more than a constant number of other qubits.This differs from independently proposed continuous-data QRAM schemes that assume all-to-all connectivity.

A. Clifford+𝑇decomposition

The paper approximates the general state-preparation protocol with Clifford+T gates while controlling output error. The resulting depth is O(n log(n/ε)), with additional classical compilation overhead.

  • A. Clifford+T decomposition: O(log(1/ε′)) depth approximates each single-qubit y-rotation used in the partial-swap decomposition.The construction uses the {Hard, T} gate set and operator 2-norm accuracy O(ε′).
  • A. Clifford+T decomposition: ε′ = ε/(2n) bounds the accumulated first-stage error by ε/2 and yields O(n log(n/ε)) depth for the first n steps.The per-rotation depth becomes O(log(n/ε)) under this accuracy allocation.
  • A. Clifford+T decomposition: O(log(1/ε)) depth bounds the phase-gate approximation error by ε/2.An ancillary qubit is introduced so that only two controlled phase gates contribute to the error for each basis component.
  • A. Clifford+T decomposition: O(n log(n/ε)) Clifford+T depth approximates the full state-preparation algorithm to accuracy ε.The approximation combines decompositions of partial-swap and phase gates; all other stages have constant Clifford+T depth.
  • A. Clifford+T decomposition: O(N polylog(n/ε)) sequential classical runtime compiles the Clifford+T decomposition.Parallel computing reduces the compiling time to O(polylog(n/ε)) with O(N) space complexity.
  • A. Clifford+T decomposition: Ref. [23] achieves O(n + log(1/ε)) T depth with all-to-all connectivity, whereas naive FANOUT-CNOT decomposition gives quadratically higher total Clifford+T depth.The comparison concerns different gate assumptions and decomposition choices.

B. Surface code implementation with nearest-neighbor interaction

The surface-code implementation realizes the preparation protocol on a two-dimensional nearest-neighbor array using lattice-surgery CNOTs. Ancillary-qubit enlargement supports constant-depth parallel CNOT operations despite spatial separation.

  • B. Surface code implementation with nearest-neighbor interaction: Nearest-neighbor coupling on a two-dimensional physical-qubit array implements the protocol using surface-code logic qubits.Logic qubits are encoded as surfaces arranged on a board of tiles.
  • B. Surface code implementation with nearest-neighbor interaction: Stage 1 creates the H binary tree, stage 2 creates the V_l trees, and later stages measure out uncomputed qubits before encoding the target state.The layout uses ancillary-qubit paths between the tree structures.
  • B. Surface code implementation with nearest-neighbor interaction: Constant-depth lattice-surgery operations implement the CNOTs used in the protocol.The implementation uses ancillary logic qubits, joint measurements, local measurements, and corrective Pauli gates.
  • B. Surface code implementation with nearest-neighbor interaction: Constant depth is maintained for simultaneous CNOTs when ancillary-qubit enlargement and shrinking paths do not cross.The general preparation layout ensures this condition across its stages.
  • B. Surface code implementation with nearest-neighbor interaction: O(n^2N) space complexity and O(n log(n/ε)) total depth result for the nearest-neighbor implementation.The array has height O(n^2) and width O(N), while parallel CNOTs add no circuit-depth overhead.
  • B. Surface code implementation with nearest-neighbor interaction: Ancillary-qubit enlargement enables interactions between spatially separated control and target logic qubits using local stabilizer measurements.Each stabilizer remains measurable with constant local operations in the next time step.

C. Surface code implementation with nonlocal interactions

The paper also considers nonlocal interactions for surface-code implementation and sparse approximations of general states. Nonlocal CNOTs can reduce the required implementation space, while sparse approximations retain controlled fidelity and preparation cost.

  • C. Surface code implementation with nonlocal interactions: O(N) space complexity is sufficient when nonlocal CNOT implementation avoids substantial surface enlargement and shrinking.This implementation is associated with the nonlocal CNOT proposal in Ref. [41].
  • C. Surface code implementation with nonlocal interactions: The sparse approximation begins by constructing an unnormalized state from selected components of the general target state.The approximation is introduced to speed up preparation of a general quantum state.
  • C. Surface code implementation with nonlocal interactions: 1/(1−ε) normalization gives sparse-state fidelity F_sp = 1/(1−ε) |⟨ψ|ψ̃_sp⟩|^2 = 1/(1−ε).The expression follows from the normalized approximation state and its overlap with the ideal state.
  • C. Surface code implementation with nonlocal interactions: O(log(nd)) runtime and O(nd log d) ancillary qubits prepare the d-sparse approximation state.The sparse approximation is prepared using the sparse-state preparation theorem.
Loading 2201.11495v4…