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.