Quantum advantage from energy measurements of many-body quantum systems

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.

Comments are welcome

References in corpus (10)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Probing many-body dynamics on a 51-atom quantum simulator
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Spectral signatures of many-body localization with interacting photons
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Variational Fast Forwarding for Quantum Simulation Beyond the Coherence Time
• Emergence of coherence and the dynamics of quantum phase transitions
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• Universal adiabatic quantum computation via the space-time circuit-to-Hamiltonian construction
• A single-shot measurement of the energy of product states in a translation invariant spin chain can replace any quantum computation

Cited by in corpus (6)

• Computational advantage of quantum random sampling
• Mesoscopic ultrafast nonlinear optics -- The emergence of multimode quantum non-Gaussian physics
• Importance of the spectral gap in estimating ground-state energies
• Quantum computational advantage with constant-temperature Gibbs sampling
• Dynamics of single-mode nonclassicalities and quantum correlations in the Jaynes-Cummings model
• Quantum advantage in temporally flat measurement-based quantum computation