Quantum annealing for systems of polynomial equations
arXiv:1812.06917 · doi:10.1038/s41598-019-46729-0
Abstract
Numerous scientific and engineering applications require numerically solving systems of equations. Classically solving a general set of polynomial equations requires iterative solvers, while linear equations may be solved either by direct matrix inversion or iteratively with judicious preconditioning. However, the convergence of iterative algorithms is highly variable and depends, in part, on the condition number. We present a direct method for solving general systems of polynomial equations based on quantum annealing, and we validate this method using a system of second-order polynomial equations solved on a commercially available quantum annealer. We then demonstrate applications for linear regression, and discuss in more detail the scaling behavior for general systems of linear equations with respect to problem size, condition number, and search precision. Finally, we define an iterative annealing process and demonstrate its efficacy in solving a linear system to a tolerance of .
arXiv comment11 pages, 4 figures. Added example for a system of quadratic equations. Supporting code is available at https://github.com/cchang5/quantum_poly_solver . This is a post-peer-review, pre-copyedit version of an article published in Scientific Reports. The final authenticated version is available online at: https://www.nature.com/articles/s41598-019-46729-0
References in corpus (22)
- Quantum algorithm for solving linear systems of equations
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Quantum Annealing and Analog Quantum Computation
- Defining and detecting quantum speedup
- A percent-level determination of the nucleon axial coupling from Quantum Chromodynamics
- Demonstration of a scaling advantage for a quantum annealer over simulated annealing
- Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
- Decoherence in adiabatic quantum computation
- Local coherence and deflation of the low quark modes in lattice QCD
- Non-perturbative k-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spins
- Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
- Solving Systems of Linear Equations with a Superconducting Quantum Processor
- Adaptive Multigrid Algorithm for Lattice QCD
- Decoherence in adiabatic quantum computation
- Computing and deflating eigenvalues while solving multiple right hand side linear systems in Quantum Chromodynamics
- A deceptive step towards quantum speedup detection
- Experimental realization of quantum algorithms for linear system inspired by adiabatic quantum computing
- Thermalization, freeze-out and noise: deciphering experimental quantum annealers
- An Integrated Programming and Development Environment for Adiabatic Quantum Optimization
- Bond chaos in spin glasses revealed through thermal boundary conditions
- Retrieving the ground state of spin glasses using thermal noise: Performance of quantum annealing at finite temperatures
Cited by in corpus (13)
- Preparations for Quantum Simulations of Quantum Chromodynamics in 1+1 Dimensions: (I) Axial Gauge
- Basic Elements for Simulations of Standard Model Physics with Quantum Annealers: Multigrid and Clock States
- Quantum simulation of open quantum systems in heavy-ion collisions
- Quantum Algorithms for Solving Ordinary Differential Equations via Classical Integration Methods
- FEqa: Finite Element Computations on Quantum Annealers
- An Application of Quantum Annealing Computing to Seismic Inversion
- Hybrid classical-quantum linear solver using Noisy Intermediate-Scale Quantum machines
- A hybrid classical-quantum approach to solve the heat equation using quantum annealers
- Quantum Search Approaches to Sampling-Based Motion Planning
- Ising Machines for Diophantine Problems in Physics
- Quantum-inspired optimization for wavelength assignment
- A QUBO Algorithm to Compute Eigenvectors of Symmetric Matrices
- Hybrid adiabatic quantum computing for tomographic image reconstruction -- opportunities and limitations