Preparing ground states of quantum many-body systems on a quantum computer

Abstract

Preparing the ground state of a system of interacting classical particles is an NP-hard problem. Thus, there is in general no better algorithm to solve this problem than exhaustively going through all N configurations of the system to determine the one with lowest energy, requiring a running time proportional to N. A quantum computer, if it could be built, could solve this problem in time sqrt(N). Here, we present a powerful extension of this result to the case of interacting quantum particles, demonstrating that a quantum computer can prepare the ground state of a quantum system as efficiently as it does for classical systems.

7 pages, 1 figure

References in corpus (2)

• N-representability is QMA-complete
• Quantum Simulations of Classical Annealing Processes

Cited by in corpus (76)

• Simulating chemistry using quantum computers
• Quantum computational finance: Monte Carlo pricing of financial derivatives
• From transistor to trapped-ion computers for quantum chemistry
• Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer
• Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
• Near-optimal ground state preparation
• A Quantum-Quantum Metropolis Algorithm
• Using Quantum Computers for Quantum Simulation
• Quantum Algorithm for Spectral Measurement with Lower Gate Count
• Time-dependent Hamiltonian simulation with $L^1$-norm scaling
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Linear Response on a Quantum Computer
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• Quantum SDP-Solvers: Better upper and lower bounds
• Variational approaches to constructing the many-body nuclear ground state for quantum computing
• Solving Quantum Ground-State Problems with Nuclear Magnetic Resonance
• Evaluating energy differences on a quantum computer with robust phase estimation
• Computing Ground State Properties with Early Fault-Tolerant Quantum Computers
• Introduction to Quantum Algorithms for Physics and Chemistry
• Grid-based methods for chemistry simulations on a quantum computer
• Dynamical critical scaling and effective thermalization in quantum quenches: the role of the initial state
• Quantum state restoration and single-copy tomography
• Quantum digital cooling
• Quantum proofs can be verified using only single qubit measurements
• On the complexity of implementing Trotter steps
• Self-healing of Trotter error in digital adiabatic state preparation
• Efficient quantum Gibbs samplers with Kubo--Martin--Schwinger detailed balance condition
• Quantum algorithms from fluctuation theorems: Thermal-state preparation
• Resource estimate for quantum many-body ground-state preparation on a quantum computer
• Quantum simulations of one dimensional quantum systems
• Nearly-optimal state preparation for quantum simulations of lattice gauge theories
• The quantum marginal problem for symmetric states: applications to variational optimization, nonlocality and self-testing
• Quantum algorithm for obtaining the eigenstates of a physical system
• State Preparation Boosters for Early Fault-Tolerant Quantum Computation
• Fault-tolerant quantum computation of molecular observables
• Dissipative Preparation of Many-Body Quantum States: Towards Practical Quantum Advantage
• Optimal scheduling in probabilistic imaginary-time evolution on a quantum computer
• Quantum Computing and Tensor Networks for Laminate Design: A Novel Approach to Stacking Sequence Retrieval
• Variational quantum algorithms for scanning the complex spectrum of non-Hermitian systems
• Randomized adaptive quantum state preparation
• Quantifying $T$-gate-count improvements for ground-state-energy estimation with near-optimal state preparation
• Using a Feedback-Based Quantum Algorithm to Analyze the Critical Properties of the ANNNI Model Without Classical Optimization
• Quantum Computed Green's Functions using a Cumulant Expansion of the Lanczos Method
• More quantum chemistry with fewer qubits
• Entanglement-assisted phase estimation algorithm for calculating dynamical response functions
• Quantum algorithms for cooling: a simple case study
• Quantum algorithm for spectral projection by measuring an ancilla iteratively
• Quantum Simulation of Simple Many-Body Dynamics
• First-quantized adiabatic time evolution for the ground state of a many-electron system and the optimal nuclear configuration
• Randomized semi-quantum matrix processing
• Exponential quantum advantages for practical non-Hermitian eigenproblems
• Quantum Zeno approach for molecular energies with maximum commuting initialHamiltonians
• Metropolis-style random sampling of quantum gates for the estimation of low-energy observables
• Quantum phase estimation based filtering: performance analysis and application to low-energy spectral calculation
• Investigation of commuting Hamiltonian in quantum Markov network
• Double-bracket algorithm for quantum signal processing without post-selection
• Quantum eigenstate broadcasting assisted by a coherent link
• Quantum eigenvalue processing
• Beating the natural Grover bound for low-energy estimation and state preparation
• Locating quantum critical points with shallow quantum circuits
• Algorithm for initializing a generalized fermionic Gaussian state on a quantum computer
• Simplified projection on total spin zero for state preparation on quantum computers
• Preparing low-variance states using a distributed quantum algorithm
• Simple and efficient end-to-end quantum thermal and ground state preparation
• Hamiltonian formulations of centroid-based clustering
• Enhancing Scalability of Quantum Eigenvalue Transformation of Unitary Matrices for Ground State Preparation through Adaptive Finer Filtering
• Efficient quantum algorithm for solving structured problems via multi-step quantum computation
• Quantum linear system algorithm with optimal queries to initial state preparation
• Noise-resilient and resource-efficient hybrid algorithm for robust quantum gap estimation
• Quantum Heaviside Eigen Solver
• Quantum Belief Propagation Algorithm versus Suzuki-Trotter approach in the one-dimensional Heisenberg chains
• Robust phase estimation of the ground-state energy without controlled time evolution on a quantum device
• Quantum Merlin-Arthur proof systems for synthesizing quantum states
• Energy Spectra of Compressed Quantum States
• Nonadiabatic Self-Healing of Trotter Errors in Digitized Counterdiabatic Dynamics
• Evolution of quantum geometric tensor of 1D periodic systems after a quench