# Theoretical and Experimental Perspectives of Quantum Verification

Jose Carrasco  Institute for Theoretical Physics, University of Innsbruck,
Austria  Andreas Elben  Center for Quantum Physics, University of Innsbruck,
Austria  Institute for Quantum Optics and Quantum Information of the Austrian
Academy of Sciences, Innsbruck, Austria  Christian Kokail  Center for Quantum
Physics, University of Innsbruck, Austria  Institute for Quantum Optics and
Quantum Information of the Austrian Academy of Sciences, Innsbruck, Austria
Barbara Kraus  Institute for Theoretical Physics, University of Innsbruck,
Austria  Peter Zoller  Center for Quantum Physics, University of Innsbruck,
Austria  Institute for Quantum Optics and Quantum Information of the Austrian
Academy of Sciences, Innsbruck, Austria

###### Abstract

In this perspective we discuss verification of quantum devices in the context
of specific examples, formulated as proposed experiments. Our first example is
verification of analog quantum simulators as Hamiltonian learning, where the
input Hamiltonian as design goal is compared with the parent Hamiltonian for
the quantum states prepared on the device. The second example discusses cross-
device verification on the quantum level, i.e. by comparing quantum states
prepared on different quantum devices. We focus in particular on protocols
using randomized measurements, and we propose establishing a central data
repository, where existing experimental devices and platforms can be compared.
In our final example, we address verification of the output of a quantum
device from a computer science perspective, addressing the question of how a
user of a quantum processor can be certain about the correctness of its
output, and propose minimal demonstrations on present day devices.

##  I Introduction

The dream and vision of now more than two decades to build quantum computers
and quantum simulators has materialized as nascent programmable quantum
devices in today’s laboratories Deutsch (2020); Preskill (2018); National
Academies of Sciences and Medicine (2020). While first generation experiments
focused on basic demonstration of building blocks of quantum information
processing, quantum laboratories now host programmable intermediate scale
quantum devices, which - while still imperfect and noisy - open the
perspective of building quantum machines, which fulfill the promise of
becoming more powerful than their classical counterparts. Significant advances
in building small scale quantum computers and quantum simulators have been
reported with various physical platforms, from atomic and photonic systems to
solid state devices. A central aspect in further developments is verification
of proper functioning of these quantum devices, including cross-device and
cross-platform verification. Quantum verification is particularly challenging
in regimes where comparison with classical simulation of quantum devices is no
longer feasible.

Quantum characterization, validation and verification (QCVV) is a well-
developed field in quantum information theory, and we refer to reviews Eisert
_et al._ (2020); Gheorghi  _et al._ (2019); Šupić and Bowles (2020) and
tutorials Kliesch and Roth (2021) on this topic. The challenge in designing
practical techniques to characterize quantum processes on intermediate and
large-scale quantum devices is related to the (in general) exponential scaling
of number of experiments and digital post-processing resources with system
size, as is manifest in quantum process tomography or state tomography.
Exponential resources can be circumvented by extracting partial information
about quantum processes providing a figure of merit, such as a process
fidelity. However, such protocols also face the requirement of decoupling the
state preparation and measurement errors from a process fidelity. Applications
of well established protocols in experimental settings, for example as
randomized or cycle benchmarking of quantum computers Erhard  _et al._ (2019)
or verifiable measurement-based quantum computation Barz  _et al._ (2013) have
been reported.

In this ‘perspective’ we wish to look forward to possible near future
experiments addressing verification of quantum computers and quantum
simulators, and in particular venturing into less explored territories. We
illustrate aspects of verification, which are physically relevant and
conceptually complementary to previous work, by describing three experimental
scenarios as ‘proposed experiments’. Our discussion aims at connecting recent
theoretical results with possible implementation of verification protocols in
existing experimental settings. Clearly, different communities from quantum
experimentalists to theorists, and computer scientists look at perspectives on
verification from quite different angles, and our examples are chosen to
reflect this diversity.

Our first example illustrates verification of analog quantum simulators Cirac
and Zoller (2012); National Academies of Sciences and Medicine (2020) via
Hamiltonian learning Bairey  _et al._ (2019); Qi and Ranard (2019); Li  _et
al._ (2020). The central idea is to verify the analog quantum simulator by
comparing the desired many-body Hamiltonian, i.e. the Hamiltonian to be
implemented, with the actual, physically realized Hamiltonian, which can be
efficiently reconstructed from measurements of quantum states prepared on the
quantum device. This is applicable to, and immediately relevant for present
analog quantum simulation experiments for spin and Hubbard models with atoms
and ions, and superconducting qubits Altman  _et al._ ; Tarruell and Sanchez-
Palencia (2018); Browaeys and Lahaye (2020); Morgado and Whitlock ; Ebadi  _et
al._ ; Mazurenko  _et al._ (2017); Argüello-Luengo  _et al._ (2019); Schäfer
_et al._ (2020); Kokail  _et al._ (2019); Monroe  _et al._ ; Huang  _et al._
(2020a).

In our second example we address cross-device and cross-platform verification
as applicable to quantum computers and quantum simulators. Here the goal is
the pairwise comparison of quantum states implemented on different quantum
devices on the level of the full many-qubit wave function, or for reduced
density matrices of subsystems. To this end, results of randomized
measurements, performed on each device separately, can be classically
correlated to estimate the fidelity of two quantum states, with efficiency
scaling better with (sub-) system size than what is achieved in quantum state
tomography Elben  _et al._ (2020); Flammia (2020). We envision a community
effort where data from randomized measurements are uploaded to a central data
repository, enabling the direct comparison of multiple quantum devices for a
defined set of quantum problems, specified either as quantum circuits and
algorithms or Hamiltonian evolution.

Finally, in our third example we move on to verification from a computer
scientist perspective, and address the question of how a user of a quantum
processor can be certain about the correctness of its output. This question
becomes particularly important in case the user of a quantum device does not
have direct access to it (e.g. cloud computing). Is it even possible for a
user to rely on the result if they cannot verify it efficiently themselves?
This question has been answered in the affirmative in case the user has access
to a limited amount of quantum resources Morimae and Fujii (2013); Morimae
(2014); Hayashi and Morimae (2015); Gheorghiu  _et al._ (2015); Hajdušek  _et
al._ ; Fitzsimons and Kashefi (2017); Aharonov  _et al._ ; Takeuchi  _et al._
(2019). Interestingly, such a verification of the output is feasible even via
purely classical means Mahadev . However, not very surprisingly, the resources
required to implement such a verification protocol are beyond reach with
current technology. Due to the rapid technological developments and the
accompanying need for the ability to verify the output of a computation, we
propose here a proof-of-principle experiment to implement such a verification
protocol that is feasible with current technologies.

##  II Verification of Analog Quantum Simulators via Hamiltonian Learning

The goal of quantum simulation is to solve the quantum many-body problem Cirac
and Zoller (2012), from strongly correlated quantum materials in condensed
matter physics Tarruell and Sanchez-Palencia (2018) to quantum field theories
in high-energy physics Bañuls  _et al._ (2020), or modeling of complex
molecules and their dynamics in quantum chemistry McArdle  _et al._ (2020);
Argüello-Luengo  _et al._ (2019). Building an analog quantum simulator amounts
to realizing in the laboratory synthetic, programmable quantum matter as an
isolated quantum system. Here, first of all, a specified many-body Hamiltonian
$H$ must be implemented faithfully in highly controllable quantum system with
given physical resources. Furthermore, quantum states of matter must be
prepared on the physical quantum device corresponding to equilibrium phases,
e.g. as ground states, or represent non-equilibrium phenomena as in quench
dynamics.

