# Extremal jumps of circuit complexity of unitary evolutions generated by
random Hamiltonians

Marcin Kotowski, Michał Oszmaniec, Michał Horodecki

###### Abstract

We investigate circuit complexity of unitaries generated by time evolution of
randomly chosen strongly interacting Hamiltonians in finite dimensional
Hilbert spaces. Specifically, we focus on two ensembles of random generators –
the so called Gaussian Unitary Ensemble ($\mathrm{GUE}$) and the ensemble of
diagonal Gaussian matrices conjugated by Haar random unitary transformations.
In both scenarios we prove that the complexity of $\exp(-itH)$ exhibits a
surprising behaviour – with high probability it reaches the maximal allowed
value on the same time scale as needed to escape the neighborhood of the
identity consisting of unitaries with trivial (zero) complexity. We
furthermore observe similar behaviour for quantum states originating from time
evolutions generated by above ensembles and for diagonal unitaries generated
from the ensemble of diagonal Gaussian Hamiltonians. To establish these
results we rely heavily on structural properties of the above ensembles (such
as unitary invariance) and concentration of measure techniques. This gives us
a much finer control over the time evolution of complexity compared to
techniques previously employed in this context: high-degree moments and frame
potentials.

##  1 Introduction

Complexity is a central notion of computer science and quantum complexity is
therefore at the heart of quantum computing. Quantum complexity of a unitary
operation is the minimal number of some elementary gates that are needed to
approximate the unitary to some a priori given accuracy. The famous Shor’s
factoring algorithm can be thought as a unitary that enables factoring large
numbers, but has relatively small complexity. A typical Haar random unitary is
actually the opposite – a simple counting argument shows that a randomly
selected unitary has almost maximal complexity. There is a long standing
conjecture due to Brown and Susskind [BS18] that complexity of unitary
evolution $U_{t}=\exp(-iHt)$ generated by chaotic many-body Hamiltonians (such
as the SYK model [BDKP20]) grows linearly with time until exponential time and
after doubly exponential time it undergoes recurrence (i.e. drops down to
zero).

One may ask about the rationale for studying long-time properties of quantum
evolutions, given that the success of quantum computing lies in efficient,
carefully designed quantum algorithms. One reason is that Brown-Susskind
conjecture, if true, implies that a quantum computer cannot efficiently
simulate (via fast-forwarding) long time evolution of states and unitaries
generated by generic quantum many-body evolutions. Another prominent reason
for which actually the Brown-Susskind conjecture was formulated and then
studied for quite some time is its relation to the so called AdS-CFT (Anti-de
Sitter - Conformal Field Theory) correspondence. This conjectured
correspondence relates classical gravity in the bulk with quantum field theory
on the boundary. The so called wormhole growth paradox has been identified
[SS14] (see also [Sus16]), namely wormhole (i.e. a sort of ”bridge” joining
two parts of Penrose diagram for black whole in Anti-de Sitter universe) in
the bulk grows for a long time time, while, equilibration of the quantum field
on boundary is quite fast (logarithmic in black hole entropy). It would thus
seem that the slow growth of the wormhole does not have a counterpart in the
field dynamical behaviour – there, after logarithmic time, nothing in
principle evolves. The idea of [SS14] was, then, that there is still some
quantity that can grow for a long time – complexity. Therefore, since the
evolution of quantum fields at the boundary is believed to be mimicked by
chaotic quantum systems, the paradox could be resolved if such chaotic
evolution would exhibit linear growth of complexity.

For unitary time evolutions _upper bounds_ on the complexity that grow
linearly with time can be obtained from _Hamiltonian simulation_ algorithms
[Llo96, BCK15, LC19] , which work in a multitude of settings including local
and sparse Hamiltonians. However, proving unconditional lower bounds is much
more challenging. In a pioneering work, Nielsen and collaborators [Nie05,
NDGD06] established a connection between complexity and geodesic distance in a
well-defined sub-Riemannian geometry. Unfortunately, this approach cannot be
directly employed to large systems due to the challenging optimization problem
of finding the shortest geodesic. Nevertheless, Nielsen’s geometric method was
applied to compute complexity in free fermionic and bosonic theories in
Refs.[HM18, CEH+19] (see also Ref.[Eis21] which utilized this perspective to
connect exact complexity based on the entangling power of quantum gates).
Additionally, complexity-theoretic conjectures (such as PSPACE $\neq$ BQP) can
be used to demonstrate that the complexity of specific Hamiltonian evolutions
must grow faster than polynomial for exponentially long times, as shown in
Refs. [Aar16, AA17, Sus18, BBa17]. Finally, we note that recently in [JW22]
the authors give explicit constructions of unitaries (corresponding to
Hamiltonian evolutions) which provably have exponential circuit complexity .

Due to immense difficulty of the Brown-Susskind conjecture in its original
formulation, simplified models of evolution were therefore considered. One
idea was to analyse evolution generated by random quantum circuits. These
models were examined in [BaCHJ+21, HFK+21, OHHJ22]. In [BaCHJ+21] growth of
complexity was confirmed, though still sublinear. In [HFK+21] (see also [Li22]
for a simplified proof) linear growth was shown, but the notion of complexity
was not physical – the authors used exact complexity and unfortunately their
methods were so tightly related to that notion that it is not possible to
extend it to cover approximate complexity. Then in [OHHJ22] the physically
sound notion of complexity was used and it was shown that after exponential
time, complexity becomes maximal, and moreover recurrence after double
exponential times was showed.

Another possible simplification is to consider unitary evolutions $\exp(-itH)$
generated by random Hamiltonians $H$. However, the problem is nontrivial
already for the most well studied model of strongly interacting quantum
systems – the so-called Gaussian Unitary Ensemble (GUE) [AGZ09a] Equilibration
properties of such system were examined in [BaiaCanH+12, MRA13, VŽ 12, CDEO08]
and compared with properties many-body chaotic systems in [CHJLY17]. One
prominent difference is extremely fast scrambling, which for GUE happens at
constant time. Furthermore [CHJLY17] attempted to lower bound complexity of
GUE unitaries by using findings of earlier work[RY17] that showed how theory
of $k$ designs and machinery of _frame potentials_ can be used to this
purpose. By approximately and somewhat heuristically analysing formulas for
high degree frame potentials of the ensemble
$\\{\exp(-itH)\\}_{H\sim\mathrm{GUE}}$ the paper claimed quadratic ($\sim
ct^{2}$) lower bound on complexity of typical unitary generated by GUE
hamiltonian in the limit of large dimension. To our knowledge, except from
informal and not fully rigorous findings of [CHJLY17], there are no results on
complexity of GUE evolutions.

$t_{\mathrm{escape}}$$t_{\mathrm{jump}}$$\cdots$$t$$C_{\varepsilon}(\boldsymbol{U}_{t})$$\cdots$$C_{\max}\sim
d^{2}$

(a)

$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathbb{T}_{V}$$\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\boldsymbol{U}_{t}=e^{iHt}$$B(\boldsymbol{I},\varepsilon)$$B(\boldsymbol{G}_{4},\varepsilon)$$B(\boldsymbol{G}_{1},\varepsilon)$$B(\boldsymbol{G}_{2},\varepsilon)$$B(\boldsymbol{G}_{5},\varepsilon)$$B(\boldsymbol{G}_{3},\varepsilon)$
(b)

Figure 1: (a) Diagram presenting the complexity jump, with threshold
$t\sim\varepsilon$ appearing for evolutions under GUE Hamiltonian. Initially
the complexity is zero and after a threshold it becomes nearly maximal. (b)
Idea of our proof for unitary invariant ensembles proofs: we show that after
the threshold time the evolution leaves the ball around identity, and that it
avoids balls around low complexity unitaries
$\boldsymbol{G}_{i}\in\mathcal{G}^{\leq k}$. Technically we show that this
avoidance holds with high probability for the whole torus $\mathbb{T}_{V}$ on
which the evolution is localized ($V$ is Haar random unitary).

In this work we focus on two ensembles of random generators: GUE and the
ensemble of diagonal Gaussian matrices conjugated by Haar random unitary
transformations. Our main result is a striking complexity jump – from trivial
to nearly maximal. Namely, we show that in these models the time of achieving
nearly maximal complexity is the same as the time of escaping the
neighbourhood of identity – see Fig.1(a). Since being in neighbourhood of
identity means that the complexity of a unitary transformation is trivial, we
have the aforementioned sudden jump. Similar behavior is found for evolutions
generated by Gaussian diagonal Hamiltonians and for states evolving according
to Hamiltonians from the above unitary invariant evolutions.

To establish these results we rely heavily on structural properties of the
above ensembles and concentration of measure techniques. This gives us a much
finer control over the time evolution of complexity compared to techniques
previously employed in this context: high-degree moments and frame potentials.
The idea of our proof is depicted in Fig. 1(b). We do this in two steps: we
show that after threshold time $t_{\mathrm{escape}}$ the evolution leaves the
$\varepsilon$-ball around identity denoted as $B(\boldsymbol{I},\varepsilon)$.
On the other hand, we prove, that for all times, with high probability the
evolution avoids $\varepsilon$-balls around low complexity unitaries. The
latter behaviour takes place for any unitarly invariant ensemble of
Hamiltonians. Technically, the crucial part of our approach is separating the
treatment of the (random) eigenbasis and the (random) spectrum of the relevant
Hamiltonian. The randomness of the eigenbasis can be handled using unitary
invariance of the ensemble. Once the eigenbasis is chosen, the time evolution
is confined to some specific torus embedded in the unitary group and is
described by phases determined by the eigenvalues. These phases are,
asymptotically as time goes to infinity, distributed uniformly and
independently, so their expected asymptotic behavior is transparent. We stress
that the resulting time evolution operator is asymptotically not distributed
as a Haar random unitary since Haar random unitaries do not have independent
eigenvalues.

Structure of the paper: The paper is structured as follows. In Section 2 we
introduce notation and basic mathematical mathematical setup used throughout
the paper. Section 3 contains outline of results, high level overview of proof
strategy abd discussion of open problems. The remaining sections are of
technical nature. Section 4 deals with unitary complexity and builds up to the
proof of main results for unitary complexity: Result 1 and 2. Subsections 4.1
and 4.2 deal with the case of unitary invariant ensembles, i.e. the
$\mathrm{GUE}(d)$ and random basis i.i.d. Gaussian models. In the case of the
diagonal i.i.d. Gaussian model (proof of Result 3), a different approach is
needed, which is presented in Subsection 4.3. Finally, Section 5 is concerned
with evolution of state complexity and proves Result 4, with ideas similar to
those used for unitary complexity. We have relegated proofs of some purely
technical statements to the Appendix.

Acknowledgements We thank Adam Sawicki and Nick Hunter-Jones for helpful
discussions. MK and MO acknowledge financial support from the TEAM-NET project
(contract no. POIR.04.04.00-00-17C1/18-00). MH acknowledges support from the
Foundation for Polish Science through an IRAP project co-financed by the EU
within the Smart Growth Operational Programme (contract no. 2018/MAB/5).

##  2 Preliminaries

We will be concerned with complexity of objects defined on a finite
dimensional Hilbert space $\mathcal{H}\simeq\mathbb{C}^{d}$ (for system of $n$
qubits we have $d=2^{n}$). The set of pure quantum states $\mathcal{S}(d)$
consists of rank one projectors on normalised vectors in $\mathcal{H}$,
denoted by $\psi:=\outerproduct{\psi}{\psi}$. Every unitary operator $U$ on
$\mathbb{C}^{d}$ we have a unitary channel $\boldsymbol{U}$ defined by
$\boldsymbol{U}(\rho)=U\rho U^{\dagger}$. Let $\mathcal{U}(d)$ denote the set
of unitary channels in $\mathbb{C}^{d}$. Since, for a given unitary channel
$\boldsymbol{U}$ the global phase of its operator representative $U$ is
irrelevant, the set of unitary channels $\mathcal{U}(d)$ is isomorphic to
projective unitary group $P\mathrm{U}(d)=\mathrm{U}(d)/U(1)$. We will
formulate our results in terms of standard distances on $\mathcal{U}(d)$ and
$\mathcal{S}(d)$:

$\mathrm{D}_{\diamond}(\boldsymbol{U},\boldsymbol{V}):=\norm{\boldsymbol{U}-\boldsymbol{V}}_{\diamond}\
,\
\mathrm{D}(\psi,\phi)=\frac{1}{2}\norm{\psi-\phi}_{1}=\sqrt{1-\tr(\psi\phi)}\
,$ (1)

where $\norm{\cdot}_{1}$ and $\norm{\cdot}_{\diamond}$ denote trace and
diamond norm respectively [NC11]. We will also use the following distances on
$\mathcal{U}(d)$ which are induced from from norms on linear operators on
$\mathbb{C}^{d}$:

$\mathrm{D}_{\infty}(\boldsymbol{U},\boldsymbol{V}):=\inf_{\varphi\in[0,2\pi)}\norm{U-e^{i\varphi}V}_{\infty}\
,\
\mathrm{D}_{\mathrm{HS}}(\boldsymbol{U},\boldsymbol{V}):=\inf_{\varphi\in[0,2\pi)}\norm{U-e^{i\varphi}V}_{\mathrm{HS}}\
,$ (2)

where $\norm{\cdot}_{\infty}$, $\norm{\cdot}_{\mathrm{HS}}$ denote the
operator norm and the Hilbert-Schmidt norm, while $U,V$ are arbitrary unitary
matrices that give rise to channels $\boldsymbol{U}$ and $\boldsymbol{V}$ (in
what follows we would refer to such matrices as matrix representatives of
unitary channels). We have the following useful estimate for the diamond
metric of unitary channels ([OSH22], Proposition 6):

$\mathrm{D}_{\infty}(\boldsymbol{U},\boldsymbol{V})\leq\mathrm{D}_{\diamond}(\boldsymbol{U},\boldsymbol{V})\leq
2\mathrm{D}_{\infty}(\boldsymbol{U},\boldsymbol{V})$ (3)

In order to define state and unitary complexity we consider circuits formed
from a universal discrete gate set $\mathcal{G}\subset\mathcal{U}(d)$. In our
context universality means only that the set of gate sequences generated from
$\mathcal{G}$ is dense in $\mathcal{U}(d)$ (see however Remark 3.2 for
additional natural assumptions about the gate set, that make our results
exhibit optimal scaling with $d$). Let $\mathcal{G}^{r}$ ($r=0,1,2,\ldots$) be
the set of all size $r$ circuits built from $\mathcal{G}$.

######  Definition 1 (Unitary complexity).

For $\varepsilon\in[0,1]$, we say that a unitary $\boldsymbol{U}$ has
$\varepsilon$-unitary complexity equal to $r$ if and only if
$r=\min\left\\{l:\exists\boldsymbol{V}\in\mathcal{G}^{l}\leavevmode\nobreak\
\text{s.t.}\leavevmode\nobreak\
\mathrm{D}_{\diamond}(\boldsymbol{U},\boldsymbol{V})\leq\varepsilon\right\\}$,
which we denote as $C_{\varepsilon}(\boldsymbol{U})=r$.

######  Definition 2 (State complexity).

For $\varepsilon\in[0,1]$, we say that a pure state $\psi$ has
$\varepsilon$-state complexity equal to $r$ if and only if
$r=\min\left\\{l:\exists\boldsymbol{V}\in\mathcal{G}^{l}\leavevmode\nobreak\
\text{s.t.}\leavevmode\nobreak\
\mathrm{D}(\psi,\boldsymbol{V}(\psi_{0}))\leq\varepsilon\right\\}$, which we
denote as $C_{\varepsilon}(\psi)=r$.

In the physical context we typically have
$\mathcal{H}\simeq(\mathbb{C}^{2})^{\otimes n}$ and $\psi_{0}$ in the
definition of state complexity is chosen to be an unentangled product state,
for instance $\psi_{0}=\outerproduct{0}{0}^{\otimes n}$.

Setting: The main object of study of this paper are time evolutions governed
by random Hamiltonians. We let the Hamiltonian $H$ to be drawn from some
probability distribution on $d\times d$ Hermitian matrices and let
$U_{t}=\exp(-itH)$ be the unitary time evolution operator associated to $H$.
We will analyze in the detail the complexity of the corresponding unitary
channel $\boldsymbol{U}_{t}$ and states
$\psi_{t}:=\boldsymbol{U}_{t}(\psi_{0})$ for the following models:

######  Definition 3.

(Gaussian Unitary Ensemble ($\mathrm{GUE}$)) Fix $d$ and $\sigma>0$. Let
$X_{i,j}$ for $1\leq j\leq i\leq d$ and $Y_{i,j}$ for $j<i$ be independent
Gaussians of mean $0$ and variance $\sigma^{2}$. We say that $H$ is drawn from
$\mathrm{GUE}(d,\sigma^{2})$ if $H$ is a hermitian matrix such that for every
$i$ $H_{ii}=X_{i,i}$ and $H_{ij}=\frac{X_{i,j}+iY_{i,j}}{\sqrt{2}}$ for $i>j$.
Note that $H\sim\mathrm{GUE}(d,\sigma^{2})$ has the same distribution as
$\sigma H^{\prime},H^{\prime}\sim\mathrm{GUE}(d,1)$. We will write
$\mathrm{GUE}(d)$ for $\mathrm{GUE}\left(d,\frac{1}{d}\right)$.

######  Definition 4.

(Diagonal i.i.d Gaussian) We say that $H$ is drawn from the diagonal i.i.d.
Gaussian ensemble, denoted $\mathrm{DiagGauss(d)}$, if $H$ is diagonal with
diagonal elements $\lambda_{i}$ which are independent Gaussians of mean $0$
and variance $1$.

######  Definition 5.

(Random basis i.i.d Gaussian) We say that $H$ is drawn from the random basis
i.i.d. Gaussian ensemble, denoted $\mathrm{UGauss(d)}$, if $H=UDU^{\dagger}$,
where $U$ is Haar random unitary on $\mathbb{C}^{d}$ and $D$ is diagonal with
elements $\lambda_{i}$ which are independent Gaussians of mean $0$ and
variance $1$.

##  3 Overview of results

In this section we first outline our main findings about the complexity of
random Hamiltonian evolution, then give a high level overview our main proof
techniques, and conclude with a list of open problems. Our typical result will
be that for all times $t\leq t_{\mathrm{escape}}$, $\boldsymbol{U}_{t}$ has
with high probability trivial (zero) complexity, while after fixed slightly
larger time $t>t_{\mathrm{jump}}>t_{\mathrm{escape}}$ it has nearly maximal
complexity (scaling with $d^{2}$, see the discussion in Remark 3.2). In the
sharpest of the results, the ratio of the two timescales
$t_{\mathrm{jump}}/t_{\mathrm{escape}}=\Theta(1)$, while individual timescales
scale individually with accuracy parameter
$t_{\mathrm{escape}}\sim\varepsilon$, We thus obtain an extreme jump, which is
illustrated in Fig. 1(a).

In the results below $U_{t}=e^{iHt}$, $\boldsymbol{U}_{t}$ is the
corresponding unitary channel, and $\psi_{t}=\boldsymbol{U}_{t}(\psi_{0})$,
for computationally trivial initial state $\psi_{0}$. The gateset
$\mathcal{G}$ is fixed and $C,C^{\prime},C^{\prime\prime}$ are absolute
constants that may change from one result to another. On the other hand the
parameter $\varepsilon>0$ is either fixed (independent of $d$) or has to
satisfy $\varepsilon\gtrsim d^{-1/8}$, which in particular allows the
treatment of the physically relevant case for moderately small values of
$\varepsilon=1/\mathrm{polylog}(d)=1/\mathrm{poly}(n)$ (with the latter
equality valid for the system of $n$ qubits).

We start from:

######  Result 1 (Complexity jump for GUE evolutions).

Let $t_{\mathrm{escape}}=C\varepsilon$,
$t_{\mathrm{jump}}=C^{\prime}\varepsilon$ ($C^{\prime}>C$). With high
probability over $H\sim\mathrm{GUE}(d)$

  1. (a)

For all times time $t\in[0,t_{\mathrm{escape}}]$ complexity of evolution
$\boldsymbol{U}_{t}$ is trivial: $C_{\varepsilon}(\boldsymbol{U}_{t})=0$ .

  2. (b)

For any fixed time $t>t_{\mathrm{jump}}$ complexity satisfies
$C_{\varepsilon}(\boldsymbol{U}_{t})\geq\frac{C^{\prime\prime}\varepsilon^{2}}{{\log\absolutevalue{\mathcal{G}}}}d^{2}$
which exhibits optimal scaling with $d$ due to Solovay-Kitaev compilation.

The statement (a) is proven in Proposition 4.10 and follows from the property
that for typical $H\sim\mathrm{GUE}(d)$ we have
$\lambda_{max}-\lambda_{\min}=\Theta(1)$, while statement (b) is proven in
Theorem 4.9.

