Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications

Abstract

Quantum state preparation is an important subroutine for quantum computing. We show that any $n$-qubit quantum state can be prepared with a $\Theta (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⩾2$ non-zero entries, we can reduce the circuit depth to $\Theta (\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.

6+18 pages, 1+7 figures. Revise some claims in Sec. VIII A of Supplementary Material

References in corpus (9)

• Quantum algorithm for solving linear systems of equations
• Surface codes: Towards practical large-scale quantum computation
• Quantum random access memory
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Synthesis of Quantum Logic Circuits
• Quantum-state preparation with universal gate decompositions
• Architectures for a quantum random access memory
• Circuit-based quantum random access memory for classical data with continuous amplitudes
• Double sparse quantum state preparation

Cited by in corpus (74)

• Speed limits and locality in many-body quantum dynamics
• A Divide-and-Conquer Approach to Dicke State Preparation
• Short-Depth Circuits for Dicke State Preparation
• Hunting for quantum-classical crossover in condensed matter problems
• Efficient quantum amplitude encoding of polynomial functions
• Quantum Resources Required to Block-Encode a Matrix of Classical Data
• Quantum State Preparation of Normal Distributions using Matrix Product States
• Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits
• Linear-depth quantum circuits for loading Fourier approximations of arbitrary functions
• Preparing Valence-Bond-Solid states on noisy intermediate-scale quantum computers
• Nearly-optimal state preparation for quantum simulations of lattice gauge theories
• Sparse Quantum State Preparation for Strongly Correlated Systems
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
• Circuit complexity of quantum access models for encoding classical data
• Compact quantum algorithms for time-dependent differential equations
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications
• Engineering unsteerable quantum states with active feedback
• Quantum algorithms for computing observables of nonlinear partial differential equations
• Benchmarking universal quantum gates via channel spectrum
• Quantum state preparation for multivariate functions
• Exploring the optimality of approximate state preparation quantum circuits with a genetic algorithm
• A novel approach for quantum financial simulation and quantum state preparation
• Enhancing Quantum Field Theory Simulations on NISQ Devices with Hamiltonian Truncation
• Solving reaction dynamics with quantum computing algorithms
• Quantum simulation of discrete linear dynamical systems and simple iterative methods in linear algebra via Schrodingerisation
• Quantum Carleman linearisation efficiency in nonlinear fluid dynamics
• QRAM: A Survey and Critique
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates
• Quantum simulation of dissipation for Maxwell equations in dispersive media
• A Quantum Simulation Approach to Implementing Nuclear Density Functional Theory via Imaginary Time Evolution
• Quantum algorithms for matrix geometric means
• Symmetric quantum states: a review of recent progress
• Numerical circuit synthesis and compilation for multi-state preparation
• Probabilistic state synthesis based on optimal convex approximation
• Quantum Pathways for Charged Track Finding in High-Energy Collisions
• Efficient fault-tolerant code switching via one-way transversal CNOT gates
• Lower bound for simulation cost of open quantum systems: Lipschitz continuity approach
• Initial-state-dependent quantum speed limit for dissipative state preparation: Framework and optimization
• Quantum Algorithm for Estimating Betti Numbers Using Cohomology Approach
• Reducing Circuit Depth in Quantum State Preparation for Quantum Simulation Using Measurements and Feedforward
• Dictionary-based Block Encoding of Sparse Matrices with Low Subnormalization and Circuit Depth
• Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs
• Quantum circuits for partial differential equations in Fourier space
• QKAN: quantum Kolmogorov-Arnold networks with applications in machine learning and multivariate state preparation
• Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations
• Non-unitary Coupled Cluster Enabled by Mid-circuit Measurements on Quantum Computers
• Multi-target quantum compilation algorithm
• Optimization Framework for Reducing Mid-circuit Measurements and Resets
• Quantum state preparation via piecewise QSVT
• Measuring Correlation and Entanglement between Molecular Orbitals on a Trapped-Ion Quantum Computer
• Quantum Computational Insurance and Actuarial Science
• Topological Signal Processing on Quantum Computers for Higher-Order Network Analysis
• Adaptive Circuit Learning of Born Machine: Towards Realization of Amplitude Embedding and Quantum Data Loading
• Efficient Sparse State Preparation via Quantum Walks
• Quantum Software Ecosystem Design
• Solving coupled Non-linear Schrödinger Equations via Quantum Imaginary Time Evolution
• Quantum Global Minimum Finder based on Variational Quantum Search
• Dissipative ground state preparation in ab initio electronic structure theory
• A general approach to quantum integration of cross sections in high-energy physics
• Quantum State Preparation Of Multiconfigurational States For Quantum Chemistry
• Suppressing decoherence in quantum state transfer with unitary operations
• Three-Qubit State Preparation: Classification and Explicit Circuits
• Gravitational-wave matched filtering on a quantum computer
• Quantum data generation in a denoising model with multiscale entanglement renormalization network
• Matrix-product entanglement characterizing the optimality of state-preparation quantum circuits
• Quantum states supported by matroids
• Optimized General Uniform Quantum State Preparation
• Block Encoding of Sparse Matrices via Coherent Permutation
• Nonlinear path-following via the asymptotic numerical method on a quantum processor
• Quantum algorithm for anisotropic diffusion and convection equations with vector norm scaling
• Quantum Encoding of Structured Data with Matrix Product States
• Quantum Simulation-Based Optimization for Cooling System Design
• Hybrid Quantum-Classical Clustering for Preparing a Prior Distribution of Eigenspectrum
• Quantum Algorithms for State Preparation and Data Classification based on Stabilizer Codes