Experimental realization of quantum algorithm for solving linear systems of equations

Abstract

Quantum computers have the potential of solving certain problems exponentially faster than classical computers. Recently, Harrow, Hassidim and Lloyd proposed a quantum algorithm for solving linear systems of equations: given an $N\times N$ matrix $A$ and a vector $\vec{b}$, find the vector $\vec{x}$ that satisfies $A\vec{x}=\vec{b}$. It has been shown that using the algorithm one could obtain the solution encoded in a quantum state $|x$ using $O(\log N)$ quantum operations, while classical algorithms require at least O(N) steps. If one is not interested in the solution $\vec{x}$ itself but certain statistical feature of the solution $x|M|x$ ($M$ is some quantum mechanical operator), the quantum algorithm will be able to achieve exponential speedup over the best classical algorithm as $N$ grows. Here we report a proof-of-concept experimental demonstration of the quantum algorithm using a 4-qubit nuclear magnetic resonance (NMR) quantum information processor. For all the three sets of experiments with different choices of $\vec{b}$, we obtain the solutions with over 96% fidelity. This experiment is a first implementation of the algorithm. Because solving linear systems is a common problem in nearly all fields of science and engineering, we will also discuss the implication of our results on the potential of using quantum computers for solving practical linear systems.

13 pages,8 figures

References in corpus (7)

• Quantum algorithm for solving linear systems of equations
• Quantum Data Fitting
• Experimental implementation of an adiabatic quantum optimization algorithm
• Quantum algorithm and circuit design solving the Poisson equation
• A Quantum Adiabatic Algorithm for Factorization and Its Experimental Implementation
• Experimental Quantum Computing to Solve Systems of Linear Equations
• Liquid State NMR as a Test-bed for Developing Quantum Control Methods

Cited by in corpus (41)

• Quantum algorithms: an overview
• Qudits and high-dimensional quantum computing
• Experimental Realization of Quantum Artificial Intelligence
• Entanglement-Based Machine Learning on a Quantum Computer
• Variational Quantum Linear Solver
• Solving nonlinear differential equations with differentiable quantum circuits
• Quantum Image Processing and Its Application to Edge Detection: Theory and Experiment
• Quantum Machine Learning for Chemistry and Physics
• Solving systems of linear equations on a quantum computer
• Solving Systems of Linear Equations with a Superconducting Quantum Processor
• A Quantum Algorithm for Solving Linear Differential Equations: Theory and Experiment
• Experimental realization of quantum algorithms for linear system inspired by adiabatic quantum computing
• Quantum computation of molecular response properties
• Box algorithm for the solution of differential equations on a quantum annealer
• Efficient quantum circuit for singular value thresholding
• Quantum Circulant Preconditioner for Linear System of Equations
• Experimental quantum pattern recognition in IBMQ and diamond NVs
• Hybrid classical-quantum linear solver using Noisy Intermediate-Scale Quantum machines
• Analyzing the impact of time-correlated noise on zero-noise extrapolation
• Quantum Circuit Design Methodology for Multiple Linear Regression
• Realizing quantum linear regression with auxiliary qumodes
• Linear optical demonstration of quantum speed-up with a single qudit
• Experimental implementation of quantum algorithm for association rules mining
• Controlling NMR spin systems for quantum computation
• Harrow-Hassidim-Lloyd algorithm without ancilla postselection
• Quantum algorithms for matrix operations and linear systems of equations
• Efficient quantum circuits for Toeplitz and Hankel matrices
• Digital-analog co-design of the Harrow-Hassidim-Lloyd algorithm
• Classical and quantum machine learning applications in spintronics
• Variational Quantum Support Vector Machine based on $\Gamma$ matrix expansion and Variational Universal-Quantum-State Generator
• Effective quantum state reconstruction using compressive sensing in NMR quantum computing
• Quantum Algorithms for Geologic Fracture Networks
• Coherence dynamics in quantum algorithm for linear systems of equations
• A Universal Quantum Circuit Design for Periodical Functions
• Characterization of overparametrization in the simulation of realistic quantum systems
• Quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems
• Accelerating the training of single-layer binary neural networks using the HHL quantum algorithm
• Quantum resources in Harrow-Hassidim-Lloyd algorithm
• Quantum Anomaly Detection with a Spin Processor in Diamond
• Quantum Higher Order Singular Value Decomposition
• Quantum Fourier Transform in Oscillating Modes