Institute for Quantum Information Seminar

Semidefinite programming (SDP) is a powerful technique from both an analytic and computational point of view for optimization problems.  It is also intimately related to quantum computation, as many optimization problems over density operators (quantum states) could be naturally formulated as SDPs.  

In spite of the existence of polynomial time solvers for general SDPs (e.g., interior point method), the black-box use of these solvers is, however, unsatisfactory for many purposes. For instance, the lack of explicitness makes it hard to adapt (or optimize) these solvers for special instances of SDPs.  Moreover, these polynomial time solvers provide no guarantee when one requires stronger efficiency, such as space efficiency (or equivalently, efficient computability by a parallel machine).  

In this talk, I will present a new approach called "Equilibrium Value Method" (EVM) that provides an explicit and time/space efficient solution to a substantial class of SDPs, which, in particular, includes many examples that arise naturally in quantum computation. The main idea behind EVM is to characterize the procedure to solve a SDP as a zero-sum game, in which one player tries to provide an optimal solution of the SDP while the other player tries to find anything wrong with that solution.

I will focus on the main application of EVM, which serves as a way to obtain PSPACE upper bounds of quantum complexity classes. First, I will show how EVM could lead to a simple and intuitive alternative proof to the recent celebrated result QIP=PSPACE. Second, I will illustrate how EVM could extend to a much more general setting, by proving that the quantum refereed games (i.e., the competing-prover variant of QIP) with two turns (QRG(2)) coincide with PSPACE.  

I will also talk about a few additional features of this approach and discuss a little bit about how it can extend to convex optimizations beyond SDPs. No background on either SDP or computational complexity will be assumed.

Based on results by myself and a joint result with Gus Gutoski (IQC, U Waterloo).