Spacetime-Efficient Low-Depth Quantum State Preparation with Applications

Abstract

We propose a novel deterministic method for preparing arbitrary quantum states. When our protocol is compiled into CNOT and arbitrary single-qubit gates, it prepares an $N$-dimensional state in depth $O(\log (N))$ and spacetime allocation (a metric that accounts for the fact that oftentimes some ancilla qubits need not be active for the entire circuit) $O(N)$, which are both optimal. When compiled into the $\{\mathrm{H},\mathrm{S},\mathrm{T},\mathrm{CNOT}\}$ gate set, we show that it requires asymptotically fewer quantum resources than previous methods. Specifically, it prepares an arbitrary state up to error $\epsilon$ with optimal depth of $O(\log (N)+\log (1/\epsilon ))$ and spacetime allocation $O(N\log (\log (N)/\epsilon ))$, improving over $O(\log (N)\log (\log (N)/\epsilon ))$ and $O(N\log (N/\epsilon ))$, respectively. We illustrate how the reduced spacetime allocation of our protocol enables rapid preparation of many disjoint states with only constant-factor ancilla overhead -- $O(N)$ ancilla qubits are reused efficiently to prepare a product state of $w$ $N$-dimensional states in depth $O(w+\log (N))$ rather than $O(w\log (N))$, achieving effectively constant depth per state. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations. We provide quantum circuit descriptions of our protocol, detailed pseudocode, and gate-level implementation examples using Braket.

References in corpus (28)

• An overview of gradient descent optimization algorithms
• Quantum Machine Learning
• Quantum algorithm for solving linear systems of equations
• Quantum support vector machine for big data classification
• Quantum principal component analysis
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Toward the first quantum simulation with quantum speedup
• Quantum advantage in learning from experiments
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Quantum-state preparation with universal gate decompositions
• A quantum linear system algorithm for dense matrices
• Quantum algorithms and the finite element method
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• A divide-and-conquer algorithm for quantum state preparation
• Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications
• Quantum singular value decomposition of non-sparse low-rank matrices
• The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
• Quantum simulation of electronic structure with a transcorrelated Hamiltonian: improved accuracy with a smaller footprint on the quantum computer
• Quantum Spectral Clustering
• Quantum Resources Required to Block-Encode a Matrix of Classical Data
• Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits
• SQUARE: Strategic Quantum Ancilla Reuse for Modular Quantum Programs via Cost-Effective Uncomputation
• Improving the accuracy of quantum computational chemistry using the transcorrelated method
• End-to-end resource analysis for quantum interior point methods and portfolio optimization

Cited by in corpus (10)

• Trading T gates for dirty qubits in state preparation and unitary synthesis
• Simulating unsteady fluid flows on a superconducting quantum processor
• Primitive Quantum Gates for an SU(3) Discrete Subgroup: $\Sigma (36\times 3)$
• Circuit complexity of quantum access models for encoding classical data
• Multireference error mitigation for quantum computation of chemistry
• Quantum Multiplexer Simplification for State Preparation
• Efficient Sparse State Preparation via Quantum Walks
• Robust and optimal loading of general classical data into quantum computers
• Comment on arXiv:2307.08384 "Efficient Quantum State Preparation with Walsh Series"
• Quantum Encoding of Structured Data with Matrix Product States