A Visitor

For those of you local to Seattle, Scott Aaronson, keeper of the complexity zoo, will be giving a talk this Thursday:

Event: Colloquium, 05/25/2006 11:30 am, Gates Commons, CSE 691
Speaker: Scott Aaronson (University of Waterloo)
Talk: The Learnability of Quantum States
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