Remarkable progress has been made recently in building analog quantum
simulators to emulate quantum many-body systems. Examples are the realization
of lattice spin-models with trapped ions Kokail  _et al._ (2019); Monroe  _et
al._ , Rydberg tweezer arrays Browaeys and Lahaye (2020); Morgado and Whitlock
; Ebadi  _et al._ , superconducting devices Huang  _et al._ (2020a), or
Hubbard models with ultracold bosonic or fermionic atoms in optical lattices
Tarruell and Sanchez-Palencia (2018); Mazurenko  _et al._ (2017); Schäfer  _et
al._ (2020). While analog quantum simulation can be viewed as special purpose
quantum computing with the rather focused task of emulating a many-body
systems via a specified $H$, the unique experimental feature is the ability to
scale to rather large particle numbers. This is in contrast to present day
quantum computers, which provide a high-fidelity universal gate set for a
small number of qubits.

Today’s ability of analog quantum simulators to prepare and store on a
scalable quantum device a highly entangled many-body state, while solving a
quantum problem of physical relevance, fulfills one of the original visions of
Feynman’s proposal of quantum simulation. However, this also raises the
question of verification in regimes where comparison with classical
computations with controlled error, such as tensor network techniques, are no
longer available. This includes also higher dimensional lattice models, or
with fermionic particles, and quench dynamics.

The proper functioning of a quantum simulator can be assured by comparing
experiment vs. theory Hauke  _et al._ (2012), or predictions from two
different experimental quantum devices. This can be done on the level of
comparing expectation values of relevant observables, e.g. on the most
elementary level by comparing phase diagrams Hauke  _et al._ (2012), or the
increasingly complex hierarchies of correlation functions Schweigler  _et al._
(2017). We return to approaches of directly comparing quantum states in Sec.
III below.

Verification by Hamiltonian Learning: Instead, we will rephrase here
verification of an analog quantum simulator as comparing the ‘input’
Hamiltonian, specified as the design goal for the quantum simulator, with the
actual Hamiltonian realized on the physical device. This latter, experimental
Hamiltonian can be determined via ‘Hamiltonian tomography’, or ‘Hamiltonian
learning’, i.e. inferring from measurements under certain conditions the
parent Hamiltonian underlying the experimentally prepared quantum state Bairey
_et al._ (2019); Qi and Ranard (2019).

Figure 1: (a) Schematic illustration of the protocol for verifying a local
Hamiltonian from local measurements. (b) Number of required measurements
(number of experimental runs) per constraint to achieve a certain parameter
distance $\parallel\\!\Delta\hat{\boldsymbol{c}}\\!\parallel$ =
$\parallel\\!\hat{\boldsymbol{c}}-\tilde{\hat{\boldsymbol{c}}}\\!\parallel$
for a $3\times 4$ isotropic Fermi-Hubbard model with hole-doping ($N_{f}=10$
fermions). Here $\hat{\boldsymbol{c}}$ denotes the normalized vector
$\hat{\boldsymbol{c}}=\boldsymbol{c}/\parallel\\!\boldsymbol{c}\\!\parallel$
with $\boldsymbol{c}=\\{c_{m}\\}$ the expansion coefficients of the
Hamiltonian $H$ in the local operator basis: $H=\sum_{m}c_{m}S_{m}$. (c)
Smallest achievable parameter distanace
$\parallel\\!\Delta\hat{\boldsymbol{c}}\\!\parallel$ as a function of the
number of constraints $N_{C}$.

Hamiltonians of many-body physics consist of a small set of terms which are
(quasi-) local and consist of few-body interactions, i.e. $H=\sum_{i}h_{i}$
with $h_{i}$ quasi-local terms. Thus, for a given $H$, only a small set of
physical parameters determines the accessible quantum states and their
entanglement structure: for example, as ground state,
${H}\ket{\Psi_{G}}=E_{G}\ket{\Psi_{G}}$, as a finite temperature state in the
form of a Gibbs ensemble $\sim\exp{(-\beta{H})}$; or as generator of the
quench dynamics with an initial (pure) state $\ket{\Psi_{0}}$ evolving in time
as $\ket{\Psi_{t}}=\exp{(-i{H}t)}\ket{\Psi_{0}}$.

Remarkably, as shown in recent work Bairey  _et al._ (2019); Qi and Ranard
(2019); Li  _et al._ (2020), it is the local and few-body structure of
physical Hamiltonians in operator space which allows efficient Hamiltonian
tomography via measurements from experimentally prepared (single) quantum
states on the quantum simulator. These states include the ground state, a
Gibbs state, or states produced in quench dynamics. It is thus the restricted
operator content of Hamiltonians, which promises scalable Hamiltonian learning
with system size, i.e. makes Hamiltonian tomography efficient.

Here we wish to outline ‘Hamiltonian verification’ for a Fermi Hubbard model.
This can be implemented with atoms in an optical lattice, and observed with a
quantum gas microscope Tarruell and Sanchez-Palencia (2018); Mazurenko  _et
al._ (2017). To be specific, we apply the protocol of Ref. Bairey  _et al._
(2019) for reconstruction of the parent Hamiltonian from an experimentally
prepared ground state. Similar results apply to energy eigenstates, thermal
states, or any stationary state. We simulate experimental runs of the
protocols including the measurement budget, thus assessing accuracy and
convergence Kokail  _et al._ .

The protocol of Ref. Bairey  _et al._ (2019) describes learning of local
Hamiltonians from local measurements. The starting point is the assumption of
an experimentally prepared stationary state $\rho$, as described above. The
protocol finds the parent Hamiltonian ${H}$ from ${\rho}$ via the steady state
condition $[{H},{\rho}]=0$. As ${\rho}$ is stationary under ${H}$, so is the
expectation value of any observable ${A}$:
$\partial_{t}\braket{{A}}=\braket{-i[{A},{H}]}=0$. The latter equation can be
used to obtain a set of linear constraints from which ${H}$ can be
reconstructed. Consequently, for lattice systems the algorithm can be
summarized as follows (see also Fig. 1 a):

  1. 1.

Expand the Hamiltonian ${H}$ in a local operator basis
${H}=\sum_{m=1}^{M}c_{m}{S}_{m}$. For a $k$-local ${H}$,
$M\sim\mathcal{O}(L^{k})$ basis elements are required, with $L$ the number of
lattice site.

  2. 2.

Select a set of $N_{C}>M$ linearly independent operators (constraints)
$\\{{A}_{n}\\}_{n=1}^{N_{C}}$.

  3. 3.

Construct a system of equations
$\braket{-i[{A}_{n},{H}]}=\sum_{m}c_{m}\braket{-i[{A}_{n},{S}_{m}]}=K\boldsymbol{c}=0$
by measuring the matrix elements $K_{nm}=\braket{-i[{A}_{n},{S}_{m}]}$.

  4. 4.

Find the lowest right singular vector $\tilde{\boldsymbol{c}}$ of $K$, which
minimizes the norm $\parallel\\!K\boldsymbol{c}\\!\parallel$.

As stated in Ref. Qi and Ranard (2019), the locality of ${H}$ implies that
such a Hamiltonian reconstruction will be unique. The reconstructed parameters
$\tilde{\boldsymbol{c}}$ can be cross-checked with respect to the parameters
of an input Hamiltonian and serve as quantifier for the verification of the
quantum simulator. The required number of experimental runs is controlled by
the gap of the correlation matrix $\mathcal{M}=K^{T}K$, which strongly depends
on the type and number of constraints Bairey  _et al._ (2019). In the limit of
all possible constraints, the matrix $\mathcal{M}$ coincides with the
correlation matrix defined by Qi and Ranard Qi and Ranard (2019). The lowest
eigenvalue of this matrix corresponds to the Hamiltonian variance measured on
the input state, which has been used previously for experimental verification
of variationally prepared many-body states Kokail  _et al._ (2019).

In Fig. 1 (b) and (c) we illustrate Hamiltonian learning for a Fermi-Hubbard
model

$\displaystyle{H}=-J\sum_{\braket{ij}\sigma}\left({c}_{i\sigma}^{\dagger}{c}_{j\sigma}+\text{H.c.}\right)+U\sum_{i}n_{i\uparrow}n_{i\downarrow}$
(1)

