Show simple item record

dc.contributor.authorNovo, Leonardo
dc.contributor.authorBermejo Vega, Juan 
dc.contributor.authorGarcía Patrón, Raúl
dc.identifier.citationPublished version: Novo, L., Bermejo-Vega, J., & García-Patrón, R. (2021). Quantum advantage from energy measurements of many-body quantum systems. Quantum, 5, 465. []es_ES
dc.descriptionWe acknowledge discussions with Shantanav Chakraborty, Ashley Montanaro, Alex Grilo and Johannes Bausch. Furthermore, we thank Anthony Leverrier, Jelmer Renema and Dominik Hangleiter for valuable feedback on this manuscript. We also thank Mayec Rancel for designing Figure 1. LN acknowledges funding from Wiener-Anspach Foundation and F.R.S.-FNRS. J.B.V. acknowledges funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement Nº 754446 and UGR Research and Knowledge Transfer Found – Athenea3i. Part of this project took place during J.B.V.’s stay at Freie Universität Berlin, supported by ERC (TAQ). R.G.-P. is a Research Associate of the F.R.S.-FNRS and acknowledges funding from Wiener-Anspach foundation.es_ES
dc.description.abstractThe 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.es_ES
dc.description.sponsorshipWiener-Anspach Foundationes_ES
dc.description.sponsorshipFonds de la Recherche Scientifique - FNRSes_ES
dc.description.sponsorshipEuropean Commission 754446es_ES
dc.description.sponsorshipUGR Research and Knowledge Transfer Found Athenea3ies_ES
dc.description.sponsorshipERC (TAQ)es_ES
dc.rightsAtribución 3.0 España*
dc.titleQuantum advantage from energy measurements of many-body quantum systemses_ES

Files in this item


This item appears in the following Collection(s)

Show simple item record

Atribución 3.0 España
Except where otherwise noted, this item's license is described as Atribución 3.0 España