plainlemlemma#1 plainlemLemma#1 plainthmtheorem#1 plainthmTheorem#1
plaincorcorollary#1 plaincorCorollary#1 plaindefidefinition#1
plaindefiDefinition#1 plainalgalgorithm#1plainalgAlgorithm#1
plainappappendix#1plainappAppendix#1

# A game of quantum advantage: linking verification and simulation

Daniel Stilck França  QMATH, Department of Mathematical Sciences, University
of Copenhagen, Denmark Raul Garcia-Patron  School of Informatics, University
of Edinburgh, Edinburgh EH8 9AB, UK

###### Abstract

We present a formalism that captures the process of proving quantum
superiority to skeptics as an interactive game between two agents, supervised
by a referee. Bob, is sampling from a classical distribution on a quantum
device that is supposed to demonstrate a quantum advantage. The other player,
the skeptical Alice, is then allowed to propose mock distributions supposed to
reproduce Bob’s device’s statistics. He then needs to provide witness
functions to prove that Alice’s proposed mock distributions cannot properly
approximate his device. Within this framework, we establish three results.
First, for random quantum circuits, Bob being able to efficiently distinguish
his distribution from Alice’s implies efficient approximate simulation of the
distribution. Secondly, finding a polynomial time function to distinguish the
output of random circuits from the uniform distribution can also spoof the
heavy output generation problem in polynomial time. This pinpoints that
exponential resources may be unavoidable for even the most basic verification
tasks in the setting of random quantum circuits. Beyond this setting, by
employing strong data processing inequalities, our framework allows us to
analyse the effect of noise on classical simulability and verification of more
general near-term quantum advantage proposals.

##  1 Introduction

The transition from the reign of classical computers to quantum superiority is
expected not to be a singular event but rather a process of accumulation of
evidence. It will most probably happen through an iterative process of claims
of proofs and refutations until a consensus is reached among the scientific
community. The series of claims a few years back of the advantage of quantum
annealers followed by refutations and an intense debate inside the quantum
computation community [SSSV14, SS14, BRI+14, WRB+13] can be seen as an example
of that. Similarly, the recent claim of quantum advantage [AAB+19] was
followed by a growing interest in its potential simulation by a classical
device [HZN+20, PGN+19].

Ideally, one would like to demonstrate the advantage of quantum computers
solving a well-established hard computational problem, such as factoring large
numbers or simulating large-sized molecules. Such demonstration will most
likely need a fault-tolerant quantum computer, which will not be available in
the near-future. Thus, a lot of attention has been focused in the last years
to quantum advantage proposals based on sampling from the outcomes of random
quantum circuits, a task considered achievable. This effort culminated in the
recent landmark experiment of [AAB+19].

The classical hardness of computing the outcome probability of random circuits
has been reduced to standard complexity theoretic assumptions in various
settings [HM17, BFNV19, LBR17, Mov18, BJS11, AC17, BMS17, HHB+19]. For
instance, in [BFNV19] the authors prove that it is $\sharp P$ hard to compute
the exact probability of the outputs of random quantum circuits unless the
polynomial hierarchy collapses. This result can be extended to devices with
very low noise by assuming a couple of widely-accepted conjectures. Despite
this significant progress on putting the classical hardness of sampling from a
distribution close to the outputs of the random circuit on solid grounds,
equivalent hardness statements are not known to hold for the levels of noise
that affect current quantum computing architectures. Moreover, certifying
closeness to the ideal distribution in total variation distance requires an
exponential number of samples [HKEG19]. Thus, it is both not feasible to
verify closeness in total variation, and the actual distance is unlikely to be
in the regime where a quantum advantage has been proven.

These shortcomings have shifted the interest to benchmarks of advantage that
are thought to be more robust against noise and that are known to be
verifiable with a feasible number of samples. Prominent examples are the heavy
output generation problem (XHOG) [AC17, AG19] and the related linear cross-
entropy benchmarking (linear XEB) fidelity [NRK+18, BIS+18, AAB+19]. The
recent quantum advantage experiment used linear XEB as a benchmark for the
quantum state generated by the 53 qubit device. However, these approaches have
two main drawbacks. First, they require the computation of the probability of
sampled strings under the circuit’s ideal distribution, which consumes a
running time growing exponentially with the system’s size. Secondly, the
number of required samples grows exponentially with the size of the system for
a constant noise rate [AAB+19]. Thus, the linear XEB verification approach
requires us to be in the “sweet spot” where both the number of samples needed
given the noise level and the size of the circuit are not too large to render
the verification impossible. This approach is not scalable to larger system
sizes with current levels of noise. Besides, it is still unknown how to reduce
the hardness of the heavy output generation problem (XHOG) [AC17, AG19, Kre20]
to standard complexity-theoretic assumptions.

This difficulty of finding efficient certification protocols and benchmarks
for random circuit sampling extends to other proposals of near-term quantum
advantage, such as boson sampling [AA14b]. This has sparked interest in
simpler sanity checks, such as efficiently distinguishing the output
distribution from the uniform and other “easy” distributions [AA14a, CMS+14,
PWR+19, SVB+14]. As mentioned in [HKEG19], these verification forms are
manifestly weaker than certifying the total variation distance and do not
preclude the possibility of the device being classically simulable. However,
in the setting of random circuit sampling, not even an efficient verification
test that allows us to distinguish the outputs from the uniform distribution
is known.

Independent of the recent quantum advantage experiment, the development of
more efficient certification techniques of quantum advantage that can be
scaled with the increasing size of the quantum computer is an area of
relevance for near-term quantum computation [BKVV20]. In parallel, it is
important to develop a better understanding of how noise reduces the power of
quantum computers and how noise affects quantum advantage proposals or near
term applications of quantum devices.

To these ends, in this work, we envision this certification process as an
interactive game between two agents, Alice that uses classical computing
resources, and Bob that holds a (noisy) quantum computer and wants to convince
Alice of its computational advantage. They are both supervised by the referee
Robert. To win, Bob has to find functions that allow him to efficiently
distinguish the output of his device from every alternative distribution Alice
proposes. In turn, Alice needs to propose alternative distributions that
approximate the expectation values obtained by Bob’s quantum computer,
otherwise she loses the game.

Central to our result is the connection between the mirror descent algorithm
[TRW05, Bub15] and the proposed framework of the certification game. This
allows us to connect distinguishing probability distributions from a target
quantum distribution and learning an approximate classical description of the
latter. Our framework is inspired by a recent result of the authors [FGP20].
There, we show how to use mirror descent, strong data processing inequalities
and related concepts to analyse the performance of noisy quantum devices
performing optimization. In contrast, this article’s main result also hold for
noiseless circuits and our overarching goal is to formally link the hardness
of verification of quantum advantage proposals and their approximate classical
simulation.

##  2 Summary of results

We envision a quantum advantage demonstration as a game played between Bob,
who is sampling from a (noisy) quantum circuit and claiming that it
demonstrates a quantum advantage, and Alice, who is skeptical of Bob’s claim
and defends that her classical computer can mimic Bob’s behaviour efficiently.

As Bob is the person looking to convince the others that his quantum computer
has an advantage over Alice’s classical device, we place the burden of the
demonstration on him. In addition, Bob discloses publicly a description of the
hardware and the quantum algorithm his device is implementing. The game
consists of different rounds at which Alice can propose an alternative
hypothesis to the claim that Bob has achieved a quantum advantage. At the
beginning of the game, they both agree on a distinguishability parameter
$\epsilon>0$, which captures how close Alice needs to match Bob’s result, and
confidence probability $\delta$, which captures the probability of the outcome
of the game being correct. In what follows, we denote the probability
distribution Bob is sampling from by $\nu$.

###  2.1 The quantum advantage game

At the beginning of the first round, Alice discloses an alternative hypothesis
to quantum advantage in the form of a randomized classical algorithm sampling
from a given distribution $\mu_{0}(x)$, for example the uniform distribution.
It is then Bob’s role to refute Alice’s proposal. He does so by providing a
function $f_{1}:\\{0,1\\}^{n}\to[0,1]$ such that with probability at least
$1-\delta$,

$\displaystyle\mathbb{E}_{\mu_{0}}(f_{1})-\mathbb{E}_{\nu}(f_{1})\geq\epsilon.$
(1)

Alice is then allowed to update her hypothesis to $\mu_{1}(x)$ given the
information gained from the first round of the game, which Bob needs to
refute, providing a new witness $f_{2}$. Alice’s new distribution then needs
to pass both tests for the functions $f_{1}$ and $f_{2}$. The game continues
with Bob proposing new distinguishing functions $f_{t+1}$ and Alice mock
distributions $\mu_{t}$. The game ends if one of two players is declared
defeated following a set of previously established rules.

For example, Alice could concede defeat if she takes too much time to propose
a new candidate or sample from it. Similarly, Bob could be forced to
acknowledge his defeat if he takes too long to offer a new witness that
challenges Alice. In some sense, the rules should be consistent with the
process of building community consensus on the validity of a quantum advantage
result.

It is important to remark that the condition in Eq. (1) must be checked by a
referee Robert, to whom Alice and Bob provide samples at each round. That is,
they give Robert enough samples of their distributions to estimate the
expectation values by computing the empirical average for the functions
$f_{i}$ on the samples. The required number of samples can be estimated by
e.g. an application of Höffding’s inequality, as we show later. Note that this
guarantees that Alice cannot cheat by using Bob’s samples to find better
distributions. For instance, if Bob’s quantum computer is solving an NP
problem, then knowing the samples themselves would give Alice an efficient
classical strategy. In order to suppress statistical anomalies, we also make
the number of samples depend on the current round. More specifically, the
number of samples for round $t$ should be
$\mathcal{O}(t\epsilon^{-2}\log(t\delta^{-1}))$. This choice ensures that the
overall probability of an error occurring remains $\mathcal{O}(\delta)$.

In order for the verification game to work, we may further request that
sampling from Alice’s distributions, evaluating Bob’s test functions $f_{i}$
and the size of the messages sent to Robert to be tasks that need be achieved
efficiently with the resources at hand. In what follows, we define efficient
as a consumption of resources that scales polynomially with the size of the
problem, i.e., the number of qubits of the quantum computer. But a more at
hands definition, where we impose constraints on their size and time of
computation justified by the state of the art of classical computing hardware,
is also compatible with this framework and most probably be the definition
used in any real experimental demonstration.

This framework is very general, and it can be applied to any quantum algorithm
supposed to sample from a classical distribution, beyond random quantum
circuits. As an example, let us consider the optimization version of an NP-
complete problem, such as MAXCUT on a $\Delta$-regular graph with $\Delta\geq
3$:

######  Example 2.1 (MAXCUT).

