Separating Quantum and Classical Learning.
R. Servedio.
28th International Conference on Automata, Languages and Programming (ICALP), 2001, pp. 1065-1080.


Abstract:

We consider a model of learning Boolean functions from {\em quantum membership queries}. This model was studied in \cite{ServedioGortler:00}, where it was shown that any class of Boolean functions which is information-theoretically learnable from polynomially many quantum membership queries is also information-theoretically learnable from polynomially many classical membership queries.

In this paper we establish a strong {\em computational} separation between quantum and classical learning. We prove that if any cryptographic one-way function exists, then there is a class of Boolean functions which is polynomial-time learnable from quantum membership queries but not polynomial-time learnable from classical membership queries. A novel consequence of our result is a quantum algorithm that breaks a general cryptographic construction which is secure in the classical setting.


Postscript or pdf.


Back to main papers page