EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Randomized Adiabatic Quantum Linear Solver Algorithm with Optimal Complexity Scaling and Detailed Running Costs

David Jennings, Matteo Lostaglio, Sam Pallister, Andrew T. Sornborger, Yiğit Subaşı

PRX Quantum · 29.12.2025 · 6 (4)

DOI: 10.1103/1xkb-22cc ↗

Kurz gefasst

Fachartikel in der Zeitschrift PRX Quantum, online erschienen am 29.12.2025. Verfasst von David Jennings und 4 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 36 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: US Department of Energy.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Solving linear systems of equations is a fundamental problem with a wide variety of applications across many fields of science, and there is increasing effort to develop quantum linear solver algorithms. Subaşı . [Phys. Rev. Lett. 122, 060504 (2019)] proposed a randomized algorithm inspired by adiabatic quantum computing, based on a sequence of random Hamiltonian simulation steps, with suboptimal scaling in the condition number κ of the linear system and the target error ϵ . Here we go beyond these results in several ways. Firstly, using filtering [Lin and Tong, Quantum 4, 361 (2020)] and Poissonization techniques [Cunningham and Roland, ArXiv:2406.03972 (2024)], the algorithm complexity is improved to the optimal scaling O ( κ log  ( 1 / ϵ ) ) —an exponential improvement in ϵ , and a shaving of a log  κ scaling factor in κ . Secondly, the algorithm is further modified to achieve constant factor improvements, which are vital as we progress towards hardware implementations on fault-tolerant devices. We introduce a cheaper randomized walk operator method replacing Hamiltonian simulation—which also removes the need for potentially challenging classical precomputations; randomized routines are sampled over optimized random variables; circuit constructions are improved. We obtain a closed formula rigorously upper bounding the expected number of times one needs to apply a block-encoding of the linear system matrix to output a quantum state encoding the solution to the linear system. The upper bound is 837 κ at ϵ = 10 − 10 for Hermitian matrices.

Förderung

  • US Department of Energy

Zitieren

APA

Jennings, D., Lostaglio, M., Pallister, S., Sornborger, A. T., & Subaşı, Y. (2025). Randomized Adiabatic Quantum Linear Solver Algorithm with Optimal Complexity Scaling and Detailed Running Costs. PRX Quantum, 6(4). https://doi.org/10.1103/1xkb-22cc

Vancouver

Jennings D, Lostaglio M, Pallister S, Sornborger AT, Subaşı Y. Randomized Adiabatic Quantum Linear Solver Algorithm with Optimal Complexity Scaling and Detailed Running Costs. PRX Quantum. 2025;6(4). doi:10.1103/1xkb-22cc

BibTeX
@article{Jennings2025,
  author = {Jennings, David and Lostaglio, Matteo and Pallister, Sam and Sornborger, Andrew T. and Subaşı, Yiğit},
  title = {Randomized Adiabatic Quantum Linear Solver Algorithm with Optimal Complexity Scaling and Detailed Running Costs},
  journal = {PRX Quantum},
  year = {2025},
  volume = {6},
  number = {4},
  doi = {10.1103/1xkb-22cc}
}
Kostenlos starten →