Large-scale quantum hybrid solution for linear systems of equations

Abstract

State-of-the-art noisy intermediate-scale quantum devices (NISQ), although imperfect, enable computational tasks that are manifestly beyond the capabilities of modern classical supercomputers. However, present quantum computations are restricted to exploring specific simplified protocols, whereas the implementation of full-scale quantum algorithms aimed at solving concrete large scale problems arising in data analysis and numerical modelling remains a challenge. Here we introduce and implement a hybrid quantum algorithm for solving linear systems of equations with exponential speedup, utilizing quantum phase estimation, one of the exemplary core protocols for quantum computing. We introduce theoretically classes of linear systems that are suitable for current generation quantum machines and solve experimentally a $2^{17}$-dimensional problem on superconducting IBMQ devices, a record for linear system solution on quantum computers. The considered large-scale algorithm shows superiority over conventional solutions, demonstrates advantages of quantum data processing via phase estimation and holds high promise for meeting practically relevant challenges.

arXiv comment8 pages, 6 figures

References in corpus (18)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum Machine Learning
• Quantum algorithm for solving linear systems of equations
• Validating quantum computers using randomized model circuits
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Training variational quantum algorithms is NP-hard
• Arbitrary accuracy iterative phase estimation algorithm as a two qubit benchmark
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Approximate Quantum Fourier Transform with $O(n\log (n))$ T gates
• Hybrid quantum linear equation algorithm and its experimental test on IBM Quantum Experience
• Quantum-enhanced magnetometry by phase estimation algorithms with a single artificial atom
• Bayesian Deep Learning on a Quantum Computer
• Quantum metrology with a transmon qutrit
• Experimental realization of quantum algorithms for linear system inspired by adiabatic quantum computing
• Computing a logarithm of a unitary matrix with general spectrum
• Linear Ascending Metrological Algorithm

Cited by in corpus (3)

• Quantum Machine Learning: from physics to software engineering
• Quantum Computers for Weather and Climate Prediction: The Good, the Bad and the Noisy
• Divide-and-conquer verification method for noisy intermediate-scale quantum computation