2026-07-20T11:16:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1813 2024-03-06T10:33:10Z ddc:004 open_access

Locally Decodable Quantum Codes Briet, Jop de Wolf, Ronald Data structures Locally decodable codes Quantum computing We study a quantum analogue of locally decodable error-correcting codes. A $q$-query \emph{locally decodable quantum code} encodes $n$ classical bits in an $m$-qubit state, in such a way that each of the encoded bits can be recovered with high probability by a measurement on at most $q$ qubits of the quantum code, even if a constant fraction of its qubits have been corrupted adversarially. We show that such a quantum code can be transformed into a \emph{classical} $q$-query locally decodable code of the same length that can be decoded well on average (albeit with smaller success probability and noise-tolerance). This shows, roughly speaking, that $q$-query quantum codes are not significantly better than $q$-query classical codes, at least for constant or small $q$. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jop Briet and Ronald de Wolf 2009 Is Part Of LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2009.1813 urn:nbn:de:0030-drops-18134 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1813 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode