# Towards identifying possible fault-tolerant advantage of quantum linear system algorithms in terms of space, time and energy

arXiv: https://arxiv.org/abs/2502.11239 · HTML: https://mlsanity.com/paper/2502.11239/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 47 references that are in the map.
- First posted on arXiv 16 Feb 2025.

## Builds on (most cited first, 7 of 7)

- [Predicting Many Properties of a Quantum System from Very Few Measurements](https://mlsanity.com/paper/2002.08953/) (2020)
- [Towards provably efficient quantum algorithms for large-scale machine-learning models](https://mlsanity.com/paper/2303.03428/) (2023)
- [Quantum linear systems algorithms: a primer](https://mlsanity.com/paper/1802.08227/) (2018)
- [Quantum linear system algorithm with optimal queries to initial state preparation](https://mlsanity.com/paper/2410.18178/) (2024)
- [Randomized adiabatic quantum linear solver algorithm with optimal complexity scaling and detailed running costs](https://mlsanity.com/paper/2305.11352/) (2023)
- [Fundamental causal bounds of quantum random access memories](https://mlsanity.com/paper/2307.13460/) (2023)
- [Simulation-Based Evaluation of Energy-Constrained Quantum-Classical Competition](https://mlsanity.com/paper/2308.08025/) (2023)

## Built on by (most cited first, 1 of 1)

- [The Efficiency Frontier: Classical Shadows versus Direct Quantum Measurement](https://mlsanity.com/paper/2509.06218/) (2025)

## Abstract (arXiv)

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 ≈ 233 ~ 248 or even lower, requiring O(105) physical qubits, O(1012~1013) Joules, and O(106) 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 kappa, s≈O(10~100), ε~0.01, and physical error 10-5. Our resource estimator adjusts N, kappa, 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.