suppose that Bob claims his quantum computer can achieve a better value for an
NP optimization problem, say MAXCUT, than Alice’s classical computer. Recall
that for a graph $G=(V,E)$ with $n$ vertices and maximum degree $\Delta$,
MAXCUT of the graph can be cast as finding the maximum over $\\{0,1\\}^{n}$ of
the function

$\displaystyle f_{G}(x)=\frac{1}{n\Delta}\sum\limits_{(i,j)\in
E}(1-\delta(x_{i},x_{j})).$ (2)

Here, the normalization $n\Delta$ ensures that $0\leq f(x)\leq 1$. Thus, in
this case, Bob can propose the function $f_{G}$ to distinguish his
distribution from Alice’s classical computer. If the value for MAXCUT he can
achieve is indeed at least $\epsilon$ better than what Alice can achieve, he
wins the game. On the other hand, if classical methods can yield a better cut
than Bob’s quantum computer, then $f_{G}$ will not suffice and Bob will have
to find another function to justify his claim of quantum advantage. Note that
our choice of normalization in Eq. (2) implies that an additive error
$\epsilon$ on approximating the expectation value of $f_{G}$ implies a
multiplicative error of order $\epsilon$ for the cut’s value.

As exemplified above, for NP optimization problems, there is a clear choice
for which function Bob should propose and it can be computed in polynomial
time.

At first sight, the possibility of the game always requiring an exponential
number of rounds seems a plausible outcome. However, there is an update rule
for Alice’s distribution that will lead to the game having at most
$\mathcal{O}(n\epsilon^{-2})$ rounds, where $n$ is the number of qubits of
Bob’s device, as we explain below. Note that we do not claim that this update
rule will always lead to Alice winning, only that it will converge after a
finite number of rounds. However, we will argue that this update rule is an
appropriate choice against random circuits and when competing with noisy
quantum devices.

This update rule uses the connection between our certification game and mirror
descent [Bub15], a method to learn probability distributions by approximating
them by a sequence of Gibbs distributions. In a nutshell, Alice can exploit
each test function $f_{t}$ that Bob provides to improve her guess of the
distribution $\nu$. The updates are of the form $\mu_{t+1}\propto
e^{\log(\mu_{t})-\tfrac{\epsilon}{4}f_{t}}$. She can use her method of choice
to sample from the Gibbs distribution, such as rejection sampling. One can
then show that at every round of the game, the guess of Alice gets closer to
the ideal distribution by at least a finite amount, converging to $\mu_{t}$
being $\epsilon$-close to the ideal quantum distribution $\nu$ in a finite
number of rounds. In fact, regardless of the distribution Bob is sampling
from, if Alice chooses to use mirror descent to update her distribution, then
it follows from standard properties of mirror descent that the game will end
after at most $16n\epsilon^{-2}$ rounds. We explain this in more detail in
Section 4. The caveat is that knowledge from which Gibbs distribution Alice
needs to sample from does not guarantee that she can do it efficiently.

Let us exemplify this again with MAXCUT:

######  Example 2.2 (MAXCUT continued-mirror descent and simulated annealing).

In the same setting as in Example 2.1, one can show that if Alice uses mirror
descent to update her probability distributions, her sequence of probability
distributions $\mu_{t}$ is given by:

$\displaystyle\mu_{t}(x)=\frac{e^{\frac{t}{4\epsilon}f_{G}(x)}}{\mathcal{Z}_{t}},\quad\mathcal{Z}_{t}=\sum_{x\in\\{0,1\\}^{n}}e^{\frac{t}{4\epsilon}f_{G}(x)}.$

That is, her strategy will be akin to performing simulated annealing to try to
obtain a better value of MAXCUT. This is one of the most widely used methods
for combinatorial optimization [KGV83]. If one picks $t$ large enough,
$\mu_{t}$ is guaranteed to be sharply concentrated around the maximum of
$f_{G}$, but the complexity of sampling from $\mu_{t}$ increases accordingly
and at some point Alice won’t be able to sample from it anymore. We refer to
e.g. [GLS12, Chapter 28] and references therein for a discussion of the
application of simulated annealing to combinatorial optimization. We can
interpret the parameter $t/\epsilon$ as the inverse temperature $\beta$. Thus,
if Alice picks the mirror descent strategy, she would win if a classical Monte
Carlo algorithm has a performance comparable to that of Bob’s quantum
computer.

###  2.2 Main results

As we anticipated, this framework of quantum advantage certification allows us
to prove three main results. Our first result is that for random circuits, we
are only required to play a number of rounds that is independent of the number
of qubits $n$ and Bob never wins if Alice plays mirror descent and
$\epsilon=\Omega(\log(n)^{-1})$.

######  Theorem 2.1 (Alice approximately learns $\nu$ after $\epsilon^{-2}$
rounds for random circuits).

Let $\nu$ be the probability distribution of the outcome of a random quantum
circuit on $n$ qubits stemming from a $2^{-2n-1}$-approximate two design and
$\epsilon=\Omega(\log(n)^{-1})$ be given. Suppose that Bob succeeds in
providing functions $f_{1},\ldots,f_{t}$ that can be computed in polynomial
time and distinguish $\nu$ from a sequence $\mu_{1},\ldots,\mu_{t}$ of
distributions that Alice discloses, with $t=\mathcal{O}(\epsilon^{-2})$. Then
there is an algorithm that allows Alice to learn a distribution $\mu_{t+1}$
exploiting the revealed information on $f_{t}$ that can be sampled from in
polynomial time. Moreover, $\mu_{t}$ is $\epsilon$ close in total variation
distance to $\nu$.

The above result is connected to the entropy of the outcome distributions of
random circuits, as it reads $S(\nu)=n-\mathcal{O}(1)$ with high probability.
Thus, up to a small constant, its value matches that of $n$ random coins. This
implies that mirror descent converges fast. While in the case of MAXCUT we
needed, in general, $n$ iterations to lower the temperature and reach the
ground state, because of the entropy bound for random circuits, the outputs of
a random circuit are well-approximated by a high-temperature Gibbs state.
Thus, one way of rephrasing Theorem 2.1 is that if Bob can efficiently find
distinguishing functions and they can be computed efficiently, then Alice can
also find and sample from a high-temperature Gibbs state that is close to the
ideal distribution.

An important corollary of this is that either the hardness conjectures of
random quantum circuits are not valid for distances
$\epsilon=\Omega(\log(n)^{-1})$ or a complete certification strategy for Bob,
providing a discrimination function for every guess of Alice, is impossible
with polynomial resources.

Our second result concerns a connection between the hardness of fooling the
XHOG problem and distinguishing the output of a random circuit from the
uniform. We refer to Sec. 5 for a precise definition of the XHOG problem.
There we also show that if the conjectures related to the hardness of fooling
the XHOG problem are true, not even distinguishing from the uniform
distribution in polynomial time should be possible. In this case, Bob will
have to resort to verification strategies that take super-polynomial time to
demonstrate a quantum advantage. More precisely, in Section 5 we prove the
following result.

######  Theorem 2.2 (Distingushing from uniform and HOG).

Let $f:\\{0,1\\}^{n}\to\\{0,1\\}$ be a function that for some $\epsilon>0$
satisfies: $\mathbb{E}_{\nu}(f)-\mathbb{E}_{\mathcal{U}}(f)\geq\epsilon,$
where $\nu$ is the outcome distribution of a random quantum circuit stemming
from a $2^{-2n-1}$-approximate two design in $n$ qubits. Then there is an
algorithm that samples from a distribution that fools XHOG up to $\epsilon$
using $\mathcal{O}(\epsilon^{-4})$ evaluations of $f$ in expectation.

One possible criticism of the above framework is that it might be in general
hard to distinguish the outcome of a circuit stemming from a design from the
uniform distribution. However, we show in Appendix C that in case Bob is
sampling from a stabilizer circuit, then Alice can easily fool XHOG.

All the results above concern the outcome distribution of the _ideal_ circuit.
In Sec. 6 we extend our results to the approximate simulability of the outcome
distribution of noisy devices. We show that, under doubly-stochastic noise,
the number of rounds of the verification game when Alice uses mirror descent
decreases exponentially with the depth of the circuit Bob is implementing. As
we believe these results are interesting beyond quantum advantage proposals
and apply to the broader topic of classical simulability of noisy circuits, we
state them in more general terms. Below we state a specialized version of our
main result regarding the complexity of approximating the statistics of
outcomes of noisy circuits, Theorem 6.1:

######  Theorem 2.3.

Let $\nu$ be the outcome distribution of a noisy quantum circuit on $n$ qubits
of depth $D$ affected by local depolarizing noise with rate $p$ after each
gate, measured in the computational basis. Given functions
$f_{1},\ldots,f_{k}:\\{0,1\\}^{n}\to[0,1]$, mirror descent will converge to a
distribution $\mu_{t}$ satisfying:

$\displaystyle\left|\mathbb{E}_{\nu}(f_{i})-\mathbb{E}_{\mu_{t}}(f_{i})\right|\leq\epsilon$

for all $1\leq i\leq k$ in at most $T=\mathcal{O}(\epsilon^{-2}(1-p)^{2D+2}n)$
iterations. Moreover, we can sample from $\mu_{t}$ by evaluating
$f_{1},\ldots,f_{k}$ at most

$\displaystyle\operatorname{exp}\left(\frac{4(1-p)^{2D+2}n}{\epsilon}\right)$

times.

As discussed in the recent [FGP20], which we discuss in more detail shortly,
this restrains the power of noisy quantum computers to demonstrate a
significant advantage versus classical methods for more structured problems.
Let us exemplify this with the noisy MAXCUT example:

######  Example 2.3 (MAXCUT continued- noisy circuits).

Let us exemplify the consequences of Theorem 2.3 to approximating MAXCUT on a
noisy quantum device. Suppose that Bob’s device suffers from local
depolarizing noise with rate $p$ and consists of a circuit of depth $D$. In
this scenario, Alice will be able to obtain an expected value of MAXCUT that
is $\epsilon$ close to Bob’s by sampling from the distribution $\mu_{t}$ given
by:

$\displaystyle\mu_{t}(x)=\frac{e^{\beta
f_{G}(x)}}{\mathcal{Z}},\quad\mathcal{Z}=\sum_{x\in\\{0,1\\}^{n}}e^{\beta
f_{G}(x)}$

with $\beta=\epsilon^{-1}(1-p)^{2D+2}n$. That is, the noise decreases the
inverse temperature $\beta$ we have to go when performing classical simulated
annealing to obtain comparable results.

