估算量子计算机解线性方程组的资源开销，找出超越经典算法的可能条件。
Towards identifying possible fault-tolerant advantage of quantum linear system algorithms in terms of space, time and energy
- 基于表面码容错，量化了超导量子计算机运行HHL算法的时空能资源消耗。
- 在矩阵规模 $N o 2^{33} ext{ 到 } 2^{48}$ 时，量子优势可能显现。
- 适合关注量子计算实用边界与硬件需求的研究者参考。
量子计算作为突破摩尔定律的非冯·诺依曼范式，对某些问题可实现超多项式加速。然而其在机器学习等任务中的效率优势仍待验证，量子噪声使资源估算与经典对比复杂化。本文针对容错超导设备运行的哈罗-哈西迪-洛伊德（HHL）算法——一种与线性代数和机器学习相关的量子线性系统求解器——详细估算其空间、时间与能量资源。排除内存与数据传输后，当矩阵规模 $N o 2^{33} ext{ 至 } 2^{48}$ 甚至更低时，量子优势可能超越经典共轭梯度法；此情形需约 ${O}(10^5)$ 个物理量子比特、${O}(10^{12} ext{ 至 } 10^{13})$ 焦耳能量及 ${O}(10^6)$ 秒运行时间，采用三种魔态蒸馏方案（15-1、116-12、225-1）。关键参数包括条件数 $κ o O(10 ext{ 至 }100)$、稀疏度 $s o O(10 ext{ 至 }100)$、精度 $ε o 0.01$ 及物理误差 $10^{-5}$。我们的资源估算器可调节 $N, κ, s, ε$，绘制量子-经典边界地图，揭示实际量子优势可能出现的条件。本工作定量确定了实现显著效益所需容错量子计算机的先进程度。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。