Research Overview

Here I will briefly describe some of my existing and on-going projects.

Research Goals

My research aims to contribute to the development of quantum information and computation through the study in theoretical computer science (complexity & algorithms), cryptography, and formal methods & programming languages. On one side, my research aims to study the impact of quantum mechanics on the theoretical foundation of computer science. On the other side, I am also aiming to provide solutions to challenges in the near-term quantum hardware and software research. My research is interdisciplinary in nature: many of my quantum projects are not only related to classical theoretical computer science topics, but also naturally connect to central topics in physics and mathematics.

Entanglement, Non-locality, and Sum-of-Squares

Research on this topic studies many aspects of one of the key quantum features, entanglement and non-locality. I attack this topic by exploring a surprising connection between quantum information and the sum-of-squares (SOS) proof in approximation algorithms and the famous Unique Games Conjecture (UGC). This connection allows one to leverage technical advances in one field to apply to the other. Specific problems that I am working on includes the characterization of separable (unentangled) states, the complexity of quantum Merlin-Arthur games with unentangled provers (QMA(2)), the possibility of a quantum-inspired approach to attack the UGC.

Publications:

  • Limitations of semidefinite programs for separable states and entangled games. Aram Harrow, Anand Natarajan, Xiaodi Wu. QIP 2017.

  • Tight SoS-degree bounds for approximate Nash equilibria. Aram Harrow, Anand Natarajan, Xiaodi Wu. CCC 2016.

  • An improved semidefinite programming hierarchy for testing entanglement. Aram Harrow, Anand Natarajan, Xiaodi Wu. Communications in Mathematical Physics, June 2017, Volume 352, Issue 3, pp 881– 904.

  • Epsilon-net method for optimizations over separable states. Yaoyun Shi and Xiaodi Wu. QIP 2012, ICALP 2012. Theoretical Computer Science, Volume 598, Pages 51–63.

Tamper-resilient Cryptography under Physical Assumptions

Devices, classical or quantum, are subject to tampering in cryptographic settings, especially due to the proliferation of side-channel attacks. These attacks exploit the fact that de- vices leak information to the outside world not just through input-output interaction, but through physical characteristics of computation such as power consumption, timing, and electro-magnetic radiation. Research on this topic explores two possible solutions to protect cryptographic systems from (quantum) side-channel attacks.

  • Device-independent Cryptography: In this setting, none of the devices can be a priori trusted: security is based solely on simple tests performed by the honest users on the input-output behavior of their devices. The security analysis guarantees that any set of devices meeting reasonable physical assumptions (e.g., spatial separations of devices that prohibit mutual communication) and conducting an acceptable interaction will lead to a secure outcome, regardless of the actual process inside the devices. My research focuses on generating uniform random bits in this setting under minimal assumptions. Check the recent review in Nature (Certified randomness in quantum physics) about this research direction and my work.

  • Leakage-resilient Cryptography: Modern computing environment, such as cloud computing where computation no long takes place on private machines under our control, makes a lot of classical cryptographic systems victims to all kinds of side-channel attacks. The leakage can be quantum. Collecting and storing quantum side information is technically much less challenging than building fully-fledged quantum computers, and could become realistic in the near future. My research focuses on studying the role of quantum side information in both information-theoretical and computational setting. In a recent result, I initiated the study of computational notions of entropy in the quantum setting and developed the first quantum leakage-resilient cryptographic protocol.

Both device-independent and leakage-resilient cryptography can be deemed as tamper-resilient cryptography under physical assumptions. My future plan is to bring these cryptographic designs closer to practice, with better efficiency and broader functionality.

Publications:

  • Computational Notions of Quantum Min-Entropy. Yi-Hsiu Chen, Kai-Min Chung, Ching-Yi Lai, Salil P. Vadhan, and Xiaodi Wu. arXiv: 1704.07309.

  • General randomness amplification with non-signaling security. Kai-Min Chung, Yaoyun Shi, and Xiaodi Wu. QIP 2017.

  • Multi-Source Randomness Extractors Against Quantum Side Information, and their Applications. Kai-Min Chung, Xin Li, and Xiaodi Wu. arXiv:1411.2315.

  • Physical Randomness Extractors. Kai-Min Chung, Yaoyun Shi, and Xiaodi Wu. Plenary talk at QIP 2014.

Quantum Computational Complexity

