- Accueil »
- Quantum algorithm for Statistical Difference problem

Le contenu de cette page n’est pas disponible en français. Veuillez nous en excuser.

Playing this video requires the latest flash player from Adobe.

Download link (right click and 'save-as') for playing in VLC or other f4v compatible player.

Speaker(s):

Scientific Areas:

Collection/Series:

PIRSA Number:

09020008

Suppose we are given two probability distributions on some N-element set. How many samples do we need to test whether the two distributions are close or far from each other in the L_1 norm? This problem known as Statistical Difference has been extensively studied during the last years in the field of property testing. I will describe quantum algorithms for Statistical Difference problem that provide a polynomial speed up in terms of the query complexity compared to the known classical lower bounds. Specifically, I will assume that each distribution can be generated by querying an oracle function on a random uniformly distributed input string. It will be shown that testing whether distributions are orthogonal requires approximately N^{1/2} queries classically and approximately N^{1/3} queries quantumly. Testing whether distributions are close requires approximately N^{2/3} queries classically and O(N^{1/2}) queries quantumly. This is a joint work with Aram Harrow (University of Bristol) and Avinatan Hassidim (The Hebrew University).

©2012 Institut Périmètre de Physique Théorique