on a 2D square lattice Kokail  _et al._ . Here ${c}_{i\sigma}^{\dagger}$
(${c}_{i\sigma}$) denote creation (annihilation) operators of
spin-$\frac{1}{2}$ fermions at lattice sites $i$ and
${n}_{i\sigma}={c}_{i\sigma}^{\dagger}{c}_{i\sigma}$. Consequently, in this
example the local basis $\\{S_{m}\\}_{m=1}^{M}$ consists of hopping operators
for all bonds $(i,j)$: $({c}_{i\sigma}^{\dagger}{c}_{j\sigma}+\text{H.c.})$
for each spin component $\sigma$, and of operators counting double occupancies
on the individual sites $i$: $n_{i\uparrow}n_{i\downarrow}$. In case of the
$3\times 4$ lattice studied in Fig. 1, the operator basis therefore includes
$M=46$ elements. As an input state for the protocol we take the ground state
in the strongly repulsive regime ($J=1$, $U=8$) and introduce a small hole
doping of $n=0.83$. As a set of constraints we adopt the operators
${A}_{ijk}=i({c}_{i\sigma}^{\dagger}{c}_{j\sigma}-\text{H.c.})n_{k\sigma^{\prime}}$
in which $i$, $j$ and $k$ are nearest-neighbor sites 111Since the ground state
wave function of the Fermi Hubbard model as well as the Hamiltonian ${H}$ are
real-valued, the constraints must be chosen as imaginary operators in order to
obtain nonzero matrix elements $K_{nm}=\braket{-i[{A}_{n},{S}_{m}]}$.. The
particular combinations of sites $\\{i,j,k\\}$ is chosen in such a way that
the rows of the matrix $K$ are linearly independent. Note that obtaining the
matrix elements $K_{nm}=\braket{-i[{A}_{n},{S}_{m}]}$ requires the measurement
of locally resolved atomic currents $\mathcal{J}_{i\leftrightarrow
j}^{\sigma}=i({c}_{i\sigma}^{\dagger}{c}_{j\sigma}-\text{H.c.})$, where $j$
can be located within 2 lattice constants around $i$. In experiments with
atoms in optical lattices, these currents can be accessed by inducing
superexchange oscillations accompanied by spin resolved measurements in a
quantum gas microscope Schweizer  _et al._ (2016); Keßler and Marquardt
(2014).

Fig. 1 (b) shows the relation between the distance of the exact vs the
reconstructed Hamiltonian parameters
$\parallel\\!\Delta\hat{\boldsymbol{c}}\\!\parallel$ and the number of
measurements per constraint on a $3\times 4$ Hubbard lattice. Panel (c)
displays the improvement in quality of the Hamiltonian reconstruction as
additional constraints ${A}_{ijk}$ are added to system of equations
$K\boldsymbol{c}=0$. As can be seen, the Hamiltonian can be recovered exactly
as the number of constraints $N_{C}$ approaches the number of elements $M$ in
the operator basis $\\{S_{m}\\}_{m=1}^{M}$. We note that the total measurement
budget can be optimized via arranging the operators $[{A}_{n},{S}_{m}]$ into
commuting groups, such that they can be evaluated from the same measurement
outcomes Kokail  _et al._ .

In the Hamiltonian learning protocol outlined above, the number of required
measurement to obtain a fixed parameter distance
$\parallel\\!\Delta\hat{\boldsymbol{c}}\\!\parallel$ scales polynomially with
the system size Bairey  _et al._ (2019). Recent work demonstrates that the
method can be extended for recovering Linbladians from steady states,
potentially allowing an efficient recovery of dissipative processes Bairey
_et al._ (2020). Future investigations will have to include the relation of
the type and number of constraints to the gap of the correlation matrix which
determines the total number of required experimental runs, as well the role of
measurement errors and decoherence (see for instance Ref. Poggi  _et al._
(2020)).

An entirely different verification protocol, which can also be applied to
quantum simulation, is Cross-Device Verification described in the following
Section. There, verification is achieved by cross-checking the results from
two quantum simulators simulating the same physics by measuring overlaps of
quantum states on the level of reduced density operators for various subsystem
sizes.

##  III Cross-Device Verification of quantum computations and quantum
simulations

In the previous section, we presented the verification of an analog quantum
simulator by comparing the Hamiltonian actually realized in the device with
the input or target Hamiltonian. A different approach to verification, aiming
to gain confidence into the output of a quantum simulation or quantum
computation is to run the simulation or computation on various different
quantum devices, and compare the outcomes with each other, and - if available
- with a idealized theoretical simulation [see for an illustration Fig. 2 a)].
Such cross-comparison can be implemented on different levels of
sophistication. While quantum simulations have been compared on the level of
low-order observables Hauke  _et al._ (2012), for instance order parameters
characterizing phase diagrams, recent protocols aim to compare full quantum
states Flammia and Liu (2011); da Silva  _et al._ (2011); Elben  _et al._
(2020); Huang  _et al._ (2020b).

A convenient measure of comparison of two, possibly mixed, quantum states
$\rho_{1}$ and $\rho_{2}$ are quantum fidelities $F(\rho_{1},\rho_{2})$. While
various definitions of fidelities exist, they have in common that
$F(\rho_{1},\rho_{2})=1$ for identical states $\rho_{1}=\rho_{2}$, and that
$F(\rho_{1},\rho_{2})=|\braket{\psi_{1}}{\psi_{2}}|^{2}$ for pure states
$\rho_{1}=\ket{\psi_{1}}\bra{\psi_{1}}$ and
$\rho_{2}=\ket{\psi_{2}}\bra{\psi_{2}}$. A standard choice is provided by the
Uhlmann fidelity
$F_{U}(\rho_{1},\rho_{2})=\textrm{Tr}\left[\sqrt{\sqrt{\rho_{1}}\rho_{2}\sqrt{\rho_{1}}}\right]$
Jozsa (1994) which is in general difficult to access, experimentally and also
via numerical calculations Liang  _et al._ (2019). Simpler alternatives are
Hilbert-Schmidt fidelities Liang  _et al._ (2019), such as

$\displaystyle
F_{\text{max}}(\rho_{1},\rho_{2})=\frac{\textrm{Tr}\left[\rho_{1}\rho_{2}\right]}{\max\\{\textrm{Tr}\left[\rho_{1}^{2}\right],\textrm{Tr}\left[\rho_{2}^{2}\right]\\}}.$
(2)

Here, $F_{\text{max}}$ defines a metric on the space of density matrices Liang
_et al._ (2019) and coincides with the Uhlmann fidelity if one state is pure
Liang  _et al._ (2019).

Figure 2: (a) Cross-device verification of unknown quantum states
$\rho_{1},\rho_{2},\dots$ prepared on different quantum machines QM1, QM2,
…based on various platforms via (b) a central, standardized data-repository
and classical communication of randomized measurements (local random unitaries
and measurement outcomes). In regimes, where a classical simulation is
possible, the implemented states can additionally be compared to a theoretical
target state $\rho_{T}$. (c) Experiment-theory fidelities between a quantum
states prepared in a trapped ion quantum simulator and its classical
simulation as a function of the subsystem size $N_{A}$ (the total system
consists of $10$ qubits) for various evolution times (different colors) after
a quantum quench in a long-range Ising model Brydges  _et al._ (2019),
reprinted from Ref. Elben  _et al._ (2020).

To measure quantum fidelities, various approaches exist. A pure _quantum_
protocol would establish a quantum link, teleport quantum states and compare
states locally, for instance via a SWAP-test Ekert  _et al._ (2002); Abanin
and Demler (2012); Daley  _et al._ (2012). While such overlap measurements
have been demonstrated locally in seminal experiments Islam  _et al._ (2015);
Kaufman  _et al._ (2016); Linke  _et al._ (2018), a quantum link teleporting
large quantum states of many particles with high accuracy between two quantum
devices is not expected to be available in the near future.

