[quantum-info] Seminar IQC - Thursday, 19 June 2014 at 11:45AM

[Matthew Fries]

Seminar

Institute for Quantum Computing

Thursday, 19 June 2014 at 11:45AM

QNC 0101

Physical Randomness Extractors

Yaoyun Shi

University of Michigan

How can one be certain that the output of an alleged random number generator is indeed random? This question is important not only for the efficiency and the security of information processing, but also for understanding how intrinsically unpredictable events are possible in Nature. Practical random number generators have often been found to be insecure. All existing theoretical solutions require a certain form of independence among two or more sources of randomness, a condition impossible to test and difficult to guarantee.

In this talk, I will show how this fundamental limit can be circumvented by extractors that base security on the validity of physical laws. In conjunction with the recent work of Miller and Shi (arXiv:1402.0489), our "physical extractor" uses just a single and arbitrarily weak source, produces an arbitrarily long and near-uniform output, secure against all-powerful quantum adversaries, tolerating a constant level of implementation imprecision, with a near-optimal error. Our method enables practical provably secure random number generation with minimal assumptions. It also implies that unless the world is deterministic, we can experimentally create arbitrarily many, inherently random events and be confident of their unpredictability. I will conclude with several major open problems on this new paradigm of randomness extraction.

Joint work with Kai-Min Chung and Xiaodi Wu (arXiv:1402.4797).

About the speaker: Yaoyun Shi received his Bachelor's degree from Beijing University in 1997 and his PhD from Princeton University in 2001, both in Computer Science. He was a postdoc at the Institute of Quantum Information at Caltech and is currently an Associate Professor at the University of Michigan, Ann Arbor. His research focuses on the theory of quantum information processing.