Analogous result holds in the case of random basis, i.i.d. Gaussian
eigenvalues, yet with a less sudden jump. Namely, until
$t\sim\varepsilon/\sqrt{\log d}$ complexity is trivial, while after time
$t\sim\varepsilon$, it becomes near maximal. The ratio of these times exhibits
a (sub) polynomial scaling with $n$ for the system of $n$ qubits.

######  Result 2 (Complexity jump for random basis i.i.d. Gaussian
Hamiltonians).

Let $t_{\mathrm{escape}}=C\varepsilon/\sqrt{\log(d)}$,
$t_{\mathrm{jump}}=C^{\prime}\varepsilon$. With high probability over the
choie of random basis i.i.d. Guassian Hamiltonian $H$

  1. (a)

For all times time $t\in[0,t_{\mathrm{escape}}]$ the complexity of evolution
$\boldsymbol{U}_{t}$ is trivial: $C_{\varepsilon}(\boldsymbol{U}_{t})=0$ .

  2. (b)

For any fixed time $t>t_{\mathrm{jump}}$ the complexity satisfies
$C_{\varepsilon}(\boldsymbol{U}_{t})\geq\frac{C^{\prime\prime}\varepsilon^{2}}{{\log\absolutevalue{\mathcal{G}}}}d^{2}$
which exhibits optimal scalling with $d$ due to Solovay-Kitaev compilation.

The part (a) is proven in Proposition 4.10 and follows from the property that
typically $\lambda_{max}-\lambda_{\min}\sim\sqrt{\log(d)}$ for i.i.d. Gaussian
Hamiltonians, while part (b) is proven in Theorem 4.9. For discussion about
the gap between $t_{\mathrm{escape}}$ and $t_{\mathrm{jump}}$, see Remark 4.4.

Related results, albeit using different techniques and different scaling with
respect to $\varepsilon$, can be obtained for the random Gaussian Hamiltonian
with fixed basis.

######  Result 3 (Complexity bound for diagonal i.i.d. Gaussian Hamiltonians).

Let $t_{\mathrm{escape}}=C\varepsilon/\sqrt{\log(d)}$,
$t_{\mathrm{jump}}=C^{\prime}$. With high probability over the choice of
i.i.d. Gaussian Hamiltonian $H$ in the _diagonal_ basis

  1. (a)

For all times time $t\in[0,t_{\mathrm{escape}}]$ complexity of evolution
$\boldsymbol{U}_{t}$ is trivial: $C_{\varepsilon}(\boldsymbol{U}_{t})=0$ .

  2. (b)

For any fixed time $t>t_{\mathrm{jump}}$ complexity satisfies
$C_{\varepsilon}(\boldsymbol{U}_{t})\geq\frac{C^{\prime\prime}}{{\log\absolutevalue{\mathcal{G}}}}\cdot
d\log\left(\frac{1}{\varepsilon}\right)$.

The lower bound from Result 3 b is near optimal in $d$ provided that
eigenbasis of $H$ is the computational basis in $n$ qubit system. This is due
to the following upper bound valid for all unitaries diagonal in the
computational basis: $C_{\varepsilon}(\boldsymbol{U})\leq Cd\log
d\log^{\gamma}\left(\frac{1}{\varepsilon}\right)$ (see Lemma 4.14). The
statement (a) is proven in Proposition 4.10, while (b), but without the
$\log\left(\frac{1}{\varepsilon}\right)$ scaling, is proved in Theorem 4.13.
The proof of $\log\left(\frac{1}{\varepsilon}\right)$ scaling requires a more
particular technique and is given in Theorem E.3. Note that in the case of
fixed basis model, in contrast to the GUE and random basis models, we only
prove high complexity after _constant_ time (not $\sim\varepsilon$), so we do
not prove a sudden jump; see more discussion in Remark 4.5.

Note that Result 3(a) and Result 2(a) are actually the same, since triviality
of complexity means staying near the identity, which depends only on spectral
properties and the two models have the same spectrum. Also, the above two
results, unlike Result 1, do not indicate whether after time
$t\sim\frac{\varepsilon}{\sqrt{\log d}}$ complexity becomes nonzero. Actually,
this is the case – namely, for any larger time, with high probability $U_{t}$
is outside an $\varepsilon$-ball around the identity. This is proven in
Proposition 4.11.

Similar picture as for unitary complexity can be drawn for state complexity.

######  Result 4 (Complexity jumps for states evolving according to unitary
invariant random Hamiltonians: GUE or random basis i.i.d. Gaussian).

Let $t_{\mathrm{escape}}=C\varepsilon$ for $H\sim\mathrm{GUE}(d)$ and
$t_{\mathrm{escape}}=C\varepsilon/\sqrt{\log(d)}$ for
$H\sim\mathrm{UGauss(d)}$, $t_{\mathrm{jump}}=C^{\prime}\varepsilon$. Then,
with high probability over the choice of $H$

  1. (a)

For times $t\leq t_{\mathrm{escape}}$ complexity of
$\psi_{t}=\boldsymbol{U}_{t}(\psi_{0})$ is trivial:
$C_{\varepsilon}(\psi_{t})=0$.

  2. (b)

For any fixed time $t>t_{\mathrm{jump}}$ complexity satisfies
$C_{\varepsilon}(\psi_{t})\geq\frac{C^{\prime\prime}\varepsilon^{2}}{{\log\absolutevalue{\mathcal{G}}}}\cdot
d$, which has near optimal scaling with $d$ due to the upper bound in Remark
3.2.

The statement (a) follows from application of Proposition 4.10, which states
that for certain times the diamond distance of $\boldsymbol{U}_{t}$ from the
identity is smaller than $\varepsilon$. Due to the relation between diamond
norm and operator norm (3), we obtain the same for states. The statement (b)
is proven in Theorem 5.6. In the case of state complexity, we do not consider
the diagonal basis model, see Remark 5.1.

######  Remark 3.1.

Random Hamiltonians in considered models do not have a well prescribed notion
of locality and hence their energy scale (and therefore also the time scale of
unitary evolution) is not uniquely defined. In above definitions we adopted
the conventions ensuring that with high probability $\norm{H}=\Theta(1)$ for
GUE ensemble and $\norm{H}=\Theta(\sqrt{\log(d)})$ for the Gaussian ensemble.
Importantly our results do not depend on these specific choices of
normalisation. What matters is the _ratio_ of the timescales: (i)
$t_{\mathrm{escape}}$ needed to escape the $\varepsilon$ ball around identity
channel $\boldsymbol{I}$ and (ii) $t_{\mathrm{jump}}$ at which it is possible
to claim essentially maximal complexity of $\boldsymbol{U}_{t}$. This ratio is
not affected by the choice of normalisation for $H$.

######  Remark 3.2.

In order to claim optimality of our results with the dimension $d$ we need to
have absolute upper bound for the complexity of unitaries and states. One way
to realise this is to assume that we have $n$ qubit system, and our gateset
consists of geometrically local universal gateset (acting nontrivially on a
fixed number of qubits). In this case, assuming that the gateset is symmetric
(i.e. containing every gate together with its inverse), the celebrated Solovay
and Kitaev algorithm [DN05] gives the following absolute upper bound on
complexity $C_{\varepsilon}(\boldsymbol{U})\leq
c(\mathcal{G})d^{2}\log\left(\frac{1}{\varepsilon}\right)^{\gamma}$, for some
constant $c(\mathcal{G})$ depending on the gateset and $\gamma\in[1,3)$.
Furthermore, as shown in [HRC02] we can chose $\gamma=1$ if our gate set
enjoys the property of _a spectral gap_ (which is conjectured [BG11]to hold
arbitrary universal $\mathcal{G}$ and known to hold provided gates in
$\mathcal{G}$ have algebraic entries). By similar techniques it is possible to
obtain the following bound for state complexity $C_{\varepsilon}(\psi)\leq
c(\mathcal{G})d\log\left(\frac{1}{\varepsilon}\right)^{\gamma}$. When gateset
$\mathcal{G}$ is not symmetric, currently known extensions [BO17, BG21] of the
Solovay-Kitaev algorithm give a worse exponent $\gamma$. Finally, stronger
non-existential results [Var13] on approximating sequences for general
universal gatesets imply that for general non symmetric universal gatesets we
can use above bounds for $\gamma\leq 2$ (see also [OSH22] for detailed
discussion).

### Open problems

Below we highlight some of the open problems and future research directions
related to findings of our paper.

First, it is natural to attempt to establish similar results for other classes
of models of random Hamiltonian evolutions. The most physically natural ones
would be a random local Hamiltonians or models that exhibit structure or
sparsity in some operator basis (such as the SYK model [BDKP20] or the
recently introduced random sparse Pauli models [CCD+23]).

Second, it would be interesting to study recurrence of time evolution, in a
manner similar to [OHHJ22]. Note that the case of random Hamiltonians is more
difficult than random quantum circuits, as the Hamiltonian is chosen once at
the beginning, so the process $\\{e^{iHt}\\}_{t\geq 0}$ is non-Markovian. At
the same time it seams plausible that by using techniques from [RPA22] one
could get access to _average_ recurrence times for unitary evolutions
generated by Hamiltonians with _generic_ spectra. More generally, for fixed
eigenbasis of $H$, time evolution $\exp(-itH)$ is equivalent to a dynamical
system known as the linear flow on a torus. For this reason we expect that
techniques of ergodic theory (for example quantitative results developed in
[Bec17]) might be suitable to study recurrence properties of$\exp(-itH)$.

Finally, in our lower bounds on complexity, the parameter $\varepsilon^{2}$
appears in the numerator. We believe it should be possible to remove it,
although it may require more detailed knowledge about the distribution of
unitaries generated from fundamental $\mathcal{G}$. It is also worth
investigating whether purely geometric considerations (as opposed to using
concentration of measure as we do in the paper) could give the optimal scaling
with respect to $\varepsilon$, namely $\log(1/\varepsilon)$ – see Appendix E
for attempts in this direction.

### Overview of proofs and techniques

We outline the high level strategy of the proofs and proof techniques.

######  Remark 3.3.

For technical reasons it will be convenient for us to work with the
approximate complexity $C^{\mathrm{HS}}_{\varepsilon}(\boldsymbol{U})$ defined
in a manner analogous to that in Definition 1 but using the Hilbert-Schmidt
metric $\mathrm{D}_{\mathrm{HS}}$ as a distance. Note that the diameter of the
set of unitaries with respect to the Hilbert-Schmidt metric scale as
$\sqrt{d}$, so it is natural to consider complexity $C^{\mathrm{HS}}$ with
parameter $\varepsilon\sqrt{d}$, with $\varepsilon$ independent of $d$.

By the inequality between the Hilbert-Schmidt and operator norm
$\norm{A}_{\mathrm{HS}}\leq\sqrt{d}\norm{A}_{\infty}$ it follows after taking
infimum over phases and using Eq. (3) that: for every
$\boldsymbol{U},\boldsymbol{V}$

$\mathrm{D}_{\mathrm{HS}}(\boldsymbol{U},\boldsymbol{V})\leq\sqrt{d}\cdot\mathrm{D}_{\diamond}(\boldsymbol{U},\boldsymbol{V})\
.$ (4)

Hence, if for any $\boldsymbol{G}\in\mathcal{G}^{r}$ we have
$\mathrm{D}_{\mathrm{HS}}(\boldsymbol{U},\boldsymbol{G})>\varepsilon\sqrt{d}$,
then also$\mathrm{D}_{\diamond}(\boldsymbol{U},\boldsymbol{G})>\varepsilon$.
This proves that $C_{\varepsilon}(\boldsymbol{U})\geq
C^{\mathrm{HS}}_{\varepsilon\sqrt{d}}(\boldsymbol{U})$, so it suffices to
provide lower bounds using the Hilbert-Schmidt metric.

To bound complexity, we first use the union bound. For now let the
distribution of $H$ be general. The probability below is with respect to the
random choice of Hamiltonian $H$ and $U_{t}=\exp(itH)$ :

$\mathbb{P}_{H}(C^{HS}_{\varepsilon\sqrt{d}}(\boldsymbol{U}_{t})\leq
k)=\mathbb{P}_{H}(\boldsymbol{U}_{t}\in\bigcup_{\boldsymbol{G}\in\mathcal{G}^{\leq
k}}B(\boldsymbol{G},\varepsilon\sqrt{d}))\leq\sum_{\boldsymbol{G}\in\mathcal{G}^{\leq
k}}\mathbb{P}_{H}\left(\boldsymbol{U}_{t}\in
B(\boldsymbol{G},\varepsilon\sqrt{d})\right)$ (5)

We will now sketch the approach to estimating
$\mathbb{P}\left(\boldsymbol{U}_{t}\in
B(\boldsymbol{G},\varepsilon\sqrt{d})\right)$ fleshed out in the following
sections. Let us write $H=VDV^{\dagger}$, with $D$ real diagonal and $V$
unitary, where both $D$ and $V$ are in general random. We then have
$U_{t}=Ve^{iDt}V^{\dagger}$, where $e^{iDt}$ is diagonal with entries
$(e^{\lambda_{1}t},\dots,e^{\lambda_{d}t})$, where $\lambda_{i}$ are the
eigenvalues of $H$. This implies that once $V$ is chosen, the whole time
evolution happens inside a $d$-dimensional torus $\mathbb{T}_{V}$ determined
by $V$, where:

$\mathbb{T}_{V}=\\{VAV^{\dagger}\ |\
A=\mathrm{Diag}(e^{i\varphi_{1}},\dots,e^{i\varphi_{d}}),\varphi_{i}\in[0,2\pi)\\}$
(6)

(note that the closure of the set $\\{U_{t}\\}_{t\geq 0}$ may have dimension
strictly smaller than $d$ if the eigenvalues $\lambda_{i}$ are algebraically
dependent)

Note that if the phases $(e^{\lambda_{1}t},\dots,e^{\lambda_{d}t})$ were
distributed according to the Haar measure on the torus $T_{V}$, all the
probabilities appearing in the union bound would of order
$\sim\varepsilon^{d}$, which would easily imply a complexity lower bound of
order
$\sim\frac{1}{\log\absolutevalue{\mathcal{G}}}d\log\left(\frac{1}{\varepsilon}\right)$.
Of course for general $H$ the phases will not be Haar random. Nevertheless, if
the distribution of the eigenvalues of $H$ is continuous (as is the case in
the ensembles we consider), it can be shown that the phase distribution will
approach the Haar measure as $t\to\infty$ (see Appendix E for a more detailed
discussion). Thus, we expect the same complexity lower bound of
$\sim\frac{1}{\log\absolutevalue{\mathcal{G}}}d\log\left(\frac{1}{\varepsilon}\right)$
to hold for large times. This explains heuristically why we expect the
unitaries $\boldsymbol{U}_{t}$ to have high complexity for large times.

We can obtain a much better $d^{2}$ scaling instead of just $d$ if the
eigenbasis of $H$ is Haar random (for example, if $H$ is drawn from the
$\mathrm{GUE}$ ensemble). If this is the case, one can show that for
$\boldsymbol{G}$ not too close to $\boldsymbol{I}$, the random torus
$\mathbb{T}_{V}$ hosting the time evolution of $U_{t}$ will not intersect the
ball $B(\boldsymbol{G},\varepsilon)$ at all with very high probability. This
will be made rigorous in Section 4.1. This part of the argument does not
depend on the spectrum of $H$.

Then, the only term left in (5) will be $\boldsymbol{G}=\boldsymbol{I}$. Note
that since $\boldsymbol{U}_{0}=\boldsymbol{I}$, by continuity for small times
the channel $\boldsymbol{U}_{t}$ will typically be still close to the
identity, so the bound on $\mathbb{P}\left(\boldsymbol{U}_{t}\in
B(\boldsymbol{I},\varepsilon)\right)$ will necessarily be time dependent and
will depend on the spectrum of $H$ (but not on the eigenbasis). Intuitively,
we expect it should take time $\sim\varepsilon$ to leave the ball of radius
$\varepsilon$ around the identity with high probability. This will be made
precise in Section 4.2 for two models unders considerations – the GUE model
and the random basis i.i.d. Gaussian model $\mathrm{UGauss(d)}$.

If the Haar randomness of the eigenbasis $V$ is not available (e.g. when $H$
always has a fixed eigenbasis or when the distribution of its eigenbasis is
intractable), we are forced to deal with all the terms in (5), not only
$\boldsymbol{G}=\boldsymbol{I}$. We analyze this problem for the diagonal
i.i.d. Gaussian model $\mathrm{DiagGauss(d)}$ in two different ways: in
Section 4.3 using probabilistic concentration inequalities and in Appendix E
using purely geometric considerations. The former approach is more in line
with other probabilistic techniques used in the paper, but gives worse scaling
of the complexity lower bound with respect to $\varepsilon$.

We end the overview by briefly commenting on the mathematical techniques used.
The main tool for proving that certain desired properties hold with high
probability is the concentration of measure [Mec19]. Roughly speaking, this
means that if a quantity depends on a large number of random variables and not
too strongly on any of them, it should be typically very close to its average
value. The most familiar situation where such concentration occurs are sums of
independent random variables (the law of large numbers setting), which are
sharply peaked around their means. We employ this phenomenon in two ways. To
handle the randomness of the eigenbasis of $H$, we use concentration of
measure on the unitary group, which states that smooth functions of large
unitary matrices are close to their expected values. Then, to analyze the time
evolution on the torus we use concentration for functions of eigenvalues of a
random Hamiltonian. In the case of the i.i.d. Gaussian ensembles this is
simply concentration for independent variables, but for the GUE case we need
technical statements coming from random matrix theory.

##  4 Unitary complexity

###  4.1 Avoiding low complexity unitaries by random tori

Throughout this section we assume that $H=VDV^{\dagger}$ with $V$ distributed
according to the Haar measure on $\mathrm{U}(d)$ and $D$ arbitrary diagonal.
The time evolution $U_{t}$ happens inside $\mathbb{T}_{V}$ as defined in (6),
which is a random torus since $V$ is Haar random. In this Section, we show
that with high probability over the choice of $H$, this random torus will not
intersect any of the balls around $\boldsymbol{G}\in\mathcal{G}^{\leq k}$,
save for $\boldsymbol{G}$ very close to the identity. This will allow us to
focus only on the neighborhood of the identity, which is done in Section 4.2.

We first observe that since the time evolution $U_{t}$ happens inside
$\mathbb{T}_{V}$, we have by conjugation invariance:

$\mathbb{P}\left(\boldsymbol{U}_{t}\in
B(\boldsymbol{G},\varepsilon\sqrt{d})\right)\leq\mathbb{P}_{V}\left(\mathbb{T}_{V}\cap
B(\boldsymbol{G},\varepsilon\sqrt{d})\neq\emptyset\right)=\mathbb{P}_{V}\left(\mathbb{T}\cap
B(\boldsymbol{V}\boldsymbol{G}\boldsymbol{V}^{-1},\varepsilon\sqrt{d})\neq\emptyset\right)$
(7)

where $\mathbb{T}$ is the set of all diagonal unitary channels. Thus, to upper
bound the right hand side of (7) it will suffice to show that with high
probability over the choice of $V$, the distance from $VGV^{\dagger}$ to
$\mathbb{T}$ is greater than $\varepsilon\sqrt{d}$.

To this end, let us define:

$\mathrm{dist}(X,\mathbb{T}):=\inf_{D\in\mathbb{T}}\norm{X-D}_{\mathrm{HS}}=\inf_{D\in\mathbb{T}}\mathrm{D}_{\mathrm{HS}}(\boldsymbol{X},\boldsymbol{D})$
(8)

where the last equality follows since $\mathbb{T}$ is closed under
multiplication by $e^{i\varphi}$. We will first bound from below the
expectation over $V$ of $\mathrm{dist}(VGV^{\dagger},\mathbb{T})$ (Theorem
4.2) and then use concentration of measure to show that the distance is close
to its expectation with high probability.

######  Lemma 4.1.

For any unitary $X$ we have:

$\mathrm{dist}(X,\mathbb{T})^{2}=2d-2\sum_{i=1}^{d}\absolutevalue{X_{ii}}$ (9)

###### Proof.

It is straightforward to derive:

$\mathrm{dist}(X,\mathbb{T})^{2}=2d-2\sup_{D\in\mathbb{T}}\mathrm{Re}\tr(XD^{\dagger})$
(10)

We now claim that:

$\displaystyle\sup_{D\in\mathbb{T}}\mathrm{Re}\tr(XD^{\dagger})=\sum_{i=1}^{d}\absolutevalue{X_{ii}}$
(11)

Indeed, note that for any $D\in\mathbb{T}$:

$\displaystyle\mathrm{Re}\tr(XD^{\dagger})\leq\absolutevalue{\tr(XD^{\dagger})}\leq\sum_{i=1}^{d}\absolutevalue{(XD^{\dagger})_{ii}}\leq\sum_{i=1}^{d}\absolutevalue{(X)_{ii}}\absolutevalue{D^{\dagger}_{ii}}=\sum_{i=1}^{d}\absolutevalue{X_{ii}}$
(12)

