Title: Quartic quantum speedups for planted inference
| Speaker: | Ryan O'Donnell |
| Affiliation: | CMU |
| Location: | MC 5501 |
Abstract: Consider the following task ("noisy 4XOR"), arising in CSPs, optimization, and cryptography. There is a 'secret' Boolean vector x in {-1,+1}^n. One gets m randomly chosen pairs (S, b), where S is a set of 4 coordinates from [n] and b is x^S := prod_{i in S} x_i with probability 1-eps, and -x^S with probability eps. Can you tell the difference between the cases eps = 0.1 and eps = 0.5?
It depends on m. The best known algorithms use the "Kikuchi method" and run in time ~n^L when m ~ n^2/L. We will review this method, and also show that the running time can be improved to roughly n^{L/4} with a quantum computer. Most of the talk will be about the Kikuchi method, and almost no background on quantum computing will be assumed.
Joint work with Alexander Schmidhuber (MIT), Robin Kothari (Google), and Ryan Babbush (Google).
There will be a reception following the seminar in MC 5511.