Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices

Abstract

Under suitable assumptions, the algorithms in [Lin, Tong, Quantum 2020] can estimate the ground state energy and prepare the ground state of a quantum Hamiltonian with near-optimal query complexities. However, this is based on a block encoding input model of the Hamiltonian, whose implementation is known to require a large resource overhead. We develop a tool called quantum eigenvalue transformation of unitary matrices with real polynomials (QET-U), which uses a controlled Hamiltonian evolution as the input model, a single ancilla qubit and no multi-qubit control operations, and is thus suitable for early fault-tolerant quantum devices. This leads to a simple quantum algorithm that outperforms all previous algorithms with a comparable circuit structure for estimating the ground state energy. For a class of quantum spin Hamiltonians, we propose a new method that exploits certain anti-commutation relations and further removes the need of implementing the controlled Hamiltonian evolution. Coupled with Trotter based approximation of the Hamiltonian evolution, the resulting algorithm can be very suitable for early fault-tolerant quantum devices. We demonstrate the performance of the algorithm using IBM Qiskit for the transverse field Ising model. If we are further allowed to use multi-qubit Toffoli gates, we can then implement amplitude amplification and a new binary amplitude estimation algorithm, which increases the circuit depth but decreases the total query complexity. The resulting algorithm saturates the near-optimal complexity for ground state preparation and energy estimating using a constant number of ancilla qubits (no more than 3).

References in corpus (12)

• Entanglement-free Heisenberg-limited phase estimation
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Quantum computing enhanced computational catalysis
• General optimality of the Heisenberg limit for quantum metrology
• The power of quantum systems on a line
• Optimal Quantum Measurements of Expectation Values of Observables
• Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
• Focus beyond quadratic speedups for error-corrected quantum advantage
• Rodeo Algorithm for Quantum Computing
• Early fault-tolerant simulations of the Hubbard model
• Fast-forwarding quantum evolution
• Exploiting fermion number in factorized decompositions of the electronic structure Hamiltonian

Cited by in corpus (90)

