Near-term quantum algorithms for linear systems of equations

Abstract

Solving linear systems of equations is essential for many problems in science and technology, including problems in machine learning. Existing quantum algorithms have demonstrated the potential for large speedups, but the required quantum resources are not immediately available on near-term quantum devices. In this work, we study near-term quantum algorithms for linear systems of equations of the form $Ax=b$. We investigate the use of variational algorithms and analyze their optimization landscapes. There exist types of linear systems for which variational algorithms designed to avoid barren plateaus, such as properly-initialized imaginary time evolution and adiabatic-inspired optimization, suffer from a different plateau problem. To circumvent this issue, we design near-term algorithms based on a core idea: the classical combination of variational quantum states (CQS). We exhibit several provable guarantees for these algorithms, supported by the representation of the linear system on a so-called Ansatz tree. The CQS approach and the Ansatz tree also admit the systematic application of heuristic approaches, including a gradient-based search. We have conducted numerical experiments solving linear systems as large as $2^{300}\times 2^{300}$ by considering cases where we can simulate the quantum algorithm efficiently on a classical computer. These experiments demonstrate the algorithms' ability to scale to system sizes within reach in near-term quantum devices of about $100$-$300$ qubits.

14+8 pages, 6 figures

Cited by in corpus (35)

• Noisy intermediate-scale quantum (NISQ) algorithms
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• Robust data encodings for quantum classifiers
• Information-theoretic bounds on quantum advantage in machine learning
• Diagnosing Barren Plateaus with Tools from Quantum Optimal Control
• Variational Quantum Linear Solver
• Solving nonlinear differential equations with differentiable quantum circuits
• Efficient estimation of Pauli observables by derandomization
• Variational algorithms for linear algebra
• Large gradients via correlation in random parameterized quantum circuits
• A Comparison of Various Classical Optimizers for a Variational Quantum Linear Solver
• A comprehensive review of Quantum Machine Learning: from NISQ to Fault Tolerance
• Biology and medicine in the landscape of quantum advantages
• Concentration for random product formulas
• Beyond the swap test: optimal estimation of quantum state overlap
• Machine Learning meets Quantum Foundations: A Brief Survey
• Iterative Quantum Assisted Eigensolver
• Calculating transition amplitudes by variational quantum deflation
• Enabling Multi-programming Mechanism for Quantum Computing in the NISQ Era
• Quantum unary approach to option pricing
• Computing Ground State Properties with Early Fault-Tolerant Quantum Computers
• Variational Quantum-Based Simulation of Waveguide Modes
• Variational quantum algorithms for Poisson equations based on the decomposition of sparse Hamiltonians
• Variational quantum Gibbs state preparation with a truncated Taylor series
• Complexity of quantum state verification in the quantum linear systems problem
• Variational Quantum Cloning: Improving Practicality for Quantum Cryptanalysis
• Quantum-classical algorithms for skewed linear systems with optimized Hadamard test
• Variational Approach to Quantum State Tomography based on Maximal Entropy Formalism
• Quantum gradient descent algorithms for nonequilibrium steady states and linear algebraic systems
• Computationally Efficient Quantum Expectation with Extended Bell Measurements
• Qsun: an open-source platform towards practical quantum machine learning applications
• A Universal Quantum Circuit Design for Periodical Functions
• Adaptive shot allocation for fast convergence in variational quantum algorithms
• Lower Bounds on Circuit Depth of the Quantum Approximate Optimization Algorithm
• Logical Abstractions for Noisy Variational Quantum Algorithm Simulation