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— The same quantum 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
Page edit log
- Victor V. Albert (2023-01-08) — most recent
- Sam Gunn (2022-01-08)
Cite as:
“Singleton-bound approaching AQECC”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/quantum_singleton