Associate Professor of Electrical Engineering and Computer Science, MIT
Scott Aaronson is an Associate Professor of Electrical Engineering and Computer Science at MIT. He received his Ph.D. in computer science from University of California, Berkeley and did postdocs at the Institute for Advanced Study and the University of Waterloo. Scott's research interests center around fundamental limits on what can efficiently be computed in the physical world. This has entailed studying quantum computing, the most powerful model of computation we have, based on known physical theory. Scott's work on this subject has included limitations of quantum algorithms in the black-box model; algorithms for quantum spatial search and for simulating restricted classes of quantum circuits; the learnability of quantum states; quantum versus classical proofs and advice; and
quantum computing with linear optics. He also writes a popular blog (www.scottaaronson.com/blog), and is the creator of the Complexity Zoo
(www.complexityzoo.com), an online encyclopedia of computational complexity theory.
Are there quantum states that (1) anyone can use to do
useful things (like perform computations, or verify statements), but
(2) no one can copy who doesn't know the secret of how they were
prepared? This question has been tantalizingly open ever since
Stephen Wiesner first raised the possibility of "quantum money" 40
years ago. After surveying the history of the problem, in this talk
I'll discuss some very recent progress (joint work with Paul
Christiano), including a classical oracle relative to which
unconditionally-secure, publicly-verifiable quantum money exists, and
a new proposal for an explicit quantum money scheme. If time permits,
I'll also discuss connections with the QMA vs. QCMA problem.