Today, protocols relying on _classical_ communication between many-body
quantum devices are thus required. Here, ultimate brute-force tests are
quantum state and quantum progress tomography which aim for a full classical
reconstruction, allowing for a classical comparison, of quantum states or
processes. Even incorporating recent advances, such as compressed sensing for
density matrices with low rank Gross  _et al._ (2010), such approach requires
however at least $3^{N}$ measurements to accurately determine an arbitrary $N$
qubit states. Efficient methods, such as tensor network Cramer  _et al._
(2010); Lanyon  _et al._ (2017) or neural network tomography Torlai  _et al._
(2018), have been developed, rely however on a special structure of the states
of interest.

A direct approach towards fidelity estimation is provided by randomized
measurements van Enk and Beenakker (2012); Elben  _et al._ (2018); Brydges
_et al._ (2019); Elben  _et al._ (2019, 2020); Huang  _et al._ (2020b);
Ketterer  _et al._ ; Knips (2020). Here, a randomized measurement on a
$N$–qubit quantum state $\rho$ is performed by the application of a unitary
$U$, chosen at random from a tomographically complete set and a subsequent
measurement in the computational basis $\left\\{\ket{\mathbf{s}}\right\\}$.
Statistical correlations of such randomized measurements, performed
sequentially on a single quantum device, allow for tomographic reconstruction
of the quantum state Ohliger  _et al._ (2013); Elben  _et al._ (2019); Huang
_et al._ (2020b), but also give direct access to non-local and non-linear
(polynomial) functionals of density matrices such as Rényi entropies van Enk
and Beenakker (2012); Elben  _et al._ (2018); Huang  _et al._ (2020b). In
particular, recent work Huang  _et al._ (2020b) combined randomized
measurements with the notion of shadow tomography Aaronson (2018) which aims
to predict directly expectation values of arbitrary observables, instead of
reconstructing the full density matrix. Using insights from the stabilizer
formalism Gottesman (1997), Ref. Huang  _et al._ (2020b) devised an efficient
implementation of shadow tomography via randomized measurements, which enables
to estimate expectation values of arbitrary (multi-copy) observables with high
precision and rigorous performance guarantees Huang  _et al._ (2020b). This
allows in particular to estimate the fidelity between the quantum state $\rho$
and a known theoretical target. It complements methods such as direct fidelity
estimation da Silva  _et al._ (2011); Flammia and Liu (2011) and randomized
benchmarking Emerson  _et al._ (2005); Dankert  _et al._ (2009); Knill  _et
al._ (2008); Emerson  _et al._ (2007); Magesan  _et al._ (2012); Erhard  _et
al._ (2019), which utilize the absolute knowledge of the theoretical target to
be efficient for certain target states and processes.

Cross-device verification with randomized measurements: In a very general
setting, one faces the situation where two _unknwon_ quantum states have been
prepared on two separate quantum devices, potentially at very different points
in space and time [Fig. 2 a)]. In Ref. Elben  _et al._ (2020) (see also Ref.
Flammia (2020)), it has been proposed to measure the cross-device fidelity
$F_{\text{max}}(\rho_{1},\rho_{2})$ of two unknown quantum states, described
by (reduced) density matrices $\rho_{1}$ and $\rho_{2}$ and prepared on two
separate devices. To this end, randomized measurements are implemented with
the _same_ random unitaries $U$ on both devices. Facilitating the direct
experimental realization, these unitaries $U$ can be local,
$U=\bigotimes_{k=1}^{N}U_{k}$, with $U_{k}$, acting on qubit $k$ and sampled
from a unitary $2$-design Gross  _et al._ (2007); Dankert  _et al._ (2009)
defined on the local Hilbert space $\mathbb{C}^{2}$. From statistical cross-
and auto-correlations of the outcome probabilities
$P_{U}^{(i)}(\mathbf{s})={\rm
Tr}[{U\,\rho_{i}\,U^{\dagger}\ket{\mathbf{s}}\bra{\mathbf{s}}}]$ of the
randomized measurements, the overlap
$\textrm{Tr}\left[\rho_{1}\rho_{2}\right]$ and purities
$\textrm{Tr}\left[\rho_{1}^{2}\right]$
($\textrm{Tr}\left[\rho_{2}^{2}\right]$), and thus
$F_{\text{max}}(\rho_{1},\rho_{2})$, are estimated via

$\displaystyle\textrm{Tr}\left[\rho_{i}\rho_{j}\right]\\!=\\!2^{N}\\!\sum_{\mathbf{s},\mathbf{s}^{\prime}}\\!(-2)^{-\mathcal{D}[\mathbf{s},\mathbf{s}^{\prime}]}\;\overline{P_{U}^{(i)}(\mathbf{s})P_{U}^{(j)}(\mathbf{s}^{\prime})},$
(3)

for $i,j=1,2$. Here, $\overline{\vphantom{a}\dots}$ denotes the ensemble
average over local random unitaries and the Hamming distance
$\mathcal{D}[\mathbf{s},\mathbf{s}^{\prime}]$ between two strings $\mathbf{s}$
and $\mathbf{s}^{\prime}$ is defined as
$\mathcal{D}[\mathbf{s},\mathbf{s}^{\prime}]\equiv\left|\left\\{k\in\\{1,\dots,N\\}\,|\,s_{k}\neq{s}^{\prime}_{k}\right\\}\right|$.

In the regime where a classical simulation of the output is possible, this
protocol can also be used for a experiment-theory comparison (c.f. direct
fidelity estimation Flammia and Liu (2011); da Silva  _et al._ (2011) and
classical shadow tomography Huang  _et al._ (2020b)). In Fig. 2(c),
experiment-theory fidelities between highly entangled quantum states prepared
via quench dynamics in a trapped ion quantum simulator Brydges  _et al._
(2019) and its theoretical simulation are shown Elben  _et al._ (2020). We
note that such experiment-theory comparisons to simple (product) states can
also be used to identify and mitigate errors resulting from imperfect
measurements Elben  _et al._ (2020); Chen  _et al._ ; Koh and Grewal .

Based on numerical simulations, it was found in Ref. Elben  _et al._ (2020)
that the number of necessary experimental runs to estimate the fidelity
$F_{\text{max}}$ up to a fixed statistical error scales exponentially with
subsystem size, $\sim 2^{bN}$. The exponents $b\lesssim 1$ are however
favorable compared to quantum state tomography, enabling fidelity estimation
for (sub-) systems consisting of a few tens of qubits with state of the art
quantum devices. For two very large quantum devices, consisting of several
tens to a few hundreds of qubits, the present protocol allows thus only to
estimate fidelities of possibly disconnected subsystems up to a given size,
determined by the available measurement budget. This data represents very
fine-grained local information on fidelities of subsystems. It remains an open
question whether this information can be combined with additional knowledge of
a few global properties to obtain (at least bounds on) the total system
fidelity.

While we have outlined above protocols to cross-check two individual devices,
we envision a community effort where specific quantum problems, either as
quantum circuits and algorithms, or for quantum simulation are defined, and
data from theoretical simulations as well as measurement data from quantum
devices are uploaded to a central data repository [see for an illustration
Fig. 2 b)]. In regimes, where a classical simulation is possible, an ultimate
reference could here be represented by a theory target state. For larger
quantum devices, reference operations and circuits could be executed, and
density matrices of (sub-)systems could be compared with each other. This
would allow for a standardized, pairwise cross-check of multiple quantum
devices representing various platforms.

The outlined protocols rely on classical communication of randomized
measurement results, and are restricted, due to an exponential scaling of the
number of required experimental runs, to (sub)-systems of a few tens of
qubits. To overcome this challenge, we expect that in the future quantum state
transfer protocols become available to develop efficient fully quantum in
addition to hybrid quantum-classical protocols for cross-checking quantum
devices.

##  IV Verification of the output of an untrusted quantum device

In the validation procedures considered above, the person testing the quantum
processor (the user) has either direct access to the device or trusts the
person operating it. Computer scientists are often concerned about a very
different notion of verification: the verification of the output of a
computation performed by an untrusted device. Such a verifiability demand will
become particularly relevant once quantum devices, that reliably process
hundreds of qubits, become usable as cloud computers.

