SCS Special Seminar

  • Remote Access - Zoom
  • Virtual Meeting - ET
  • Assistant Professor
  • Department of Computer Science
  • University of Texas at Austin


Quantum complexity theory gives us a powerful lens to study basic resources and properties that arise in quantum computing. One of the most beguiling of these is the mysterious phenomenon of quantum entanglement, in which two far-apart quantum systems can affect each other faster than the speed of light. To study this, researchers in 2004 introduced the complexity class MIP*, which connected entanglement to a classic notion in complexity theory known as multiprover interactive proofs. Since then, determining the power of MIP* has remained a major open problem in the field of quantum complexity theory.

In this talk, I will describe recent work giving a solution to this problem: MIP* = RE, the complexity class containing the halting problem and those languages which reduce to it. This shows that entanglement is a resource of almost unimaginable power, as it can be used to solve problems which are undecidable. The proof involves new techniques that allow a classical verifier to use entanglement to delegate increasingly complex computations to two quantum provers. I will also describe the deep and surprising connections that MIP* has to two other major open problems, Tsirelson's problem from entanglement theory and Connes' embedding problem from operator algebras, and show how my results lead to a resolution of both problems in the negative.

John Wright is an assistant professor in the Department of Computer Science at the University of Texas at Austin. He received his Ph.D. at Carnegie Mellon University, after which he did a postdoc at the Massachusetts Institute of Technology and another postdoc at the California Institute of Technology. His research focuses on quantum algorithms and quantum complexity theory, especially the complexity class MIP*. He was the recipient of a best paper award at FOCS 2019.

Faculty Host: David Woodruff

Computer Science Department

Zoom Participation. See announcement.

For More Information, Please Contact: