Erlangen 2018 – scientific programme

Parts | Days | Selection | Search | Updates | Downloads | Help

Q: Fachverband Quantenoptik und Photonik

Q 7: Quantum Information (Quantum Computing)

Q 7.5: Talk

Monday, March 5, 2018, 11:45–12:00, K 1.020

Anti-concentration theorems for schemes showing a quantum speedup — •Dominik Hangleiter, Juan Bermejo-Vega, Martin Schwarz, and Jens Eisert — FU Berlin, Fachbereich Physik, Arnimallee 14, 14195 Berlin

Demonstrating a quantum speedup in as simple a setting as possible is a key milestone in the development of quantum technologies. Within the last year, achieving this milestone has come into close reach, in part but not only due to the quantum computing programmes of IBM and Google. At the heart of any task suitable for demonstrating a quantum speedup lies a complexity-theoretic proof that a quantum device computationally outperforms any classical device. Most proposals for near-term devices are based on sampling from some probability distribution. The technique most often used to prove a speedup for such tasks in that require certain complexity-theoretic conjectures about the sampled distribution to be assumed, one of them being that the distribution `anti-concentrates'. In this talk we will prove this conjecture for unitary two-designs which covers many interesting settings that are based on random quantum circuits including, most prominently, random universal circuits.