Near-optimal ground state preparation

Abstract

Preparing the ground state of a given Hamiltonian and estimating its ground energy are important but computationally hard tasks. However, given some additional information, these problems can be solved efficiently on a quantum computer. We assume that an initial state with non-trivial overlap with the ground state can be efficiently prepared, and the spectral gap between the ground energy and the first excited energy is bounded from below. With these assumptions we design an algorithm that prepares the ground state when an upper bound of the ground energy is known, whose runtime has a logarithmic dependence on the inverse error. When such an upper bound is not known, we propose a hybrid quantum-classical algorithm to estimate the ground energy, where the dependence of the number of queries to the initial state on the desired precision is exponentially improved compared to the current state-of-the-art algorithm proposed in [Ge et al. 2019]. These two algorithms can then be combined to prepare a ground state without knowing an upper bound of the ground energy. We also prove that our algorithms reach the complexity lower bounds by applying it to the unstructured search problem and the quantum approximate counting problem.

References in corpus (25)

• A variational eigenvalue solver on a quantum processor
• Strengths and Weaknesses of Quantum Computing
• Quantum Amplitude Amplification and Estimation
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Toward the first quantum simulation with quantum speedup
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Quantum Simulation of Electronic Structure with Linear Depth and Connectivity
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Undecidability of the Spectral Gap (short version)
• Low Depth Quantum Simulation of Electronic Structure
• The power of quantum systems on a line
• Quantum algorithms to simulate many-body physics of correlated fermions
• The methodology of resonant equiangular composite quantum gates
• Preparing ground states of quantum many-body systems on a quantum computer
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Quantum search by measurement
• Product Decomposition of Periodic Functions in Quantum Signal Processing
• Black-box Hamiltonian simulation and unitary implementation
• Finding Angles for Quantum Signal Processing with Machine Precision
• Undecidability of the Spectral Gap in One Dimension
• A Lower Bound for Quantum Phase Estimation

Cited by in corpus (124)

• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
• Standard Model Physics and the Digital Quantum Revolution: Thoughts about the Interface
• Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices
• Drug design on quantum computers
• Algorithms for quantum simulation at finite energies
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• Even shorter quantum circuit for phase estimation on early fault-tolerant quantum computers with applications to ground-state energy estimation
• Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
• Exact and efficient Lanczos method on a quantum computer
• Variational approaches to constructing the many-body nuclear ground state for quantum computing
• Quadratic speedup for spatial search by continuous-time quantum walk
• Single-ancilla ground state preparation via Lindbladians
• Nearly tight Trotterization of interacting electrons
• Evaluating energy differences on a quantum computer with robust phase estimation
• On the energy landscape of symmetric quantum signal processing
• Simulating key properties of lithium-ion batteries with a fault-tolerant quantum computer
• Efficient quantum computation of molecular forces and other energy gradients
• Computing Ground State Properties with Early Fault-Tolerant Quantum Computers
• Initial state preparation for quantum chemistry on quantum computers
• Grid-based methods for chemistry simulations on a quantum computer
• Nearly Optimal Quantum Algorithm for Estimating Multiple Expectation Values
• Quantum simulation of partial differential equations via Schrodingerisation
• On low-depth algorithms for quantum phase estimation
• Imaginary Time Propagation on a Quantum Chip
• Heisenberg-limited quantum phase estimation of multiple eigenvalues with few control qubits
• Quantum digital cooling
• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
• Rapid initial state preparation for the quantum simulation of strongly correlated molecules
• On the complexity of implementing Trotter steps
• Self-healing of Trotter error in digital adiabatic state preparation
• Quantum Phase Processing and its Applications in Estimating Phase and Entropies
• Amplitude Estimation from Quantum Signal Processing
• A quantum hamiltonian simulation benchmark
• Nearly-optimal state preparation for quantum simulations of lattice gauge theories
• Quantum Regularized Least Squares
• Quantum Multiple Eigenvalue Gaussian filtered Search: an efficient and versatile quantum phase estimation method
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
• Perturbation theory with quantum signal processing
• Exponential improvements in the simulation of lattice gauge theories using near-optimal techniques
• State Preparation Boosters for Early Fault-Tolerant Quantum Computation
• Efficient quantum imaginary time evolution by drifting real time evolution: an approach with low gate and measurement complexity
• Hierarchical Clifford transformations to reduce entanglement in quantum chemistry wavefunctions
• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Optimizing the information extracted by a single qubit measurement
• Fault-tolerant quantum computation of molecular observables
• Rapid quantum ground state preparation via dissipative dynamics
• Infinite quantum signal processing
• Double-bracket quantum algorithms for diagonalization
• Optimal scheduling in probabilistic imaginary-time evolution on a quantum computer
• Efficient Quantum Simulation of QCD Jets on the Light Front
• Exponentially faster implementations of Select(H) for fermionic Hamiltonians
• Success of digital adiabatic simulation with large Trotter step
• Tailored and Externally Corrected Coupled Cluster with Quantum Inputs
• Spin coupling is all you need: Encoding strong electron correlation in molecules on quantum computers
• Simple and high-precision Hamiltonian simulation by compensating Trotter error with linear combination of unitary operations
• Quantifying $T$-gate-count improvements for ground-state-energy estimation with near-optimal state preparation
• Beyond MP2 initialization for unitary coupled cluster quantum circuits
• Sequential optimal selection of a single-qubit gate and its relation to barren plateau in parameterized quantum circuits
• Convex Optimization for Nonequilibrium Steady States on a Hybrid Quantum Processor
• Partonic distribution functions and amplitudes using tensor network methods
• Quantum Computed Green's Functions using a Cumulant Expansion of the Lanczos Method
• Multi-nucleon structure and dynamics via quantum computing
• TFermion: A non-Clifford gate cost assessment library of quantum phase estimation algorithms for quantum chemistry
• Using a Feedback-Based Quantum Algorithm to Analyze the Critical Properties of the ANNNI Model Without Classical Optimization
• Quantum simulation of discrete linear dynamical systems and simple iterative methods in linear algebra via Schrodingerisation
• Accelerating quantum imaginary-time evolution with random measurements
• More quantum chemistry with fewer qubits
• Solving the Hele-Shaw flow using the Harrow-Hassidim-Lloyd algorithm on superconducting devices: A study of efficiency and challenges
• Quantum algorithms for cooling: a simple case study
• Double-bracket quantum algorithms for quantum imaginary-time evolution
• Halving the Cost of Quantum Algorithms with Randomization
• Entanglement-assisted phase estimation algorithm for calculating dynamical response functions
• Improved precision scaling for simulating coupled quantum-classical dynamics
• Automatic Post-selection by Ancillae Thermalisation
• Efficient ground-state energy estimation and certification on early fault-tolerant quantum computers
• Quantum search in many-body interacting system with long-range interaction
• First-quantized adiabatic time evolution for the ground state of a many-electron system and the optimal nuclear configuration
• Randomized semi-quantum matrix processing
• Nearly-frustration-free ground state preparation
• Exponential quantum advantages for practical non-Hermitian eigenproblems
• Quantum computing quantum Monte Carlo algorithm
• Error mitigation and circuit division for early fault-tolerant quantum phase estimation
• Metropolis-style random sampling of quantum gates for the estimation of low-energy observables
• Adaptive measurement strategy for noisy quantum amplitude estimation with variational quantum circuits
• Quantum phase estimation based filtering: performance analysis and application to low-energy spectral calculation
• Improved quantum algorithm for calculating eigenvalues of differential operators and its application to estimating the decay rate of the perturbation distribution tail in stochastic inflation
• Double-bracket algorithm for quantum signal processing without post-selection
• Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation
• Lower Bounds for Unitary Property Testing with Proofs and Advice
• Some Error Analysis for the Quantum Phase Estimation Algorithms
• Quantum eigenvalue processing
• Semicoherent Symmetric Quantum Processes: Theory and Applications
• Simplifying a classical-quantum algorithm interpolation with quantum singular value transformations
• Exponential distillation of dominant eigenproperties
• Quantum Lower Bounds by Sample-to-Query Lifting
• Identification of a natural fieldlike entanglement resource in trapped-ion chains
• Faster quantum mixing of Markov chains in non-regular graph with fewer qubits
• High-precision and low-depth quantum algorithm design for eigenstate problems
• Beating the natural Grover bound for low-energy estimation and state preparation
• Unstructured Adiabatic Quantum Optimization: Optimality with Limitations
• Scalable Quantum Computational Science: A Perspective from Block-Encodings and Polynomial Transformations
• Dissipative ground state preparation in ab initio electronic structure theory
• Quantum linear system algorithm with optimal queries to initial state preparation
• Hamiltonian formulations of centroid-based clustering
• Calculating potential energy surfaces with quantum computers by measuring only the density along adiabatic transitions
• Enhancing Scalability of Quantum Eigenvalue Transformation of Unitary Matrices for Ground State Preparation through Adaptive Finer Filtering
• Towards Practical Quantum Phase Estimation: A Modular, Scalable, and Adaptive Approach
• Optimizing Quantum Chemistry Simulations with a Hybrid Quantization Scheme
• Beyond asymptotic reasoning: the practicalities of a quantum ground state projector based on the wall-Chebyshev expansion
• Simple and efficient end-to-end quantum thermal and ground state preparation
• Feasibility of performing quantum chemistry calculations on quantum computers
• Numerical investigation of the quantum inverse algorithm on small molecules
• Evolution of quantum geometric tensor of 1D periodic systems after a quench
• Energy Spectra of Compressed Quantum States
• Nonadiabatic Self-Healing of Trotter Errors in Digitized Counterdiabatic Dynamics
• Robust phase estimation of the ground-state energy without controlled time evolution on a quantum device
• Co-Designing Spectral Transformation Oracles with Hybrid Oscillator-Qubit Quantum Processors: From Algorithms to Compilation
• A penalty-free quantum algorithm to find energy eigenstates
• Deterministic Ground State Preparation via Power-Cosine Filtering of Time Evolution Operators
• Double-bracket quantum algorithms for high-fidelity ground state preparation
• Explicit decoders using fixed-point amplitude amplification based on QSVT
• Operator-Level Quantum Acceleration of Non-Logconcave Sampling
• Robust and optimal loading of general classical data into quantum computers