Variational Quantum Linear Solver

Abstract

Previously proposed quantum algorithms for solving linear systems of equations cannot be implemented in the near term due to the required circuit depth. Here, we propose a hybrid quantum-classical algorithm, called Variational Quantum Linear Solver (VQLS), for solving linear systems on near-term quantum computers. VQLS seeks to variationally prepare $|x⟩$ such that $A|x⟩\propto |b⟩$. We derive an operationally meaningful termination condition for VQLS that allows one to guarantee that a desired solution precision $\epsilon$ is achieved. Specifically, we prove that $C\ge {\epsilon }^2/{\kappa }^2$, where $C$ is the VQLS cost function and $\kappa$ is the condition number of $A$. We present efficient quantum circuits to estimate $C$, while providing evidence for the classical hardness of its estimation. Using Rigetti's quantum computer, we successfully implement VQLS up to a problem size of $1024\times 1024$. Finally, we numerically solve non-trivial problems of size up to $2^{50}\times 2^{50}$. For the specific examples that we consider, we heuristically find that the time complexity of VQLS scales efficiently in $\epsilon$, $\kappa$, and the system size $N$.

arXiv comment16 + 8 pages, 15 figures, 7 tables

References in corpus (61)

• Quantum Computing in the NISQ era and beyond
• A variational eigenvalue solver on a quantum processor
• Quantum algorithm for solving linear systems of equations
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Barren plateaus in quantum neural network training landscapes
• A Quantum Approximate Optimization Algorithm
• Quantum Circuit Learning
• Quantum Chemistry in the Age of Quantum Computing
• Error mitigation for short-depth quantum circuits
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• Evaluating analytic gradients on quantum hardware
• On the Power of One Bit of Quantum Information
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Efficient variational quantum simulator incorporating active error minimisation
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Self-Verifying Variational Quantum Simulation of the Lattice Schwinger Model
• Quantum autoencoders for efficient compression of quantum data
• Variational Quantum Computation of Excited States
• Theory of variational quantum simulation
• An initialization strategy for addressing barren plateaus in parametrized quantum circuits
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Quantum-assisted quantum compiling
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• Variational quantum algorithms for discovering Hamiltonian spectra
• Learning the quantum algorithm for state overlap
• Variational Fast Forwarding for Quantum Simulation Beyond the Coherence Time
• A quantum linear system algorithm for dense matrices
• Stochastic gradient descent for hybrid quantum-classical optimization
• Variational Quantum State Diagonalization
• Noise Resilience of Variational Quantum Compiling
• The SWAP test and the Hong-Ou-Mandel effect are equivalent
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Variational algorithms for linear algebra
• Experimental Quantum Computing to Solve Systems of Linear Equations
• Large gradients via correlation in random parameterized quantum circuits
• Variational Quantum State Eigensolver
• Low-depth gradient measurements can improve convergence in variational hybrid quantum-classical algorithms
• An Adaptive Optimizer for Measurement-Frugal Variational Algorithms
• Variational Quantum Fidelity Estimation
• Experimental realization of quantum algorithm for solving linear systems of equations
• Solving systems of linear equations on a quantum computer
• Variational-State Quantum Metrology
• Solving Systems of Linear Equations with a Superconducting Quantum Processor
• Fast-forwarding of Hamiltonians and Exponentially Precise Measurements
• Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem
• Quantum approximate optimization is computationally universal
• Hybrid quantum linear equation algorithm and its experimental test on IBM Quantum Experience
• The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
• Quantum Singular Value Decomposer
• Variational Consistent Histories as a Hybrid Algorithm for Quantum Foundations
• Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations
• Impossibility of Classically Simulating One-Clean-Qubit Computation
• Near-term quantum algorithms for linear systems of equations
• Subspace Variational Quantum Simulator
• Robust quantum compilation and circuit optimisation via energy minimisation
• Experimental realization of quantum algorithms for linear system inspired by adiabatic quantum computing
• Hardness of classically sampling one clean qubit model with constant total variation distance error
• Operator Sampling for Shot-frugal Optimization in Variational Algorithms
• The boundary effects of transverse field Ising model

Cited by in corpus (73)

• Connecting ansatz expressibility to gradient magnitudes and barren plateaus
• Diagnosing Barren Plateaus with Tools from Quantum Optimal Control
• Variational algorithms for linear algebra
• Grover Adaptive Search for Constrained Polynomial Binary Optimization
• Variational Quantum State Eigensolver
• Digitized-counterdiabatic quantum approximate optimization algorithm
• Universal Variational Quantum Computation
• A comprehensive review of Quantum Machine Learning: from NISQ to Fault Tolerance
• Neural Predictor based Quantum Architecture Search
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• Minimizing estimation runtime on noisy quantum computers
• NISQ Computers: A Path to Quantum Supremacy
• On the practical usefulness of the Hardware Efficient Ansatz
• Quantum Singular Value Decomposer
• Overhead for simulating a non-local channel with local channels by quasiprobability sampling
• Integrating Quantum Computing Resources into Scientific HPC Ecosystems
• Computing Ground State Properties with Early Fault-Tolerant Quantum Computers
• Progress toward favorable landscapes in quantum combinatorial optimization
• Can Error Mitigation Improve Trainability of Noisy Variational Quantum Algorithms?
• Operator Sampling for Shot-frugal Optimization in Variational Algorithms
• Sub-Quantum Fisher Information
• Variational Quantum-Based Simulation of Waveguide Modes
• Hamiltonian simulation for hyperbolic partial differential equations by scalable quantum circuits
• Tight and Efficient Gradient Bounds for Parameterized Quantum Circuits
• Automated Quantum Circuit Design with Nested Monte Carlo Tree Search
• Incompressible Navier-Stokes solve on noisy quantum hardware via a hybrid quantum-classical scheme
• Enabling Large-Scale and High-Precision Fluid Simulations on Near-Term Quantum Computers
• A hybrid quantum-classical framework for computational fluid dynamics
• Simulating fluid flows with quantum computing
• Compact quantum algorithms for time-dependent differential equations
• Scalable Quantum Simulations of Scattering in Scalar Field Theory on 120 Qubits
• Ensemble-learning error mitigation for variational quantum shallow-circuit classifiers
• Bridging Paradigms: Designing for HPC-Quantum Convergence
• Beyond unital noise in variational quantum algorithms: noise-induced barren plateaus and limit sets
• Boundary Treatment for Variational Quantum Simulations of Partial Differential Equations on Quantum Computers
• Dissipative variational quantum algorithms for Gibbs state preparation
• Hybrid discrete-continuous compilation of trapped-ion quantum circuits with deep reinforcement learning
• Improving Gradient Methods via Coordinate Transformations: Applications to Quantum Machine Learning
• Expressivity of Variational Quantum Machine Learning on the Boolean Cube
• Detect anomalous quartic gauge couplings at muon colliders with quantum kernel k-means
• Solving the Hele-Shaw flow using the Harrow-Hassidim-Lloyd algorithm on superconducting devices: A study of efficiency and challenges
• Adaptive shot allocation for fast convergence in variational quantum algorithms
• A multiple-circuit approach to quantum resource reduction with application to the quantum lattice Boltzmann method
• Towards Variational Quantum Algorithms for generalized linear and nonlinear transport phenomena
• Quantum Dynamics Simulation of the Advection-Diffusion Equation
• A variational quantum algorithm for tackling multi-dimensional Poisson equations with inhomogeneous boundary conditions
• Quantum Circuit Design using a Progressive Widening Enhanced Monte Carlo Tree Search
• Hierarchical Multigrid Ansatz for Variational Quantum Algorithms
• Photonic variational quantum eigensolver using entanglement measurements
• Multidimensional Quantum Generative Modeling by Quantum Hartley Transform
• Quantum Feasibility Labeling for NP-complete Vertex Coloring Problem
• qlbm -- A Quantum Lattice Boltzmann Software Framework
• Perturbative gadgets for gate-based quantum computing: Non-recursive constructions without subspace restrictions
• Simulating the Fermi-Hubbard model with long-range hopping on a quantum computer
• Expanding Hardware-Efficiently Manipulable Hilbert Space via Hamiltonian Embedding
• Variational quantum algorithm based on Lagrange polynomial encoding to solve differential equations
• Variational quantum cloning machine on an integrated photonic interferometer
• An Efficient Decomposition of the Carleman Linearized Burgers' Equation
• Comprehensive Library of Variational LSE Solvers
• A quantum machine learning classifier to search for new physics
• Resource-efficient quantum algorithm for linear systems of equations
• High-Entanglement Capabilities for Variational Quantum Algorithms: The Poisson Equation Case
• Quantum Global Minimum Finder based on Variational Quantum Search
• End-to-End Quantum Algorithm for Topology Optimization in Structural Mechanics
• Multi-channel convolutional neural quantum embedding
• Scaling Hybrid Quantum-HPC Applications with the Quantum Framework
• Notes on Quantum Computing for Thermal Science
• Warm-Start Variational Quantum Policy Iteration
• Variational quantum algorithms with invariant probabilistic error cancellation on noisy quantum processors
• A Noise-Aware Scalable Subspace Classical Optimizer for the Quantum Approximate Optimization Algorithm
• Nonlinear path-following via the asymptotic numerical method on a quantum processor
• Role of overparametrization in quantum approximate optimization
• Performance evaluation of variational quantum eigensolver and quantum dynamics algorithms on the advection-diffusion equation