arXiv:2609.28461
Purely-logarithmic-time- and constant-space-overhead fault-tolerant quantum computation
Zhengyi Han, Zi-Wen Liu
Abstract
We prove that constant-space-overhead fault-tolerant quantum computation can be achieved with provably strictly logarithmic time overhead, improving over the best known results with additional subpolylogarithmic factors. Our main construction uses polynomial-subrank transversal logical $\CCZ$ gates on good quantum locally testable codes to implement addressable universal computation by transferring batches of logical qubits between dense storage and active logical subspaces while reusing the same ancillary workspace. Logical $\CCZ$ gates are implemented directly by the transversal operation, so only stabilizer resource states require separate preparation. Furthermore, we give an alternative construction that also achieves purely logarithmic time overhead based on modifying the quantum Reed--Solomon magic-state distillation scheme of Nguyen and Pattison. Recursively applying a fixed distillation circuit protected by qLTCs of increasing block length eliminates the subpolylogarithmic time factor.
AI Summary
The paper addresses whether universal fault-tolerant quantum computation can achieve constant quantum-space overhead with strictly logarithmic time overhead, removing the subpolylogarithmic factor in the previous $O(\log^{1+o(1)}(WD/\varepsilon))$ bound. For adaptive Clifford+$\mathrm{CCZ}$ circuits of width $W$, depth $D$, and target output error $\varepsilon$, the main construction uses code length $n=\Theta(\log(WD/\varepsilon))$ and achieves physical depth $O(D\log(WD/\varepsilon))$ and quantum space $O(W+F(n))$, where $\log F(n)=O(\log n\log\log n)$. Space overhead is constant when $W\ge C_FF(n)$; this holds asymptotically for polynomial depth and inverse-polynomial target error in $W$. The construction uses good quantum locally testable codes whose transversal action supplies $r=n^{\Omega(1)}$ independent logical $\mathrm{CCZ}$ gates. Code switching, reversible linear embeddings, and logical routing transfer dense logical storage into active subspaces in $O(n/r)$ batches, reusing ancillary workspace. Decoder contraction, single-shot error correction, stabilizer-resource preparation, and fault-support weight enumerators establish a constant threshold under locally stochastic noise with arbitrary supported CPTP faults. An alternative construction recursively applies a fixed Reed–Solomon magic-state distillation circuit protected at increasing code lengths, obtaining the same time bound with larger additive space. The model allows arbitrary connectivity and noiseless polynomial-size classical hardware, whose runtime—but not hardware space—is charged. Optimality, the necessity of the width condition, and overheads under noisy classical control or geometric connectivity remain unresolved.
The authors set the overall strategy, and generative AI tools provided substantial assistance in developing the proof details and presentation.
Central claim may not hold: The abstract's constant-space-overhead claim needs a width qualification: both constructions prove O(W) physical space only when the circuit width dominates an additive workspace depending on log(WD/epsilon), a condition not guaranteed for arbitrary widths and depths.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.