Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems

Abstract

We present a quantum eigenstate filtering algorithm based on quantum signal processing (QSP) and minimax polynomials. The algorithm allows us to efficiently prepare a target eigenstate of a given Hamiltonian, if we have access to an initial state with non-trivial overlap with the target eigenstate and have a reasonable lower bound for the spectral gap. We apply this algorithm to the quantum linear system problem (QLSP), and present two algorithms based on quantum adiabatic computing (AQC) and quantum Zeno effect respectively. Both algorithms prepare the final solution as a pure state, and achieves the near optimal $\tilde{\mathcal{O}}(d\kappa \log (1/\epsilon ))$ query complexity for a $d$-sparse matrix, where $\kappa$ is the condition number, and $\epsilon$ is the desired precision. Neither algorithm uses phase estimation or amplitude amplification.

References in corpus (30)

• Adiabatic 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
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Bounds for the adiabatic approximation with applications to quantum computation
• Quantum Zeno dynamics: mathematical and physical aspects
• Hamiltonian simulation with nearly optimal dependence on all parameters
• A quantum-inspired classical algorithm for recommendation systems
• Fixed-point quantum search with an optimal number of queries
• A quantum linear system algorithm for dense matrices
• A different kind of quantum search
• Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Quantum algorithm and circuit design solving the Poisson equation
• Quantum Simulations of Classical Annealing Processes
• Quantum-inspired algorithms in practice
• Speed-up via Quantum Sampling
• Preparing ground states of quantum many-body systems on a quantum computer
• Quantum Algorithm for Spectral Measurement with Lower Gate Count
• Optimizing quantum optimization algorithms via faster quantum gradient computation
• Quantum search by measurement
• Product Decomposition of Periodic Functions in Quantum Signal Processing
• The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
• A note on the switching adiabatic theorem
• Berry phase from a quantum Zeno effect
• A Quantum Anti-Zeno Paradox
• Non-Abelian Phases from a Quantum Zeno Dynamics

Cited by in corpus (62)

• Solving nonlinear differential equations with differentiable quantum circuits
• Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
• Near-optimal ground state preparation
• Efficient phase-factor evaluation in quantum signal processing
• Improved quantum algorithms for linear and nonlinear differential equations
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• Time-marching based quantum solvers for time-dependent linear differential equations
• Nearly tight Trotterization of interacting electrons
• On the energy landscape of symmetric quantum signal processing
• Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance
• Computing Ground State Properties with Early Fault-Tolerant Quantum Computers
• Constrained Optimization via Quantum Zeno Dynamics
• FABLE: Fast Approximate Quantum Circuits for Block-Encodings
• Random circuit block-encoded matrix and a proposal of quantum LINPACK benchmark
• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
• Multivariable quantum signal processing (M-QSP): prophecies of the two-headed oracle
• A quantum hamiltonian simulation benchmark
• Quantum Regularized Least Squares
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
• A hybrid quantum-classical framework for computational fluid dynamics
• Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm
• End-to-end resource analysis for quantum interior point methods and portfolio optimization
• Derivative Pricing using Quantum Signal Processing
• On efficient quantum block encoding of pseudo-differential operators
• Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra
• Dissipative Preparation of Many-Body Quantum States: Towards Practical Quantum Advantage
• Quantum-classical algorithms for skewed linear systems with optimized Hadamard test
• Quantum differential equation solvers: limitations and fast-forwarding
• Infinite quantum signal processing
• Quantifying $T$-gate-count improvements for ground-state-energy estimation with near-optimal state preparation
• Quantum state preparation for multivariate functions
• Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters
• Early Fault-Tolerant Quantum Algorithms in Practice: Application to Ground-State Energy Estimation
• Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
• Accelerating Quantum Algorithms with Precomputation
• Design nearly optimal quantum algorithm for linear differential equations via Lindbladians
• Quantum Hypothesis Testing with Group Structure
• Limitations of the Macaulay matrix approach for using the HHL algorithm to solve multivariate polynomial systems
• Halving the Cost of Quantum Algorithms with Randomization
• Explicit block encodings of boundary value problems for many-body elliptic operators
• Complementary polynomials in quantum signal processing
• Nearly-frustration-free ground state preparation
• The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver
• Block encoding of matrix product operators
• Quantum eigenvalue processing
• Quantum Iterative Methods for Solving Differential Equations with Application to Computational Fluid Dynamics
• Calculating response functions of coupled oscillators using quantum phase estimation
• Quantum algorithms for linear and non-linear fractional reaction-diffusion equations
• Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations
• High-precision and low-depth quantum algorithm design for eigenstate problems
• Quantum Realization of the Finite Element Method
• On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number
• Unstructured Adiabatic Quantum Optimization: Optimality with Limitations
• 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
• Quantum linear system algorithm with optimal queries to initial state preparation
• Quantum algorithm for solving generalized eigenvalue problems with application to the Schrödinger equation
• Randomized adiabatic quantum linear solver algorithm with optimal complexity scaling and detailed running costs
• Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices
• Quantum community detection via deterministic elimination
• Towards Classical Software Verification using Quantum Computers
• Vortex Detection from Quantum Data