As is discussed in more detail in [FGP20], results like the one above can be
used to rigorously establish maximal depths before noisy quantum devices are
not outperformed by polynomial time classical algorithms. But the main message
of the example above in our context of verification is that if there are clear
candidate functions to distinguish the output of the noisy quantum circuit,
then the noise will make it easier for Alice to simulate the output of the
device, as one would expect. We refer to Section 6 for a derivation of this
bound and a more detailed discussion of its consequences.

##  3 Preliminaries

We will now introduce some basic definitions and notation together with the
concepts of mirror descent and rejection sampling, which are relevant to our
work.

###  3.1 Notation

#### Probability distributions on binary strings:

we define $F=\left(\\{0,1\\}^{n}\right)^{[0,1]}$ to be the set of functions
$f:\\{0,1\\}^{n}\to[0,1]$.

Given two probability distributions $\mu,\nu$ on $\\{0,1\\}^{n}$, we define
their total variation distance $\|\nu-\mu\|_{TV}$ as:

$\displaystyle\|\nu-\mu\|_{TV}=\frac{1}{2}\sum\limits_{x\in\\{0,1\\}^{n}}\left|\mu(x)-\nu(x)\right|.$

The total variation is widely accepted as one of the most natural and
operationally relevant measures of distinguishability for two probability
distributions. One of the reasons for that is its dual formulation. One can
show that:

$\displaystyle\|\nu-\mu\|_{TV}=2\sup\limits_{f\in F,\|f\|_{\infty}\leq
1}(\mathbb{E}_{\mu}(f)-\mathbb{E}_{\nu}(f)),$ (3)

where

$\displaystyle\|f\|_{\infty}=\sup\limits_{x\in\\{0,1\\}^{n}}f(x).$

Moreover, defining $S=\\{x\in\\{0,1\\}^{n}:\mu(x)\geq\nu(x)\\}$ and letting
$\chi_{S}$ be the indicator function of $S$, it is easy to see that:

$\displaystyle\|\nu-\mu\|_{TV}=2(\mathbb{E}_{\mu}(\chi_{S})-\mathbb{E}_{\nu}(\chi_{S})).$

That is, we can restrict to indicator functions in Eq. (3). This indicator
function provides the optimal guessing strategy between distributions
$\mu,\nu$ connecting it with the total variation distance [CT12].

The characterization given in Eq. (3) can also be used to certify that the
total variation between two probability distributions is at least $\epsilon$.
To see why, given some function $f$ with $\|f\|_{\infty}\leq 1$ and samples
$X_{1},\ldots,X_{s}$ from $\mu$ and $Y_{1},\ldots,Y_{s}$ from $\nu$, it
follows from Hoeffding’s inequality that:

$\displaystyle\left|s^{-1}\sum\limits_{i=1}^{s}f(X_{i})-\mathbb{E}_{\mu}(f)\right|\leq\frac{\epsilon}{2},\quad\left|s^{-1}\sum\limits_{i=1}^{s}f(Y_{i})-\mathbb{E}_{\nu}(f)\right|\leq\frac{\epsilon}{2}$
(4)

with probability at least $1-\delta$ as long as

$\displaystyle s=\mathcal{O}(\epsilon^{-2}\log(\delta^{-1})).$ (5)

Thus, if

$\displaystyle\left|s^{-1}\sum\limits_{i=1}^{s}\left(f(Y_{i})-f(X_{i})\right)\right|\geq
2\epsilon,$

then a simple application of the triangle inequality yields together with Eq.
(4) that

$\displaystyle\left|\mathbb{E}_{\mu}(f)-\mathbb{E}_{\nu}(f))\right|\geq\epsilon,$

with probability at least $1-\delta$. This, in turn, implies that
$\|\mu-\nu\|_{TV}\geq\epsilon$ with probability at least $1-\delta$. Thus, we
conclude from Eq. (5) and the discussion above that as long as
$\epsilon^{-1}\log(\delta^{-1})=\mathcal{O}(\text{poly}(n))$, polynomially
many samples and evaluations of the function $f$ are sufficient to certify
that two distributions are at least at a certain distance $\epsilon$ in total
variation. Of course, this in no sense discards the possibility that finding
the distinguishing function $f$ itself or evaluating it may not be possible in
polynomial time. This allows us to estimate the number of samples we need to
provide at each round of the game to ensure that the probability of a
deviation greater than $\epsilon$ from the target is upper bounded by
$1-\mathcal{O}(\delta)$ for some $\delta$. As at each round $t$ we have to
estimate $t$ expectation values up to $\epsilon$, obtaining
$\mathcal{O}(\epsilon^{-2}\log(t\delta^{-t}))$ samples for each round ensures
that the probability one of them deviates by more than $\epsilon$ is at most
$\delta^{t}$. By a union bound, the probability that there was a deviation
after $T$ rounds is at most

$\displaystyle\sum\limits_{t=1}^{T}\delta^{t}\leq\frac{\delta}{1-\delta}=\mathcal{O}(\delta)$

for $\delta\leq\frac{1}{3}$. Thus, letting the number of samples per round
grow like $t\log(t\delta^{-1})$ is enough to ensure that the probability of an
error occurring at some point remains of order $\delta$.

#### Distinguishability measures for quantum states and unitary designs:

we are also going to need other distinguishability measures for distributions
and quantum states. We will introduce them only for quantum states and note
that the corresponding classical definition is obtained by considering the
classical probability distribution as a diagonal quantum state. For two
quantum states $\rho,\sigma\in\mathcal{M}_{2^{n}}$ we define their relative
entropy to be:

$\displaystyle
S(\rho||\sigma)=\text{tr}\left(\rho\left(\log\rho-\log\sigma\right)\right)$

if $\text{kern }\rho\subset\text{kern }\sigma$ and $+\infty$ otherwise.
Moreover, we define the $\alpha-$Rényi entropies $S_{\alpha}$ for $\alpha>1$
to be given by:

$\displaystyle
S_{\alpha}(\rho)=-\frac{\alpha}{\alpha-1}\log\left(\text{tr}\left(\rho^{\alpha}\right)\right).$

and the von Neumann entropy to be
$S_{1}(\rho)=S(\rho)=-\text{tr}\left(\rho\log(\rho)\right)$. Note that we
have:

$\displaystyle n\geq S(\rho)\geq S_{\alpha}(\rho).$

Let us also set our notation and terminology for random quantum circuits.
Given a distribution $\tau$ on the unitary group on $n$ qubits, $U(2^{n})$,
and $t\in\mathbbm{N}$, we define
$\mathcal{G}^{(t)}_{\tau}:\mathcal{M}_{2^{n}}\to\mathcal{M}_{2^{n}}$ to be the
quantum channel:

$\displaystyle\mathcal{G}^{(t)}_{\tau}(X)=\int\limits_{U(2^{n})}U^{\otimes
t}X\left(U^{\dagger}\right)^{\otimes t}d\tau.$

$\mathcal{G}^{(t)}_{\tau}$ is then said to be an $(\epsilon)$-approximate
$t$-design [AE07] if

$\displaystyle\|\mathcal{G}^{(t)}_{\tau}-\mathcal{G}^{(t)}_{\mu_{G}}\|_{\diamond}\leq\epsilon,$

where $\|\cdot\|_{\diamond}$ is the diamond norm and $\mu_{G}$ is the Haar
measure on the unitary group. Moreover, given $C$ distributed according to
$\tau$, we will always denote by $\nu$ the probability measure we obtain by
measuring $C\ket{0}$ in the computational basis, i.e.

$\displaystyle\nu(x)=\text{tr}\left(|x\rangle\langle x|C|0\rangle\langle
0|^{\otimes n}C^{\dagger}\right)$

for $x\in\\{0,1\\}^{n}$.

###  3.2 Mirror descent

Mirror descent [TRW05, Bub15] is an optimization and learning algorithm to
approximate probability distributions efficiently and in a structured way
through a series of Gibbs probability measures. It allows us to formally
connect the problem of distinguishing probability distributions and learning
them. That is, given some target distribution $\nu$ on $\\{0,1\\}^{n}$ we wish
to learn, say the output distribution of a given random quantum circuit,
mirror descent is an iterative procedure that proposes a sequence of
$\mu_{0},\ldots,\mu_{T}$ of guesses for $\nu$. Furthermore, the initial
distribution $\mu_{0}$ is the uniform distribution $\mathcal{U}$. The
algorithm requires us to find functions
$f_{1},\ldots,f_{T}:\\{0,1\\}^{n}\to[0,1]$ that allow us to distinguish
$\mu_{t}$ from $\nu$, i.e.

$\displaystyle\mathbb{E}_{\mu_{t}}(f_{t})-\mathbb{E}_{\nu}(f_{t})\geq\epsilon$
(6)

for some given distinguishability parameter $\epsilon>0$. One can now
appreciate the direct connection between mirror descent and our verification
game. Of course, it is a priori not clear how to find such functions in a
traditional mirror descent application. In the certification game, this
problem is overcome by having the responsibility to provide $f$ on Bob’s side.
Also note that if no function $f_{t}$ exists that satisfies (6), then
$\|\nu-\mu_{t}\|_{TV}\leq\epsilon$ by the dual formulation of the total
variation distance in eq. (3).

Algorithm 1 Mirror descent for learning probability distributions.

1:function Mirror descent($T,\epsilon$)

2: Set $\mu_{0}=\mathcal{U}$ $\triangleright$ initialize to the uniform
distribution

3: for $t=1,\ldots,T=\lceil
16S\left(\nu\|\mathcal{U}\right)\epsilon^{-2}\rceil$ do

4: Demand function $f_{t}$ such that
$\mathbb{E}_{\mu_{t}}(f_{t})-\mathbb{E}_{\nu}(f_{t})\geq\epsilon$

5: if Given $f_{t}$ then

6: Set
$\mu_{t+1}(x)=\operatorname{exp}(-\frac{\epsilon}{4}\sum\limits_{i=0}^{t}f_{i}(x))/\mathcal{Z}_{t+1}$.
$\triangleright$ Update the guess.

7: end if

8: if no such function exists then

9: Return $\mu_{t}$

10: break loop

11: end if

12: end for

13: Return $\mu_{T}$ and exit function $\triangleright$ Current guess is
$\epsilon$ indistinguishable from $\nu$

14:end function

As outlined in 1, mirror descent works by updating the probability measure as:

$\displaystyle\mu_{t+1}=\operatorname{exp}\left(-\frac{\epsilon}{4}\sum\limits_{i=0}^{t}f_{i}\right)/\mathcal{Z}_{t+1},$
(7)

where

$\displaystyle\mathcal{Z}_{t+1}=\sum\limits_{x\in\\{0,1\\}^{n}}\operatorname{exp}\left(-\frac{\epsilon}{4}\sum\limits_{i=0}^{t}f_{i}(x)\right)$

