Locally Decodable Quantum Codes

Briet, Jop; de Wolf, Ronald

doi:10.4230/LIPIcs.STACS.2009.1813

Document

Locally Decodable Quantum Codes

Authors Jop Briet, Ronald de Wolf

Part of: Volume: 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: Symposium on Theoretical Aspects of Computer Science (STACS)
License: Creative Commons Attribution-NoDerivs 3.0 Unported license
Publication Date: 2009-02-19

PDF

File

PDF

LIPIcs.STACS.2009.1813.pdf

Filesize: 187 kB
12 pages

Document Identifiers

DOI: 10.4230/LIPIcs.STACS.2009.1813
URN: urn:nbn:de:0030-drops-18134

Subject Classification

Keywords

Data structures
Locally decodable codes
Quantum computing

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

Abstract

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$.

Cite As Get BibTex

Jop Briet and Ronald de Wolf. Locally Decodable Quantum Codes. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 219-230, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009) https://doi.org/10.4230/LIPIcs.STACS.2009.1813

Author Details

Jop Briet

Ronald de Wolf

Any Issues?

Feedback on the Current Page

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail