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.

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

References in corpus (32)

• Quantum Machine Learning
• Elementary gates for quantum computation
• Quantum algorithm for solving linear systems of equations
• Surface codes: Towards practical large-scale quantum computation
• Quantum Teleportation is a Universal Computational Primitive
• Quantum principal component analysis
• Quantum random access memory
• Hamiltonian Simulation by Qubitization
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Synthesis of Quantum Logic Circuits
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Surface code quantum computing by lattice surgery
• Toward the first quantum simulation with quantum speedup
• A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
• Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
• Quantum-state preparation with universal gate decompositions
• Architectures for a quantum random access memory
• Minimal Universal Two-qubit Quantum Circuits
• Deterministic teleportation of a quantum gate between two logical qubits
• Efficient decomposition of quantum gates
• A quantum linear system algorithm for dense matrices
• Quantum Circuits for Isometries
• Hardware-efficient quantum random access memory with hybrid quantum acoustic systems
• Quantum circuits with uniformly controlled one-qubit gates
• Quantum gate teleportation between separated qubits in a trapped-ion processor
• Efficient Scheme for Initializing a Quantum Register with an Arbitrary Superposed State
• Resilience of quantum random access memory to generic noise
• An improved quantum-inspired algorithm for linear regression
• Circuit-based quantum random access memory for classical data with continuous amplitudes
• Quantum Circuits for Sparse Isometries
• Scalable and High-Fidelity Quantum Random Access Memory in Spin-Photon Networks
• Double sparse quantum state preparation

Cited by in corpus (75)

• 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 State Preparation of Normal Distributions using Matrix Product States
• 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
• 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
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
• Sparse Quantum State Preparation for Strongly Correlated Systems
• Circuit complexity of quantum access models for encoding classical data
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications
• Compact quantum algorithms for time-dependent differential equations
• 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
• Parallel Quantum Algorithm for Hamiltonian Simulation
• 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 Carleman linearisation efficiency in nonlinear fluid dynamics
• Quantum simulation of discrete linear dynamical systems and simple iterative methods in linear algebra via Schrodingerisation
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates
• QRAM: A Survey and Critique
• 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
• Quantum simulation of dissipation for Maxwell equations in dispersive media
• Quantum Pathways for Charged Track Finding in High-Energy Collisions
• Efficient fault-tolerant code switching via one-way transversal CNOT gates
• Numerical circuit synthesis and compilation for multi-state preparation
• Probabilistic state synthesis based on optimal convex approximation
• 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 circuits for partial differential equations in Fourier space
• Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs
• 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
• Quantum Software Ecosystem Design
• Non-unitary Coupled Cluster Enabled by Mid-circuit Measurements on Quantum Computers
• Multi-target quantum compilation algorithm
• 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
• Optimization Framework for Reducing Mid-circuit Measurements and Resets
• Adaptive Circuit Learning of Born Machine: Towards Realization of Amplitude Embedding and Quantum Data Loading
• Efficient Sparse State Preparation via Quantum Walks
• Topological Signal Processing on Quantum Computers for Higher-Order Network Analysis
• Dissipative ground state preparation in ab initio electronic structure theory
• Solving coupled Non-linear Schrödinger Equations via Quantum Imaginary Time Evolution
• Quantum Global Minimum Finder based on Variational Quantum Search
• A general approach to quantum integration of cross sections in high-energy physics
• Suppressing decoherence in quantum state transfer with unitary operations
• Quantum State Preparation Of Multiconfigurational States For Quantum Chemistry
• 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 Algorithms for State Preparation and Data Classification based on Stabilizer Codes
• Quantum states supported by matroids
• 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
• Optimized General Uniform Quantum State Preparation
• Hybrid Quantum-Classical Clustering for Preparing a Prior Distribution of Eigenspectrum