It is straightforward to see that the maximum value on the RHS can be obtained
by putting $D_{ii}=\frac{X_{ii}}{\absolutevalue{X_{ii}}}$ if $X_{ii}\neq 0$
and $D_{ii}=1$ otherwise. ∎

A similar proof shows that for any $X$ we have:

$\mathrm{D}_{\mathrm{HS}}(\boldsymbol{X},\boldsymbol{I})^{2}=2d-2\absolutevalue{\tr(X)}$
(13)

######  Theorem 4.2.

For any $\boldsymbol{G}\in\mathcal{G}^{\leq k}$ we have:

$\mathbb{E}_{V}\mathrm{dist}(VGV^{\dagger},\mathbb{T})\geq\frac{1}{3}\cdot\mathrm{D}_{\mathrm{HS}}(\boldsymbol{G},\boldsymbol{I})$
(14)

(note that the projective Hilbert-Schmidt metric on the right hand side is
necessary, since e.g. for $G=e^{i\varphi}I$ the left hand side is zero, but
$\norm{G-I}_{\mathrm{HS}}>0$).

###### Proof.

We will first bound the square of the expected distance. By Lemma 4.1 we have:

$\mathbb{E}_{V}\mathrm{dist}(VGV^{\dagger},\mathbb{T})^{2}=2d-2\sum_{i=1}^{d}\mathbb{E}_{V}\absolutevalue{(VGV^{\dagger})_{ii}}=2d-2\sum_{i=1}^{d}\mathbb{E}_{V}\absolutevalue{\tr(\outerproduct{i}{i}VGV^{\dagger})}$
(15)

To estimate the second term we use Jensen inequality:

$\mathbb{E}_{V}\absolutevalue{\tr(\outerproduct{i}{i}VGV^{\dagger})}\leq\left(\mathbb{E}_{V}\absolutevalue{\tr(\outerproduct{i}{i}VGV^{\dagger})}^{2}\right)^{1/2}$
(16)

and then perform the second moment computation which follows from Corollary 1
from [MPO21]:

$\mathbb{E}_{V}\absolutevalue{\tr(\outerproduct{i}{i}VGV^{\dagger})}^{2}=\frac{1}{d+1}\left(1+\frac{\absolutevalue{\tr(G)}^{2}}{d}\right)$
(17)

Together this implies that:

$\mathbb{E}_{V}\mathrm{dist}(VGV^{\dagger},\mathbb{T})^{2}\geq
2d-2d\sqrt{\frac{1}{d+1}\left(1+\frac{\absolutevalue{\tr(G)}^{2}}{d}\right)}$
(18)

By (13), we have
$\absolutevalue{\tr(G)}=d-\frac{1}{2}\mathrm{D}_{\mathrm{HS}}(\boldsymbol{G},\boldsymbol{I})^{2}$.
Combining this with the inequality $\sqrt{1+x}\leq 1+\frac{1}{2}x$ and
$\mathrm{D}_{\mathrm{HS}}(\boldsymbol{G},\boldsymbol{I})^{4}\leq
2d\cdot\mathrm{D}_{\mathrm{HS}}(\boldsymbol{G},\boldsymbol{I})^{2}$, after a
short computation we end up with:

$\mathbb{E}_{V}\mathrm{dist}(VGV^{\dagger},\mathbb{T})^{2}\geq\frac{d}{2(d+1)}\cdot\mathrm{D}_{\mathrm{HS}}(\boldsymbol{G},\boldsymbol{I})^{2}\geq\frac{1}{3}\cdot\mathrm{D}_{\mathrm{HS}}(\boldsymbol{G},\boldsymbol{I})^{2}$
(19)

Now, by (8) have:

$\mathrm{dist}(VGV^{\dagger},\mathbb{T})=\inf_{D\in\mathbb{T}}\mathrm{D}_{\mathrm{HS}}(\boldsymbol{V}\boldsymbol{G}\boldsymbol{V}^{-1},\boldsymbol{D})\leq\mathrm{D}_{\mathrm{HS}}(\boldsymbol{V}\boldsymbol{G}\boldsymbol{V}^{-1},\boldsymbol{I})=\mathrm{D}_{\mathrm{HS}}(\boldsymbol{G},\boldsymbol{I})$
(20)

which together with (19) implies:

$\frac{1}{3}\cdot\mathrm{D}_{\mathrm{HS}}(\boldsymbol{G},\boldsymbol{I})^{2}\leq\mathbb{E}_{V}\mathrm{dist}(VGV^{\dagger},\mathbb{T})^{2}\leq\mathbb{E}_{V}\mathrm{dist}(VGV^{\dagger},\mathbb{T})\cdot\mathrm{D}_{\mathrm{HS}}(\boldsymbol{G},\boldsymbol{I})$
(21)

and the theorem is proved. ∎

Having bounded the expectation, we now move to the concentration of measure.
To this end, we will need control over the Lipschitz constant:

######  Lemma 4.3.

For any $G\in\mathrm{U}(d)$, the function $f:\mathrm{U}(d)\to\mathbb{R}$
defined as $f(V)=\mathrm{dist}(VGV^{\dagger},\mathbb{T})$ is Lipschitz with
respect to the Hilbert-Schmidt norm with Lipschitz constant
$2\norm{G-I}_{\infty}$.

###### Proof.

We write $f=g\circ h$, where $g(V)=VGV^{\dagger}$ and
$h(W)=\mathrm{dist}(W,\mathbb{T})$. First note that the function
$\widetilde{g}(V)=VGV^{\dagger}-I=V(G-I)V^{\dagger}$ obviously has the same
Lipschitz constant as $g$, so it suffices to bound the Lipschitz constant of
$\widetilde{g}$. Using the properties of the Hilbert-Schmidt norm, we get:

$\displaystyle\norm{\widetilde{g}(U)-\widetilde{g}(V)}_{\mathrm{HS}}=\norm{U(G-I)U^{\dagger}-V(G-I)V^{\dagger}}_{\mathrm{HS}}=$
(22)
$\displaystyle\norm{U(G-I)(U^{\dagger}-V^{\dagger})-(V-U)(G-I)V^{\dagger}}_{\mathrm{HS}}\leq$
$\displaystyle\norm{U(G-I)(U^{\dagger}-V^{\dagger})}_{\mathrm{HS}}+\norm{(V-U)(G-I)V^{\dagger}}_{\mathrm{HS}}\leq
2\norm{G-I}_{\infty}\norm{U-V}_{\mathrm{HS}}$ (23)

which proves that $\widetilde{g}$, so also $g$, is Lipschitz with constant
$2\norm{G-I}_{\infty}$.

As for $h$, it is Lipschitz with constant $1$, which follows from the general
fact that in any metric space $X$ and a set $A\subseteq X$ the function
$x\mapsto\mathrm{dist}(x,A)$ is Lipschitz with constant $1$. Since $f=g\circ
h$, it follows that $f$ is Lipschitz with constant $2\norm{G-I}_{\infty}$. ∎

We will use concentration of measure for $\mathrm{U}(d)$ in the following form
(implied by [Mec19], Theorem 5.17):

######  Theorem 4.4.

Let $F:\mathrm{U}(d)\to\mathbb{R}$ be Lipschitz with Lipschitz constant $L$
with respect to the Hilbert-Schmidt norm. Then for any $a>0$:

$\displaystyle\mathbb{P}_{U}\left(F(U)\geq\mathbb{E}_{U}F(U)+a\right)\leq\exp(-\frac{(d-2)a^{2}}{12L^{2}})$
(24)

We can now state and prove the main theorem of this section:

######  Theorem 4.5.

Let $\boldsymbol{G}$ be such that
$\mathrm{D}_{\mathrm{HS}}(\boldsymbol{G},\boldsymbol{I})>6\varepsilon\sqrt{d}$.
Then for any $t\geq 0$ we have:

$\mathbb{P}\left(\boldsymbol{U_{t}}\in
B(\boldsymbol{G},\varepsilon\sqrt{d})\right)\leq\exp\left(-\frac{\varepsilon^{2}d^{2}}{384}\right)$
(25)

###### Proof.

By (7) it suffices to prove that:

$\mathbb{P}_{V}\left(\mathrm{dist}(VGV^{\dagger},\mathbb{T})\leq\varepsilon\sqrt{d}\right)\leq\exp\left(-\frac{\varepsilon^{2}d^{2}}{384}\right)$
(26)

Let $F(V)=\mathrm{dist}(VGV^{\dagger},\mathbb{T})$. By Theorem 4.2, we have:

$\mathbb{E}_{V}\mathrm{dist}(VGV^{\dagger},\mathbb{T})\geq\frac{1}{3}\mathrm{D}_{\mathrm{HS}}(\boldsymbol{G},\boldsymbol{I})\geq
2\cdot\varepsilon\sqrt{d}$ (27)

By applying the concentration theorem (switching $F$ to $-F$) with
$a=\varepsilon\sqrt{d}$, invoking Lemma 4.3 and using $\norm{G-I}_{\infty}\leq
2$ we obtain:

$\mathbb{P}_{V}\left(\mathrm{dist}(VGV^{\dagger},\mathbb{T})\leq\varepsilon\sqrt{d}\right)\leq\exp\left(-\frac{\varepsilon^{2}(d-2)d}{48\norm{G-I}^{2}_{\infty}}\right)\leq\exp\left(-\frac{\varepsilon^{2}d^{2}}{384}\right)$
(28)

∎

######  Remark 4.1.

It would be desirable to improve the dependence of the probability bound on
$\varepsilon$, e.g. by removing the factor $\varepsilon^{2}$. This could be
possible by ensuring that $\norm{G-I}_{\infty}$, which controls the Lipschitz
constant, is sufficiently small for all or most
$\boldsymbol{G}\in\mathcal{G}^{\leq k}$. However, available results about the
distribution of unitaries from $\mathcal{G}^{\leq k}$ seem not to be strong
enough to support such attempts.

###  4.2 Leaving the neighborhood of identity

In this Section, we analyze the probability that $\boldsymbol{U}_{t}$ leaves
the ball $B(\boldsymbol{I},\varepsilon\sqrt{d})$ and prove that this happens
with high probability as soon as $t\sim\varepsilon$. The bulk of this Section
is devoted to the GUE model. We then prove the same statement for the random
basis i.i.d Gaussian model, which is considerably simpler. Arguments in this
Section depend only on the spectrum of $H$ and not on its eigenbasis.

For now let the distribution of the Hamiltonian $H$ be general. By (13), we
have:

$\mathbb{P}(\mathrm{D}_{\mathrm{HS}}(\boldsymbol{U}_{t},\boldsymbol{I})<\varepsilon\sqrt{d})=\mathbb{P}\left(\absolutevalue{\tr(U_{t})}>(1-\frac{1}{2}\varepsilon^{2})d\right)$
(29)

where the probability is now only with respect to the distribution of
eigenvalues of $U_{t}=e^{iHt}$. We now need to control the expected value and
concentration of $\tr(U_{t})$. To this end, it is convenient to introduce the
concept of spectral measure. Let $\lambda_{1},\dots,\lambda_{d}$ be the
eigenvalues of $H$ in arbitrary order. We define the spectral measure of $H$,
denoted as $\mu_{H}$, to be the unique probabilistic measure such that for any
function $F$ of the eigenvalues we have:

$\int_{\mathbb{R}}F(\lambda)d\mu_{H}(\lambda)=\frac{1}{d}\mathbb{E}_{H}\sum_{i=1}^{d}F(\lambda_{i})$
(30)

One can obtain $\mu_{H}$ by taking the average over the (random) empirical
spectral measures $\mu=\frac{1}{d}\sum_{i=1}^{d}\delta_{\lambda_{i}}$.

We have:

$\frac{1}{d}\mathbb{E}_{H}\tr(U_{t})=\frac{1}{d}\mathbb{E}_{H}\tr(e^{iHt})=\frac{1}{d}\mathbb{E}_{H}\sum_{k=1}^{d}e^{i\lambda_{k}t}=\int_{\mathbb{R}}e^{i\lambda
t}d\mu_{H}(\lambda)$ (31)

We will now specify $H$ to be drawn from the GUE ensemble $\mathrm{GUE}(d)$
(c.f. Definition 3). The scaling of variance as $\frac{1}{d}$ guarantees
convergence of the distribution of eigenvalues to the Wigner semicircle law.
For such $H$ we have the following Theorem, whose proof we defer to Appendix
A:

######  Theorem 4.6.

Let $H_{d}\sim\mathrm{GUE}(d)$ and let $\mu_{sc}$ be the Wigner semicircle law
with density
$\rho_{sc}(x)=\frac{1}{2\pi}\sqrt{4-x^{2}}\mathbbm{1}_{\\{\absolutevalue{x}\leq
2\\}}$. Then we have:

$\lim_{d\to\infty}\int_{\mathbb{R}}e^{i\lambda
t}d\mu_{H_{d}}(\lambda)=\int_{\mathbb{R}}e^{i\lambda
t}d\mu_{sc}(\lambda)=\frac{J_{1}(2t)}{t}$ (32)

uniformly over $t$, where $J_{1}$ is the Bessel function of the first kind.
The convergence rate is at least $O\left(\frac{\log d}{d}\right)$.

We note that the above statement is stronger than the classic convergence of
GUE law to the Wigner semicircle law, since we require uniformity over all
$t$.

######  Theorem 4.7.

Fix $\delta,\varepsilon>0$. If $\varepsilon>cd^{-1/8}$, for some constant $c$
depending on $\delta$, and $H\sim\mathrm{GUE}(d)$, then for any
$t>C\varepsilon$, where $C>0$ is an absolute constant, we have:

$\mathbb{P}(\mathrm{D}_{\mathrm{HS}}(\boldsymbol{U}_{t},\boldsymbol{I})<\varepsilon\sqrt{d})<\delta$
(33)

###### Proof.

By (53), we need to upper bound the probability:

$\mathbb{P}\left(\absolutevalue{\tr(U_{t})}>(1-\frac{1}{2}\varepsilon^{2})d\right)$
(34)

By standard properties of Bessel functions, we can pick an absolute constant
$C$ such that $\absolutevalue{\frac{J_{1}(2t)}{t}}<1-2\varepsilon^{2}$ if
$t>C\varepsilon$. Then, by Theorem 4.6, for sufficiently large $d$ we have
$\absolutevalue{\int_{\mathbb{R}}e^{i\lambda
t}d\mu_{H}(\lambda)}<1-\varepsilon^{2}$ – in fact, since the convergence rate
is $\frac{\log d}{d}$, it suffices to have $\varepsilon>cd^{-1/4}$ for some
$c$. This implies that
$\absolutevalue{\mathbb{E}\tr(U_{t})}<(1-\varepsilon^{2})d$.

We will now use two different arguments in two time regimes. For the first
argument, we have by Chebyshev inequality:

$\mathbb{P}\left(\absolutevalue{\tr(U_{t})}>(1-\frac{1}{2}\varepsilon^{2})d\right)\leq\mathbb{P}\left(\absolutevalue{\tr(U_{t})-\mathbb{E}\tr(U_{t})}>\frac{1}{2}\varepsilon^{2}d\right)\leq\frac{4\mathrm{Var}\tr(U_{t})}{\varepsilon^{4}d^{2}}$
(35)

where for a complex variable $Z$ the variance
$\mathrm{Var}Z=\mathbb{E}\absolutevalue{Z}^{2}-\absolutevalue{\mathbb{E}Z}^{2}$.
It follows that

$\mathrm{Var}\tr(U_{t})=\mathrm{Var}\mathrm{Re}\tr(U_{t})+\mathrm{Var}\mathrm{Im}\tr(U_{t})=\mathrm{Var}\cos(Ht)+\mathrm{Var}\sin(Ht)$
(36)

where $\cos(Ht),\sin(Ht)$ are matrix functions defined for Hermitian matrices
in the usual way. We now invoke the following variance bound ([LP09],
Proposition 2.4; it is stated for GOE, but holds for $\mathrm{GUE}$ as well):

######  Proposition 4.8.

Let $H$ be a $d\times d$ $\mathrm{GUE}$ matrix with entries of variance
$w^{2}$ and let $\varphi:\mathbb{R}\to\mathbb{R}$ be continuously
differentiable with bounded derivative. Then:

$\displaystyle\mathrm{Var}\Tr\varphi(H)\leq
2w^{2}\sup_{\lambda\in\mathbb{R}}\absolutevalue{\varphi^{\prime}(\lambda)}^{2}$
(37)

In our case $w^{2}=\frac{1}{d}$ and $\phi(x)=\cos{xt}$ or $\sin(xt)$, which
leads to $\mathrm{Var}\cos(Ht),\mathrm{Var}\sin(Ht)\leq\frac{2t^{2}}{d}$.
Finally we obtain:

$\mathbb{P}\left(\absolutevalue{\tr(U_{t})}>(1-\frac{1}{2}\varepsilon^{2})d\right)\leq\frac{16t^{2}}{\varepsilon^{4}d^{3}}<\delta$
(38)

assuming $t<\frac{\sqrt{\delta}\varepsilon^{2}}{4}d^{3/2}$.

For larger times, we bound the variance by analyzing directly the $2$-point
correlation function of $\mathrm{GUE}$. The details are deferred to Theorem
A.1 in Appendix A. The Theorem implies that for any $\alpha>0$, if $d$ is
sufficiently large, then for $t>c_{\alpha}d^{1+\alpha}$ we have
$\mathrm{Var}\tr(U_{t})<2d$. By (35), this is sufficient if
$d>\frac{8}{\delta\varepsilon^{4}}$. Since the first bound works for
$t<\frac{\sqrt{\delta}\varepsilon^{2}}{4}d^{3/2}$, it suffices to take any
$\alpha<1/2$ and $d$ sufficiently large for the two bounds to cover the whole
interval of times $t>C\varepsilon$ – we can e.g. take $\alpha=1/4$ and
$\varepsilon>cd^{-1/8}$. This finishes the proof. ∎

######  Remark 4.2.

The proof of Theorem 4.7 for the random basis i.i.d Gaussian model is
considerably simpler, so we only sketch the necessary changes. It is
straightforward to verify that if the eigenvalues $\lambda_{i}$ are
independent standard Gaussians, then
$\frac{1}{d}\mathbb{E}\tr(U_{t})=e^{-t^{2}/2}$, which can be made
$<1-2\varepsilon^{2}$ if $t>C\varepsilon$ for some $C>0$. One also readily
computes that $\mathrm{Var}\tr(U_{t})=d(1-e^{-t^{2}})$, so the Chebyshev bound
also holds.

######  Remark 4.3.

The probability bounds used in the proof of Theorem 4.7 rely on estimating the
second moment of $\tr(U_{t})$ and are thus only inversely polynomial in $d$.
For times $t=o(d)$ in the GUE case, or all times in the random basis i.i.d
Gaussian case, exponential bounds are available using concentration of
measure. We describe this approach in Appendix B.

We can now prove the main theorem describing the circuit complexity for
$\mathrm{GUE}$ time evolution:

######  Theorem 4.9.

Fix $\varepsilon,\delta>0$ and the gateset $\mathcal{G}$. Let $H$ be drawn
from the $\mathrm{GUE}(d)$ ensemble and assume $\varepsilon>cd^{-1/8}$, for
some constant $c$ depending on $\delta$. Then for any time $t>C\varepsilon$,
with $C$ an absolute constant, we have the following bound on the complexity
of $U_{t}=e^{iHt}$ with respect to the Hilbert-Schmidt metric:

$\mathbb{P}(C^{\mathrm{HS}}_{\varepsilon\sqrt{d}}(\boldsymbol{U}_{t})>k)>1-\delta$
(39)

with

$k=\frac{1}{{\log\absolutevalue{\mathcal{G}}}}\left(C^{\prime}\varepsilon^{2}d^{2}-\log(\frac{1}{\delta})\right)$
(40)

and $C^{\prime}$ an absolute constant. The same result holds for random basis
i.i.d Gaussian ensemble.

###### Proof.

We claim that for $t>C\varepsilon$ and $d$ sufficiently large:

$\displaystyle\mathbb{P}\left(\boldsymbol{U}_{t}\in\bigcup_{\boldsymbol{G}\in\mathcal{G}^{\leq
k}}B(\boldsymbol{G},\varepsilon\sqrt{d})\right)<\delta$ (41)

Let us divide $\mathcal{G}^{\leq k}=\mathcal{G}^{\leq
k}_{0}\cup\mathcal{G}^{\leq k}_{1}$, where $\mathcal{G}^{\leq
k}_{0}:=\\{\boldsymbol{G}\in\mathcal{G}^{\leq k}\ |\ \boldsymbol{G}\in
B(\boldsymbol{I},6\varepsilon\sqrt{d})\\}$ and $\mathcal{G}^{\leq k}_{1}$
contains the remaining elements. For every $\boldsymbol{G}\in\mathcal{G}^{\leq
k}_{0}$ we have $B(\boldsymbol{G},\varepsilon\sqrt{d})\subseteq
B(\boldsymbol{I},7\varepsilon\sqrt{d})$, so:

