List Decodable Quantum LDPC Codes
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913573172674560 |
|---|---|
| author | Bergamaschi, Thiago Jeronimo, Fernando Granha Mittal, Tushant Srivastava, Shashank Tulsiani, Madhur |
| author_facet | Bergamaschi, Thiago Jeronimo, Fernando Granha Mittal, Tushant Srivastava, Shashank Tulsiani, Madhur |
| contents | We give a construction of Quantum Low-Density Parity Check (QLDPC) codes with near-optimal rate-distance tradeoff and efficient list decoding up to the Johnson bound in polynomial time. Previous constructions of list decodable good distance quantum codes either required access to a classical side channel or were based on algebraic constructions that preclude the LDPC property.
Our construction relies on new algorithmic results for codes obtained via the quantum analog of the distance amplification scheme of Alon, Edmonds, and Luby [FOCS 1995]. These results are based on convex relaxations obtained using the Sum-of-Squares hierarchy, which reduce the problem of list decoding the distance amplified codes to unique decoding the starting base codes. Choosing these base codes to be the recent breakthrough constructions of good QLDPC codes with efficient unique decoders, we get efficiently list decodable QLDPC codes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_04306 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | List Decodable Quantum LDPC Codes Bergamaschi, Thiago Jeronimo, Fernando Granha Mittal, Tushant Srivastava, Shashank Tulsiani, Madhur Information Theory Quantum Physics We give a construction of Quantum Low-Density Parity Check (QLDPC) codes with near-optimal rate-distance tradeoff and efficient list decoding up to the Johnson bound in polynomial time. Previous constructions of list decodable good distance quantum codes either required access to a classical side channel or were based on algebraic constructions that preclude the LDPC property. Our construction relies on new algorithmic results for codes obtained via the quantum analog of the distance amplification scheme of Alon, Edmonds, and Luby [FOCS 1995]. These results are based on convex relaxations obtained using the Sum-of-Squares hierarchy, which reduce the problem of list decoding the distance amplified codes to unique decoding the starting base codes. Choosing these base codes to be the recent breakthrough constructions of good QLDPC codes with efficient unique decoders, we get efficiently list decodable QLDPC codes. |
| title | List Decodable Quantum LDPC Codes |
| topic | Information Theory Quantum Physics |
| url | https://arxiv.org/abs/2411.04306 |