Closing Gaps of a Quantum Advantage with Short-Time Hamiltonian Dynamics

Haferkamp J, Hangleiter D, Bouland A, Fefferman B, Eisert J, Bermejo-Vega J (2020)

Publication Type: Journal article

Publication year: 2020

Journal

Physical Review Letters American Physical Society

Book Volume: 125

Article Number: 250501

Journal Issue: 25

DOI: 10.1103/PhysRevLett.125.250501

Abstract

Demonstrating a quantum computational speed-up is a crucial milestone for near-term quantum technology. Recently, sampling protocols for quantum simulators 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 such as boson sampling - is to lessen the assumptions and close the theoretical loopholes, replacing them by rigorous arguments. In this work, we prove two open conjectures for a simple sampling protocol that is based on the continuous time evolution of a translation-invariant Ising Hamiltonian: anticoncentration 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 exploit the insight that approximate 2-designs for the unitary group admit anticoncentration. We then develop new techniques to prove that the 2D time evolution of the protocol gives rise to approximate 2-designs. Our work provides the strongest theoretical evidence to date that Hamiltonian quantum simulators are classically intractable.

Involved external institutions

Freie Universität Berlin DE Germany (DE) University of California, Berkeley US United States (USA) (US) University of Chicago US United States (USA) (US)

How to cite

APA:

Haferkamp, J., Hangleiter, D., Bouland, A., Fefferman, B., Eisert, J., & Bermejo-Vega, J. (2020). Closing Gaps of a Quantum Advantage with Short-Time Hamiltonian Dynamics. Physical Review Letters, 125(25). https://doi.org/10.1103/PhysRevLett.125.250501

MLA:

Haferkamp, J., et al. "Closing Gaps of a Quantum Advantage with Short-Time Hamiltonian Dynamics." Physical Review Letters 125.25 (2020).

BibTeX: Download