To demonstrate the need of these verification protocols, let us consider the
various kinds of problems such cloud computers could be utilized for. If the
user employs a quantum computer to solve a problem within NP, such as
factoring a large number into its prime factors, the solution to the problem
is simple: knowing the factors, the output can be efficiently verified with a
classical computer. However, it is believed that quantum computers are capable
of efficiently solving problems that can no longer be efficiently verified
classically, such as simulating quantum many-body systems. How can one then
rely on the output, given that the quantum computer (or the person operating
it) might be malicious and wants to convince the user that the answer to e.g.
a decision problem is "yes" when it is actually "no"? Hence, harnessing the
full power of a quantum device, which is not directly accessible to the user,
brings with it the necessity to derive protocols for verifying its output. The
aim here is to derive quantum verification protocols that allow a
computationally limited (e.g. a classical) user to verify the output of a
(powerful) quantum computer. Complicating matters, is the need to ensure that
a honest prover (the quantum computer) can convince the user of the correct
outcome efficiently Aharonov and Vazirani . To express things more simply, we
will refer now to the user (called verifier) as Alice ($\sf A$) and to the
prover as Bob ($\sf B$).

Verification protocols 222For an excellent, recent review of these protocols
see Gheorghi  _et al._ (2019). where $\sf A$ has access to limited quantum
resources Morimae and Fujii (2013); Morimae (2014); Hayashi and Morimae
(2015); Gheorghiu  _et al._ (2015); Hajdušek  _et al._ ; Fitzsimons and
Kashefi (2017); Aharonov  _et al._ ; Takeuchi  _et al._ (2019) or is able to
interact with two non–communicating provers have been derived Reichardt  _et
al._ . In a recent breakthrough Mahadev Mahadev  showed that even a purely
classical user can verify the output of a quantum processor. In contrast to
the verification protocols mentioned before, this protocol relies on a
computational assumption: the existence of trapdoor functions which are post-
quantum secure 333These functions are constructed in Mahadev ; Mahadev (2018)
based on the hardness of the Learning With Errors (LWE) problem Regev (2005).
These functions are hard to invert even for a quantum computer. However the
possession of additional information (trapdoor) enables one to compute the
preimages of the function efficiently. Using the notion of post-quantum secure
trapdoor functions in combination with powerful previously derived findings,
led to the surprising result that a classical user can indeed verify the
output of a quantum computer, as we will briefly explain below. The notion and
techniques developed in Mahadev ; Mahadev (2018) have recently been utilized
to put forward protocols with e.g. zero-knowledge polynomial-time verifiers
Vidick and Zhang (2020) and non-interactive classical verification Alagic  _et
al._ .

At a first glance it simply seems impossible to efficiently verify the output
of a much more powerful device (even if it was classical) if one is just given
that output and is prevented from testing the device. The key idea here is to
use interactive proofs. The exchange of messages allows $\sf A$ to test $\sf
B$ and to eventually get convinced that the $\sf B$’s claim is indeed correct
or to mistrust him and reject the answer. The Graph Non–isomorphism problem is
a simple example of a task where the output (of a powerful classical device)
can be verified with an interactive proof Vidick .

To explain the general idea of how to verify the output of a quantum device,
we assume that $\sf B$ possesses a quantum computer, whereas $\sf A$ only has
classical computational power. $\sf A$ asks $\sf B$ to solve a decision
problem (within BQP, i.e. a problem which can be solved efficiently by a
quantum computer) and wants to verify the answer. Of particular importance
here is that one can show that the outcome of such a decision problem can be
encoded in the ground state energy of a suitable, efficiently computable,
local Hamiltonian $H$ Kempe  _et al._ (2005). This implies that in case $\sf
B$ claims that the answer to the decision problem is "yes" 444The case in
which $\sf B$ claims that the answer to the decision problem is ”no” can be
treated similarly., he can convince $\sf A$ of this fact by preparing a state
with energy (w.r.t. $H$) below a certain value, which would be impossible in
case the correct answer was "no". An instance of such a state is the so–called
clock–state, $\ket{\eta}$ Feynman (1986); Kitaev  _et al._ (2002), which can
be prepared efficiently by a quantum computer. Hence, the output of the
quantum computer can be verified by determining the energy of the state
prepared by $\sf B$. This can be achieved by performing only measurements in
the $X$– as well as the $Z$–basis Biamonte and Love (2008); Morimae  _et al._
(2016); Fitzsimons  _et al._ (2018). It remains to ensure that $\sf A$ can
delegate these measurements to $\sf B$ without revealing the measurement
basis. The important contribution of Mahadev Mahadev  is the derivation of
such a measurement protocol (see Fig. 3). The properties of post–quantum
secure trapdoor functions are exploited precisely at this point to ensure that
$\sf B$ can not learn whether a qubit is measured in the $Z$\- or $X$-basis,
which prevents him from cheating.

For reasonable choices of the security parameters, the realization of such a
verification protocol is, even without considering faulty devices, not
feasible with current technology (on $\sf B$’s side). Already the number of
auxiliary qubits required in the measurement protocol would be too demanding
(Lindner and Peikert (2010) and Brakerski  _et al._ (2018)). Nevertheless, due
to the rapid technological development and the accompanying need for these
kind of verification protocols, we present here a proposal for a
proof–of–principle experiment. The minimal example explained here can already
be carried out with a total of seven qubits.

Figure 3: Sketch of steps 1–4 in the measurement protocol Mahadev  (see main
text). Alice ($\sf A$) represents a classical verifier, Bob ($\sf B$) an
efficient quantum prover, and we have used arrows to emphasise the flow of
classical information. $\sf A$ performs a delegated measurement on a single-
qubit state $\ket{\psi}=\alpha_{0}\ket{0}+\alpha_{1}\ket{1}$ in either the
$Z$\- or $X$-basis without revealing the measurement basis to $\sf B$. An
appropriate combination of the statistics of the results of such measurements
allows $\sf A$ to calculate the energy of the state prepared by $\sf B$ and
thereby verify the outcome of the original decision problem.

First, the original decision problem is mapped to a local Hamiltonian problem.
$\sf B$ prepares the corresponding state, $\ket{\eta}$ (consisting of 4 qubits
in this example), whose energy needs to be determined. Due to the linearity of
the measurement protocol, it is sufficient to demonstrate how $\sf A$ can
delegate the measurement in the $X$\- or $Z$-basis on a single-qubit state
$\ket{\psi}=\alpha_{0}\ket{0}+\alpha_{1}\ket{1}$ (belonging to $\ket{\eta}$)
without revealing the measurement basis to $\sf B$. The measurement protocol
has the following high-level structure (see Fig. 3):

  1. 1.

$\sf A$ computes a family of post–quantum secure trapdoor functions
$\\{y_{k}\\}$, labeled by an index $k$, together with the associated
information $t_{k}$ (trapdoor). The functions $y_{k}$ are of one of the two
types, either one-to-one or two-to-one 555Note that the two-to-one functions
are such that $y_{k}(0,\cdot)$ and $y_{k}(1,\cdot)$ are injective. If $\sf A$
wants to measure $\ket{\psi}$ in the $Z$-basis ($X$-basis), she chooses a
label $k$, such that $y_{k}$ is one-to-one (two-to-one), respectively. $\sf A$
keeps $t_{k}$ private (this is precisely the leverage $\sf A$ has over $\sf
B$) and sends $k$ to $\sf B$. Knowing $k$, $\sf B$ can efficiently evaluate
the function $y_{k}$ on any input. However, it is computationally hard for him
to determine which type $y_{k}$ is. Furthermore, $\sf A$ can compute the
preimages of $y_{k}$ efficiently using $t_{k}$ while $\sf B$ cannot.

  2. 2.

$\sf B$ is asked to prepare the state
$\ket{\phi_{k}}\propto\sum_{b,x}\alpha_{b}\ket{b}\ket{x}\ket{y_{k}(b,x)}$.
This can be done efficiently by a quantum computer.

  3. 3.

