Locally Decodable Quantum Codes

Abstract : We study a quantum analogue of locally decodable error-correcting codes. A q-query local ly 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 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.
Type de document :
Communication dans un congrès
Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.219-230, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [5 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00359198
Contributeur : Publications Loria <>
Soumis le : vendredi 6 février 2009 - 11:50:11
Dernière modification le : mercredi 20 décembre 2017 - 17:42:07
Document(s) archivé(s) le : mardi 8 juin 2010 - 19:12:13

Fichiers

briet_new.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00359198, version 1
  • ARXIV : 0806.2101

Collections

Citation

Jop Briët, Ronald De Wolf. Locally Decodable Quantum Codes. Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.219-230, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00359198〉

Partager

Métriques

Consultations de la notice

83

Téléchargements de fichiers

95