Resource-efficient quantum algorithm for linear systems of equations

Abstract

Finding the solution to linear systems is at the heart of many applications in science and technology. Over the years a number of algorithms have been proposed to solve this problem on a digital quantum device, yet most of these are too demanding to be applied to the current noisy hardware. In this work, an original algorithmic procedure to solve the Quantum Linear System Problem (QLSP) is presented, which combines ideas from Variational Quantum Algorithms (VQA) and the framework of classical shadows. The result is the Shadow Quantum Linear Solver (SQLS), a quantum algorithm solving the QLSP avoiding the need for large controlled unitaries, requiring a number of qubits that is logarithmic in the system size. In particular, our heuristics show an exponential advantage of the SQLS in circuit execution per cost function evaluation when compared to other notorious variational approaches to solving linear systems of equations. We test the convergence of the SQLS on a number of linear systems, and results highlight how the theoretical bounds on the number of resources used by the SQLS are conservative. Finally, we apply this algorithm to a physical problem of practical relevance, by leveraging decomposition theorems from linear algebra to solve the discretized Laplace Equation in a 2D grid for the first time using a hybrid quantum algorithm.

References in corpus (41)

• SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
• Quantum Computing in the NISQ era and beyond
• A variational eigenvalue solver on a quantum processor
• Quantum algorithm for solving linear systems of equations
• Variational Quantum Algorithms
• Barren plateaus in quantum neural network training landscapes
• Quantum support vector machine for big data classification
• Quantum Chemistry in the Age of Quantum Computing
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Parameterized quantum circuits as machine learning models
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum Data Fitting
• Variational Quantum Computation of Excited States
• A Race Track Trapped-Ion Quantum Processor
• Variational quantum algorithms for nonlinear problems
• Preconditioned quantum linear system algorithm
• The General Quantum Interference Principle and the Duality Computer
• Variational quantum algorithms for discovering Hamiltonian spectra
• A quantum linear system algorithm for dense matrices
• Barren Plateaus in Variational Quantum Computing
• Variational Quantum Linear Solver
• Efficient estimation of Pauli observables by derandomization
• Noise Resilience of Variational Quantum Compiling
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Quantum computers as universal quantum simulators: state-of-art and perspectives
• Universal expressiveness of variational quantum classifiers and quantum kernels for support vector machines
• A Comparison of Various Classical Optimizers for a Variational Quantum Linear Solver
• Hamiltonian variational ansatz without barren plateaus
• Duality and Recycling Computing in Quantum Computers
• Impossibility of Classically Simulating One-Clean-Qubit Computation
• 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
• Optimal data processing for quantum measurements
• Trainability Enhancement of Parameterized Quantum Circuits via Reduced-Domain Parameter Initialization
• Application of a variational hybrid quantum-classical algorithm to heat conduction equation
• Nonlinear dynamics as a ground-state solution on quantum computers
• Tensorized Pauli decomposition algorithm
• Dual frame optimization for informationally complete quantum measurements
• PauliComposer: Compute Tensor Products of Pauli Matrices Efficiently
• Near Term Algorithms for Linear Systems of Equations