Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing

Abstract

We present two quantum algorithms based on evolution randomization, a simple variant of adiabatic quantum computing, to prepare a quantum state $|x⟩$ that is proportional to the solution of the system of linear equations $A\vec{x}=\vec{b}$. The time complexities of our algorithms are $O({\kappa }^2\log (\kappa )/\epsilon )$ and $O(\kappa \log (\kappa )/\epsilon )$, where $\kappa$ is the condition number of $A$ and $\epsilon$ is the precision. Both algorithms are constructed using families of Hamiltonians that are linear combinations of products of $A$, the projector onto the initial state $|b⟩$, and single-qubit Pauli operators. The algorithms are conceptually simple and easy to implement. They are not obtained from equivalences between the gate model and adiabatic quantum computing. They do not use phase estimation or variable-time amplitude amplification, and do not require large ancillary systems. We discuss a gate-based implementation via Hamiltonian simulation and prove that our second algorithm is almost optimal in terms of $\kappa$. Like previous methods, our techniques yield an exponential quantum speedup under some assumptions. Our results emphasize the role of Hamiltonian-based models of quantum computing for the discovery of important algorithms.

arXiv comment9 pages, 2 figures. Changes in version 2: - Includes a simpler algorithm for the special case of positive matrices. - Added pseudocode for the algorithms - Overall improved presentation

References in corpus (15)

• Quantum algorithm for solving linear systems of equations
• Quantum principal component analysis
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum Data Fitting
• Bounds for the adiabatic approximation with applications to quantum computation
• Preconditioned quantum linear system algorithm
• High-order quantum algorithm for solving linear differential equations
• Quantum Simulations of Classical Annealing Processes
• Quantum Speedup by Quantum Annealing
• Experimental realization of quantum algorithms for linear system inspired by adiabatic quantum computing
• Spectral Gap Amplification
• Improved Bounds for Eigenpath Traversal

Cited by in corpus (92)

• Variational Quantum Algorithms
• Hybrid quantum-classical algorithms and quantum error mitigation
• Variational quantum simulation of general processes
• Variational Quantum Linear Solver
• Solving nonlinear differential equations with differentiable quantum circuits
• Variational algorithms for linear algebra
• Quantum Machine Learning for Chemistry and Physics
• Quantum Algorithm Implementations for Beginners
• Variational Quantum algorithm for Poisson equation
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Improved quantum algorithms for linear and nonlinear differential equations
• A comprehensive review of Quantum Machine Learning: from NISQ to Fault Tolerance
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• Quantum simulation of partial differential equations via Schrodingerisation: technical details
• A Quantum Algorithm for Solving Linear Differential Equations: Theory and Experiment
• Variational Quantum Singular Value Decomposition
• Concentration for random product formulas
• Time-marching based quantum solvers for time-dependent linear differential equations
• Exponential quantum speedup in simulating coupled classical oscillators
• Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance
• Time complexity analysis of quantum algorithms via linear representations for nonlinear ordinary and partial differential equations
• Variational Quantum Computation of Molecular Linear Response Properties on a Superconducting Quantum Processor
• Computing Ground State Properties with Early Fault-Tolerant Quantum Computers
• Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation
• Quantum computation of molecular response properties
• Hybrid quantum algorithms for flow problems
• Constrained Optimization via Quantum Zeno Dynamics
• A variational quantum eigensolver for dynamic correlation functions
• Simultaneous estimation of multiple eigenvalues with short-depth quantum circuit on early fault-tolerant quantum computers
• Quantum Resources Required to Block-Encode a Matrix of Classical Data
• Random circuit block-encoded matrix and a proposal of quantum LINPACK benchmark
• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
• Quantum annealing for systems of polynomial equations
• Self-healing of Trotter error in digital adiabatic state preparation
• An Application of Quantum Annealing Computing to Seismic Inversion
• Hybrid classical-quantum linear solver using Noisy Intermediate-Scale Quantum machines
• Quantum Computing and Preconditioners for Hydrological Linear Systems
• Time complexity analysis of quantum difference methods for linear high dimensional and multiscale partial differential equations
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
• Incompressible Navier-Stokes solve on noisy quantum hardware via a hybrid quantum-classical scheme
• A hybrid quantum-classical framework for computational fluid dynamics
• End-to-end resource analysis for quantum interior point methods and portfolio optimization
• Simulating fluid flows with quantum computing
• Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm
• Compact quantum algorithms for time-dependent differential equations
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications
• Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra
• Randomized Row and Column Iterative Methods with a Quantum Computer
• Complexity of quantum state verification in the quantum linear systems problem
• Quantum gradient descent algorithms for nonequilibrium steady states and linear algebraic systems
• Large-scale quantum hybrid solution for linear systems of equations
• Quantum differential equation solvers: limitations and fast-forwarding
• Speedup of the Quantum Adiabatic Algorithm using Delocalization Catalysis
• Quantum Expectation-Maximization for Gaussian Mixture Models
• Highly optimized quantum circuits synthesized via data-flow engines
• Quantum Algorithm for Solving a Quadratic Nonlinear System of Equations
• Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters
• Quantum Carleman linearisation efficiency in nonlinear fluid dynamics
• Quantum simulation of discrete linear dynamical systems and simple iterative methods in linear algebra via Schrodingerisation
• Qsun: an open-source platform towards practical quantum machine learning applications
• A full circuit-based quantum algorithm for excited-states in quantum chemistry
• Solving the Hele-Shaw flow using the Harrow-Hassidim-Lloyd algorithm on superconducting devices: A study of efficiency and challenges
• Design nearly optimal quantum algorithm for linear differential equations via Lindbladians
• Quantum Algorithms for Geologic Fracture Networks
• Coherence dynamics in quantum algorithm for linear systems of equations
• Limitations of the Macaulay matrix approach for using the HHL algorithm to solve multivariate polynomial systems
• Quantum Computing for Location Determination
• Solving Differential-Algebraic Equations in Power System Dynamic Analysis with Quantum Computing
• Solving Differential-Algebraic Equations in Power System Dynamic Analysis with Quantum Computing
• An Early Investigation of the HHL Quantum Linear Solver for Scientific Applications
• The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver
• Randomized semi-quantum matrix processing
• Identifying Bottlenecks of NISQ-friendly HHL algorithms
• Speeding up Quantum Annealing with Engineered Dephasing
• Quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems
• Quantum Iterative Methods for Solving Differential Equations with Application to Computational Fluid Dynamics
• Quantum algorithms for linear and non-linear fractional reaction-diffusion equations
• On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number
• Unstructured Adiabatic Quantum Optimization: Optimality with Limitations
• Quantum homotopy perturbation method for nonlinear dissipative ordinary differential equations
• Quantum Realization of the Finite Element Method
• Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations
• Resource-efficient quantum algorithm for linear systems of equations
• Quantum linear system algorithm with optimal queries to initial state preparation
• Warm-Start Variational Quantum Policy Iteration
• Range dependent Hamiltonian Algorithm for numerical QUBO formulation
• Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms
• Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices
• Vortex Detection from Quantum Data
• Quantum community detection via deterministic elimination
• Randomized adiabatic quantum linear solver algorithm with optimal complexity scaling and detailed running costs
• Nonadiabatic Self-Healing of Trotter Errors in Digitized Counterdiabatic Dynamics