Quantum annealing for systems of polynomial equations

Chia Cheng Chang; Arjun Gambhir; Travis S. Humble; Shigetoshi Sota

doi:10.1038/s41598-019-46729-0

Quantum annealing for systems of polynomial equations

Chia Cheng Chang, Arjun Gambhir, Travis S. Humble, Shigetoshi Sota

Quantum Science Center

Research output: Contribution to journal › Article › peer-review

35 Scopus citations

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 10⁻⁸.

Original language	English
Article number	10258
Journal	Scientific Reports
Volume	9
Issue number	1
DOIs	https://doi.org/10.1038/s41598-019-46729-0
State	Published - Dec 1 2019

Funding

We thank Hidetoshi Nishimori (Tokyo Tech), Tetsuo Hatsuda (ℝIKEN), and Chih-Chieh Chen (ITℝI) for discussions. This work was performed under the auspices of the U.S. Department of Energy by LLNL under Contract No. DE-AC52-07NA27344 (AG). Access to the D-Wave 2000Q computing system was provided by Oak ℝidge National Laboratory. TSH acknowledges support from the Department of Energy, Office of Science, Early Career ℝesearch Project and the OℝNL Directed ℝesearch and Development funds. This manuscript has been authored by UT-Battelle, LLC, under Contract No. DE-AC0500Oℝ22725 with the U.S. Department of Energy. The Department of Energy will provide public access to these results of federally sponsored research in accordance with the DOE Public Access Plan (http://energy.gov/downloads/doe-public-access-plan).

Funders	Funder number
U.S. Department of Energy	DE-AC0500OR22725, DE-AC52-07NA27344
Office of Science
Lawrence Livermore National Laboratory

Access to Document

10.1038/s41598-019-46729-0

Cite this

@article{463c5ce03c2345d19563b50e27a5d283,

title = "Quantum annealing for systems of polynomial equations",

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 10−8.",

author = "Chang, {Chia Cheng} and Arjun Gambhir and Humble, {Travis S.} and Shigetoshi Sota",

note = "Publisher Copyright: {\textcopyright} 2019, The Author(s).",

year = "2019",

month = dec,

day = "1",

doi = "10.1038/s41598-019-46729-0",

language = "English",

volume = "9",

journal = "Scientific Reports",

issn = "2045-2322",

publisher = "Nature Research",

number = "1",

}

TY - JOUR

T1 - Quantum annealing for systems of polynomial equations

AU - Chang, Chia Cheng

AU - Gambhir, Arjun

AU - Humble, Travis S.

AU - Sota, Shigetoshi

PY - 2019/12/1

Y1 - 2019/12/1

N2 - 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 10−8.

AB - 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 10−8.

UR - http://www.scopus.com/inward/record.url?scp=85069481271&partnerID=8YFLogxK

U2 - 10.1038/s41598-019-46729-0

DO - 10.1038/s41598-019-46729-0

M3 - Article

C2 - 31311997

AN - SCOPUS:85069481271

SN - 2045-2322

VL - 9

JO - Scientific Reports

JF - Scientific Reports

IS - 1

M1 - 10258

ER -

Quantum annealing for systems of polynomial equations

Abstract

Funding

Access to Document

Other files and links

Fingerprint

Cite this