Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
arXiv:2102.11340 · doi:10.1103/PRXQuantum.3.010318
Abstract
Under suitable assumptions, the quantum phase estimation (QPE) algorithm is able to achieve Heisenberg-limited precision scaling in estimating the ground state energy. However, QPE requires a large number of ancilla qubits and large circuit depth, as well as the ability to perform inverse quantum Fourier transform, making it expensive to implement on an early fault-tolerant quantum computer. We propose an alternative method to estimate the ground state energy of a Hamiltonian with Heisenberg-limited precision scaling, which employs a simple quantum circuit with one ancilla qubit, and a classical post-processing procedure. Besides the ground state energy, our algorithm also produces an approximate cumulative distribution function of the spectral measure, which can be used to compute other spectral properties of the Hamiltonian.
References in corpus (14)
- Entanglement-free Heisenberg-limited phase estimation
- 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
- Chemical Basis of Trotter-Suzuki Errors in Quantum Chemistry Simulation
- Near-optimal ground state preparation
- Focus beyond quadratic speedups for error-corrected quantum advantage
- Algorithms for quantum simulation at finite energies
- Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
- Early fault-tolerant simulations of the Hubbard model
- Parameter Estimation with Mixed-State Quantum Computation
- First-Order Trotter Error from a Second-Order Perspective
- Quantum-accelerated constraint programming
- Spectral Analysis of Product Formulas for Quantum Simulation
Cited by in corpus (121)
- Is there evidence for exponential quantum advantage in quantum chemistry?
- A perspective on the current state-of-the-art of quantum computing for drug discovery applications
- Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices
- 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
- Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
- Exact and efficient Lanczos method on a quantum computer
- Quantum algorithm for ground state energy estimation using circuit depth with exponentially improved dependence on precision
- Single-ancilla ground state preparation via Lindbladians
- Computing Ground State Properties with Early Fault-Tolerant Quantum Computers
- Initial state preparation for quantum chemistry on quantum computers
- On low-depth algorithms for quantum phase estimation
- Demonstrating Bayesian Quantum Phase Estimation with Quantum Error Detection
- Simultaneous estimation of multiple eigenvalues with short-depth quantum circuit on early fault-tolerant quantum computers
- Heisenberg-limited quantum phase estimation of multiple eigenvalues with few control qubits
- Real-Time Krylov Theory for Quantum Computing Algorithms
- 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
- Quantum Phase Processing and its Applications in Estimating Phase and Entropies
- Measuring the Loschmidt amplitude for finite-energy properties of the Fermi-Hubbard model on an ion-trap quantum computer
- Quantum algorithms from fluctuation theorems: Thermal-state preparation
- Noise-resilient phase estimation with randomized compiling
- Statistical phase estimation and error mitigation on a superconducting quantum processor
- Nearly-optimal state preparation for quantum simulations of lattice gauge theories
- 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
- Quantum simulations of Fermionic Hamiltonians with efficient encoding and ansatz schemes
- Perturbation theory with quantum signal processing
- Quantum simulation of battery materials using ionic pseudopotentials
- Exploiting fermion number in factorized decompositions of the electronic structure Hamiltonian
- Non-asymptotic Heisenberg scaling: experimental metrology for a wide resources range
- State Preparation Boosters for Early Fault-Tolerant Quantum Computation
- The advantage of quantum control in many-body Hamiltonian learning
- Fault-tolerant quantum algorithms for quantum molecular systems: A survey
- Quantum algorithms for scientific computing
- Local minima in quantum systems
- Nuclear scattering via quantum computing
- Rapid quantum ground state preparation via dissipative dynamics
- Analysis of quantum Krylov algorithms with errors
- 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
- Phase-Sensitive Quantum Measurement without Controlled Operations
- Counterdiabatic optimized driving in quantum phase sensitive models
- Efficient Quantum Simulation of QCD Jets on the Light Front
- Algorithmic Shadow Spectroscopy
- High ground state overlap via quantum embedding methods
- Spin coupling is all you need: Encoding strong electron correlation in molecules on quantum computers
- Quantum error mitigation for Fourier moment computation
- Modeling the Performance of Early Fault-Tolerant Quantum Algorithms
- Quantifying -gate-count improvements for ground-state-energy estimation with near-optimal state preparation
- Simple and high-precision Hamiltonian simulation by compensating Trotter error with linear combination of unitary operations
- Compilation of a simple chemistry application to quantum error correction primitives
- Sequential optimal selection of a single-qubit gate and its relation to barren plateau in parameterized quantum circuits
- Spectral estimation for Hamiltonians: a comparison between classical imaginary-time evolution and quantum real-time evolution
- Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters
- On proving the robustness of algorithms for early fault-tolerant quantum computers
- Early Fault-Tolerant Quantum Algorithms in Practice: Application to Ground-State Energy Estimation
- Computation of Green's function by local variational quantum compilation
- Probing spectral features of quantum many-body systems with quantum simulators
- Virtual quantum error detection
- Solving the Hele-Shaw flow using the Harrow-Hassidim-Lloyd algorithm on superconducting devices: A study of efficiency and challenges
- In the shadow of the Hadamard test: Using the garbage state for good and further modifications
- Halving the Cost of Quantum Algorithms with Randomization
- Quantum Algorithm For Estimating Eigenvalue
- Double-bracket quantum algorithms for quantum imaginary-time evolution
- Unlocking early fault-tolerant quantum computing with mitigated magic dilution
- Efficient ground-state energy estimation and certification on early fault-tolerant quantum computers
- TE-PAI: Exact Time Evolution by Sampling Random Circuits
- First-quantized adiabatic time evolution for the ground state of a many-electron system and the optimal nuclear configuration
- Quantum computing quantum Monte Carlo algorithm
- Accelerating two-dimensional electronic spectroscopy simulations with a probe qubit protocol
- Iteration Complexity of Variational Quantum Algorithms
- Molecular Properties from Quantum Krylov Subspace Diagonalization
- Randomized semi-quantum matrix processing
- Statistics of topological defects across a phase transition in a digital superconducting quantum processor
- LSQCA: Resource-Efficient Load/Store Architecture for Limited-Scale Fault-Tolerant Quantum Computing
- Error mitigation and circuit division for early fault-tolerant quantum phase estimation
- Subspace-Based Local Compilation of Variational Quantum Circuits for Large-Scale Quantum Many-Body Simulation
- Encoded probabilistic imaginary-time evolution on a trapped-ion quantum computer for ground and excited states of spin qubits
- Quantum Phase Estimation by Compressed Sensing
- Experimental demonstration of optimal measurement for unambiguously discriminating asymmetric qudit states
- Quantum eigenvalue processing
- Double-bracket algorithm for quantum signal processing without post-selection
- Faster Coherent Quantum Algorithms for Phase, Energy, and Amplitude Estimation
- Hardware-efficient quantum phase estimation via local control
- Nonlinear Spectroscopy via Generalized Quantum Phase Estimation
- Heisenberg-limited adaptive gradient estimation for multiple observables
- Some Error Analysis for the Quantum Phase Estimation Algorithms
- Chemically Motivated Simulation Problems are Efficiently Solvable by a Quantum Computer
- Optimal Coherent Quantum Phase Estimation via Tapering
- Comprehensive Library of Variational LSE Solvers
- Adaptive measurement strategy for quantum subspace methods
- High-precision and low-depth quantum algorithm design for eigenstate problems
- Superconducting qubits in the millions: the potential and limitations of modularity
- Channel-based framework for phase esimation of multiple eigenvalues
- Practical limitations of quantum data propagation on noisy quantum processors
- Quantum many-body simulation of finite-temperature systems with sampling a series expansion of a quantum imaginary-time evolution
- Measuring Correlation and Entanglement between Molecular Orbitals on a Trapped-Ion Quantum Computer
- Stabilizer configuration interaction: Finding molecular subspaces with error detection properties
- Fault-tolerant quantum simulation of generalized Hubbard models
- Phase estimation with partially randomized time evolution
- Exponential distillation of dominant eigenproperties
- Toward scalable quantum computations of atomic nuclei
- Feasibility of performing quantum chemistry calculations on quantum computers
- Averaging gate approximation error and performance of Unitary Coupled Cluster ansatz in Pre-FTQC Era
- Enhancing Scalability of Quantum Eigenvalue Transformation of Unitary Matrices for Ground State Preparation through Adaptive Finer Filtering
- Classical post-processing approach for quantum amplitude estimation
- Dissipative ground state preparation in ab initio electronic structure theory
- Hybrid quantum gap estimation algorithm using a filtered time series
- Tensor-based phase difference estimation on time series analysis
- Deterministic Ground State Preparation via Power-Cosine Filtering of Time Evolution Operators
- Robust phase estimation of the ground-state energy without controlled time evolution on a quantum device
- Double-bracket quantum algorithms for high-fidelity ground state preparation
- Numerical investigation of the quantum inverse algorithm on small molecules
- Noise-resilient and resource-efficient hybrid algorithm for robust quantum gap estimation
- Quantum Imaginary-Time Evolution with Polynomial Resources in Evolution Time
- Transversal architecture for megaquop-scale quantum simulation with neutral atoms