$\displaystyle\mathbb{P}\left(\boldsymbol{U}_{t}\in\bigcup_{\boldsymbol{G}\in\mathcal{G}^{\leq
k}}B(\boldsymbol{G},\varepsilon\sqrt{d})\right)\leq\mathbb{P}\left(\boldsymbol{U}_{t}\in
B(\boldsymbol{I},7\varepsilon\sqrt{d})\right)+\mathbb{P}\left(\boldsymbol{U}_{t}\in\bigcup_{\boldsymbol{G}\in\mathcal{G}^{\leq
k}_{1}}B(\boldsymbol{G},\varepsilon\sqrt{d})\right)\leq$ (42)
$\displaystyle\mathbb{P}\left(\boldsymbol{U}_{t}\in
B(\boldsymbol{I},7\varepsilon\sqrt{d})\right)+\sum_{\boldsymbol{G}\in\mathcal{G}^{\leq
k}_{1}}\mathbb{P}\left(\boldsymbol{U}_{t}\in
B(\boldsymbol{G},\varepsilon\sqrt{d})\right)$ (43)

For every $\boldsymbol{G}\in\mathcal{G}_{1}^{<k}$ we have
$\mathrm{D}_{\mathrm{HS}}(\boldsymbol{G},\boldsymbol{I})>6\varepsilon\sqrt{d}$,
so we can invoke Theorem 4.5, to obtain:

$\sum_{\boldsymbol{G}\in\mathcal{G}^{\leq
k}_{1}}\mathbb{P}\left(\boldsymbol{U}_{t}\in
B(\boldsymbol{G},\varepsilon\sqrt{d})\right)\leq\absolutevalue{\mathcal{G}^{\leq
k}}\exp\left(-\frac{\varepsilon^{2}d^{2}}{384}\right)<\frac{\delta}{2}$ (44)

if
$k<\frac{C^{\prime}}{\log\absolutevalue{\mathcal{G}}}\left(\varepsilon^{2}d^{2}-\log(\frac{1}{\delta})\right)$
for appropriately chosen constant $C^{\prime}$. Note that this part of the
bound is time-independent.

It remains to bound $\mathbb{P}\left(\boldsymbol{U}_{t}\in
B(\boldsymbol{I},7\varepsilon\sqrt{d})\right)$. To this end we simply invoke
Theorem 4.7 and plug $\varepsilon\to 7\varepsilon,\delta\to 1/2\delta$.

The proof for the random basis i.i.d. Gaussian model proceeds in the same
fashion. ∎

Theorem 4.9 says that after a time $t>C\varepsilon$, the operator $U_{t}$
typically has high complexity. We show a complementary result that $U_{t}$
stays in the neighborhood of the identity (so has trivial complexity equal to
zero) for smaller times. In this sense, the complexity exhibits a sudden jump
– for sufficiently short time it has complexity zero and afterwards jumps to
almost maximal complexity.

######  Proposition 4.10.

Fix $\varepsilon\leq 2$. For times $t\leq\frac{\varepsilon}{4}$ (GUE) or
$t\leq\frac{\varepsilon}{2\sqrt{2\log(d)}}$ (i.i.d. Gaussian) the probability
of leaving the $\varepsilon$-ball around identity in the diamond norm for
$\mathrm{GUE}(d)$ is bounded by $e^{-d}$ and for i.i.d. Gaussian by
$\frac{1}{2d^{2}}$.

###### Proof.

From [JKP09] we know that the diamond distance between $\boldsymbol{U}$ and
$\boldsymbol{I}$ is equal to the diameter of the set of eigenvalues of $U$.
Let $\phi_{min},\phi_{max}\in[-\pi,\pi)$ be ordered phases of eigenvalues of
$U$, and assume that $\phi_{\max}-\phi_{\min}\leq\pi$. Then:

$\displaystyle\|\boldsymbol{U}-\boldsymbol{I}\|_{\diamond}=2\sin\left(\frac{\phi_{\max}-\phi_{\min}}{2}\right)\leq\phi_{\max}-\phi_{\min}$
(45)

Let $\lambda_{j}$ be eigenvalues of $H$, with $\lambda_{\max},\lambda_{\min}$,
being maximal and minimal eigenvalues respectively. Now, if
$t\|H\|_{\infty}\leq\pi/2$, then we can write:

$\displaystyle\|\boldsymbol{U}-\boldsymbol{I}\|_{\diamond}\leq
t(\lambda_{\max}-\lambda_{\min})\leq 2t\|H\|_{\infty}$ (46)

Then:

$\displaystyle\mathbb{P}(\|\boldsymbol{U}-\boldsymbol{I}\|_{\diamond}\leq\varepsilon)\geq\mathbb{P}(\|\boldsymbol{U}-\boldsymbol{I}\|_{\diamond}\leq\varepsilon\
\cap\ t\|H\|_{\infty}\leq\pi/2)\geq\mathbb{P}(t\|H\|_{\infty}\leq\varepsilon\
\cap\ t\|H\|_{\infty}\leq\pi/2)$ (47)

so that for $\varepsilon\leq\pi/2$ we get

$\displaystyle\mathbb{P}(\|\boldsymbol{U}-\boldsymbol{I}\|_{\diamond}\leq\varepsilon)\geq\mathbb{P}(t\|H\|_{\infty}\leq\varepsilon)$
(48)

Using the following tail bound [AS17] for $\mathrm{GUE}(d)$:

$\displaystyle\mathbb{P}(\|H\|_{\infty}\geq
2+a)\leq\frac{1}{2}e^{-\frac{1}{2}ad^{2}}$ (49)

with any $a\geq 0$ and taking $t\leq\varepsilon/4$ one gets

$\displaystyle\mathbb{P}(\|H\|_{\infty}\geq\frac{\varepsilon}{t})=\mathbb{P}(\|H\|_{\infty}\geq
4)\leq\frac{1}{2}e^{-d^{2}}$ (50)

which ends the proof for GUE. For the i.i.d. Gaussian model, we have the
following tail bound:

$\displaystyle\mathbb{P}(\|H\|_{\infty}\geq\sqrt{2\log(d)}+a)\leq\frac{1}{2}e^{-\frac{a^{2}}{2}}.$
(51)

Then taking $t\leq\frac{\varepsilon}{2\sqrt{2\log(d)}}$ we obtain the result.
∎

We end with a proposition concerning the random basis i.i.d. Gaussian model.
The arguments used in Theorem 4.9 work for times $t>C\varepsilon$. However, if
we consider the diamond distance, in this model Proposition 4.10 suggests that
the threshold time to exit identity should behave like
$\sim\frac{\varepsilon}{\sqrt{\log d}}$. We show that this is in fact the case
by working directly with the diamond metric (i.e. not using the Hilbert-
Schmidt metric, as was done in previous arguments). The proof is presented in
Appendix D.

######  Proposition 4.11.

Fix $\varepsilon,\delta>0$ and let $\varepsilon<1/2$. Let
$t>C\frac{\varepsilon}{\sqrt{\log d}}$ for some constant $C>0$ depending on
$\delta$. Then if $H$ is drawn from the random basis i.i.d. Gaussian model, we
have:

$\mathbb{P}\left(\mathrm{D}_{\diamond}(\boldsymbol{U}_{t},\boldsymbol{I})>\varepsilon\right)>1-\delta$
(52)

######  Remark 4.4.

The above Proposition concerns only leaving the ball around the identity and
is not enough to show high complexity with respect to the diamond metric after
time $t\sim\frac{\varepsilon}{\sqrt{\log(d)}}$. The arguments from Section
4.1, used to eliminate all other balls, relied heavily on the use of Hilbert-
Schmidt metric. In fact, the $\sim\exp(-\Theta(d^{2}))$ bound as in Theorem
4.5 cannot hold in general in the diamond metric. Consider e.g. $G$ which is
diagonal with eigenvalues $(-1,1,1\dots,1)$. Then $UGU^{\dagger}=G$ for all
unitaries $U$ which fix the first basis vector and the set of such unitaries
has co-dimension $2d-1$ in $\mathrm{U}(d)$ – this suggests we can only expect
an $\sim\exp(-\Theta(d))$ type of bound if we want to use the same argument as
in Theorem 4.5 to exclude balls around $G\neq I$ with high probability.

###  4.3 Gaussian Hamiltonians in computational basis

####  4.3.1 Lower bound on unitary complexity

We now consider the Hamiltonian drawn from the diagonal i.i.d. Gaussian model,
i.e. $H$ is diagonal with eigenvalues being i.i.d. standard Gaussians c.f. 4.
We will provide a lower bound on the complexity of $e^{iHt}$. In this case,
the basis is fixed, so we cannot take advantage of the Haar randomness and
concentration of measure on the unitary group to exclude all
$\boldsymbol{G}\in\mathcal{G}^{\leq k}$ but those close to the identity – we
need to deal with all of them. Note that the bounds used in Section 4.2 rely
on bounding the moments of $\absolutevalue{\tr(U_{t})}$ and therefore cannot
accommodate a union bound consisting of exponentially many in $d$ terms. To
circumvent this problem we linearize $\absolutevalue{\tr(U_{t})}$ to deal with
its real and imaginary parts separately and then apply concentration for
independent random variables. The bound on complexity will scale as $d$, not
$d^{2}$ as in the random basis case, and in fact we show a nearly matching
upper bound in Section 4.3.2.

Let $\boldsymbol{G}\in\mathcal{G}^{\leq k}$ be arbitrary. We aim to bound:

$\mathbb{P}(\mathrm{D}_{\mathrm{HS}}(\boldsymbol{U}_{t},\boldsymbol{G})<\varepsilon\sqrt{d})=\mathbb{P}\left(\absolutevalue{\tr(U_{t}G^{\dagger})}>(1-\frac{1}{2}\varepsilon^{2})d\right)$
(53)

Letting
$\bra{k}G^{\dagger}\ket{k}=r_{k}e^{i\varphi_{k}},\absolutevalue{r_{k}}\leq 1$
(the choice of global phase implicit in passing from
$\boldsymbol{U}_{t},\boldsymbol{G}$ to specific $U_{t},G$ can be absorbed into
$\varphi_{k}$) and using the fact that $U_{t}$ is diagonal with eigenvalues
$e^{i\lambda_{k}t}$, we have:

$\absolutevalue{\tr(U_{t}G^{\dagger})}=\absolutevalue{\sum_{k}r_{k}e^{i(\lambda_{k}t+\varphi_{k})}}$
(54)

We make the following simple observation – if $\absolutevalue{z}\geq c$, then
at least one of: $\absolutevalue{\mathrm{Re}z}\geq\frac{1}{\sqrt{2}}c$ or
$\absolutevalue{\mathrm{Im}z}\geq\frac{1}{\sqrt{2}}c$ must hold. By union
bound, we thus obtain:

$\displaystyle\mathbb{P}\left(\absolutevalue{\sum_{k}r_{k}e^{i(\lambda_{k}t+\varphi_{k})}}>(1-\frac{1}{2}\varepsilon^{2})d\right)\leq$
(55)
$\displaystyle\mathbb{P}\left(\absolutevalue{\mathrm{Re}(\sum_{k}r_{k}e^{i(\lambda_{k}t+\varphi_{k})})}>\frac{1}{\sqrt{2}}(1-\frac{1}{2}\varepsilon^{2})d\right)+\mathbb{P}\left(\absolutevalue{\mathrm{Im}(\sum_{k}r_{k}e^{i(\lambda_{k}t+\varphi_{k})})}>\frac{1}{\sqrt{2}}(1-\frac{1}{2}\varepsilon^{2})d\right)$
(56)

We focus on the real part first. We have:

$\displaystyle\mathbb{P}\left(\absolutevalue{\mathrm{Re}(\sum_{k}r_{k}e^{i(\lambda_{k}t+\varphi_{k})})}>\frac{1}{\sqrt{2}}(1-\frac{1}{2}\varepsilon^{2})d\right)\leq$
(57)
$\displaystyle\mathbb{P}\left(\mathrm{Re}(\sum_{k}r_{k}e^{i(\lambda_{k}t+\varphi_{k})})>\frac{1}{\sqrt{2}}(1-\frac{1}{2}\varepsilon^{2})d\right)+\mathbb{P}\left(\mathrm{Re}(\sum_{k}r_{k}e^{i(\lambda_{k}t+\varphi_{k})})<-\frac{1}{\sqrt{2}}(1-\frac{1}{2}\varepsilon^{2})d\right)$
(58)

We can write the first terms as:

$\mathbb{P}\left(\sum_{k}r_{k}\cos(\lambda_{k}t+\varphi_{k})>\frac{1}{\sqrt{2}}(1-\frac{1}{2}\varepsilon^{2})d\right).$
(59)

Define random variables $X_{k}:=r_{k}\cos(\lambda_{k}t+\varphi_{k})$. Since
the distribution of $\lambda_{k}$ is symmetric with respect to $0$, we have
$\mathbb{E}\cos(\lambda_{k}t)=\mathbb{E}e^{i\lambda_{k}t}=e^{-t^{2}/2}$ and
for the same reason $\mathbb{E}\sin(\lambda_{k}t)=0$. Therefore,
$\mathbb{E}X_{k}=r_{k}\cos\varphi_{k}e^{-t^{2}/2}$. It follows that
$\mathbb{E}\sum_{k}X_{k}\leq de^{-t^{2}/2}$. By choosing $t$ large enough we
can make
$e^{-t^{2}/2}<\frac{1}{\sqrt{2}}(1-\frac{1}{2}\varepsilon^{2})-\frac{1}{2\sqrt{2}}$,
therefore:

$\mathbb{P}\left(\sum_{k}X_{k}>\frac{1}{\sqrt{2}}(1-\frac{1}{2}\varepsilon^{2})d\right)\leq\mathbb{P}\left(\sum_{k}X_{k}-\mathbb{E}\sum_{k}X_{k}>\frac{1}{2\sqrt{2}}d\right)$
(60)

We are now in position to use concentration inequality for bounded independent
variables in the form of Hoeffding bound:

######  Proposition 4.12 (Hoeffding’s inequality).

Let $X_{i}$ be independent random variables such that almost surely $a_{i}\leq
X_{i}\leq b_{i}$. Let $S_{n}=X_{1}+\dots+X_{n}$. Then for all $s>0$:

$\displaystyle\mathbb{P}\left(S_{n}-\mathbb{E}S_{n}\geq
s\right)\leq\exp\left(-\frac{s^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}\right)$
(61)

In our case $a_{i}=1,b_{i}=-1$, so the final inequality reads:

$\mathbb{P}\left(\sum_{k}X_{k}-\mathbb{E}\sum_{k}X_{k}>\frac{1}{2\sqrt{2}}d\right)\leq\exp\left(-\frac{d}{32}\right)$
(62)

Bounding the other term with the real part and the the terms with imaginary
part proceeds in the same way. By the same reasoning as in the proof of
Theorem 4.9, we have arrived at the following complexity bound. Note that
there is no dependence of the complexity on $\varepsilon^{2}$, but at the cost
of considering times $t$ greater than a constant instead of $\sim\varepsilon$.

######  Theorem 4.13.

Fix $\varepsilon,\delta>0$ and the gateset $\mathcal{G}$. If $H$ is drawn from
the diagonal i.i.d. Gaussian model, then for any time $t>C$, with $C$ an
absolute constant, we have:

$\mathbb{P}(C^{HS}_{\varepsilon\sqrt{d}}(\boldsymbol{U}_{t})>k)>1-\delta$ (63)

with

$k=\frac{1}{{\log\absolutevalue{\mathcal{G}}}}\left(C^{\prime}d-\log(\frac{1}{\delta})\right)$
(64)

and $C^{\prime}$ an absolute constant.

######  Remark 4.5.

The above Theorem shows high complexity only after constant time. This is in
contrast with unitary invariant ensembles, where high complexity occurs right
after leaving the ball around identity, i.e. at time $t\sim\varepsilon$. In
the absence of random basis, we are forced to consider all balls in the union
bound. If we do not know anything about their distribution, we have to handle
their possible worst case placement, e.g. all balls clustered around identity
so that it takes constant time to even leave that cluster with high
probability. Excluding such cases and proving that time $t\sim\varepsilon$ is
sufficient would require a rather fine grained control of the distribution of
unitaries in $\mathcal{G}^{\leq k}$ (= the distribution of a random walk on
the unitary group with steps from $\mathcal{G}$).

####  4.3.2 Upper bound on complexity via explicit compilation for qubits

For the upper bound, we specialize the Hilbert space to the case of an $n$
qubit system, so that $d=2^{n}$.

######  Lemma 4.14.

Consider an arbitrary Hamiltonian $H$ acting on $n$ qubits which is diagonal
in computation basis. Let the gateset contain $CNOT^{\prime}s$ and $Z$ gates.
Then the $\varepsilon$-complexity of the unitary $U_{t}=e^{itH}$ (defined with
respect to the diamond metric) satisfies:

$\displaystyle C_{\varepsilon}(U_{t})\leq
Cn2^{n}\log^{c}\left(\frac{1}{\varepsilon}\right)=Cd\log
d\log^{c}\left(\frac{1}{\varepsilon}\right)$ (65)

where $c$ and $C$ are absolute constants.

###### Proof.

Any Hamiltonian acting on $n$ qubits diagonal in computational basis can be
written as

$\displaystyle H=\sum_{\alpha}\lambda_{\alpha}Z^{\alpha}$ (66)

where the sum runs over $n$-tuples $\alpha=(\alpha_{1},\ldots,\alpha_{n})$,
$\alpha_{j}=0,1$ and

$\displaystyle Z^{\alpha}=Z_{1}^{\alpha_{1}}\ldots Z_{n}^{\alpha_{n}}$ (67)

with $Z_{j}$ being Pauli matrix on $j$’th qubit. From Lemma 4.15 we have that

$\displaystyle e^{itZ^{\alpha}}=V_{\alpha}e^{itZ_{1}}V_{\alpha}^{\dagger}$
(68)

where $V_{\alpha}$ is composed out of at most $4n$ gates. To compile $e^{itH}$
we proceed as follows. First we compile $e^{itZ_{1}}$ up to precision $\delta$
using $k=\ln^{c}\frac{1}{\delta}$ gates, obtaining $U_{0}$ satisfying
$\|U_{0}-e^{itZ_{1}}\|_{\infty}\leq\delta$ (as follows from the Solovay-Kitaev
theorem). Next we sandwich $U_{0}$ with $V_{\alpha},V_{\alpha}^{\dagger}$,
obtaining $U_{\alpha}=V_{\alpha}U_{0}V_{\alpha}^{\dagger}$ which is $\delta$
approximation of $e^{itZ^{\alpha}}$ and costs $4n+k$ gates. Finally, since
$e^{itH}=\Pi_{\alpha}e^{itZ^{\alpha}}$, we compose $U_{\alpha}$’s, which by a
telescopic estimate, satisfies

$\displaystyle\|\Pi_{\alpha}e^{itZ_{\alpha}}-U_{2^{n}-1}\ldots
U_{0}\|_{\infty}\leq 2^{n}\delta$ (69)

where we have written $\alpha$’s in a unary way. It remains to choose $k$ such
that the above norm is smaller than $\varepsilon$. This is done by
$k=n\log^{c}2+\log^{c}\frac{1}{\varepsilon}$. Overall, the number of needed
gates is $K=2^{n}\times 4n\times
k=4n2^{n}(n\log^{c}2+\log^{c}\frac{1}{\varepsilon})$, or it is enough to take
$K=Cn2^{n}\log^{c}\frac{1}{\varepsilon}$, where $C$ is absolute constant. We
have obtained an approximation in the operator norm, which implies
approximation in the diamond metric. Hence:

$\displaystyle C_{\varepsilon}(e^{itH})\leq
Cn2^{n}\log^{c}\frac{1}{\varepsilon}.$ (70)

∎

######  Lemma 4.15.

In the above notation for any $\alpha$ we have

$\displaystyle e^{itZ^{\alpha}}=V_{\alpha}e^{itZ_{1}}V^{\dagger}_{\alpha}.$
(71)

###### Proof.

Since for any unitary we have $Ue^{X}U^{\dagger}=e^{UXU^{\dagger}}$, it is
enough to find $V_{\alpha}$ such that

$\displaystyle Z^{\alpha}=V_{\alpha}Z_{1}V_{\alpha}^{\dagger}.$ (72)

We construct $V_{\alpha}$ as follows. Since CNOT’s propagate $Z$-errors
backwards, we sandwich $Z_{1}$ with a cascade of CNOT’s to produce
$Z_{1}\ldots Z_{n}$. Then we need to remove $Z$’s in places where
$\alpha_{j}=0$. We do this by adding another CNOT’s with source qubits
coinciding with the places where we do not want Z’s. Such $V_{\alpha}$
requires no more than $2n$ CNOTs. The circuit is illustrated in Fig. 2.

