Quantum locally recoverable code (QLRC)[1]
Description
A QLRC of locality \(r\) is a block quantum code whose code states can be recovered after a single erasure by performing a recovery map on at most \(r\) subsystems.
Protection
A Singleton-like QLRC bound states that an \(((n,K,d))_q\) QLRC of locality \(r\) and rate \(R = \frac{\log_q K}{n}\) must have relative distance [1; Thm. 4] \begin{align} \delta = \frac{d}{n} \leq \frac{1-R}{2} - \Omega\left(\frac{1}{r}\right)~, \tag*{(1)}\end{align} implying that locality restricts the distance of the code. Random QLRCs with qudit dimension \(q = 2^{O(r)}\) achieve a relative distance that is order \(O(1/r)\) below the bound [1; Prop. 5]. Codes constructed with the help of AEL distance amplification [2,3] admit a gap of order \(O(1/r^{1/4})\) [1; Prop. 6].
Decoding
Parent
Children
- Quantum LDPC (QLDPC) code — QLDPC codes are stabilizer QLRCs whose locality \(r \leq w\), the maximum number of subsystems that a stabilizer generator participates in [1].
- Quantum Tamo-Barg (QTB) code — Folded versions of QTB codes defined on qudits of dimension \(q = n^{O(r^2)}\) yield explicit examples of QLRCs of arbitrary locality \(r\) [1; Thm. 2].
Cousins
- Locally recoverable code (LRC)
- Galois-qudit CSS code — A Galois-qudit CSS code is a QLRC of locality \(r\) if each qudit participates in at least one \(X\)-type and one \(Z\)-type stabilizer whose product is of weight \(\leq r\) [1; Corr. 34].
- Random quantum code — Random QLRCs with qudit dimension \(q = 2^{O(r)}\) achieve a relative distance that is order \(O(1/r)\) below the Singleton-like QLRC bound [1; Prop. 5].
- Locally decodable code (LDC) — There are quantum versions of LDCs, but they can be transformed into LDCs which can be decoded well on average [4].
- Locally correctable code (LCC) — There is not a natural quantum version of LCCs [1; Thm. 9].
References
- [1]
- L. Golowich and V. Guruswami, “Quantum Locally Recoverable Codes”, (2023) arXiv:2311.08653
- [2]
- N. Alon, J. Edmonds, and M. Luby, “Linear time erasure codes with nearly optimal recovery”, Proceedings of IEEE 36th Annual Foundations of Computer Science DOI
- [3]
- N. Alon and M. Luby, “A linear time erasure-resilient code with nearly optimal recovery”, IEEE Transactions on Information Theory 42, 1732 (1996) DOI
- [4]
- J. Briët and R. de Wolf, “Locally Decodable Quantum Codes”, (2008) arXiv:0806.2101
Page edit log
- Victor V. Albert (2024-03-26) — most recent
Cite as:
“Quantum locally recoverable code (QLRC)”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/quantum_locally_recoverable