Events Calendar

How Hard is it to Decide if a Quantum State is Separable or Entangled?

Speaker: Mark M. Wilde, McGill University

Talk Title: How Hard is it to Decide if a Quantum State is Separable or Entangled?

Abstract: Suppose that a physical process, described as a sequence of local interactions that can be executed in a reasonable amount of time, generates a quantum state shared between two parties. We might then wonder, does this physical process produce a quantum state that is separable or entangled? Here, we give evidence that it is computationally hard to decide the answer to this question, even if one has access to the power of quantum computation. In order to address this question, we begin by demonstrating a two-message quantum interactive proof system that can decide the answer to a promise version of this problem. We then prove that this promise problem is hard for the class ``quantum statistical zero knowledge'' (QSZK) by demonstrating a polynomial-time reduction from the QSZK-complete promise problem ``quantum state distinguishability'' to our quantum separability problem. Thus, the quantum separability problem (as phrased above) constitutes the first nontrivial promise problem decidable by a two-message quantum interactive proof system while being hard for both NP and QSZK. This is joint work with Patrick Hayden and Kevin Milner, it will be presented at the 2013 IEEE Conference on Computational Complexity, and it is available as arXiv:1211.6120.

Biography: Mark M. Wilde received the Ph.D. degree in electrical engineering from the University of Southern California, Los Angeles, California, in 2008. Until recently, he has been a Postdoctoral Fellow at the School of Computer Science, McGill University, and he will start in August 2013 as an Assistant Professor in the Department of Physics and Astronomy and the Center for Computation and Technology at Louisiana State University. He is the author of the text "Quantum Information Theory" which will soon be published by Cambridge University Press. His current research interests are in quantum Shannon theory, quantum optical communication, quantum computational complexity theory, and quantum error correction.

Host: Todd Brun, x03503, tbrun@usc.edu

Location: Frank R. Seaver Science Center (SSC) - 319

Audiences: Everyone Is Invited

Contact: Gerrielyn Ramos