log in  |  register  |  feedback?  |  help  |  web accessibility
Logo
From Monogamy of Entanglement to Quantum Programming Languages: A Theorist’s Adventure in Quantum Wonderland
Xiaodi Wu - University of Oregon
Thursday, March 9, 2017, 11:00 am-12:00 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)
Abstract

Recent years have witnessed a rapid development of quantum information technologies. In this talk, I will describe my personal strategies on how to contribute to this exciting field as a theorist and how my own research fits in the big picture. 

In particular, I will talk about my research on a central feature of quantum information, called the monogamy of entanglement, and how it makes impact on classical theoretical computer science and cryptography. Specifically, I will describe its surprising connection to the sum-of-squares (SOS) optimization, the Unique Games Conjecture (UGC) in approximation algorithms, and the approximate Nash equilibria (ANE) problem. By leveraging this connection in both ways, I have derived the state-of-the-art upper and lower bounds for entanglement detection (i.e., the separability problem) and provided an evidence supporting the UGC. The techniques developed therein have also led to a tight quasi-polynomial complexity of the SOS approach to solving the ANE problem, an evidence supporting ANE being NP-intermediate. I will also illustrate how one can utilize the monogamy of entanglement to generate an infinite amount of near perfect randomness under minimal assumptions. This works in the device-independent cryptographic scenario where the security can be established without any trust of the devices, an impossible task in the classical world. 

Finally, I will briefly mention about my recent projects on developing fundamental tools for the verification of quantum programs, an important topic in quantum programming languages and a prerequisite for quantum software.

Bio

Xiaodi Wu is an assistant professor in the Computer and Information Science Department at the University of Oregon, working on quantum information and computation, quantum cryptography, and quantum programming languages. Before coming to Oregon, he was a postdoc at MIT and a Simons Research Fellow at UC Berkeley. He received his Ph.D. in theoretical computer science from the University of Michigan in 2013 and his B.S. in mathematics and physics from Tsinghua University in 2008.

This talk is organized by Adelaide Findlay