Anticoncentration theorems for schemes showing a quantum
speedup
D. Hangleiter, J. Bermejo-Vega, M. Schwarz, and J. Eisert
Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany
May 16, 2018
One of the main milestones in quantum in-
formation science is to realise quantum de-
vices that exhibit an exponential computa-
tional advantage over classical ones without
being universal quantum computers, a state
of affairs dubbed quantum speedup, or some-
times “quantum computational supremacy”.
The known schemes heavily rely on mathe-
matical assumptions that are plausible but un-
proven, prominently results on anticoncentra-
tion of random prescriptions. In this work, we
aim at closing the gap by proving two anticon-
centration theorems and accompanying hard-
ness results, one for circuit-based schemes,
the other for quantum quench-type schemes
for quantum simulations. Compared to the
few other known such results, these results
give rise to a number of comparably simple,
physically meaningful and resource-economical
schemes showing a quantum speedup in one
and two spatial dimensions. At the heart of
the analysis are tools of unitary designs and
random circuits that allow us to conclude that
universal random circuits anticoncentrate as
well as an embedding of known circuit-based
schemes in a 2D translation-invariant architec-
ture.
1 Introduction
Realising a quantum device that computationally out-
performs state-of-the art classical supercomputers for
a certain task that is provably intractable classically
has become a key milestone in the field of quantum
simulation and computing. This goal is often referred
to as “quantum (computational) supremacy” [1] or
quantum speedup. Such a quantum speedup is not
merely meant in the sense of quantum dynamics being
no longer tractable on classical supercomputers using
the best known algorithms to date, for which there is
evidence already today [2–4]. Instead, to make sure
that the inefficient classical simulation is not victim of
D. Hangleiter: dominik.hangleiter@fu-berlin.de
J. Bermejo-Vega: jbermejovega@gmail.com
M. Schwarz: martin.schwarz@gmail.com
J. Eisert: jense@zedat.fu-berlin.de
a lack of imagination, such a quantum speedup is usu-
ally meant to refer to schemes for which the speedup
can be related to a notion of computational complex-
ity. For a quantum speedup scheme to be physically
realisable in principle in the absence of quantum error
correction, it is crucial that the hardness of the task is
robust under physically realistic errors. To have any
hope of realising such a scheme in the near term one
would moreover wish for the resources required for an
implementation of the architecture in the intractable
regime to be achievable with present-day (or near-
term) technology.
There are only very few quantum speedup archi-
tectures that are robust against physically realistic
constant total-variation distance errors [5–12]. Even
fewer of those are physically realistic when it comes to
an implementation in present-day technology in that
they require only nearest-neighbour interactions and
are feasible in the available experimental platforms
such as linear optics [5], superconducting qubits [7, 8],
ion traps or cold atoms in optical lattices [10]. The
computational task that is solved in all of these pro-
posals is a sampling task, in particular, the task of
sampling from the output distribution of a certain
random time-evolution. That random time evolution
may take the form of a Haar-random unitary applied
to a bosonic state [5], a random circuit from a gate set
[8], IQP circuits [7] applied to an all-zero state, or even
a translation-invariant nearest-neighbour Ising Hamil-
tonian that is applied to a random product state [10].
In addition to this discussion, there is the question to
what extent schemes showing a quantum speedup can
be certified in their correctness [9, 10, 12–16].
The central ingredient of all existing quantum
speedup proofs is Stockmeyer’s algorithm [17] that
implies a collapse of the Polynomial Hierarchy if sam-
pling from the output distribution of the respective
circuits is #P-hard on average. In order for this hard-
ness argument to be valid, one crucially requires so-
called anticoncentration bounds for the output prob-
ability distribution of the respective random circuits
[18].
Indeed, it has been shown that one can efficiently
classically sample from output distributions of cer-
tain circuit families, including IQP circuits, the out-
put distribution of which concentrates on a polynomi-
ally small subset of the sample space [19]. This shows
Accepted in Quantum 2018-05-09, click title to verify 1
arXiv:1706.03786v4 [quant-ph] 15 May 2018
that concentrated output distributions are in many
relevant cases simulable, rendering anticoncentration
a necessary condition for classical hardness for these
cases.
Despite of their central role in the hardness ar-
gument of quantum speedup proposals, only few
proofs of anticoncentration bounds are known so far
[6, 7, 11]. In all other speedup architectures – bo-
son sampling [5], universal random circuits [8], and
translation-invariant Ising models [9, 10] – there exists
none or merely numerical evidence for anticoncentra-
tion of the respective circuit families and the validity
of the anticoncentration assumption needs to be con-
jectured. This still gives rise to plausible schemes, but
in order to complete the program of realising quan-
tum schemes showing a quantum speedup, these gaps
must necessarily be closed. Rigorous anticoncentra-
tion results for classically intractable circuit families
are therefore both of crucial importance to corrobo-
rate the validity of those existing speedup proposals,
as well as to shine light on the conditions of them
coming about which are highly debated in the litera-
ture.
In this work, we provide rigorous anticoncentration
results for two types of such quantum architectures
that are at the same time not classically simulable.
First, we show that random circuits drawn from a
unitary 2-design anticoncentrate. We then apply this
result to both show that random circuits comprised
of nearest-neighbour gates that are drawn from a uni-
versal gate set containing inverses anticoncentrate in
linear depth, and propose two new schemes based
on this insight. Second, we prove that the output
distribution of a particular nearest-neighbour quan-
tum quench architecture based on the time evolution
of product states under certain translation-invariant
Ising models anticoncentrate in constant depth. Thus,
we consider two types of architectures tailored to-
wards different kinds of experimental platforms in the
following sense. In platforms in which achieving large
numbers of qubits is expensive and local control fea-
sible, circuit-based schemes such as universal random
circuits can be reasonably implemented. A paradig-
matic example of such a platform might be consti-
tuted of superconducting qubits. In contrast, there
are physically most natural settings of quantum sim-
ulators in which local control on the level of individual
gates is difficult to achieve, but for which extremely
large numbers of local constituents can be reached.
Cold atoms in optical lattices, in which 10
4
− 10
5
atoms are readily reachable, provide the most promi-
nent example of such an architecture. Our quench-
type architecture is tailored toward such settings.
The application of our first result to universal ran-
dom circuits complies with the intuition that due to
the ballistic spread of correlations anticoncentration
will generically arise in depth that scales linearly with
the diameter of the system under consideration, and
hence, linearly in a one-dimensional architecture [8].
Still, to the best of our knowledge there is no rigorous
proof for anticoncentration of universal random cir-
cuits. In contrast, in the light of this intuition the sec-
ond result is quite surprising: It has even been argued
[18] that it cannot be expected to reach anticoncen-
trating output distributions in constant depth, retain-
ing its classical intractability. We conjecture the scal-
ing of both results to be optimal in the settings con-
sidered (unstructured circuits in one dimension and
highly structured circuits in two dimensions).
To prove the first result (Theorem 5) we make
use of properties of approximate unitary 2-designs
and apply the Paley-Zygmund inequality. In apply-
ing this result to show that several schemes anticon-
centrate we use the fact that all these schemes form
approximate 2-designs. This includes, universal ran-
dom circuits as in [8], Clifford circuits acting on in-
put product magic states [20], and certain models of
diagonal unitaries [21]. What is more, we provide
new complexity-theoretic evidence for the hardness
of classically simulating these random-circuit fami-
lies in the approximate sampling sense. In doing so,
we focus on universal random circuits, which attain
this property already in linear O(n) depth [22, 23].
For this case, we derive a matching classical-hardness
upper bound by proving that a broad class of 1D
random quantum circuits are hard to simulate clas-
sically already in linear O(n) circuit depth, in the
strong simulation sense (Lemma 8). The novel as-
pects of our work are the generality of these results
and the minimal linear-depth requirements for achiev-
ing both classical hardness and anticoncentration on
a 1D nearest-neighbour architecture. This drastically
improves over prior work [8] on universal random cir-
cuits, which gave only numerical evidence for anti-
concentration (in depth O(
√
n), and in 2D), and no
matching classical-hardness depth bound. Prior to
us, analogous depth results were only available for
nearest-neighbour IQP circuit models supplemented
by SWAP gates: for these, Ref. [7] gave O(
√
n log n)
depth bounds for anticoncentration and hardness in
2D architectures, and Ref. [10] proved linear O(n)
ones in 1D layouts.
For the second result (Theorem 9) and Corollar-
ies 10–12 thereof, we use the facts that IQP circuits
anticoncentrate [7] and can be implemented in a 1D
architecture in linear depth [10]. Our technical con-
tribution is to provide an embedding of such IQP
circuits in the constant-time evolution of a product
state under a translation-invariant Ising model on a
two-dimensional lattice. Via this embedding we are
thus able to show the first anticoncentration bound
for translation-invariant constant-depth schemes that
exhibit a quantum speedup [9, 10].
This work is structured as follows: First, in Sec. 2,
we will introduce the formal statement of anticon-
centration and show how it is used in the Stock-
Accepted in Quantum 2018-05-09, click title to verify 2
meyer hardness proof. In Sec. 3 we will both state
and prove the anticoncentration result for approxi-
mate unitary 2-designs and then apply this result to
relevant examples, most importantly, universal ran-
dom circuits in linear depth. In Sec. 4 we will then
prove the anticoncentration result for the constant-
time evolution of a random product state under a
certain nearest-neighbour translation-invariant Ising
Hamiltonian. Finally, we discuss the implications of
our results in the context of the timely literature in
Sec. 5, and conclude in Sec. 6.
2 Preliminaries: Anticoncentration
and quantum speedups
Throughout this work, we consider quantum systems
consisting of n qubits (with obvious generalisation
to d-dimensional local constituents). To start with,
let us make precise, what is meant by anticoncentra-
tion of the output distribution of a unitary U drawn
from a certain measure µ. We call the distribution of
probabilities |hx|U|0i|
2
of obtaining x ∈ {0, 1}
n
when
applying a unitary U ∈ U(N), N = 2
n
, to an ini-
tial state vector |0i := |0i
⊗n
and measuring in the
computational basis, the output distribution. We say
that this output distribution anticoncentrates if there
exist universal constants α, β > 0 such that for any
x ∈ {0, 1}
n
, the probabilities |hx|U|0i|
2
of this unitary
anticoncentrate,
Pr
U∼µ
|hx|U|0i|
2
≥
α
N
> β . (1)
We can interpret this probability as the probability
that an arbitrarily chosen entry x of the first col-
umn of a µ-randomly chosen U is larger than α/N.
Throughout this work, we say that a quantity X is
approximated by a quantity
˜
X with multiplicative er-
ror c if X/c ≤
˜
X ≤ cX, with relative error r if
(1 − r)X ≤
˜
X ≤ (1 + r)X, and with additive error a
if kX − Xk
∗
≤ a for some norm k · k
∗
.
In the commonly used proof technique for quantum
speedups [24, 25] Stockmeyer’s algorithm [17] is ap-
plied to show a collapse of the polynomial hierarchy if
for an arbitrary such x the amplitude |hx|U |0i|
2
is #P-
hard to approximate multiplicatively. Anticoncentra-
tion comes into this proof when hardness is shown
not up to multiplicative but up to an additive error
in total-variation distance. More specifically, to prove
a quantum speedup with constant total-variation dis-
tance errors for sampling from the output distribution
of a circuit family F using the argument developed in
Refs. [5, 6] one requires three ingredients: (i) The out-
put distribution of F anticoncentrates in the sense of
Eq. (3). (ii) postF = postBQP. By the result of Refs.
[26, 27] the output probabilities are then #P-hard to
approximate up to relative error 1/4. (iii) The output
probabilities of F are #P-hard to approximate up to
multiplicative errors in the average case. This needs
to be conjectured for all quantum speedup schemes
1
,
preferably in terms of a universal quantity such as
the imaginary-time partition function of Ising models
[6], the permanent [5], or the Jones polynomial [29].
Together, (ii) and (iii) permit a reduction from hard-
ness of strong simulation up to multiplicative error to
hardness of weak simulation up to an additive error
using Stockmeyer’s algorithm [17] in the third level
of the Polynomial Hierarchy. As a result, very often
three conjectures need to be made when proving a
quantum speedup using this technique:
C1 The Polynomial Hierarchy cannot collapse to its
3rd level [30–32].
C2 If it is #P-hard to approximate the output prob-
ability of a circuit drawn from F up to a constant
relative error, then the same problem is #P-hard
for a constant fraction of the instances
2
.
C3 The output distribution of F anticoncentrates.
In the following, we will prove the anticoncentra-
tion conjecture C3 in the sense of equation (1) both
for certain circuit-based schemes, in fact, those that
form an approximate 2-design, and a quantum-quench
architecture in the mindset of Ref. [10].
3 Anticoncentration of circuit-based
schemes
In this section we will begin by introducing and prov-
ing our first result, namely, that approximate unitary
2-designs anticoncentrate, and then apply this result
to three relevant examples of circuit-based schemes,
most prominently, universal random circuits.
3.1 Anticoncentration of unitary 2-designs
Unitary k-designs approximate the uniform (Haar)
measure on the unitary group (see App. A.1) in the
sense that the first k moments of a unitary k-design
and the Haar measure match (exactly or approxi-
mately). The definition of a k-design is motivated by
the fact that in experiments samples from a unitary
k-design are much easier to realise than samples from
the full Haar measure. In order to define the notion
of a k design, we need the notion of the k
th
-moment
operator that acts as a unitary twirl with respect to
some measure µ on the unitary group maps on an
operator.
1
In the exact case, one can even prove average-case results
for the permanent [5] and random-circuit based schemes [28].
2
This conjecture may be regarded as a qubit analogue of the
“permanent-of-Gaussians” conjecture of Ref. [5].
Accepted in Quantum 2018-05-09, click title to verify 3
Definition 1 (k
th
-moment operator). Let M
k
µ
be the
k-th moment operator on L(H
⊗k
) with respect to a
distribution µ on U (N ), N = 2
n
= dim H defined as
X 7→ M
k
µ
(X)
:
= E
µ
U
⊗k
X(U
†
)
⊗k
=
Z
U(N )
U
⊗k
X(U
†
)
⊗k
µ(U).
(2)
We can now define unitary k-designs [22, 33].
Definition 2 (Unitary k-design). Let µ be a distribu-
tion on the unitary group U(N). Then µ is an exact
unitary k-design if
M
k
µ
= M
k
µ
Haar
.
In all of what follows, we will need to relax this no-
tion to the notion of an approximate unitary k-design.
In such a definition we can allow for both relative and
additive errors on the equality (2) [23, 34]:
Definition 3 (Approximate unitary k-designs). Let
µ be a distribution on the unitary group U (N). Then
µ is
1. an additive -approximate unitary k-design if
kM
k
µ
− M
k
µ
Haar
k
≤ ,
2. a relative -approximate unitary k-design if
(1 − )M
k
µ
Haar
≤ M
k
µ
≤ (1 + )M
k
µ
Haar
.
Since the former definition is much more common
in the literature, let us remark that the two definitions
are closely related via the following Lemma of Ref. [23]
in which, however, a factor of the dimension enters.
Lemma 4 (Additive and relative approximate de-
signs). If µ is a relative -approximate unitary k-
design then kM
k
µ
− M
k
µ
Haar
k
≤ 2. Conversely, if
kM
k
µ
− M
k
µ
Haar
k
≤ , then µ is a relative N
2k
-
approximate unitary k-design.
We are now ready to state our first anticoncentra-
tion result on unitary 2-designs.
Theorem 5 (Anticoncentration of unitary 2-designs).
Let µ be a relative -approximate unitary 2-design
on the group U (N ). Then the output probabilities
|hx|U|0i|
2
for x ∈ {0, 1}
n
of a µ-random unitary U ∈
U(N) anticoncentrate in the sense that for 0 ≤ α ≤ 1
P
U∼µ
|hx|U|0i|
2
>
α(1 − )
N
≥
(1 − α)
2
(1 − )
2
2(1 + )
.
(3)
We point out that Theorem 5 also holds in ex-
actly the same way for relative -approximate state
2-designs. This is a weaker condition than the unitary
design condition since any (approximate) unitary 2-
design generates an (approximate) state 2-design via
application to an arbitrary reference state. Also note
that the fact that µ is a relative -approximate 1-
design (cf. App. A.3) is crucial for the bound (3) to
become non-trivial. If instead µ was an additive de-
sign the lower bound would asymptotically tend to
zero as 1/N and hence not stay larger than a con-
stant. However, the 1-design condition holds even ex-
actly for many distributions µ, although for the higher
moments it may only hold approximately.
Proof of Theorem 5. Our proof of the anticoncentra-
tion bound (3) has two steps and relies on two ingre-
dients: In the first step, we prove anticoncentration of
a single but fixed entry of Haar random unitaries. To
this end we make use of the Paley-Zygmund inequality
and an explicit expression of the distribution of ma-
trix elements of Haar-random unitaries. In the second
step, we extend this result to full anticoncentration of
all output probabilities in the sense of equation (3).
The Paley-Zygmund inequality is a lower-bound
analogue of Markov-type tail bounds and can be
stated as follows. If Z ≥ 0 is a random variable with
finite variance, and if 0 ≤ α ≤ 1
P(Z > αE[Z]) ≥ (1 − α)
2
E[Z]
2
E[Z
2
]
. (4)
That is, it lower bounds the probability that a positive
random variable is small in terms of its mean and
variance.
Now let µ be a relative -approximate unitary 2-
design. Then for l = 2, 4, it holds that
(1 − )E
U∼Haar
|ha|U|bi|
l
≤ E
U∼µ
|ha|U|bi|
l
≤ (1 + )E
U∼Haar
|ha|U|bi|
l
.
(5)
This is due to the fact that for any unitary k-
design µ the expectation value of an arbitrary
polynomial P of degree 2 in the matrix elements
of both U and U
†
over µ equals the same ex-
pectation value but taken over the Haar measure
up to a relative error > 0 [35]. To see this,
observe that averaging a monomial in the matrix
elements of U over the k-design µ can be expressed
as hi
1
, . . . , i
k
|M
k
µ
(|j
1
, . . . , j
k
ihj
0
1
, . . . , j
0
k
|)|i
0
1
, . . . , i
0
k
i.
Hence, if M
k
µ
= M
k
Haar
, “then any polynomial of
degree k in the matrix elements of U will have the
same expectation over both distributions” [35]. This
gives rise to
P
U∼µ
(|hx|U|0i|
2
> α(1 − )E
U∼Haar
[|hx|U|0i|
2
])
≥ P
U∼µ
(|hx|U|0i|
2
> αE
U∼µ
[|hx|U|0i|
2
])
≥ (1 − α)
2
E
U∼µ
[|hx|U|0i|
2
]
2
E
U∼µ
[|hx|U|0i|
4
]
≥ (1 − α)
2
(1 − )
2
E
U∼Haar
[|hx|U|0i|
2
]
2
(1 + )E
U∼Haar
[|hx|U|0i|
4
]
.
(6)
Lemma 6 (Marginal output distribution). The dis-
tribution of the marginal output probabilities p =
Accepted in Quantum 2018-05-09, click title to verify 4
|hx|U|0i|
2
of Haar random unitaries U and arbitrary
but fixed x is given by
P
Haar
(p) = (N − 1)(1 − p)
N−2
N1
−−−→ N exp(−Np).
(7)
In particular, P
Haar
’s first and second moments are
given by
E
Haar
[p] =
1
N
, E
Haar
[p
2
] =
2
N(N + 1)
. (8)
We prove this lemma in App. B. Inserting the
expressions Eqs. (8) for E
U∼Haar
[|hx|U|0i|
2
] and
E
U∼Haar
[|hx|U|0i|
4
], we find
P
U∼µ
|hx|U|0i|
2
>
α(1 − )
N
≥ (1 − α)
2
N(N + 1)
2N
2
(1 − )
2
(1 + )
≥ (1 − α)
2
(1 − )
2
2(1 + )
,
which completes the proof.
Note that the moments (8) can alternatively be ob-
tained for both state and unitary 2-designs exploiting
Schur-Weyl duality. This yields an explicit expression
of the k
th
-moment operators M
k
µ
(X) as the projec-
tor onto the span of the symmetric group on k tensor
copies of the Hilbert space H. Moreover, the moments
of the output probabilities of state 2-designs are also
given by (8). This can be seen similarly using the
fact that the expectation value over a state k-design
is given by the projection onto the k-partite symmet-
ric subspace of H
⊗k
[36]. We note that the output
distribution (7) of a Haar random unitary asymp-
totically approaches the exponential (Porter-Thomas)
distribution. This behaviour has already been ob-
served numerically in many different contexts involv-
ing pseudo-random operators [22, 37], non-adaptive
measurement-based quantum computation [38], and
universal random circuits [8].
3.2 Applications: a “recipe” for quantum
speedups
Our anticoncentration theorem 5 for approximate uni-
tary (and state) 2-designs leads to a generic “recipe”
for the identification of quantum circuit families and
input states that are hard to simulate classically un-
der plausible complexity-theoretic conjectures, build-
ing upon the approach of Refs. [5, 6]. The strategy
goes in three steps parallel to ingredients (i-iii) of the
proof based on Stockmeyer’s algorithm introduced in
Sec. 2. In the following, we apply this general strat-
egy to a few examples of random circuits, most promi-
nently, universal random circuits.
Universal random circuits. The first exam-
ple that we also focus on are random quan-
tum circuits constructed from single- and two-qubit
(a)
|0i
|0i
|0i
|0i
|0i
(b)
|0i
|0i
|0i
|0i
|0i
U
4
U
0
U
1
U
0
U
3
U
2
U
4
U
2
U
3
U
3
U
4
U
4
U
0
U
4
U
1
U
2
U
0
U
0
U
0
U
0
Figure 1: Layout of the parallel random circuit families.
In each step either the even or odd configuration of parallel
two-qubit unitaries is applied with probability 1/2. Every two-
qubit gate is chosen from the respective measure on U(4) –
(a) the Haar measure, (b) the uniform distribution on the
gate set G. Here we depict a five-qubit random instance of
depth 10 where in (a) the colour choice represents different
gates, and in (b) the gate set consists of 5 two-qubit unitaries
G = {U
0
, U
2
, . . . , U
4
}.
gates, most prominently, the gate set G
BIS
=
{CZ, H,
√
X,
√
Y , T } studied by Boixo et al. [8, 39].
In presenting this example we put particular emphasis
on the circuit depth required to reach a scheme that
shows a provable quantum speedup. As a first step (i)
of the general strategy, the following Corollary estab-
lishes that the output distribution of a random circuit
formed in a particular fashion from G
BIS
anticoncen-
trates. This holds already in linear depth.
Corollary 7 (Universal random circuits anticoncen-
trate). The output probabilities of universal random
circuits in one dimension from the following two cir-
cuit families (illustrated in Fig. 1) anticoncentrate in
a depth that scales as O(n log(1/)) in the sense of
Eq. (3).
• Parallel local random circuits: In each step ei-
ther the unitary U
1,2
⊗U
3,4
⊗···⊗U
n−1,n
or the
unitary U
2,3
⊗ U
4,5
⊗ ··· ⊗ U
n−2,n−1
is applied
(each with probability 1/2), with U
j,j+1
indepen-
dent unitaries drawn from the Haar measure on
U(4). (This assumes n is even.)
• Universal gate sets: Let G
:
= {g
i
}
m
i=1
with each
g
i
∈ U (4) be a universal gate set containing in-
verses with elements composed of algebraic iden-
tities, i.e., a gate set G such that the group
generated by G is dense in U(4) and satisfying
Accepted in Quantum 2018-05-09, click title to verify 5
g
i
∈ G ⇒ g
−1
i
∈ G. In each step either the
unitary U
1,2
⊗ U
3,4
⊗ ··· ⊗ U
n−1,n
or the uni-
tary U
2,3
⊗U
4,5
⊗···⊗U
n−2,n−1
is applied (each
with probability 1/2), with U
j,j+1
independent
unitaries drawn uniformly from G.
Proof of Corollary 7. The central ingredient of our
proof of Corollary 7 is the result of Ref. [23]. There,
the authors show that the two random circuit families
are relative -approximate unitary k-designs on U (2
n
)
in depth poly(k) ·O(n log(1/)) (Corollary 6 and 7 in
Ref. [23]).
Hence, in particular, these random circuits are
relative -approximate unitary 2-designs in depth
O(n log(1/)), i.e., linear in the number of qubits and
logarithmic in 1/. Applying Theorem 5 to the output
probabilities |hx|C|0i|
2
of a random circuit C applied
to an initial all-zero state yields the claimed anticon-
centration bound for the output probabilities of such
circuits.
To prove a quantum speedup using the Stock-
meyer technique the second required ingredient is #P-
hardness of strong classical simulation of the output
probabilities (ii). Indeed, since the gate set G
BIS
is
universal, the postF =postBQP connection is im-
mediate. Boixo et al. [8] moreover showed that the
output probabilities can be expressed in terms of the
imaginary-time partition function of a random Ising
model, suggesting that the average-case conjecture for
random circuits is a natural one (iii). It remains to
be shown that random universal circuits are both not
classically strongly simulable and anticoncentrate in
linear depth in a one-dimensional setting. Lemma 8
(below) establishes this is indeed the case for a large
class of finite gate sets with efficiently-computable
matrix entries (so that they cannot artificially encode
solutions to hard problems). It is an open question
whether this can be improved to square-root depth in
a two-dimensional setting such as that of Refs. [8, 39].
Given two O(1)-local gate sets A and B, we say
that A exactly synthesises B if every gate V ∈ B can
be exactly implemented via a polynomial-time com-
putable constant-size circuit of gates in A.
Lemma 8 (Hardness of strong classical simulation).
Let G be any finite universal gate set with alge-
braic efficiently computable matrix entries that can
exactly synthesise either the {e
i
π
8
X
, e
i
π
4
X⊗X
, SWAP}
or {e
i
π
8
X⊗X
, SWAP}. Then, approximating the out-
put probabilities of O(n)-depth circuits of G nearest-
neighbour gates in one dimension up to relative error
1/4 is #P-hard.
Let us highlight that Lemma 8 applies to many well-
studied universal gate sets, including G
BIS
, the ubiqui-
tous Clifford+T [40], Hadamard+controlled-
√
Z [41],
Hadamard+Toffoli [42, 43] and others [44–46]. Inter-
estingly, Lemma 8 holds also for non-universal gate
sets, though the latter may not always anticoncen-
trate. We now prove Lemma 8.
Proof of Lemma 8. We begin by showing that both
given target gate sets can exactly implement sub-
groups of the 2-qubit dense IQP circuits of Ref.
[6]. Specifically, the first gate set gives us the
group G
1
generated by exp
i
π
8
X
i
, exp
i
π
4
X
i
X
j
gates acting on a complete graph, while the second
gives the group generated by arbitrary long range
exp
i
π
8
X
i
X
j
gates. In both cases, long range in-
teractions are obtained via the available SWAPs.
Next, we show that, like the circuits in Ref. [6],
both G
1
and G
2
are universal under post-selection.
Indeed, both can adaptively implement a single-
qubit Hadamard via gate teleportation [47] (see also
[24, 48]), and non-adaptively, if we can post-select.
The claim follows from the universality of known gate
sets [40, 41].
Last, due to Refs. [27, 49], the output proba-
bilities of post-selected universal quantum circuits
are #P-hard to approximate up to multiplicative er-
ror
√
2 (relative error 1/4). The previous fact im-
plies that this holds for the dense IQP circuits in
G
1
and G
2
. Furthermore, n-qubit dense IQP cir-
cuit can be exactly implemented in O(n) depth on a
1D nearest-neighbour architecture using SWAP gates
[10, Lemma 6]. It follows that the output probabilities
of linear-depth circuits in G
1
or G
2
are #P-hard to ap-
proximate. This readily extends to any circuit family
that can exactly synthesise either of the former, since
this process only introduces a constant depth over-
head.
We do not know whether Lemma 8 extends to ar-
bitrary gate sets since applying some Solovay-Kitaev
type gate synthesis algorithms [41, 50, 51] should in-
troduce a polynomial overhead factor in depth. This
is because due to Chernoff-Hoeffding’s bound #P-
hard-to-approximate quantum probabilities need to
be (at least) super-polynomially small, for other-
wise they could be inferred in quantum polynomial
time by mere sampling, which is not believed possi-
ble [52, 53]. To approximate such small probabili-
ties via the Solovay-Kitaev algorithm requires Ω(n
α
)
overhead for some α > 0 assuming the counting expo-
nential time hypothesis [54]. These issues are closely
related to the open question of whether or not the
power of post-selected quantum circuits is gate set
independent given some
˜
O(n
α
) depth bound [26].
Commuting circuits. As a second example, we
consider circuits of diagonal unitaries composed of
controlled-phase type one- and two-qubit gates of the
form diag(1, 1, 1, e
iφ
), and an input state |+i
⊗n
. By
the result of Ref. [21] this gate set yields a state
2-design if the phases are picked from discrete sets
({0, π} for the two-qubit gates, and {0, 2π/3, 4π/3}
for the single qubit gates), and thus satisfies anticon-
centration in the sense of Eq. 3 (i). Adding the S-
gate to the gate set and measuring all qubits in the
X-basis we obtain postF = postBQP by Refs. [6, 27]
Accepted in Quantum 2018-05-09, click title to verify 6
Circuit family Input state (State) 2-design Worst-case hardness Average-case conjecture in
F |ψ
0
i property (postF = postBQP) terms of universal quantity
G
BIS
|0i
⊗n
[23] [8, 40] Ising part. func./Jones polyn.
Diagonal unitaries |+i
⊗n
[21] [26, 27] Ising partition function
Clifford circuits (T |0i)
⊗n
[33] [20] Ising partition function
Table 1: Examples of random circuit families that exhibit a provable quantum speedup up to total-variation distance errors.
as IQP circuits are an instance of diagonal unitaries
(ii). Here, we have used the fact that adding the S-
gate and post-selection gives us access to the universal
gate set Clifford + π/12 [55, 56]. Again, the average-
case conjecture can be phrased in terms of an Ising
partition function (iii). Last, the circuits can be im-
plemented in linear depth if either long-range interac-
tions or nearest-neighbour SWAPs are allowed [10].
Clifford circuits with product-state inputs. A
similar argument can be applied to Clifford circuits
which are known to be an exact 2-design [33, 57] ap-
plied to magic input states. By the result of Ref. [58]
an arbitrary element of the Clifford group in 2
n
di-
mensions can be decomposed into O(n
3
) elementary
Clifford gates. The result of Ref. [57] even achieves
an exact 2-design using only quasi-linearly many one-
and two-qubit Clifford gates. The postF =postBQP
for this case is due to Ref. [20]. We summarise these
examples in Table 1.
4 Anticoncentration of quenched
many-body dynamics
In this section, we investigate anticoncentration of
a particular type of quantum simulation scheme ex-
hibiting a quantum speedup based on the architec-
ture recently introduced in Ref. [10] (specifically, ar-
chitectures I-II therein). These implement quenched
(constant-time) dynamical evolutions [59, 60] under
many-body Ising Hamiltonians on the square lattice
whose graph we denote by L = (V, E). More specifi-
cally, we consider a particular variant of such a setting
and prove both anticoncentration for its output dis-
tribution and the hardness of strongly classically sim-
ulating it. In virtue of the Stockmeyer-type argument
presented in Sec. 2 this gives rise to a new quantum
speedup result for this architecture.
4.1 A new quantum quench architecture
Let us start by reviewing the idea of the quench archi-
tectures introduced in Ref. [10]. There, the computa-
tion in the circuit model amounts to, first, preparing
a product state vector |ψ
β
i =
N
i∈V
(|0i+ e
iβ
i
|1i)/
√
2
with β
i
chosen randomly from a finite set of an-
gles; second, implementing a constant-time evolution
U
:
= e
−iH
under a nearest-neighbour translation-
invariant Ising Hamiltonian
H :=
X
(i,j)∈E
J
i,j
Z
i
Z
j
−
X
i∈V
h
i
Z
i
, (9)
and, third, measuring all qubits in the X basis. Ref.
[10] proved that quantum simulations of this form
cannot be efficiently classically sampled from up to
constant total-variation distance assuming variants of
the average-case and anticoncentration conjecture. As
supporting evidence for the anticoncentration conjec-
ture, Ref. [10] built a link to the anticoncentration
of certain families of universal random circuits and
provided numerical data.
We note that these architectures are closely related
to that of Gao et al. [9]. The similarities and differ-
ences are spelled out in Ref. [10].
We now introduce a new variant of such a quan-
tum quench architecture, named Q
ac
and illustrated
in Fig. 2 that produces provably hard-to-approximate
anticoncentrated distributions which cannot be classi-
cally sampled from if an average-case conjecture holds
and the Polynomial Hierarchy does not collapse. The
architecture picks a uniformly-random input prod-
uct state from a finite family S
ac
= {|ψ
β
i}
β
and
lets it evolve under a nearest-neighbour translation-
invariant Hamiltonian H
ac
(defined below).
Specifically, the architecture uses n(m) := m(2m +
1) qubits, arranged in an m-row (2m + 1)-column
square lattice. Boundary qubits on even-rows are ini-
tialised on |0i or |1i uniformly at random. The re-
maining ones are divided in two groups, named “blue”
and “yellow”, using a lattice 2-colouring that places no
blue qubit on the top-left and top-right columns. Blue
qubits are initialised on (|0i+|1i)/
√
2; yellow ones on
e
−ik
i
πZ
i
/8
|+i with uniformly-random k
i
∈ {0, 1, 2, 3}.
Next, the prepared state evolves under a
translation-invariant Ising Hamiltonian H
ac
. Letting
[i, j] denote the qubit on the i-th row and j-th col-
umn lattice (in left-to-right top-to-bottom order), the
latter reads
H
ac
=
X
i≤k, j≤l
([i,j],[k,l])∈E
π
4
δ
k,l
i,j
Z
[i,j]
Z
[k,l]
−
X
v∈V
π
4
deg
I
(v)Z
v
,
(10)
δ
k,l
i,j
:=
0 if (i 6= k) ∧ (j = 0 mod 4) ∧ ([i, j] is blue),
0 if (i 6= k) ∧ (j = 2 mod 4) ∧ ([i, j] is yellow),
1 otherwise.
Accepted in Quantum 2018-05-09, click title to verify 7
Figure 2: Quantum quench architecture. Circles denote
qubits, lines denote interactions. Blue sites are initialised
on |+i; pink ones on |0i or |1i at random; yellow ones on
e
−ik
i
πZ/8
|+i with random k
i
∈ {0, 1, 2, 3}. The Hamilto-
nian evolution (10) implements CZ gates on connected qubit
pairs. Qubits are measured in the X basis.
.
Above, δ
k,l
i,j
is the indicator function of the edge set
E
I
of a (4,2)-periodic interaction sub-lattice I =
(V, E
I
) ⊂ L (Fig. 2) and deg
I
(v) is the degree of
v ∈ V in I. It is easily seen that I is a brick-
work pattern of 2-square-cells with closed boundaries
(Fig. 2). The net effect of the dynamics is to imple-
ment a controlled-Z gate on every pair of neighbouring
qubits in I before all qubits are measured in the X
basis.
In what follows the central quantity will be the
probability distribution defined by the probabilities
q
ac
(x, β)
:
=
hx|H
⊗n
e
−iH
ac
|ψ
β
i
2
/|S
ac
| (11)
of measuring the outcomes x after picking |ψ
β
i and
evolving it under H
ac
for unit time. We also let x
R
be
x’s sub-string of rightmost column’s outcomes in the
square lattice, and x
L
:= x − x
R
be its set-theoretic
complement.
4.2 Anticoncentration and classical hardness
of Q
ac
Our second main result from which anticoncentra-
tion and classical hardness follow, shows that this
quantum quench architecture is closely related to the
“dense” IQP circuit family of Ref. [6] consisting of cir-
cuits of e
iθ
i
πX
i
, e
iθ
i,j
πX
i
X
j
gates acting at arbitrary
pairs of qubits, with θ
i
, θ
i,j
chosen fully and uniformly
at random from {kπ/8 : k ∈ {0, . . . , 7}}. Dense IQP
circuits form a commutative finite group under mul-
tiplication G
IQP
with Haar measure µ
IQP
. The im-
plementation of a dense IQP circuit proposed in [6]
requires a fully-connected architecture, and the enact-
ment of Θ(m
2
) long-range gates for m-qubits in aver-
age. Here, we show that our constant-depth nearest-
neighbour architecture Q
ac
implements exact sam-
pling over dense IQP circuits with a linear (2m + 1)
overhead-factor in qubit number.
Theorem 9 (Quantum quench architecture). For
n(m) = m(2m + 1) qubits, the output probability dis-
tribution q
ac
of architecture Q
ac
fulfils
q
ac
(x
L
|β) =
1
2
n−m
, q
ac
(x
R
|x
L
, β) = |hx
R
|V
x
L
,β
|0i|
2
for some x
L
, β-dependent m-qubit dense IQP cir-
cuit V
x
L
,β
∈ G
IQP
such that Pr
(x
L
,β)∼q
ac
(V
x
L
,β
) =
µ
IQP
(V
x
L
,β
).
Before we turn to proving this theorem, let us state
the two Corollaries important for us, namely, that
both the anticoncentration result and the simulability
result proven for dense IQP circuits in Ref. [6] carry
over to the quench architecture Q
ac
.
Corollary 10 (Anticoncentration from quenched dy-
namics). The distribution q
ac
(11) of the quench
architecture Q
ac
described below satisfies q
ac
(β) =
1/|S
ac
| and
Pr
β∼q
ac
q
ac
(x|β) ≥
1
2N
≥
1
12
. (12)
Corollary 11 (Hardness of approximation). Approx-
imating either q
ac
(x, β) or q
ac
(x|β) up to relative error
1/4 is #P-hard.
Corollary 10 proves anticoncentration for Q
ac
’s out-
put probabilities, while Corollary 11 shows that the
latter are #P-hard to approximate. As an application
of these two technical statements, a quantum-speedup
result follows from a Stockmeyer argument. This re-
sult is based on the average case conjecture C1*:
C1* Let H
v
:
= H +
P
i∈V
v
i
Z
i
be the random Ising
model derived from (9) by adding uniformly ran-
dom on-site fields v
i
Z
i
with random angles v
i
=
(β
i
+ x
i
)/2, where β
i
are the phases of the in-
put state |ψ
β
i and x
i
are the measurement out-
comes. The conjecture states that, if its #P-hard
to approximate the imaginary temperature parti-
tion function tr [exp(iH
v
)] up to a constant rela-
tive error, then the same problem is #P-hard for a
constant fraction of the instances—intuitively, be-
cause random Ising models have no visible struc-
ture making this problem easier in average (see
also Refs. [6–8]).
Corollary 12 (Intractability of classical sampling).
If conjectures C1-C1* hold, then a classical computer
cannot sample from the outcome distribution of archi-
tecture Q
ac
up to `
1
-error 1/192 in time O(poly(n)).
The significance of Corollary 12 is that, as shown
below, architecture Q
ac
defines a resource-wise plausi-
ble, certifiable experiment for demonstrating a quan-
tum speedup with experimental demands competitive
to those in Ref. [10]. However, unlike the latter, the
speedup of Q
ac
relies only on a natural average-case
hardness conjecture about Ising models and a Polyno-
mial Hierarchy collapse. Hence, we believe this corol-
lary should help in the analysis of quantum speedups
in near-term quantum devices.
4.3 Proof of Theorem 9 and its Corollaries
Proof of Theorem 9. We make use of two circuit gad-
gets, named “odd” and “even”, illustrated next,
Accepted in Quantum 2018-05-09, click title to verify 8
Odd gadget Even gadget
which represent quantum circuit identities modulo
terminal Pauli operator corrections. Vertical links
represent CZ gates. Crossing qubit lines perform
SWAP gates. Blue “H” blocks implement Hadamard
gates preceded by uniformly-random Z
x
i
, x ∈ {0, 1},
single-qubit gates. Yellow “H” blocks, H
i
e
−iπkZ
i
/8
Z
x
0
i
gates with uniformly-random 0 ≤ k ≤ 3, x
0
∈ {0, 1},
where e
−ikπZ
i
/8
Z
x
0
i
is a uniformly-random power of
e
−iπZ
i
/8
up to a global phase since the latter has order
8 and Z
i
∝ e
−i4πZ
i
/8
. Analogously, yellow “Z” (resp.
“ZX” blocks) perform uniformly-random powers of
e
−i
π
8
Z
i
(resp. e
−i
π
8
Z
i
X
i+1
). The correctness of the iden-
tities is easily verified using the stabiliser formalism
[51]. Pauli corrections correspond to “by-product” Zs
in blue blocks, which we can propagate to the end of
the circuit by flipping some of the e
−ikπZ
i
/8
gates’ an-
gles in yellow blocks, which leaves them invariant.
We next show that the computation carried out
by Q
ac
is equivalent to a 1D circuit of our odd and
even gadgets composed in a brickwork layout. We
begin by reminding the reader of the properties of
X-teleportation circuits [47], namely, that given an
(r +1)-qubit state vector |ψi|+i, the effect of measur-
ing the i-th qubit of |ψi in the D
†
XD basis after en-
tangling it with |+i via a CZ gate is, first, to produce
a uniformly-random bit x; second, teleport the value
of the former qubit onto the latter; and, third, imple-
ment a single-qubit gate H
r+1
Z
x
r+1
D
r+1
on site r + 1.
Next, note that pink sites in Fig. 2 can be eliminated
from the lattice by introducing uniformly-random si-
multaneous Z
i
rotations on their neighbouring qubits.
Combining these three facts and using induction, we
obtain that Q
ac
can be simulated exactly by an al-
gorithm that first generates a uniformly-random clas-
sical bit-string x
L
∈ {0, 1}
n−m
and then draws x
R
from the output of the following network of random
1D nearest-neighbour quantum gates,
which we draw for m = 4 and explicate next. The
“bulk” of this network (white area) contains an m-
layered brickwork layout of odd and even gadgets
with boundaries connected by pairs of blue and yellow
blocks. Blue/yellow blocks act as before. n−m out of
these are placed in the bulk; their associated random
Z
x
L
i
i
gates originally correspond to the by-product
rotations introduced via X-teleportation, and are ac-
tivated by the algorithm depending distinct bits val-
ues of x
L
. Qubits are initialised on |0i, followed by a
“blue” Hadamard (resp. a “pink” uniformly random
{I
i
, X
i
}) gate on odd (resp. even) rows. Even qubit
lines are measured on the Z basis (preceded by “pink”
identity gates in the figure); and odd ones on the X
basis preceded by a e
i
πk
8
Z
i
gate. Straight-line random
blocks are mutually uncorrelated (terminal “dashed”
ones are not). Dashed CZs are “gauge gates” that
can be included or removed from by inserting CNOT
gates at predetermined input/output locations and
reinterpreting the measurement outcomes. As before,
we assume H block’s by-product Pauli operators are
w.l.o.g. conjugated to the end.
Next, we apply our odd/even gadgets to the bulk
of our network to rewrite the full quantum circuit in
an m-layered brickwork normal form
where odd layers execute random gates of the form
Y
odd i
h
H
i
H
i+1
SWAP
i,i+1
e
−i
πa
i
8
Z
i
X
i+1
e
−i
πb
i
8
Z
i
i
,
with a
i
, b
i
∈Z
8
, followed by random-gate even layers
of the form
Y
even i
h
e
−i
πd
i
8
X
i
SWAP
i,i+1
e
−i
πc
i
8
Z
i
X
i+1
H
i−1
H
i
i
,
where c
i
, d
i
∈Z
8
and we define H
j
= Z
j
= X
j
=
SWAP
k,k+1
= 1 for j, k < 1 and j, k + 1 > n. Trailing
Hadamard gates in odd layers cancel out with their
counterparts in even-layers. By a parity-counting ar-
gument, it follows that SWAP gates move qubits ini-
tially on odd (resp. even) rows travel down (resp. up)
the circuit; the latter first undergo Z-type (resp. X-
type) interactions, meet an odd number of H gates
when they reach the bottom (resp. top) qubit line,
and then undergo the opposite process. By propagat-
ing all Hadamards in the full circuit to the measure-
ment step, we are left only with a bulk of n brickwork
layers of uniformly-random e
−i
πa
i
8
X
i
X
i+1
, e
−i
πb
i
8
X
i
and
SWAPs, and some additional IQP gates and random
Pauli by-products in the preparation/measurement
steps. It was shown in Ref. [10] that all pairs of
qubits in a bulk circuit of the given form meet exactly
once, hence, the network implements exact sampling
over dense IQP circuits (crucially, due to their lack
of temporal structure). Furthermore the remaining
gates are either also dense IQP gates, which leave
the Haar measure µ
IQP
invariant, or terminal Pauli
Z gates, which do not affect the final measurement
statistics.
Accepted in Quantum 2018-05-09, click title to verify 9
We now exploit the mapping in Lemma 9 between
Q
ac
’s and IQP circuits’ output statistics to prove
Corollaries 10 and 12.
Proof of Corollary 10. Recall that m-qubit dense
IQP circuits fulfil
Pr
V ∼µ
IQP
|hx|V |0i|
2
≥
1
2
m+1
≥
1
12
, ∀x∈{0, 1}
m
.
(13)
Since V
x
L
,β
is drawn according to µ
IQP
in Lemma 9,
we get
Pr
(x
L
,β)∼q
ac
q
ac
(x
R
|x
L
, β) ≥
1
2
m+1
≥
1
12
. (14)
Since q
ac
(x
L
|β) = 1/2
n−m
, we derive (12). Last,
q
ac
(β) = 1/|S
ac
| by definition.
Proof of Corollary 12. The proof of Corollary 12 is
analogous to those of Ref. [10, Theorem 1] and Ref. [6,
Theorem 7], noting that X-measurements on qubits
prepared in states |0i or |1i in Q
ac
are equivalent to
the Z-measurements on qubits prepared in the |+i-
state of architecture III in Ref. [10]. Then, the same
argument as in Ref. [10] shows that the output proba-
bilities q
ac
(x
L
, x
R
|β) are proportional to an Ising par-
tition function as in conjecture C1*.
The only remaining difference with the proof of
Theorem 1 in Ref. [10] is that we employ a different
anticoncentration bound. Here, we use Eq. (12) of
Theorem 10, which is the same bound used in Ref. [6,
Theorem 7]. As a result, we obtain a bound of 1/192
for the allowed sampling error identical to that of The-
orem 7 in [6].
5 Implications and discussion
We now discuss the implications of our two main an-
ticoncentration results and discuss possible improve-
ments in both settings.
First, we conjecture that the linear-circuit-depth
scaling in our anticoncentration result for universal
random circuits in one dimension is optimal. Indeed,
on the one hand, this result is in agreement with
the intuition that anticoncentration arises as soon as
correlations have spread across the entire system, a
process that occurs ballistically and thus scales with
the diameter of the system. On the other hand, for
one-dimensional random universal circuits to be in-
tractable classically, the depth needs to be polyno-
mial in the number of qubits. Hence, our result only
leaves room for a sub-linear improvement, since for
circuits of poly-logarithmic depth there is a quasi-
polynomial time classical simulation based on matrix-
product states. However, as is argued in Refs. [7, 18],
it would seem counter-intuitive that one can achieve
sub-linear depth. Indeed, standard tensor network
contraction techniques would allow any output prob-
abilities of a circuit of depth t in one dimension to be
computed in a time scaling as O(2
t
) [61]. Hence, if
the depth t as a function of n required for the classical
hardness of generic circuits could be brought down to
sub-linear, this would violate the counting exponen-
tial time hypothesis [62] and is therefore considered
highly unlikely.
Second, we highlight that the anticoncentration re-
sult for the two-dimensional quenched-dynamics set-
ting provably achieves the optimal asymptotic scaling
of depth, namely, constant in the number of qubits.
This is due to the highly specific structure of the
dynamical evolution and not believed to hold in an
approach that relies on sampling random gates such
as Refs. [7, 8, 63]. Indeed, in such settings a scal-
ing as Θ(
√
n) is expected to be necessary and suffi-
cient for an average-case hardness result and hence
for anticoncentration. Again, this is due to the bal-
listic spreading of correlations in the system. Last,
the discussed connections between 2D quenches and
one-dimensional random circuits lead us to conjec-
ture that the required lattice width in our result,
m × (2m + 1) ∈ O(m
2
), is also asymptotically op-
timal.
6 Conclusion
In summary, we have presented two anticoncentra-
tion theorems for quantum speedup schemes that are
based on simple nearest-neighbour interactions and
hence realisable with plausible physical architectures,
filling a significant gap in the literature. We contrast
the anticoncentration property of random circuits in
one dimension that are sampled from a universal gate
set with anticoncentration of the output distribu-
tion of quenched constant-time evolution of product
states under translation-invariant nearest-neighbour
Ising models. In the former setting the depth required
to achieve classical hardness and at the same time an-
ticoncentration of the output distribution scales with
the diameter of the system size. In the latter set-
ting a similar hardness and anticoncentration result
is achieved after evolution for constant time. We ar-
gue that both results are optimal for the respective
setting. We hope that this kind of endeavour sig-
nificantly contributes to the quest of realising quan-
tum devices that outperform classical supercomput-
ers, equipped with strong complexity-theoretic claims.
7 Acknowledgements
We are grateful to Richard Kueng for pointing us
to the application of our result to diagonal unitary
circuits. Moreover, we thank Richard Kueng and
Emilio Onorati for insightful discussions and com-
ments on the draft, Andreas Elben for discussions on
Haar random matrices, Tomoyuki Morimae for com-
ments on the draft, and the EU Horizon 2020 (640800
AQuS), the ERC (TAQ), the Templeton Foundation,
Accepted in Quantum 2018-05-09, click title to verify 10
the DFG (CRC 183, EI 519/7-1, EI 519/14-1), and the
Alexander-von-Humboldt Foundation for support.
References
[1] J. Preskill, Bull. Am. Phys. Soc. 58 (2013),
arXiv:1203.5813 .
[2] S. Trotzky, Y.-A. Chen, A. Flesch, I. P. McCul-
loch, U. Schollwöck, J. Eisert, and I. Bloch, Na-
ture Phys. 8, 325 (2012), arXiv:1101.2659 .
[3] J.-Y. Choi, S. Hild, J. Zeiher, P. Schauß,
A. Rubio-Abadal, T. Yefsah, V. Khemani, D. A.
Huse, I. Bloch, and C. Gross, Science 352, 1547
(2016), arXiv:1604.04178 .
[4] S. Braun, M. Friesdorf, S. S. Hodgman,
M. Schreiber, J. P. Ronzheimer, A. Riera, M. del
Rey, I. Bloch, J. Eisert, and U. Schneider, Proc.
Natl. Ac. Sc. 112, 3641 (2015), arXiv:1403.7199
.
[5] S. Aaronson and A. Arkhipov, Th. Comp. 9, 143
(2013), arXiv:1011.3245 .
[6] M. J. Bremner, A. Montanaro, and D. J.
Shepherd, Phys. Rev. Lett. 117, 080501 (2016),
arXiv:1504.07999 .
[7] M. J. Bremner, A. Montanaro, and D. J. Shep-
herd, Quantum 1, 8 (2017).
[8] S. Boixo, S. V. Isakov, V. N. Smelyanskiy,
R. Babbush, N. Ding, Z. Jiang, M. J. Bremner,
J. M. Martinis, and H. Neven, Nature Physics ,
1 (2018), arXiv:1608.00263 .
[9] X. Gao, S.-T. Wang, and L.-M. Duan, Phys.
Rev. Lett. 118, 040502 (2017), arXiv:1607.04947
.
[10] J. Bermejo-Vega, D. Hangleiter, M. Schwarz,
R. Raussendorf, and J. Eisert, Phys. Rev. X 8,
021010 (2018), arXiv:1703.00466 .
[11] T. Morimae, Phys. Rev. A 96, 040302 (2017),
arXiv:1704.03640 .
[12] J. Miller, S. Sanders, and A. Miyake, Phys. Rev.
A 96, 062320 (2017), arXiv:1703.11002 .
[13] C. Gogolin, M. Kliesch, L. Aolita, and J. Eisert,
“Boson sampling in the light of sample complex-
ity,” arXiv:1306.3995 .
[14] S. Aaronson and A. Arkhipov, “BosonSampling
is far from uniform,” arXiv:1309.7460 .
[15] D. Hangleiter, M. Kliesch, M. Schwarz, and
J. Eisert, Quantum Sci. Technol. 2, 015004
(2017), arXiv:1602.00703 .
[16] T. Kapourniotis and A. Datta, (2017),
arXiv:1703.09568 .
[17] L. Stockmeyer, Proceedings of the Fifteenth An-
nual ACM Symposium on Theory of Computing,
STOC ’83, 118 (1983).
[18] A. P. Lund, M. J. Bremner, and T. C. Ralph,
npj Quant. Inf. 3, 15 (2017), arXiv:1702.03061 .
[19] M. Schwarz and M. V. den Nest, (2013),
arXiv:1310.6749 .
[20] R. Jozsa and M. V. d. Nest, Quant. Inf. Comp
14, 0633–0648 (2014), arXiv:1305.6190 .
[21] Y. Nakata, M. Koashi, and M. Murao, New J.
Phys. 16, 053043 (2014), arXiv:1311.1128 .
[22] D. Gross, K. Audenaert, and J. Eisert, J.
Math. Phys. 48, 052104 (2007), arXiv:quant-
ph/0611002 .
[23] F. G. S. L. Brandão, A. W. Harrow, and
M. Horodecki, Commun. Math. Phys. 346, 397
(2016).
[24] M. J. Bremner, R. Jozsa, and D. J.
Shepherd, Proc. Roy. Soc. 467, 2126 (2010),
arXiv:1005.1407 .
[25] B. M. Terhal and D. P. DiVincenzo, Quant. Inf.
Comp. 4, 134 (2004), arXiv:quant-ph/0205133 .
[26] G. Kuperberg, Theory of Computing 11, 183
(2015).
[27] K. Fujii and T. Morimae, New J. Phys. 19,
033003 (2017), arXiv:1311.2128 .
[28] A. Bouland, B. Fefferman, C. Nirkhe, and
U. Vazirani, (2018), arXiv:1803.04402 .
[29] R. L. Mann and M. J. Bremner,
arXiv:1711.00686 .
[30] S. Aaronson, “P6=NP?” in Open problems in
mathematics (Springer, 2016).
[31] L. Fortnow, in Proceedings of the Thirty-seventh
Annual ACM Symposium on Theory of Comput-
ing, STOC ’05 (ACM, 2005).
[32] R. M. Karp and R. J. Lipton, in Proceedings of
the Twelfth Annual ACM Symposium on Theory
of Computing, STOC ’80 (1980).
[33] C. Dankert, R. Cleve, J. Emerson, and E. Livine,
Phys. Rev. A 80, 012304 (2009), arXiv:quant-
ph/0606161 .
[34] E. Onorati, O. Buerschaper, M. Kliesch,
W. Brown, A. H. Werner, and J. Eis-
ert, Commun. Math. Phys. 355, 905 (2017),
arXiv:1606.01914 .
[35] A. W. Harrow and R. A. Low, Commun. Math.
Phys. 291, 257 (2009), arXiv:0802.1919 .
[36] H. Zhu, R. Kueng, M. Grassl, and D. Gross,
(2016), arXiv:1609.08172 .
[37] J. Emerson, Y. S. Weinstein, M. Saraceno,
S. Lloyd, and D. G. Cory, Science 302, 2098
(2003).
[38] W. G. Brown, Y. S. Weinstein, and L. Viola,
Phys. Rev. A 77, 040303 (2008), arXiv:0802.2675
.
[39] C. Neill, P. Roushan, K. Kechedzhi, S. Boixo,
S. V. Isakov, V. Smelyanskiy, R. Barends,
B. Burkett, Y. Chen, and Z. Chen, (2017),
arXiv:1709.06678 .
[40] P. O. Boykin, T. Mor, M. Pulver, V. Roychowd-
hury, and F. Vatan, Inf. Proc. Lett. 75, 101
(2000), arXiv:quant-ph/9906054 .
[41] A. Kitaev, A. Shen, and M. Vyalyi, Classical
and Quantum Computation, Graduate studies in
Accepted in Quantum 2018-05-09, click title to verify 11
mathematics (American Mathematical Society,
2002).
[42] Y. Shi, Quant. Inf. Comp. 3, 84 (2003),
arXiv:quant-ph/0205115 .
[43] A. Paetznick and B. W. Reichardt, Phys. Rev.
Lett. 111, 090505 (2013), arXiv:1304.3709 .
[44] P. W. Shor, in Proc. of 37th Conf. Found. Comp.
Sci. (1996) pp. 56–65, arXiv:quant-ph/9605011 .
[45] E. Knill, R. Laflamme, and W. Zurek, (1996),
arXiv:quant-ph/9610011 .
[46] E. Knill, R. Laflamme, and W. H. Zurek, Proc.
Roy. Soc. A 454, 365 (1998).
[47] D. Gottesman and I. L. Chuang, Nature 402, 390
(1999).
[48] R. Raussendorf, D. E. Browne, and H. J. Briegel,
Phys. Rev. A 68, 022312 (2003), arXiv:quant-
ph/0301052 .
[49] L. A. Goldberg and H. Guo, (2014),
arXiv:1409.5627 .
[50] A. Y. Kitaev, Russ. Math. Surv. 52, 1191 (1997).
[51] M. A. Nielsen and I. L. Chuang, Quantum com-
putation and quantum information, Cambridge
Series on Information and the Natural Sciences
(Cambridge University Press, 2000).
[52] C. H. Bennett, E. Bernstein, G. Brassard, and
U. Vazirani, SIAM J. Comp. 26, 1510 (1997),
arXiv:quant-ph/9701001 .
[53] S. Aaronson, Proc. Roy. Soc. A 461, 2063 (2005),
arXiv:quant-ph/0412187 .
[54] H. Dell, T. Husfeldt, D. Marx, N. Taslaman, and
M. Wahlén, ACM Trans. Algorithms 10, 21:1
(2014).
[55] S. X. Cui and Z. Wang, J. Math. Phys. 56,
032202 (2015).
[56] A. Bocharov, M. Roetteler, and K. M. Svore,
Phys. Rev. A 91, 052317 (2015), arXiv:1409.3552
.
[57] R. Cleve, D. Leung, L. Liu, and C. Wang, Quant.
Inf. Comp. 16, 0721 (2016), arXiv:1501.04592 .
[58] R. Koenig and J. A. Smolin, J. Math. Phys. 55,
122202 (2014), arXiv:1406.2170 .
[59] J. Eisert, M. Friesdorf, and C. Gogolin, Nature
Phys 11, 124 (2015), arXiv:1408.5148 .
[60] A. Polkovnikov, K. Sengupta, A. Silva, and
M. Vengalattore, Rev. Mod. Phys. 83, 863
(2011), arXiv:1007.5331 .
[61] R. Jozsa, (2006), arXiv:quant-ph/0603163 .
[62] R. Impagliazzo and R. Paturi, in Proc. XIV IEEE
Conf. Comp. Compl. (1999) pp. 237–240.
[63] S. Aaronson and L. Chen, (2016),
arXiv:1612.05903 .
[64] M. Ozols, How to generate a random unitary ma-
trix (Mar, 2009).
[65] F. Mezzadri, (2006), arXiv:math-ph/0609050 .
[66] Y. S. Weinstein and C. S. Hellberg, Phys. Rev.
A 72, 022331 (2005).
[67] K. Zyczkowski and M. Kus, J. Phys. A 27, 4235
(1994).
[68] M. Pozniak, K. Zyczkowski, and M. Kus,
J. Phys. A 31, 1059 (1998), arXiv:chao-
dyn/9707006 .
[69] F. Haake, Quantum signatures of chaos, Springer
Series in Synergetics, Vol. 54 (Springer Berlin
Heidelberg, Berlin, Heidelberg, 2010).
A Some facts on random matrix the-
ory, the Haar measure, and unitary de-
signs
A.1 The Haar measure
In this appendix, we give a precise definition of the
Haar measure on the unitary group. To do so, let us
first define a Radon measure.
Definition 13 (Radon measure). Let (X, T ) be a
topological space and B its Borel algebra. A Radon
measure on X is a measure µ : B → [0, +∞] such
that
i for any compact set K ⊂ X, µ(K) < ∞
ii for any B ∈ B, µ(B) = inf{µ(V ) : B ⊂
V and V open}
iii for any open set V ⊂ X, µ(V ) = sup{µ(K) :
K ⊂ V and K compact}.
Definition 14 (Haar measure on the unitary group).
The Haar measure is the unique (up to a strictly
positive scalar factor) Radon measure which is non-
zero on non-empty open sets and is left- and right-
translation invariant, i.e.
µ
Haar
(U) > 0 for any non-empty open set U ⊂ U
(15)
and
µ
Haar
(B) = µ
Haar
(uB) = µ
Haar
(Bu) (16)
for any u ∈ U and Borel set B of U, where the left-
and right-translate of B with respect to u is given by
uB = {u b : b ∈ B} and Bu = {b u : b ∈ B}.
(17)
A.2 Random matrix ensembles
For the calculation of the distribution matrix elements
of Haar-random unitaries it is instructive to introduce
a few important ensembles of random matrices. In
this appendix we do so from a rather hands-on per-
spective.
• G(N) (Ginibre Ensemble): The set of matrices Z
with complex Gaussian entries.
G(N) is characterised by the measure dµ
G
(Z)
:
=
π
−N
2
exp(−tr(Z
†
Z)dZ, i.e., each individual en-
try z
i,j
is distributed as exp(−|z
i,j
|
2
)/π.
Accepted in Quantum 2018-05-09, click title to verify 12
• GUE(N) (Gaussian Unitary Ensemble): The set
of N ×N Hermitian matrices with complex Gaus-
sian entries, i.e., H ∈ GUE ⇔ H = D + R + R
†
,
where D is a diagonal matrix with real Gaussian
entries and R is an upper triangular matrix with
complex Gaussian entries.
GUE(N) is characterised by the measure
dµ
GUE
= Z
GUE(N)
−1
exp(−Ntr(H
2
)/2)dH on
the space of Hermitian matrices.
• CUE(N) (Circular Unitary Ensemble): The set
of Haar-random N × N unitary matrices.
CUE(N) is characterised by the Haar measure
dµ
Haar
.
All of dµ
GUE
, dµ
G
, and dµ
Haar
are left- and right
invariant under the action of U(N). There are two
ways of constructing Haar-random matrices.
1. Draw a Gaussian matrix Z ∈ G(N), and perform
the unique QR decomposition such that Z = QR,
with an orthogonal matrix Q and R is required
to have positive diagonal entries. Setting U = Q,
yields a Haar-random unitary [64, 65].
2. Draw a GUE matrix Z ∈ GUE. Since Z is
Hermitian, the eigenvectors v
i
, i = 1, . . . , N of
Z are orthonormal. Multiplying each eigen-
vector v
i
by a random phase e
φ
i
we can con-
struct a Haar-random unitary matrix U =
(e
φ
1
v
1
e
φ
2
v
2
··· e
φ
n
v
N
) writing those eigenvec-
tors into the columns of U [66].
A.3 Unitary designs
It is a simple exercise to show that if µ is a unitary
k-design, all up to the k
th
moments of µ equal the
moments of the Haar measure.
Lemma 15 (k − 1 designs from k designs). Let µ
be a distribution on the unitary group U(N) that is
an exact unitary k-design. Then µ is also a (k − 1)-
design.
Proof . Let µ be a unitary k design. That means that
it holds
E
µ
U
⊗k
X(U
†
)
⊗k
= E
Haar
U
⊗k
X(U
†
)
⊗k
(18)
for all operators X acting on L(H
⊗k
). Choose
X = Y ⊗ id with Y being an arbitrary operator on
L(H
⊗k−1
). Then
E
µ
U
⊗k−1
Y (U
†
)
⊗k−1
= E
µ
U
⊗k
X(U
†
)
⊗k
(19)
i.e., µ is a unitary (k − 1)-design.
Corollary 16 (Approximate k − 1 designs from ap-
proximate k designs). Let µ be an (additive or rela-
tive) approximate unitary k-design. Then µ is also an
approximate unitary (k −1)-design, i.e.,
kM
k
µ
− M
k
Haar
k
≤ ⇒ kM
k−1
µ
− M
k−1
Haar
k
≤ (20)
and likewise for relative errors.
B Matrix elements of Haar-random
unitaries
Let us now derive the distribution of the amplitudes
|ha|U|bi|
2
of the matrix elements a Haar-random uni-
tary U [66–69]. To this end we apply knowledge about
the distribution of entries of eigenvectors of GUE ma-
trices and their relation to Haar-random unitaries (see
App. A.2). We follow Ref. [69], Chapter 4.9.
The eigenvectors v
i
of a given operator H ∈
GUE(N) have N complex components c
k
and unit
norm kv
i
k
2
= 1. Since every eigenvector can be uni-
tarily transformed into an arbitrary vector of unit
norm, the only invariant characteristic of those eigen-
vectors is the norm itself. Thus, the joint probability
for its components {c
k
} must read
P
GUE
({c
k
}) = const · δ
1 −
N
X
k=1
|c
k
|
2
!
, (21)
where the constant is fixed by normalisation.
Assuming real entries for now (we can always go to complex ones by doubling N ) we can calculate that
normalisation by evaluating the integral on the N-dimensional unit sphere
const =
Z
∞
−∞
N
Y
i=1
dc
i
!
δ
1 −
N
X
k=1
|c
k
|
2
!
(22)
=
Z
dω
N−1
Z
∞
0
dR R
N−1
δ(1 − R
2
) (23)
=
Z
dω
N−1
Z
∞
0
dR R
N−1
1
2R
[δ(1 − R) + δ(1 + R)] (24)
= π
N/2
/Γ(N/2) . (25)
Accepted in Quantum 2018-05-09, click title to verify 13
Similarly, we can calculate the marginal distribution
P
(N,l)
(c
1
, . . . , c
l
) = π
−N/2
Γ(N/2)
Z
∞
−∞
N
Y
i=l+1
dc
i
!
δ
1 −
N
X
k=1
|c
k
|
2
!
(26)
=
Z
dω
N−l−1
Z
∞
0
dR R
N−l−1
δ(1 − R
2
−
l
X
k=1
|c
k
|
2
) (27)
= π
−l/2
Γ(N/2)
Γ((N − l)/2)
1 −
l
X
k=1
|c
k
|
2
!
(N−l−2)/2
. (28)
For the GUE we then obtain the probability density
for the amplitude y = x
2
1
+x
2
2
of a single complex entry
x
1
+ ix
2
of an eigenvector to be the twofold integral
over real and imaginary part
P
GUE
(y) =
Z
dx
1
dx
2
P
(2N,2)
(x
1
, x
2
)δ(y −x
2
1
− x
2
2
)
= (N − 1)(1 − y)
N−2
. (29)
Since the eigenvectors of a GUE matrix are identically
distributed (up to a global phase) as the columns of a
CUE matrix, we obtain the same distribution as (29)
for the amplitudes of the matrix elements of a CUE
matrix [66]. Notably, as N becomes much larger than
1, we obtain
P
Haar
(p) = (N − 1)(1 − p)
N−2
N1
−−−→ N exp(−Np) .
(30)
The first and second moments of P
CUE
are then given
by
E
Haar
[p] =
1
N
, (31)
E
Haar
[p
2
] =
2
N(N + 1)
. (32)
Accepted in Quantum 2018-05-09, click title to verify 14