Theory Lunch/Seminar

TIME:: Wednesday, Dec. 12, noon till 1pm

PLACE:: 7220 Wean Hall

TITLE::  Quantum Versus Classical Learning

SPEAKER::  Rocco Servedio, Harvard University


Consider the following hypothetical scenario: you are charged with the 
task of extracting information from a "black-box" oracle which computes 
some unknown function. You can present inputs to the black box and 
receive the value of the function on those inputs, but have no other way 
of gathering information about the unknown function. Your mission is to 
obtain a complete description of the function computed by the black box, 
i.e. to exactly learn the unknown function.

In the classical setting this problem has been studied by researchers in 
computational learning theory and is fairly well understood. This talk 
will consider the following question: does learning the unknown function 
become (substantially) easier if you are dealing with a *quantum* black 

We'll see that the answer is both yes and no depending on how we measure 
the difficulty of learning. First we'll show that the number of queries 
which need to be made to the black box is roughly the same in the 
classical and quantum models (up to a polynomial factor); so from a query 
complexity perspective quantum learning is not substantially easier than 
classical learning. 

However, we'll also show that from a computational complexity perspective 
-- how much computation do we need to do in order to construct the desired 
description of the black-box function? -- the quantum learning model can 
have a superpolynomial advantage over the classical model. This 
computational separation relies only on general cryptographic assumptions 
(the existence of any one-way function).

The talk will be self-contained and does not presuppose any background in 
quantum computation. Part of this work was done jointly with Steven