is the partition function. As we update the distributions, the candidate
distributions $\mu_{t}$ become closer and closer to the target distribution,
as made precise by the following lemma:

######  Lemma 3.1.

The distributions $\mu_{t}$ of the algorithm 1 satisfy:

$\displaystyle
S\left(\nu\|\mu_{t}\right)\leq-t\frac{\epsilon^{2}}{16}+S\left(\nu\|\mathcal{U}\right),$
(8)

where $\mathcal{U}$ is the uniform distribution.

Eq. (8) is a standard property of mirror descent [Bub15].

Exploiting the direct connection between the verification protocol and mirror
descent, we can directly use lemma 3.1 to bound the number of rounds of the
game of in terms of $S\left(\nu\|\mathcal{U}\right)$. We then immediately
obtain:

######  Theorem 3.1.

The output of algorithm 1 satisfies:

$\displaystyle\|\mu_{t}-\nu\|_{TV}\leq\epsilon$ (9)

after at most $T\leq 16\epsilon^{-2}S\left(\nu\|\mathcal{U}\right)$
iterations.

###### Proof.

Using Pinsker’s inequality and Eq. (8) it is easy to prove the relation

$\displaystyle\|\mu_{t}-\nu\|_{TV}\leq\sqrt{2S\left(\nu\|\mu_{t}\right)}\leq\sqrt{2\left(S\left(\nu\|\mathcal{U}\right)-t\frac{\epsilon^{2}}{16}\right)},$
(10)

This together with the positivity of the total variation distance provides the
claim. ∎

Note that Eq. (10) ensures that we make constant progress in total variation
at each iteration. Theorem 3.1 implies that if Bob provides a sequence of
functions $f_{1},\ldots,f_{T+1}$ that allow distinguishing $\nu$ from the
sequence $\mu_{0},\ldots,\mu_{T}$ of at most
$\mathcal{O}(\epsilon^{-2}S\left(\nu\|\mathcal{U}\right))$ distributions up to
an error $\epsilon$, then we can also find a distribution that is $\epsilon$
close to it in total variation distance. Furthermore, as we will show later,
it is possible to use this connection to the relative entropy to quantify the
effect of noise on the complexity of learning the distribution.

###  3.3 Rejection sampling

Let us now show how to generate samples from $\mu_{t}$ and the underlying
complexity. We will use the standard technique of rejection sampling described
in Algorithm 2. We refer to [Appendix B.5][LP17] for a brief review of its
properties. In rejection sampling we sample indirectly from a target
distribution $\mu_{t}$ by first generating a sample $x$ with an easy to sample
distribution $\gamma(x)$ and accepting the sample with probability
$\mu_{t}(x)/(M\gamma(x))$, where $M$ is a constant such that the ratio is
bounded by $1$. It is a standard fact that rejection sampling will output a
sample after $M$ runs in expectation, as the probability of rejection follows
a geometric distribution with parameter $M^{-1}$.

Algorithm 2 Rejection sampling.

1:ability to generate samples from distribution $\gamma$ on $\\{0,1\\}^{n}$,
distribution $\mu_{t}$ on $\\{0,1\\}^{n}$, constant $M$ such that
$\frac{\mu_{t}(x)}{M\gamma(x)}\leq 1$, ability to compute
$\frac{\mu_{t}(x)}{M\gamma(x)}$ and samples from $\mathcal{U}([0,1])$.

2:function Rejection sampling(M)

3: Sample $u$ distributed according to $\mathcal{U}([0,1])$ and $x$
distributed acoording to $\gamma$.

4: if $u\leq\frac{\mu_{t}(x)}{M\gamma(x)}$ then

5: Output $x$

6: end if

7:end function

In the case of Gibbs distributions
$\mu_{t}=\operatorname{exp}(-H_{t})/\mathcal{Z}_{t}$, where

$\displaystyle H_{t}(x)=\frac{\epsilon}{4}\sum\limits_{i=1}^{t}f_{i}(x),$

a common choice for $\gamma$ is the uniform distribution and
$M_{t}=\frac{2^{n}}{\mathcal{Z}_{t}}$, where $\mathcal{Z}_{t}$ is once again
the partition function. Note that for this choice of $M_{t}$, we have that:

$\displaystyle\frac{\mu_{t}(x)}{M_{t}\mathcal{U}(x)}=e^{-H_{t}(x)}\leq 1,$

as $H_{t}(x)\geq 0$ for all $x\in\\{0,1\\}^{n}$ by our choice of $f_{t}$. In
particular, note that with this choice, we never have to compute the partition
function $\mathcal{Z}_{t}$ to run rejection sampling, only $H_{t}(x)$. Thus,
we conclude that the complexity of running one round of rejection sampling is
the same as computing $H_{t}(x)$. Let us now estimate how many rounds are
required in expectation before we accept a sample:

######  Lemma 3.2 (Sampling from $\mu_{t}$).

Let $\mu_{t}$ be the guess at iteration $t$ of Algorithm 1. Running rejection
sampling with the uniform distribution as $\gamma$ and
$M_{t}=\frac{2^{n}}{\mathcal{Z}_{t}}$ returns a sample from $\mu_{t}$ after at
most $e^{\frac{\epsilon}{4}t}$ trials and evaluations of $H_{t}$, in
expectation.

###### Proof.

Note that by our previous discussion the expected number of trials is
$M_{t}=\frac{2^{n}}{\mathcal{Z}_{t}}$. By construction, $f_{t}$ are functions
with image $[0,1]$. Thus, it follows from a triangle inequality that:

$\displaystyle\|H_{t}\|_{\infty}\leq\frac{\epsilon}{4}\sum\limits_{i=1}^{t}\|f_{i}\|_{\infty}\leq\frac{t\epsilon}{4}.$

This implies that

$\displaystyle\mathcal{Z}_{t}=\sum\limits_{x\in\\{0,1\\}^{n}}\operatorname{exp}(-H_{t}(x))\geq
2^{n}e^{-\frac{\epsilon}{4}t}.$

We conclude from the last inequality that

$\displaystyle M_{t}=\frac{2^{n}}{\mathcal{Z}_{t}}\leq
e^{\frac{\epsilon}{4}t}$

which yields the claim. ∎

We see that as long as $\epsilon t=\mathcal{O}(\log(n))$, then we can sample
from $\mu_{t}$ in a polynomial expected number of trials and evaluations of
$H_{t}$.

In practice, rejection sampling is not necessarily the most efficient way of
simulating probability distributions and other techniques to sample from a
Gibbs distribution such as Glauber dynamics or simulated annealing [LP17]
perform better. However, rejection sampling allows for a simple analytical
analysis, which is more challenging for more refined techniques.

##  4 Random quantum circuits

Let us now discuss the implications to the verification of quantum advantage
proposals based on sampling the output distribution of random circuits. The
key technical assumption behind various state of the art classical hardness
proofs for quantum advantage proposals is the property that the underlying
ensemble is an approximate two design [HBVSE18]. Thus, we will also depart
from this assumption. We then have:

######  Lemma 4.1.

Let $\nu$ be the probability distribution of the outcome of a random quantum
circuit on $n$ qubits stemming from a $2^{-2n-1}$-approximate two design.
Then, with probability at least $1-\delta$, we have:

$\displaystyle S(\nu)\geq n+\log(\delta)-\log(3).$

###### Proof.

We refer to Prop. A.1 in Appendix A for a proof. ∎

Similar statements were shown in [HKEG19, AA14a]. From this, we have:

######  Theorem 4.1 (Disitinguishing output distributions and classical
simulability).

Let $\nu$ be the probability distribution of the outcome of a random quantum
circuit on $n$ qubits stemming from a $2^{-2n-1}$-approximate two design and
$\epsilon=\Omega(\log(n)^{-1})$ be given. Suppose that we can distinguish
$\nu$ from a sequence $\mu_{1},\ldots,\mu_{t}$ of distributions that can be
sampled from in polynomial time. Moreover, we can distinguish them by
functions $f_{1},\ldots,f_{T}$ that can be evaluated in polynomial time. That
is:

$\displaystyle\forall 1\leq t\leq
T:\mathbb{E}_{\mu_{t}}(f_{t})-\mathbb{E}_{\nu}(f_{t})\geq\epsilon.$ (11)

with $f_{t}$ computable in polynomial time. Then, with probability at least
$1-\delta$, we can find a distribution $\mu_{t}$ satisfying:

$\displaystyle\|\nu-\mu_{t}\|_{TV}=\sqrt{2\left(\log(3)-\log(\delta)-t\frac{\epsilon^{2}}{16}\right)}$
(12)

and sample from it in time
$\mathcal{O}(e^{\frac{c}{\epsilon}}\operatorname{poly}(n))=\mathcal{O}(\operatorname{poly}(n))$.

###### Proof.

As we show in Prop. A.1, we have that with probability at least $1-\delta$

$\displaystyle S(\nu)\geq n-\log(2+\epsilon)+\log(\delta).$

Conditioned on the event above, it follows from Cor. 3.1 that mirror descent
outputs a distribution satisfying Eq. (12) after at most

$\displaystyle 16\epsilon^{-2}\left(\log(3)-\log(\delta)\right)$

iterations, or equivalently after that many game rounds. Now, at each
iteration $t$ of mirror descent, we need a function satisfying Eq. (11).
Moreover, we have that
$\mu_{t}\propto\operatorname{exp}\left(-\epsilon/4\sum\limits_{i}f_{i}\right)$.
Thus, if all the $f_{i}$ can be computed in polynomial time, then it follows
from Lemma 3.2 that we can also sample from $\mu_{t}$ using rejection sampling
in polynomial time. This is because Lemma 3.2 implies that we need at most a
polynomial number

$\displaystyle\operatorname{exp}\left(\frac{4(\log(3)-\log(\delta))}{\epsilon}\right)$

of rejection sampling rounds, in expectation. As each round of rejection
sampling requires us to evaluate the functions $f_{i}$ once and we suppose
that they can be evaluated in polynomial time, this gives the claim. ∎

Therefore, if Bob provides for every proposed distribution $\mu_{t}$ of Alice
a polytime computable function $f_{t}$ that distinguishes it from $\nu$, after
at most a constant number of rounds Alice will be sampling efficiently from an
approximate distribution. It is interesting to point out that the
certification game and the sampling of Alice remains efficient, even if we
relax the condition of Lemma 4.1 to $S(\nu)\geq n-\mathcal{O}(\log(n))$ and
request $\epsilon$ to decrease with the size $n$ of the quantum device with
scaling $\epsilon=\mathcal{O}(\log(n)^{-1})$.

A direct consequence of our result is that if the hardness conjecture of
random quantum circuits is true, then Bob must fail to provide a certification
function that is efficiently computable at some stage of the certification
game. A natural question would then be to ask at which stage Bob will fail to
provide such a function. In the following section, we will prove that if the
XHOG conjecture [AG19] is correct, Bob must fail at the first round of the
game, i.e., even distinguishing the output distributions from the uniform
distribution cannot be done in polynomial time.

We note that these results have important differences from the results in
[AA14a, Appendix 11]. There the authors show the existence of a high min-
entropy distribution that can be sampled from classically and is
indistinguishable from the random quantum circuit by classical circuits of
polynomial size. This is because in our case we have the guarantee of a good
approximation in total variation distance, i.e. the distributions are
indistinguishable under any function after a couple of iterations. Moreover,
we have an efficient way of finding the distribution and sampling from it if
the distinguishing functions can be computed efficiently, while, to the best
of our knowledge, the aforementioned result should be taken as an existence
result. Finally, our framework allows us to work with the Shannon entropy
instead of the min-entropy. The min-entropy is notoriously more difficult to
bound and always smaller than the Shannon entropy.

##  5 Distinguishing from the uniform distribution

To the best of our knowledge, the state of the art approach for the
verification of quantum advantage proposals based on random circuit sampling
is the linear cross-entropy heavy output generation problem (XHOG) [AG19],
which is closely related to the linear cross-entropy benchmarking (linear XEB)
fidelity $\mathcal{F}_{\operatorname{XEB}}$ [NRK+18, BIS+18, AAB+19]. The XHOG
refers to the problem of, given some circuit $C$, generating distinct samples
$z_{1},\ldots,z_{k}$ such that:

$\displaystyle\mathbb{E}_{i}\left[\left|\left\langle
z_{i}|C|0^{n}\right\rangle\right|^{2}\right]\geq b/2^{n}$ (13)

for some $b>1$ with probability at least $\frac{1}{2}+\frac{1}{2b}$ and $k$
satisfying:

$\displaystyle k\geq\frac{1}{((2s-1)b-1)(b-1)}.$ (14)

Note that, given the samples $z_{1},\ldots,z_{k}$, verifying that they indeed
satisfy eq. (13) requires us to compute the probability of the outcomes under
the ideal circuit. In turn, the linear cross-entropy fidelity for a
distribution $\mu$, $\mathcal{F}_{\operatorname{XEB}}(\mu)$, as defined in
[NRK+18, BIS+18, AAB+19], is given by:

$\displaystyle\mathcal{F}_{\operatorname{XEB}}(\mu)=2^{n}\mathbb{E}_{\nu}\left(\mu\right)-1.$

Here we see the probability distribution $\mu$ as a function
$\mu:\\{0,1\\}^{n}\to\mathbbm{R}$ and, as usual, $\nu$ is the output
probability distribution of the ideal random circuit. A simple manipulation
then shows that samples $z_{i}$ from $\mu$ satisfy

$\displaystyle\mathbb{E}_{i}\left[\left|\left\langle
z_{i}|C|0^{n}\right\rangle\right|^{2}\right]\geq\frac{1+\mathcal{F}_{\operatorname{XEB}}(\mu)}{2^{n}}.$

In [AG19], the authors relate the complexity of computing outcome
probabilities of random quantum circuits to the XHOG problem. More precisely,
the authors start by assuming that there is no polynomial-time classical
algorithm that takes as input a (random) quantum circuit $C$ and produces an
estimate $p$ of $p_{0}=\mathbb{P}[C\operatorname{outputs}0]$ such that

$\displaystyle\mathbb{E}\left[\left(p_{0}-2^{-n}\right)^{2}\right]=\mathbb{E}\left[\left(p_{0}-p\right)^{2}\right]+\Omega\left(2^{-3n}\right).$

where the expectations are taken over circuits $C$ as well as the algorithm’s
internal randomness. They then show that this conjecture implies that there is
no polynomial time algorithm that solves the XHOG problem. As the verification
of XHOG requires us to estimate the outcome probabilities, this path to
proving and verifying the hardness of the sampling task also implies that XHOG
is not verifiable in polynomial time.

But the hardness of XHOG imposes barriers to even more basic verification
tasks. As we will see now, the hardness of XHOG would imply that it is
impossible to efficiently distinguish the output from the circuit from the
uniform distributions. In turn, efficient distinguishability implies a
polynomial time algorithm to spoof XHOG. Therefore, Bob will have to resort to
verification strategies that take superpolynomial time to demonstrate a
quantum advantage in our game. The proof of the statement will once again rely
on the fact that the output distribution is essentially flat. We will start by
showing that any distribution with large $2-$Rényi entropy cannot have small
sets of large mass in the following sense:

######  Lemma 5.1.

Let $\nu$ be a probability distribution on $\\{0,1\\}^{n}$ such that
$S_{2}(\nu)\geq n-\log(c)$ for some constant $c>0$. Then, for any $\epsilon>0$
and subset $L\subset\\{0,1\\}^{n}$ we have that

$\displaystyle\nu(L)=\sum\limits_{x\in L}\nu(x)\geq\epsilon$

implies that

$\displaystyle|L|\geq\epsilon^{2}c^{-1}2^{n}.$

###### Proof.

Note that the condition $S_{2}(\nu)\geq n-\log(c)$ is equivalent to

$\displaystyle\sum\limits_{x\in\\{0,1\\}^{n}}\nu(x)^{2}\leq c2^{-n}.$ (15)

Moroever, we have

$\displaystyle\sum\limits_{x\in\\{0,1\\}^{n}}\nu(x)^{2}\geq\sum\limits_{x\in
L}\nu(x)^{2}\geq\frac{\epsilon^{2}}{|L|}.$ (16)

To see the last inequality, note that, by the concavity of the function
$x\mapsto x^{2}$,

$\displaystyle\frac{1}{|L|}\sum\limits_{x\in
L}\nu(x)^{2}\geq\left(\frac{1}{|L|}\sum\limits_{x\in
L}\nu(x)\right)^{2}\geq\frac{\epsilon^{2}}{|L|^{2}}.$

Combining (16) with (15) we conclude that:

$\displaystyle\frac{\epsilon^{2}}{|L|}\leq c2^{-n},$

which yields the claim after rearranging the terms. ∎

It then immediately follows that:

######  Lemma 5.2.

Let $f:\\{0,1\\}^{n}\to\\{0,1\\}$ be a function that for some $\epsilon>0$
satisfies:

$\displaystyle\mathbb{E}_{\nu}(f)-\mathbb{E}_{\mathcal{U}}(f)\geq\epsilon,$
(17)

where $\nu$ is the outcome distribution of a random quantum circuit stemming
from a $2^{-2n-1}$-approximate two design on $n$ qubits. Let

$\displaystyle L=\\{x\in\\{0,1\\}^{n}:f(x)=1\\}.$

Then, with probability at least $1-\delta$,

$\displaystyle|L|=\Omega\left(\epsilon^{2}\delta 2^{n}\right).$ (18)

and

$\displaystyle\frac{1}{|L|}\nu(L)\geq\frac{1}{2^{n}}+\frac{\epsilon}{|L|}\geq\frac{1+\epsilon}{2^{n}}.$
(19)

###### Proof.

First note that Eq. (17) is equivalent to

$\displaystyle\nu(L)\geq\frac{|L|}{2^{n}}+\epsilon$

and, in particular, $\nu(L)\geq\epsilon$. Moreover, Eq. (19) readily follows
by dividing the equation above by $|L|$. As we show in Prop. A.1 in Eq. (24)
that with probability at least $1-\delta$

$\displaystyle S_{2}(\nu)\geq n-\log(3)+\log(\delta).$ (20)

Conditioned on Eq. (20), it follows from Lemma 5.1 that

$\displaystyle|L|\geq c\epsilon^{2}\delta 2^{n}$ (21)

for some constant $c>0$, which yields Eq. (18). ∎

We restricted the result above to functions with binary outputs to simplify
the arguments, but we show in Appendix B that this can be done without loss of
generality. That is, given a function $f$ that distinguished the distributions
for $\epsilon$ and range $[0,1]$, there always exists some $f^{\prime}$ that
is binary and has the same properties and distinguished the distribution up to
$\tfrac{\epsilon^{2}}{4}$.

If the function $f$ in Lemma 5.2 can be computed in polynomial time, then we
can use it to fool XHOG in polynomial time:

######  Theorem 5.1 (From distinguishing to fooling XHOG).

Let $f$ as in Lemma 5.2. Moreover, let $\mathcal{U}(L)$ be the uniform
distribution on $L$. Then we can sample from $\mathcal{U}(L)$ by evaluating
$f$ $\mathcal{O}(\epsilon^{-4})$ many times, in expectation. Moreover, samples
from $\mathcal{U}(L)$ violate HOG up to $\epsilon$.

###### Proof.

Let us start with the statement that samples from $\mathcal{U}(L)$ violate
XHOG up to at least $\epsilon$. To see this, note that:

$\displaystyle\mathbb{E}_{\nu}\left(\mathcal{U}(L)\right)=\sum\limits_{x\in
L}\frac{\nu(x)}{|L|}\geq\frac{1+\epsilon}{2^{n}}$

by Eq. (19). To sample from $\mathcal{U}(L)$, we can once again resort to a
variation of rejection sampling. We sample a point $x_{1}\in\\{0,1\\}^{n}$
from the uniform distribution and compute $f(x_{1})$. If $f(x_{1})=1$, we
output $x_{1}$. If not, we rerun this procedure with a new sample $x_{2}$. It
is easy to see that when we accept, $x_{i}$ is uniformly distributed on $L$.
Moreover, the probability of accepting is $\frac{L}{2^{n}}$. By Eq. (21), it
then follows that the probability of accepting is at least
$\Omega(\epsilon^{2})$, from which we obtain that the expected number of
rounds is $\mathcal{O}(\epsilon^{-4})$. As for each round we have to evaluate
$f$ once, the claim follows. ∎

It follows that if we can efficiently distinguish the output from the uniform
distribution, then we can fool XHOG. In particular, it would follow from the
conjectures of [AG19] that it is not possible to distinguish the output of
random circuits from the uniform distribution for $\epsilon$ at least inverse
polynomial in $n$ in polynomial time if XHOG cannot be solved in polynomial
time.

Note that the results of this section only required the property that the
underlying random circuit ensemble is a two design. However, it is well-known
that random Clifford unitaries also are two designs and can still be simulated
efficiently classically. It is then natural to ask if finding a function
distinguishing the output of a random Clifford from the uniform distribution
can be found in polynomial time. As we show in Appendix C, for random
Cliffords, the function can be found and be computed in polynomial time.

##  6 Noisy devices

