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$.

16 + 8 pages, 15 figures, 7 tables

References in corpus (15)

• Quantum algorithm for solving linear systems of equations
• A Quantum Approximate Optimization Algorithm
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• Variational Fast Forwarding for Quantum Simulation Beyond the Coherence Time
• Stochastic gradient descent for hybrid quantum-classical optimization
• Noise Resilience of Variational Quantum Compiling
• Variational algorithms for linear algebra
• Large gradients via correlation in random parameterized quantum circuits
• Variational Quantum State Eigensolver
• An Adaptive Optimizer for Measurement-Frugal Variational Algorithms
• Variational-State Quantum Metrology
• Quantum approximate optimization is computationally universal
• Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations
• Near-term quantum algorithms for linear systems of equations
• Operator Sampling for Shot-frugal Optimization in Variational Algorithms

Cited by in corpus (71)

• 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
• 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
• Overhead for simulating a non-local channel with local channels by quasiprobability sampling
• Computing Ground State Properties with Early Fault-Tolerant Quantum Computers
• Integrating Quantum Computing Resources into Scientific HPC Ecosystems
• 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
• Solving the Hele-Shaw flow using the Harrow-Hassidim-Lloyd algorithm on superconducting devices: A study of efficiency and challenges
• Detect anomalous quartic gauge couplings at muon colliders with quantum kernel k-means
• 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
• Adaptive shot allocation for fast convergence in variational quantum algorithms
• A variational quantum algorithm for tackling multi-dimensional Poisson equations with inhomogeneous boundary conditions
• Quantum Dynamics Simulation of the Advection-Diffusion Equation
• 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
• qlbm -- A Quantum Lattice Boltzmann Software Framework
• Multidimensional Quantum Generative Modeling by Quantum Hartley Transform
• Quantum Feasibility Labeling for NP-complete Vertex Coloring Problem
• Perturbative gadgets for gate-based quantum computing: Non-recursive constructions without subspace restrictions
• Variational quantum algorithm based on Lagrange polynomial encoding to solve differential equations
• Comprehensive Library of Variational LSE Solvers
• Simulating the Fermi-Hubbard model with long-range hopping on a quantum computer
• Variational quantum cloning machine on an integrated photonic interferometer
• Expanding Hardware-Efficiently Manipulable Hilbert Space via Hamiltonian Embedding
• An Efficient Decomposition of the Carleman Linearized Burgers' Equation
• End-to-End Quantum Algorithm for Topology Optimization in Structural Mechanics
• High-Entanglement Capabilities for Variational Quantum Algorithms: The Poisson Equation Case
• Resource-efficient quantum algorithm for linear systems of equations
• Scaling Hybrid Quantum-HPC Applications with the Quantum Framework
• Multi-channel convolutional neural quantum embedding
• A quantum machine learning classifier to search for new physics
• Warm-Start Variational Quantum Policy Iteration
• Notes on Quantum Computing for Thermal Science
• 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
• Quantum Global Minimum Finder based on Variational Quantum Search
• Nonlinear path-following via the asymptotic numerical method on a quantum processor
• Performance evaluation of variational quantum eigensolver and quantum dynamics algorithms on the advection-diffusion equation
• Role of overparametrization in quantum approximate optimization