Freiburg 2019 – wissenschaftliches Programm

Sitzungen | Tage | Auswahl | Suche | Aktualisierungen | Downloads | Hilfe

FM: Fall Meeting

FM 75: Quantum Computation: Simulation II

FM 75.6: Talk

Donnerstag, 26. September 2019, 15:15–15:30, 1010

Closing the gaps of a quantum advantage with short-time Hamiltonian dynamics — •Jonas Haferkamp¹, Dominik Hangleiter¹, Adam Bouland², Bill Fefferman³, Jens Eisert¹, and Juani Bermejo-Vega¹ — ¹Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany — ²Electrical Engineering and Computer Sciences, University of California, Berkeley — ³Joint Center for Quantum Information and Computer Science, University of Maryland

Demonstrating a quantum computational speed-up is a crucial milestone for near-term quantum technology. Recently, comparably feasible quantum simulation architectures have been proposed that have the potential to show such a quantum advantage, based on commonly made assumptions. The key challenge in the theoretical analysis of this scheme - as of other comparable schemes - is to lessen the assumptions and close the theoretical loopholes, replacing them by rigorous arguments. In this work, we prove two open conjectures for these architectures of quantum simulators: Anti-concentration of the generated probability distributions and average-case hardness of exactly evaluating those probabilities. The latter is proven building upon recently developed techniques for random circuit sampling. For the former, we develop new techniques that exploit the insight that approximate 2-designs for the unitary group admit anti-concentration. We prove that the translation-invariant, constant depth architectures of quantum simulation form approximate 2-designs in a specific sense, thus obtaining a significantly stronger result.