Quantum advantage from energy measurements

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

• Leonardo Goncalves Novo, QuIC, Université libre de Bruxelles
• Friday 04 October 2019, 12:00-13:00
• MR14, Centre for Mathematical Sciences, Wilberforce Road, Cambridge.

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

A central challenge in the field of quantum computation is to demonstrate that a quantum device can show an unambiguous computational advantage over classical computers. Although several quantum algorithms exhibit an advantage when compared to the best-known classical algorithms for the same problem, it is hard to guarantee that future algorithmic developments will not erase these advantages.

Recently, a considerable research effort has been devoted towards demonstrating a more reliable quantum advantage by considering the problem of sampling from certain quantum circuits that could conceivably be implemented in the near-term, such as the problems of boson sampling, IQP sampling or sampling from random quantum circuits. The existence of an efficient classical simulation of these problems would have strong implications in complexity theory, such as the collapse of the Polynomial Hierarchy, and thus is believed to be highly unlikely. Unfortunately, these sampling problems are rather artificial, in that they were constructed with the primary purpose of being hard to simulate classically.

In this work, we focus on demonstrating quantum advantage for the problem of sampling from energy measurements on easy-to-prepare, product quantum states. We give examples of local Hamiltonians and regimes of resolution and error parameters characterizing the measurement that can be efficiently reached by quantum devices, while providing strong complexity theoretic evidence for the impossibility of efficient classical methods to simulate such measurements. We believe this is an important step towards bringing quantum advantage demonstrations to more physically motivated problems, occurring naturally in many-body physics.

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

Note that ex-directory lists are not shown.