arXiv:2610.03684
Single-Shot Error Correction at Optimal Spacetime Cost
Kishor Bharti, Tobias Haug, Derek Khu, Andrew Tanggara
Abstract
Recent work established that, for independent erasures, storing $K$ logical qubits for $S$ time steps with error at most $\varepsilon$ requires a spacetime cost of $Ω(S(K+\log(S/\varepsilon)))$. A matching construction was also given, but assumes ideal error correction. Here we show that the same scaling can be achieved with an explicit noisy error-correction circuit and efficient decoding, counting all state-preparation, gate, measurement, and wait locations, provided that the hardware supports long-range qubit connectivity and fast, reliable classical processing. Thus, reliability adds only a logarithmic overhead shared by all stored qubits. The construction works for sufficiently weak but otherwise general circuit noise, including faults during syndrome extraction and correlated faults, and for independent erasures it matches the best known lower bound up to constant factors. We attain this scaling using quantum Tanner codes, with each memory step consisting of one round of syndrome extraction followed by a fixed number of parallel classical decoder steps that reduce the residual error enough to keep later faults correctable, regardless of memory size, storage time, or target accuracy. Together, this gives exponentially small failure probability per step while keeping the cost of each memory step linear in the code size. The same analysis also extends to certain constant-depth logical Clifford operations.
AI Summary
The paper asks whether the optimal spacetime cost of quantum memory remains achievable when error correction is noisy and decoding latency is counted. It constructs an encoded memory using quantum Tanner codes with constant rate, linear distance, and single-shot decoding. Storing $K$ logical qubits for $S$ recovery cycles with logical diamond-norm error at most $\varepsilon$ requires $N=O(K+\log(S/\varepsilon))$ data qubits, $O(N)$ peak quantum width, and $C=O(SN)$ total preparation, gate, measurement, and wait locations. For independent erasures, this matches the stated lower bound up to constants. Each constant-duration cycle measures every check once and runs a fixed number of parallel decoder iterations, requiring $O(N)$ classical work. Building on existing Tanner-decoder guarantees, the circuit analysis establishes a residual-error contraction $r_{t+1}\le\lambda r_t+Bf_t$, with $\lambda<1$. A cycle exceeding a fixed fault fraction has probability exponentially small in $N$, yielding total error $O(S e^{-\gamma N})$. A common Knill–Laflamme recovery handles the linear span of successful error operators, retaining coherent interference and reference entanglement. The construction assumes long-range connectivity and reliable parallel classical processing with size-independent communication latency. Fault locations are sampled classically under a local-stochastic bound; coherent operations within fault paths are allowed, but persistent small overrotations everywhere are not covered. Inputs and quantum outputs remain encoded. Destructive readout and specified bounded-depth Clifford layers are covered; addressable logical CNOTs require an unproved sparse-representative assumption. Encoding interfaces and universal computation are not supplied.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 20 pages