$\sf B$ is asked to measure the last register (qubits 3 and 4 in our example)
of $\ket{\phi_{k}}$ in the $Z$-basis and to send the measurement outcome $y$
to $\sf A$. The state of the first and second register (qubits 1 and 2 in our
example) is then, depending on the type of $y_{k}$ either: (i) The product
state $\ket{b}\ket{x}$ (with probability $|\alpha_{b}|^{2}$) where
$y_{k}(b,x)=y$; or (ii) The entangled state
$\alpha_{0}\ket{0}\ket{x_{0}}+\alpha_{1}\ket{1}\ket{x_{1}}$ where
$y_{k}(0,x_{0})=y_{k}(1,x_{1})=y$.

  4. 4.

$\sf A$ randomly chooses to run either a "test" or a "measurement" round. In a
"test" ("measurement") round, $\sf B$ is asked to measure the qubits in the
first and second register in the $Z$-basis ($X$-basis) respectively, and to
send the outcome to $\sf A$. The "test" rounds allow $\sf A$ to gain
confidence that $\sf B$ has indeed prepared $\ket{\phi_{k}}$ by checking that
$y_{k}(b,x)=y$. In a "measurement" round the first qubit has effectively been
measured in either the $Z$ or $X$ basis, depending on the type of $y_{k}$.
Using the trapdoor information $t_{k}$, $\sf A$ can classically post-process
the outputs to obtain the corresponding measurement outcome.

As mentioned above, a minimal, non-trivial example, which can be realized with
an ion-trap quantum computer Carrasco  _et al._ requires only $7$ qubits in
total and some tens of single and two–qubit gates 666This would correspond to
a decision problem encoded in the output of a quantum circuit composed of
three single- and two-qubit gates acting on two qubits initialized in the
state $\ket{0}^{\otimes 2}$.. In this case the clock-state $\ket{\eta}$ is a
$4$-qubits state and, for this minimal example, one can choose the second and
third register to have $1$ and $2$ qubits, respectively (as displayed in Fig.
3). Here, $y_{k}:\\{0,1\\}^{2}\to\\{0,1\\}^{2}$ and $k$ labels either one of
the $24$ one-to-one functions or one of the $24$ two-to-one functions.

Let us finally mention that protocols which allow the verification of the
output of imperfect quantum computers have been recently put forward in case
the verifier has limited access to quantum resources Gheorghiu  _et al._
(2019). Similar ideas can also be utilized in the purely classical
verification protocol Mahadev , ensuring that the measurements can still be
performed without jeopardizing its security Carrasco  _et al._ .

##  V Conclusion and Outlook

In an era, where we build noisy intermediate scale quantum devices, with the
effort to scale them towards larger system sizes and optimize their
performance, verification of quantum devices becomes a main motif in
theoretical and experimental quantum information science. In this perspective
on theoretical and experimental aspects of quantum verification we have taken
an approach of discussing three examples, formulated as proposed experiments.
The three examples are verification of quantum simulation via Hamiltonian
learning (Sec. II), cross-checking of quantum states prepared on different
quantum devices (Sec. III), and addressing the question of how a user of a
quantum processor can be certain about the correctness of its output (Sec.
IV). While our choice of examples highlighting quantum verification is
subjective and guided by personal interests, the common theme is that these
‘proposed experiments’ can be performed with the quantum devices existing in
today’s quantum laboratories or near-future devices. In addition, our examples
illustrate the diversity of questions in quantum verification and tools and
techniques to address them, with emphasis on what we identify as problems of
high relevance.

Of course, by the very nature of a perspective as forward looking, we identify
interesting topics and outline possible avenues, while putting the finger on
open issues for future theoretical and experimental work. These open problems
range from technical to conceptual issues, and we summarize some of these
questions within the various sections. The overarching challenge is, of
course, to develop efficient and quantitative verification protocols and
techniques, which eventually scale to large system sizes we envision as useful
quantum devices. In Sec. II on verification of analog quantum simulation via
Hamiltonian learning, the local Hamiltonian ansatz scales, by construction,
with the system size, and leads, in principle, to a quantified error
assessment. While one may raise issues of imperfect state preparation and
measurement errors in experiments, and the measurement budget available in a
specific experiment, we emphasize that these protocols also involve heavy
classical post-processing of data, which may provide limits from a practical
and conceptual perspective. While this might not pose serious limitations for
near-term devices, we might ask here, but also in a broader context, if some
of this post-processing can be replaced by more efficient quantum post-
processing on the device. The cross-device check of quantum states in Sec. III
provides another example of this type. There, the protocol underlying the
comparison of quantum states with a central data repository involves classical
communication. The protocol described is much more efficient than tomography,
and scales with a ‘friendly exponential’ in system size, allowing today
experimental implementation for tens of qubits. A future development of
quantum state transfer as quantum communication between the devices promises
to overcome these limitations. Finally, our discussion in Sec. IV on
verification of the output of an untrusted quantum device presents an absolute
minimal example which can be run on present quantum computers, leaving as
challenges the verification of outputs of imperfect quantum devices and more
advanced experimental demonstrations.

Verification of quantum processors become particularly challenging and
relevant in the regimes of quantum advantage, where quantum devices outperform
their classical counterparts Arute  _et al._ (2019); Zhong  _et al._ (2020).
As solving a "useful" computational task (such as factoring a large number)
would neither be feasible with noisy intermediate–scale quantum computers nor
necessary to demonstrate quantum superiority, one focuses on sampling problems
Aaronson and Arkhipov ; Boixo  _et al._ (2018); Bouland  _et al._ (2019), in
this context. However, these approaches entail difficulties in demonstrating
quantum superiority. On the one hand, the fact that the sampling was performed
faithfully needs to be verified. On the other hand, one needs to show that the
task is computationally hard for any classical device (taking into account
that the quantum computer is imperfect). In this context, both, strong
complexity–theoretical evidence of classical intractability as well as new
proposals for experimental realizations for various setups are desirable.

Acknowledgment –  Work at Innsbruck is supported by the European Union program
Horizon 2020 under Grants Agreement No. 817482 (PASQuanS) and No. 731473
(QuantERA via QTFLAG), the US Air Force Office of Scientific Research (AFOSR)
via IOE Grant No. FA9550-19-1-7044 LASCEM, by the Simons Collaboration on
Ultra-Quantum Matter, which is a grant from the Simons Foundation (651440,
PZ), by the Austrian Science Fund (FWF): stand alone project P32273-N27, by
the SFB BeyondC, and by the Institut für Quanteninformation.

