Scott Aaronson

Massachusetts Institute of Technology

When Qubits Go Analog

November 19, 2008 - 4:45-5:10pm

RLE Conference Center - 36-428

Abstract

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.

Bio

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.