An efficient test for product states

Add to your list(s) Download to your calendar using vCal

• Ashley Montanaro
• Thursday 29 April 2010, 14:15-15:15
• MR3, Centre for Mathematical Sciences.

If you have a question about this talk, please contact Jonathan.

In this talk, I will discuss a test that can distinguish efficiently between pure product states of n quantum systems and states which are far from product. Understanding this test turns out to be a special case of a more general result regarding stability of maximum output purity of the depolarising channel.

An application of the test is to quantum Merlin-Arthur games; it can be used to show that a witness from two unentangled provers can simulate a witness from arbitrarily many unentangled provers, up to a constant loss of soundness. This result implies that there is an efficient quantum algorithm to verify SAT instances with constant soundness, given two unentangled proofs of O(sqrt(n)) qubits, which in turn implies complexity-theoretic obstructions to solving various problems in quantum information theory.

This talk will be based on the paper arXiv:1001.0017, which is joint work with Aram Harrow.

This talk is part of the CQIF Seminar series.

This talk is included in these lists:

• All CMS events
• CMS Events
• CQIF Seminar
• DAMTP info aggregator
• Hanchen DaDaDash
• Interested Talks
• MR3, Centre for Mathematical Sciences
• bld31

Note that ex-directory lists are not shown.