Mark Wilde - Applying Quantum Information-Theoretic Techniques to Quantum Computational Complexity

Quantum Computation in Isolation virtual seminar on May 11th. Mark Wilde, Louisiana State University- Applying Quantum Information-Theoretic Techniques to Quantum Computational Complexity The main goal of quantum computational complexity theory is to understand the fundamental limits of computation, and the main goal of quantum information theory is to understand the fundamental limits of communication. These two fields are inevitably intertwined, given that every computational device typically makes use of communication in a non-trivial way and vice versa. In this talk, I’ll show several ways in which we can use concepts from quantum information theory to address problems of interest in quantum complexity, focusing for the main part on the quantum interactive proof model of computation. The main concrete results I’ll discuss are the complexity of entanglement, the complexity of recoverability of tripartite quantum states, and the complexity of testing symmetry. See https://arxiv.org/abs/1211.6120, https://arxiv.org/abs/1308.5788, and https://arxiv.org/abs/1512.05324 for background reading.