Towards identifying possible fault-tolerant advantage of quantum linear system algorithms in terms of space, time and energy
This work addresses the challenge of quantifying practical quantum advantages for machine learning and linear algebra problems, providing a detailed resource map for researchers in quantum computing and applied mathematics, though it is incremental in refining existing estimations.
The paper tackles the problem of assessing the potential efficiency advantages of quantum computing for linear algebra tasks by estimating the space, time, and energy resources required for fault-tolerant superconducting devices running the HHL algorithm, finding that possible quantum advantages over classical methods could emerge at large problem sizes (N ≈ 2^33 to 2^48) with requirements of O(10^5) physical qubits, O(10^12-10^13) Joules, and O(10^6) seconds.
Quantum computing, a prominent non-Von Neumann paradigm beyond Moore's law, can offer superpolynomial speedups for certain problems. Yet its advantages in efficiency for tasks like machine learning remain under investigation, and quantum noise complicates resource estimations and classical comparisons. We provide a detailed estimation of space, time, and energy resources for fault-tolerant superconducting devices running the Harrow-Hassidim-Lloyd (HHL) algorithm, a quantum linear system solver relevant to linear algebra and machine learning. Excluding memory and data transfer, possible quantum advantages over the classical conjugate gradient method could emerge at $N \approx 2^{33} \sim 2^{48}$ or even lower, requiring ${O}(10^5)$ physical qubits, ${O}(10^{12}\sim10^{13})$ Joules, and ${O}(10^6)$ seconds under surface code fault-tolerance with three types of magic state distillation (15-1, 116-12, 225-1). Key parameters include condition number, sparsity, and precision $κ, s\approx{O}(10\sim100)$, $ε\sim0.01$, and physical error $10^{-5}$. Our resource estimator adjusts $N, κ, s, ε$, providing a map of quantum-classical boundaries and revealing where a practical quantum advantage may arise. Our work quantitatively determine how advanced a fault-tolerant quantum computer should be to achieve possible, significant benefits on problems related to real-world.