PhD Comprehensive Seminar | Eric Culf, Connections between Entanglement and Complexity

M3 4206

Candidate

Eric Culf | Applied Mathematics, University of Waterloo

Title

Connections between Entanglement and Complexity

Abstract

Entanglement, a form of correlation arising from quantum mechanics, can be used to achieve stronger correlations than anything possible classically. This has had many consequences, notably that quantum systems can contain much greater complexity than comparable classical systems. I will present some of the questions that arise from this property, and my ongoing work to study them.

First, in classical complexity theory, there is no distinction between one or many proofs. However, if the proofs can be entangled, there may be a distinction. In work with Arthur Mehta, we studied a problem arising from quantum graphs that captures this distinction in a natural way.

Next, the expressive power of correlation scenarios, such as nonlocal games, is much increased when the provers share entanglement. However, the value of some scenarios, XOR nonlocal games, is actually much easier to find quantumly than classically. In work with Hamoon Mousavi and Taro Spirig, we developed approximation algorithms for nonlocal games, that show that there are games of intermediate complexity that are easy to approximate while being hard to solve exactly.

Finally, error-correcting codes for quantum systems are important in both theoretical study and applications. In particular, stabiliser states of codes form an important family of examples of entangled states. In ongoing work with Richard Cleve, we study the behaviour of stabiliser states in systems of infinitely-many qubits.