# Quantum advantage from energy measurements of many-body quantum systems

Leonardo Novo<EMAIL_ADDRESS>Centre for Quantum Information and
Communication, Ecole Polytechnique de Bruxelles, CP 165, Université Libre de
Bruxelles, 1050 Brussels, Belgium  Juani Bermejo-Vega<EMAIL_ADDRESS>Electromagnetism and Matter Physics Department, University of Granada,
Granada, Spain  Carlos I Institute of Theoretical and Matter Physics,
University of Granada, Granada, Spain  Free University of Berlin, Berlin,
Germany  Raúl García-Patrón<EMAIL_ADDRESS>Centre for Quantum Information
and Communication, Ecole Polytechnique de Bruxelles, CP 165, Université Libre
de Bruxelles, 1050 Brussels, Belgium

###### 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.

##  1 Introduction

Impressive recent developments in experimental quantum physics are enabling
the manipulation of many-body quantum systems of larger and larger sizes. The
high degree of control and local resolution of measurement reached in
experimental platforms such as quantum gas microscopes [1], Rydberg atoms
manipulated with optical tweezers [2], ion traps [3, 4], or superconducting
circuits [5, 6], are moving these experiments closer to the quantum advantage
frontier – a regime that is challenging to model using our traditional
computers. Experiments at this scale should lead to new insights into
important problems in many-body physics. For example, recent developments of
many-body interferometric techniques to estimate the entanglement entropy [7,
8] have opened experimental access to the investigation of quantum
thermalization [9]. Similarly, the access to complex many-body correlators on
large-size many-body systems has enabled the experimental study of quantum
critical dynamics and dynamical phase-transitions [2, 10, 3], many-body
localization [11, 12], scrambling [13, 14] and topological order [15, 16].

Several experimental demonstrations of large-scale quantum simulators that
outperform certain classical simulations methods have already been reported
[17, 18, 11, 2, 3]. Unfortunately, the evidence for quantum advantage in these
experiments is based solely on numerical benchmarks against available
classical algorithms such as, e.g., DMRG [17]. Hence, this does not exclude
the possibility that a _new classical algorithm_ performs as efficiently as a
given quantum simulator or quantum algorithm, for a problem where it was
previously thought there was an exponential quantum speed-up. A remarkable
example where this happened is the recent work “dequantizing" certain quantum
machine learning algorithms [19].

For this reason, it is of utmost importance to put statements about quantum
advantage on rigorous mathematical ground. This has been the subject of
several recent works which demonstrate, based on strong complexity-theoretic
evidence, that there are certain tasks that can be performed efficiently by
quantum devices for which an efficient classical algorithm cannot exist. These
are based on sampling problems that exhibit certain robustness against noise
and are tailored to near-term hardware. Examples include boson sampling [20],
IQP sampling [21], sampling from random quantum circuits [22, 6] and quantum
simulations of constant-time Hamiltonian evolutions [23, 24]. The key strength
of these results is that the existence of a quantum advantage is provable
assuming plausible complexity theoretic conjectures, such as the non-collapse
of the Polynomial Hierarchy (a commonly made assumption in theoretical
computer science, which can be seen as a generalization of the P$\neq$NP
conjecture) [20, 21]. The prospect of demonstrating in a reliable way
exponential quantum speed-ups has initiated a new field of theoretical and
experimental activity coined _quantum computational advantage_ (or quantum
“supremacy”) [25, 26].

This has motivated several efforts to bring quantum advantage proposals closer
to a realistic physical implementation. These efforts have largely focused on
finding approximate sampling problems that are robust against certain
experimental errors [20, 21]; tailoring quantum sampling problems to existing
implementations [22, 27, 24]; verifying such devices with efficient quantum
resources [24, 23, 28] or exponential classical ones [22, 29, 30, 31]. Some
works have also brought a many-body physics perspective to previously existing
quantum advantage proposals, through the study of the connections between
transitions in sampling complexity and dynamical phase transitions [32, 33,
34]. All these works, however, mostly rely on “unphysical” sampling problems
that were discovered for the sole purpose of demonstrating a quantum
advantage, and further connections with questions of central interest in many-
body physics are yet to be explored.

In this work, we take a step further towards identifying physically-motivated
quantum advantages in many-body quantum systems. We ask whether complexity-
theoretic results can deliver reliable quantum advantages for the measurement
of a physically meaningful observable or the calculation of quantities of
physical relevance. Specifically, we investigate whether quantum advantages
can be related to the measurement of the energy of a many-body quantum system.
Such measurements can be implemented, for example, on a quantum computer via
quantum phase estimation [35, 36], or on analog quantum simulators [37].

In retrospective, one could interpret the work by Huh and collaborators [38]
as a first attempt in this direction. This work connects a quantum "supremacy"
device, namely a Gaussian boson sampler [39], to the problem of determining
the vibrational spectrum of a molecule [40]. However, this work did not prove
this problem to be hard for a classical computer and, in practice, there exist
classical algorithms that build this spectrum for molecules of a hundred
harmonic vibrational modes on a desktop within a few minutes [41].

Hence, demonstrating a conclusive physically motivated quantum advantage
remains a difficult milestone. We would like such a quantum advantage proposal
to meet two desiderata:

  * •

It describes a physical experiment that efficiently measures or estimates a
relevant many-body observable or quantity.

  * •

It provides a rigorous mathematical proof of the impossibility of simulating
the outcome of the physical experiment efficiently with classical computers.

In this work we focus on the task of sampling outcomes of an energy
measurements of a many-body quantum system, a problem we refer to as energy
sampling. Naturally, the complexity this task depends on the different
parameters characterizing the outcome probability distribution, such as the
measurement resolution or other errors affecting the measurement device. Our
main contribution is to present complexity theoretic arguments that likely
exclude the existence of efficient classical simulators for the energy
sampling problem in different parameter regimes. In particular, we demonstrate
that for Hamiltonians that can be measured efficiently by quantum devices with
very high resolution, it is possible to demonstrate quantum advantage for the
energy sampling problem based on the widely believed conjecture of the non-
collapse of the Polynomial Hierarchy, together with other standard assumptions
[20, 21]. We give an explicit example of a simple family of Hamiltonians
(e.g., with nearest neighbour interactions on the 2D square lattice) for which
energy measurements are hard to simulate on classical computers, yet, should
be relatively feasible to measure on a near-term quantum device, which is able
to approximately sample from 2D circuits of commuting gates [24].
Interestingly, for this example, the correct functioning of the quantum
measurement device can be efficiently verified using existing fidelity-witness
methods [24], if reliable single-qubit measurements are available. This leads
to a conceivable quantum advantage proposal based on measurements of many-body
Hamiltonians. We further discuss limitations of current theoretical tools to
prove quantum advantage for energy sampling in low resolution regimes and how
it connects to the fundamental problem of proving that quantum computers are
strictly more powerful than classical ones.

For our proof of quantum advantage, we introduce the concept of quantum
diagonalizable Hamiltonians. This defines the set of Hamiltonians for which
one can efficiently obtain, using a quantum computer, a description of its
diagonalizing unitary as a poly-size quantum circuit as well as efficiently
compute its eigenvalues. We believe this concept can be of relevance outside
the scope of this work and may lead to new investigations of speed-ups with
respect to classical algorithms.

Figure 1: Given a Hamiltonian $H$, an energy measurement can be modelled as a
procedure that takes as input a quantum state $\rho_{A}$ and outputs a
measurement outcome $E_{i}$, as well as a post-measurement state
$\sigma_{A}^{i}$. We characterize a _noiseless measurement_ (inside the
smaller blue box) by its measurement resolution $\delta$, which determines the
accuracy of the output value $E_{i}$, and its failure probability $\epsilon$
(see Eqs. (1) and (4)). Moreover, to characterize a _noisy measurement_
(inside larger brown box), we introduce an extra parameter $\beta$ that
quantifies the sampling error, in total variation distance, between the
noiseless probability distribution and the observed one (represented by the
blue and brown histogram bars, respectively). These probability distributions
are defined explicitly in Definitions 2 and 3.

###  1.1 Measurement statistics and parameter regimes

Before summarizing our contributions in more detail we introduce some
terminology regarding the parameters characterizing an energy measurement as
well as the different measurement regimes achievable by quantum devices (a
more detailed discussion is presented in Sec. 2).

A model of the measurement outcome statistics needs to take into consideration
the imperfect nature of a realistic measurement. A schematic representation of
an energy measurement and the parameters we use in this work to characterize
it is depicted in Figure 1. Following Refs. [42, 43, 44], we characterize the
quality of a measurement by the measurement resolution $\mathbf{\delta}$,
which sets the smallest measurement unit, and the measurement confidence
$\mathbf{\eta}$. For example, an energy measurement of an eigenstate
$\ket{\psi_{E}}$ with energy $E$ is said to have resolution $\delta$ and
confidence $\eta$ if it outputs an estimate $E^{\prime}$ such that

$\Pr(|E^{\prime}-E|\leq\delta)\geq\eta.$ (1)

It will be useful to also define the parameter $\epsilon=1-\eta$, denoting the
probability of failure of the measurement. A generalization of Eq. (1) for
arbitrary input states (see Sec. 2) defines the target probability
distribution we would like to sample from.

The finite resolution and measurement confidence result from natural
limitations such as a finite measurement time or energy, which are present
even if we assume a noiseless measurement device. In addition, to take into
account the unavoidable presence of noise in the implementation of a realistic
measurement, we introduce the sampling error parameter $\mathbf{\beta}$. This
parameter quantifies the deviation in $\ell_{1}$-norm between the target
outcome distribution and that of an ideal measurement of resolution $\delta$
and confidence $\eta$.

In order to achieve a certain measurement resolution $\delta$, widely used
quantum measurement models, such as the von Neumann model or quantum phase
estimation (Sec. 2.1), require a scaling of the resources needed to perform
the measurement which is polynomial in the inverse resolution i.e.,
$\mathrm{poly}(1/\delta)$. Typically, the resources are quantified by the time
required to perform the experiment (assuming a fixed interaction strength
between system and a pointer variable [45]) or by the number of gates of a
quantum circuit that implements the desired measurement. We will refer to such
a measurement with this performance as a _standard-resolution measurement_ ,
since it can efficiently achieve what we refer to as _standard resolution_ ,
where $\delta=1/\mathrm{poly}(n)$. This can be seen as a coarse-grained energy
measurement since, in general, it is not able to distinguish each of the
exponentially many eigenvalues. Nevertheless, for unknown Hamiltonians it is
the best that can be achieved efficiently. It has been demonstrated that if
the Hamiltonian is unknown but its time-evolution can be implemented (as in an
experimental setting), an energy-time uncertainty relation is obeyed implying
that the measurement time will be inversely proportional to the targeted
energy precision [46]. On the other hand, as discussed in [44] and in Sec.
2.3, in some specific situations one can exploit knowledge of the Hamiltonian
to achieve what we refer to as a _super-resolution measurement_ , where the
scaling of resources is $O(\mathrm{poly}(\log(1/\delta)))$. This allows us to
perform a much more accurate measurement which achieves _super-resolution_
efficiently, i.e. an exponentially small measurement resolution
$\delta=1/\exp(n)$.

For our purpose it is sufficient to divide the sampling error parameter
$\mathbf{\beta}$ into two regimes. We define the measurement as
_“approximate”_ [20, 21] when the desired sampling error $\beta$ is required
to be only some constant independent of the system size $n$. Our results on
hardness of approximate sampling extend to the regime
$\beta=1/\mathrm{poly}(n)$. Moreover, we define the _“near-exact”_ sampling
regime if the sampling error $\beta$ is required to be inverse-exponential in
the input size.

###  1.2 Summary of results

Our results on classical hardness of simulating energy measurements concern
the previously defined regimes of resolution and sampling errors as summarized
in Table 1 and in more detail below. For the sake of clarity we omit the
confidence parameter $\eta$, which can be taken to be $\eta=1-O(\beta)$. We
provide complexity theoretic evidence that an efficient classical simulation
of energy measurements should not be possible, and discuss how the latter
provides a suitable test of quantum advantage for suitable resolution and
sampling error regimes. Due to their relevance in describing physical systems,
we focus on measurements of _$k$ -local Hamiltonians_ acting on $n$ qubits
(two level quantum systems) i.e., Hamiltonians of the form $H=\sum_{j}H_{j}$
where each term $H_{j}$ acts on $k$ qubits, for constant $k\in O(1)$. Our main
contributions are the following:

(i) We provide quantum advantage protocols for _approximate super-resolution_
energy measurements (Sec. 3). Specifically, we consider Hamiltonians with
nearest-neighbor interactions on 2D lattices that can be efficiently
diagonalized on a quantum computer. For the latter, we show, first, that
approximate super-resolution measurements can be implemented by building an
approximate sampler from the diagonalizing quantum circuit (Theorem 1). At the
same time, we prove that these measurements are hard to simulate classically
assuming plausible complexity-theoretic conjectures (Corollary 1). This leads
to a verifiable quantum advantage result based on energy measurements that
could be feasibly implemented in available quantum simulators. These results
exploit a connection between quantum advantage proposals based on simulating
constant-time Hamiltonian dynamics [24, 23] and energy measurement problems.
(ii) Super-resolution measurement procedures for _arbitrary_ Hamiltonians are
unlikely to exist based on complexity theoretic evidence [47, 44]. For this
reason, we investigate the hardness of energy measurements with _standard
resolution_. In Sec. 4, we give complexity-theoretic evidence that classical
computers cannot efficiently simulate energy measurements with standard
resolution, even for simple translation-invariant nearest-neighbor
Hamiltonians on the square lattice (Theorem 3). Analogously to results
obtained in Refs. [48, 49, 50] for other sampling problems, our hardness
result is valid in the _near-exact_ sampling regime where $\beta=0$ or is
inverse-exponential. We give two hardness proofs, one being based on the
quantum advantage proposal of [24], the other being based on circuit-to-
Hamiltonian constructions [51].
(iii) Ideally, one would like a physically motivated quantum advantage
experiment based on _approximate sampling problems with standard resolution_ ,
which are more resilient to imperfections. However, in Sec. 5, we argue that,
with current techniques, it is not possible to link the classical hardness of
this problem to a Polynomial Hierarchy (PH) collapse as in Refs. [20, 21]. As
an intermediate step, we provide alternative hardness results inspired by the
BQP-hardness of this problem [42, 43]. Using circuit-to-Hamiltonian
constructions [51], we show that a hypothetical classical simulator for energy
measurement of local Hamiltonians could be used to approximate arbitrary
marginals of the output distribution of any poly-sized quantum circuit
(Theorem 4). Based on hardness of simulating universal quantum circuits [22,
29, 31], these results give evidence that approximately measuring a local
Feynman-Kitaev Hamiltonian in the standard resolution regime is classically
intractable. As we will discuss in our manuscript, an open challenge in
complexity theory would be to tie these hardness results to a Polynomial
Hierarchy (PH) complexity-theoretic collapse. Such a result could have
additional implications for the development of quantum protocols exhibiting
physically-motivated quantum advantages.

|  |  Super-resolution
---
$\delta=1/\text{exp}(n)$
|  Standard-resolution
---
$\delta=1/\text{poly}(n)$
|  Near-exact samp.
---
$\beta=1/2^{\text{poly}(n)}$
(i) PH-collapse | (ii) PH-collapse
|  Approx. samp.
---
$\beta=\text{const.}$
(i) PH-collapse* | (iii) BPP=BQP
Table 1: Our results on classical hardness for the energy measurement problem,
summarized in points (i)-(iii) in Sec. 1.2. For the different regimes of
resolution $\delta$ and sampling error $\beta$, we show the complexity
theoretic implications of the existence of an efficient classical algorithm
for sampling outcomes of energy measurements, corresponding to the local
Hamiltonians we construct. The cells in grey correspond to problems that admit
efficient quantum algorithms. In particular, in Sec. 3, we describe an
efficient quantum protocol for approximate super-resolution energy
measurements, which could be used to demonstrate a quantum advantage. This
result, marked by “*”, requires plausible complexity theoretic assumptions
other than the collapse of the Polynomial Hierarchy (PH).

##  2 Setting

In this section we set up the framework to discuss quantum advantage for
measurements of many-body Hamiltonians. We start in Sec. 2.1 by discussing two
ubiquitous quantum measurement protocols: the Von Neumann pointer, for analog
devices, and quantum phase estimation, for digital quantum computers. We
discuss how our ability to measure is limited by experimental noise as well as
physical restrictions on available resources, such as time, energy, or quantum
gates counts. These limitations motivate us to define the problem of
approximate Energy Sampling in Sec. 2.2, where we introduce precisely the
parameters mentioned in Sec. 1.1 characterizing the probability distribution
of an imperfect energy measurement. Finally, we discuss in Sec. 2.3 the
different parameter regimes and how they can be achieved by quantum devices.

###  2.1 Measurement models and their limitations: from the von Neumann
pointer to quantum phase estimation

Let us consider a physical observable $\hat{O}_{A}$, with eigenvectors
$\ket{\psi_{i}}$ and eigenvalues $\lambda_{i}$, and a quantum system $A$ in
state $\rho_{A}$, where both operators act on a finite dimensional Hilbert
space $\mathcal{H}$. Upon an ideal measurement of this observable on system
$A$, the probability of obtaining an outcome $\lambda_{i}$ is given by

$p(\lambda_{i})={\rm Tr}[\rho_{A}\Pi_{i}],$ (2)

where $\Pi_{i}$ is the spectral projection on the eigenstates with eigenvalues
$\lambda_{i}$. In a realistic physical implementation of a quantum
measurement, though, the outcome probability distribution deviates from the
ideal one and is characterized by a finite resolution and other error
parameters. To understand the fundamental limitations of quantum measurements,
let us take as an example the _Von Nenmann pointer_ model of quantum
measurement [45]. In this model, the system under study interacts with a
continuous-variable pointer register $R$ for a time $t$ through the unitary
coupling

$U_{meas}=e^{-i\alpha t\left(\hat{O}_{A}\otimes\hat{p}_{R}\right)},$ (3)

where $\hat{p}_{R}$ is the momentum operator of the pointer register and
$\alpha$ is a parameter that captures the strength of the interaction. If
$\rho_{A}$ corresponds to an eigenvector $\ket{\psi}\bra{\psi}_{i}$ of
$\hat{O}_{A}$, the effect of $U_{meas}$ will be to apply a
$\alpha\lambda_{i}t$ continuous shift of the pointer register $R$. Therefore,
by having access to the value of the position of the pointer we can infer the
outcome $\lambda_{i}$. For example, the proposal for quantum non-demolition
energy measurements of many-body systems from [14] consists in an
implementation of a von Neumann pointer. Naturally, experimental constraints,
such as the finite width of the initial pointer state, a limited accuracy of
the measurement of the pointer position, or a finite interaction strength
$\alpha$ and interaction time $t$, impose intrinsic limitations on the
resolution of the measurement process and the probability that it succeeds. In
addition, a realistic measurement process is only able to achieve a noisy
approximation of the ideal unitary $U_{meas}$ which results in further errors
in the outcome probability distribution. These limitations justify the
introduction of the parameters $\delta$, $\eta$ and $\beta$ presented in
Section 1.2 (see also Figure 1) and rigorously defined in the next subsection.

Figure 2: Scheme of a quantum circuit for energy measurements. An energy
measurement on state $\ket{\psi}$ with Hamiltonian $H$ can be performed via
the quantum phase estimation (QPE) algorithm, by estimating the eigenphases of
the unitary $e^{iH}$. This algorithm exploits a superposition of different
time evolutions as well as an efficient implementation of the quantum Fourier
transform (QFT).

Quantum algorithms for simulating measurements of physical observables also
suffer from limitations and imperfections. In this case, the measurement
resolution as well as the different measurement errors are determined by the
finite number of quantum gates, as well as the noise and imperfections in the
implementation of these gates. It is well known that an observable
$\hat{O}_{A}$ can be measured using the quantum phase estimation (QPE)
algorithm [35, 36], represented in Figure 2. The QPE algorithm is a quantum
algorithm for estimating the eigenphases of a unitary matrix, which can easily
be converted into an algorithm for estimating the eigenvalues of $\hat{O}_{A}$
by taking the unitary $\hat{U}=e^{i2\pi\hat{O}_{A}/\Lambda}$, where
$\Lambda\geq||\hat{O}_{A}||$ is an upper bound on the norm of $\hat{O}_{A}$.
This way, the eigenphases of $\hat{U}$ can be understood as a normalized
outcome of the measurement of $\hat{O}_{A}$. In fact, it was discussed in Ref.
[52] that the QPE algorithm can be seen as a discretized simulation of a Von-
Neumann measurement. In this scenario, the ancillary register of phase-
estimation plays the role of a discretized von Neumann pointer, where every
ancillary qubit encodes an additional bit of precision. Therefore, a quantum
simulation of the measurement process will be also prone to error and
necessitate the introduction of the parameters $\delta$, $\eta$ and $\beta$.
The same holds for any potential classical algorithm trying to simulate the
quantum measurement process.

###  2.2 The Energy Sampling problem

Due to their simplicity and significance in condensed-matter physics, we will
focus on measurement problems for local many-body Hamiltonians on two-level
systems (qubits). Our framework can be easily extended to measurements of
general many-body observables.

######  Definition 1 (Measurement resolution).

An energy measurement on a state $\rho$ is said to have resolution $\delta$
and confidence $\eta$ if the probability of outcome $E^{\prime}$ is such that

$\Pr(E^{\prime}\in[E_{A}-\delta,E_{B}+\delta])\geq\eta\text{{tr}}(\Pi_{[E_{A},E_{B}]}\leavevmode\nobreak\
\rho),$ (4)

where $\Pi_{[E_{A},E_{B}]}$ is the spectral projection of $H$ in the energy
interval $[E_{A},E_{B}]$.

We will also define the parameter $\epsilon=1-\eta$, representing the
probability of failure of the measurement.

Without loss of generality, we assume all observables throughout the text to
have spectra contained in $[0,1]$: any observable can be written in this form
via a suitable rescaling.111Let $\kappa$ be an upper bound of $||H||$. Then,
$(H^{\prime}:=H/\kappa+1)/2$ has spectrum in $[0,1]$. Furthermore, such an
upper bound can be efficiently computed for $k$-local Hamiltonians
$H=\sum_{i=1}^{r}h_{i}$ with constant $k$, where the number of terms $r$ can
be at most $O(n^{k})$. Specifically, $\kappa\leq\max_{i}\|h_{i}\|r$. Moreover,
although in general an energy $E$ can be any real number, any device
performing an energy measurement has a discrete set of output values. For this
reason, we discretize the real line into steps of size $\delta>0$ and assume a
measurement outcome is given by a value
$E_{m}\in\\{0,\delta,...,1-\delta,1\\}$ (we take $\delta=1/K$ for some
positive integer $K$).222Strictly speaking the constraints on the measurement
outcome distribution from Eq. (4) could allow for outcomes $-\delta$ or
$1+\delta$. We assume that these outcomes would be identified with outcome $0$
and $1$, respectively, via classical postprocessing.

In principle, we could consider energy measurements on any state that can be
efficiently prepared by a quantum device. However, we focus on measurements on
_product states_ , since we are interested in energy measurement problems
whose complexity comes from the Hamiltonian and not from the state to be
measured. Also, considering measurements on more general quantum states would
only increase the classical complexity of the problem. Hence, we define the
problem of Energy Sampling as follows.

######  Definition 2 (Energy Sampling).

Given an $n$-qubit product quantum state $\rho$, an $n$-qubit local
Hamiltonian $H=\sum_{i=1}^{M}h_{i}$, $M\in O(\mathrm{poly}(n))$, and
parameters $\eta,\delta>0$, output $E_{m}\in\\{0,\delta...,1-\delta,1\\}$ with
probabilities $q_{m}$ such that Eq. (4) is fulfilled.

Such a sampler can be used to build an histogram containing information about
how the state $\rho$ decomposes in the eigenbasis of the measured Hamiltonian
and thus to learn about the Hamiltonian spectrum, as represented in Figure 1.
Namely, for a given outcome $E_{m}$, the probability $p(E_{m})$ can be
reconstructed up to 1/poly($n$) errors in probabilistic polynomial time.

It is important to remark that Definition 2 is not robust to experimental
imperfections, as the latter can introduce a sampling error in total variation
distance. For this reason, our main interest will be the notion of
_approximate_ energy sampling, which allows us to consider laboratory errors.

######  Definition 3 ($\beta$-approximate Energy Sampling).

Given a $n$-qubit product quantum state $\rho$, an $n$-qubit local Hamiltonian
$H=\sum_{i=1}^{M}h_{i}$, $M\in O(\mathrm{poly}(n))$, and parameters
$\eta,\delta,\beta>0$, output $E_{m}\in\\{0,\delta...,1-\delta,1\\}$ with
probabilities $q^{\prime}_{m}$ such that this probability distribution is
$\beta$-close in total variation distance to the outcome probability
distribution of an energy sampler (Definition 2).

The parameter $\beta$ quantifies how well the probabilities $q^{\prime}_{m}$
approximate the probability distribution of an energy measurement with
resolution $\delta$ and confidence $\eta$. Hence, we will refer to the
parameter $\beta$ as the sampling error.

###  2.3 Regimes of resolution and error achievable by quantum devices

As anticipated in the previous section, theoretical knowledge about the
Hamiltonian as well as experimental restrictions lead to different regimes of
resolution, confidence and sampling error. In what follows we extend that
presentation with some important remarks.

_Standard-resolution measurements._ For many ubiquitous measurement
procedures, the time necessary to achieve resolution $\delta$ grows as ${\rm
poly}(1/\delta)$. Taking again as example the von Neumann model, if we assume
that the pointer is prepared as a wavepacket of a fixed width $\sigma$ (fixed
energy), it is possible to distinguish two consecutive eigenvalues $E_{1}$ and
$E_{2}$ with high confidence by letting the system interact with the pointer
for a time such that $\alpha t|E_{2}-E_{1}|\gg\sigma$. Hence, a scaling of
$t=O(1/\delta)$ is needed to achieve resolution $\delta$, for a fixed value of
the coupling $\alpha$.

For quantum algorithms that simulate energy measurements, such as QPE, the
natural way to quantify their running time is based on the number of quantum
gates applied. It is known that an energy measurement protocol based on QPE
achieves a resolution $\delta$ with a number of gates scaling as
$\mathrm{poly}(1/\delta)$ [36]. This follows from the fact that the bottleneck
for this algorithm is the implementation of an approximation of the time-
evolution operator $\exp(iHT)$ for time $T=O(1/\delta)$ in terms of quantum
gates, which takes time $\mathrm{poly}(1/\delta,||H||)$ using standard quantum
simulation methods [53, 54]. More generally, it was shown in Ref. [44] that if
the Hamiltonian is unknown and we can only access the Hamiltonian evolution as
a black box, or even if its eigenstates are known but there is no information
about its eigenvalues, a number of gates scaling as $\mathrm{poly}(1/\delta)$
is the best that can be achieved by any quantum algorithm.

An alternative way to approximate the probability distribution of an energy
measurement on a state $\rho$ is by considering its Fourier transform

$P(\omega)\leavevmode\nobreak\
=\sum_{i}p(\lambda_{i})\delta(\omega-\lambda_{i})=\int\chi(t)e^{i\omega t}dt,$
(5)

where $\lambda_{i}$ are the eigenvalues of the Hamiltonian, $p(\lambda_{i})$
is defined in Eq. (2) and $\chi(t)={\rm Tr}[\rho e^{-iHt}]$ is the expected
value of the time evolution operator. The function $P(\omega)$ can be
approximated by measuring the correlators $\chi(t)$ at different times $t$ and
calculating the discrete Fourier transform of these values [55, 56]. Such
correlators can be measured via an many-body-interferometric experiment akin
to, for example, Ref. [57]. In this case, if we want to increase the
resolution of the approximation by a factor $1/x$, it is necessary to measure
$x$ times more values of the correlator $\chi(t)$, where the longest time will
be $x$ times larger than before. It is then expected that the time needed to
run the experiment grows quadratically with the inverse resolution
$\delta^{-1}$.

_Super-resolution measurements._ By exploiting certain knowledge about the
Hamiltonian it is sometimes possible to construct quantum algorithms for
energy measurements whose running time is ${\rm
poly}(\log\left(1/\delta\right))$, i.e., the cost of increasing the resolution
(decreasing $\delta$) grows polynomially in the number of digits of $\delta$,
instead of $\delta$ itself. We say that such a measurement procedure is a
_super-resolution measurement_ , as it allows to resolve even exponentially
small energy gaps of a Hamiltonian, with a cost increasing only polynomially
in $n$. It was demonstrated in Ref. [44] that this regime can be achieved by a
quantum algorithm iff the corresponding Hamiltonian can be _exponentially
fast-forwarded_ i.e., the time-evolution $\hat{U}=\exp(-iHT)$ can be
implemented for exponentially large $T$ using only polynomially many quantum
gates. It is important to note, however, that it is not known how to implement
super-resolution measurements of all local or sparse Hamiltonians, and indeed
there is strong complexity theoretic evidence that this is impossible [47, 44]
– if such a quantum procedure existed, it would imply that quantum computers
would be able to solve any problem in PSPACE, which is considered very
unlikely.

_Near-exact sampling._ It is interesting to consider the regime where the
sampling error $\beta$ is $0$ or inverse-exponential in $n$
($\beta=1/2^{\mathrm{poly}(n)}$), in order to understand the hardness of
nearly-exact simulations of _ideal_ (noiseless) quantum devices [58, 59, 48,
20]. As we will show, classical hardness results can be demonstrated in this
regime using the widely believed computational complexity-theoretic conjecture
that the Polynomial Hierarchy (PH) does not collapse (see Sec. 3.3).

As an important side remark, we note that achieving the standard resolution
and near-exact sampling regime via QPE is non-trivial, even assuming noiseless
quantum gates. To achieve this regime, it is necessary to efficiently
approximate the time-evolution operator $\hat{U}=e^{iHT}$ up to an inverse-
exponential error, which is not possible with methods based on product
formulas such as the original quantum simulation proposal of Lloyd [53].
However, it is possible to solve this problem thanks to recently developed
quantum simulation algorithms, which are exponentially more precise than the
original proposal by Lloyd, and are applicable for most Hamiltonians of
interest such as local, sparse, or low-rank ones [60, 54, 61, 62, 63].

_Approximate sampling._ The sampling error considered in the near-exact
sampling is extremely demanding and it is unknown to be reachable even by
fault-tolerant universal quantum devices [64]. For this reason, several
efforts to develop quantum advantage protocols that are robust against certain
sampling errors have been developed [20, 21, 25]. The latter consider
approximate sampling problems, where the sampling error $\beta$ is a small
constant. However, such proofs require the introduction of additional
computational complexity conjectures, as will be discussed in more detail in
Sec. 3.4. Furthermore, we discuss in Secs. 5 that current techniques to
demonstrate hardness of approximate sampling fail for energy sampling problems
with standard resolution, as they become sampling problems with a small output
space.

_Confidence regimes._ For the purposes of our discussion on classical hardness
of the energy sampling problem, we can take the value of the measurement
failure probability $\epsilon=1-\eta$ to be of the same order of magnitude of
the sampling error $\beta$, i.e., in the approximate sampling regime we can
tolerate a small constant value of $\epsilon$ whereas in the near-exact
sampling regime we require $\epsilon=1/2^{\mathrm{poly}(n)}$.

Using a standard energy measurement procedure such as quantum phase
estimation, a resolution $\delta=2^{-l}$ can be achieved with failure
probability $\epsilon$ by using $l+\log(2+(2\epsilon)^{-1})$ ancillary qubits
[65]. The scaling of the number of gates with this approach is
$O(\mathrm{poly}(\delta^{-1},\epsilon^{-1}))$ and so a small constant value of
$\epsilon$ can be achieved with a constant overhead. Furthermore, any quantum
algorithm for energy measurements achieving a failure probability smaller than
$\epsilon\leq 1/2-1/\mathrm{poly}(n)$, can be efficiently converted into a
procedure achieving an _exponentially small_ failure probability
$\epsilon=1/2^{\mathrm{poly}(n)}$ via confidence amplification methods [44].

##  3 Quantum advantage for super-resolution energy measurements

As we previously mentioned, [44] proves the connection between energy
measurements with super-resolution and the capability to exponentially fast-
forward the time evolution of the Hamiltonian. The intuition behind this
result comes from the combination of three concepts: (i) the connection
between energy measurements and QPE (ii) the capability to exponentially fast-
forward the time evolution of a Hamiltonian; (iii) the quantum parallelization
achieved in QPE that allows exponentially many more queries than a classical
Fourier transform. The authors of [44] provide some examples of Hamiltonians
amenable to an exponential speed-up of the time evolution: commuting local
Hamiltonians, a Hamiltonian constructed from the modular exponentiation
unitary in Shor’s algorithm and free-fermions. The reason behind the
capability to exponentially fast-forward the time evolution of free-fermions
(which is also applicable in the case of free bosons) is the fact that the
diagonalization of the Hamiltonian is known [66, 67], which allows to
construct a quantum circuit that accelerates the simulation of the time
evolution. Interestingly, this last set of examples can be generalized to
define a potentially larger set that we name Quantum Diagonalizable
Hamiltonians.

###  3.1 Quantum Hamiltonian Diagonalization

In full generality, we say that a Hamiltonian $\tilde{H}$ is quantum
diagonalizable if

$\tilde{H}=U^{\dagger}H_{f}U,$ (6)

where $U$ is a poly-size quantum circuit and $H_{f}$ is a diagonal matrix in
the computational basis written as

$H_{f}=\sum_{z=0}^{2^{n}-1}f(z)\ket{z}\bra{z},$ (7)

where the gate decomposition of the circuit $U$ can be obtained efficiently
using a quantum computer and there is a quantum circuit that computes $f(z)$
up to a given number of digits of precision $l$ in time $\mathrm{poly}(l)$.
The two conditions on $U$ and $f(z)$ guarantee the existence of a poly-size
quantum circuit that can exponentially fast-forward the Hamiltonian time
evolution (see Figure 3(a)).

Hybrid quantum-classical algorithms for finding quantum circuits for
approximate diagonalization of a Hamiltonian have been proposed, as a way to
develop more efficient Hamiltonian simulation procedures [68]. In this work we
will restrict to cases where both the gate decomposition for $U$ and the
function $f(z)$ can be computed efficiently _classically_ , which allows us to
consider simple energy measurement procedures in Sec. 3.2.

(a)

(b)

Figure 3: a) Representation of the five steps of the quantum circuit for
implementing the time-evolution $e^{i\tilde{H}T}$ of a Hamiltonian with a
known quantum diagonalization, i.e. of the form $\tilde{H}=U^{\dagger}H_{f}U$
discussed in Sec. 3.1. Exploiting the structure of $\tilde{H}$ the time
evolution can be implemented efficiently even for exponentially large time
$T$. b) If the Hamiltonian has a quantum diagonalization, the energy
measurements can be performed by sampling the outcomes $z$ from the quantum
circuit implementing $U$ and computing the eigenvalues via the function
$f(z)$. This procedure is simpler than QPE and exponentially precise energy
measurements can be achieved efficiently.

Bellow, we explain how to build a circuit for fast-forwarding a quantum
diagonalizable Hamiltonian $\tilde{H}$ by analyzing how the circuit acts on an
eigenstate, which has the form $\ket{\psi_{z}}=U^{\dagger}\ket{z}$. The steps
of the circuit are the following:

  1. 1.

Apply $U$ to $\ket{\psi_{z}}$ to obtain the state $\ket{z}$.

  2. 2.

For a given desired evolution time $T$, compute an $a$-bit approximation of
the phase $\phi_{z,T}=f(z)T\leavevmode\nobreak\
(\text{mod}\leavevmode\nobreak\ 2\pi)$, where $a=O(\log(n))$, on an ancillary
register. This takes time $O(\mathrm{poly}(\log(T),\log(n)))$ since we assume
that $l$-bits of $f(z)$ can be computed in $O(\mathrm{poly}(\log(l)))$ time.
This creates a state $\ket{z}\ket{\tilde{\phi}_{z,T}}$, where
$\tilde{\phi}_{z,T}$ is the $a$-bit approximation of $\phi_{z,T}$.

  3. 3.

Apply the controlled phase
$e^{-i\tilde{\phi}_{z,T}}\ket{z}\ket{\tilde{\phi}_{z,T}}$

  4. 4.

Undo the computation of $\tilde{\phi}_{z,T}$ in the ancillary register to
obtain the state $e^{-i\tilde{\phi}_{z,T}}\ket{z}\ket{0}^{\otimes a}$.

  5. 5.

Apply $U^{\dagger}$ to obtain the state
$e^{-i\tilde{\phi}_{z,T}}\ket{\psi_{z}}$.

This quantum circuit, sketched in Figure 3, implements an approximation
$U^{\prime}$ of the time-evolution operator in time
$O(\mathrm{poly}(\log(n),\log(T)))$. The choice $a=\log(n)$ ensures that
$||U^{\prime}-\exp(-i\tilde{H}T)||=O(2^{-a})=O(1/\mathrm{poly}(n))$, which
shows that $\tilde{H}$ is exponentially fast-forwardable, according to the
definition in Ref. [44] (see Appendix A).

We leave open the problem of how quantum diagonalizable Hamiltonians relate to
the potentially larger class of exponentially fast-forwardable Hamiltonians.
Also, it is important to remark that, since the quantum diagonalization
assumptions imply the ability to fast-forward, it is unlikely that arbitrary
Hamiltonians are quantum diagonalizable – otherwise, this would imply a
general procedure for exponentially precise energy measurements of arbitrary
Hamiltonians which, combined with the results in [44, 47], implies BQP=PSPACE.

###  3.2 Super-resolution energy measurements for Hamiltonians with known
diagonalization

The motivation to restrict $f(z)$ to functions that can be computed
efficiently classically, instead of the more general case where $f(z)$ can be
computed by a quantum circuit, is that it allows us to connect super-
resolution energy measurements of $\tilde{H}$ to the problem of sampling from
$U$. In fact, given that the quantum diagonalization of the Hamiltonian is
known, super-resolution can be achieved by sampling from the quantum circuit
$U$, together with some classical post-processing to compute $f(z)$, as
schematically depicted in Fig. 3(b) . Furthermore, the generated distribution
can be characterized by the parameters $\delta,\eta$ and $\beta$ defined in
Sec. 2.2.

In order to show this, let us assume we have access to an approximate sampler
from outputs of $U$, i.e. a device that samples approximately from the
probabilities $P_{z}=|\bra{z}U\ket{\psi}|^{2}$. More precisely, we define the
problem of approximate $U$-sampling as follows.

######  Definition 4 ($\beta$-approximate $U$-sampling).

Given an initial state $\ket{\psi}$ and a unitary $U$, sample outcomes $z$
with probabilities $P^{\prime}_{z}$ such that
$\sum_{z}|P_{z}-P^{\prime}_{z}|\leq\beta$.

We will refer to such a sampler as a _$\beta$ -approximate sampler_ for $U$.
We can now demonstrate the following

######  Theorem 1 (Quantum algorithm for super-resolution energy
measurements).

Consider any quantum diagonalizable Hamiltonian $\tilde{H}=U^{\dagger}H_{f}U$
as in (6). Then, the following quantum algorithm efficiently solves the
$\beta-$approximate Energy Sampling problem for Hamiltonian $\tilde{H}$, with
the initial state $\ket{\psi}$ and parameters $\eta=1$ and $\delta=2^{-l}$:

  * •

Query a $\beta$-approximate sampler for $U$, with initial state $\ket{\psi}$.

  * •

Given an outcome $z$, output an $l$-digit approximation of the value $f(z)$ .

Theorem 1 provides a simple quantum procedure for super-resolution energy
measurements, since $l$ digits of precision can be achieved in
$\mathrm{poly}(l)$ time. The procedure is represented schematically in Fig. 3
and can be used to bypass the QPE algorithm, which requires further overhead.
The details of the proof of Theorem 1 are given in Appendix B, but the result
can be understood intuitively. As expected, an $l$-digit accuracy in the
computation of $f(z)$ translates into an $l$-digit resolution of the energy
measurement $\delta$. Moreover, the finite total variation distance $\beta$ of
the approximate sampler for $U$ implies that the output distribution of the
algorithm solves a $\beta$-approximate energy sampling problem. Finally, since
we have assumed $f(z)$ can be computed deterministically, the confidence
$\eta$ is $1$.

This provides a reinterpretation of the result in [38] as a proposal for
super-resolution energy measurements of the vibronic spectra of a molecule
(described by a quadratic bosonic Hamiltonian) via a more economical quantum
circuit than the traditional quantum phase-estimation algorithm.333In a
nutshell, the Franck-Condon profile at zero temperature which, under certain
approximations, gives the vibronic spectrum of a molecule, can be seen as the
distribution obtained by measuring the energy of the vaccuum state of a given
bosonic quadratic Hamiltonian $H$, according to a different bosonic quadratic
Hamiltonian $H^{\prime}$. If we choose our basis as the Fock basis of $H$, it
is possible to compute classically the parameters describing the gaussian
transformation $U$ that diagonalizes $H^{\prime}$ and write
$H^{\prime}=U^{\dagger}H_{f}U$, i.e. find a quantum diagonalization for
$H^{\prime}$. The proposal of Ref. [38] for sampling from the Franck-Condon
profile can thus be seen as an instance of the scheme for energy measurements
discussed in Theorem 1 and represented in Fig. 3(b). The discussion above
provides also a generalization of that result to any Hamiltonian with a
quantum diagonalization.

###  3.3 Classical hardness of super-resolution Energy Sampling

In this subsection, we present our quantum advantage result based on super-
resolution energy measurements of local Hamiltonians. After introducing the
diagonalizable local Hamiltonians of interest for our proof, we show how the
existence of an efficient classical (quantum) algorithm for the energy
sampling problem implies also an efficient classical (quantum) solution to the
problem of sampling from its diagonalization unitary (see Theorem 2).
Exploiting known results on the hardness of sampling unitary circuits, we
obtain as a corollary (Corollary 1) the existence of a simple class of local
Hamiltonians for which super-resolution measurements can be feasibly
implemented in a quantum device but not efficiently classically simulated
(assuming plausible complexity theoretic statements). Our proof is
constructive and applies to a family of Hamiltonians diagonalizable by IQP
circuits [21, 24] (i.e., quantum circuits that are diagonal in the $X$ Pauli
basis). However, the ideas behind the proof are general and can be applied to
find other hard energy sampling problems, by considering Hamiltonians that are
diagonalized by quantum circuits from other quantum advantage proposals.

_The Hamiltonian._ Specifically, our Hamiltonian family is defined by
conjugating a diagonal Hamiltonian of form (7) with an IQP unitary. For
physical reasons, we further focus on a specific family of nearest neighbor
IQP circuits on the 2D square lattice $\mathcal{L}_{\mathrm{2D}}$ [24]. The
latter implements a unitary

$U_{2D}=\exp\left[i\frac{\pi}{4}\left(\sum_{(j,k)\in\mathcal{L}_{\mathrm{2D}}}X_{j}X_{k}+\sum_{k}X_{k}\right)\right],$
(8)

corresponding to a constant time-evolution of a translation-invariant nearest-
neighbor Hamiltonian on $\mathcal{L}_{\mathrm{2D}}$. The Hamiltonian we use to
define an energy measurement problem is of the form

$H_{2D}\left[\vec{w}\right]=\sum_{j=1}^{n}w_{j}U^{\dagger}_{2D}\hat{n}_{j}U_{2D},\quad\hat{n}_{j}:=(\mathbb{I}_{j}-Z_{j})/2$
(9)

where $\hat{n}_{j}$ acts locally on qubit $j$ and $\vec{w}=(w_{1},...,w_{n})$
is a set of real-valued weights. It is easy to see that the unitary (8)
implements a product of controlled-Z [65] gates in the $X$ basis, whose action
on Pauli operators can be analyzed in the stabilizer formalism [69]. Using
this property, we arrive at the final expression for our Hamiltonian:

$H_{2D}\left[\vec{w}\right]=\sum_{j=1}^{n}w_{j}X_{j}\prod_{j:(j,l)\in\mathcal{L}_{\mathrm{2D}}}Z_{l}.$
(10)

This Hamiltonian is 5-local, with local terms represented in Fig. 4. It is a
“weighted” non-translation-invariant variation of the 2D cluster state
Hamiltonian used in measurement based quantum computation [70, 71].

Figure 4:  Schematic representation of the Hamiltonian $H_{2D}[\vec{w}]$, from
Eq. (10) and (9), and three of its local terms $H_{a}$, $H_{b}$ and $H_{c}$.
Each of these terms is a 5-local Hamiltonian acting on a given qubit ($a$,
$b$, $c$) and its nearest neighbors on the 2D lattice (represented inside each
one of the three squares). We remark that each term can have a different
weight. When all the weights are the same, as in Eq. (9), the Hamiltonian is
translationally invariant.

_Quantum advantage result._ Our next result gives complexity theoretic
evidence that energy measurements of Hamiltonians of form (10) on product
states cannot be efficiently classically simulated. To demonstrate our result,
we exploit recent quantum advantage results [24]. Namely, we reduce the
problem of measuring these Hamiltonians with super resolution, to that of
sampling from the output distribution of a constant-time Hamiltonian evolution
of form (8) given an input product states of form

$\ket{\psi_{\theta,x}}=\bigotimes_{j=1}^{n}(\ket{+}+(-1)^{x_{j}}e^{i\theta_{j}}\ket{-}),$
(11)

where $\theta_{j}$ and $x_{j}$ are chosen uniformly at random from the set
$\Theta=\\{0,\pi/4\\}$ and the set $\\{0,1\\}$, respectively [24]444We assume
measurements are performed in the standard computational basis.. Precisely, we
prove the following reduction between these two problems.

######  Theorem 2 (Circuit sampling from energy sampling).

Consider the problem of measuring the Hamiltonians
$H_{2D}\left[\vec{w}\right]$ on input product states $\ket{\psi_{\theta,x}}$
with $\theta_{j}$ and $x_{j}$ are chosen uniformly at random from the set
$\Theta=\\{0,\pi/4\\}$ and the set $\\{0,1\\}$, respectively. Assume the
existence of an efficient classical (quantum) algorithm for the associated
approximate energy sampling problem with resolution $\delta=O(2^{-n})$,
confidence $\eta=1-\epsilon$ and approximation error $\beta$. Then, there
exists an efficient classical (quantum) algorithm for $\gamma-$approximate
sampling from the unitary $U_{2D}$ (8), acting on the same inputs, with
$\gamma=2\epsilon+\beta$.

Ref. [24] rules out the existence of efficient classical simulations for
short-time Hamiltonian evolutions of form (8) based on three plausible
complexity-theoretic conjectures: (C1) the non-collapse of the Polynomial
Hierarchy; (C2) an approximate average-case hardness conjecture; (C3) an
anticoncentration conjecture. These conjectures are similar to those in [20,
21] and are reviewed in Sec. 3.4. Here, we demonstrate a hardness result for
super-resolution Hamiltonian measurements, which is a corollary of Theorem 2
and the hardness results in Refs. [24].

