[talks] Colloquium Speaker Umesh Vazirani, Tues March 27- 4:30pm
Nicole E. Wagenblast
nwagenbl at CS.Princeton.EDU
Fri Mar 23 09:15:38 EDT 2012
Certifiable Quantum Dice
Umesh Vazirani , University of California, Berkeley
Tuesday, March 27 4:30pm
Computer Science Small Auditorium (Room 105)
A source of independent and uniform random bits is a basic resource in many computational tasks, such as cryptography, game theoretic protocols, algorithms and physical simulations. In the classical world it is impossible to construct a random number generator whose output can be certified to be a uniformly random n-bit string, since there seems to be no basis on which to reject any particular output in favor of any other. Quantum mechanics allows for a remarkable random number generator: its output is certifiably random in the sense that if the output passes a simple statistical test, and a no-signaling condition is met between the two boxes in the randomness generating device (based, say, on the speed of light limit imposed by special relativity), even a quantum skeptic (viz Einstein's famous quote ``God does not play dice with the Universe''), would be convinced that the output is truly random, independent of the validity of quantum mechanics. Based on joint work with Thomas Vidick.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the talks