Research OverviewHere I will briefly describe some of my existing and ongoing projects.
Research GoalsMy 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 nearterm 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, Nonlocality, and SumofSquaresResearch on this topic studies many aspects of one of the key quantum features, entanglement and nonlocality. I attack this topic by exploring a surprising connection between quantum information and the sumofsquares (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 MerlinArthur games with unentangled provers (QMA(2)), the possibility of a quantuminspired approach to attack the UGC. Publications:
Tamperresilient Cryptography under Physical AssumptionsDevices, classical or quantum, are subject to tampering in cryptographic settings, especially due to the proliferation of sidechannel attacks. These attacks exploit the fact that de vices leak information to the outside world not just through inputoutput interaction, but through physical characteristics of computation such as power consumption, timing, and electromagnetic radiation. Research on this topic explores two possible solutions to protect cryptographic systems from (quantum) sidechannel attacks.
Both deviceindependent and leakageresilient cryptography can be deemed as tamperresilient cryptography under physical assumptions. My future plan is to bring these cryptographic designs closer to practice, with better efficiency and broader functionality. Publications:
Quantum Computational ComplexityInteractive 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 polynomialtime verifier and allpowerful 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 spaceefficient 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 kplayer games. Publications:
Provable Quantum Advantage in Property Testing, Monte Carlo Methods, Optimization, and Machine LearningIt is a fundamental question and a longterm 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 wellmotivated and timely for various reasons, and on the other side introduce new technical challenges that potentially request revolutionary techniques. Specifically, my ongoing research on this topic investigates the potential quantum advantage in property testing, Monte Carlo methods (over general domains), optimization (e.g., convex optimization, semidefinite programming, submodular optimization), and highdimensional geometrical problems in machine learning. Publications:
Theoretical Solutions to Quantum Engineering ProblemsMediumsize quantum devices are expected in the next five or ten years. My research aims to facilitate applications of mediumsize quantum devices via theoretical techniques. In an ongoing project, I study the possibility of simulating largescale quantum computation with limited resources that are expected to be available in the near future. A specific goal is, e.g., to perform 60qubit quantum computation with 40qubit quantum devices, which is already a significant advance for major applications of mediumsize 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 longstanding gap between the upper and lower bounds for quantum tomography. Publications:
Formal Methods and Programming Languages for Quantum Software, Hardware, and CryptographyFormal 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 ongoing 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:
