BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:An efficient test for product states - Ashley Montanaro
DTSTART:20100429T131500Z
DTEND:20100429T141500Z
UID:TALK23583@talks.cam.ac.uk
CONTACT:Jonathan
DESCRIPTION:In this talk\, I will discuss a test that can distinguish effi
 ciently between pure product states\nof n quantum systems and states which
  are far from product. Understanding this test turns out to be a special c
 ase of a more general result regarding stability of maximum output purity 
 of the depolarising channel. \n\nAn application of the test is to quantum 
 Merlin-Arthur games\; it can be used to show that a witness from two unent
 angled provers can simulate a witness from arbitrarily many unentangled pr
 overs\, up to a constant loss of soundness. This result implies that there
  is an efficient quantum algorithm to verify SAT instances with constant s
 oundness\, given two unentangled proofs of O(sqrt(n)) qubits\, which in tu
 rn implies complexity-theoretic obstructions to solving various problems i
 n quantum information theory.\n\nThis talk will be based on the paper arXi
 v:1001.0017\, which is joint work with Aram Harrow.
LOCATION:MR3\, Centre for Mathematical Sciences
END:VEVENT
END:VCALENDAR