######  Corollary 1 (Quantum advantage for approximate super-resolution energy
measurements).

There cannot exist an efficient classical algorithm for simulating
measurements of the Hamiltonian (10) with super-resolution on input product
states as in Theorem 2, for any $\eta=1-\epsilon$, $\beta$ such that
$2\epsilon+\beta\leq 1/22$, assuming complexity-theoretic conjectures C1-C3
below, in section 3.4.

Corollary 1 leads to a natural quantum advantage proposal, since the problem
can be solved via the quantum algorithm in Theorem 1, by realizing the unitary
(8), which can conceivably be implemented in several quantum simulation
platforms, e.g., cold-atomic ones [24]. Furthermore, an efficient _quantum
verification_ protocol for the required quantum sampler exists, which only
requires reliable single-qubit measurements [24, 30]. Additionally, the result
provides a connection between the quantum advantage protocol of [24], based on
sampling measurements of a quantum state in a fixed basis, and a high-
precision spectroscopy problem. This relates these Hamiltonian quantum
advantage proposals to a physical problem of interest, complementing previous
work on vibronic spectra [38].

To prove Theorem 2, we choose an appropriate set of weights $\vec{w}$ that
establishes a one-to-one map between the eigenvalues of $H_{2D}[\vec{w}]$ and
its eigenvectors. The proof technique (detailed next) generally yields quantum
advantage results for measurements of Hamiltonians that are diagonalized by
“Ising-type” evolutions that implement IQP circuits [48, 59, 21], if the
associated diagonalizing unitary $U$ is hard to simulate classically. For
instance, we could replace $U_{2D}$ with the long-ranged local IQP circuits of
[21], or the nearest-neighbor translation invariant Hamiltonian evolutions of
[24, 72, 23]. The resulting Hamiltonian for an IQP circuit on a $k$-degree
interaction graph would be $k+1$ local (see Appendix C for details). These
alternative constructions yield quantum advantage results analogous to
Corollary 1 for Hamiltonians that are $n$-body long-ranged considering the
quantum circuits from [21]; 6-local nearest-neighbor on the dangling-bond
square lattice for [24]; and 4 or 5-local for the brickwork lattices of [23,
72]. Alternatively, the diagonalizing unitaries could also be chosen from
other families of quantum circuits that lead to quantum advantage beyond IQP
circuits, such as random quantum circuits [22]. In the latter case, however,
the resulting Hamiltonian family would be $n$-local and hence of less physical
interest.
_Proof of Theorem 2: _The Hamiltonian $H_{2D}[\vec{w}]$ is local and admits a
diagonalization of the form (6), since it is diagonalized by the matrix
$U_{2D}$ and its eigenvalues can be efficiently computed classically via the
function $f(z)=\sum_{i}w_{i}z_{i}$, where $z_{i}$ denotes the bit
decomposition of the integer $z\in\\{0,2^{n}-1\\}$. We will consider the case
where $f(z)$ is an invertible function such that the value of $z$ can be
efficiently computed from the energy value $f(z)$. In this case the
probability of observing a particular energy value (up to error $\delta$) can
directly be related to a certain output probability of the quantum circuit
$U_{2D}$. For simplicity, we will consider the choice of weights
$u_{j}=2^{-j}$, in which case $f(z)\equiv Id(z)=z2^{-n}$, for
$z\in\\{0,...,2^{n}-1\\}$ is a rescaled identity function, which is clearly
invertible. Other choices could be possible without necessarily requiring
exponentially decaying weights 555Another possible choice of weights which
leads to an invertible function $f(z)$ is $u_{i}=\log(p_{i})/C$, where the
$p_{i}$’s are different prime numbers and $C$ is a large enough positive
number that guarantees the maximum energy to be less or equal to one. In this
case $f(z)=\log(\prod_{i}p_{i}^{z_{i}})$ and given that each number has an
unique prime decomposition and the values of $p_{i}$ are known, $z$ can be
computed efficiently from the value of $f(z)$..

Let us consider a $\beta$-approximate energy sampler for the Hamiltonian
$H_{2D}[\vec{u}]$, given by

$H_{2D}[\vec{u}]=\sum_{j}2^{-j}U_{2D}^{\dagger}\hat{n}_{j}U_{2D}.$ (12)

To show how an efficient classical sampler from $U_{2D}$ can be constructed
from a classical algorithm for super-resolution energy measurements, we
consider the following sampling algorithm

Algorithm 1

  * •

Query a $\beta-$approximate energy sampler with input Hamiltonian
$H_{2D}[\vec{u}]$, input state
$\rho=\ket{\psi_{\theta,x}}\bra{\psi_{\theta,x}}$ and parameters
$\delta=2^{-n}/3$, $\eta=1-\epsilon$.

  * •

Given an output $E_{m}=m\delta$, output the unique $z$ satisfying
$E_{m}\in\\{z/2^{n}-\delta,z/2^{n},z/2^{n}+\delta\\}$.

The algorithm queries an energy sampler with a resolution one third smaller
than the separation between consecutive eigenvalues of
$H_{2D}\left[\vec{u}\right]$, which is $2^{-n}$, in order to guarantee that
the spectral projection in the interval $[z2^{-n}-\delta,z2^{-n}+\delta]$ is
simply given by $\Pi_{z2^{-n}}$. As shown below, this allows us to relate the
probability that Algorithm 1 outputs $z$ to the quantity
$P_{z}=|\bra{z}U\ket{\psi_{\theta,x}}|^{2}$, the latter being the probability
of observing the computational basis state $\ket{z}$ from a sampler from
$U_{2D}$ with initial state $\ket{\psi_{\theta,x}}$.

To demonstrate this relation, we first analyze the case when $\beta=0$. Using
the definition of measurement resolution from Eq. (4), we obtain that the
probability that Algorithm 1 outputs $z$ is given by

$\displaystyle p_{z}$ $\displaystyle=\Pr(|E_{m}-z/2^{n}|\leq\delta)$ (13)
$\displaystyle\geq(1-\epsilon)\bra{\psi_{\theta,x}}\Pi_{z2^{-n}}\ket{\psi_{\theta,x}}$
(14) $\displaystyle\geq(1-\epsilon)|\bra{z}U_{2D}\ket{\psi_{\theta,x}}|^{2}$
(15)

The equality follows from the constraints on the probability distribution of
an energy sampler, defined by Eq. (4). The first inequality results from the
spectral projection in the interval $[z2^{-n}-\delta,z2^{-n}+\delta]$ being
simply given by $\Pi_{z2^{-n}}$. The second inequality follows from the fact
that, by construction of $H_{2D}\left[\vec{u}\right]$, we have that

$\Pi_{z2^{-n}}=U^{\dagger}_{2D}\ket{z}\bra{z}U_{2D}.$ (16)

From Eq. (15) we can define $dp_{z}\geq 0$ such that
$p_{z}=(1-\epsilon)P_{z}+dp_{z}$. In addition, it can be seen, from the
construction of Algorithm 1, that the probabilities $p_{z}$ are normalized,
which implies that

$\displaystyle\sum_{z}p_{z}=1\Leftrightarrow\sum_{z}(1-\epsilon)P_{z}+dp_{z}=1$
(17) $\displaystyle\Rightarrow\sum_{z}dp_{z}=\epsilon.$ (18)

Hence, it follows that

$\displaystyle\sum_{z}|P_{z}-p_{z}|$ $\displaystyle=\sum_{z}|\epsilon
P_{z}-dp_{z}|$ $\displaystyle\leq\epsilon+\sum_{z}dp_{z}\leq 2\epsilon,$ (19)

which shows that Algorithm 1 is an $2\epsilon$-approximate sampler for
$U_{2D}$.

For the case where $\beta\geq 0$, Algorithm 1 outputs $z$ with probability
$p^{\prime}_{z}$

$\sum_{z}|p^{\prime}_{z}-p_{z}|\leq\beta.$ (20)

Consequently, the bounds from Eqs. (19) and (20) imply that

$\sum_{z}|p^{\prime}_{z}-P_{z}|\leq\beta+2\epsilon.$ (21)

This implies that Algorithm 1 is an efficient $\gamma$-approximate sampler for
unitary $U_{2D}$ and initial state $\ket{\psi_{\theta,x}}$, with
$\gamma=2\epsilon+\beta$. $\square$

###### Proof of corollary 1.

The classical hardness result for this energy measurement problem follows
directly from the application of Theorem 2, which maps this problem to that of
sampling from $U_{2D}$, together with the quantum advantage result of Ref.
[24]. Specifically, Theorem 1 from Ref. [24] states that a classical algorithm
cannot approximately sample from outputs of the circuit $U_{2D}$, up to a
total variation distance of $\beta=1/22$, in polynomial time. This result is
based on three complexity theoretic assumptions which we summarize in section
3.4. ∎

We remark that a crucial point of the proof of Theorem 2 is to choose the
weights $w_{i}$ so the spectrum of the Hamiltonian is non-degenerate. It can
be seen that this requires the weights $w_{i}$ to be defined up to $O(n)$ bits
of precision. Such precision in controlling the parameters of a Hamiltonian is
hard to achieve in an experimental setting. Nevertheless, measuring the energy
of quantum states according to such Hamiltonians is a valid theoretical
question that can be explored using quantum devices beyond what is likely to
be simulable efficiently classically given Corollary 1 . We leave as an open
problem whether a similar hardness result to Corollary 1 can be achieved for
measurements of Hamiltonians whose parameters are defined up to constant
precision.

###  3.4 Complexity theoretic assumptions needed for quantum advantage via
sampling problems

The quantum advantage proposal of Corollary 1 relies on complexity-theoretic
conjectures. Specifically, these are the same conjectures666This follows, from
the proofs of Theorem 2 and Corollary 1, since we exploit a reduction to the
quantum sampling problem therein. underlying the quantum advantage proposal of
Ref. [24]; the latter are, in turn, analogous to those involved in hardness
proofs for random universal quantum circuits [22, 31] and slightly weaker than
those in the seminal boson sampling and IQP proposals of Refs. [20, 21]. Any
progress towards proving the conjectures in Ref. [24] would simultaneously
improve our results.

For the sake of completeness we here summarize the conjectures that enter the
quantum advantage results in [24]. The first (C1) is the non-collapse of the
Polynomial Hierarchy, a widely believed generalization of the
$\textsf{P}\neq\textsf{NP}$ conjecture [73, 74, 75], first linked to hardness
of classical simulation of quantum circuits in [58]. This assumption alone
rules out the existence of near-exact classical simulators for a large family
of quantum devices, including the ones we study: specifically, this is the
case for quantum devices with output probabilities that are #P-hard to
approximate up to constant relative errors in worst case (see [20, 59] and
appendix D).

Following an approach pioneered in [20, 21], this classical hardness result
can be made noise-robust up to a constant sampling error in total variation
distance $\beta$ assuming two additional conjectures about the output
probabilities of the quantum device. Specifically, let the set of all output
probabilities of our device be
$\mathcal{P}_{n}=\\{p_{x},x\in\\{0,1\\}^{n}\\}$, where $n$ is the number of
qubits. Then, we require: (C2) an approximate average-case hardness
conjecture, which states that a constant fraction of the output probabilities
in $\mathcal{P}_{n}$ are #P-hard to approximate (up to a constant relative
error); (C3) an anticoncentration conjecture, stating that the output
distribution is “sufficiently flat”, in the sense that
$\mathrm{prob}_{p_{x}\sim\mathcal{P}_{n}}\left[p_{x}>\alpha/2^{n}\right]>\gamma$,
for some constants $\alpha,\gamma\in O(1)$. Assuming (C2)-(C3), it can be
shown that the existence of an efficient classical algorithm for
$\beta$-approximate sampling from the unitary $U_{2D}$ implies the collapse of
the Polynomial Hierarchy to its 3rd level. The central technique in this
argument is Stockmeyer’s counting algorithm [76] (Sec. 5.1 and Appendix D),
which shows that such a classical sampler implies the existence of an
algorithm (inside the third level of the Polynomial Hierarchy) for estimating
the probabilities in $\mathcal{P}_{n}$ on average with high accuracy, a
#P-hard problem. This then implies the aforementioned collapse of complexity
classes by Toda’s theorem[77] (see appendix D for more details). We note that
the specific total variation distance $\beta$ tolerated for the classical
sampler depends on the choices of the constant parameters in the statement of
the conjectures; the values chosen in Ref. [24] lead to the threshold
$\beta=1/22$.

There has been steady progress towards proving the complexity theoretic
assumptions made. In Ref. [24], numerical evidence was presented which
supports the anticoncentration conjecture (C3), for the choice of angles of
the input state from the set $\Theta=\\{0,\pi/4\\}$. Moreover, this conjecture
was recently proven for a uniform random choice of angles of the input state
(see Eq. 11) from the set $\Theta=[0,2\pi]$ [78]. Furthermore, positive
evidence for conjecture (C2) is given by approximate worst-case hardness
results in [24] (case $\Theta=\\{0,\pi/4\\}$), as well as by recent proofs of
exact average-case hardness and anticoncentration theorems given in [78] for
the larger set of angles (case $\Theta=[0,2\pi]$). The results in [24, 78] are
analogous to approximate worst-case hardness results in [20, 21, 22]; proofs
of anti-concentration of the output distribution in [21, 72]; and exact
average-case hardness results in [79, 31]. For all known quantum advantage
proposals, including ours, proving approximate average-case hardness remains
an open question.

##  4 Near-exact simulation of energy measurements with standard resolution

The previous result establishes a complexity-theoretic obstruction for
classical algorithms to simulate energy measurements of certain local
Hamiltonians in the super-resolution regime. In this section, we investigate
whether the less restrictive standard resolution regime can be efficiently
reached classically. Our main result shows this problem remains hard, with
high complexity theoretic evidence (specifically, a collapse of the Polynomial
Hierarchy, introduced in section 3.3), if we demand exponentially small error
parameters.

######  Theorem 3 (Hardness of near-exact standard-resolution energy
measurements).

Let $H$ be a local Hamiltonian acting on $n$ qubits. If there exists an
efficient classical algorithm for the energy sampling problem for any such $H$
with product-state inputs; resolution $\delta\in O(1/\mathrm{poly}(n))$;
confidence $\eta=1-O(1/2^{\mathrm{poly}(n)})$; and sampling error $\beta\in
O(1/2^{\mathrm{poly}(n)})$; then the Polynomial Hierarchy collapses to the 3rd
level. Furthermore, the same holds if $H$ is a nearest-neighbor, translation
invariant 5-local Hamiltonian on a 2d lattice.

To demonstrate this theorem, the idea is to show that such a classical
algorithm would efficiently sample an outcome whose probability is $\\#$P-hard
to approximate. This is achieved by constructing local Hamiltonians with two
properties:

  * (i)

there is a unique ground state with energy 0, and a polynomially small gap to
the first excited state.

  * (ii)

the overlap of this ground state with a product state is $\\#$P-hard to
calculate up to an inverse-exponential additive error.

The first condition ensures that a standard-resolution energy measurement
protocol is capable of efficiently discriminating the ground state from the
rest of the spectra, while the second ensures that a near-exact sampling
measurement samples from a $\\#$P-hard probability.

We provide two examples of families of local Hamiltonians that fulfill these
properties in Secs. 4.1. The first example is presented in Secs. 4.1.1 and is
a translation-invariant version of the 5-local cluster state Hamiltonian from
Eq. (10). By construction, the ground state is related to an output state of
the quantum circuit $U_{2D}$ and hence property (ii) follows directly from the
results of Ref. [24]. The second example, presented in Sec. 4.1.2, is a
4-local Hamiltonian based on Feynman-Kitaev (FK) circuit-to-Hamiltonian
constructions [51, 80], used in the proof of equivalence between adiabatic and
circuit model quantum computation [80]. This construction, although more
complicated than the first example, gives a general technique to relate the
output state of an arbitrary poly-size quantum circuit to the ground state of
a local Hamiltonian. Consequently, all the results on $\\#$P-hardness of
output probabilities of quantum circuits can be translated to results on
hardness of Energy Sampling with standard resolution.

