Theory Lunch/Seminar -------------------- TIME:: Wednesday, Dec. 12, noon till 1pm PLACE:: 7220 Wean Hall TITLE:: Quantum Versus Classical Learning SPEAKER:: Rocco Servedio, Harvard University ABSTRACT:: 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 box? 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 Gortler.