Quantum algorithms for testing properties of distributions - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2010

Quantum algorithms for testing properties of distributions

Résumé

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}).
Fichier principal
Vignette du fichier
bravyi.pdf (210.65 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00455782 , version 1 (11-02-2010)

Identifiants

  • HAL Id : inria-00455782 , version 1

Citer

Sergey Bravyi, Aram W. Harrow, Avinatan Hassidim. Quantum algorithms for testing properties of distributions. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Inria Nancy Grand Est & Loria, Mar 2010, Nancy, France. pp.131-142. ⟨inria-00455782⟩

Collections

STACS2010
86 Consultations
219 Téléchargements

Partager

Gmail Facebook X LinkedIn More