Figure 2: Compilation of $Z^{\alpha}$ from $Z_{1}$ and c-not gates.

∎

##  5 State complexity

The general strategy for lower bounding
$C_{\varepsilon}(\boldsymbol{U}_{t}(\psi_{0}))$ will be the same as in the
unitary case – we first aim to exploit the Haar randomness of the eigenbasis
of $H$ and then upper bound the probability of staying close to the initial
state $\psi_{0}$. The reader is advised to first read Section 4.

######  Remark 5.1.

In the case of state complexity, we do not consider the diagonal Gaussian
model $\mathrm{DiagGauss(d)}$ as the results would depend very strongly on the
choice of the initial state. For example, if the state $\psi_{0}$ is chosen to
be one of the computational basis states $\ket{k}$, which are the eigenstates
of the Hamiltonian $H$, it will not evolve at all, so the complexity of
$\boldsymbol{U}_{t}(\psi_{0})$ will always be trivial. In general, if we
write:

$\ket{\psi_{0}}=\sum_{k}c_{k}\ket{k}$ (73)

then, for example, analyzing the trace distance between $\psi_{0}$ and
$\boldsymbol{U}_{t}(\psi_{0})$ is equivalent to analyzing:

$\bra{\psi_{0}}U_{t}\ket{\psi_{0}}=\sum_{k}\absolutevalue{c_{k}}^{2}e^{i\lambda_{k}t}$
(74)

If $\absolutevalue{c_{k}}^{2}=\frac{1}{d}$ for all $k$, we are reduced to
analyzing the trace of $U_{t}$, which was done in previous sections. For
general coefficients $c_{k}$ the probabilistic properties of 74 will depend on
some measure of uniformity of $c_{k}$.

###  5.1 Random tori in state spaces

As in the unitary case, we first aim to exploit the Haar randomness of the
basis to eliminate from consideration all balls but the one at the initial
state $\ket{0}$. For a fixed state $\ket{\phi}$, let us define:

$T_{\ket{\phi}}:=\left\\{\ket{\alpha}\ |\ \forall k=1,\dots,d\
\absolutevalue{\innerproduct{k}{\alpha}}=\absolutevalue{\innerproduct{k}{\phi}}\right\\}$
(75)

Let $H=V^{\dagger}DV$, with $V$ a Haar random unitary. For a fixed
$\ket{\phi}\in S^{\leq k}$ we have:

$d(\ket{\phi},U_{t}\ket{0})^{2}=1-\absolutevalue{\bra{\phi}V^{\dagger}e^{iDt}V\ket{0}}^{2}$
(76)

Note that:

$e^{iDt}V\ket{0}=\sum_{k}e^{i\lambda_{k}t}\outerproduct{k}{k}V\ket{0}$ (77)

Thus, the states of the form $e^{iDt}V\ket{0}$ lie inside a (random)
$d$-dimensional torus $T_{V\ket{0}}$ as defined in (75). We will prove that
for any state $\ket{\phi}$ which is at least $\varepsilon$ away from
$\ket{0}$, the probability over $V$ that $V\ket{\phi}$ is $\varepsilon$-close
to $T_{V\ket{0}}$ is exponentially small (note that the same $V$ occurs twice
in this statement), and thus $U_{t}\ket{0}$ avoids the the $\varepsilon$-ball
around $\ket{0}$. This allows us to focus only on the neighborhood of
$\ket{0}$. The logic of the argument is essentially the same as in the
operator case.

Define:

$\mathrm{dist}(\ket{\psi},T_{\ket{\phi}}):=\inf_{\ket{\alpha}\in
T_{\ket{\phi}}}d(\ket{\psi},\ket{\alpha})$ (78)

######  Lemma 5.1.

Fix two states $\ket{\psi},\ket{\phi}$. We then have:

$\mathrm{dist}(\ket{\psi},T_{\ket{\phi}})^{2}=1-\left(\sum_{k}\absolutevalue{\innerproduct{k}{\psi}}\cdot\absolutevalue{\innerproduct{k}{\phi}}\right)^{2}$
(79)

###### Proof.

By definition, for any $\ket{\alpha}\in T_{\ket{\phi}}$ we have
$\ket{\alpha}=\sum_{k}e^{i\varphi_{k}}\ket{k}\innerproduct{k}{\phi}$, so:

$\mathrm{dist}(\ket{\psi},T_{\ket{\phi}})^{2}=1-\sup_{\ket{\alpha}\in
T_{\ket{\phi}}}\absolutevalue{\innerproduct{\psi}{\alpha}}^{2}=1-\sup_{\varphi_{k}}\absolutevalue{\sum_{k}e^{i\varphi_{k}}\innerproduct{\phi}{k}\innerproduct{k}{\psi}}^{2}$
(80)

and clearly the $\sup$ is attained for the choice $\varphi_{k}$ such that
$e^{i\varphi_{k}}\innerproduct{\phi}{k}\innerproduct{k}{\psi}=\absolutevalue{\innerproduct{\phi}{k}\innerproduct{k}{\psi}}$,
which finishes the proof. ∎

As in the unitary case, we would first like to estimate
$\mathbb{E}_{V}\mathrm{dist}(V\ket{0},T_{V\ket{\phi}})$ in terms of
$d(\ket{0},\ket{\phi})$. Curiously, trying to estimate:

$\mathbb{E}_{V}\mathrm{dist}(V\ket{0},T_{V\ket{\phi}})^{2}=1-\mathbb{E}_{V}\left(\sum_{k}\absolutevalue{\bra{k}V\ket{0}}\cdot\absolutevalue{\bra{k}V\ket{\phi}}\right)^{2}$
(81)

by reducing the expression to polynomials in
$\absolutevalue{\bra{k}V\ket{0}}^{2},\absolutevalue{\bra{k}V\ket{\phi}}^{2}$
(as was done in the unitary case) does not result in useful bounds. We are
therefore forced to analyze the expressions
$\mathbb{E}_{V}\absolutevalue{\bra{k}V\ket{0}}\cdot\absolutevalue{\bra{k}V\ket{\phi}}$
directly, which is more difficult since they are not polynomials. To achieve
this, note that $V\ket{k}$ is a Haar random state from the complex sphere. It
is well known that coordinates of such vectors are well approximated by
complex Gaussian variables. This is formalized in the following Lemma. Note
that by the Haar randomness of $V$ we can without loss of generality only
consider states of the form $\ket{\phi}=\alpha\ket{0}+\beta\ket{1}$.

######  Lemma 5.2.

Let $\ket{\phi}=\alpha\ket{0}+\beta\ket{1}$, with
$\absolutevalue{\alpha}^{2}+\absolutevalue{\beta}^{2}=1$. Let $V$ be a
$d\times d$ Haar random unitary and let $X,Y$ be independent standard complex
Gaussians, i.e. $X,Y\sim a+ib$, where $a,b$ are real Gaussians of mean zero
and variance $1/2$. Then we have:

$\lim_{d\to\infty}d\cdot\mathbb{E}_{V}\absolutevalue{\bra{k}V\ket{0}}\absolutevalue{\bra{k}V\ket{\phi}}=\mathbb{E}\absolutevalue{X}\absolutevalue{\alpha
X+\beta Y}$ (82)

uniformly over the choice of $\alpha,\beta$ and with convergence rate at least
$d^{-1/2}$.

###### Proof.

Note that for any $\ket{k}$ the state $V\ket{k}$ is a Haar random state. It is
known [DF87]that if $X$ is a randomly distributed point on the real
$n$-dimensional sphere of radius $\sqrt{n}$ and $Z$ is a standard real
Gaussian random vector, then for any $k\leq n$:

$d_{TV}((X_{1},\dots,X_{k}),(Z_{1},\dots,Z_{k}))\leq\frac{2(k+3)}{n-k-3}$ (83)

where $d_{TV}$ is the total variation distance. The bound immediately applies
also to the complex case. Applying this bound for $k=2$, we obtain that the
joint law of $\sqrt{d}(\bra{k}V\ket{0},\bra{k}V\ket{1})$ converges in total
variation distance to $(X,Y)$, where $X,Y$ are standard independent complex
Gaussians.

By unitary invariance, without loss of generality we can write
$\ket{\phi}=\alpha\ket{0}+\beta\ket{1}$, where
$\absolutevalue{\alpha}^{2}+\absolutevalue{\beta}^{2}=1$. Let $\mu_{d}$ denote
the joint law of $\sqrt{d}(\bra{k}V\ket{0},\bra{k}V\ket{1})$, let $\mu$ denote
the joint law of $(X,Y)$ and let
$f_{\alpha}(x,y)=\absolutevalue{\alpha\absolutevalue{x}^{2}+\beta xy}$. We are
left with proving uniformly over $\alpha$ that:

$\lim_{d\to\infty}\mathbb{E}_{\mu_{d}}f_{\alpha}=\mathbb{E}_{\mu}f_{\alpha}$
(84)

The argument below is standard, but since we need to ensure uniformity over
$\alpha$ and the functions $f_{\alpha}$ are not bounded, we spell it out in
detail. Pick $K>0$ and write:

$\displaystyle\absolutevalue{\mathbb{E}_{\mu_{d}}f_{\alpha}-\mathbb{E}_{\mu}f_{\alpha}}\leq$
(85)
$\displaystyle\absolutevalue{\mathbb{E}_{\mu_{d}}f_{\alpha}-\mathbb{E}_{\mu_{d}}f_{\alpha}\mathbbm{1}_{\\{f_{\alpha}\leq
K\\}}}+\absolutevalue{\mathbb{E}_{\mu_{d}}f_{\alpha}\mathbbm{1}_{\\{f_{\alpha}\leq
K\\}}-\mathbb{E}_{\mu}f_{\alpha}\mathbbm{1}_{\\{f_{\alpha}\leq
K\\}}}+\absolutevalue{\mathbb{E}_{\mu}f_{\alpha}\mathbbm{1}_{\\{f_{\alpha}\leq
K\\}}-\mathbb{E}_{\mu}f_{\alpha}}=$ (86)
$\displaystyle\absolutevalue{\mathbb{E}_{\mu_{d}}f_{\alpha}\mathbbm{1}_{\\{f_{\alpha}\geq
K\\}}}+\absolutevalue{\mathbb{E}_{\mu_{d}}f_{\alpha}\mathbbm{1}_{\\{f_{\alpha}\leq
K\\}}-\mathbb{E}_{\mu}f_{\alpha}\mathbbm{1}_{\\{f_{\alpha}\leq
K\\}}}+\absolutevalue{\mathbb{E}_{\mu}f_{\alpha}\mathbbm{1}_{\\{f_{\alpha}\geq
K\\}}}$ (87)

We first bound the second term. From the dual formulation of the total
variation distance, we know that:

$d_{TV}(\mu_{d},\mu)=\frac{1}{2}\sup_{g}\absolutevalue{\mathbb{E}_{\mu_{d}}g-\mathbb{E}_{\mu}g}$
(88)

where the supremum is taken over all bounded measurable function $g$ such that
$\absolutevalue{g}\leq 1$. This easily implies that:

$\absolutevalue{\mathbb{E}_{\mu_{d}}f_{\alpha}\mathbbm{1}_{\\{f_{\alpha}\leq
K\\}}-\mathbb{E}_{\mu}f_{\alpha}\mathbbm{1}_{\\{f_{\alpha}\leq K\\}}}\leq
K\cdot d_{TV}(\mu_{d},\mu)$ (89)

To bound the first and third terms in (85), we use the bound:

$\mathbb{E}_{\mu_{d}}f_{\alpha}\mathbbm{1}_{\\{f_{\alpha}\geq
K\\}}\leq\frac{\mathbb{E}_{\mu_{d}}f^{2}}{K}$ (90)

Note that $\mathbb{E}_{\mu_{d}}f^{2}\leq 1$. Indeed, we have by Cauchy-
Schwartz:

$\mathbb{E}_{\mu_{d}}f^{2}=d\cdot\mathbb{E}_{V}\absolutevalue{\bra{k}V\ket{0}}\absolutevalue{\bra{k}V\ket{\psi}}\leq
d(\mathbb{E}_{V}\absolutevalue{\bra{k}V\ket{0}}^{2})^{1/2}(\mathbb{E}_{V}\absolutevalue{\bra{k}V\ket{\psi}}^{2})^{1/2}=1$
(91)

A similar bound holds for $\mu$. Inserting bounds (89) and (90) into (85), we
can choose $K$ large enough and then $d$ large enough so that
$\absolutevalue{\mathbb{E}_{\mu_{d}}f_{\alpha}-\mathbb{E}_{\mu}f_{\alpha}}$ is
arbitrarily small, which finishes the proof. Since the convergence rate in 83
is explicit, one easily checks that for a given error $\varepsilon$ it
suffices to take $K\sim\frac{1}{\varepsilon}$ and then
$d\sim\varepsilon^{-2}$, which overall implies convergence rate $d^{-1/2}$. ∎

We need to estimate the Gaussian average
$\mathbb{E}\absolutevalue{X}\absolutevalue{\alpha X+\beta Y}$. Such an
estimate is supplied by the following Lemma, whose proof we defer to Appendix
C:

######  Lemma 5.3.

Let $X,Y$ be independent standard complex Gaussians. Let
$\absolutevalue{\alpha}^{2}+\absolutevalue{\beta}^{2}=1$. The following
inequalities hold for some constant $c>0,\beta_{0}\in(0,1)$:

$1-(\mathbb{E}\absolutevalue{X}\absolutevalue{\alpha X+\beta Y})^{2}\geq
c\min\\{\absolutevalue{\beta}^{2},\beta_{0}^{2}\\}$ (92)

######  Lemma 5.4.

The function $f:\mathrm{U}(d)\to\mathbb{R}$, defined as:

$f(U)=\sum_{k}\absolutevalue{\bra{k}U\ket{0}}\absolutevalue{\bra{k}U\ket{\phi}}$
(93)

is Lipschitz with respect to the Hilbert-Schmidt norm with Lipschitz constant
$1$.

###### Proof.

By Lemma 5.1 we have:

$f(U)=\sup_{\ket{\alpha}\in
T_{U\ket{\phi}}}\absolutevalue{\bra{\alpha}U\ket{0}}$ (94)

For any fixed $\ket{\alpha}\in T_{U\ket{\phi}}$, the function
$f_{\ket{\alpha}}(U):=\absolutevalue{\bra{\alpha}U\ket{0}}$ is Lipschitz with
constant $1$. Since $f(U)=\sup_{\ket{\alpha}}f_{\ket{\alpha}}(U)$, it is also
Lipschitz with constant $1$ as a supremum of uniformly Lipschitz functions. ∎

######  Theorem 5.5.

Let $c,\beta_{0}$ be as in Lemma 5.3 and let $C_{0}=\frac{2}{\sqrt{c}}$. Let
$\ket{\phi}$ be such that $d(\ket{\phi},\ket{0})>C_{0}\varepsilon$ and let
$\varepsilon<\frac{\beta_{0}}{C_{0}}$. Then for any $t\geq 0$ we have:

$\mathbb{P}\left(U_{t}\ket{0}\in
B(\ket{\phi},\varepsilon)\right)\leq\exp\left(-\frac{\varepsilon^{2}d}{6}\right)$
(95)

###### Proof.

To prove the theorem it suffices to upper bound
$\mathbb{P}(\mathrm{dist}(V\ket{0},T_{V\ket{\phi}})<\varepsilon)$. Without
loss of generality assume that $\ket{\phi}=\alpha\ket{0}+\beta\ket{1}$, where
$\absolutevalue{\alpha}^{2}+\absolutevalue{\beta}^{2}=1$. Note that
$\absolutevalue{\beta}=d(\ket{\phi},\ket{0})>C_{0}\varepsilon$. Let

$Z_{d}=\sum_{k}\absolutevalue{\bra{k}V\ket{0}}\absolutevalue{\bra{k}V\ket{\phi}}$
(96)

so that $\mathrm{dist}(V\ket{0},T_{V\ket{\phi}})=1-Z_{d}^{2}$ by Lemma 5.1.
Let $\mu_{d}=\mathbb{E}Z_{d}$ and let
$\mu:=\mathbb{E}\absolutevalue{X}\absolutevalue{\alpha X+\beta Y}$, where
$X,Y$ are independent standard complex Gaussians. By Lemma 5.2 we have
$\mu_{d}\to\mu$ uniformly over $\alpha,\beta$, so also
$\mu_{d}^{2}\to\mu^{2}$. Pick $d$ large enough so that
$\mu_{d}^{2}<\mu^{2}+\varepsilon^{2}$ (since the convergence rate is
$d^{-1/2}$, it suffices that $\varepsilon>cd^{-1/4}$). By Lemma 5.3 we have:

$\mu^{2}\leq 1-c\min\\{\absolutevalue{\beta}^{2},\beta_{0}^{2}\\}<1-c\cdot
C_{0}^{2}\varepsilon^{2}=1-4\varepsilon^{2}$ (97)

which implies that:

$\mu_{d}^{2}\leq\mu^{2}+\varepsilon^{2}<1-3\varepsilon^{2}$ (98)

We can now estimate:

$\displaystyle\mathbb{P}(\mathrm{dist}(V\ket{0},T_{V\ket{\phi}})<\varepsilon)=\mathbb{P}(1-Z_{d}^{2}<\varepsilon)=$
(99)
$\displaystyle\mathbb{P}(Z_{d}>\sqrt{1-\varepsilon^{2}})=\mathbb{P}(Z_{d}-\mu_{d}>\sqrt{1-\varepsilon^{2}}-\mu_{d})\leq\mathbb{P}(Z_{d}-\mu_{d}>\sqrt{1-\varepsilon^{2}}-\sqrt{1-3\varepsilon^{2}})$
(100)

By the inequality $\sqrt{1-x}-\sqrt{1-y}\geq\frac{1}{2}(y-x)$ we have
$\sqrt{1-\varepsilon^{2}}-\sqrt{1-3\varepsilon^{2}}\geq\varepsilon^{2}$, so we
are finally left with bounding:

$\mathbb{P}(Z_{d}-\mu_{d}>\varepsilon^{2})$ (101)

We can now apply concentration of measure. By Lemma 5.4, the random variable
$Z_{d}$ is Lipschitz with respect to the Hilbert-Schmidt norm with constant
$1$. Applying Theorem 4.4 we obtain:

$\mathbb{P}(Z_{d}-\mu_{d}>\varepsilon^{2})\leq\exp(-\frac{\varepsilon^{2}(d-2)}{12})\leq\exp(-\frac{\varepsilon^{2}d}{6})$
(102)

as desired. ∎

###  5.2 Leaving the neighborhood of the initial state

We now estimate the probability that $U_{t}\ket{0}$ leaves the ball around
$\ket{0}$ for times $t\sim\varepsilon$. Recall that
$U_{t}=V^{\dagger}e^{iDt}V$. We have:

$\mathbb{P}(d(U_{t}\ket{0},\ket{0})<\varepsilon)=\mathbb{P}(\absolutevalue{\bra{0}V^{\dagger}e^{iDt}V\ket{0}}^{2}>1-\varepsilon^{2})=\mathbb{P}(\absolutevalue{\tr(\outerproduct{0}{0}V^{\dagger}e^{iDt}V)}^{2}>1-\varepsilon^{2})$
(103)

Let us write
$f(V,D):=\absolutevalue{\tr(\outerproduct{0}{0}V^{\dagger}e^{iDt}V)}^{2}$. For
fixed $D$, by (17) we have:

$\mu(D):=\mathbb{E}_{V}f(V,D)=\frac{1}{d+1}\left(1+\frac{\absolutevalue{\tr(U_{t})}^{2}}{d}\right)$
(104)

We split the probability into two parts:

$\displaystyle\mathbb{P}(f(V,D)>1-\varepsilon^{2})=$ (105)
$\displaystyle\mathbb{P}(f(V,D)>1-\varepsilon^{2}\ \cap\ \mu(D)\leq
1-2\varepsilon^{2})+\mathbb{P}(f(V,D)>1-\varepsilon^{2}\cap\mu(D)>1-2\varepsilon^{2})\leq$
(106)
$\displaystyle\mathbb{P}(f(V,D)-\mu(D)>\varepsilon^{2})+\mathbb{P}(f(V,D)>1-\varepsilon^{2}\cap\mu(D)>1-2\varepsilon^{2})\leq$
(107)
$\displaystyle\mathbb{P}(f(V,D)-\mu(D)>\varepsilon^{2})+\mathbb{P}(\mu(D)>1-2\varepsilon^{2})$
(108)

We bound the first term again using concentration of measure. For every $D$,
the function $f(V,D)$ is easily checked to be Lipschitz in the Hilbert-Schmidt
norm with respect to $V$ with Lipschitz constant $4$. By 4.4, the first term
is therefore bounded by:

