High-precision and low-depth quantum algorithm design for eigenstate problems
arXiv:2406.04307 · doi:10.1126/sciadv.aeb1622
Abstract
Estimating the eigenstate properties of quantum systems is a long-standing, challenging problem for both classical and quantum computing. Existing universal quantum algorithms typically rely on ideal and efficient query models (e.g. time evolution operator or block encoding of the Hamiltonian), which, however, become suboptimal for actual implementation at the quantum circuit level. Here, we present a full-stack design of quantum algorithms for estimating the eigenenergy and eigenstate properties, which can achieve high precision and good scaling with system size. The gate complexity per circuit for estimating generic Hamiltonians' eigenstate properties is , which has a logarithmic dependence on the inverse precision . For lattice Hamiltonians, the circuit depth of our design achieves near-optimal system-size scaling, even with local qubit connectivity. Our full-stack algorithm has low overhead in circuit compilation, which thus results in a small actual gate count (CNOT and non-Clifford gates) for lattice and molecular problems compared to advanced eigenstate algorithms. The algorithm is implemented on IBM quantum devices using up to 2,000 two-qubit gates and 20,000 single-qubit gates, and achieves high-precision eigenenergy estimation for Heisenberg-type Hamiltonians, demonstrating its noise robustness.
52 pages, 11 figures, and 5 tables
References in corpus (58)
- Noisy intermediate-scale quantum (NISQ) algorithms
- Hamiltonian Simulation by Qubitization
- Quantum algorithms for quantum chemistry and quantum materials science
- Elucidating Reaction Mechanisms on Quantum Computers
- Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution
- Entanglement-free Heisenberg-limited phase estimation
- 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
- A random compiler for fast Hamiltonian simulation
- Gate count estimates for performing quantum chemistry on small quantum computers
- Even more efficient quantum computations of chemistry through tensor hypercontraction
- Quantum computing enhanced computational catalysis
- Is there evidence for exponential quantum advantage in quantum chemistry?
- Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization
- Unbiasing Fermionic Quantum Monte Carlo with a Quantum Computer
- Optimal Quantum Measurements of Expectation Values of Observables
- On the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization
- Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
- Near-optimal ground state preparation
- Faster quantum simulation by randomization
- Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization
- Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices
- Efficient synthesis of universal Repeat-Until-Success circuits
- Reliably assessing the electronic structure of cytochrome P450 on today's classical computers and tomorrow's quantum computers
- Quantum algorithm for simulating real time evolution of lattice Hamiltonians
- Algorithms for quantum simulation at finite energies
- Quantum Krylov subspace algorithms for ground and excited state energy estimation
- Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
- Observing ground-state properties of the Fermi-Hubbard model using a scalable algorithm on a quantum computer
- Fault-tolerant resource estimate for quantum chemical simulations: Case study on Li-ion battery electrolyte molecules
- Early Fault-Tolerant Quantum Computing
- A randomized quantum algorithm for statistical phase estimation
- Even shorter quantum circuit for phase estimation on early fault-tolerant quantum computers with applications to ground-state energy estimation
- Linear combination of Hamiltonian simulation for nonunitary dynamics with optimal state preparation cost
- Error mitigation via verified phase estimation
- Quantum algorithm for ground state energy estimation using circuit depth with exponentially improved dependence on precision
- Single-ancilla ground state preparation via Lindbladians
- Nearly tight Trotterization of interacting electrons
- Computing Ground State Properties with Early Fault-Tolerant Quantum Computers
- Reducing the quantum computing overhead with complex gate distillation
- An efficient magic state approach to small angle rotations
- Rapid initial state preparation for the quantum simulation of strongly correlated molecules
- Accelerated quantum Monte Carlo with mitigated error on noisy quantum computer
- Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
- Self-healing of Trotter error in digital adiabatic state preparation
- Error-resilient Monte Carlo quantum simulation of imaginary time
- Diagonalization of large many-body Hamiltonians on a quantum processor
- Quantum Multiple Eigenvalue Gaussian filtered Search: an efficient and versatile quantum phase estimation method
- Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
- Improved Accuracy for Trotter Simulations Using Chebyshev Interpolation
- Rapid quantum ground state preparation via dissipative dynamics
- Quantum Gaussian filter for exploring ground-state properties
- Simple and high-precision Hamiltonian simulation by compensating Trotter error with linear combination of unitary operations
- Quantum Routing with Teleportation
- Early Fault-Tolerant Quantum Algorithms in Practice: Application to Ground-State Energy Estimation
- Exploring Ground States of Fermi-Hubbard Model on Honeycomb Lattices with Counterdiabaticity
- Escaping Local Minima with Quantum Coherent Cooling