Accurately Solving Linear Systems with Quantum Oracles

ORAL

Abstract

Quantum linear system algorithms (QLSA), w.r.t dimension, have the potential to solve linear systems (LSs) faster than classical methods. However, to extract the classical solution, a quantum tomography algorithm (QTA) is needed which increases both error and time complexity. To accurately and efficiently solve LSs using QLSA and QTA algorithms, we propose an Iterative Refinement method (IRM) which uses limited-precision quantum oracles iteratively to improve dependence on precision to logarithmic. The IRM is broadly applicable. We discuss its application in Quantum Interior Point Methods (QIPM) and discuss how the proposed IRM accelerates QIPMs.

*This work is supported by Defense Advanced Research Projects Agency as part of the project W911NF2010022: The QuantumComputing Revolution and Optimization: Challenges and Opportunities.

–

Publication: Accurately Solving Linear Systems with Quantum Oracles (preparing to submit)

Presenters

  • Mohammadhossein Mohammadisiahroudi

    • Lehigh University

Authors

  • Mohammadhossein Mohammadisiahroudi

    • Lehigh University

  • Ramin Fakhimi

    • Lehigh University

  • Brandon Augustino

    • Lehigh University

  • Tamás Terlaky

    • Lehigh University

  • Giacomo Nannicini

    • University of Southern California