Most of the current implementations of quantum circuits have high levels of
noise. In principle, highly-correlated noise can make simulating the quantum
device classically even more complex [KBG+11]. However, in other contexts, as
demonstrated for boson sampling [QBQGP20], noise can render the simulation
significantly less complex. Here, we show that in the scenario of doubly
stochastic Markovian noise, i.e., quantum channels that map the maximally
mixed state to itself, the noise diminishes the complexity of approximating
the underlying distribution being sampled from. To see what we mean, let us go
back the game described in Section 2. There we considered Bob to have a
quantum advantage and win the game if he could find functions
$f_{1},\ldots,f_{t}$ whose expectation values under his distribution Alice
cannot reproduce classically. However, suppose now that Bob’s device is
affected by noise, say a global depolarizing channel with parameter $0\leq
p\leq 1$. One would then expect that as $p\to 1$, it should be easier for
Alice to reproduce the statistics of Bob’s device and win the game. As we show
below, if Alice once again uses mirror descent to find her candidate
distributions, then the algorithm will converge faster to a distribution that
reproduces the statistics of Bob’s distribution as the level of noise
increases. For example, for MAXCUT, this will also make it easier for her to
sample from the distribution mirror descent proposes, as a smaller number of
iterations implies not having to go down to lower temperatures.

###  6.1 Strong data processing inequalities and mirror descent

Let us first recall the following definition:

######  Definition 6.1 (Strong data processing inequality).

A doubly stochastic quantum channel $T:\mathcal{M}_{d}\to\mathcal{M}_{d}$
(i.e. a CPTP map satisfying $T(I)=T^{*}(I)=I$) is said to satisfy a strong
data processing inequality with contraction $\alpha>0$ w.r.t. $\frac{I}{d}$ if
for all states $\rho$ we have:

$\displaystyle
S\left(T(\rho)\|\frac{I}{d}\right)\leq(1-\alpha)S\left(\rho\|\frac{I}{d}\right).$

Strong data processing inequalities for doubly stochastic can be derived using
the framework of hypercontractivity and logarithmic Sobolev inequalities
[KT13, MHFW16b, MHFW16a, HRF20, BDR20] and are known explicitly in some cases.
See also [BSW19] for another approach. As shown by other works [ABOIN96,
BOGH13, MHRW15, FGP20], strong data processing can be used to quantify how
useful a noisy quantum device is and for how long it can sustain interesting
computations.

Let us illustrate the strong data processing inequality with an example. Let
$\Phi_{p}:\mathcal{M}_{2}\to\mathcal{M}_{2}$ be the depolarizing channel on
one qubit with depolarizing parameter $p$, i.e.

$\displaystyle\Phi_{p}(\rho)=(1-p)\rho+p\frac{I}{2}.$

The authors of [MHFW16b] show that:

$\displaystyle S\left(\Phi_{p}^{\otimes
n}(\rho)\|\frac{I}{2^{n}}\right)\leq\left(1-2p+p^{2}\right)S\left(\rho\|\frac{I}{2^{n}}\right)$

and similar results are available for other relevant noise models. In
particular, optimal inequalities have been derived in [KT13, MHFW16a] for
tensor products of single qubit, doubly stochastic channels.

Suppose now that the noisy circuit of interest consists of $n$ qubits
initialized to $\ket{0}^{\otimes n}$, $D$ layers of unitaries
$U_{1},U_{2},\ldots,U_{D}$ and a measurement in the computational basis.
However, due to imperfections in the implementation, the state initialization,
the measurements and the unitaries are noisy. We will model this by assuming
that every layer of unitaries is proceeded by a layer of doubly stochastic
quantum channel $\Phi$ that satisfies a strong data processing inequality
$\alpha$. Moreover, we will assume that the measurement is also affected by an
extra noisy channel $\Phi$. We only make these assumptions to simplify the
notation and argument, but it is easy to adapt the argument to different
channels at different times and different noise rates. Under the assumptions
above, the probability distribution $\nu$ describing the outcomes of the noisy
device is given by:

