Colloquium Details
The Power and Limits of Quantum Computers
| Author: | Xiaodi Wu, Postdoctoral Associate Massachusetts Institute of Technology (MIT) |
|---|---|
| Date: | February 26, 2015 |
| Time: | 15:30 |
| Location: | 220 Deschutes |
Abstract
The possibility of quantum computers, especially its power to break cryptographic systems and to provide efficient physical simulation, has attracted significant interest from academia, industry and governments. But how powerful are quantum computers? And what are their limits? In this talk, I’ll highlight my contributions to both sides of this fundamental question.
On the power side, I’ve constructed the first random number generator (RNG) whose security solely relies on the validity of quantum mechanics. Specifically, our RNG produces an arbitrarily long and near-uniform output that is secure against computationally unbounded adversaries limited only by the laws of quantum mechanics, even if the RNG was manufactured by a malicious adversary. Moreover, our RNG uses technology much simpler than that required for a universal quantum computer and is within the realm of practicality.
On the limits side, I’ve developed a general framework that shows quantum machines cannot improve the computational power of a central model in complexity theory, called the interactive proof system. As a surprising byproduct, my framework also yields efficient classical parallel algorithms for a large class of optimization problems.
Biography
Xiaodi Wu is a postdoctoral associate at MIT working on theoretical computer science, with a focus on quantum computation. He was also a Simons research fellow at the Simons institute for the theory of computing, University of California, Berkeley in the Spring of 2014. Before that, he obtained his Ph.D. degree from the University of Michigan, Ann Arbor in 2013, and his B.S. degree from Tsinghua University in 2008.
His work has appeared as plenary and featured talks at QIP, the most prestigious conference in theoretical aspects of quantum information science, as well as leading theory of computing conferences.