一句话：识别量子控制流抽象会以多项式增加 T-复杂度，提出代价模型与 Spire 程序级优化以恢复渐近高效性。
量子纠错能克服物理量子比特的不可靠性，却引入独特的 T-复杂度瓶颈，使量子程序可能慢于理想硬件。本文发现，量子 if 语句等控制流编程抽象会使程序 T-复杂度多项式增长，若不缓解会削弱量子算法优势。作者提出代价模型，用于在纠错下准确分析 T-复杂度并定位慢速来源；并提出程序级优化，通过重写降低 T-复杂度、用模型预测优化后复杂度，再编译为高效电路。优化实现在 Tower 编译器扩展 Spire 中。基于 11 个含控制流的基准程序，实验表明代价模型准确，Spire 优化可恢复渐近高效程序：纠错下运行 T-复杂度等于理想硬件时间复杂性。仅 2/8 个已有量子电路优化器能达到该效果，而 Spire 编译时间少 54×–2400×。
Numerous quantum algorithms require the use of quantum error correction to overcome the intrinsic unreliability of physical qubits. However, quantum error correction imposes a unique performance bottleneck, known as T -complexity, that can make an implementation of an algorithm as a quantum program run more slowly than on idealized hardware. In this work, we identify that programming abstractions for control flow, such as the quantum if-statement, can introduce polynomial increases in the T -complexity of a program. If not mitigated, this slowdown can diminish the computational advantage of a quantum algorithm. To enable reasoning about the costs of control flow, we present a cost model that a developer can use to accurately analyze the T -complexity of a program under quantum error correction and pinpoint the sources of slowdown. To enable the mitigation of these costs, we present a set of program-level optimizations that a developer can use to rewrite a program to reduce its T -complexity, predict the T -complexity of the optimized program using the cost model, and then compile it to an efficient circuit via a straightforward strategy. We implement the program-level optimizations in Spire, an extension of the Tower quantum compiler. Using a set of 11 benchmark programs that use control flow, we empirically show that the cost model is accurate, and that Spire's optimizations recover programs that are asymptotically efficient, meaning their runtime T -complexity under error correction is equal to their time complexity on idealized hardware. Our results show that optimizing a program before it is compiled to a circuit can yield better results than compiling the program to an inefficient circuit and then invoking a quantum circuit optimizer found in prior work. For our benchmarks, only 2 of 8 tested quantum circuit optimizers recover circuits with asymptotically efficient T -complexity. Compared to these 2 optimizers, Spire uses 54 × − 2400 × less compile time.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{abs-2311-12772,
title = {The T-Complexity Costs of Error Correction for Control Flow in Quantum Computation},
author = {Charles Yuan and Michael Carbin},
journal = {Proceedings of the ACM on Programming Languages},
volume = {8},
number = {PLDI},
year = {2024},
doi = {10.1145/3656397}
}