Using these examples of local Hamiltonians, we present the proof of Theorem 3
in Sec. 4.2, following standard arguments from the quantum advantage
literature.

###  4.1 Physical examples

####  4.1.1 A 5-local translationally invariant Hamiltonian

We consider the Hamiltonian family defined in Eq. (10). If we pick a uniform
choice of weights $v_{j}:=1/n,j=1,\ldots,n$, the resulting Hamiltonian is
5-local nearest-neighbor and translation-invariant. In particular, up to
single-qubit rotations, it is the well-known 2D cluster state Hamiltonian [70,
71]:

$H_{2D}\left[\vec{v}\right]=\frac{1}{n}\sum_{j=1}^{n}X_{j}\prod_{j:(j,l)\in
E_{2D}}Z_{l}.$ (22)

This model is mapped to a trivial unentangled one via the unitary (8), which
has constant depth. In a condensed matter sense, this implies that
$H_{2D}\left[\vec{v}\right]$ can be seen as the energy density operator (the
Hamiltonian divided by the number of particles in the lattice) of a gapped
model in the trivial phase [81, 82]. In particular,
$H_{2D}\left[\vec{v}\right]$ has an inverse polynomial gap $\Omega(1/n)$,
which ensures that a standard-resolution measurement can efficiently
discriminate its ground state from the rest of the spectra.

Upon an ideal energy measurement of a state $\ket{\psi_{\theta,x}}$ from Eq.
(11), the probability of obtaining outcome $E=0$, which is the ground-state
energy, is given by

$P_{GS}=|\bra{0}^{\otimes n}U_{2D}\ket{\psi_{\theta,x}}|^{2}.$ (23)

Such probabilities are related to partition functions of Ising models and were
shown to be $\\#$P-hard to approximate to relative error or to inverse-
exponential additive error [21, 24]. This is a crucial ingredient for the
proof of Theorem 3, presented in Sec. 4.2.

####  4.1.2  Circuit-to-Hamiltonian constructions

So far, we have only considered Hamiltonians whose diagonalization is known.
Here we present a more general strategy to relate probabilities of outputs of
_arbitrary quantum circuits_ to probabilities of outcomes of energy
measurements, while keeping the Hamiltonian local. To do so, we use the so-
called circuit-to-Hamiltonian constructions, based on Feynman clocks, that
have been widely used in Hamiltonian complexity and adiabatic quantum
computation [51, 80]. In fact, the Hamiltonian that has the properties we
require is used in the proof that the adiabatic model of quantum computation
is equivalent to the circuit model [80]. More precisely, we consider the final
Hamiltonian at the end of the adiabatic schedule, since it has polynomially
small gap and its ground state contains a information about the final state of
a quantum computation, as we explain in what follows. We describe this
construction in more detail since we build upon it to demonstrate our main
result in Sec. 5.2.

Let us consider a quantum circuit of $T=\mathrm{poly}(n)$ gates
$U=U_{T}U_{T-1}...U_{1}$ and the propagation Hamiltonian

$H_{prop}=\frac{1}{2}\sum_{t=1}^{T}\mathbbm{1}\otimes\ket{t}\bra{t}_{c}+\mathbbm{1}\otimes\ket{t-1}\bra{t-1}_{c}\\\
-U_{t}\otimes\ket{t}\bra{t-1}_{c}-U_{t}^{\dagger}\otimes\ket{t-1}\bra{t}_{c},$
(24)

which is defined on a Hilbert space with $T+1$ clock states $\ket{t}_{c}$ and
$n$ qubits. We will describe the case, where the clock is implemented with
$O(\log(T+1))$ qubits, in which case the Hamiltonian $H_{prop.}$ is
$O(\log(n))$-local. Nevertheless our result extends to 5-local Hamiltonians
using the unary clock implementation of Ref. [51], or 4-local Hamiltonians
using a clock implementation based on the hopping of a excitation in a
unidimensional spin-chain (see [83] for a recent discussion on different clock
implementations). We define the states

$\displaystyle\ket{\eta_{y}(0)}$ $\displaystyle=\ket{y}\ket{0}_{c}$
$\displaystyle\ket{\eta_{y}(t)}$
$\displaystyle=U_{t}U_{t-1}...U_{1}\ket{y}\ket{t}_{c},t\in\\{1,...,T\\},$ (25)

and the subspaces

$\Omega^{(y)}=\text{span}\\{\ket{\eta_{y}(t)},t=0,...,T\\}.$ (26)

We note that for each $y$ the subspace $\Omega^{(y)}$ is invariant under the
action of the Hamiltonian $H_{prop}$. Hence, we can diagonalize the
Hamiltonian in each of these subspaces, obtaining the $2^{n}$ degenerate
ground states

$\ket{\psi^{(y)}}=\frac{1}{\sqrt{T+1}}\sum_{t=0}^{T}\ket{\eta_{y}(t)}$ (27)

which have energy $0$. These are called history states as they contain
information about the whole history of a quantum computation. In particular,
we have that
$\bra{x}\bra{t}_{c}\ket{\psi^{(y)}}=\frac{1}{\sqrt{T+1}}\bra{x}U_{t}...U_{1}\ket{y}$,
which is proportional to the transition amplitude from state $y$ to state $x$
after $t$ steps of the computation. It can be shown that $H_{prop}$ is
positive semidefinite and has a gap of $O(1/T^{2})$ with respect to the first
excited state [51].

To fix the initial state of the computation to be $\ket{0}$ it is necessary to
add an energy penalty Hamiltonian of the form

$H_{init}=\sum_{i=1}^{n}\ket{1}\bra{1}_{i}\otimes\ket{0}\bra{0}_{c},$ (28)

where the projector $\ket{1}\bra{1}_{i}$ acts on the $i$_th_ qubit, ensuring
that when the clock is in its initial state $\ket{0}_{c}$, any computational
basis state which is not the $\ket{0}$ state is energetically penalized. The
total Hamiltonian

$H=H_{init}+H_{prop}$ (29)

has a single ground state $\ket{\psi^{(0)}}$ with energy $0$ and gap
$\Delta=O(1/T^{3})$ [51], ensuring the discernibility of the groundstate via a
standard-resolution measurement. Hence, the probability of observing the
ground state of $H$ upon an ideal energy measurement of a state
$\ket{y}\ket{T}_{c}$ is given by

$\displaystyle P_{GS}$
$\displaystyle=|\bra{\psi^{(0)}}(\ket{y}\ket{T}_{c})|^{2}$ (30)
$\displaystyle=\frac{1}{T+1}|\braket{y}{U}{0}|^{2}$ (31)

This quantity is $\\#$P-hard to estimate to relative error or inverse-
exponential additive error for several families of quantum circuits such as
IQP [21, 84], or boson sampling [20] (which can also be implemented in the
circuit model [85]), among others. Depending on the family of circuits we
choose, this defines a family of local Hamiltonians of the form given by Eq.
(29) for which Theorem 3 applies.

###  4.2 Proof of Theorem 3

Before we proceed, let us prove the following technical lemma that will be
useful in what follows.

######  Lemma 1.

Let $H$ be a Hamiltonian with eigenvalues in the interval $[0,1]$, a ground
state energy $E_{GS}=0$ and a gap $\Delta$ to the first excited state. Given
this Hamiltonian and an initial state $\ket{\psi}$, consider a
$\beta-$approximate Energy sampler with $\delta=\Delta/3$ and confidence
$\eta=1-\epsilon$. Let $q^{\prime}_{GS}$ be the probability that this sampler
outputs a value $E_{m}$ in the interval $[0,\Delta/3]$. We have the following
bounds on $q^{\prime}_{GS}$:

$|q^{\prime}_{GS}-P_{GS}|\leq\epsilon+\beta.$ (32)

where

$P_{GS}=\braket{\psi}{\Pi_{GS}}{\psi}$ (33)

and $\Pi_{GS}$ is the spectral projection in the ground state space of $H$.

###### Proof.

An energy sampler with parameters $\eta=1-\epsilon$ and $\delta=\Delta/3$
outputs a value in the interval $[0,\Delta/3]$ with probability

$q_{GS}\geq(1-\epsilon)P_{GS}\geq P_{GS}-\epsilon,$ (34)

which follows from the constraints on the outcome probability distribution
defined by Eq. (4). On the other hand, the probability of obtaining a value in
the interval $[2\Delta/3,1]$ obeys the bound

$\displaystyle\bar{q}$
$\displaystyle\geq(1-\epsilon)\bra{\psi}\Pi_{[\Delta,1]}\ket{\psi}$ (35)
$\displaystyle=(1-\epsilon)(1-P_{GS}),$ (36)

where we used Eq. (4) in the first step and the fact that
$\Pi_{GS}+\Pi_{[\Delta,1]}=I$ in the second step, which follows from the
assumption that the Hamiltonian has a gap $\Delta$. In addition, the $\bar{q}$
and $q_{GS}$ probabilities sum up to 1, which implies that

$\displaystyle q_{GS}$ $\displaystyle=1-\bar{q}$ (37) $\displaystyle\leq
1-(1-\epsilon)(1-P_{GS})$ (38) $\displaystyle=(1-\epsilon)P_{GS}+\epsilon\leq
P_{GS}+\epsilon,$ (39)

where in the second step we used Eq. (36). Combining equations (34 and (39))
we obtain the inequality

$|q_{GS}-P_{GS}|\leq\epsilon.$ (40)

A $\beta$-approximate Energy sampler with parameters $\eta=1-\epsilon$ and
$\delta=\Delta/3$ outputs a value in the interval $[0,\Delta/3]$ with
probability $q^{\prime}_{GS}$, where $|q^{\prime}_{GS}-q_{GS}|\leq\beta$.
Hence, using (40) and the triangle inequality we conclude the proof. ∎

With this lemma we are ready to prove Theorem 3.

###### Proof of theorem 3.

Lemma 1 implies that an approximate energy sampler with
$\delta=\Delta/3=1/(3n+3)$, $\epsilon=1-\eta=1/2^{\mathrm{poly}(n)}$ and
$\beta=1/2^{\mathrm{poly}(n)}$ would output $E_{m}\in[0,\Delta/3]$ with a
probability $q_{GS}=P_{GS}+\epsilon^{\prime}$, where $|\epsilon^{\prime}|$ is
an exponentially small number. Furthermore, we have seen two constructions of
local Hamiltonians for which $P_{GS}$ is $\\#$P-hard to estimate with inverse-
exponential additive error (Eqs. (23) and (31)). Let us assume there is an
efficient classical energy sampler with the parameters defined in Theorem 3
for these Hamiltonians. Following standard arguments in the literature of
quantum advantage [20, 21], this would imply the probability $q^{\prime}_{GS}$
could be estimated up to an inverse-exponential additive error via
Stockmeyer’s algorithm, an algorithm in the third level of the polynomial
hierarchy (PH). This implies that a $\\#$P-hard problem could be solved in the
third level of the PH and hence the PH would collapse to the third level.
Stockmeyer’s algorithm and its connection to quantum advantage is reviewed in
more detail in Sec. 5.1 and Appendix D. ∎

This gives strong evidence to the impossibility for classical computers to
efficiently simulate energy sampling problems with confidence exponentially
close to optimal, i.e., $\eta=1-1/2^{\mathrm{poly}(n)}$, inverse-exponential
$\beta=1/2^{\mathrm{poly}(n)}$, and standard resolution
$\delta=1/\mathrm{poly}(n)$. This can be seen as a classical hardness result
for the problem of simulating an ideal implementation of the quantum phase
estimation algorithm (with confidence amplification [44]), for measuring the
energy of a local Hamiltonian with standard resolution.

##  5 Computational Complexity of approximate energy sampling with standard
resolution

The previous section provided evidence that classical algorithms for near-
exact simulations of energy measurements of many-body Hamiltonians cannot
efficiently simulate measurements with standard resolution
($\delta=1/\mathrm{poly}(n)$). From a physical perspective, it is natural to
ask whether the previous complexity theoretic results involving collapses of
the Polynomial Hierarchy can be extended to approximate simulations.
Specifically, we are interested in extending Theorem 3 to the regime where the
measurement failure probability $\epsilon$ and the sampling error $\beta$ are
small constants. We present a no-go lemma and one positive result.

Approximate sampling measurements of Hamiltonians in the standard resolution
regime can be interpreted as examples of quantum sampling problems with a
small number of output qubits. It would thus be tempting to apply the
Stockmeyer-based techniques of Refs. [21, 20] (cf. section 3.4) to study the
complexity theory of classically simulating such measurements. Unfortunately,
we first point out in Lemma 2 (section 5.1) that the Stockmeyer argument
cannot meaningfully link the hardness of approximate sampling problems with
few outputs to a Polynomial Hierarchy collapse. This is due to an error
parameter in such proofs that becomes too large precisely for quantum
computations where the number of measured output qubits is “small”: constant
or $O(\log(n))$. This issue is generic and affects, e.g., existing quantum
advantage proposals based on variations of the one-clean-qubit (DQC1) model
[49, 50].

In spite of the above hurdle, our second result (Theorem 4, section 5.2 below)
gives complexity theoretic evidence of the classical hardness of approximate
standard-resolution energy sampling. The result links the worst-case
complexity of this problem to that of classically simulating universal quantum
computers. Specifically, we prove that the existence of an efficient classical
algorithm for this problem would imply the ability to efficiently classically
compute arbitrary marginal output probabilities of universal poly-sized
quantum circuits (a BQP-hard task, in the language of complexity theory [65]).
This provides evidence against an efficient classical simulation of energy
measurements with standard resolution.

The first result in this section highlights the existence of a gap in the
complexity theoretic understanding of quantum approximate sampling problems
with small output support. The second opens the possibility to develop quantum
advantage tests based on such problems. This is however complicated by the
lack of tools to study the average-case hardness of this problem. We discuss
this latter possibility and associated open challenges in section 5.3.

###  5.1 Sampling problems with small support “do not simply” collapse the
Polynomial Hierarchy

Here, we point out a technical obstruction towards extending available
approaches in quantum advantage proofs [21, 20] to the standard-resolution
approximate energy sampling problems. First, we remark that any algorithm for
energy measurements with standard resolution samples from a probability
distribution with $\mathrm{poly}(n)$ outcomes. This is in contrast with most
quantum advantage proposals, which have an outcome space that is exponentially
large. This fact constitutes a roadblock for the application of the proof
technique of Refs. [21, 20].

To understand the limitation, we recall (section 3.4) that the traditional
approach to prove quantum advantage results via sampling problems heavily
relies on Stockmeyer’s algorithm Refs. [21, 20]. The goal there is to induce a
Polynomial Hierarchy (PH) collapse assuming, among other assumptions, that it
is #P-hard to approximate the output probabilities of a quantum device up to
very small errors: specifically, a constant relative one if we have
anticoncentration. Unfortunately, as shown next, if we tried to adapt the same
argument to rule out classical algorithms for sampling problems with poly-
sized support, we would have to adopt an analogous average-case conjecture
where the error is too large for the assumption to be plausible. Below, we
characterize these errors for circuits with an arbitrary number of output
bits. Let $q_{U}$ be the output probability distribution of a quantum circuit
$U$, and $0_{m}$ be the string with $m$ zeroes.

######  Lemma 2 (Stockmeyer error).

Let $\mathcal{Q}_{n},{n\in\mathbb{N}}$ be a family of uniformly-generated
poly-size $n$-qubit quantum circuits with $m$ output bits and the hiding
property

