Singleton-bound approaching AQECC[1]
Description
A member of an approximate quantum code family of rate \(R\) that can tolerate adversarial errors nearly saturating the quantum Singleton bound of \((1-R)/2\). The formulation of such codes relies on a notion of quantum list decoding [1,2].
One construction first builds constant-alphabet quantum list-decodable CSS codes from folded quantum Reed-Solomon outer codes, random CSS inner codes, and quantum Alon-Edmonds-Luby distance amplification/alphabet reduction, and then compiles them into AQECCs using purity-testing codes and robust secret sharing [1]. The resulting codes are efficiently encodable and decodable, and descriptions of the codes can be sampled by an efficient randomized algorithm with \(2^{-\Omega(n)}\) failure probability.
Protection
For any \(\gamma>0\) and rate \(0<R<1\), these approximate quantum \([[n,R \cdot n]]_q\) codes have constant Galois-qudit dimension \(q=2^{O(1/\gamma^5)}\) and correct errors acting on \((1-R-\gamma) \cdot n/2\) registers, up to a recovery error of \(2^{-\Omega(n)}\) [1].Rate
For any target rate \(R\in(0,1)\), codes can tolerate adversarial errors on nearly a \((1-R)/2\) fraction of registers while keeping constant alphabet size [1].Encoding
Efficient encoding.Decoding
Efficient decoder based on quantum list decoding together with purity-testing and robust-secret-sharing post-processing [1].Cousins
- Quantum maximum-distance-separable (MDS) code— Singleton-bound approaching AQECCs asymptotically approach the quantum Singleton bound, rather than exactly saturating it at finite blocklength.
- Folded quantum RS (FQRS) code— Singleton-bound approaching AQECCs are built using folded quantum Reed-Solomon (FQRS) codes [1].
- Approximate secret-sharing code— Quantum secret-sharing codes have asymptotically decaying rate and require qudit dimension to increase exponentially with \(n\), while Singleton-bound approaching AQECCs have constant rate and qudit dimension.
- Good QLDPC code— AEL distance amplification [3,4] can be used to construct constant-alphabet QLDPC CSS codes of any target rate \(R\) and relative distance \((1-R-\gamma)/2\) that are decodable in linear time up to half that distance [1; Corr. 5.3]. The AEL distance-amplification framework also yields constant-alphabet approximate quantum codes that decode nearly up to the quantum Singleton bound [1].
Primary Hierarchy
References
- [1]
- T. Bergamaschi, L. Golowich, and S. Gunn, “Approaching the Quantum Singleton Bound with Approximate Error Correction”, (2022) arXiv:2212.09935
- [2]
- D. Leung and G. Smith, “Communicating over adversarial quantum channels using quantum list codes”, (2007) arXiv:quant-ph/0605086
- [3]
- N. Alon, J. Edmonds, and M. Luby, “Linear time erasure codes with nearly optimal recovery”, Proceedings of IEEE 36th Annual Foundations of Computer Science 512 DOI
- [4]
- N. Alon and M. Luby, “A linear time erasure-resilient code with nearly optimal recovery”, IEEE Transactions on Information Theory 42, 1732 (1996) DOI
Page edit log
- Victor V. Albert (2026-06-08) — most recent
- Victor V. Albert (2023-01-08)
- Sam Gunn (2022-01-08)
Cite as:
“Singleton-bound approaching AQECC”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/quantum_singleton, arXiv:2606.11484