Quantum algorithms for testing properties of distributions

Sergey Bravyi 1 Aram W. Harrow 2, 3 Avinatan Hassidim 3
1 IBM Watson Research Center
2 Department of Mathematics [Bristol]
3 MIT - Massachusetts Institute of Technology
Abstract : Suppose one has access to oracles generating samples from two unknown probability distributions P and Q on some N-element set. How many samples does one need to test whether the two distributions are close or far from each other in the L_1-norm ? This and related questions have been extensively studied during the last years in the field of property testing. In the present paper we study quantum algorithms for testing properties of distributions. It is shown that the L_1-distance between P and Q can be estimated with a constant precision using approximately N^{1/2} queries in the quantum settings, whereas classical computers need \Omega(N) queries. We also describe quantum algorithms for testing Uniformity and Orthogonality with query complexity O(N^{1/3}). The classical query complexity of these problems is known to be \Omega(N^{1/2}).
Keywords : quantum computing property testing sampling
Type de document :
Communication dans un congrès
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.131-142, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00455782
Contributeur : Publications Loria <>
Soumis le : jeudi 11 février 2010 - 11:08:54
Dernière modification le : jeudi 11 février 2010 - 11:16:07
Document(s) archivé(s) le : vendredi 18 juin 2010 - 20:11:45

Fichier

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

Identifiants

  • HAL Id : inria-00455782, version 1

Collections

STACS2010

Citation

Sergey Bravyi, Aram W. Harrow, Avinatan Hassidim. Quantum algorithms for testing properties of distributions. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.131-142, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00455782〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

155

Téléchargements de fichiers

98

Contact


archive-ouverte@inria.fr