TIME: 12:00-12:50 pm,  Thursday, May 25, 2006

PLACE: CSE 691 (Gates Commons)

TITLE: The Learnability of Quantum States

SPEAKER:  Scott Aaronson 
          University of Waterloo

ABSTRACT:
Using ideas from computational learning theory, I'll show that "for
most practical purposes," one can learn a quantum state using a number
of measurements that grows only linearly with the number of qubits n.
By contrast, traditional quantum state tomography requires a number of
measurements that grows exponentially with n.  I'll then give two
applications of this learning theorem to quantum computing: first, the
use of trusted classical advice to verify untrusted quantum advice,
and second, a new simulation of quantum one-way protocols.

Even though there exists an algorithm to "learn" a quantum state after
a small number of measurements, that algorithm might not be efficient
computationally.  As time permits, I'll discuss ongoing work on how to
exploit that fact to copy-protect and obfuscate quantum software.