Single-shot code

Single-shot code[1,2]

Description

Block quantum qudit code whose error-syndrome weights increase linearly with the distance of the error state to the code space.

Measurement errors during decoding can yield the wrong syndrome outcome, which can cause error correction to fail even against correctable data errors. A single-shot code is a block quantum code admitting a fault-tolerant error-correcting protocol that does not "fail too badly" when faced with noisy syndrome measurements.

The property typically implies that a sufficiently large number of error-correction rounds will keep both (sufficiently low-weight) data and measurement errors bounded, as opposed to yielding eventually uncorrectable residual errors. The property is sufficient (but not necessary [3]) to reduce the number of error-correction rounds required for fault-tolerant error correction. The word "single" refers to the ability to decode well using syndrome data from only one measurement round, i.e., without using syndrome data from previous rounds.

In the loosest form of the single-shot property for qubit, modular qudit, or Galois qudit codes, given some data error \(e\), ideal data error syndrome \(s\), and measurement error \(m\), there exists an error-correction protocol that outputs a correction \(f\) such that the Hamming weight of the residual error \(e-f\) is polynomial in the weight of \(m\). Note that the stabilizer-reduced weight [2] of \(e\) is often used instead of the weight of \(e\), with the justification that many decoders are designed to obtain the minimum-weight error representative.

A related property is linear confinement, which states that low-weight errors cause low-weight syndromes. A code admits \((\gamma,\alpha)\) linear confinement if the (stabilizer-reduced) weight of the syndrome is proportional to the (stabilizer-reduced) weight of the data error (for data errors of weight less than \(\gamma\)) with proportionality constant \(\alpha\). Linear confinement is sufficient for being single shot against local stochastic noise, and more general notions of confinement are sufficient for being single shot against adversarial noise [4].

Threshold

Residual errors do not become unwieldy after some system-size-independent number cycles of faulty syndrome measurements, and a perfect decoder would be able to recover the information if the final residual error is correctable. Consider acting on a state \(\rho\) with a noise channel \(\mathcal N\) with noise rate \(p\), followed by \(t\) rounds of faulty syndrome measurements \(\mathcal R\) with noise rate \(\eta\) and one perfect recovery (which can be substituted with destructive physical-qubit measurements in practice). The failure probability of a single-shot code should decrease exponentially with the distance of the code, \begin{align} p_{\text{fail}}&=1-F\left(\mathcal{R}[\mathcal{R}_{\eta}\mathcal{N}_{p}]^{t}(\rho),\rho\right)\tag*{(1)}\\&=t\left(p/p_{\star}\right)^{d}~, \tag*{(2)}\end{align} where \(F\) is a state fidelity, and where \(p_{\star}\) is called the sustainable threshold [4]. For any \(p\) below this threshold, some maximum measurement noise \(\eta_{\star}>0\) can be tolerated after sufficiently large \(t\). The final ideal decoding step \(\mathcal{R}\) cannot be done non-destructively in practice due to noisy syndrome measurements, but information can still be recovered by measuring all logical qubits in the computational basis and correcting the outcomes. If the code is single-shot, then such a procedure will output the correct logical information.

Parent

Block quantum code

Children

Quantum expander code — Quantum expander codes are single-shot [5].
Quantum Tanner code — Quantum Tanner codes facilitate single-shot decoding [6].
3D subsystem surface code — The 3D subsystem surface code is a single-shot code [7,8]; see Ref. [9] for an alternative formulation.

Cousins

Self-correcting quantum code — The presence of an energy barrier (i.e., confinement) is sufficient for a code to be single shot, and is also conjectured to be necessary for a code to be a self-correcting memory.
Quantum low-density parity-check (QLDPC) code — Qubit QLDPC codes satisfying linear confinement are single shot [4]. Any code that admits a local greedy decoder also satisfies linear confinement, and so is single shot [10].
Homological product code — It is conjectured that a particular class of codes called three-dimensional product codes is single shot [4].
Qubit stabilizer code — Any stabilizer code can be single shot if sufficiently non-local high-weight stabilizer generators are used for syndrome measurements. These can be obtained with a Gaussian elimination procedure [2].
Subsystem color code — The 3D subsystem color code is a single-shot code [1,11].
Generalized bicycle (GB) code — A qubit GB code \([[n,k,d]]_2\) has \(k\) non-trivial relations between the syndrome bits, which is expected to help with operation in a fault-tolerant regime (in the presence of syndrome measurement errors). See Ref. [12] for many examples of such codes.

References

[1]: H. Bombín, “Single-Shot Fault-Tolerant Quantum Error Correction”, Physical Review X 5, (2015) arXiv:1404.5504 DOI
[2]: E. T. Campbell, “A theory of single-shot error correction for adversarial noise”, Quantum Science and Technology 4, 025006 (2019) arXiv:1805.09271 DOI
[3]: N. Delfosse, B. W. Reichardt, and K. M. Svore, “Beyond Single-Shot Fault-Tolerant Quantum Error Correction”, IEEE Transactions on Information Theory 68, 287 (2022) arXiv:2002.05180 DOI
[4]: A. O. Quintavalle et al., “Single-Shot Error Correction of Three-Dimensional Homological Product Codes”, PRX Quantum 2, (2021) arXiv:2009.11790 DOI
[5]: O. Fawzi, A. Grospellier, and A. Leverrier, “Constant Overhead Quantum Fault-Tolerance with Quantum Expander Codes”, 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) (2018) arXiv:1808.03821 DOI
[6]: S. Gu et al., “Single-shot decoding of good quantum LDPC codes”, (2023) arXiv:2306.12470
[7]: A. Kubica and M. Vasmer, “Single-shot quantum error correction with the three-dimensional subsystem toric code”, Nature Communications 13, (2022) arXiv:2106.02621 DOI
[8]: J. C. Bridgeman, A. Kubica, and M. Vasmer, “Lifting topological codes: Three-dimensional subsystem codes from two-dimensional anyon models”, (2023) arXiv:2305.06365
[9]: C. Stahl, “Single-Shot Quantum Error Correction in Intertwined Toric Codes”, (2023) arXiv:2307.08118
[10]: Q. Xu et al., “Constant-Overhead Fault-Tolerant Quantum Computation with Reconfigurable Atom Arrays”, (2023) arXiv:2308.08648
[11]: B. J. Brown, N. H. Nickerson, and D. E. Browne, “Fault-tolerant error correction with the gauge color code”, Nature Communications 7, (2016) arXiv:1503.08217 DOI
[12]: H.-K. Lin and L. P. Pryadko, “Quantum two-block group algebra codes”, (2023) arXiv:2306.16400

Page edit log

Victor V. Albert (2023-05-02) — most recent

Cite as:

“Single-shot code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/single_shot

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/quantum/properties/block/single_shot.yml.