$\displaystyle\nu(i)=\text{tr}\left(|i\rangle\langle i|T(|0\rangle\langle
0|^{\otimes n})\right)=\text{tr}\left(|i\rangle\langle
i|(M\circ\Phi\circ\mathcal{U}_{D}\circ\Phi\circ\ldots\circ\mathcal{U}_{1}\circ\Phi(|0\rangle\langle
0|^{\otimes n})\right),$ (22)

where $\mathcal{U}_{i}$ is the channel given by conjugations with $U_{i}$ and
$M$ is the q.c. channel

$\displaystyle
M(\rho)=\sum\limits_{i=0}^{2^{n}-1}\text{tr}\left(\rho|i\rangle\langle
i|\right)|i\rangle\langle i|$

and

$\displaystyle T(|0\rangle\langle 0|^{\otimes
n})=(M\circ\Phi\circ\mathcal{U}_{D}\circ\Phi\circ\ldots\circ\mathcal{U}_{1}\circ\Phi(|0\rangle\langle
0|^{\otimes n}).$

We then have:

######  Theorem 6.1.

Let $\nu$ be the distribution defined in Eq. (22) and assume $\Phi$ satisfies
a strong data processing inequality with parameter $\alpha$. Given functions
$f_{1},\ldots,f_{k}:\\{0,1\\}^{n}\to[0,1]$, mirror descent will converge to a
distribution $\mu_{t}$ satisfying:

$\displaystyle\left|\mathbb{E}_{\nu}(f_{i})-\mathbb{E}_{\mu_{t}}(f_{i})\right|\leq\epsilon$

for all $1\leq i\leq k$ in at most
$T=\mathcal{O}(\epsilon^{-2}(1-\alpha)^{D+1}n)$ iterations. Moreover, we can
sample from $\mu_{t}$ by evaluating $f_{1},\ldots,f_{k}$ at most

$\displaystyle\operatorname{exp}\left(\frac{4(1-\alpha)^{D+1}n}{\epsilon}\right)$

times.

###### Proof.

Mirror descent will converge to a distribution with the desired properties
after $16\epsilon^{-2}S\left(\nu\|\mathcal{U}\right)$ iterations. Moreover, by
Lemma 3.2, the complexity of sampling from $\mu$ is bounded by

$\displaystyle\operatorname{exp}\left(\frac{4S\left(\nu\|\mathcal{U}\right)}{\epsilon}\right)$

evaluations of the functions $f_{i}$. Thus, the statement follows if we can
bound the relative entropy of the outcome. Note that:

$\displaystyle S\left(\nu\|\mathcal{U}\right)=S\left(T(|0\rangle\langle
0|^{\otimes n})\|\frac{I}{2^{n}}\right),$

as the maximally mixed state gives rise to the uniform distribution when
measured in the computational basis. By the data processing inequality:

$\displaystyle S\left(T(|0\rangle\langle 0|^{\otimes
n})\|\frac{I}{2^{n}}\right)\leq
S\left(\Phi\circ\mathcal{U}_{D}\circ\Phi\circ\ldots\circ\mathcal{U}_{1}\circ\Phi(|0\rangle\langle
0|^{\otimes n})\|\frac{I}{2^{n}}\right)$

and by our assumption on $\Phi$:

$\displaystyle
S\left(\Phi\circ\mathcal{U}_{D}\circ\Phi\circ\ldots\circ\mathcal{U}_{1}\circ\Phi(|0\rangle\langle
0|^{\otimes
n})\|\frac{I}{2^{n}}\right)\leq(1-\alpha)S\left(\mathcal{U}_{D}\circ\Phi\circ\ldots\circ\mathcal{U}_{1}\circ\Phi(|0\rangle\langle
0|^{\otimes n})\|\frac{I}{2^{n}}\right).$

The relative entropy is unitarily invariant, thus:

$\displaystyle(1-\alpha)S\left(\mathcal{U}_{D}\circ\Phi\circ\ldots\circ\mathcal{U}_{1}\circ\Phi(|0\rangle\langle
0|^{\otimes
n})\|\frac{I}{2^{n}}\right)=(1-\alpha)S\left(\Phi\circ\ldots\circ\mathcal{U}_{1}\circ\Phi(|0\rangle\langle
0|^{\otimes n})\|\frac{I}{2^{n}}\right).$

Applying the chain of arguments above another $D$ times we conclude that:

$\displaystyle S\left(T(|0\rangle\langle 0|^{\otimes
n})\|\frac{I}{2^{n}}\right)\leq(1-\alpha)^{D+1}S\left(|0\rangle\langle
0|^{\otimes n}\|\frac{I}{2^{n}}\right)=(1-\alpha)^{D+1}n,$

which yields the claim. ∎

Thus, we see that the complexity of approximate sampling from the output of
noisy circuits decreases exponentially with the noise level and depth. For
instance, for circuits with local depolarizing noise with parameter $p$ and
depth $D$, the theorem above gives a complexity of:

$\displaystyle\operatorname{exp}\left(\frac{4(1-p)^{2D+2}n}{\epsilon}\right).$
(23)

evaluations of the distinguishing functions. Thus, we see that our framework
has the desirable feature that it becomes easier for Alice to mock Bob’s
device as the noise increases. Unfortunately, the scaling with $n$ in the
bound above is undesirable for high-entropy distributions. Thus, we plan to
derive more specialized bounds in upcoming work.

##  7 Acknowledgments

DSF was supported by VILLUM FONDEN via the QMATH Centre of Excellence under
Grant No. 10059. RGP was supported by the Quantum Computing and Simulation
Hub, an EPSRC-funded project, part of the UK National Quantum Technologies
Programme. We thank Anthony Leverrier and Juani Bermejo-Vega for helpful
comments and discussions.

## References

  * [AA14a] Scott Aaronson and Alex Arkhipov.  Boson sampling is far from uniform.  Quantum Info. Comput., 14(15–16):1383–1423, November 2014.
  * [AA14b] Scott Aaronson and Alex Arkhipov.  The computational complexity of linear optics.  In Research in Optical Sciences. OSA, 2014.
  * [AAB+19] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G S L Brandao, David A Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graff, Keith Guerin, Steve Habegger, Matthew P Harrigan, Michael J Hartmann, Alan Ho, Markus Hoffmann, Trent Huang, Travis S Humble, Sergei V Isakov, Evan Jeffrey, Zhang Jiang, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Paul V Klimov, Sergey Knysh, Alexander Korotkov, Fedor Kostritsa, David Landhuis, Mike Lindmark, Erik Lucero, Dmitry Lyakh, Salvatore Mandrà, Jarrod R McClean, Matthew McEwen, Anthony Megrant, Xiao Mi, Kristel Michielsen, Masoud Mohseni, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Murphy Yuezhen Niu, Eric Ostby, Andre Petukhov, John C Platt, Chris Quintana, Eleanor G Rieffel, Pedram Roushan, Nicholas C Rubin, Daniel Sank, Kevin J Satzinger, Vadim Smelyanskiy, Kevin J Sung, Matthew D Trevithick, Amit Vainsencher, Benjamin Villalonga, Theodore White, Z Jamie Yao, Ping Yeh, Adam Zalcman, Hartmut Neven, and John M Martinis.  Quantum supremacy using a programmable superconducting processor.  Nature, 574(7779):505–510, 2019.
  * [ABOIN96] Dorit Aharonov, Michael Ben-Or, Russell Impagliazzo, and Noam Nisan.  Limitations of noisy reversible computation.  arXiv preprint quant-ph/9611028, 1996.
  * [AC17] Scott Aaronson and Lijie Chen.  Complexity-theoretic foundations of quantum supremacy experiments.  In Proceedings of the 32nd Computational Complexity Conference, 2017\.
  * [AE07] Andris Ambainis and Joseph Emerson.  Quantum t-designs: t-wise independence in the quantum world.  In Twenty-Second Annual IEEE Conference on Computational Complexity 07). IEEE, jun 2007.
  * [AG04] Scott Aaronson and Daniel Gottesman.  Improved simulation of stabilizer circuits.  Physical Review A, 70(5), Nov 2004.
  * [AG19] Scott Aaronson and Sam Gunn.  On the classical hardness of spoofing linear cross-entropy benchmarking, 2019.  arXiv:1910.12085.
  * [BDR20] Salman Beigi, Nilanjana Datta, and Cambyse Rouzé.  Quantum reverse hypercontractivity: Its tensorization and application to strong converses.  Communications in Mathematical Physics, 376(2):753–794, may 2020\.
  * [BFNV19] Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani.  On the complexity and verification of quantum random circuit sampling.  Nature Physics, 15(2):159, 2019.
  * [BIS+18] 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, 14(6):595–600, apr 2018.
  * [BJS11] Michael J Bremner, Richard Jozsa, and Dan J Shepherd.  Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy.  In Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, volume 467, pages 459–472. The Royal Society, 2011.
  * [BKVV20] Zvika Brakerski, Venkata Koppula, Umesh Vazirani, and Thomas Vidick.  Simpler Proofs of Quantumness, 2020.  arXiv:2005.04826v1.
  * [BMS17] Michael J. Bremner, Ashley Montanaro, and Dan J. Shepherd.  Achieving quantum supremacy with sparse and noisy commuting quantum computations.  Quantum, 1:8, apr 2017.
  * [BOGH13] Michael Ben-Or, Daniel Gottesman, and Avinatan Hassidim.  Quantum refrigerator.  arXiv preprint arXiv:1301.1995, 2013.
  * [BRI+14] Sergio Boixo, Troels F. Rønnow, Sergei V. Isakov, Zhihui Wang, David Wecker, Daniel A. Lidar, John M. Martinis, and Matthias Troyer.  Evidence for quantum annealing with more than one hundred qubits.  Nature Physics, 10(3):218–224, feb 2014.
  * [BSW19] Mario Berta, David Sutter, and Michael Walter.  Quantum Brascamp-Lieb Dualities, 2019.  arXiv:1909.02383v2.
  * [Bub15] Sébastien Bubeck.  Convex Optimization: Algorithms and Complexity.  Foundations and Trends® in Machine Learning, 8(3-4):231–357, 2015.
  * [CMS+14] Jacques Carolan, Jasmin D. A. Meinecke, Peter J. Shadbolt, Nicholas J. Russell, Nur Ismail, Kerstin Wörhoff, Terry Rudolph, Mark G. Thompson, Jeremy L. Brien, Jonathan C. F. Matthews, and Anthony Laing.  On the experimental verification of quantum complexity in linear optics.  Nature Photonics, 8(8):621–626, jul 2014.
  * [CT12] Thomas M Cover and Joy A Thomas.  Elements of information theory.  John Wiley & Sons, 2012.
  * [DCEL09] Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine.  Exact and approximate unitary 2-designs and their application to fidelity estimation.  Physical Review A, 80(1), jul 2009.
  * [DLT02] D.P. DiVincenzo, D.W. Leung, and B.M. Terhal.  Quantum data hiding.  IEEE Transactions on Information Theory, 48(3):580–598, Mar 2002\.
  * [FGP20] Daniel Stilck Franca and Raul Garcia-Patron.  Limitations of optimization algorithms on noisy quantum devices, 2020\.  arXiv:2009.05532v1.
  * [GLS12] Martin Grötschel, László Lovász, and Alexander Schrijver.  Geometric algorithms and combinatorial optimization, volume 2.  Springer Science & Business Media, 2012.
  * [Got98] Daniel Gottesman.  The heisenberg representation of quantum computers, 1998.  arXiv:quant-ph/9807006.
  * [HBVSE18] Dominik Hangleiter, Juani Bermejo-Vega, Martin Schwarz, and Jens Eisert.  Anticoncentration theorems for schemes showing a quantum speedup.  Quantum, 2:65, may 2018.
  * [HHB+19] Jonas Haferkamp, Dominik Hangleiter, Adam Bouland, Bill Fefferman, Jens Eisert, and Juani Bermejo-Vega.  Closing gaps of a quantum advantage with short-time hamiltonian dynamics, 2019.  arXiv 1908.08069.
  * [HKEG19] Dominik Hangleiter, Martin Kliesch, Jens Eisert, and Christian Gogolin.  Sample complexity of device-independently certified “quantum supremacy”.  Phys. Rev. Lett., 122:210502, May 2019.
  * [HM17] Aram W Harrow and Ashley Montanaro.  Quantum computational supremacy.  Nature, 549(7671):203, 2017.
  * [HRF20] Christoph Hirche, Cambyse Rouzé, and Daniel Stilck França.  On contraction coefficients, partial orders and approximation of capacities for quantum channels, 2020.  arXiv:2011.05949v1.
  * [HZN+20] Cupjin Huang, Fang Zhang, Michael Newman, Junjie Cai, Xun Gao, Zhengxiong Tian, Junyin Wu, Haihong Xu, Huanjun Yu, Bo Yuan, Mario Szegedy, Yaoyun Shi, and Jianxin Chen.  Classical simulation of quantum supremacy circuits, 2020.  arXiv:2005.06787.
  * [KBG+11] M. Kliesch, T. Barthel, C. Gogolin, M. Kastoryano, and J. Eisert.  Dissipative quantum church-turing theorem.  Physical Review Letters, 107(12), sep 2011.
  * [KGV83] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi.  Optimization by simulated annealing.  Science, 220(4598):671–680, may 1983.
  * [Kre20] William Kretschmer.  The Quantum Supremacy Tsirelson Inequality, 2020.  arXiv:2008.08721v1.
  * [KT13] Michael J. Kastoryano and Kristan Temme.  Quantum logarithmic sobolev inequalities and rapid mixing.  Journal of Mathematical Physics, 54(5):052202, may 2013.
  * [LBR17] AP Lund, Michael J Bremner, and TC Ralph.  Quantum sampling problems, Boson sampling and quantum supremacy.  npj Quantum Information, 3(1):15, 2017.
  * [LP17] David A Levin and Yuval Peres.  Markov chains and mixing times, volume 107.  American Mathematical Soc., 2017.
  * [MHFW16a] Alexander Müller-Hermes, Daniel Stilck França, and Michael M. Wolf.  Entropy production of doubly stochastic quantum channels.  Journal of Mathematical Physics, 57(2):022203, feb 2016.
  * [MHFW16b] Alexander Müller-Hermes, Daniel Stilck França, and Michael M. Wolf.  Relative entropy convergence for depolarizing channels.  Journal of Mathematical Physics, 57(2):022202, feb 2016.
  * [MHRW15] Alexander Müller-Hermes, David Reeb, and Michael M. Wolf.  Quantum subdivision capacities and continuous-time quantum coding.  IEEE Transactions on Information Theory, 61(1):565–581, jan 2015\.
  * [Mov18] Ramis Movassagh.  Efficient unitary paths and quantum computational supremacy: A proof of average-case hardness of random circuit sampling.  arXiv preprint arXiv:1810.04681, 2018.
  * [NRK+18] C. Neill, P. Roushan, K. Kechedzhi, S. Boixo, S. V. Isakov, V. Smelyanskiy, A. Megrant, B. Chiaro, A. Dunsworth, K. Arya, R. Barends, B. Burkett, Y. Chen, Z. Chen, A. Fowler, B. Foxen, M. Giustina, R. Graff, E. Jeffrey, T. Huang, J. Kelly, P. Klimov, E. Lucero, 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, 360(6385):195–199, apr 2018.
  * [PGN+19] Edwin Pednault, John A. Gunnels, Giacomo Nannicini, Lior Horesh, and Robert Wisnieff.  Leveraging secondary storage to simulate deep 54-qubit sycamore circuits, 2019.  arXiv 1910.09534.
  * [PWR+19] D. S. Phillips, M. Walschaers, J. J. Renema, I. A. Walmsley, N. Treps, and J. Sperling.  Benchmarking of gaussian boson sampling using two-point correlators.  Physical Review A, 99(2), feb 2019.
  * [QBQGP20] Haoyu Qi, Daniel J. Brod, Nicolás Quesada, and Raul Garcia-Patron.  Regimes of classical simulability for noisy gaussian boson sampling.  Physical Review Letters, 124(10), mar 2020.
  * [SS14] John A. Smolin and Graeme Smith.  Classical signature of quantum annealing.  Frontiers in Physics, 2, sep 2014.
  * [SSSV14] Seung Woo Shin, Graeme Smith, John A. Smolin, and Umesh Vazirani.  How ”quantum” is the d-wave machine?, 2014.  arXiv 1401.7087.
  * [SVB+14] Nicolò Spagnolo, Chiara Vitelli, Marco Bentivegna, Daniel J. Brod, Andrea Crespi, Fulvio Flamini, Sandro Giacomini, Giorgio Milani, Roberta Ramponi, Paolo Mataloni, Roberto Osellame, Ernesto F. Galvão, and Fabio Sciarrino.  Experimental validation of photonic boson sampling.  Nature Photonics, 8(8):615–620, jun 2014.
  * [TRW05] Koji Tsuda, Gunnar Rätsch, and Manfred K Warmuth.  Matrix exponentiated gradient updates for on-line learning and bregman projection.  J. Mach. Learn. Res., 6(Jun):995–1018, 2005.
  * [WRB+13] Lei Wang, Troels F. Rønnow, Sergio Boixo, Sergei V. Isakov, Zhihui Wang, David Wecker, Daniel A. Lidar, John M. Martinis, and Matthias Troyer.  Comment on: ”classical signature of quantum annealing”, 2013.  arXiv 1305.5837.

##  Appendix A Bound on the Shannon entropy from design property

We will now show that the Shannon entropy of the output distributions of
approximate two designs when measured in the computational basis is
essentially maximal. This result is similar in spirit to those of [AA14a,
HKEG19].

######  Proposition A.1.

Let $U$ be a $(2,\epsilon 2^{-2n-1})$ approximate unitary design and define
$\nu$ as before. Then, with probability at least $1-\delta$:

$\displaystyle S(\nu)\geq n-\log(2-\epsilon)+\log(\delta)$

###### Proof.

For a Haar random unitary and $x\in\\{0,1\\}^{n}$ we have that:

$\displaystyle\mathbb{E}\left(\left|\bra{x}U\ket{0}\right|^{2}\right)=\frac{1}{2^{n}},\quad\mathbb{E}\left(\left|\bra{x}U\ket{0}\right|^{4}\right)=\frac{2}{2^{n}(2^{n}+1)}.$

Thus, for an approximate two design as above, we have that:

$\displaystyle\mathbb{E}\left(\left|\bra{x}U\ket{0}\right|^{4}\right)\leq\frac{2}{2^{n}(2^{n}+1)}+\frac{\epsilon}{2^{n}(2^{n}+1)}.$

Recall that the $2$-Renyi entropy $S_{2}$ is defined as:

$\displaystyle S_{2}(\nu)=-\log\left(\sum\limits_{x}\nu(x)^{2}\right)$

and that $S(\nu)\geq S_{2}(\nu)$. Moreover, the function $-\log$ is convex.
Thus, it follows from Jensen’s inequality that:

$\displaystyle\mathbb{E}\left(-\log\left(\sum\limits_{x}\nu(x)^{2}\right)\right)\geq-\log\left(\mathbb{E}\left[\sum\limits_{x}\nu(x)^{2}\right]\right).$

From the computations above, we have that:

$\displaystyle\frac{2+\epsilon}{(2^{n}+1)}\geq\mathbb{E}\left[\sum\limits_{x}\nu(x)^{2}\right],$

from which we readily obtain that:

$\displaystyle\mathbb{E}\left(-\log\left(\sum\limits_{x}\nu(x)^{2}\right)\right)\geq
n-\log(2+\epsilon).$

It follows from Markov’s inequality that

$\displaystyle\mathbb{P}\left(\sum\limits_{x}\nu(x)^{2}\geq\frac{2+\epsilon}{\delta
2^{n}}\right)\leq\delta,$ (24)

from which the claim follows. ∎

##  Appendix B Auxiliary results for Section 5

In Section 5 we showed that being able to efficiently distinguish the
probability distributions arising from sampling from random circuits from the
uniform distribution implies the ability to fool the XHOG problem associated
to the same class of circuits to a certain level.

But we assumed that the function that distinguished the distributions has
binary outputs, although our framework for distinguishability allows for
functions with outputs in $[0,1]$. We now show that it is always possible to
obtain an efficiently computable function with binary outputs from an
efficiently function with image $[0,1]$ that distinguishes the two probability
distributions, at the expense of a smaller distinguishability power.

######  Lemma B.1.

Let $f:\\{0,1\\}^{n}\to[0,1]$ be a function that can be computed in polynomial
time such that for some probability measure $\nu$ and $\epsilon>0$ we have
that:

$\displaystyle\mathbb{E}_{\nu}(f)-\mathbb{E}_{\mathcal{U}}(f)\geq\epsilon.$

Then there exists a function $f^{\prime}:\\{0,1\\}^{n}\to\\{0,1\\}$ that can
be computed in polynomial time such that:

$\displaystyle\mathbb{E}_{\nu}(f^{\prime})-\mathbb{E}_{\mathcal{U}}(f^{\prime})\geq\frac{\epsilon^{2}}{4}.$

###### Proof.

Assume w.l.o.g. that $\epsilon=m^{-1}$ for some integer $m$ and consider the
discretization of $f_{1}$ of $f$ given by:

$\displaystyle f_{1}(x)=(2m)^{-1}\lceil 2mf(x)\rceil.$

Note that $\|f-f_{0}\|_{\infty}\leq(4m)^{-1}$ and, thus,

$\displaystyle\mathbb{E}_{\nu}(f_{0})-\mathbb{E}_{\mathcal{U}}(f_{0})\geq\frac{\epsilon}{2}.$

Moreover, note that $f_{1}$ only takes the $2m$ possible values
$\\{(2m)^{-1},\ldots,1\\}$. Combining this fact and that for every real valued
random variable $X$ we have:

$\displaystyle\mathbb{E}(X)=\int\mathbb{P}(X\geq x)dx,$

we see that

$\displaystyle\mathbb{E}_{\nu}(f_{0})=\sum\limits_{k=1}^{2m}\nu\left(f_{0}(x)\geq\frac{k}{2m}\right)\geq\frac{\epsilon}{4}+\sum\limits_{k=1}^{2m}\frac{\left|\\{f_{0}(x)\geq\frac{k}{2m}\\}\right|}{2^{n}}.$

It then follows that for at least one $1\leq k_{0}\leq 2m$ we have that:

$\displaystyle\nu\left(f_{0}(x)\geq\frac{k}{2m}\right)\geq\frac{\left|\\{f_{0}(x)\geq\frac{k}{2m}\\}\right|}{2^{n}}+\frac{\epsilon}{8m}.$
(25)

Thus, by setting $f^{\prime}(x)=1$ if $f_{0}(x)\geq\frac{k}{2m}$ and $0$ else
and recalling that $m^{-1}=\epsilon$, we see that Eq. (25) immediately implies

$\displaystyle\mathbb{E}_{\nu}(f^{\prime})-\mathbb{E}_{\mathcal{U}}(f^{\prime})\geq\frac{\epsilon^{2}}{8},$

which yields the claim. ∎

##  Appendix C Distinguishing the output distribution of stabilizer states

Note that we only assumed in the proofs of Sec. 5 that the underlying circuit
ensemble is an approximate two design. It is well-known that circuits being
approximate two designs does not imply that one cannot sample from their
output distribution efficiently, as is prominently exemplified by Clifford
circuits. Random Cliffords are two-designs [DCEL09, DLT02] and it is possible
to simulate measurements in the computational basis efficiently for them
[Got98, AG04]. We now show that in this case, it is also possible to easily
distinguish the outcome distribution from the uniform one, if this is possible
at all.

It is not difficult to see that for a Pauli string
$P=\otimes_{i=1}^{n}\sigma_{i}$ we have for a Clifford $C$ that

$\displaystyle\text{tr}\left(PC|0\rangle\langle 0|^{\otimes
n}C^{\dagger}\right)\in\\{-1,0,1\\}.$

This is because, as Cliffords stabilize the Pauli group, we have that
$\tilde{P}=C^{\dagger}PC$ is again, up to a global sign, a Pauli string. And
for a Pauli string $\text{tr}\left(\tilde{P}|0\rangle\langle 0|^{\otimes
n}\right)\in\\{0,1\\}$. Now assume that there exists a Pauli string $P$
consisting only of $I$ and $Z$ Pauli matrices that differs from the identity
and such that

$\displaystyle\text{tr}\left(PC|0\rangle\langle 0|^{\otimes
n}C^{\dagger}\right)\not=0.$

Then, interpreting diagonal operators as functions, we have that the function
$f=\frac{P+I}{2}$ is a binary function that satisfies:

$\displaystyle|\mathbb{E}_{\nu}(f)-\mathbb{E}_{\mathcal{U}}(f)|=\frac{1}{2}.$

Thus, in this case, we have found a function that efficiently distinguishes
the outcome from uniform. But note that in some cases such a Pauli string does
not exist, such as if the Clifford is $H^{\otimes n}$, as then the outcome
distribution is uniform.

Let us now discuss how to efficiently find the appropriate distinguishing
Pauli string. We refer to [AG04] for a review of the basics of the stabilizer
formalism. First, we recall that a stabilizer state $\ket{\psi}$ on $n$ qubits
can always be described by $n$ generators $g_{1},\ldots,g_{n}$ of its
stabilizer group $SG(\ket{\psi})$. Moreover, note that for a Pauli string

$\displaystyle\text{tr}\left(PC|0\rangle\langle 0|^{\otimes
n}C^{\dagger}\right)\in\\{-1,1\\}.$

is equivalent to $P\in SG(\ket{\psi})$ or $-P\in SG(\ket{\psi})$. Thus, by our
previous discussion, the problem of finding a function to distinguish the
output of the Clifford circuit from the uniform distribution is equivalent to
finding a stabilizer of the state consisting solely of $Z$ and $I$ Pauli
operators.

Let us now discuss how to achieve this. First, decompose each generator
$g_{i}$ as the product of a string of Pauli $X$ and Pauli $Z$ matrices plus a
global $\pm 1$ phase and represent each one of these as vectors
$(x_{i},z_{i},s_{i})$ in $\mathbb{F}^{2n+1}_{2}$. In order to simplify the
presentation, we are not going to keep track of the global phase of the
elements of the stabilizer group for now. Thus, we restrict to the vectors
$(x_{i},z_{i})$ corresponding to the first $2n$ entries. It is easy to see
that if we do not keep track of the global phase, then multiplying two
generators is equivalent to adding the corresponding vectors in
$\mathbb{F}^{2n}_{2}$. Now define the $n\times(2n+1)$ binary matrix $A$ with
the vectors $x_{i}$ in its rows. We then have:

######  Proposition C.1.

Let $\ket{\psi}$ be a stabilizer state with generators $g_{1},\ldots,g_{n}$
and corresponding vectors $(x_{i},z_{i})\in\mathbbm{Z}^{2n}$. Then there
exists a $Z$ string $P\in SG(\ket{\psi})$ if and only if:

$\displaystyle\operatorname{span}\\{(x_{1},y_{1}),\ldots,(x_{n},y_{n})\\}\cap\left(\\{0\\}\times\mathbbm{Z}^{n}\right)\not=\\{0\\}$
(26)

###### Proof.

Note that

$\displaystyle\operatorname{span}\\{(x_{1},y_{1}),\ldots,(x_{n},y_{n})\\}$

corresponds to the elements of the stabilizer group of the state, up to a
global phase. This is because, as discussed before, multiplication in the
Pauli group just corresponds to a sum of the vectors, up to the global phase.
Thus, if we find a string of $Z$ in the stabilizer group, then it is also in
the intersection in eq. (26). ∎

Thus, we can find the distinguishing Pauli operator by a nonzero element of
the subspace

$\displaystyle\operatorname{span}\\{(x_{1},y_{1}),\ldots,(x_{n},y_{n})\\}\cap\left(\\{0\\}\times\mathbbm{Z}^{n}\right),$

which can be done by Gaussian elimination.