Quantum linear system algorithm with optimal queries to initial state preparation

Abstract

Quantum algorithms for linear systems produce the solution state $A^{-1}|b⟩$ by querying two oracles: $O_A$ that block encodes the coefficient matrix and $O_b$ that prepares the initial state. We present a quantum linear system algorithm making $\mathbf{\Theta }\left(1/\sqrt{p}\right)$ queries to $O_b$, which is optimal in the success probability, and $\mathbf{O}\left(\kappa \log \left(1/p\right)\left(\log \log \left(1/p\right)+\log \left(1/\epsilon \right)\right)\right)$ queries to $O_A$, nearly optimal in all parameters including the condition number and accuracy. Notably, our complexity scaling of initial state preparation holds even when $p$ is not known $\text{a priori}$. This contrasts with recent results achieving $\mathbf{O}\left(\kappa \log \left(1/\epsilon \right)\right)$ complexity to both oracles, which, while optimal in $O_A$, is highly suboptimal in $O_b$ as $\kappa$ can be arbitrarily larger than $1/\sqrt{p}$. In various applications such as solving differential equations, preparing ground states of operators with real spectra, and estimating and transforming eigenvalues of non-normal matrices, we can further improve the dependence on $p$ using a block preconditioning scheme to nearly match or outperform best previous results based on other methods, which also furnishes an extremely simple quantum linear system algorithm with an optimal query complexity to $O_A$. Underlying our results is a new Variable Time Amplitude Amplification algorithm with Tunable thresholds (Tunable VTAA), which fully characterizes generic nested amplitude amplifications, improves the ${\ell }_1$-norm input cost scaling of Ambainis to an ${\ell }_{\frac{2}{3}}$-quasinorm scaling, and admits a deterministic amplification schedule for the quantum linear system problem.

89 pages, 3 figures. Corrected typos

References in corpus (41)

• Quantum algorithm for solving linear systems of equations
• Quantum metrology
• Non-Hermitian Physics
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• 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
• Faster than Hermitian Quantum Mechanics
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Preconditioned quantum linear system algorithm
• Quantum computing enhanced computational catalysis
• General optimality of the Heisenberg limit for quantum metrology
• Quantum algorithm for linear differential equations with exponentially improved dependence on precision
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Near-optimal ground state preparation
• The methodology of resonant equiangular composite quantum gates
• Quantum Search on Bounded-Error Inputs
• Preparing ground states of quantum many-body systems on a quantum computer
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Improved quantum algorithms for linear and nonlinear differential equations
• A randomized quantum algorithm for statistical phase estimation
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
• Concrete resource analysis of the quantum linear system algorithm used to compute the electromagnetic scattering cross section of a 2D target
• Time-marching based quantum solvers for time-dependent linear differential equations
• Hamiltonian Simulation by Uniform Spectral Amplification
• Rapid initial state preparation for the quantum simulation of strongly correlated molecules
• Improving the accuracy of quantum computational chemistry using the transcorrelated method
• Quantum Circulant Preconditioner for Linear System of Equations
• Quantum algorithm for time-dependent differential equations using Dyson series
• Quantum Regularized Least Squares
• Complexity of quantum state verification in the quantum linear systems problem
• Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters
• Quantum algorithm for matrix functions by Cauchy's integral formula
• The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver
• Computing eigenvalues of diagonalizable matrices in a quantum computer
• Exponential quantum advantages for practical non-Hermitian eigenproblems
• Solving generalized eigenvalue problems by ordinary differential equations on a quantum computer
• Resolvent-based quantum phase estimation: Towards estimation of parametrized eigenvalues
• A shortcut to an optimal quantum linear system solver
• Quantum Algorithms based on the Block-Encoding Framework for Matrix Functions by Contour Integrals

Cited by in corpus (1)

• Block encoding the 3D heterogeneous Poisson equation with application to fracture flow