BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Two-message quantum interactive proofs and the quantum separabilit
 y problem - Mark M. Wilde (McGill University)
DTSTART:20130118T130000Z
DTEND:20130118T140000Z
UID:TALK43074@talks.cam.ac.uk
CONTACT:Paul Skrzypczyk
DESCRIPTION:Suppose that a polynomial-time mixed-state quantum circuit\, d
 escribed as a sequence of local unitary interactions followed by a partial
  trace\, generates a quantum state shared between two parties. One might t
 hen wonder\, does this quantum circuit produce a state that is separable o
 r entangled? Here\, we give evidence that it is computationally hard to de
 cide the answer to this question\, even if one has access to the power of 
 quantum computation. We begin by exhibiting a two-message quantum interact
 ive proof system that can decide the answer to a promise version of the qu
 estion. We then prove that the promise problem is hard for the class of pr
 omise problems with "quantum statistical zero knowledge" (QSZK) proof syst
 ems by demonstrating a polynomial-time Karp reduction from the QSZK-comple
 te promise problem "quantum state distinguishability" to our quantum separ
 ability problem. By exploiting Knill's efficient encoding of a matrix desc
 ription of a state into a description of a circuit to generate the state\,
  we can show that our promise problem is NP-hard. Thus\, the quantum separ
 ability problem (as phrased above) constitutes the first nontrivial promis
 e problem decidable by a two-message quantum interactive proof system whil
 e being hard for both NP and QSZK. We consider a variant of the problem\, 
 in which a given polynomial-time mixed-state quantum circuit accepts a qua
 ntum state as input\, and the question is to decide if there is an input t
 o this circuit which makes its output separable across some bipartite cut.
  We prove that this problem is a complete promise problem for the class QI
 P of problems decidable by quantum interactive proof systems. Finally\, we
  show that a two-message quantum interactive proof system can also decide 
 a multipartite generalization of the quantum separability problem. 
LOCATION:MR14\, Centre for Mathematical Sciences
END:VEVENT
END:VCALENDAR