## References

  * Deutsch (2020) I. H. Deutsch, PRX Quantum 1, 020101 (2020).
  * Preskill (2018) J. Preskill, Quantum 2, 79 (2018).
  * National Academies of Sciences and Medicine (2020) E. National Academies of Sciences and Medicine,  _Manipulating Quantum Systems: An Assessment of Atomic, Molecular, and Optical Physics in the United States_ (The National Academies Press, Washington, DC, 2020).
  * Eisert  _et al._ (2020) J. Eisert, D. Hangleiter, N. Walk, I. Roth, D. Markham, R. Parekh, U. Chabaud, and E. Kashefi, Nat. Rev. Phys. 2, 382 (2020).
  * Gheorghi  _et al._ (2019) A. Gheorghi, T. Kapourniotis, and E. Kashefi., Theory Comput. Syst. 63, 715 (2019).
  * Šupić and Bowles (2020) I. Šupić and J. Bowles, Quantum 4, 337 (2020).
  * Kliesch and Roth (2021) M. Kliesch and I. Roth, PRX Quantum 2, 010201 (2021).
  * Erhard  _et al._ (2019) A. Erhard, J. J. Wallman, L. Postler, M. Meth, R. Stricker, E. A. Martinez, P. Schindler, T. Monz, J. Emerson, and R. Blatt, Nat. Commun. 10, 5347 (2019).
  * Barz  _et al._ (2013) S. Barz, J. Fitzsimons, E. Kashefi, and P. Walther, Nat. Phys. 9, 727–731 (2013).
  * Cirac and Zoller (2012) J. I. Cirac and P. Zoller, Nat. Phys. 8, 264 (2012).
  * Bairey  _et al._ (2019) E. Bairey, I. Arad, and N. H. Lindner, Phys. Rev. Lett. 122, 020504 (2019).
  * Qi and Ranard (2019) X.-L. Qi and D. Ranard, Quantum 3, 159 (2019).
  * Li  _et al._ (2020) Z. Li, L. Zou, and T. H. Hsieh, Phys. Rev. Lett. 124, 160502 (2020).
  * (14) E. Altman, K. R. Brown, G. Carleo, L. D. Carr, E. Demler, C. Chin, B. DeMarco, S. E. Economou, M. A. Eriksson, K.-M. C. Fu, _et al._ , arXiv:1912.06938 .
  * Tarruell and Sanchez-Palencia (2018) L. Tarruell and L. Sanchez-Palencia, C. R. Phys. 19, 365 (2018).
  * Browaeys and Lahaye (2020) A. Browaeys and T. Lahaye, Nat. Phys. 16, 132–142 (2020).
  * (17) M. Morgado and S. Whitlock, arXiv:2011.03031 .
  * (18) S. Ebadi, T. T. Wang, H. Levine, A. Keesling, G. Semeghini, A. Omran, D. Bluvstein, R. Samajdar, H. Pichler, W. W. Ho, _et al._ , arXiv:2012.12281 .
  * Mazurenko  _et al._ (2017) A. Mazurenko, C. S. Chiu, G. Ji, M. F. Parsons, M. Kanász-Nagy, R. Schmidt, F. Grusdt, E. Demler, D. Greif, and M. Greiner, Nature 545, 462 (2017).
  * Argüello-Luengo  _et al._ (2019) J. Argüello-Luengo, A. González-Tudela, T. Shi, P. Zoller, and J. I. Cirac, Nature 574, 215 (2019).
  * Schäfer  _et al._ (2020) F. Schäfer, T. Fukuhara, S. Sugawa, Y. Takasu, and Y. Takahashi, Nat. Rev. Phys. 2, 411–425 (2020).
  * Kokail  _et al._ (2019) C. Kokail, C. Maier, R. van Bijnen, T. Brydges, M. K. Joshi, P. Jurcevic, C. A. Muschik, P. Silvi, R. Blatt, C. F. Roos, and P. Zoller, Nature 569, 355 (2019).
  * (23) C. Monroe, W. Campbell, L.-M. Duan, Z.-X. Gong, A. Gorshkov, P. Hess, R. Islam, K. Kim, N. Linke, G. Pagano, _et al._ , arXiv:1912.07845 .
  * Huang  _et al._ (2020a) H.-L. Huang, D. Wu, D. Fan, and X. Zhu, Sci. China Inf. Sci. 63, 1 (2020a).
  * Elben  _et al._ (2020) A. Elben, B. Vermersch, R. van Bijnen, C. Kokail, T. Brydges, C. Maier, M. K. Joshi, R. Blatt, C. F. Roos, and P. Zoller, Phys. Rev. Lett. 124, 010504 (2020).
  * Flammia (2020) S. Flammia, Physics 13, 3 (2020).
  * Morimae and Fujii (2013) T. Morimae and K. Fujii, Phys. Rev. A 87, 050301(R) (2013).
  * Morimae (2014) T. Morimae, Phys. Rev. A 89, 060302(R) (2014).
  * Hayashi and Morimae (2015) M. Hayashi and T. Morimae, Phys. Rev. Lett. 115, 220502 (2015).
  * Gheorghiu  _et al._ (2015) A. Gheorghiu, E. Kashefi, and P. Wallden, New J. Phys. 17, 083040 (2015).
  * (31) M. Hajdušek, C. A. Pérez-Delgado, and J. F. Fitzsimons, arXiv:1502.02563 .
  * Fitzsimons and Kashefi (2017) J. F. Fitzsimons and E. Kashefi, Phys. Rev. A 96, 012303 (2017).
  * (33) D. Aharonov, M. Ben-Or, E. Eban, and U. Mahadev, arXiv:1704.04487 .
  * Takeuchi  _et al._ (2019) Y. Takeuchi, T. Morimae, and H. Masahito, Sci. Rep.-UK 9, 13585 (2019).
  * (35) U. Mahadev, arXiv:1804.01082 .
  * Bañuls  _et al._ (2020) M. C. Bañuls, R. Blatt, J. Catani, A. Celi, J. I. Cirac, M. Dalmonte, L. Fallani, K. Jansen, M. Lewenstein, S. Montangero, _et al._ , Eur. Phys. J. D 74, 1 (2020).
  * McArdle  _et al._ (2020) S. McArdle, S. Endo, A. Aspuru-Guzik, S. C. Benjamin, and X. Yuan, Rev. of Mod. Phys. 92, 015003 (2020).
  * Hauke  _et al._ (2012) P. Hauke, F. M. Cucchietti, L. Tagliacozzo, I. Deutsch, and M. Lewenstein, Rep. Prog. Physics 75, 082401 (2012).
  * Schweigler  _et al._ (2017) T. Schweigler, V. Kasper, S. Erne, I. Mazets, B. Rauer, F. Cataldini, T. Langen, T. Gasenzer, J. Berges, and J. Schmiedmayer, Nature 545, 323 (2017).
  * (40) C. Kokail, L. Pastori, _et al._ , Unpublished.
  * Note (1) Since the ground state wave function of the Fermi Hubbard model as well as the Hamiltonian ${H}$ are real-valued, the constraints must be chosen as imaginary operators in order to obtain nonzero matrix elements $K_{nm}=\mathinner{\langle{-i[{A}_{n},{S}_{m}]}\rangle}$.
  * Schweizer  _et al._ (2016) C. Schweizer, M. Lohse, R. Citro, and I. Bloch, Phys. Rev. Lett. 117, 170405 (2016).
  * Keßler and Marquardt (2014) S. Keßler and F. Marquardt, Phys. Rev. A 89, 061601 (2014).
  * Bairey  _et al._ (2020) E. Bairey, C. Guo, D. Poletti, N. H. Lindner, and I. Arad, New J. Phys. 22, 032001 (2020).
  * Poggi  _et al._ (2020) P. M. Poggi, N. K. Lysne, K. W. Kuper, I. H. Deutsch, and P. S. Jessen, PRX Quantum 1, 020308 (2020).
  * Flammia and Liu (2011) S. T. Flammia and Y.-K. Liu, Phys. Rev. Lett. 106, 230501 (2011).
  * da Silva  _et al._ (2011) M. P. da Silva, O. Landon-Cardinal, and D. Poulin, Phys. Rev. Lett. 107, 210404 (2011).
  * Huang  _et al._ (2020b) H.-Y. Huang, R. Kueng, and J. Preskill, Nat. Phys. 16, 1050–1057 (2020b).
  * Jozsa (1994) R. Jozsa, J. Mod. Opt. 41, 2315 (1994).
  * Liang  _et al._ (2019) Y.-C. Liang, Y.-H. Yeh, P. E. M. F. Mendonça, R. Y. Teh, M. D. Reid, and P. D. Drummond, Rep. Prog. Phys. 82, 076001 (2019).
  * Brydges  _et al._ (2019) T. Brydges, A. Elben, P. Jurcevic, B. Vermersch, C. Maier, B. P. Lanyon, P. Zoller, R. Blatt, and C. F. Roos, Science 364, 260 (2019).
  * Ekert  _et al._ (2002) A. K. Ekert, C. M. Alves, D. K. L. Oi, M. Horodecki, P. Horodecki, and L. C. Kwek, Phys. Rev. Lett. 88, 217901 (2002).
  * Abanin and Demler (2012) D. A. Abanin and E. Demler, Phys. Rev. Lett. 109, 020504 (2012).
  * Daley  _et al._ (2012) A. J. Daley, H. Pichler, J. Schachenmayer, and P. Zoller, Phys. Rev. Lett. 109, 020505 (2012).
  * Islam  _et al._ (2015) R. Islam, R. Ma, P. M. Preiss, M. Eric Tai, A. Lukin, M. Rispoli, and M. Greiner, Nature 528, 77 (2015).
  * Kaufman  _et al._ (2016) A. M. Kaufman, M. E. Tai, A. Lukin, M. Rispoli, R. Schittko, P. M. Preiss, and M. Greiner, Science 353, 794 (2016).
  * Linke  _et al._ (2018) N. M. Linke, S. Johri, C. Figgatt, K. A. Landsman, A. Y. Matsuura, and C. Monroe, Phys. Rev. A 98, 052334 (2018).
  * Gross  _et al._ (2010) D. Gross, Y.-K. Liu, S. T. Flammia, S. Becker, and J. Eisert, Phys. Rev. Lett. 105, 150401 (2010).
  * Cramer  _et al._ (2010) M. Cramer, M. B. Plenio, S. T. Flammia, R. Somma, D. Gross, S. D. Bartlett, O. Landon-Cardinal, D. Poulin, and Y.-K. Liu, Nat. Commun. 1, 149 (2010).
  * Lanyon  _et al._ (2017) B. P. Lanyon, C. Maier, M. Holzäpfel, T. Baumgratz, C. Hempel, P. Jurcevic, I. Dhand, A. S. Buyskikh, A. J. Daley, _et al._ , Nat. Phys. 13, 1158 (2017).
  * Torlai  _et al._ (2018) G. Torlai, G. Mazzola, J. Carrasquilla, M. Troyer, R. Melko, and G. Carleo, Nat. Phys. 14, 447–450 (2018).
  * van Enk and Beenakker (2012) S. J. van Enk and C. W. J. Beenakker, Phys. Rev. Lett. 108, 110503 (2012).
  * Elben  _et al._ (2018) A. Elben, B. Vermersch, M. Dalmonte, J. Cirac, and P. Zoller, Phys. Rev. Lett. 120, 050406 (2018).
  * Elben  _et al._ (2019) A. Elben, B. Vermersch, C. F. Roos, and P. Zoller, Phys. Rev. A 99, 052323 (2019).
  * (65) A. Ketterer, S. Imai, N. Wyderka, and O. Gühne, arXiv:2012.12176 .
  * Knips (2020) L. Knips, Quantum Views 4, 47 (2020).
  * Ohliger  _et al._ (2013) M. Ohliger, V. Nesme, and J. Eisert, New J. Phys. 15, 015024 (2013).
  * Aaronson (2018) S. Aaronson, in  _Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing_ (2018) pp. 325–338.
  * Gottesman (1997) D. Gottesman,  _Stabilizer codes and quantum error correction_ , Ph.d. thesis, Caltech (1997).
  * Emerson  _et al._ (2005) J. Emerson, R. Alicki, and K. Życzkowski, J. Opt. B 7, 347 (2005).
  * Dankert  _et al._ (2009) C. Dankert, R. Cleve, J. Emerson, and E. Livine, Phys. Rev. A 80, 012304 (2009).
  * Knill  _et al._ (2008) E. Knill, D. Leibfried, R. Reichle, J. Britton, R. B. Blakestad, J. D. Jost, C. Langer, R. Ozeri, S. Seidelin, and D. J. Wineland, Phys. Rev. A 77, 012307 (2008).
  * Emerson  _et al._ (2007) J. Emerson, M. Silva, O. Moussa, C. Ryan, M. Laforest, J. Baugh, D. G. Cory, and R. Laflamme, Science 317, 1893 (2007).
  * Magesan  _et al._ (2012) E. Magesan, J. M. Gambetta, B. R. Johnson, C. A. Ryan, J. M. Chow, S. T. Merkel, M. P. da Silva, G. A. Keefe, M. B. Rothwell, T. A. Ohki, _et al._ , Phys. Rev. Lett. 109, 080505 (2012).
  * Gross  _et al._ (2007) D. Gross, K. Audenaert, and J. Eisert, J. Math. Phys. 48, 052104 (2007).
  * (76) S. Chen, W. Yu, P. Zeng, and S. T. Flammia, arXiv:2011.09636 .
  * (77) D. E. Koh and S. Grewal, arXiv:2011.11580 .
  * (78) D. Aharonov and U. Vazirani, arXiv:1206.3686 .
  * Note (2) For an excellent, recent review of these protocols see Gheorghi  _et al._ (2019).
  * (80) B. W. Reichardt, F. Unger, and U. Vazirani, arXiv:1209.0448 .
  * Note (3) These functions are constructed in Mahadev ; Mahadev (2018) based on the hardness of the Learning With Errors (LWE) problem Regev (2005).
  * Mahadev (2018) U. Mahadev, in  _2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)_ (2018) pp. 332–338, arXiv:1708.02130 .
  * Vidick and Zhang (2020) T. Vidick and T. Zhang, Quantum 4, 266 (2020).
  * (84) G. Alagic, A. M. Childs, A. B. Grilo, and S.-H. Hung, arXiv:1911.08101 .
  * (85) T. Vidick, Notices of the American Mathematical Society 66, 1619.
  * Kempe  _et al._ (2005) J. Kempe, A. Kitaev, and O. Regev, SIAM J. Comput. 35(5), 1070 (2005).
  * Note (4) The case in which $\sf B$ claims that the answer to the decision problem is "no" can be treated similarly.
  * Feynman (1986) R. P. Feynman, Found. Phys. 16, 507 (1986).
  * Kitaev  _et al._ (2002) A. Y. Kitaev, A. Shen, and M. N. Vyalyi,  _Quantum Computation_ , Vol. 47 (American Mathematical Society, Providence, 2002).
  * Biamonte and Love (2008) J. Biamonte and P. Love, Phys. Rev. A 78, 012352(7) (2008).
  * Morimae  _et al._ (2016) T. Morimae, D. Nagaj, and N. Schuch, Phys. Rev. A 93, 022326(6) (2016).
  * Fitzsimons  _et al._ (2018) J. F. Fitzsimons, M. Hajdušek, and T. Morimae, Phys. Rev. Lett. 120, 040501(5) (2018).
  * Lindner and Peikert (2010) R. Lindner and C. Peikert, “Better key sizes (and attacks) for lwe-based encryption,” Cryptology ePrint Archive, Report 2010/613 (2010), https://eprint.iacr.org/2010/613.
  * Brakerski  _et al._ (2018) Z. Brakerski, P. Christiano, U. Mahadev, U. Vazirani, and T. Vidick, in  _2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)_ (2018) pp. 320–331.
  * Note (5) Note that the two-to-one functions are such that $y_{k}(0,\cdot)$ and $y_{k}(1,\cdot)$ are injective.
  * (96) J. Carrasco _et al._ , Unpublished.
  * Note (6) This would correspond to a decision problem encoded in the output of a quantum circuit composed of three single- and two-qubit gates acting on two qubits initialized in the state $\mathinner{|{0}\rangle}^{\otimes 2}$.
  * Gheorghiu  _et al._ (2019) A. Gheorghiu, M. Hoban, and E. Kashefi, Quantum Sci. Technol. 4, 015009 (2019).
  * Arute  _et al._ (2019) F. Arute _et al._ , Nature 574, 505 (2019).
  * Zhong  _et al._ (2020) H.-S. Zhong _et al._ , Science 370, 1460 (2020).
  * (101) S. Aaronson and A. Arkhipov, arXiv:1011.3245 .
  * Boixo  _et al._ (2018) S. Boixo _et al._ , Nat. Phys. 14, 595 (2018).
  * Bouland  _et al._ (2019) A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani, Nat. Phys. 15, 159 (2019).
  * Regev (2005) O. Regev, in  _Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing_ , STOC ’05 (2005) pp. 84–93.