Massachusetts Institute of Technology
When Qubits Go Analog
November 19, 2008 - 4:45-5:10pm
RLE Conference Center - 36-428
Hellman and Cover showed that to decide (with bounded error) whether a coin is fair or has bias epsilon, you need at least ~log(1/epsilon) bits of memory, even assuming an unlimited number of flips. I'll show how to do the same using two qubits, independent of epsilon. On the other hand, I'll also show that with s qubits of memory, you can learn at most s+log(s) bits about epsilon. In other words, quantum mechanics nullifies the Hellman-Cover Theorem, yet does not let you extract unlimited information from the bias of a coin.
Scott Aaronson is an Assistant Professor of EECS at MIT. He received his bachelor's from Cornell and his PhD in computer science from UC Berkeley, and has done postdocs at the Institute for Advanced Study and the University of Waterloo. His main research interest is quantum complexity theory.