Interactive proof systems have been a central model in complexity theory with applications ranging from the PCP theorem in hardness of approximation to cryptography. It studies problems with efficiently verifiable proofs via interactions between a polynomial-time verifier and all-powerful provers, where the verifier determines the validity of the proofs. My main contribution on this topic is the development of the Equilibrium Value Method to obtain space-efficient simulations of quantum interactive proof systems, including QIP=PSPACE, QRG(2)=PSPACE. Recently, I have been working on the quantum variant of the PCP theorem in the interactive proof setting. As a concrete first step, I have obtained a parallel repetition result for entangled k-player games.

Publications:

  • Parallel repetition for entangled k-player games via fast quantum search. Kai-Min Chung, Xiaodi Wu and Henry Yuen. CCC 2015.

  • Epsilon-net method for optimizations over separable states. Yaoyun Shi and Xiaodi Wu. QIP 2012, ICALP 2012. Theoretical Computer Science, Volume 598, Pages 51?63.

  • Parallel approximation of min-max problems with applications to classical and quantum zero-sum games Gus Gutoski and Xiaodi Wu. QIP 2012, CCC 2012. Computational Complexity, 22(2):385-428, 2013, the special issue of CCC 2012.

  • Equilibrium Value Method for the proof of QIP=PSPACE. Xiaodi Wu . arXiv:1004.0264.

Provable Quantum Advantage in Property Testing, Monte Carlo Methods, Optimization, and Machine Learning

It is a fundamental question and a long-term pursuit to establish quantum advantage in algorithms that goes beyond the techniques in Grover's and Shor's algorithms. I adopt a humble approach to tackle this ultimate goal. In particular, I am fascinated by a few emerging topics which, on one side, are well-motivated and timely for various reasons, and on the other side introduce new technical challenges that potentially request revolutionary techniques. Specifically, my on-going research on this topic investigates the potential quantum advantage in property testing, Monte Carlo methods (over general domains), optimization (e.g., convex optimization, semi-definite programming, sub-modular optimization), and high-dimensional geometrical problems in machine learning.

Publications:

  • Quantum query complexity of entropy estimation. Tongyang Li and Xiaodi Wu. arXiv: 1710.06025.

  • Quantum SDP Solvers: Large Speed-ups, Optimality, and Applications to Quantum Learning. Fernando G. S. L. Brandao, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu. arXiv: 1710.02581v2.

Theoretical Solutions to Quantum Engineering Problems

Medium-size quantum devices are expected in the next five or ten years. My research aims to facilitate applications of medium-size quantum devices via theoretical techniques. In an on-going project, I study the possibility of simulating large-scale quantum computation with limited resources that are expected to be available in the near future. A specific goal is, e.g., to perform 60-qubit quantum computation with 40-qubit quantum devices, which is already a significant advance for major applications of medium-size quantum machines, such as quantum simulation or quantum supremacy. My ultimate goal is to build a theoretical foundation for this purpose, which could be valuable to both theorists as well as experimentalists and engineers. In a recent project, I have also closed a long-standing gap between the upper and lower bounds for quantum tomography.

Publications:

  • Simulating large quantum circuits on a small quantum computer. Aram Harrow, Maris Ozols, Tianyi Peng, and Xiaodi Wu. Manuscript, 2016.

  • Sample-optimal tomography of quantum states. Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, Nengkun Yu. QIP 2016 and STOC 2016.

Formal Methods and Programming Languages for Quantum Software, Hardware, and Cryptography

Formal methods and programming languages have been the cornerstone in software and hardware engineering. In particular, they provide appropriate mathematically based techniques for the specification, development, and verification of software and hardware systems. It won't be surprised at all that these methods will play important roles in quantum systems. This is a timely and exciting direction. In particular, my research on this topic aims to contribute to the formal method for quantum software, hardware, and cryptography. In a recent result, I made the first attempt to define the notion of invariant and to develop a method of invariant generation for quantum programs. My on-going projects include (1) theory of quantum programming languages, (2) verifiable compliers of quantum programs with optimization of hardware factors (e.g., architectural constraints, error, and relevant resources), and (3) automatic verification of the security of classical protocols against quantum attacks.

Publications:

  • Invariants of Quantum Programs: Characterizations and Generation. Mingsheng Ying, Shenggang Ying, and Xiaodi Wu. POPL 2017.