$\mathbb{P}(f(V,D)-\mu(D)>\varepsilon^{2})\leq\exp(-\frac{\varepsilon^{2}(d-2)}{12})\leq\exp(-\frac{\varepsilon^{2}d}{6})$
(109)

Bounding the second term is equivalent to bounding
$\mathbb{P}(\absolutevalue{\tr(U_{t})}^{2}>(1-2\varepsilon^{2})d^{2}-2\varepsilon^{2}d)$.
This is estimated in the same way as in Theorem 4.7 and is bounded by
$<\delta/2$ for $t>C\varepsilon$ for some constant $C>0$. We have thus
obtained that for $d$ large enough we have:

$\mathbb{P}(d(U_{t}\ket{0},\ket{0})<\varepsilon)<\delta$ (110)

######  Theorem 5.6.

Fix $\varepsilon,\delta>0$ and the gateset $\mathcal{G}$. Let $H$ be drawn
from the $\mathrm{GUE}(d)$ ensemble and assume $\varepsilon>cd^{-1/4}$ for
some constant $c$ depending on $\delta$. Then for any time $t>C\varepsilon$,
with $C$ an absolute constant, we have:

$\mathbb{P}(C_{\varepsilon}(U_{t}\ket{0})>k)>1-\delta$ (111)

with

$k=\frac{1}{{\log\absolutevalue{\mathcal{G}}}}\left(C^{\prime}\varepsilon^{2}d-\log(\frac{1}{\delta})\right)$
(112)

and $C^{\prime}$ an absolute constant. The same result holds for random basis
i.i.d Gaussian ensemble.

###### Proof.

The proof is virtually the same as the proof of Theorem 4.9. We claim that for
$t>C\varepsilon$ and $d$ sufficiently large:

$\displaystyle\mathbb{P}\left(U_{t}\ket{0}\in\bigcup_{\ket{\phi}\in S^{\leq
k}}B(\ket{\phi},\varepsilon)\right)<\delta$ (113)

Let us divide $S^{\leq k}=S^{\leq k}_{0}\cup S^{\leq k}_{1}$, where $S^{\leq
k}_{0}:=\\{\ket{\phi}\in S^{\leq k}\ |\ \ket{\phi}\in
B(\ket{0},C_{0}\varepsilon)\\}$, where $C_{0}$ is the constant from Theorem
5.5, and $S^{\leq k}_{1}$ contains the remaining elements. For every
$\ket{\phi}\in S^{\leq k}_{0}$ we have $B(\ket{\phi},\varepsilon)\subseteq
B(\ket{0},(C_{0}+1)\varepsilon)$, so:

$\displaystyle\mathbb{P}\left(U_{t}\ket{0}\in\bigcup_{\ket{\phi}\in S^{\leq
k}}B(\ket{\phi},\varepsilon)\right)\leq\mathbb{P}\left(U_{t}\ket{0}\in
B(\ket{0},(C_{0}+1)\varepsilon)\right)+\mathbb{P}\left(U_{t}\ket{0}\in\bigcup_{\ket{\phi}\in
S^{\leq k}_{1}}B(\ket{\phi},\varepsilon)\right)\leq$ (114)
$\displaystyle\mathbb{P}\left(U_{t}\ket{0}\in
B(\ket{0},(C_{0}+1)\varepsilon)\right)+\sum_{\ket{\phi}\in S^{\leq
k}_{1}}\mathbb{P}\left(U_{t}\ket{0}\in B(\ket{\phi},\varepsilon)\right)$ (115)

For every $\ket{\phi}\in S^{\leq k}_{1}$ we have
$d(\ket{\phi},\ket{0})>C_{0}\varepsilon$, so we can invoke Theorem 5.5, to
obtain:

$\sum_{\ket{\phi}\in S^{\leq k}_{1}}\mathbb{P}\left(U_{t}\ket{0}\in
B(\ket{\phi},\varepsilon)\right)\leq\absolutevalue{S^{\leq
k}}\exp\left(-\frac{\varepsilon^{2}d}{6}\right)<\frac{\delta}{2}$ (116)

if
$k<\frac{C^{\prime}}{\log\absolutevalue{\mathcal{G}}}\left(\varepsilon^{2}d-\log(\frac{1}{\delta})\right)$
for appropriately chosen constant $C^{\prime}$. Note that this part of the
bound is time-independent.

It remains to bound $\mathbb{P}\left(U_{t}\ket{0}\in
B(\ket{0},(C_{0}+1)\varepsilon)\right)$. To this end we simply invoke (110)
and plug $\varepsilon\to(C_{0}+1)\varepsilon,\delta\to 1/2\delta$.

The proof for the random basis i.i.d. Gaussian model proceeds in the same
fashion. ∎

## Appendices

##  Appendix A Technical details for GUE

###### Proof of Theorem 4.6.

Let $\rho_{d}$ be the density of $\mu_{H_{d}}$. The starting point will the
following result on the convergence of densities $\rho_{d}$ to the semicircle
density $\rho_{sc}$ [GT05]: there exist absolute constants $C,\gamma>0$ such
that for $x\in[-2+\gamma d^{-2/3},2-\gamma d^{-2/3}]$ we have:

$\absolutevalue{\rho_{d}(x)-\rho_{sc}(x)}\leq\frac{C}{d(4-x^{2})}$ (117)

Fix $t>0$ and $\varepsilon>0$. Let us estimate:

$\displaystyle\absolutevalue{\int_{-\infty}^{\infty}e^{itx}\rho_{d}(x)dx-\int_{-\infty}^{\infty}e^{itx}\rho_{sc}(x)dx}\leq\int_{-\infty}^{\infty}\absolutevalue{\rho_{d}(x)-\rho_{sc}(x)}dx\leq$
$\displaystyle\int_{-\infty}^{-2+\gamma
d^{-2/3}}\absolutevalue{\rho_{d}(x)-\rho_{sc}(x)}dx+\int_{2-\gamma
d^{-2/3}}^{\infty}\absolutevalue{\rho_{d}(x)-\rho_{sc}(x)}dx+\int_{-2+\gamma
d^{-2/3}}^{2-\gamma d^{-2/3}}\absolutevalue{\rho_{d}(x)-\rho_{sc}(x)}dx$ (118)

