From Monogamy of Entanglement to Quantum Programming Languages: A Theorist’s Adventure in Quantum Wonderland

CS Seminar

Xiaodi Wu (University of Oregon)
March 9, 2017
AV Williams 4172
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.