Quantum annealing for polynomial systems of equations
The advent of Noisy Intermediate-Scale Quantum (NISQ) quantum computers has galvanized efforts towards discovering near-term applications. An algorithm for solving polynomial systems of equations was proposed by Dr. Chang (iTHEMS) in collaboration with Dr. Gambhir (Lawrence Livermore National Lab), Dr. Humble (Oak Ridge National Lab), and Dr. Sota (R-CCS) and implemented a linear solver on a D-Wave quantum annealer. While the problems are currently limited to sizes that are easily solved by classical computers, the team showed that the quantum algorithm exhibits constant scaling with increasing condition number, in direct contrast with classical methods. Additionally, the quantum algorithm may also be applied iteratively to exponentially decrease the relative residual, allowing for the classical solution to be reproduced by the quantum computer to single precision. However, the scaling with problem size is unfortunately exponentially bad, reflecting limitations of current quantum computers. Fortunately, there is a great amount of interest and effort put fourth by the greater quantum annealing community geared towards tackling this problem, including using inhomogeneous driving fields, reverse annealing, and even hardware developments towards universal quantum annealers.
- Chia Cheng Chang, Arjun Gambhir, Travis S. Humble, Shigetoshi Sota
"Quantum annealing for polynomial systems of equations"