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

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,, and for background reading.