$\forall U\in\mathcal{Q}_{n},x\in\\{0,1\\}^{m},\exists U_{x}\in\
\mathcal{Q}_{n}:q_{U}(x)=q_{U_{x}}(0_{m}).$

Assume there exists a classical algorithm $\mathcal{A}$ that samples from
$q_{U}$ with $\ell_{1}$ error $\beta$ in $O(\mathrm{poly}(n,1/\beta))$ time
given $U\in\mathcal{Q}_{n}$. Then, for any $0<\nu<1$, there is an
$\textnormal{FBPP}^{\textnormal{NP}}$ algorithm which, given access to
$\mathcal{A}$, approximates $q_{U}(x),x\in\\{0,1\\}^{m}$ up to additive error
$\varepsilon$

$\varepsilon\in
O\left(\frac{q_{U}(x)}{\mathrm{poly}(n)}+\frac{\beta}{2^{m}\nu}\left(1+\frac{1}{\mathrm{poly}(n)}\right)\right).$
(41)

with probability $1-\nu$ over the choice of $x\in\\{0,1\\}^{m}$.

We provide the proof of this lemma in Appendix D. There, we also argue in
detail how the Stockmeyer argument fails to provide a plausible collapse of PH
in the $m<\log(n)$ regime. The basic intuition is as follows. In Refs. [20,
21], where $m=n$, the algorithm provides a relative error estimation of the
output probabilities in average case if we assume anticoncentration. This
problem is then conjectured to be $\\#$P-hard. Evidence for this conjecture is
provided by worst-case results and near-exact worst-to-average reductions
(section 3.4). Because of Toda’s theorem, that provides a collapse of PH,
since PH$\subset$P${}^{\textrm{\\#{P}}}$. In the $m<\log(n)$ regime, the right
hand side of Eq. (41) has a term that can only be upper bounded by an inverse
polynomial, which limits the accuracy $\varepsilon$ of the algorithm that
estimates probabilities in $\textnormal{FBPP}^{\textnormal{NP}}$.
Unfortunately, to induce the same collapse of PH in the case $m<\log(n)$, we
would need to show that it is $\\#$P-hard to estimate quantum output
probabilities with an inverse polynomial error. This is however implausible
because, if it was true, then quantum computers could efficiently solve
$\\#$P-hard problems, which is believed to be impossible [86, 79].

###  5.2 Hardness of approximate energy measurements with standard resolution

In the previous section, we discussed obstructions towards proving quantum
advantage results based on known complexity theoretic conjectures for
approximate standard-resolution energy sampling, as well as quantum sampling
problems with small support. This points towards a tension between having
practical physically-motivated quantum advantage schemes and strong complexity
theoretic proofs of classical hardness.

This motivates us to consider different approaches to prove physically-
motivated quantum advantage results, which do not rely on the Stockmeyer
argument of Refs. [21, 20]. In fact, alternative evidence for the
impossibility of developing efficient classical algorithms to simulate
approximate energy measurements with standard resolution can be drawn from the
work of Refs. [42, 43]. Therein, the authors show that a procedure for energy
measurements of local Hamiltonians achieving a resolution of
$1/\mathrm{poly}(n)$ and confidence $\eta=1-\epsilon$, where $\epsilon$ is a
small constant, can be used to decide any problem in BQP, the class of
decision problems that can be efficiently solved by a quantum computer [65].
The Hamiltonians considered therein are $4$-local non-nearest neighbor
Hamiltonians in [42] and translational invariant chains of qudits in [43].
Although these works did not explicitly consider $\beta$ sampling errors, they
can be easily extended to the approximate energy sampling regime where $\beta$
is a small constant. Consequently, the existence of a classical algorithm for
standard resolution approximate energy sampling problems, would imply that
classical computers could solve efficiently any problem in BQP.

In this section, we provide additional complexity-theoretic evidence that
classical computers cannot efficiently simulate energy measurements with
standard resolution. We do so by showing that this problem is at least as hard
as estimating marginals of output probability distributions of universal
circuits, a problem that is more general than considering only decision
problems solvable by quantum circuits. Specifically, our main result (Theorem
4) shows that the ability to simulate the approximate energy sampling problem
efficiently would imply the existence of a “poly box”, in the notation of
[87]: i.e., an efficient algorithm to estimate any marginal output probability
of any poly-size quantum circuit up to a polynomially small error, a BQP-hard
task.

######  Definition 5 (Probability estimator or “poly-box”).

Let $U$ be a poly-size quantum circuit acting on $n$-qubits. An algorithm is
said to be a probability estimator or poly-box for $U$ if it can compute an
estimate $\hat{p}$ of any marginal probability $p$ of the distribution
$|\bra{x}U\ket{0}|^{2}$ such that

$\Pr(|p-\hat{p}|\leq\delta_{p})\geq 1-\epsilon_{p}$ (42)

in time $O(poly(n,\delta_{p}^{-1},\log({\epsilon_{p}}^{-1})))$.

The connection between standard-resolution energy measurements and probability
estimators is stated precisely in the following theorem.

######  Theorem 4 (Hardness of approximate standard-resolution energy
measurements).

Let us assume the existence of a classical algorithm for approximate energy
sampling for 4-local Hamiltonians on product states, reaching a resolution
$\delta$, confidence $\eta=1-\epsilon$ and sampling error $\beta$, with a
running time of $O(\mathrm{poly}(n,\delta^{-1},\beta^{-1},\epsilon^{-1}))$.
This implies existence of a classical poly-box for arbitrary poly-size quantum
circuits.

Theorem 4 shows that standard-resolution energy measurements can be used to
estimate arbitrary output probabilities of quantum circuits, and not just of
single-qubit measurements, generalizing the results of [42, 43].

To prove theorem 4, we show that it is possible to encode any marginal
probability of a quantum circuit’s output distribution as the probability of
measuring the ground state energy of a certain 4-local Feynman-Kitaev
Hamiltonian, which has a polynomially small gap. Hence, with a polynomial
number of energy measurements, the marginal probability can be estimated with
a polynomially small error via the Hoeffding bound.

###### Proof of Theorem 4.

Let $p$ be an output probability or a marginal probability of a poly-size
quantum circuit $U$ from a family of quantum circuits $\mathcal{C}$ acting on
$n$-qubits. For a fixed computational basis state input of the circuit
$\ket{x}$, we can write the marginal probability as

$p=\sum_{y\in S^{*}}|\bra{y}U\ket{x}|^{2}.$ (43)

for a given set of bit strings $S^{*}$. More precisely, we define $S^{*}$ has
a set of $2^{n-l}$ bit strings of size $n$ where $l$ bits are fixed. We pick
the bits at different positions $k_{i}$, with $k_{i}\in\\{1,...,n\\}$,
$i\in\\{1,...,l\\}$, such that the $k_{i}$_th_ bit is fixed to a chosen value
$b_{i}\in\\{0,1\\}$ i.e.,

$S^{*}=\\{y\leavevmode\nobreak\ :y_{k_{i}}=b_{i},i\in\\{1,..,l\\}\\}.$ (44)

To demonstrate the theorem we will first show that it is possible to construct
a local Hamiltonian with two properties: the ground state energy is $E_{GS}=0$
and there is a polynomially small gap to the first excited state. Moreover,
the probability of observing the outcome $E_{GS}=0$ after an energy
measurement of this Hamiltonian on a product state is given by
$P_{GS}=p/(T+1)$, where $T$ is the number of gates of circuit $U$. Such
Hamiltonian can be constructed by a simple modification of the circuit-to-
Hamiltonian construction mentioned in Sec. 4.1.2 in the following way.

Let us consider the gate decomposition of circuit $U=U_{T}U_{T-1}...U_{1}$ and
the propagation Hamiltonian from Eq. (24). Similarly to Sec. 4.1.2, we will
prove our result for the simplest case, where the clock is implemented with
$O(\log(T+1))$ qubits and the Hamiltonian $H_{prop.}$ is $O(\log(n))$-local.
The physicality of the Hamiltonian can be improved to 4-local or 5-local,
using standard clock implementations [51, 83].

We recall that the subspaces

$\Omega^{(y)}=\text{span}\\{\ket{\eta_{y}(t)},t=0,...,T\\},$ (45)

with the states $\ket{\eta_{y}(t)}$ defined in Eq. (25), are invariant under
the action of the Hamiltonian $H_{prop}$. Furthermore, $H_{prop}$ has $2^{n}$
degenerate ground states $\ket{\psi^{(y)}}$ (see Eq. (27)) with energy zero.
Another important property that will be used in the following proof is that
$H_{prop}$ is positive semidefinite and has a gap of $O(1/T^{2})$ with respect
to the first excited state [51].

To relate the probability of observing the ground state to the marginal
probability $p$ we need to lift the ground state such that $\ket{\psi^{(y)}}$
is a ground state only for $y\in S^{*}$. With this aim, we introduce the
following penalty Hamiltonian

$H_{pen}=\sum_{i=1}^{l}\left(\ket{\bar{b_{i}}}\bra{\bar{b_{i}}}\right)_{k_{i}}\otimes\ket{0}\bra{0}_{c},$
(46)

where $\bar{b_{i}}$ denotes the NOT of the bit $b_{i}$ and the projector
$\left(\ket{\bar{b_{i}}}\bra{\bar{b_{i}}}\right)_{k_{i}}$ acts non-trivially
only on the $k_{i}$_th_ qubit (and as identity in the other qubits). It can
easily be checked that $\ket{\eta_{y}(t)}$ are eigenstates of $H_{pen}$ with
eigenenergies

$\bra{\eta_{y}(t)}H_{pen}\ket{\eta_{y}(t)}=\begin{cases}0,\text{\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ if\leavevmode\nobreak\ }t\neq 0\\\
0,\text{\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
if\leavevmode\nobreak\ }t=0\wedge y\in S^{*}\\\
C_{y},\text{\leavevmode\nobreak\ if\leavevmode\nobreak\ }t=0\wedge y\notin
S^{*}\\\ \end{cases}$ (47)

where $C_{y}\geq 1$, since if $y\notin S^{*}$ then at least one bit of $y$ in
one of the positions $k_{i}$ is in state $\bar{b_{i}}$. From Eq. (47) it can
be seen that $H_{pen}$ has no effect in the subspaces $\Omega^{(y)}$ with
$y\in S^{*}$.

Let us now determine the ground states of $H=H_{prop}+H_{pen}$ as well as the
gap to the first excited state. First, let us note that the subspaces
$\Omega^{(y)}$ from Eq. (45) are also invariant under the action of $H_{pen}$,
which trivially follows from the fact that $\ket{\eta_{y}(t)}$ are eigenstates
of $H_{pen}$. Furthermore, since both $H_{prop}$ and $H_{pen}$ are positive
semidefinite matrices, $H$ is also positive semidefinite.

Let us denote as $H^{(y)}$ and $H_{prop}^{(y)}$ the Hamiltonian $H$ and
$H_{prop}$ restricted to the subspace $\Omega^{(y)}$, respectively. Then we
have

$\displaystyle H^{(y)}$
$\displaystyle=H_{prop}^{(y)},\text{\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ if\leavevmode\nobreak\ }y\in S^{*}$ (48) $\displaystyle
H^{(y)}$
$\displaystyle=H_{prop}^{(y)}+C_{y}\ket{\eta_{y}(0)}\bra{\eta_{y}(0)},\text{\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ if\leavevmode\nobreak\ }y\notin
S^{*},$ (49)

which follows from Eq. (47). Hence, for $y\in S^{*}$ the state of $H^{(y)}$
with the lowest energy is $\ket{\psi^{(y)}}$, which has energy $0$, and the
first excited state has energy $O(1/T^{2})$.

The final step needed to demonstrate that these are the only ground states of
$H$ is to show that the state with the lowest energy of $H^{(y)}$, with
$y\notin S^{*}$, has an energy at least of $O(1/T^{3})$. This implies that no
state belonging to the subspace $\Omega^{(y)}$ with $y\notin S^{*}$ is a
ground state of the whole Hamiltonian $H$ and that this Hamiltonian has indeed
a gap of $1/\mathrm{poly}(n)$. To show this we use the geometrical lemma [51,
88].

######  Lemma 3.

(Geometrical Lemma) Let $H_{1}$ and $H_{2}$ be two Hamiltonians with ground
state energies $g_{1}$ and $g_{2}$, respectively. Also, let $\Delta_{1}$ and
$\Delta_{2}$ be the their respective gaps to their first excited states. Then
the ground state energy of $H$ is $g\geq g_{1}+g_{2}+\Delta(1-\cos(\theta))$,
where $\Delta=\text{min}(\Delta_{1},\Delta_{2})$ and $cos(\theta)$ is the
maximum possible absolute value of the overlap between a ground state of
$H_{1}$ with a ground state of $H_{2}$.

We will use this lemma considering $H_{1}=H_{prop}^{(y)}$ and
$H_{2}=C_{y}\ket{\eta_{y}(0)}\bra{\eta_{y}(0)}$. In this case, we have
$g_{1}=0$, $\Delta_{1}=O(1/T^{2})$ and $g_{2}=0$, $\Delta_{1}=C_{y}\geq 1$.
Hence we can take $\Delta=O(1/T^{2})$. Moreover, the ground state of
$H_{prop}^{(y)}$ is $\ket{\psi^{(y)}}$ whereas the ground state space of
$C_{y}\ket{\eta_{y}(0)}\bra{\eta_{y}(0)}$ is spanned by the states
$\ket{\eta_{y}(t)}$, for $t=1,...,T$.

In order to calculate the maximum overlap between the two ground spaces, let
us define $\Pi_{2}=\sum_{t=1}^{T}\ket{\eta_{y}(t)}\bra{\eta_{y}(t)}$. The
state belonging to the ground state space of $H_{2}$ with the maximum overlap
with $\ket{\psi^{(y)}}$ is
$\ket{v_{2}}=\Pi_{2}\ket{\psi^{(y)}}/\sqrt{\bra{\psi^{(y)}}\Pi_{2}\ket{\psi^{(y)}}}$.
Hence, we obtain

$\displaystyle\cos(\theta)$
$\displaystyle=|\braket{v_{2}}{\psi^{(y)}}|=\sqrt{\bra{\psi^{(y)}}\Pi_{2}\ket{\psi^{(y)}}}$
(50) $\displaystyle=\sqrt{\frac{T}{T+1}}\leq 1-\frac{1}{2T}.$ (51)

Hence, the geometrical lemma implies that the lowest energy state of $H^{(y)}$
for $y\notin S^{*}$ is $O(1/T^{3})$.

This shows that the states $\ket{\psi^{(y)}}$ for $y\in S^{*}$ are the ground
states of $H=H_{prop}+H_{pen}$. Consequently, the probability of observing $0$
upon an ideal energy measurement of a quantum state $\ket{x}\ket{T}$ is given
by

$\displaystyle P_{GS}$ $\displaystyle=\frac{1}{T+1}\sum_{y\in
S^{*}}|\bra{\psi^{(y)}}(\ket{x}\ket{T})|^{2}$
$\displaystyle=\frac{1}{T+1}\sum_{y\in
S^{*}}|\bra{y}U_{T}U_{T-1}...U_{1}\ket{x}|^{2}.$ $\displaystyle=\frac{p}{T+1}$
(52)

Let us assume now that we have a classical algorithm for approximate energy
sampling for Hamiltonian $H=H_{prop}+H_{pen}$ and initial state
$\ket{x}\ket{T}$, with a running time
$O(\mathrm{poly}(n,\delta^{-1},\beta^{-1},\epsilon^{-1}))$. In what follows we
demonstrate that we can estimate $p$ from such energy sampler by making use of
Lemma 1 together with Hoeffding inequality. First, we choose the parameters of
the energy sampler to be $\delta=\Delta/3=O(1/T^{3})$, where $\Delta$ is the
gap of Hamiltonian $H$ and

$\epsilon+\beta=\frac{\delta_{p}}{2(T+1)},$ (53)

where $\delta_{p}$ is defined in Eq. (42). By assumption, the energy sampling
algorithm would output one sample in time $\mathrm{poly}(n,\delta_{p}^{-1})$.
Given the choice of parameters $\epsilon,\beta$ we obtain from Lemma 1 that
the probability of obtaining an outcome $E_{m}\in[-\Delta/3,\Delta/3]$ is
given by $q^{\prime}_{GS}$ such that

$|q^{\prime}_{GS}-P_{GS}|\leq\frac{\delta_{p}}{2(T+1)}.$ (54)

We now demonstrate that we can estimate $q^{\prime}_{GS}$ within an additive
error $\delta_{p}/(2T+2)$ by querying the energy sampler $s$ times and
computing the average number of times an event in the interval
$[-\Delta/3,\Delta/3]$ is observed. Let us denote this estimator by
$\hat{q}_{s}$. By Hoeffdings inequality we have that

$\Pr\left(|q^{\prime}_{GS}-\hat{q}_{s}|\geq\frac{\delta_{p}}{2(T+1)}\right)\leq
2\exp\left(-\frac{2s{\delta_{p}}^{2}}{4(T+1)^{2}}\right)$ (55)

In order to reach an error of $\epsilon_{p}$ we choose

$\displaystyle\exp\left(-\frac{s{\delta_{p}}^{2}}{2(T+1)^{2}}\right)=\epsilon_{p}$
(56) $\displaystyle\Leftrightarrow
s=\log{\left(\frac{2}{\epsilon_{p}}\right)}\frac{2(T+1)^{2}}{{\delta_{p}}^{2}}$
(57)

Hence, with $s=O(poly(n,\delta_{p}^{-1},\log({\epsilon_{p}}^{-1})))$ number of
queries to the energy sampler we can obtain the estimator $\hat{q}_{s}$ within
the desired error bound.

Finally we can construct our estimator for $p$ as $\hat{p}=(T+1)\hat{q}_{s}$.
Given the choice of $s$ from Eq. (57) and using Eqs. (54) and (55) we obtain

$\Pr(|p-\hat{p}|\leq\delta_{p})\geq 1-\epsilon_{p}$ (58)

as desired. The number of samples needed is
$s=O(poly(n,\delta_{p}^{-1},\log({\epsilon_{p}}^{-1})))$ and for each sample
we require time $\mathrm{poly}(n,\delta_{p}^{-1})$, which shows that the total
running time to compute $\hat{p}$ is
$O(poly(n,\delta_{p}^{-1},\log({\epsilon_{p}}^{-1})))$ as required by
Definition 5. ∎

###  5.3 Random Energy Measurement (REM) Test

Given that standard-resolution energy measurements are BQP-hard to simulate,
this problem has the potential to be a suitable physically motivated test at
which quantum devices can outperform classical simulations. In particular,
this suggests the following quantum advantage experiments where one measures
the energy of a random local Hamiltonian on an input product state.  Random
Energy Measurement (REM) Test:

  1. 1.

A classical user picks a random many-body local Hamiltonian
$H=\sum_{i}J_{i}h_{i}$, where the local terms $\\{h_{i}\\}_{i}$ and couplings
$\\{J_{j}\\}_{j}$ are chosen from a target class at random, according to a
distribution that is efficient to sample from classically. The latter ensemble
is picked so that complexity theoretic evidence against an efficient classical
simulation is available.

  2. 2.

The experimenter performs an approximate standard-resolution measurement of
the energy of the Hamiltonian $H$ picked from the ensemble.

  3. 3.

The test is to produce samples from the output distribution of the above
protocol in $O(\mathrm{poly}{(n,\delta^{-1},\beta^{-1},\epsilon^{-1})})$ time,
within a $\beta$ error in the total variation distance.

As discussed in section 5.1, this type of test is radically different than
usual sampling problems [20, 21]. Further research is thus deemed necessary to
fully understand its classical simulability. Below, we discuss open directions
for future investigations.

_Complexity of the REM Test._ Theorem 4 provides worst-case evidence against
the classical simulability of standard-resolution energy measurements. Yet, it
provides no insight into the hardness of simulating a _typical_ instance of
this problem for different ensembles of random local Hamiltonians. Natural
candidates that could lead to hard problems on average are, for example,
Feynman-Kitaev Hamiltonians encoding random quantum circuits, frustrated spin
systems [89] and universal quantum Hamiltonians [90]. However, in order to
develop higher confidence against the classical simulability of the REM Test,
it would be required to develop new tools to study average-case complexity of
problems in BQP. This is because known polynomial-interpolation techniques
used in worst-to-average reductions are rather sensitive to noise [31, 91, 78,
92] and cannot be readily applied in the standard-resolution regime.

_Is the REM test easy to verify?_ Commonly-studied quantum sampling problems,
with an exponentially large output space, are difficult to verify [25].
Verifying statistical closure in the total variation distance to the ideal
distribution based on a single-round of classical post-processing requires
exponentially many experimental samples [93]. Although sample-efficient
verification approaches have been proposed [22, 31, 29], the verification
takes exponential time and works under circuit-level assumptions on noise [22,
29, 31] or new complexity conjectures [29]. If reliable single-qubit
measurements are available, a polynomial-time verification is sometimes
possible [30, 24, 28].

On the other hand, measurements with standard resolution could potentially be
easier to verify than commonly-studied sampling problems. Indeed, it is easy
to see that they bypass the no-go theorem in Ref. [93] because of the
polynomial size of the output space: via the Hoeffding bound, collecting
statistics and computing the variation distance to the ideal distribution
gives a trivial brute-force exponential-time verification method with
polynomial sample complexity, which could be applicable in near-term
experiments of limited size. In this context, available verification methods
for BQP-complete problems [94, 95, 96, 30] could potentially be useful.

##  6 Discussion

In this work, we have established energy measurements of many-body
Hamiltonians as a problem that can show a reliable quantum advantage based on
complexity theoretic arguments. We thus make a key step towards bringing
quantum advantage demonstrations closer to physically-motivated questions.

We have analyzed two different regimes regarding the scaling of the cost of
performing the measurement, which can be quantified either by the evolution
time of the experiment or the number of quantum gates applied in a quantum
algorithm such as quantum phase estimation. We have defined a standard-
resolution measurement as a measurement where the cost in increasing the
resolution is polynomial in $1/\delta$, which is the standard performance of
quantum devices for general local Hamiltonians; and super-resolution
measurements, where the measurement cost scales as
$\mathrm{poly}(\log(1/\delta))$, which can be achieved by a quantum device if
we exploit certain knowledge about the Hamiltonian, such as its
diagonalization (or in general, the ability to exponentially fast-forward its
time-evolution [44]).

We prove that for _super-resolution measurements_ it is possible to achieve a
quantum advantage demonstration even when the measurement is approximate (with
a system-size-independent sampling error), based on plausible complexity-
theoretic assumptions similar to ones used in the "quantum computational
supremacy" literature [20, 21, 24, 22, 31, 78]. The quantum advantage
originates in the super-resolution measurement of a simple 5-local cluster
state Hamiltonian on the 2D square lattice on product state inputs. The
protocol can be implemented using the quantum simulation scheme of Ref. [24]
and requires the short time-evolution of a nearest-neighbor on a 2D square
lattice, suitable for implementations in, for example, optical lattices.
Moreover, this scheme can be efficiently certified using reliable single-qubit
measurements. These results open up the possibility of near-term experimental
demonstrations of quantum advantage via energy sampling.

In the _standard-resolution regime_ , we find two types of complexity-
theoretic evidence against the efficient classical simulation of measuring
local Hamiltonians. First, in a reminiscent fashion to early work on IQP
circuits [48], we find a classical simulation to be impossible for simple 2D
translation-invariant Hamiltonians in the near-exact sampling regime with
inverse-exponential sampling errors, unless the Polynomial Hierarchy
collapses. Additionally, we point out limitations of available techniques [20,
21] to extend this quantum advantage result to an approximate-sampling one,
based on Polynomial Hierarchy collapses. Second, using circuit-to-Hamiltonian
constructions and connections to random universal quantum circuits [22, 29,
31], we give alternative complexity-theoretic evidence that approximate
standard-resolution measurements of 4-local Hamiltonians can show a quantum
advantage: a classical simulation here would lead to an efficient classical
estimator of marginal probabilities of universal quantum circuits, a BQP-hard
task [42, 43].

Three potential improvements related to the technical results in our work are:
Firstly, a major challenge would be to tie the hardness of simulating
approximate standard-resolution energy measurements to well-known complexity-
theoretic conjectures beyond BPP$\neq$BQP. This program would require
techniques beyond the Stockmeyer-method and Polynomial-Hierarchy collapses[20,
21]; Secondly, in this manuscript we have not investigated the verifiability
of the standard resolution proposals. However, due to the small size of the
energy output space, classical verification methods similar to those in Refs.
[22, 29, 31] could be developed; Thirdly, it would be interesting to improve
the locality of our Hamiltonians. The locality of the examples based on
5-local Hamiltonians on 2D lattices could, in principle, be improved using the
general techniques presented in Ref. [90], which show that there exist simple
2-local universal Hamiltonians that can reproduce the physics of other
Hamiltonians, including the energy spectrum and measurement statistics. The
examples based on circuit-to-Hamiltonian constructions could be improved using
techniques such as, e.g., perturbation gadgets or space-time circuit-to-
Hamiltonian constructions [97, 98].

We have also introduced the concept of quantum Hamiltonian diagonalization
which, up to our knowledge, is a new concept which can be of interest beyond
the scope of this work. It characterizes a class of Hamiltonians for which
there exists a polynomial-size quantum circuit $U$ mapping its eigenbasis to
the computational basis and whose eigenvalues can be computed efficiently by a
function $f(z)$ on a quantum computer. This guarantees the exponential fast-
forwarding of the dynamics of the Hamiltonian.

For the purposes of demonstrating quantum advantage, we restricted ourselves
to examples where $f(z)$ can be computed efficiently classically – this
simplifies the protocol for super-resolution measurements so it can be
potentially implemented in near-term devices. In this case, the reason why the
energy measurement problem is hard to simulate classically results from the
fact that the populations of the different eigenstates are # P-hard to
approximate. It would be interesting to construct new examples of quantum
advantage for super-resolution energy measurements where the classical
hardness results from the need to sample from the right eigenvalues (to
exponential accuracy) and not only from the right eigenstate populations.

Indeed, Ref. [44] shows that such constructions are, in principle, possible.
Therein, the authors present an academic example of a Hamiltonian which can be
measured by a quantum algorithm (Shor’s algorithm) with super resolution, even
though it is not known how to compute its eigenvalues efficiently classically.
This Hamiltonian is given by $\hat{H}=U_{ME}+U_{ME}^{\dagger}$, where $U_{ME}$
is the unitary implementation of the modular exponentiation used in Shor’s
algorithm. It is interesting to point out that it is possible to find a
quantum diagonalization for the aforementioned Hamiltonian using existing
quantum algorithms for decomposing finite commutative groups [99, 100]. This
academic example shows how quantum algorithms could potentially be helpful for
expanding our knowledge of the inner structure of a given Hamiltonian (here
its quantum diagonalization), which can later be exploited to answer specific
questions about a given physical system more accurately (here obtaining its
spectra). Finding families of Hamiltonians with stronger physical motivation
than this example, for which its quantum diagonalization could be learned
thanks to a quantum algorithm, would offer a new and interesting application
for quantum computers, potentially leading to new exponential speed-ups over
known classical algorithms.

Overall, we believe this work brings a new perspective into questions related
to Hamiltonian complexity [101] by focusing on problems that can be solved
efficiently by quantum devices, unlike problems such as the QMA-complete
ground state problem [35]. Furthermore, we believe it could inspire new
demonstrations of quantum advantage for measuring other quantities of interest
in quantum many-body physics, which would strengthen the belief that quantum
computers and simulators can answer problems about quantum matter beyond the
power of any present or future classical algorithms.

## Acknowledgements

We 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.

## References

  * Gross and Bloch [2017] Christian Gross and Immanuel Bloch.  Quantum simulations with ultracold atoms in optical lattices.  _Science_ , 357(6355):995–1001, 2017.  ISSN 0036-8075.  doi: 10.1126/science.aal3837.
  * Bernien et al. [2017] Hannes Bernien, Sylvain Schwartz, Alexander Keesling, Harry Levine, Ahmed Omran, Hannes Pichler, Soonwon Choi, Alexander S. Zibrov, Manuel Endres, Markus Greiner, Vladan Vuletić, and Mikhail D. Lukin.  Probing many-body dynamics on a 51-atom quantum simulator.  _Nature_ , 551:579–584, 2017.  doi: 10.1038/nature24622.
  * Zhang et al. [2017] J. Zhang, G. Pagano, P. W. Hess, A. Kyprianidis, P. Becker, H. Kaplan, A. V. Gorshkov, Z.-X. Gong, and C. Monroe.  Observation of a many-body dynamical phase transition with a 53-qubit quantum simulator.  _Nature_ , 551:601–604, 2017.  doi: 10.1038/nature24654.
  * Friis et al. [2018] Nicolai Friis, Oliver Marty, Christine Maier, Cornelius Hempel, Milan Holzäpfel, Petar Jurcevic, Martin B. Plenio, Marcus Huber, Christian Roos, Rainer Blatt, and Ben Lanyon.  Observation of entangled states of a fully controlled 20-qubit system.  _Phys. Rev. X_ , 8:021012, 2018.  doi: 10.1103/PhysRevX.8.021012.
  * Neill et al. [2018] C. Neill, P. Roushan, K. Kechedzhi, S. Boixo, S. V. Isakov, V. Smelyanskiy, R. Barends, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, A. Dunsworth, A. Fowler, B. Foxen, R. Graff, E. Jeffrey, J. Kelly, E. Lucero, A. Megrant, J. Mutus, M. Neeley, C. Quintana, D. Sank, A. Vainsencher, J. Wenner, T. C. White, H. Neven, and J. M. Martinis.  A blueprint for demonstrating quantum supremacy with superconducting qubits.  _Science_ , pages 195–199, 2018.  doi: 10.1126/science.aao4309.
  * Arute et al. [2019] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al.  Quantum supremacy using a programmable superconducting processor.  _Nature_ , 574(7779):505–510, 2019.  doi: 10.1038/s41586-019-1666-5.
  * Islam et al. [2015] Rajibul Islam, Ruichao Ma, Philipp M. Preiss, M. Eric Tai, Alexander Lukin, Matthew Rispoli, and Markus Greiner.  Measuring entanglement entropy in a quantum many-body system.  _Nature_ , 528:77–83, 2015.  doi: 10.1038/nature15750.
  * Brydges et al. [2019] Tiff Brydges, Andreas Elben, Petar Jurcevic, Benoit Vermersch, Christine Maier, Ben P. Lanyon, Peter Zoller, Rainer Blatt, and Christian F. Roos.  Probing rényi entanglement entropy via randomized measurements.  _Science_ , 364:260–263, 2019.  doi: 10.1126/science.aau4963.
  * Kaufman et al. [2016] Adam M. Kaufman, M. Eric Tai, Alexander Lukin, Matthew Rispoli, Robert Schittko, Philipp M. Preiss, and Markus Greiner.  Quantum thermalization through entanglement in an isolated many-body system.  _Science_ , 353:794–800, 2016.  doi: 10.1126/science.aaf6725.
  * Keesling et al. [2019] Alexander Keesling, Ahmed Omran, Harry Levine, Hannes Bernien, Hannes Pichler, Soonwon Choi, Rhine Samajdar, Sylvain Schwartz, Pietro Silvi, Subir Sachdev, Peter Zoller, Manuel Endres, Markus Greiner, Vladan Vuletić, and Mikhail D. Lukin.  Quantum kibble–zurek mechanism and critical dynamics on a programmable rydberg simulator.  _Nature_ , 568:207–211, 2019.  doi: 10.1038/s41586-019-1070-1.
  * Choi et al. [2016] Jae-yoon Choi, Sebastian Hild, Johannes Zeiher, Peter Schauß, Antonio Rubio-Abadal, Tarik Yefsah, Vedika Khemani, David A. Huse, Immanuel Bloch, and Christian Gross.  Exploring the many-body localization transition in two dimensions.  _Science_ , 352(6293):1547–1552, June 2016.  doi: 10.1126/science.aaf8834.
  * Rispoli et al. [2019] Matthew Rispoli, Alexander Lukin, Robert Schittko, Sooshin Kim, M. Eric Tai, Julian Léonard, and Markus Greiner.  Quantum critical behaviour at the many-body localization transition.  _Nature_ , 2019.  doi: 10.1038/s41586-019-1527-2.
  * Gärttner et al. [2017] Martin Gärttner, Justin G. Bohnet, Arghavan Safavi-Naini, Michael L. Wall, Bollinger John J., and Ana Maria Rey.  Measuring out-of-time-order correlations and multiple quantum spectra in a trapped-ion quantum magnet.  _Nature Physics_ , 13:781–786, 2017.  doi: 10.1038/nphys4119.
  * Vermersch et al. [2019] B. Vermersch, A. Elben, L. M. Sieberer, N. Y. Yao, and P. Zoller.  Probing scrambling using statistical correlations between randomized measurements.  _Phys. Rev. X_ , 9:021061, Jun 2019.  doi: 10.1103/PhysRevX.9.021061.
  * Satzinger et al. [2021] KJ Satzinger, Y Liu, A Smith, C Knapp, M Newman, C Jones, Z Chen, C Quintana, X Mi, A Dunsworth, et al.  Realizing topologically ordered states on a quantum processor.  _arXiv preprint arXiv:2104.01180_ , 2021.
  * Semeghini et al. [2021] Giulia Semeghini, Harry Levine, Alexander Keesling, Sepehr Ebadi, Tout T Wang, Dolev Bluvstein, Ruben Verresen, Hannes Pichler, Marcin Kalinowski, Rhine Samajdar, et al.  Probing topological spin liquids on a programmable quantum simulator.  _arXiv preprint arXiv:2104.04119_ , 2021.
  * Trotzky et al. [2012] S. Trotzky, Y.-A. Chen, A. Flesch, I. P. McCulloch, U. Schollwöck, J. Eisert, and I. Bloch.  Probing the relaxation towards equilibrium in an isolated strongly correlated one-dimensional Bose gas.  _Nature Phys._ , 8:325–330, 2012.  doi: doi:10.1038/nphys2232.
  * Braun et al. [2015] S. Braun, M. Friesdorf, J. S. Hodgman, M. Schreiber, J. P. Ronzheimer, A. Riera, M. del Rey, I. Bloch, J. Eisert, and U. Schneider.  Emergence of coherence and the dynamics of quantum phase transitions.  _PNAS_ , 112:3641–3646, March 2015.  doi: 10.1073/pnas.1408861112.
  * Tang [2019] Ewin Tang.  A quantum-inspired classical algorithm for recommendation systems.  In _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing_ , pages 217–228. ACM, 2019.  doi: 10.1145/3313276.3316310.
  * Aaronson and Arkhipov [2011] Scott Aaronson and Alex Arkhipov.  The computational complexity of linear optics.  In _Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing_ , STOC ’11, page 333–342, New York, NY, USA, 2011. Association for Computing Machinery.  ISBN 9781450306911.  doi: 10.1145/1993636.1993682.
  * Bremner et al. [2016] Michael J. Bremner, Ashley Montanaro, and Dan J. Shepherd.  Average-case complexity versus approximate simulation of commuting quantum computations.  _Phys. Rev. Lett._ , 117:080501, Aug 2016.  doi: 10.1103/PhysRevLett.117.080501.
  * Boixo et al. [2018] Sergio Boixo, Sergei V. Isakov, Vadim N. Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J. Bremner, John M. Martinis, and Hartmut Neven.  Characterizing quantum supremacy in near-term devices.  _Nature Physics_ , page 1, April 2018.  ISSN 1745-2481.  doi: 10.1038/s41567-018-0124-x.
  * Gao et al. [2017] Xun Gao, Sheng-Tao Wang, and L.-M. Duan.  Quantum supremacy for simulating a translation-invariant ising spin model.  _Phys. Rev. Lett._ , 118:040502, Jan 2017.  doi: 10.1103/PhysRevLett.118.040502.
  * Bermejo-Vega et al. [2018] Juan Bermejo-Vega, Dominik Hangleiter, Martin Schwarz, Robert Raussendorf, and Jens Eisert.  Architectures for quantum simulation showing a quantum speedup.  _Phys. Rev. X_ , 8:021010, Apr 2018.  doi: 10.1103/PhysRevX.8.021010.
  * Harrow and Montanaro [2017] Aram W Harrow and Ashley Montanaro.  Quantum computational supremacy.  _Nature_ , 549(7671):203, 2017.  doi: 10.1038/nature23458.
  * Preskill [2018] John Preskill.  Quantum Computing in the NISQ era and beyond.  _Quantum_ , 2:79, August 2018.  ISSN 2521-327X.  doi: 10.22331/q-2018-08-06-79.
  * Bremner et al. [2017] Michael J. Bremner, Ashley Montanaro, and Dan J. Shepherd.  Achieving quantum supremacy with sparse and noisy commuting quantum computations.  _Quantum_ , 1:8, April 2017.  doi: 10.22331/q-2017-04-25-8.
  * Miller et al. [2017] J. Miller, S. Sanders, and A. Miyake.  Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification.  _Phys. Rev. A_ , 96(6):062320, December 2017.  doi: 10.1103/PhysRevA.96.062320.
  * Aaronson and Chen [2017] Scott Aaronson and Lijie Chen.  Complexity-theoretic foundations of quantum supremacy experiments.  In _Proceedings of the 32Nd Computational Complexity Conference_ , CCC ’17, pages 22:1–22:67, Germany, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  ISBN 978-3-95977-040-8.  doi: 10.4230/LIPIcs.CCC.2017.22.
  * Hangleiter et al. [2017] D. Hangleiter, M. Kliesch, M. Schwarz, and J. Eisert.  Direct certification of a class of quantum simulations.  _Quantum Sci. Technol._ , 2(1):015004, 2017.  ISSN 2058-9565.  doi: 10.1088/2058-9565/2/1/015004.
  * Bouland et al. [2019] A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani.  Quantum supremacy and the complexity of random circuit sampling.  _Nature Phys._ , 15:159–163, March 2019.  doi: 10.1038/s41567-018-0318-2.
  * Deshpande et al. [2018] Abhinav Deshpande, Bill Fefferman, Minh C. Tran, Michael Foss-Feig, and Alexey V. Gorshkov.  Dynamical Phase Transitions in Sampling Complexity.  _Physical Review Letters_ , 121(3):030501, July 2018.  doi: 10.1103/PhysRevLett.121.030501.
  * Muraleedharan et al. [2019] Gopikrishnan Muraleedharan, Akimasa Miyake, and Ivan H. Deutsch.  Quantum computational supremacy in the sampling of bosonic random walkers on a one-dimensional lattice.  _New Journal of Physics_ , 21(5):055003, May 2019\.  ISSN 1367-2630.  doi: 10.1088/1367-2630/ab0610.  arXiv: 1805.01858.
  * Maskara et al. [2019] Nishad Maskara, Abhinav Deshpande, Minh C. Tran, Adam Ehrenberg, Bill Fefferman, and Alexey V. Gorshkov.  Complexity phase diagram for interacting and long-range bosonic Hamiltonians.  _arXiv:1906.04178_ , June 2019.
  * Kitaev [1995] A Yu Kitaev.  Quantum measurements and the abelian stabilizer problem.  _arXiv:quant-ph/9511026_ , 1995.
  * Abrams and Lloyd [1999] Daniel S. Abrams and Seth Lloyd.  Quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors.  _Phys. Rev. Lett._ , 83:5162–5165, Dec 1999.  doi: 10.1103/PhysRevLett.83.5162.
  * Yang et al. [2020] Dayou Yang, Andrey Grankin, Lukas M Sieberer, Denis V Vasilyev, and Peter Zoller.  Quantum non-demolition measurement of a many-body hamiltonian.  _Nature communications_ , 11(1):1–8, 2020.  doi: 10.1038/s41467-020-14489-5.
  * Huh et al. [2015] Joonsuk Huh, Gian Giacomo Guerreschi, Borja Peropadre, Jarrod R McClean, and Alán Aspuru-Guzik.  Boson sampling for molecular vibronic spectra.  _Nature Photonics_ , 9(9):615, 2015.  doi: 10.1038/nphoton.2015.153.
  * Hamilton et al. [2017] Craig S. Hamilton, Regina Kruse, Linda Sansoni, Sonja Barkhofen, Christine Silberhorn, and Igor Jex.  Gaussian boson sampling.  _Phys. Rev. Lett._ , 119:170501, Oct 2017.  doi: 10.1103/PhysRevLett.119.170501.
  * [40] Vincenzo Barone (Editor).  _Computational Strategies for Spectroscopy: from Small Molecules to Nano Systems_.  Wiley, Hoboken, New Jersey, USA, 2012.  ISBN 0470470178.
  * Santoro et al. [2007] Fabrizio Santoro, Roberto Improta, Alessandro Lami, Julien Bloino, and Vincenzo Barone.  Effective method to compute franck-condon integrals for optical spectra of large molecules in solution.  _The Journal of Chemical Physics_ , 126(8):084509, 2007.  doi: 10.1063/1.2437197.
  * Wocjan and Zhang [2006] Pawel Wocjan and Shengyu Zhang.  Several natural bqp-complete problems.  _arXiv:quant-ph/0606179_ , 2006.
  * Janzing et al. [2008] Dominik Janzing, Pawel Wocjan, and Shengyu Zhang.  A single-shot measurement of the energy of product states in a translation invariant spin chain can replace any quantum computation.  _New Journal of Physics_ , 10(9):093004, 2008\.  doi: 10.1088/1367-2630/10/9/093004.
  * Atia and Aharonov [2017] Yosi Atia and Dorit Aharonov.  Fast-forwarding of hamiltonians and exponentially precise measurements.  _Nature communications_ , 8(1):1572, 2017.  doi: 10.1038/s41467-017-01637-7.
  * Von Neumann [2018] John Von Neumann.  _Mathematical foundations of quantum mechanics: New edition_.  Princeton university press, 2018.
  * Aharonov et al. [2002] Y. Aharonov, S. Massar, and S. Popescu.  Measuring energy, estimating hamiltonians, and the time-energy uncertainty relation.  _Phys. Rev. A_ , 66:052107, Nov 2002.  doi: 10.1103/PhysRevA.66.052107.
  * Wocjan et al. [2003] Pawel Wocjan, Dominik Janzing, Thomas Decker, and Thomas Beth.  Measuring 4-local n-qubit observables could probabilistically solve PSPACE.  _arXiv:quant-ph/0308011_ , 2003.
  * Shepherd and Bremner [2009] Dan Shepherd and Michael J. Bremner.  Temporally unstructured quantum computation.  _Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences_ , 465(2105):1413–1439, 2009\.  ISSN 1364-5021.  doi: 10.1098/rspa.2008.0443.
  * Morimae et al. [2014] Tomoyuki Morimae, Keisuke Fujii, and Joseph F. Fitzsimons.  Hardness of classically simulating the one-clean-qubit model.  _Phys. Rev. Lett._ , 112:130502, Apr 2014.  doi: 10.1103/PhysRevLett.112.130502.
  * Morimae [2017] Tomoyuki Morimae.  Hardness of classically sampling the one-clean-qubit model with constant total variation distance error.  _Phys. Rev. A_ , 96:040302, Oct 2017.  doi: 10.1103/PhysRevA.96.040302.
  * Kitaev et al. [2002] Alexei Yu Kitaev, Alexander Shen, and Mikhail N Vyalyi.  _Classical and quantum computation_.  Number 47. American Mathematical Soc., 2002.
  * Childs et al. [2002] Andrew M. Childs, Enrico Deotto, Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Andrew J. Landahl.  Quantum search by measurement.  _Phys. Rev. A_ , 66:032314, Sep 2002.  doi: 10.1103/PhysRevA.66.032314.
  * Lloyd [1996] Seth Lloyd.  Universal quantum simulators.  _Science_ , pages 1073–1078, 1996.  doi: 10.1126/science.273.5278.1073.
  * Berry et al. [2015a] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma.  Simulating hamiltonian dynamics with a truncated taylor series.  _Phys. Rev. Lett._ , 114:090502, Mar 2015a.  doi: 10.1103/PhysRevLett.114.090502.
  * Somma et al. [2002] R. Somma, G. Ortiz, J. E. Gubernatis, E. Knill, and R. Laflamme.  Simulating physical phenomena by quantum networks.  _Phys. Rev. A_ , 65:042323, Apr 2002.  doi: 10.1103/PhysRevA.65.042323.
  * Somma [2019] Rolando D Somma.  Quantum eigenvalue estimation via time series analysis.  _New Journal of Physics_ , 21(12):123025, 2019\.  doi: 10.1088/1367-2630/ab5c60.
  * Roushan et al. [2017] P. Roushan, C. Neill, J. Tangpanitanon, V. M. Bastidas, A. Megrant, R. Barends, Y. Chen, Z. Chen, B. Chiaro, A. Dunsworth, A. Fowler, B. Foxen, M. Giustina, E. Jeffrey, J. Kelly, E. Lucero, J. Mutus, M. Neeley, C. Quintana, D. Sank, A. Vainsencher, J. Wenner, T. White, H. Neven, D. G. Angelakis, and J. Martinis.  Spectroscopic signatures of localization with interacting photons in superconducting qubits.  _Science_ , 358(6367):1175–1179, 2017.  ISSN 0036-8075.  doi: 10.1126/science.aao1401.
  * Terhal and DiVincenzo [2004] B. M. Terhal and D. P. DiVincenzo.  Adaptive quantum computation, constant depth quantum circuits and arthur-merlin games.  _Quantum Inf. Comput._ , 4(2):134–145, 2004.
  * Bremner et al. [2010] Michael J. Bremner, Richard Jozsa, and Dan J. Shepherd.  Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy.  _Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences_ , 2010.  ISSN 1364-5021.  doi: 10.1098/rspa.2010.0301.
  * Berry et al. [2015b] D. W. Berry, A. M. Childs, and R. Kothari.  Hamiltonian simulation with nearly optimal dependence on all parameters.  In _2015 IEEE 56th Annual Symposium on Foundations of Computer Science_ , pages 792–809, Oct 2015b.  doi: 10.1109/FOCS.2015.54.
  * Low and Chuang [2017] Guang Hao Low and Isaac L. Chuang.  Optimal hamiltonian simulation by quantum signal processing.  _Phys. Rev. Lett._ , 118:010501, Jan 2017.  doi: 10.1103/PhysRevLett.118.010501.
  * Low and Chuang [2019] Guang Hao Low and Isaac L. Chuang.  Hamiltonian Simulation by Qubitization.  _Quantum_ , 3:163, July 2019.  ISSN 2521-327X.  doi: 10.22331/q-2019-07-12-163.
  * Chakraborty et al. [2019] Shantanav Chakraborty, András Gilyén, and Stacey Jeffery.  The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation.  In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, _46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)_ , volume 132 of _Leibniz International Proceedings in Informatics (LIPIcs)_ , pages 33:1–33:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  ISBN 978-3-95977-109-2.  doi: 10.4230/LIPIcs.ICALP.2019.33.