dc.contributor.author
Novo, Leonardo
dc.contributor.author
Bermejo-Vega, Juani
dc.contributor.author
García-Patrón, Raúl
dc.date.accessioned
2021-08-23T08:39:06Z
dc.date.available
2021-08-23T08:39:06Z
dc.identifier.uri
https://refubium.fu-berlin.de/handle/fub188/31714
dc.identifier.uri
http://dx.doi.org/10.17169/refubium-31445
dc.description.abstract
The problem of sampling outputs of quantum circuits has been proposed as a candidate for demonstrating a quantum computational advantage (sometimes referred to as quantum "supremacy"). In this work, we investigate whether quantum advantage demonstrations can be achieved for more physically-motivated sampling problems, related to measurements of physical observables. We focus on the problem of sampling the outcomes of an energy measurement, performed on a simple-to-prepare product quantum state – a problem we refer to as energy sampling. For different regimes of measurement resolution and measurement errors, we provide complexity theoretic arguments showing that the existence of efficient classical algorithms for energy sampling is unlikely. In particular, we describe a family of Hamiltonians with nearest-neighbour interactions on a 2D lattice that can be efficiently measured with high resolution using a quantum circuit of commuting gates (IQP circuit), whereas an efficient classical simulation of this process should be impossible. In this high resolution regime, which can only be achieved for Hamiltonians that can be exponentially fast-forwarded, it is possible to use current theoretical tools tying quantum advantage statements to a polynomial-hierarchy collapse whereas for lower resolution measurements such arguments fail. Nevertheless, we show that efficient classical algorithms for low-resolution energy sampling can still be ruled out if we assume that quantum computers are strictly more powerful than classical ones. We believe our work brings a new perspective to the problem of demonstrating quantum advantage and leads to interesting new questions in Hamiltonian complexity.
en
dc.format.extent
29 Seiten
dc.rights.uri
https://creativecommons.org/licenses/by/4.0/
dc.subject
quantum advantage demonstrations
en
dc.subject
quantum computational advantage
en
dc.subject
Hamiltonian complexity
en
dc.subject.ddc
500 Naturwissenschaften und Mathematik::530 Physik::530 Physik
dc.title
Quantum advantage from energy measurements of many-body quantum systems
dc.type
Wissenschaftlicher Artikel
dcterms.bibliographicCitation.articlenumber
465
dcterms.bibliographicCitation.doi
10.22331/q-2021-06-02-465
dcterms.bibliographicCitation.journaltitle
Quantum
dcterms.bibliographicCitation.volume
5
dcterms.bibliographicCitation.url
https://doi.org/10.22331/q-2021-06-02-465
refubium.affiliation
Physik
refubium.affiliation.other
Institut für Theoretische Physik

refubium.resourceType.isindependentpub
no
dcterms.accessRights.openaire
open access
dcterms.isPartOf.eissn
2521-327X
refubium.resourceType.provider
WoS-Alert