Quantum states cannot be transmitted efficiently classically

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

• Ashley Montanaro, Bristol
• Friday 12 May 2017, 12:00-13:00
• MR12, Centre for Mathematical Sciences, Wilberforce Road, Cambridge.

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

In this talk I will discuss recent work showing that any classical communication protocol that can approximately simulate the result of applying an arbitrary measurement (held by one party) to a quantum state of n qubits (held by another) must transmit at least 2^{n bits, up to constant factors. The argument is based on proving a lower bound on the classical communication complexity of a distributed variant of the Fourier sampling problem. Two optimal quantum-classical separations follow as corollaries. First, a sampling problem which can be solved with one quantum query to the input, but which requires order-N classical queries for an input of size N. Second, a nonlocal task which can be solved using n Bell pairs, but for which any approximate classical solution must communicate 2}n bits, up to constant factors.

The talk will be based on the paper arXiv:1612.06546.

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
• MR12, Centre for Mathematical Sciences, Wilberforce Road, Cambridge
• bld31

Note that ex-directory lists are not shown.