Single-shot code

Single-shot code[1–3]

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 [4]) 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 [3] 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 [5].

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 [5]. 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 [6].
Quantum Tanner code — Quantum Tanner codes facilitate single-shot decoding [7].
3D subsystem surface code — The 3D subsystem surface code is a single-shot code [8,9]; see Ref. [10] 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.
Hypergraph product (HGP) code — Two-fold application of the hypergraph product to a pair of binary linear codes yields single-shot QLDPC codes that exploit redundancy in their stabilizer generators [3].
Quantum low-density parity-check (QLDPC) code — Qubit QLDPC codes satisfying linear confinement are single shot [5]. Any code that admits a local greedy decoder also satisfies linear confinement, and so is single shot [11].
Quantum data-syndrome (QDS) code — QDS codes contain redundancy in their stabilizer generators so as to protect from syndrome measurement errors.
Homological product code — It is conjectured that a particular class of codes called three-dimensional product codes is single shot [5].
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 [3].
Hyperbolic surface code — A 4D hyperbolic surface code can be decoded with the Hastings decoder [12] in time \(O(n\log n)\) and with a logical error scaling inverse polynomially with \(n\).
3D subsystem color code — The 3D subsystem color code defined on the cube-truncated rhombic dodecahedral honeycomb, i.e., a tesselation of cubes and chamfered cubes (a.k.a. tetratruncated rhombic dodecahedra) [13; Fig. 1], is a single-shot code [2,13].
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. [14] for many examples of such codes. There is numerical evidence that a particular family is single shot [15].

References

[1]: E. Dennis et al., “Topological quantum memory”, Journal of Mathematical Physics 43, 4452 (2002) arXiv:quant-ph/0110143 DOI
[2]: H. Bombín, “Single-Shot Fault-Tolerant Quantum Error Correction”, Physical Review X 5, (2015) arXiv:1404.5504 DOI
[3]: E. T. Campbell, “A theory of single-shot error correction for adversarial noise”, Quantum Science and Technology 4, 025006 (2019) arXiv:1805.09271 DOI
[4]: 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
[5]: A. O. Quintavalle et al., “Single-Shot Error Correction of Three-Dimensional Homological Product Codes”, PRX Quantum 2, (2021) arXiv:2009.11790 DOI
[6]: 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
[7]: S. Gu et al., “Single-Shot Decoding of Good Quantum LDPC Codes”, Communications in Mathematical Physics 405, (2024) arXiv:2306.12470 DOI
[8]: 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
[9]: J. C. Bridgeman, A. Kubica, and M. Vasmer, “Lifting Topological Codes: Three-Dimensional Subsystem Codes from Two-Dimensional Anyon Models”, PRX Quantum 5, (2024) arXiv:2305.06365 DOI
[10]: C. Stahl, “Single-Shot Quantum Error Correction in Intertwined Toric Codes”, (2023) arXiv:2307.08118
[11]: Q. Xu et al., “Constant-Overhead Fault-Tolerant Quantum Computation with Reconfigurable Atom Arrays”, (2023) arXiv:2308.08648
[12]: M. B. Hastings, “Decoding in Hyperbolic Spaces: LDPC Codes With Linear Rate and Efficient Error Correction”, (2013) arXiv:1312.2546
[13]: 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
[14]: H.-K. Lin and L. P. Pryadko, “Quantum two-block group algebra codes”, (2023) arXiv:2306.16400
[15]: T. R. Scruby, T. Hillmann, and J. Roffe, “High-threshold, low-overhead and single-shot decodable fault-tolerant quantum memory”, (2024) arXiv:2406.14445

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.