[quantum-info] IQC Mar 11 Colloquium

[Matthew Fries]

Colloquium

Institute for Quantum Computing

Monday, 11 March 2013 at 2:30PM

QNC 1103

Three quantum learning algorithms

Ashley Montanaro

University of Cambridge

In this talk I will discuss three optimal, and varied, quantum learning algorithms. First, I will present recent work on a problem dubbed "search with wildcards". Here we wish to learn an unknown bit-string, given the ability to determine whether arbitrary subsets of the bits are equal to a provided query string. I will present a quantum algorithm for this task which is based on novel ingredients and achieves a quadratic speed-up over any possible classical algorithm.
The second algorithm I will discuss is a generalisation of one of the earliest algorithms in quantum computing, the Bernstein-Vazirani algorithm for learning linear functions over the finite field F_2. I will present an exact quantum algorithm which learns n-variate multilinear polynomials over arbitrary finite fields and achieves an O(n) speed-up over any possible classical algorithm.

The final result is an algorithm for a purely quantum task: learning stabilizer states. In this problem, we are given access to a number of copies of an unknown stabilizer state of n qubits, and would like to identify the state. I will present an efficient algorithm for this task which uses O(n) copies of the state, which is optimal and represents an exponential improvement over standard tomography.

This talk is based on the papers arXiv:1210.1148 (joint work with Andris Ambainis), arXiv:1105.3310, and ongoing joint work with Scott Aaronson, David Chen, Daniel Gottesman and Vincent Liew.