• Early Fault-Tolerant Quantum Computing
• 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
• Linear combination of Hamiltonian simulation for nonunitary dynamics with optimal state preparation cost
• Quantum algorithm for ground state energy estimation using circuit depth with exponentially improved dependence on precision
• Single-ancilla ground state preparation via Lindbladians
• Grid-based methods for chemistry simulations on a quantum computer
• Initial state preparation for quantum chemistry on quantum computers
• On low-depth algorithms for quantum phase estimation
• Simultaneous estimation of multiple eigenvalues with short-depth quantum circuit on early fault-tolerant quantum computers
• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
• Real-Time Krylov Theory for Quantum Computing Algorithms
• Rapid initial state preparation for the quantum simulation of strongly correlated molecules
• On the complexity of implementing Trotter steps
• Quantum Phase Processing and its Applications in Estimating Phase and Entropies
• Projection algorithm for state preparation on quantum computers
• Hybrid Oscillator-Qubit Quantum Processors: Instruction Set Architectures, Abstract Machine Models, and Applications
• Diagonalization of large many-body Hamiltonians on a quantum processor
• Nearly-optimal state preparation for quantum simulations of lattice gauge theories
• Quantum Multiple Eigenvalue Gaussian filtered Search: an efficient and versatile quantum phase estimation method
• Hierarchical Clifford transformations to reduce entanglement in quantum chemistry wavefunctions
• Derivative Pricing using Quantum Signal Processing
• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Fault-tolerant quantum computation of molecular observables
• Infinite quantum signal processing
• Analysis of quantum Krylov algorithms with errors
• Quantum algorithm for the advection-diffusion equation and the Koopman-von Neumann approach to nonlinear dynamical systems
• Dissipative Preparation of Many-Body Quantum States: Towards Practical Quantum Advantage
• 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
• Counterdiabatic optimized driving in quantum phase sensitive models
• Spin coupling is all you need: Encoding strong electron correlation in molecules on quantum computers
• Quantum error mitigation for Fourier moment computation
• Early Fault-Tolerant Quantum Algorithms in Practice: Application to Ground-State Energy Estimation
• On proving the robustness of algorithms for early fault-tolerant quantum computers
• Probing spectral features of quantum many-body systems with quantum simulators
• Partonic distribution functions and amplitudes using tensor network methods
• Multi-nucleon structure and dynamics via quantum computing
• Solving reaction dynamics with quantum computing algorithms
• Toward hybrid quantum simulations with qubits and qumodes on trapped-ion platforms
• Accelerating quantum imaginary-time evolution with random measurements
• Double-bracket quantum algorithms for quantum imaginary-time evolution
• A Comprehensive Cross-Model Framework for Benchmarking the Performance of Quantum Hamiltonian Simulations
• Halving the Cost of Quantum Algorithms with Randomization
• Entanglement-assisted phase estimation algorithm for calculating dynamical response functions
• Block encoding bosons by signal processing
• Efficient ground-state energy estimation and certification on early fault-tolerant quantum computers
• Near-term quantum algorithm for computing molecular and materials properties based on recursive variational series methods
• Solving lattice gauge theories using the quantum Krylov algorithm and qubitization
• Accelerating two-dimensional electronic spectroscopy simulations with a probe qubit protocol
• Quantum computing quantum Monte Carlo algorithm
• Randomized semi-quantum matrix processing
• Exponential quantum advantages for practical non-Hermitian eigenproblems
• Encoded probabilistic imaginary-time evolution on a trapped-ion quantum computer for ground and excited states of spin qubits
• Quantum Dissipative Search via Lindbladians
• Adaptive measurement strategy for noisy quantum amplitude estimation with variational quantum circuits
• Encoding of linear kinetic plasma problems in quantum circuits via data compression
• Error mitigation and circuit division for early fault-tolerant quantum phase estimation
• Noise-aware variational eigensolvers: a dissipative route for lattice gauge theories
• Reducing Circuit Depth in Quantum State Preparation for Quantum Simulation Using Measurements and Feedforward
• Quantum phase estimation based filtering: performance analysis and application to low-energy spectral calculation
• Quantum eigenvalue processing
• Hardware-efficient quantum phase estimation via local control
• Double-bracket algorithm for quantum signal processing without post-selection
• Channel-based framework for phase esimation of multiple eigenvalues
• Simplified projection on total spin zero for state preparation on quantum computers
• High-precision and low-depth quantum algorithm design for eigenstate problems
• Optimization Framework for Reducing Mid-circuit Measurements and Resets
• Toward scalable quantum computations of atomic nuclei
• Elucidating Many-Body Effects in Molecular Core Spectra through Real-Time Approaches: Efficient Classical Approximations and a Quantum Perspective
• Phase Estimation with Compressed Controlled Time Evolution
• Towards Practical Quantum Phase Estimation: A Modular, Scalable, and Adaptive Approach
• Enhancing Scalability of Quantum Eigenvalue Transformation of Unitary Matrices for Ground State Preparation through Adaptive Finer Filtering
• Beyond asymptotic reasoning: the practicalities of a quantum ground state projector based on the wall-Chebyshev expansion
• Hamiltonian formulations of centroid-based clustering
• Bosonic Entanglement and Quantum Sensing from Energy Transfer in two-tone Floquet Systems
• Generalized Parity Measurements and Efficient Large Multi-component Cat State Preparation with Quantum Signal Processing
• Energy Spectra of Compressed Quantum States
• Quantum Simulation via Stochastic Combination of Unitaries
• Quantum Imaginary-Time Evolution with Polynomial Resources in Evolution Time
• Numerical investigation of the quantum inverse algorithm on small molecules
• Quantum Signal Processing and Quantum Singular Value Transformation on $U(N)$
• Unleashing Optimizations in Dynamic Circuits through Branch Expansion
• Gate Efficient Composition of Hamiltonian Simulation and Block-Encoding with its Application on HUBO, Chemistry and Finite Difference Method
• An adversary bound for quantum signal processing
• Accelerated spin-adapted ground state preparation with non-variational quantum algorithms
• Double-bracket quantum algorithms for high-fidelity ground state preparation
• Quantum Encoding of Structured Data with Matrix Product States