BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:CQIF Seminar
SUMMARY:Two-message quantum interactive proofs and the qua
ntum separability problem - Mark M. Wilde (McGill
University)
DTSTART;TZID=Europe/London:20130118T130000
DTEND;TZID=Europe/London:20130118T140000
UID:TALK43074AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/43074
DESCRIPTION:Suppose that a polynomial-time mixed-state quantum
circuit\, described as a sequence of local unitar
y interactions followed by a partial trace\, gener
ates a quantum state shared between two parties. O
ne might then wonder\, does this quantum circuit p
roduce a state that is separable or entangled? Her
e\, we give evidence that it is computationally ha
rd to decide the answer to this question\, even if
one has access to the power of quantum computatio
n. We begin by exhibiting a two-message quantum in
teractive proof system that can decide the answer
to a promise version of the question. We then prov
e that the promise problem is hard for the class o
f promise problems with "quantum statistical zero
knowledge" (QSZK) proof systems by demonstrating a
polynomial-time Karp reduction from the QSZK-comp
lete promise problem "quantum state distinguishabi
lity" to our quantum separability problem. By expl
oiting 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 prom
ise problem is NP-hard. Thus\, the quantum separab
ility problem (as phrased above) constitutes the f
irst nontrivial promise problem decidable by a two
-message quantum interactive proof system while be
ing hard for both NP and QSZK. We consider a varia
nt of the problem\, in which a given polynomial-ti
me mixed-state quantum circuit accepts a quantum s
tate as input\, and the question is to decide if t
here is an input to this circuit which makes its o
utput separable across some bipartite cut. We prov
e that this problem is a complete promise problem
for the class QIP of problems decidable by quantum
interactive proof systems. Finally\, we show that
a two-message quantum interactive proof system ca
n also decide a multipartite generalization of the
quantum separability problem.
LOCATION:MR14\, Centre for Mathematical Sciences
CONTACT:Paul Skrzypczyk
END:VEVENT
END:VCALENDAR