To bound the first two terms, let us pick $\eta\in(0,2)$ such
$\mu_{sc}([-\infty,-2+\eta])=\mu_{sc}([2-\eta,\infty])<\frac{1}{8}\varepsilon$
– since $\mu_{sc}$ has an explicit continuous density supported on $[-2,2]$,
such an $\eta$ exists and in fact is readily computed that it is sufficient to
take $\eta\sim\varepsilon^{2/3}$. For sufficiently large $d$ we also have
$\mu_{H_{d}}([-\infty,-2+\eta])=\mu_{H_{d}}([2-\eta,\infty)<\frac{1}{8}\varepsilon$
(this is the classic convergence of GUE to Wigner semicircle law). In fact,
Theorem 1.1 from [GT05] implies that it suffices to take
$d>\frac{C}{\varepsilon}$ for some constant $C$. By the triangle inequality
this implies that:

$\displaystyle\int_{-\infty}^{-2+\gamma
d^{-2/3}}\absolutevalue{\rho_{d}(x)-\rho_{sc}(x)}dx+\int_{2-\gamma
d^{-2/3}}^{\infty}\absolutevalue{\rho_{d}(x)-\rho_{sc}(x)}dx\leq$ (119)
$\displaystyle\mu_{d}([-\infty,-2+\eta])+\mu_{sc}([-\infty,-2+\eta])+\mu_{d}([2-\eta,\infty)+\mu_{sc}([2-\eta,\infty)<\frac{1}{2}\varepsilon$
(120)

We need to take $d$ large enough so that $\gamma d^{-2/3}<\eta$ and since
$\eta\sim\varepsilon^{2/3}$, this is again equivalent to
$d>\frac{C}{\varepsilon}$. This bounds the first two terms in (A).

To bound the last term, we use (117) to estimate:

$\displaystyle\int_{-2+\gamma d^{-2/3}}^{2-\gamma
d^{-2/3}}\absolutevalue{\rho_{d}(x)-\rho_{sc}(x)}dx\leq\frac{C}{d}\int_{-2+\gamma
d^{-2/3}}^{2-\gamma d^{-2/3}}\frac{dx}{(4-x^{2})}dx=$ (121)
$\displaystyle\frac{C}{4d}(\log(4+\gamma d^{-2/3})+\log(4-\gamma
d^{-2/3})-2\log(\gamma d^{-2/3}))=O\left(\frac{\log d}{d}\right)$

which is smaller than $\frac{1}{2}\varepsilon$ for $d$ large enough. Since the
first two terms in (A) converge as $\frac{1}{d}$ and the last term converges
as $\frac{\log d}{d}$, the overall convergence rate is proportional to
$\frac{\log d}{d}$.

The claim that $\int_{\mathbb{R}}e^{i\lambda
t}d\mu_{sc}(\lambda)=\frac{J_{1}(2t)}{t}$ is standard computation. ∎

######  Theorem A.1.

If $H$ is drawn from the $\mathrm{GUE}(d)$ ensemble, then for any $\alpha>0$
and $t>c_{\alpha}d^{1+\alpha}$ we have $\mathrm{Var}\tr(U_{t})\leq 2d$.

###### Proof.

We prove the theorem for $H\sim\mathrm{GUE}(d,1)$ and
$t>c_{\alpha}d^{1/2+\alpha}$, from which the case of $\mathrm{GUE}(d)$ follows
by rescaling time by $\sqrt{d}$.

Let $h_{n}(x)$ be the unnormalized probabilists’ Hermite polynomial:

$\displaystyle h_{n}(x)=(-1)^{n}e^{x^{2}/2}\frac{d^{n}}{dx^{n}}e^{-x^{2}/2}$
(122)

and let $\Psi_{n}(x)$ be the oscillator wavefunction:

$\displaystyle\Psi_{n}(x)=\frac{e^{-x^{2}/4}h_{n}(x)}{(\sqrt{2\pi}n!)^{1/2}}$
(123)

Recall that the $1$-point correlation function is a measure with density
$\rho^{(1)}_{d}(x_{1})$ such that for any function $F$ of the eigenvalues we
have:

$\int
F(\lambda)\rho^{(1)}_{d}(\lambda)d\lambda=\frac{1}{d}\mathbb{E}\sum_{i}F(\lambda)$
(124)

and likewise the $2$-point correlation function is a measure with density
$\rho^{(2)}_{d}(x_{1},x_{2})$ such that for any function $F$ of the
eigenvalues we have:

$\int
F(\lambda_{1},\lambda_{2})\rho^{(2)}_{d}(\lambda_{1},\lambda_{2})d\lambda_{1}d\lambda_{2}=\frac{1}{d(d-1)}\mathbb{E}\sum_{i\neq
j}F(\lambda_{i},\lambda_{j})$ (125)

We have the following formula for the GUE correlation functions (see [AGZ09b],
Section 3.2.1):

$\displaystyle\rho^{(1)}_{d}(x)=\frac{1}{d}K_{d}(x,x)$ (126)

and:

$\displaystyle\rho^{(2)}_{d}(x_{1},x_{2})=\frac{1}{d(d-1)}\det_{i,j=1}^{2}(K_{d}(x_{i},x_{j}))=\frac{1}{d(d-1)}\left(K_{d}(x_{1},x_{1})K_{d}(x_{2},x_{2})-K_{d}(x_{1},x_{2})^{2}\right)$
(127)

where $K_{d}(x,y)$ is the GUE kernel:

$\displaystyle K_{d}(x,y)=\sum_{k=0}^{d-1}\Psi_{k}(x)\Psi_{k}(y)$ (128)

Since
$\mathbb{E}\absolutevalue{\Tr(U_{t})}^{2}=\sum_{k,l}\mathbb{E}e^{i(\lambda_{k}-\lambda_{l})t}$,
we have:

$\mathrm{Var}\tr(U_{t})=\mathbb{E}\absolutevalue{\Tr(U_{t})}^{2}-\absolutevalue{\mathbb{E}\Tr(U_{t})}^{2}=d+\int
e^{i(\lambda_{1}-\lambda_{2})t}\rho^{(2)}_{d}(\lambda_{1},\lambda_{2})d\lambda_{1}-\absolutevalue{\mathbb{E}\Tr(U_{t})}^{2}$
(129)

Observe that the diagonal term
$K(\lambda_{1},\lambda_{1})K(\lambda_{2},\lambda_{2})$ in the integral will
exactly reproduce and cancel the squared mean
$\absolutevalue{\mathbb{E}\Tr(U_{t})}^{2}$. Therefore we only need to handle
the off-diagonal term $K(\lambda_{1},\lambda_{2})^{2}$. It will suffice to
prove that:

$\displaystyle\absolutevalue{\int
K(\lambda_{1},\lambda_{2})^{2}e^{i(\lambda_{1}-\lambda_{2})t}d\lambda_{1}d\lambda_{2}}<d$
(130)

for $t>c_{\alpha}d^{1/2+\alpha}$ for some constant $c_{\alpha}$.

We first write:

$\displaystyle
K_{d}(x,y)^{2}=\left(\sum_{k=0}^{d-1}\Psi_{k}(x)\Psi_{k}(y)\right)^{2}=\sum_{k,l=0}^{d-1}\Psi_{k}(x)\Psi_{k}(y)\Psi_{l}(x)\Psi_{l}(y)$
(131)

which allows us to write the Fourier transform as (switching notation from
$\lambda_{i}$ to $x,y$):

$\displaystyle\int K(x,y)^{2}e^{i(x-y)t}dxdy=$
$\displaystyle\sum_{k,l=0}^{d-1}\int\Psi_{k}(x)\Psi_{k}(y)\Psi_{l}(x)\Psi_{l}(y)e^{i(x-y)t}dxdy=$
$\displaystyle\sum_{k,l=0}^{d-1}\absolutevalue{\int\Psi_{k}(x)\Psi_{l}(x)e^{ixt}dx}^{2}$

Using the definition of oscillator wavefunctions $\Psi_{k}$, we can write:

$\int\Psi_{k}(x)\Psi_{l}(x)e^{ixt}dx=\frac{1}{\sqrt{2\pi}\sqrt{k!}\sqrt{l!}}\int
h_{k}(x)h_{l}(x)e^{-x^{2}/2}e^{ixt}dx$ (132)

We now make use of the so-called linearization formula for Hermite
polynomials, which reads:

$\displaystyle
h_{k}(x)h_{l}(x)=\sum_{j=0}^{\min(k,l)}j!\binom{k}{j}\binom{l}{j}h_{k+l-2j}(x)$
(133)

which allows us to express (132) as:

$\displaystyle\int\Psi_{k}(x)\Psi_{l}(x)e^{ixt}dx=\frac{1}{\sqrt{2\pi}\sqrt{k!}\sqrt{l!}}\sum_{j=0}^{\min(k,l)}j!\binom{k}{j}\binom{l}{j}\int
h_{k+l-2j}(x)e^{-x^{2}/2}e^{ixt}dx$ (134)

The last integral can be found explicitly using the formula (proved at the end
of this section):

$\int h_{n}(x)e^{-x^{2}/2}e^{ixt}dx=\sqrt{2\pi}i^{n}t^{n}e^{-t^{2}/2}$ (135)

We therefore obtain:

$\displaystyle\int\Psi_{k}(x)\Psi_{l}(x)e^{ixt}dx=\frac{1}{\sqrt{k!}\sqrt{l!}}\sum_{j=0}^{\min(k,l)}j!\binom{k}{j}\binom{l}{j}i^{k+l-2j}t^{k+l-2j}e^{-t^{2}/2}$
(136)

The polynomial on the right hand side can be expressed using the confluent
hypergeometric function $U(a,b,z)$, but we will not need this as very crude
bounds will suffice. Since $j,k,l\leq d$, we have for $t\geq 1$:

$\displaystyle\absolutevalue{\int\Psi_{k}(x)\Psi_{l}(x)e^{ixt}dx}\leq
e^{-t^{2}/2}\frac{1}{\sqrt{k!}\sqrt{l!}}\sum_{j=0}^{\min(k,l)}j!\cdot
k^{j}\cdot l^{j}t^{k+l-2j}\leq$ (137) $\displaystyle
e^{-t^{2}/2}\sum_{j=0}^{\min(k,l)}d!\cdot d^{d}\cdot d^{d}t^{k+l-2j}\leq
e^{-t^{2}/2}t^{2d}(d+1)!\cdot d^{2d}$ (138)

Thus we have:

$\displaystyle\int
K(x,y)^{2}e^{i(x-y)t}dxdy=\sum_{k,l=0}^{d-1}\absolutevalue{\int\Psi_{k}(x)\Psi_{l}(x)e^{ixt}dx}^{2}\leq$
$\displaystyle d^{2}\left(e^{-t^{2}/2}t^{2d}(d+1)!\cdot
d^{2d}\right)^{2}=d^{2}\cdot e^{-t^{2}}t^{4d}((d+1)!)^{2}\cdot d^{4d}\leq$
$\displaystyle\exp(-t^{2}+4d\log t+5(d+1)\log(d+1)+2\log d)$ (139)

Clearly for $t=\Omega(d^{1/2+\alpha})$ for any $\alpha>0$ the term $-t^{2}$
dominates the remaining terms as $d\to\infty$, which proves our claim.

It remains to prove formula (135)]. We proceed by induction on $n$. For $n=0$
we have $h_{0}(x)=1$, so the integral reduces to $\sqrt{2\pi}e^{-t^{2}/2}$ as
desired. For the inductive step, we use the recursion
$h_{n+1}(x)=xh_{n}(x)-h_{n}^{\prime}(x)$ to obtain:

$\displaystyle\int h_{n+1}(x)e^{-x^{2}/2}e^{ixt}dx=\int
h_{n}(x)xe^{-x^{2}/2}e^{ixt}dx-\int h_{n}^{\prime}(x)e^{-x^{2}/2}e^{ixt}dx=$
$\displaystyle-\int h_{n}(x)\left(e^{-x^{2}/2}\right)^{\prime}e^{ixt}dx-\int
h_{n}^{\prime}(x)e^{-x^{2}/2}e^{ixt}dx=$
$\displaystyle-\int\left(h_{n}(x)e^{-x^{2}/2}e^{ixt}\right)^{\prime}dx+it\int
h_{n}(x)e^{-x^{2}/2}e^{ixt}dx=0+it\cdot\sqrt{2\pi}i^{n}t^{n}e^{-t^{2}/2}=\sqrt{2\pi}i^{n+1}t^{n+1}e^{-t^{2}/2}$

as desired. ∎

##  Appendix B Concentration of measure bounds for GUE

The bounds in Section 4.2 for GUE are based on moments of
$\absolutevalue{\tr(U_{t})}$ and are therefore only inversely polynomial in
$d$. Employing similar strategy as in the case of fixed basis (Section 4.3),
we sketch an exponential bound available for $t=o(d)$

Since we are potentially dealing with times $t\sim\varepsilon$, we need a
slightly more subtle approach than in Section 4.3. Observe that for any
$\lambda\in[0,1]$ and complex number $z$, if $\absolutevalue{z}\geq c$, then
at least one of: $\absolutevalue{\mathrm{Re}z}\geq\sqrt{1-\lambda}c$ or
$\absolutevalue{\mathrm{Im}z}\geq\sqrt{\lambda}c$ must hold. By union bound,
we thus obtain:

$\displaystyle\mathbb{P}\left(\absolutevalue{\tr(U_{t})}>(1-\frac{1}{2}\varepsilon^{2})d\right)\leq$
(140)
$\displaystyle\mathbb{P}\left(\absolutevalue{\mathrm{Re}\tr(U_{t})}>\sqrt{1-\lambda}(1-\frac{1}{2}\varepsilon^{2})d\right)+\mathbb{P}\left(\absolutevalue{\mathrm{Im}\tr(U_{t})}>\sqrt{\lambda}(1-\frac{1}{2}\varepsilon^{2})d\right)$
(141)

It is straightforward to check that choosing
$\lambda=\varepsilon^{2}(1-\varepsilon^{2})$ ensures that:

$\sqrt{1-\lambda}\left(1-\frac{1}{2}\varepsilon^{2}\right)\geq
1-\varepsilon^{2}$ (142)

We are thus left with bounding:

$\mathbb{P}\left(\absolutevalue{\mathrm{Re}\tr(U_{t})}>(1-\varepsilon^{2})d\right)$
(143)

and

$\mathbb{P}\left(\absolutevalue{\mathrm{Im}\tr(U_{t})}>\varepsilon\sqrt{1-\varepsilon^{2}}\left(1-\frac{1}{2}\varepsilon^{2}\right)d\right)$
(144)

As in Section 4.3, we first deal with:

$\mathbb{P}\left(\sum_{k}\cos(\lambda_{k}t)>(1-\varepsilon^{2})d\right)$ (145)

By symmetry of the distribution of GUE eigenvalues
$\mathbb{E}\sum_{k}\cos(\lambda_{k}t)=d\cdot\mathbb{E}_{\mu_{d}}e^{it\lambda}$,
and for $d$ large enough $\mathbb{E}_{\mu_{d}}e^{it\lambda}$ can be made
smaller than $1-2\varepsilon^{2}$ for $t>C\varepsilon$ as in the proof of
Theorem 4.7. We are thus left with bounding:

$\mathbb{P}\left(\frac{1}{d}\left(\sum_{k}\cos(\lambda_{k}t)-\mathbb{E}\sum_{k}\cos(\lambda_{k}t)\right)>\varepsilon^{2}\right)=\mathbb{P}\left(\frac{1}{d}\left(\tr(\cos(Ht))-\mathbb{E}\tr(\cos(Ht))\right)>\varepsilon^{2}\right)$
(146)

We are now in position to use concentration for functions of GUE eigenvalues.
We will use the following formulation (follows directly from [AGZ09b], Theorem
2.3.5):

######  Theorem B.1.

Let $f:\mathbb{R}\to\mathbb{R}$ be an $L$-Lipschitz function. If we extend $f$
to a function on symmetric matrices in the usual manner, then for
$X\sim\mathrm{GUE}(d,1/d)$ have:

$\displaystyle\mathbb{P}\left(\absolutevalue{\tr(f(X))-\mathbb{E}\tr(f(X))}\geq\delta
d\right)\leq 2\exp\left(-\frac{d^{2}\delta^{2}}{4L^{2}}\right)$ (147)

In our case $f(x)=\cos(xt)$, which is obviously $t$-Lipschitz, and
$\delta=\varepsilon^{2}$, which leads to:

$\displaystyle\mathbb{P}\left(\frac{1}{d}\left(\sum_{k}\cos(\lambda_{k}t)-\mathbb{E}\sum_{k}\cos(\lambda_{k}t)\right)>\varepsilon^{2}\right)\leq
2\exp\left(-\frac{d^{2}\varepsilon^{4}}{4t^{2}}\right)$ (148)

which goes to $0$ as $d\to\infty$ if $t=o(d)$. The remaining terms are bounded
in the same fashion.

##  Appendix C Computation of Gaussian average for states

We proceed to prove Lemma 5.3. By using the fact that the distribution of $X$
is conjugation invariant we can write:

$\mathbb{E}\absolutevalue{X}\absolutevalue{\alpha X+\beta
Y}=\mathbb{E}\absolutevalue{\alpha\absolutevalue{X}^{2}+\beta XY}$ (149)

Let $\theta$ denote the relative phase of $X$ and $Y$, which is uniformly
distributed in $[0,2\pi)$. We then have:

$\mathbb{E}\absolutevalue{\alpha\absolutevalue{X}^{2}+\beta
XY}=\mathbb{E}\absolutevalue{\alpha\absolutevalue{X}^{2}+e^{i\theta}\beta\absolutevalue{X}\absolutevalue{Y}}$
(150)

Without loss of generality we can assume that $\alpha,\beta$ are real. Let us
put $x=\absolutevalue{X},y=\absolutevalue{Y}$. Since $X=a+ib$, where $a,b$
have variance $1/2$, we have
$\absolutevalue{X}=\sqrt{a^{2}+b^{2}}\sim\frac{1}{\sqrt{2}}\chi_{2}$, where
$\chi_{2}$ is the chi distribution with density
$f(x)=xe^{-x^{2}/2}\mathbbm{1}_{\\{x\geq 0\\}}$, and likewise for $Y$. This
implies that we can write the average over
$\absolutevalue{X},\absolutevalue{Y}$ and $\theta$ as:

$\displaystyle
A(\beta):=\mathbb{E}\absolutevalue{\alpha\absolutevalue{X}^{2}+e^{i\theta}\beta\absolutevalue{X}\absolutevalue{Y}}=\mathbb{E}\sqrt{\alpha^{2}\absolutevalue{X}^{4}+\beta^{2}\absolutevalue{X}^{2}\absolutevalue{Y}^{2}+2\alpha\beta\absolutevalue{X}^{3}\absolutevalue{Y}\cos\theta}=$
(151)
$\displaystyle\frac{1}{2}\cdot\frac{1}{2\pi}\int_{0}^{2\pi}d\theta\int_{0}^{\infty}\int_{0}^{\infty}dxdy\sqrt{\alpha^{2}x^{4}+\beta^{2}x^{2}y^{2}+2\alpha\beta
x^{3}y\cos\theta}\cdot xe^{-x^{2}/2}\cdot ye^{-y^{2}/2}$ (152)

We handle this integral by passing to polar coordinates
$x=r\cos\varphi,y=r\sin\varphi$, where $\varphi\in[0,\pi/2]$ since both $r,s$
are nonnegative.

$\displaystyle
A(\beta)=\frac{1}{4\pi}\int_{0}^{2\pi}d\theta\int_{0}^{\infty}\int_{0}^{\frac{\pi}{2}}drd\varphi\cos^{2}\varphi\sin\varphi\sqrt{\alpha^{2}\cos^{2}\varphi+\beta^{2}\sin^{2}\varphi+2\alpha\beta\cos\varphi\sin\varphi\cos\theta}\cdot
r^{5}e^{-r^{2}/2}$ (153)

The radial part separates and gives:

$\int_{0}^{\infty}r^{5}e^{-r^{2}/2}=8$ (154)

so:

$\displaystyle
A(\beta)=\frac{2}{\pi}\int_{0}^{2\pi}d\theta\int_{0}^{\frac{\pi}{2}}d\varphi\cos^{2}\varphi\sin\varphi\sqrt{\alpha^{2}\cos^{2}\varphi+\beta^{2}\sin^{2}\varphi+2\alpha\beta\cos\varphi\sin\varphi\cos\theta}=$
(155)
$\displaystyle\frac{2}{\pi}\int_{0}^{2\pi}d\theta\int_{0}^{\frac{\pi}{2}}d\varphi\cos^{2}\varphi\sin\varphi\sqrt{a^{2}+b^{2}+2ab\cos\theta}$
(156)

where $a=\alpha\cos\varphi,b=\beta\sin\varphi$.

We now write:

$\sqrt{a^{2}+b^{2}+2ab\cos\theta}=\sqrt{a^{2}+b^{2}}\cdot\sqrt{1+\frac{2ab}{a^{2}+b^{2}}\cos\theta}$
(157)

We claim that:

$\sqrt{1+x}+\sqrt{1-x}\leq 2-\frac{1}{4}x^{2}$ (158)

The inequality follows from $\sqrt{1+x}\leq
1+\frac{1}{2}x-\frac{1}{8}x^{2}+\frac{1}{16}x^{3}$, which follows by repeated
differentiation (the terms on the right hand side are the first terms of the
Taylor expansion of $\sqrt{1+x}$). Applying (158) to (157) we arrive at:

$\sqrt{a^{2}+b^{2}+2ab\cos\theta}+\sqrt{a^{2}+b^{2}-2ab\cos\theta}\leq\sqrt{a^{2}+b^{2}}\left(2-\frac{1}{4}\left(\frac{2ab}{a^{2}+b^{2}}\right)^{2}\cos^{2}\theta\right)$
(159)

Since $\cos(x)=-\cos(x+\pi)$ and $\theta$ is uniformly distributed over
$[0,2\pi)$, we can apply the above inequality to the integral $A(\beta)$ to
obtain:

$\displaystyle
A(\beta)\leq\frac{2}{\pi}\int_{0}^{2\pi}d\theta\int_{0}^{\frac{\pi}{2}}d\varphi\cos^{2}\varphi\sin\varphi\sqrt{a^{2}+b^{2}}\left(1-\frac{1}{8}\left(\frac{2ab}{a^{2}+b^{2}}\right)^{2}\cos^{2}\theta\right)$
(160)

Substituting back $a=\alpha\cos\varphi,b=\beta\sin\varphi$ and using
$\frac{1}{2\pi}\int_{0}^{2\pi}\cos^{2}\theta=1/2$ we can write the inequality
as:

$\displaystyle A(\beta)\leq I_{0}(\beta)-\alpha^{2}\beta^{2}I_{1}(\beta)$
(161)

where:

$\displaystyle
I_{0}(\beta)=4\int_{0}^{\frac{\pi}{2}}d\varphi\cos^{2}\varphi\sin\varphi\sqrt{\alpha^{2}\cos^{2}\varphi+\beta^{2}\sin^{2}\varphi}$
(162) $\displaystyle
I_{1}(\beta)=\frac{1}{2}\int_{0}^{\frac{\pi}{2}}d\varphi\cos^{2}\varphi\sin\varphi\frac{\cos^{2}\varphi\sin^{2}\varphi}{(\alpha^{2}\cos^{2}\varphi+\beta^{2}\sin^{2}\varphi)^{3/2}}.$
(163)

One can easily check that the function $I_{0}$ is nonincreasing, with
$I_{0}(0)=1,I_{0}(1)=\frac{\pi}{4}$. Moreover, $I_{1}(\beta)>0$ for all
$\beta$ (as for any $\beta$ it is an integral of some nonnegative function
that is not identically $0$).

We now have inserting $\alpha^{2}=1-\beta^{2}$:

$A(\beta)^{2}\leq
I_{0}(\beta)^{2}-(1-\beta)^{2}\beta^{2}I_{1}(\beta)\left(2I_{0}(\beta)-(1-\beta^{2})\beta^{2}I_{1}(\beta)\right)$
(164)

Since $I_{1}>0$, then for $\beta\not=0,1$ $A(\beta)$ is strictly smaller than
$I_{0}(\beta)$, hence the term that is subtracted on right hand side of the
above inequality is strictly positive for $\beta\not=0,1$ and it holds also if
we drop the factor $(1-\beta^{2})\beta^{2}$:

$\displaystyle
I_{1}(\beta)\left(2I_{0}(\beta)-(1-\beta^{2})\beta^{2}I_{1}(\beta)\right)>0,\quad{\rm
for}\quad\beta\not=0,1.$ (165)

But since $I_{1}$ and $I_{2}$ are strictly positive for all $\beta$, we obtain
that the above expression is strictly positive for all $\beta$. Since $I_{1}$
and $I_{2}$ are continuous, the above expression is therefore bounded from
below by some constant $B>0$. Therefore:

$A(\beta)^{2}\leq I_{0}(\beta)^{2}-B(1-\beta)^{2}\beta^{2}$ (166)

We easily compute that $I_{0}(1)=\frac{\pi}{4}<1$. Choose
$\delta=\frac{1}{2}\left(1-\frac{\pi}{4}\right)$. By continuity there exists a
$\beta_{0}\in(0,1)$ such that $I_{0}(\beta)<1-\delta$ for
$\beta\geq\beta_{0}$. If $\beta<\beta_{0}$, then:

$A(\beta)^{2}\leq 1-B(1-\beta_{0})^{2}\beta^{2}$ (167)

and if $\beta\geq\beta_{0}$:

$A(\beta)^{2}\leq 1-\delta$ (168)

If we choose $c:=\min\\{B(1-\beta_{0})^{2},\frac{\delta}{\beta_{0}^{2}}\\}$,
we obtain $A(\beta)^{2}<1-c\min\\{\beta^{2},\beta_{0}^{2}\\}$ and the Lemma is
proved.

##  Appendix D Leaving the identity in the i.i.d. Gaussian model

###### Proof of Proposition 4.11.

We can assume that $t<C\varepsilon$ for some constant $C$, since the case
$t>C\varepsilon$ is already handled by previous arguments. We first show that
$\norm{U_{t}-I}_{\infty}>\varepsilon$ with high probability – the case with
arbitrary global phase will be similar. Using the independence of
$\lambda_{k}$ we have:

$\displaystyle\mathbb{P}\left(\norm{U_{t}-I}_{\infty}\leq\varepsilon\right)=\mathbb{P}\left(\max_{k}\absolutevalue{1-e^{i\lambda_{k}t}}\leq\varepsilon\right)=$
(169)
$\displaystyle\mathbb{P}\left(\bigcap_{k=1}^{d}\absolutevalue{1-e^{i\lambda_{k}t}}\leq\varepsilon\right)=\mathbb{P}\left(|\sin(\frac{\lambda
t}{2})|\leq\frac{\varepsilon}{2}\right)^{d}$ (170)

Clearly it suffices to show that $\mathbb{P}\left(|\sin(\frac{\lambda
t}{2})|\leq\frac{\varepsilon}{2}\right)<1-\frac{a}{d}$ for some constant
$a>0$, as $\left(1-\frac{a}{d}\right)\to e^{-a}$.

Clearly $|\sin(\frac{\lambda t}{2})|\leq\frac{\varepsilon}{2}$ is equivalent
to:

$\lambda t\in\bigcup_{l=-\infty}^{\infty}[-\eta+2l\pi,\eta+2l\pi]$ (171)

for some $\eta$ depending on $\varepsilon$. It is easy to see that
$c_{1}\varepsilon>\eta>c_{0}\varepsilon$ for some explicit $c_{0},c_{1}>0$. We
can thus union bound:

$\displaystyle\mathbb{P}\left(|\sin(\frac{\lambda
t}{2})|\leq\frac{\varepsilon}{2}\right)\leq\sum_{l=-\infty}^{\infty}\mathbb{P}(\lambda
t\in[-\eta+2l\pi,\eta+2l\pi])=$ (172) $\displaystyle\mathbb{P}(\lambda
t\in[-\eta,\eta])+2\sum_{l=1}^{\infty}\mathbb{P}(\lambda
t\in[-\eta+2l\pi,\eta+2l\pi])$ (173)

The random variable $\lambda t$ is Gaussian with variance $t^{2}$, so the tail
consisting of terms for $l\geq 1$ can be bounded by:

$\mathbb{P}(\lambda t\in[-\eta+2l\pi,\eta+2l\pi])\leq
2\eta\cdot\frac{1}{\sqrt{2\pi}t}\exp(-\frac{(2l\pi-\eta)^{2}}{2t^{2}})$ (174)

Since $\varepsilon<1/2$, we can take $\eta<\pi$ and estimate the tail by a
geometric series:

$\displaystyle 2\sum_{l=1}^{\infty}\mathbb{P}(\lambda
t\in[-\eta+2l\pi,\eta+2l\pi])\leq 2\eta\cdot
2\sum_{l=1}^{\infty}\frac{1}{\sqrt{2\pi}t}\exp(-\frac{(2l\pi-\eta)^{2}}{2t^{2}})\leq$
(175)
$\displaystyle\frac{4\eta}{\sqrt{2\pi}t}\sum_{l=1}^{\infty}\exp(-\frac{(l\pi)^{2}}{2t^{2}})\leq\frac{4\eta}{\sqrt{2\pi}t}\sum_{l=1}^{\infty}\exp(-\frac{l\pi^{2}}{2t^{2}})=\frac{4\eta}{\sqrt{2\pi}t}\cdot\frac{\exp(-\frac{\pi^{2}}{2t^{2}})}{1-\exp(-\frac{\pi^{2}}{2t^{2}})}$
(176)

The term with $l=0$ can be estimated using the standard Gaussian tail lower
bound:

$\mathbb{P}(X>x)\geq\frac{1}{\sqrt{2\pi}}\cdot\frac{x}{x^{2}+1}\exp(-x^{2}/2)$
(177)

we get:

$\mathbb{P}(\lambda t\in[-\eta,\eta])=1-\mathbb{P}(\absolutevalue{\lambda
t}>\eta)\leq
1-\frac{2}{\sqrt{2\pi}}\frac{\frac{\eta}{t}}{1+(\frac{\eta}{t})^{2}}\exp(-\frac{\eta^{2}}{2t^{2}})$
(178)

Since $t<C\varepsilon$ and $c_{1}\varepsilon>\eta>c_{0}\varepsilon$, we have
$\frac{\eta}{t}>A$ for some constant $A$, which implies:

$\mathbb{P}(\lambda t\in[-\eta,\eta])\leq
1-A^{\prime}\frac{t}{\varepsilon}\cdot\exp(-c_{1}\frac{\varepsilon^{2}}{2t^{2}})$
(179)

We can assume that $\varepsilon$ is small enough co that
$1-\exp(-\frac{\pi^{2}}{2t^{2}})>1/2$. Putting the bounds together leaves us
with:

$\displaystyle\mathbb{P}\left(|\sin(\frac{\lambda
t}{2})|\leq\frac{\varepsilon}{2}\right)\leq
1-A^{\prime}\frac{t}{\varepsilon}\cdot\exp(-c_{1}\frac{\varepsilon^{2}}{2t^{2}})+\frac{B\varepsilon}{t}\cdot\exp(-\frac{\pi^{2}}{2t^{2}})$
(180)

Introduce $y=\frac{\varepsilon}{t}$, so that $C<y<C^{\prime}\ \sqrt{\log(d)}$
and the bound takes the form:

$1-A^{\prime}\frac{1}{y}\cdot\exp(-cy^{2})+By\cdot\exp(-\frac{\pi^{2}}{2\varepsilon^{2}}y^{2})=1-A^{\prime}\frac{1}{y}\cdot\exp(-cy^{2})\left(1-\frac{B}{A}y^{2}\exp(-(\frac{\pi^{2}}{2\varepsilon^{2}}-c)y^{2})\right)$
(181)

By choosing $\varepsilon$ small enough we can make
$\frac{\pi^{2}}{2\varepsilon^{2}}-c>0$. The appropriate choice of constants
$C,C^{\prime}$ then ensures that the bound is $<1-\frac{a}{d}$ for all $y$ in
the chosen range, which finishes the proof. Dealing with arbitrary global
phase, i.e. bounding $\norm{U_{t}-e^{i\varphi}I}_{\infty}$ for arbitrary
$\varphi$, changes only $\sin(\lambda t)$ to $\sin(\lambda t+\varphi)$ in the
above expressions and is estimated in virtually the same way. ∎

##  Appendix E Geometric arguments for approximate equidistribtion on the
torus

In this Appendix we present a purely geometric argument for the complexity
lower bound in the diagonal (fixed basis) case. In contrast to other proofs in
this paper, this one is non-probabilistic (does not use concentration of
measure or moment bounds) and gives the optimal scaling with respect to
$\varepsilon$, namely $\sim d\cdot\log\left(\frac{1}{\varepsilon}\right)$
instead of $\sim d$.

To explain the intuition behind the proof, we first sketch the setup. Let $H$
be a diagonal random Hamiltonian with eigenvalues
$\lambda_{1},\dots,\lambda_{d}$. The time evolution $e^{iHt}$ then happens on
the set of diagonal unitary matrices, which we identify with the
$d$-dimensional torus $\mathbb{T}^{d}$. The metric coming from the operator
norm is equivalent to the distance on the torus given by:

$d((e^{i\varphi_{1}},\dots,e^{i\varphi_{d}}),(e^{i\varphi^{\prime}_{1}},\dots,e^{i\varphi^{\prime}_{d}}))=\max_{i=1,\dots,d}\absolutevalue{e^{i\varphi_{i}}-e^{i\varphi^{\prime}_{i}}}$
(182)

For $t>0$ let $\nu_{t}$ denote the distribution of
$(e^{i\lambda_{1}t},\dots,e^{i\lambda_{d}t})$ and let $\nu$ denote the uniform
measure on $\mathbb{T}^{d}$. Now, suppose that the distribution of
$\lambda_{i}$’s has a continuous density $\rho$ (e.g. we exclude the case
where $\lambda_{i}$’s take only countably many values). Then, as $t\to\infty$,
the measures $\nu_{t}$ will converge weakly to $\nu$. Indeed, to check weak
convergence on a compact space it suffices to check the convergence of
polynomials. In this case this means that for any sequence of natural numbers
$\bar{n}=(n_{1},\dots,n_{d})$ which is not all zeros we must have:

$\lim_{t\to\infty}\int_{\mathbb{T}^{d}}e^{i\left\langle\bar{n},\bar{\varphi}\right\rangle}d\nu_{t}(\bar{\varphi})=\int_{\mathbb{T}^{d}}e^{i\left\langle\bar{n},\bar{\varphi}\right\rangle}d\nu(\bar{\varphi})=0$
(183)

This follows from the fact that:

$\int_{\mathbb{T}^{d}}e^{i\left\langle\bar{n},\bar{\varphi}\right\rangle}d\nu_{t}(\bar{\varphi})=\int_{\mathbb{R}^{d}}e^{i\left\langle\bar{n},\bar{\lambda}\right\rangle
t}\rho(\bar{\lambda})d\bar{\lambda}$ (184)

and that the density $\rho$ is continuous, so by standard properties of the
Fourier transform we have that the Fourier transform of $\rho$ decays to zero
at infinity.

The weak convergence of $\nu_{t}$ to $\nu$ implies that for any measurable set
$A\subseteq\mathbb{T}^{d}$ the measures $\nu_{t}(A)$ converge to $\nu(A)$. In
particular, if we take $A$ to be the $\varepsilon$-ball around any point
$x\in\mathbb{T}^{d}$, for large enough times $t$ the measure $\nu_{t}(A)$ will
be approximately $\sim\varepsilon^{d}$. This holds for any density $\rho$, but
the argument is purely qualitative – in particular, the convergence time may
depend on the dimension $d$. In the case of i.i.d. Gaussian eigenvalues, we
show that in fact constant time is sufficient for the measures $\nu_{t}$ to
approximate the uniform measure on $\varepsilon$-balls.

From now on let $H$ be drawn from the diagonal Gaussian i.i.d. ensemble, with
eigenvalues $\lambda_{1},\dots,\lambda_{d}$. We will prove the following
Theorem:

######  Theorem E.1.

There exists an absolute constant $C>0$ such that for any
$x\in\mathbb{T}^{d}$, any $t>1$ and any $\varepsilon$ we have:

$\nu_{t}(B(x,\varepsilon))\leq C^{d}\varepsilon^{d}$ (185)

where $B$ denotes the ball in the metric defined in 182.

###### Proof.

It will be convenient to work in the additive model of the torus, namely
$\mathbb{T}^{d}_{+}:=(\mathbb{R}/2\pi\mathbb{Z})^{d}$, equipped with the
metric coming from the quotient of the $\infty$-metric on $\mathbb{R}^{d}$:

$d_{2}(\varphi,\varphi^{\prime})=\max_{i}\min\\{\absolutevalue{\varphi_{i}-\varphi^{\prime}_{i}},\absolutevalue{\varphi_{i}-\varphi^{\prime}_{i}\pm
2\pi}\\}$ (186)

It is straightforward to prove that:

$\frac{2}{\pi}\min\\{\absolutevalue{\varphi_{i}-\varphi^{\prime}_{i}},\absolutevalue{\varphi_{i}-\varphi^{\prime}_{i}\pm
2\pi}\\}\leq\absolutevalue{e^{i\varphi_{i}}-e^{i\varphi^{\prime}_{i}}}$ (187)

Therefore, we have for any $x\in\mathbb{T}^{d}_{+}$ that $B(x,r)\subseteq
B_{2}(x,\frac{\pi}{2}r)$. Thus, it suffices to prove 185 in the metric $d_{2}$
at the price of a constant $C$ worse by $\frac{\pi}{2}$. By $\nu_{t}$ we will
denote the induced measure both on $\mathbb{T}^{d}$ and $\mathbb{T}^{d}_{+}$.

Let $\gamma^{(d)}$ denote the i.i.d. Gaussian measure on $\mathbb{R}^{d}$ and
for any $t>0$ let $\gamma^{(d)}_{t}$ denote the image of $\gamma^{(d)}$ under
the map $(\lambda_{1},\dots,\lambda_{d})\to(\lambda_{1}t,\dots,\lambda_{d}t)$.
Note that for any measurable set $S\subseteq\mathbb{T}_{+}$ we have by
definition of $\nu_{t}$:

$\nu_{t}(S)=\sum_{y\in(2\pi\mathbb{Z})^{d}}\gamma^{(d)}_{t}(S+y)=\sum_{y\in(2\pi\mathbb{Z})^{d}}\gamma^{(d)}\left(\frac{S+y}{t}\right)$
(188)

We now take $S=B_{2}(x,\varepsilon)$ so that
$\frac{S+y}{t}=B_{2}\left(\frac{x+y}{t},\frac{\varepsilon}{t}\right)$. We will
prove the following statement, which will imply 185:

$\gamma^{(d)}\left(B_{2}\left(\frac{x+y}{t},\frac{\varepsilon}{t}\right)\right)\leq
C^{d}\varepsilon^{d}\gamma^{(d)}\left(B_{2}\left(\frac{x+y}{t},\frac{\pi}{t}\right)\right)$
(189)

Indeed, by 188:

$\nu_{t}(B_{2}\left(x,\varepsilon\right))=\sum_{y\in(2\pi\mathbb{Z})^{d}}\gamma^{(d)}\left(B_{2}\left(\frac{x+y}{t},\frac{\varepsilon}{t}\right)\right)\leq
C^{d}\varepsilon^{d}\sum_{y\in(2\pi\mathbb{Z})^{d}}\gamma^{(d)}\left(B_{2}\left(\frac{x+y}{t},\frac{\pi}{t}\right)\right)=C^{d}\varepsilon^{d}$
(190)

where the last equality follows since the balls
$B_{2}\left(\frac{x+y}{t},\frac{\pi}{t}\right)$ are disjoint and cover all
$\mathbb{R}^{d}$ up to a set of measure of zero.

Thus, we are reduced to proving the inequality 189. For intuition behind this
inequality, notice that it can be easily rewritten to state that the average
of the density over a ball of radius $\frac{\varepsilon}{t}$ should not be
much larger than the average over a ball of radius $\frac{\pi}{t}$. We expect
this to be true as $t\to\infty$, since at finer and finer scales the density
becomes more and more flat. We will now make this intuition quantitative.

We claim that for any $z\in\mathbb{R}^{d}$, any $\varepsilon<\pi$ and $t>1$,
we have for $C=\frac{1}{\pi}e^{(2\pi+1)^{2}/2}$:

$\gamma^{(d)}\left(B_{2}\left(z,\frac{\varepsilon}{t}\right)\right)\leq
C^{d}\varepsilon^{d}\gamma^{(d)}\left(B_{2}\left(z,\frac{\pi}{t}\right)\right)$
(191)

Since the measure $\gamma^{(d)}$ is a product measure and the ball is a
product of balls on each coordinate, it suffices to prove the inequality on
each coordinate separately, that is, prove for any $z\in\mathbb{R}$:

$\gamma\left(B\left(z,\frac{\varepsilon}{t}\right)\right)\leq
C\varepsilon\gamma\left(B\left(z,\frac{\pi}{t}\right)\right)$ (192)

where $\gamma$ is the $1$-dimensional standard Gaussian measure. This
immediately translates into:

$\int_{z-\frac{\varepsilon}{t}}^{z+\frac{\varepsilon}{t}}e^{-x^{2}/2}dx\leq
C\varepsilon\int_{z-\frac{\pi}{t}}^{z+\frac{\pi}{t}}e^{-x^{2}/2}dx$ (193)

The function $f(x)=e^{-x^{2}/2}$ is concave for $\absolutevalue{x}<1$ and
convex otherwise. We deal with these possibilities separately, assuming $t>1$:

  1. 1.

If $\absolutevalue{z}<\pi+1$, then
$(z-\pi/t,z+\pi/t)\subseteq(z-\pi,z+\pi)\subseteq(-2\pi-1,2\pi+1)$, so:

$\int_{z-\frac{\pi}{t}}^{z+\frac{\pi}{t}}e^{-x^{2}/2}dx\geq\frac{2\pi}{t}e^{-(2\pi+1)^{2}/2}$
(194)

and at the same time:

$\int_{z-\frac{\varepsilon}{t}}^{z+\frac{\varepsilon}{t}}e^{-x^{2}/2}dx\leq\frac{2\varepsilon}{t}$
(195)

which proves 193 with $C=\frac{1}{\pi}e^{(2\pi+1)^{2}/2}$

  2. 2.

If $\absolutevalue{z}\geq\pi+1$, then the integrand in 193 is convex on the
whole range of integration. The desired inequality with $C=\frac{1}{\pi}$ then
follows from the fact that if $f$ is convex, then the running average
$g(t):=\frac{1}{t}\int_{0}^{t}f(x)dx$ is nondecreasing. To see this, notice
that $g^{\prime}(t)\geq 0$ is equivalent to
$\frac{1}{2}(f(0)+f(t)\geq\frac{1}{t}\int_{0}^{t}f(x)dx$, which easily follows
from the convexity of $f$ by e.g. approximating the integral by its Riemann
sums.

∎

######  Proposition E.2.

Let $\mathcal{D}$ denote the set of diagonal unitary channels. If $H$ is drawn
from the diagonal i.i.d. Gaussian model and $U_{t}=e^{iHt}$, then for any time
$t>1$ and any $\boldsymbol{D}\in\mathcal{D}$:

$\mathbb{P}(\boldsymbol{U}_{t}\in B(\boldsymbol{D},\varepsilon))\leq
C^{d}\varepsilon^{d-1}$ (196)

where $C$ is an absolute constant and the ball is in the diamond metric.

###### Proof.

By the inequality 3, it suffices to prove the same statement, but with the
diamond metric replaced with the metric $D_{\infty}$. Let $A$ be an
$\varepsilon$-net over $[0,2\pi)$ of size $\frac{1}{\varepsilon}$. We clearly
have for any choice of representatives $U_{t},D$:

$\mathbb{P}(\boldsymbol{U}_{t}\in
B_{\infty}(\boldsymbol{D},\varepsilon))=\mathbb{P}(U_{t}\in\bigcup_{\varphi\in
A}B(e^{i\varphi}D,\varepsilon))\leq\sum_{\varphi\in A}\mathbb{P}(U_{t}\in
B(e^{i\varphi}D,\varepsilon))$ (197)

But the probability $\mathbb{P}(U_{t}\in B(e^{i\varphi}D,\varepsilon))$ is
simply the measure $\nu_{t}(B(e^{i\varphi}D,\varepsilon))$ as used before,
which by Theorem E.1 is bounded by $C^{d}\varepsilon^{d}$ for $t>1$. The claim
of the Proposition follows. ∎

######  Theorem E.3.

Fix $\varepsilon,\delta>0$ and the gateset $\mathcal{G}$. If $H$ is drawn from
the diagonal i.i.d. Gaussian model, then for any time $t>1$ we have:

$\mathbb{P}(C^{\diamond}_{\varepsilon}(\boldsymbol{U}_{t})>k)>1-\delta$ (198)

with

$k=\frac{1}{{\log\absolutevalue{\mathcal{G}}}}\left(Cd\log\left(\frac{1}{C^{\prime}\varepsilon}\right)-\log(\frac{1}{\delta})\right)$
(199)

and $C,C^{\prime}$ absolute constants.

###### Proof.

We start with the union bound:

$\mathbb{P}_{H}(C^{\diamond}_{\varepsilon}(\boldsymbol{U}_{t})\leq
k)=\mathbb{P}(\boldsymbol{U}_{t}\in\bigcup_{\boldsymbol{G}\in\mathcal{G}^{\leq
k}}B(\boldsymbol{G},\varepsilon)\leq\sum_{\boldsymbol{G}\in\mathcal{G}^{\leq
k}}\mathbb{P}\left(\boldsymbol{U}_{t}\in B(\boldsymbol{G},\varepsilon)\right)$
(200)

Let $\mathcal{D}$ be the set of diagonal unitary channels. For a given
$\boldsymbol{G}\in\mathcal{G}^{\leq k}$, if
$\mathrm{D}_{\diamond}(\boldsymbol{G},\boldsymbol{D})>\varepsilon$ for all
$\boldsymbol{D}\in\mathcal{D}$, then obviously
$\mathbb{P}\left(\boldsymbol{U}_{t}\in B(\boldsymbol{G},\varepsilon)\right)=0$
as $\boldsymbol{U}_{t}$ is always diagonal. Otherwise, there exists some
$\boldsymbol{D}\in\mathcal{D}$ such that
$B(\boldsymbol{G},\varepsilon)\subseteq B(\boldsymbol{D},2\varepsilon)$. By
Proposition E.2, we have thus for some constant $C^{\prime\prime}$:

$\mathbb{P}\left(\boldsymbol{U}_{t}\in
B(\boldsymbol{G},\varepsilon)\right)\leq\mathbb{P}\left(\boldsymbol{U}_{t}\in
B(\boldsymbol{D},2\varepsilon)\right)\leq(C^{\prime\prime})^{d}2^{d-1}\varepsilon^{d-1}$
(201)

Since there are $\absolutevalue{\mathcal{G}}^{k}$ terms in 200, we have:

$\mathbb{P}_{H}(C^{\diamond}_{\varepsilon}(\boldsymbol{U}_{t})\leq
k)\leq\absolutevalue{\mathcal{G}}^{k}(C^{\prime\prime})^{d}2^{d-1}\varepsilon^{d-1}<\delta$
(202)

for $k$ as in the statement and appropriate choice of constants
$C,C^{\prime}$. ∎

## References

  * [AA17] Yosi Atia and Dorit Aharonov, _Fast-forwarding of Hamiltonians and exponentially precise measurements_ , Nature Commun. 8 (2017), 1572.
  * [Aar16] Scott Aaronson, _The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes_.
  * [AGZ09a] Greg W. Anderson, Alice Guionnet, and Ofer Zeitouni, _An introduction to random matrices_ , Cambridge Studies in Advanced Mathematics, Cambridge University Press, 2009.
  * [AGZ09b] , _An introduction to random matrices_ , Cambridge Studies in Advanced Mathematics, Cambridge University Press, 2009.
  * [AS17] Guillaume Aubrun and Stanisław J Szarek, _Alice and Bob meet Banach: the interface of asymptotic geometric analysis and quantum information theory_ , Mathematical surveys and monographs, American Mathematical Society, Providence, RI, 2017.
  * [BaCHJ+21] Fernando G. S. L. Brandão, Wissam Chemissany, Nicholas Hunter-Jones, Richard Kueng, and John Preskill, _Models of Quantum Complexity Growth_ , PRX Quantum 2 (2021), 030316.
  * [BaiaCanH+12] Fernando G. S. L. Brandão, Piotr Ćwikliński, Michał Horodecki, Paweł Horodecki, Jarosław K. Korbicz, and Marek Mozrzymas, _Convergence to equilibrium under a random hamiltonian_ , Phys. Rev. E 86 (2012), 031101.
  * [BBa17] Thomas C. Bohdanowicz and Fernando G. S. L. Brandão, _Universal Hamiltonians for Exponentially Long Simulation_.
  * [BCK15] Dominic W. Berry, Andrew M. Childs, and Robin Kothari, _Hamiltonian simulation with nearly optimal dependence on all parameters_ , 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, 2015, pp. 792–809.
  * [BDKP20] Vijay Balasubramanian, Matthew Decross, Arjun Kar, and Onkar Parrikar, _Quantum Complexity of Time Evolution with Chaotic Hamiltonians_ , JHEP 01 (2020), 134.
  * [Bec17] Jozsef Beck, _Strong uniformity and large dynamical systems_ , WORLD SCIENTIFIC, 2017.
  * [BG11] Jean Bourgain and Alex Gamburd, _A Spectral Gap Theorem in $SU(d)$_.
  * [BG21] Adam Bouland and Tudor Giurgica-Tiron, _Efficient Universal Quantum Compilation: An Inverse-free Solovay-Kitaev Algorithm_ , arXiv e-prints (2021), arXiv:2112.02040.
  * [BO17] Adam Bouland and Maris Ozols, _Trading inverses for an irrep in the Solovay-Kitaev theorem_ , arXiv e-prints (2017), arXiv:1712.09798.
  * [BS18] Adam R. Brown and Leonard Susskind, _Second law of quantum complexity_ , Phys. Rev. D97 (2018), 086015.
  * [CCD+23] Chi-Fang, Chen, Alexander M. Dalzell, Mario Berta, Fernando G. S. L. Brandão, and Joel A. Tropp, _Sparse random Hamiltonians are quantumly easy_ , arXiv e-prints (2023), arXiv:2302.03394.
  * [CDEO08] M. Cramer, C. M. Dawson, J. Eisert, and T. J. Osborne, _Exact relaxation in a class of nonequilibrium quantum lattice systems_ , Physical Review Letters 100 (2008), no. 3.
  * [CEH+19] Shira Chapman, Jens Eisert, Lucas Hackl, Michal P. Heller, Ro Jefferson, Hugo Marrochio, and Robert C. Myers, _Complexity and entanglement for thermofield double states_ , SciPost Physics 6 (2019), 034.
  * [CHJLY17] Jordan Cotler, Nicholas Hunter-Jones, Junyu Liu, and Beni Yoshida, _Chaos, Complexity, and Random Matrices_ , JHEP 11 (2017), 048\.
  * [DF87] Persi Diaconis and David Freedman, _A dozen de Finetti-style results in search of a theory_ , Annales de l’I.H.P. Probabilités et statistiques 23 (1987), no. S2, 397–423 (en).
  * [DN05] Christopher M. Dawson and Michael A. Nielsen, _The Solovay-Kitaev algorithm_.
  * [Eis21] J. Eisert, _Entangling Power and Quantum Circuit Complexity_ , Phys. Rev. Lett. 127 (2021), 020501.
  * [GT05] Friedrich Goetze and A. Tikhomirov, _The rate of convergence for spectra of gue and lue matrix ensembles_ , Central European Journal of Mathematics 3 (2005), 666–704.
  * [HFK+21] Jonas Haferkamp, Philippe Faist, Naga B. T. Kothakonda, Jens Eisert, and Nicole Yunger Halpern, _Linear growth of quantum circuit complexity_.
  * [HM18] Lucas Hackl and Robert C. Myers, _Circuit complexity for free fermions_ , JHEP 2018 (2018), 139.
  * [HRC02] Aram W. Harrow, Benjamin Recht, and Isaac L. Chuang, _Efficient discrete approximations of quantum gates_ , J. Math. Phys. 43 (2002), 4445.
  * [JKP09] Nathaniel Johnston, David W. Kribs, and Vern I. Paulsen, _Computing stabilized norms for quantum operations via the theory of completely bounded maps_ , Quantum Info. Comput. 9 (2009), no. 1, 16–35.
  * [JW22] Yifan Jia and Michael M. Wolf, _Hay from the haystack: explicit examples of exponential quantum circuit complexity_.
  * [LC19] Guang Hao Low and Isaac L. Chuang, _Hamiltonian Simulation by Qubitization_ , Quantum 3 (2019), 163.
  * [Li22] Zhi Li, _Short Proofs of Linear Growth of Quantum Circuit Complexity_.
  * [Llo96] Seth Lloyd, _Universal Quantum Simulators_ , Science 273 (1996), no. 5278, 1073–1078.
  * [LP09] A. Lytova and L. Pastur, _Central limit theorem for linear eigenvalue statistics of random matrices with independent entries_ , The Annals of Probability 37 (2009), no. 5, 1778 – 1840.
  * [Mec19] Elizabeth S. Meckes, _The random matrix theory of the classical compact groups_ , Cambridge Tracts in Mathematics, Cambridge University Press, 2019.
  * [MPO21] Filip B. Maciejewski, Zbigniew Puchała, and Michał Oszmaniec, _Exploring quantum average-case distances: proofs, properties, and examples_ , 2021.
  * [MRA13] Lluí s Masanes, Augusto J. Roncaglia, and Antonio Acín, _Complexity of energy eigenstates as a mechanism for equilibration_ , Physical Review E 87 (2013), no. 3.
  * [NC11] Michael A. Nielsen and Isaac L. Chuang, _Quantum computation and quantum information_ , 10th ed., Cambridge University Press, 2011.
  * [NDGD06] Michael A. Nielsen, Mark R. Dowling, Mile Gu, and Andrew C. Doherty, _Quantum Computation as Geometry_ , Science 311 (2006), 1133.
  * [Nie05] Michael A. Nielsen, _A geometric approach to quantum circuit lower bounds_.
  * [OHHJ22] Michał Oszmaniec, Michał Horodecki, and Nicholas Hunter-Jones, _Saturation and recurrence of quantum complexity in random quantum circuits_ , 2022.
  * [OSH22] Michał Oszmaniec, Adam Sawicki, and Michał Horodecki, _Epsilon-nets, unitary designs, and random quantum circuits_ , IEEE Trans. Inf. Theory 68 (2022), 989.
  * [RPA22] Jonathon Riddell, Nathan Pagliaroli, and Álvaro M. Alhambra, _Concentration of quantum equilibration and an estimate of the recurrence time_ , arXiv e-prints (2022), arXiv:2206.07541.
  * [RY17] Daniel A. Roberts and Beni Yoshida, _Chaos and complexity by design_ , JHEP 04 (2017), 121.
  * [SS14] Douglas Stanford and Leonard Susskind, _Complexity and Shock Wave Geometries_ , Phys. Rev. D90 (2014), 126007.
  * [Sus16] Leonard Susskind, _Computational Complexity and Black Hole Horizons_ , Fortsch. Phys. 64 (2016), 44, [Fortsch. Phys.64,24(2016)].
  * [Sus18] , _Black Holes and Complexity Classes_.
  * [Var13] Péter Pál Varjú, _Random walks in compact groups_ , Doc. Math. 18 (2013), 1137.
  * [VŽ 12] Vinayak and Marko Ž nidarič, _Subsystem dynamics under random hamiltonian evolution_ , Journal of Physics A: Mathematical and Theoretical 45 (2012), no. 12, 125204.