author title [tocbeforeskip=1ex plus 1pt minus 1pt]section toc

# Hay from the haystack: explicit examples of exponential quantum circuit
complexity

Yifan Jia  Department of Mathematics, Technische Universität München, Germany
Munich Center for Quantum Science and Technology (MCQST), Germany
{yifan.jia<EMAIL_ADDRESS>Michael M. Wolf  Department of Mathematics,
Technische Universität München, Germany
Munich Center for Quantum Science and Technology (MCQST), Germany
{yifan.jia<EMAIL_ADDRESS>
###### Abstract

Abstract: The vast majority of quantum states and unitaries have circuit
complexity exponential in the number of qubits. In a similar vein, most of
them also have exponential minimum description length, which makes it
difficult to pinpoint examples of exponential complexity. In this work, we
construct examples of constant description length but exponential circuit
complexity. We provide infinite families such that each element requires an
exponential number of two-qubit gates to be generated exactly from a product
and where the same is true for the approximate generation of the vast majority
of elements in the family. The results are based on sets of large
transcendence degree and discussed for tensor networks, diagonal unitaries and
maximally coherent states.

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
    1. 2.1 Circuit complexity
    2. 2.2 Tensor network representations
  3. 3 Transcendence degree as lower bound for complexity
  4. 4 Explicit examples and their complexities
  5. 5 Hardness of approximation
    1. 5.1 Diagonal unitaries
    2. 5.2 Maximally coherent states
    3. 5.3 Uniformly distributed sets of examples
  6. A Results in transcendental number theory
  7. B Transcendence degree of Gibbs states

##  1 Introduction

In 1949 a simple counting argument led Claude Shannon to the observation that
almost every Boolean function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ requires
an exponential size Boolean circuit [Sha49]: the number of functions simply
outgrows the number of circuits of sub-exponential size. As simple as this
argument is, it appears to be hopelessly difficult to find explicit examples
for which a better-than-linear lower bound can be proven. Even a $4n$ linear
lower bound is currently out of reach [Blu83, FGHK16]. Apart from more
sophisticated (and more severe) reasons there is an obvious obstacle to
pinpointing ‘exponential hay’ in this haystack: for most functions not only
the circuit complexity but also the descriptive complexity is exponential.
That is, we are not able to talk about them efficiently.

The quantum world exhibits a similar problem. It is textbook knowledge that
most states and unitaries on an $n$-partite Hilbert space have exponential
quantum circuit complexity (cf. p.198 in [NC02] and [Kni95]). In fact, the
very possibility of this exponential size played a crucial role in the birth
of a vastly growing research direction [Sus16]. Yet, as in the classical case,
while linear lower bounds are known (e.g., for states with topological order
[BHV06, KP14]), super-linear lower bounds remain elusive.

The aim of this paper is to provide explicit examples of exponential quantum
circuit complexity. In order to achieve this, we follow a simple idea: small
circuits involve a small number of parameters and can thus only lead to
matrices with a small number of ‘independent entries’—made precise by the
_transcendence degree_. Large transcendence degree therefore implies large
circuit complexity. The transcendence degree is a tool that is well-known and
-established in algebraic complexity theory and was introduced to the analysis
of arithmetic circuits and formulas in [SS91] and [Kal85].

The prize one has to pay when resorting to such an algebraic tool, is that it
is difficult to obtain results that are reasonably stable under perturbations.
For this reason, we will first focus on _exact_ generation of states and
unitaries. In the second part of the paper, we will then extend the focus and
discuss results on approximate generation, but those will only achieve our
goal with some caveats. As pointed out in [Aar16], stronger results would
immediately imply complexity theoretic separations such as
$\mathsf{BQP}\neq\mathsf{P}^{\mathsf{\\#P}}$, at least when obtained for
states.

After introducing some basic notions and concepts, we will first study the
transcendence degree and its relation to circuit complexity with some
excursions to tensor networks. Then we will construct examples of large
transcendence degree and thus large circuit complexity and finally look into
some hardness-of-approximation implications.

##  2 Preliminaries

###  2.1 Circuit complexity

In this section we introduce some fundamental notions and definitions
concerning circuit complexity. The _quantum circuit complexity_ of a state or
unitary on an $n$-partite Hilbert space quantifies the number of local
building blocks that are required for their implementation. The Hilbert space
that we will consider is $(\mathbb{C}^{d})^{\otimes
n}\simeq\mathbb{C}^{d^{n}}$ for arbitrary $d\in\mathbb{N}$. That is, the local
system will be a qu$d$it and the ‘local building blocks’ will be one or two-
qudit gates. More specifically, we fix a _gate set_ $\mathcal{G}\subset
U(d^{2})$ that is assumed to be _universal_ , which means that the group it
generates is dense in $U(d^{2})$.111From a physical perspective it suffices to
generate a dense subset of the projective unitary group $U(d^{n})/U(1)$.
However, we will mostly disregard this quotient since it would make many of
the statements more cumbersome without changing their essence. In particular,
it would not change the $n$-dependence of the results since a global phase can
always be changed locally. This implies that for any $U\in U(d^{n})$ and any
$\epsilon>0$ there is a finite sequence of unitaries $U_{1},\ldots,U_{g}\in
U(d^{n})$ such that

$\|U-U_{1}U_{2}\cdots U_{g}\|_{\infty}\leq\epsilon,$ (1)

where each $U_{i}$ is up to a permutation of tensor factors of the form
$U_{i}\simeq V_{i}\otimes\mathbbm{1}_{d}^{\otimes(n-2)}$ with
$V_{i}\in\mathcal{G}$. The smallest number $g$ for which this is possible then
defines the quantum circuit complexity
$\mathcal{C}_{\epsilon}(U,\mathcal{G})$. We will often consider the entire
unitary group $U(d^{2})$ as a gate set and write
$\mathcal{C}_{\epsilon}(U):=\mathcal{C}_{\epsilon}(U,U(d^{2}))$. Clearly,
$\mathcal{C}_{\epsilon}(U)\leq\mathcal{C}_{\epsilon}(U,\mathcal{G})$ holds for
any $\mathcal{G}\subset U(d^{2})$. By the Solovay-Kitaev theorem [KSV02], an
inequality in the opposite direction can be proven as well. That is, if an
$n$-qudit unitary is hard to approximate with any finite universal gate set,
then the same is true with the gate library consisting of all one- and two-
qudit gates. This well-known fact is spelled out in the following Lemma for
the case of _efficiently universal_ gate sets, i.e., those which enable an
$\epsilon$-approximation within $SU(d^{2})$ with $g=O(\ln 1/\epsilon)$.
Efficiently universal gate sets with cardinality $|\mathcal{G}|\leq
3(d^{2}-1)$ were constructed in [HRC02].

######  Lemma 1 (Change of gate sets)

For every efficiently universal gate set $\mathcal{G}\subset SU(d^{2})$ there
is a constant222A more explicit expression for $c$ can be found in Eq.(14) of
[HRC02]. $c$ such that for every $U\in SU(d^{n})$ and $\epsilon>0$:

$\mathcal{C}_{2\epsilon}(U,\mathcal{G})\leq
c\;\mathcal{C}_{\epsilon}(U)\;\ln\frac{\mathcal{C}_{\epsilon}(U)}{\epsilon}.$
(2)

_Remarks:_ (i) It is unclear how restrictive the assumption is for
$\mathcal{G}$ to be efficiently universal, as opposed to merely universal
within $SU(d^{2})$. In the latter case, a bound similar to Eq.(2) holds if the
logarithm is taken to some power $p$. Depending on assumptions (e.g. whether
$\mathcal{G}$ includes inverses) proven bounds for $p$ range from $p=3$
[OSH22] over $p=3.97$ [DN06] to $p=O(\ln d)$ [BGT21]. (ii) The restriction to
the special (or projective) unitary group is necessary for the Solovay-Kitaev
theorem. However, since a global phase can be changed locally, without
additional $n$-dependence, the distinction between $SU(d^{n})$ and $U(d^{n})$
is not relevant for our purpose.

###### Proof.

$\mathcal{C}_{\epsilon}(U)=g$ implies Eq.(1) with each of the $U_{i}$ acting
non-trivially only on at most two qudits. Approximating each of the $U_{i}$’s
in turn via $\|U_{i}-U_{i,1}\cdots U_{i,m}\|_{\infty}\leq\nu$ (for some $\nu$
to be chosen later) by $m=c\ln(1/\nu)$ unitaries from $\mathcal{G}$, we obtain

$\Big{\|}U-\prod_{i=1}^{g}\prod_{\alpha=1}^{m}U_{i,\alpha}\Big{\|}_{\infty}\leq\epsilon+g\nu$
(3)

when reading the product in the right order. Eq.(3) then proves that
$\mathcal{C}_{\epsilon+g\nu}(U,\mathcal{G})\leq mg$, which implies the claimed
inequality when inserting $m$ and choosing $\nu=\epsilon/g$. ∎

If the entire unitary group $U(d^{2})$ is chosen as gate library, then even in
the exact case ($\epsilon=0$) every unitary $U\in U(d^{n})$ has finite circuit
complexity $\mathcal{C}_{0}(U)=O(d^{2n})$ [BOB05]. Moreover, since the set
$\\{U\in U(d^{n})|\mathcal{C}_{0}(U)\leq g\\}$ is compact, we have that

$\mathcal{C}_{0}(U)=g\quad\Rightarrow\quad\exists\epsilon>0:\;\mathcal{C}_{\epsilon}(U)=g.$
(4)

The definition of the mentioned quantum circuit complexities is easily
generalized from unitaries to states: the circuit complexity of a state is
defined as the minimum exact circuit complexity of all unitaries that generate
the considered state from a product state (up to $\epsilon$). In particular,
for $|\varphi\rangle\in(\mathbb{C}^{d})^{\otimes n}$:

$\mathcal{C}_{0}(|\varphi\rangle):=\min\left\\{\mathcal{C}_{0}(U)\;|\;\exists
U\in U(d^{n}):|\varphi\rangle=U(|0\rangle)^{\otimes n}\right\\}.$ (5)

More general notions of circuit complexity could be defined by allowing for
ancillas and/or measurements. However, these can all be bounded from below by
the size of the respective tensor network description.

Figure 1: a) Graphical depiction of a circuit that involves six gates and
represents a unitary on $(\mathbb{C}^{d})^{\otimes 5}$. b) The graph of the
corresponding tensor network representation has six internal vertices of
degree four. These are assigned tensors of the same degree that are contracted
according to the edges. c) The graph corresponding to a _matrix product state_
on $(\mathbb{C}^{d})^{\otimes 8}$.

###  2.2 Tensor network representations

We will employ a perspective on tensors that is targeted on their explicit
numerical representation. That is, we will consider tensors represented in a
given product basis so that they become multi-dimensional arrays of complex
numbers. For simplicity, we assume that each dimension has the same size, say
$d$, so that a tensor of order $n$ becomes a map
$\Psi:\mathbb{Z}_{d}^{n}\rightarrow\mathbb{C}$, i.e., for any
$j=(j_{1},\ldots,j_{n})\in\mathbb{Z}_{d}^{n}$, which specifies a location in
the array, $\Psi(j)$ is the corresponding complex number. A unitary $U$ that
acts on $(\mathbb{C}^{d})^{\otimes n}$, when represented in a product basis,
then becomes a tensor of order $2n$ that maps
$\mathbb{Z}_{d}^{n}\times\mathbb{Z}_{d}^{n}\ni(j,k)\mapsto\langle
j_{1},\ldots,j_{n}|U|k_{1},\ldots,k_{n}\rangle$.

A _tensor network representation_ of a tensor
$\Psi:\mathbb{Z}_{d}^{n}\rightarrow\mathbb{C}$ has two ingredients: a graph
and an assignment of tensors to the ‘internal’ vertices of that graph. More
precisely, the set $V$ of vertices of the graph is assumed to be a union
$V=V_{i}\cup V_{e}$ of $|V_{e}|=n$ ‘external’ (or ‘physical’) vertices that
have degree one and ‘internal’ (or ‘virtual’) vertices in $V_{i}$ of higher
degree. To each edge $e$ there is assigned a dimension parameter
$d_{e}\in\mathbb{N}$, which is constrained to $d_{e}=d$ if the edge connects
to an external vertex. In addition, each internal vertex $v\in V_{i}$ gets
assigned a tensor
$\psi_{v}:\mathbb{Z}_{d_{e_{1}}}\times\cdots\times\mathbb{Z}_{d_{e_{\delta}}}\rightarrow\mathbb{C}$,
where the order $\delta$ equals the degree of the vertex and the $e_{i}$’s are
the vertex’ edges. Finally, $\Psi$ is represented by the tensor network if it
is obtained from the product $\prod_{v\in V_{i}}\psi_{v}$ after contracting
(i.e., summing) over all indices that correspond to edges that connect
internal vertices.

If $N=|V_{i}|$ is the number of internal vertices, $\delta$ is a uniform upper
bound on their degree and $D:=\max_{e}\\{d_{e}\\}$ defines the ‘maximal bond
dimension’, then the number of complex numbers that specify the tensor network
is at most

$ND^{\delta}.$ (6)

The representation of a unitary $U$ on $(\mathbb{C}^{d})^{\otimes n}$ in terms
of a circuit of size $N$ can be regarded as a special case of a tensor network
representation with $D=d$ and $N$ internal vertices, each of degree $\delta=4$
(see Fig.1). Similarly, a state vector
$|\varphi\rangle\in(\mathbb{C}^{d})^{\otimes n}$ generated from a product
$|0\rangle^{\otimes(n+m)}$ via a unitary circuit of size $N$ and conditioned
on outcomes of local measurements on an $m$-partite ancilla has a tensor
network representation with $|V_{i}|=N$, $D=d$ and $\delta\leq 4$.

##  3 Transcendence degree as lower bound for complexity

For any set $S$ of complex numbers, we denote by $\mathbb{Q}(S)$ the number
field generated by $S$ over $\mathbb{Q}$, i.e., the minimal field extension of
the rational numbers that contains $S$. The algebraic closure of a field will
be indicated by a bar, so in particular $\overline{\mathbb{Q}}$ means the
field of complex algebraic numbers.

A set of numbers $\\{a_{1},\ldots,a_{n}\\}\subset\mathbb{C}$ is called
_algebraically independent_ if the only polynomial
$p\in\overline{\mathbb{Q}}[x_{1},\ldots,x_{n}]$ with algebraic coefficients
that satisfies $p(a_{1},\ldots,a_{n})=0$ is the zero-polynomial. This leads to
the central quantity of our analysis:

######  Definition 1 (Transcendence degree)

For $S\subseteq\mathbb{C}$ we define the _transcendence degree_
$\gamma(S)\in\mathbb{N}\cup\\{0,\infty\\}$ to be the maximal number of
algebraically independent elements of $S$.

_Remark:_ We will often apply $\gamma$ to structured sets such as matrices or
tensors. In that case, the additional structure is simply ignored so that only
the set of entries is considered. More specifically, for
$A\in\mathbb{C}^{n\times n}$ we have
$\gamma(A):=\gamma\big{(}\\{A_{i,j}\\}_{i,j=1}^{n}\big{)}$ and for a map
$\Psi:X\rightarrow\mathbb{C}$ we define
$\gamma(\Psi):=\gamma\big{(}\\{\Psi(x)\\}_{x\in X}\big{)}$.

The _transcendence degree_ is well-known and studied in the theory of field
extensions (see for instance Chap.V in [Mor96]). By definition, the maximal
number of algebraically independent elements does not change when going from
$S$ to the field it generates over $\mathbb{Q}$ or its algebraic closure.
Hence,

$\gamma(S)=\gamma\left(\mathbb{Q}(S)\right)=\gamma\left(\overline{\mathbb{Q}(S)}\right).$
(7)

The following summarizes properties of $\gamma$ that turn out to be useful in
our context:

######  Lemma 2 (Properties of the transcendence degree)

  1. 1.

The matrix product $AB$ of two matrices $A$ and $B$ satisfies

$\gamma(AB)\leq\gamma(A)+\gamma(B).$ (8)

  2. 2.

Every unitary $U\in\mathbb{C}^{d\times d}$ satisfies $\gamma(U)=\gamma(U\cup
U^{*})\leq d^{2}$. Moreover, the set of unitaries for which $\gamma(U)\neq
d^{2}$ is a null set w.r.t. the Haar measure on $U(d)$.

  3. 3.

If $A\in\mathbb{C}^{d\times d}$ has spectrum ${\mathrm{spec}(A)}$, then
$\gamma(A)\geq\gamma\big{(}{\mathrm{spec}(A)}\big{)}$.

###### Proof.

(1) Using Eq.(7) together with the definition of $\gamma$, we obtain
$\gamma(AB)=\gamma(\mathbb{Q}(AB))\leq\gamma(\mathbb{Q}(A\cup B))=\gamma(A\cup
B)\leq\gamma(A)+\gamma(B)$.

(2) Clearly, $\gamma(U)\leq d^{2}$ as this is maximal number of distinct
entries. Due to Eq.(7) we can assume that $-1\not\in{\mathrm{s}pec}(U)$ since
we can always multiply $U$ with an algebraic number $\omega$ of modulus one
and use that $\gamma(U)=\gamma(\omega U)$ as well as $\gamma(U\cup
U^{*})=\gamma(\omega U\cup\overline{\omega}U^{*})$. Under this assumption, the
Cayley transform $C(X):=(\mathbbm{1}+X)(\mathbbm{1}-X)^{-1}$, which happens to
be an involution, provides a skew-hermitian matrix $A:=C(U)$ such that
$U=C(A)$. Using Gauss elimination to compute the inverse and again Eq.(7), we
see that the Cayley transform does not change the transcendence degree. So
$\gamma(U)=\gamma(A)$. Moreover, $U^{*}=C(-A)$ implies that each matrix
element of $U^{*}$ is contained in $\mathbb{Q}(A)$ as well. Hence,
$\gamma(U\cup U^{*})=\gamma(A)=\gamma(U)$.

In order to see that the bound $\gamma(U)\leq d^{2}$ generically holds with
equality it suffices to show this for $\gamma(A)$ since the Cayley transform
maps Lebesgue null sets into Haar null sets and vice versa. $A$, however, can
be parametrized by $d^{2}$ real, unconstrained parameters. If these are not
all algebraically independent, then $d^{2}-1$ of them determine the last one
up to a countable number of alternatives. Due to $\sigma$-additivity of the
Lebesgue measure, $\gamma(A)\neq d^{2}$ is thus a null set. Hence,
$\gamma(U)\neq d^{2}$ also characterizes a null set w.r.t. the Haar measure.

(3) $\lambda\in{\mathrm{s}pec}(A)$ means that $p(\lambda)=0$ holds for the
characteristic polynomial $p(\lambda):=\det(\lambda\mathbbm{1}-A)$. The fact
that $p$’s coefficients are in $\mathbb{Q}(A)$ then implies that
${\mathrm{s}pec}(A)\subset\overline{\mathbb{Q}(A)}$ and therefore, by Eq.(7),
$\gamma\big{(}{\mathrm{spec}(A)}\big{)}\leq\gamma\big{(}\overline{\mathbb{Q}(A)}\big{)}=\gamma(A)$.
∎

With this Lemma at hand we can now prove lower bounds on the circuit
complexity in terms of the transcendence degree:

######  Theorem 1 (Transcendence degree vs. circuit complexity)

Let $U$ be a unitary matrix, $|\varphi\rangle$ a state vector and $\rho$ a
density matrix, all three represented in a product basis of
$(\mathbb{C}^{d})^{\otimes n}$. Then:

$\displaystyle\gamma\big{(}{\mathrm{s}pec}(U)\big{)}\ \leq\ \gamma(U)$
$\displaystyle\leq$ $\displaystyle d^{4}\;\mathcal{C}_{0}(U),$ (9)
$\displaystyle\gamma\big{(}{\mathrm{s}pec}(\rho)\big{)}\ \leq\ \gamma(\rho)$
$\displaystyle\leq$ $\displaystyle d^{4}\;\mathcal{C}_{0}(\rho),$ (10)
$\displaystyle\gamma\big{(}|\varphi\rangle\big{)}$ $\displaystyle\leq$
$\displaystyle d^{4}\;\mathcal{C}_{0}\big{(}|\varphi\rangle\big{)}.$ (11)

###### Proof.

The leftmost inequalities in Eqs.(9,10) are from (3) in Lemma 2. For the
second inequality in Eq.(9) suppose $U=\prod_{k=1}^{\mathcal{C}_{0}(U)}U_{k}$
is a minimal circuit for $U$ where each $U_{k}$ is (up to permutation of
tensor factors) of the form $U_{k}=\mathbbm{1}\otimes V_{k}$ with $V_{k}\in
U(d^{2})$. Using that $\gamma(\mathbbm{1}\otimes V_{k})=\gamma(V_{k})$ and
applying (1) and (2) from Lemma 2 we obtain

$\gamma(U)\leq\sum_{k=1}^{\mathcal{C}_{0}(U)}\gamma(U_{k})\leq
d^{4}\;{\mathcal{C}_{0}(U)}.$

This in turn implies Eq.(11) for $|\varphi\rangle=U|0\rangle^{\otimes n}$ via
$\gamma\big{(}|\varphi\rangle\big{)}\leq\gamma(U)+\gamma\big{(}|0\rangle^{\otimes
n}\big{)}$ as $\gamma\big{(}|0\rangle^{\otimes n}\big{)}=0$. Similarly, the
second inequality in Eq.(10) follows from a minimal circuit decomposition
$\rho=U\rho_{0}U^{*}$ via $\gamma(\rho)\leq\gamma(U\cup
U^{*})+\gamma(\rho_{0})$ by using that w.l.o.g. $\gamma(\rho_{0})=0$ and that
$\gamma(U\cup U^{*})=\gamma(U)$ as shown in (3) in Lemma 2. ∎

A similar result holds if we employ the more general perspective of tensors
and tensor network representations discussed in Sec.2.2. To put it simply, the
number of parameters of the network is an upper bound on the transcendence
degree of the tensor it represents:

######  Theorem 2 (Transcendence degree of tensor networks)

Let $\Psi:\mathbb{Z}_{d}^{n}\rightarrow\mathbb{C}$ be a tensor that admits a
tensor network representation with maximal bond dimension $D$ using $N$
internal vertices of degree at most $\delta$. Then

$\gamma(\Psi)\leq ND^{\delta}.$ (12)

###### Proof.

As discussed in Sec.2.2 and Eq.(6) the set $S:=\\{\psi_{v}(j)\\}_{v,j}$ of
complex numbers that specify the considered tensor network contains at most
$ND^{\delta}$ elements. As $\Psi$ is built up by algebraic operations from
$S$, we have that $\gamma(\Psi)\leq\gamma(\mathbb{Q}(S))=\gamma(S)\leq
ND^{\delta}$. ∎

A brief discussion of the transcendence degree of Gibbs states is provided in
Appendix.B.

##  4 Explicit examples and their complexities

Since we have bounded the circuit complexity below by the transcendence
degree, obtaining explicit examples of large circuit complexity is reduced to
finding explicit sets of large transcendence degree. According to _Schanuel’s
conjecture_ (Chap.21 in [MR14]), every set of complex numbers
$\alpha_{1},\ldots,\alpha_{n}$ that are linearly independent over $\mathbb{Q}$
should lead to

$\gamma\big{(}\\{\alpha_{1},\ldots,\alpha_{n},e^{\alpha_{1}},\ldots,e^{\alpha_{n}}\\}\big{)}\geq
n.$ (13)

In fact, most of the known transcendence results would follow from here. We
will, however, not resort to this conjecture. The explicit examples provided
in the following theorem rather follow from known results that can be viewed
as proven special cases or implications of Schanuel’s conjecture.

######  Theorem 3 (Explicit sets of large transcendence degree)

Consider any $n,d\in\mathbb{N}$ with $d\geq 2$.

  1. 1.

Let $p_{1},\dots,p_{n}$ be distinct prime numbers and
$t\in\overline{\mathbb{Q}}\setminus\\{0\\}$. Then

$\gamma\left(\big{\\{}e^{it\phi(j)}\big{\\}}_{j\in\mathbb{Z}_{d}^{n}}\right)=d^{n}\quad\text{for}\quad\phi(j):=\left(\prod\limits_{k=1}^{n}p_{k}^{j_{k}}\right)^{\frac{1}{d}}.$
(14)

  2. 2.

If $\alpha\neq 0,1$ is algebraic and $m>1$ is a square-free integer, then:

$\gamma\left(\Big{\\{}\alpha^{m^{\frac{k}{d}}}\Big{\\}}_{k=1}^{d-1}\right)\geq\frac{d}{2}.$
(15)

###### Proof.

(1) As shown in Cor.A.4 in Appendix A, Besicovitch’s theorem implies that
$\\{\phi(j)\\}_{j}$ is a set of $d^{n}$ algebraic numbers that are linearly
independent over $\mathbb{Q}$. Clearly, this remains true when multiplied by
$it$. By the Lindemann-Weierstrass theorem (Thm.A.1 in Appendix A), the
exponential function then lifts $\mathbb{Q}$-linear independence to algebraic
independence.

(2) is implied by the Diaz-Philippon theorem (Thm.A.5 in Appendix A) when
using that $m^{1/d}$ is an algebraic number of degree $d$. The latter can for
instance be seen as a consequence of Besicovitch’s theorem: if $m=p_{1}\cdots
p_{s}$ is the prime factorization of $m$ and we assume that there would be a
polynomial $p\in\mathbb{Q}[x]$ of degree less than $d$ that has $m^{1/d}$ as a
root, then $P(p_{1}^{1/d},\ldots,p_{s}^{1/d}):=p\big{(}(p_{1}\cdots
p_{s})^{1/d}\big{)}=0$ would contradict Besicovitch’s theorem. ∎

Combining the sets of large transcendence degree of Thm.3 with the complexity
bounds of Thm.1 and Thm.2 then finally leads to explicit examples of
exponential complexity. The following corollary makes this explicit for the
first construction of Thm.3:

######  Corollary 1 (Explicit examples of exponential circuit complexity)

Let $\\{|j\rangle\\}_{j\in\mathbb{Z}_{d}^{n}}$ be an orthonormal product basis
of $(\mathbb{C}^{d})^{\otimes n}$, $d\geq 2$,
$t\in(\overline{\mathbb{Q}}\cap\mathbb{R})\setminus\\{0\\}$ and $\phi(j)$ as
in Eq.(14).

  1. 1.

For $H:=\sum_{j}\phi(j)|j\rangle\langle j|$ the unitary $U:=e^{itH}$ satisfies

$\mathcal{C}_{0}(U)\geq d^{n-4}.$ (16)

  2. 2.

The state vector $|\varphi\rangle:=d^{-n/2}\sum_{j}\exp[it\phi(j)]\;|j\rangle$
satisfies

$\mathcal{C}_{0}(|\varphi\rangle)\geq d^{n-4}.$ (17)

Moreover, both $U$ and $|\varphi\rangle$ do not admit a tensor network
representation (as specified in Sec.2.2) with less than $d^{n}$ parameters.

_Remark:_ Using the spectral inequality of Thm.1 we get that Eq.(16) does not
only hold for $U$ but for every unitary that has the same spectrum as $U$. In
other words, the result is stable with respect to perturbations of the
eigenbasis.

Clearly, one can construct other examples by either using Eq.(14) in a
different way or by resorting to Eq.(15). Instead of doing this, however, we
broaden the focus and look into approximability of the examples provided in
Cor.1.

##  5 Hardness of approximation

So far, we have considered the exact (i.e., $\epsilon=0$) circuit complexity,
albeit with respect to a continuous gate set. As mentioned in Sec.2.1, for
every unitary $U\in U(d^{n})$ there is an $\epsilon>0$ so that
$\mathcal{C}_{\epsilon}(U)=\mathcal{C}_{0}(U)$. Replacing this purely
topological statement by an explicit quantitative bound, however, appears to
be more than difficult. In order to be able to make any quantitative statement
for _a given_ $\epsilon>0$ we will consider sets of examples of large
$\mathcal{C}_{0}$-complexity rather than individual instances. In a nutshell,
we will first quantify the statement that ‘most diagonal unitaries and most
maximally coherent states are hard to approximate’ and then show, by a uniform
density argument, that the same is true for each set of examples.

###  5.1 Diagonal unitaries

In this section we employ a standard counting argument [Kni95, NC02] to
quantify hardness of approximation for generic diagonal unitaries. In order to
get a countable set, we consider a finite gate library $\mathcal{G}\subset
U(d^{2})$. By Lemma 1, however, the derived results can easily be transferred
to the case of any other gate set, including infinite ones.

The following theorem makes the statement ‘almost all diagonal unitaries are
hard to approximate’ precise, by showing that the set that can be approximated
by circuits of sub-exponential size $O(d^{n}/\ln n)$ is double-exponentially
small.

######  Theorem 4 (Hardness of approximating diagonal unitaries)

For $\epsilon\in[0,1)$ and a universal gate set $\mathcal{G}\subset U(d^{2})$
with $k\in\mathbb{N}$ elements, let $\mathcal{U}_{g}$ be the set of unitaries
on $(\mathbb{C}^{d})^{\otimes n}$ whose complexity is bounded by $g$ so that

$\mathcal{U}_{g}:=\big{\\{}U\;|\;\mathcal{C}_{\epsilon}(U,\mathcal{G})\leq
g\big{\\}}\quad\text{with }\quad
g:=\left(\frac{\ln\frac{\pi}{2}}{2k}\right)\frac{d^{n}}{\ln n}\ .$ (18)

  1. 1.

If $\mathcal{D}$ is the diagonal subgroup of $U(d^{n})$ and $\mu$ its
normalized Haar measure, then

$\mu\big{(}\mathcal{D}\cap\mathcal{U}_{g}\big{)}\leq\big{(}\arcsin(\epsilon/2)\big{)}^{d^{n}}.$
(19)

  2. 2.

Let $\mathcal{D}_{\pm}$ be the subgroup of $U(d^{n})$ that contains all
diagonal unitaries with diagonal entries $\pm 1$. The fraction of
$\mathcal{D}_{\pm}$ that is contained in $\mathcal{U}_{g}$ is at most

$\left(\frac{\pi}{4}\right)^{d^{n}}.$ (20)

_Remarks:_ Note that $\arcsin(\epsilon/2)\simeq\epsilon/2$ up to
$O(\epsilon^{3})$. A result closely related to (1) can be found in [Nie06]
formulated in terms of geodesic lengths.

###### Proof.

(1) Write $U\in\mathcal{D}$ as
$U=\text{diag}\\{\exp(i\alpha_{1}),\dots,\exp(i\alpha_{d^{n}})\\}$ so that we
can identify the Haar measure on $\mathcal{D}$ with the normalized Lebesgue
measure on the cube $[0,2\pi)^{d^{n}}$, which contains the vector of phases
$\alpha$. Consider two diagonal unitary matrices $U$ and $U^{\prime}$ with
distance $\epsilon$ with respect to the $\infty$-norm. Their diagonal elements
satisfy $|e^{i\alpha^{\prime}_{j}}-e^{i\alpha_{j}}|\leq\epsilon$, which by a
simple geometric argument implies

$\displaystyle\inf\limits_{k\in\mathbb{Z}}|\alpha^{\prime}_{j}-\alpha_{j}-2\pi
k|\leq\tilde{\epsilon}:=2\arcsin(\frac{\epsilon}{2}).$ (21)

So if $B_{\epsilon}$ is an $\epsilon$-ball around $U$, then the normalized
Haar measure of its intersection with $\mathcal{D}$ can be bounded by

$\mu\big{(}\mathcal{D}\cap
B_{\epsilon}\big{)}\leq\frac{1}{(2\pi)^{d^{n}}}\int_{[-\tilde{\epsilon},\tilde{\epsilon}]^{d^{n}}}d\alpha_{1}\ldots
d\alpha_{d^{n}}=\left(\frac{\tilde{\epsilon}}{\pi}\right)^{d^{n}}.$ (22)

The number of unitaries that can exactly be represented by a circuit of $g$
two-qudit gates that are taken from $\mathcal{G}$ is at most
$\binom{n}{2}^{kg}$. If we consider an $\epsilon$-ball around each of them we
obtain the set $\mathcal{U}_{g}$. Hence,

$\displaystyle\mu\big{(}\mathcal{D}\cap\mathcal{U}_{g}\big{)}$
$\displaystyle\leq$ $\displaystyle\binom{n}{2}^{kg}\mu\big{(}\mathcal{D}\cap
B_{\epsilon}\big{)}$ (23) $\displaystyle\leq$
$\displaystyle\binom{n}{2}^{kg}\left(\frac{\tilde{\epsilon}}{\pi}\right)^{d^{n}}\leq\left(\frac{\tilde{\epsilon}}{2}\right)^{d^{n}},$
(24)

where we have inserted $g$ in Eq.(24) and used the asymptotically sharp bound
$\binom{n}{2}^{1/(2\ln n)}\leq e$.

(2) is proven along the same lines: we start with Eq.(23) with $\mathcal{D}$
replaced by $\mathcal{D}_{\pm}$ and where $\mu$ is now the counting measure
divided by $|\mathcal{D}_{\pm}|=2^{d^{n}}$. Since two different unitaries
$U,U^{\prime}\in\mathcal{D}_{\pm}$ satisfy $\|U-U^{\prime}\|_{\infty}=2$,
every ball of radius smaller than one contains at most one element of
$\mathcal{D}_{\pm}$. Consequently, $\mu(\mathcal{D}_{\pm}\cap
B_{\epsilon})\leq 2^{-d^{n}}$. Inserting this and arguing like for Eq.(24)
then leads to the claimed result. ∎

###  5.2 Maximally coherent states

A state vector $|\varphi\rangle=\sum_{j}\varphi_{j}|j\rangle$ is called
_maximally coherent_ with respect to a given orthonormal product basis
$\\{|j\rangle\\}_{j\in\mathbb{Z}_{d}^{n}}$ of $(\mathbb{C}^{d})^{\otimes n}$
if all its amplitudes have the same modulus $|\varphi_{j}|=d^{-n/2}$. We
denote the set of all maximally coherent state vectors in
$(\mathbb{C}^{d})^{\otimes n}$ by $\mathcal{S}$. Since $\mathcal{S}$ is the
orbit of $d^{-n/2}\sum_{j}|j\rangle$ under the diagonal unitary group
$\mathcal{D}$, the normalized Haar measure of the latter induces a normalized
measure on $\mathcal{S}$. With a slight abuse of notation we will write $\mu$
for both. Note that despite the connection between $\mathcal{D}$ and
$\mathcal{S}$, they behave very differently regarding the quantitative effect
of parameter changes: whereas changing a single parameter suffices to move a
diagonal unitary a constant $\epsilon$ (say $1/2$) away in operator norm, one
has to change a large fraction of parameters, i.e. $\Omega(d^{n})$, in order
to move a maximally coherent state by $\epsilon=1/2$ in norm. Nevertheless a
similar hardness-of-approximation result holds. The following theorem shows
that the subset of $\mathcal{S}$ that can be approximated by circuits of sub-
exponential size $O(d^{n}/\ln n)$ is double-exponentially small. The same is
true for the subset $\mathcal{S}_{\pm}\subset\mathcal{S}$ of $2^{d^{n}}$
maximally coherent states with real amplitudes $\varphi_{j}=\pm d^{-n/2}$.

######  Theorem 5 (Hardness of approximating maximally coherent states)

For $n,d\geq 2$ and a universal gate set $\mathcal{G}\subset U(d^{2})$ with
$k\in\mathbb{N}$ elements, let $\mathcal{S}_{g}$ be the set of maximally
coherent states on $(\mathbb{C}^{d})^{\otimes n}$ that admit an
$\epsilon$-approximation by a circuit of size $g$ in the sense that

$\mathcal{S}_{g}:=\big{\\{}|\varphi\rangle\in\mathcal{S}\;\big{|}\;\exists
U\in U(d^{n}):\mathcal{C}_{0}(U,\mathcal{G})\leq
g,\big{\|}|\varphi\rangle-U|0\rangle^{\otimes
n}\big{\|}\leq\epsilon\big{\\}}.$

If $g\leq d^{n}/(16k\ln n)$, then

$\displaystyle\mu\big{(}\mathcal{S}_{g}\big{)}$ $\displaystyle\leq$
$\displaystyle(4e)\exp\left[-\frac{d^{n}}{16}\right],\qquad\forall\epsilon\in[0,1]\quad\text{and}$
(25)
$\displaystyle\frac{|\mathcal{S}_{g}\cap\mathcal{S}_{\pm}|}{|\mathcal{S}_{\pm}|}$
$\displaystyle\leq$ $\displaystyle 2\exp\left[-\frac{d^{n}}{8}\right],\
\quad\qquad\forall\epsilon\in[0,3/4].$ (26)

###### Proof.

Define $D:=d^{n}$. Aiming at Eq.(25), we begin with bounding how much of
$\mathcal{S}$ is covered by a single $\epsilon$-ball. To this end, consider an
arbitrary unit vector $\phi\in\mathbb{C}^{D}$ as the center of a ball
$B_{\epsilon}$. Regarding $\psi$ as a $\mu$-uniform random variable with
values in $\mathcal{S}$, we can write

$\displaystyle\mu\big{(}\mathcal{S}\cap B_{\epsilon}\big{)}$ $\displaystyle=$
$\displaystyle\mathbb{P}_{\psi}\big{[}\|\phi-\psi\|\leq\epsilon\big{]}$ (27)
$\displaystyle\leq$
$\displaystyle\mathbb{P}_{\psi}\Big{[}\big{|}\langle\phi,\psi\rangle\big{|}\geq
1-\frac{\epsilon^{2}}{2}\Big{]},$

where we have used that
$|\langle\phi,\psi\rangle|\geq\real\langle\phi,\psi\rangle=1-\frac{1}{2}\|\phi-\psi\|^{2}$.
That $\psi$ is $\mu$-uniformly random means that its $D$ components are, when
multiplied by $\sqrt{D}$, i.i.d. random variables uniform on the complex unit
circle—so-called _Steinhaus variables_. Hence, we can apply the Hoeffding
inequality for Steinhaus sums from Cor.8.10 in [FR13], which yields

$\displaystyle\mathbb{P}_{\psi}\Big{[}\big{|}\langle\phi,\psi\rangle\big{|}\geq
1-\frac{\epsilon^{2}}{2}\Big{]}$ $\displaystyle\leq$ $\displaystyle
D\Big{(}1-\frac{\epsilon^{2}}{2}\Big{)}^{2}\exp\left[1-D\Big{(}1-\frac{\epsilon^{2}}{2}\Big{)}^{2}\right]$
(28) $\displaystyle\leq$
$\displaystyle\frac{D}{4}\;e^{1-\frac{D}{4}}\;\leq\;4\exp\left[1-\frac{3D}{16}\right],$

where the first inequality in Eq.(28) uses monotonicity in $\epsilon$ (for
$D\geq 4$, $\epsilon\in[0,1]$) and sets $\epsilon=1$ and the last inequality
exploits $1\leq e^{D/16}16/D$.

From here on, we can copy the corresponding part of the proof of Thm.4, which
after inserting the supposed upper bound on $g$ leads to

$\displaystyle\mu(\mathcal{S}_{g})$ $\displaystyle\leq$
$\displaystyle\binom{n}{2}^{kg}\mu\big{(}\mathcal{S}\cap
B_{\epsilon}\big{)}\;\leq\;4e^{D/8}e^{1-3D/16}\;=\;(4e)\exp\left[-\frac{D}{16}\right].$

Finally, Eq.(26) is proven along the same lines, with the only differences
that $\mu$ is replaced by the normalized counting measure, the appropriate
Hoeffding inequality is the one for Rademacher sums (Cor.8.8 in [FR13]) and,
for the sake of a simpler expression, we have used that
$(1-\epsilon^{2}/2)^{2}>1/2$ holds for all $\epsilon\in[0,3/4]$. ∎

###  5.3 Uniformly distributed sets of examples

Finally, we come back to the explicit examples provided in Cor.1. In order to
obtain hardness-of-approximation results for them, we form families of those
examples and show that these obey the same estimates as general diagonal
unitaries and maximally coherent states (derived in Sec.5.1 and Sec.5.2,
respectively). We begin with examples of unitaries.

Let us fix $n$ distinct primes $p_{1},\ldots,p_{n}$ (e.g. the first $n$
primes) and consider the following set of unitaries on
$(\mathbb{C}^{d})^{\otimes n}$:

$U_{t}:=\sum_{j\in\mathbb{Z}_{d}^{n}}|j\rangle\langle
j|\exp\left[it\prod_{k=1}^{n}p_{k}^{j_{k}/d}\right],\quad t\in\mathbb{N}.$
(29)

From Cor.1 we know that each of them satisfies $\mathcal{C}_{0}(U_{t})\geq
d^{n-4}$. The following theorem shows that the vast majority of the $U_{t}$’s
are also hard to approximate in the sense that for every $\epsilon\in[0,1)$
all but a double-exponentially small fraction of the $U_{t}$’s satisfy
$\mathcal{C}_{\epsilon}(U_{t},\mathcal{G})=\Omega(d^{n}/\ln n)$. The reason
for this is, loosely speaking, that the $U_{t}$’s are uniformly distributed
within the set of all diagonal unitaries. As a consequence, the same hardness-
of-approximation result (i.e., Thm.4) applies to asymptotically large sets of
them. To phrase it more mathematically, the sequence of atomic probability
measures $\mu_{N}(U_{t}):=1/N$ supported on $U_{1},\ldots,U_{N}$ converges
weakly to the Haar measure of the group of all diagonal unitaries in the limit
$N\rightarrow\infty$.

######  Theorem 6 (Hardness of approximation – unitary examples)

For $\epsilon\in[0,1)$, a universal gate set $\mathcal{G}\subset U(d^{2})$
with $k\in\mathbb{N}$ elements and

$g:=\left(\frac{\ln\frac{\pi}{2}}{2k}\right)\frac{d^{n}}{\ln n},$

define by
$r_{N}:=\frac{1}{N}|\big{\\{}U_{t}\;|\;\mathcal{C}_{\epsilon}(U_{t},\mathcal{G})\leq
g,\;t\leq N\big{\\}}|$ the fraction of the first $N$ unitaries defined in
Eq.(29) that have circuit complexity not larger than $g$. Then

$\lim_{N\rightarrow\infty}r_{N}\leq\big{(}\arcsin(\epsilon/2)\big{)}^{d^{n}}.$
(30)

###### Proof.

The statement follows from Thm.4 as a consequence of Weyl’s uniform version of
Kronecker’s density theorem [Wey16]. In order to see this, let us parametrize
an arbitrary diagonal unitary $U={\mathrm{d}iag}(e^{2\pi ix_{1}},e^{2\pi
ix_{2}},\ldots)$ by its vector of phases $x$, which is an element of the unit
cube $Q:=[0,1)^{d^{n}}$. The Lebesgue measure on $Q$ then corresponds to the
Haar measure of the group of diagonal unitaries. It will be convenient to
identify $Q$ with $\mathbb{R}^{d^{n}}\mod 1$, i.e., to allow for components
outside the unit-interval and consider them modulo 1.

Each $U_{t}$ is parametrized by a vector of the form $t\theta\in Q$ where
$\theta_{j}:=\phi(j)/(2\pi)$ with $\phi(j)$ defined in Eq.(14). As shown in
Cor.A.4 in Appendix A, the $d^{n}$ components of $\theta$ are linearly
independent over $\mathbb{Q}$. Moreover, they are all transcendental due to
the division by $\pi$ and the fact that the $\phi(j)$’s are algebraic. Hence
the numbers $1,\theta_{1},\theta_{2},\ldots$ are linearly independent over
$\mathbb{Q}$ so that by Weyl’s uniform distribution theorem (see p.48 in
[KN12]) the sequence $(t\theta)_{t\in\mathbb{N}}$ is uniformly distributed
$\mod 1$ in $Q$. This means that for all Jordan measurable subsets $J\subseteq
Q$ we have

$\lim_{N\rightarrow\infty}\frac{1}{N}\big{|}\big{\\{}t\theta\;|\;t\theta\in
J,t\leq N\big{\\}}\big{|}=\lambda(J),$ (31)

where $\lambda$ is the Lebesgue measure and all components are understood
$\mod 1$. Applying this to the specific set $J$ that corresponds to all
diagonal unitaries with circuit complexity not larger than $g$, we obtain in
the notation of Thm.4 and by using Eq.(19):

$\lim_{N\rightarrow\infty}\frac{1}{N}\big{|}\big{\\{}U_{t}\;|\;U_{t}\in\mathcal{U}_{g},t\leq
N\big{\\}}\big{|}=\mu(\mathcal{D}\cap\mathcal{U}_{g})\leq\big{(}\arcsin(\epsilon/2)\big{)}^{d^{n}}.$
(32)

The chosen $J$ is Jordan measurable since it is a finite union of at most
$\binom{n}{2}^{kg}$ bounded convex, and thus Jordan measurable, subsets. ∎

Now let us turn to the state examples. Still assuming distinct primes
$p_{1},\ldots,p_{n}$ we define the following family of maximally coherent
states:

$\psi_{t}:=d^{-n/2}\sum_{j\in\mathbb{Z}_{d}^{n}}|j\rangle\exp\left[it\prod_{k=1}^{n}p_{k}^{j_{k}/d}\right],\quad
t\in\mathbb{N}.$ (33)

Again, we know from Cor.1 that each of them satisfies
$\mathcal{C}_{0}(\psi_{t})\geq d^{n-4}$. Apart from a double-exponentially
small fraction, they are also hard to approximate:

######  Theorem 7 (Hardness of approximation – state examples)

For $n,d\geq 2$, $\epsilon\in[0,1]$, a universal gate set $\mathcal{G}\subset
U(d^{2})$ with $k\in\mathbb{N}$ elements and

$g:=\left(\frac{1}{16k}\right)\frac{d^{n}}{\ln n},$

define by
$r_{N}:=\frac{1}{N}|\big{\\{}\psi_{t}\;|\;\psi_{t}\in\mathcal{S}_{g},\;t\leq
N\big{\\}}|$ the fraction of the first $N$ examples defined in Eq.(33) that
admit an $\epsilon$-approximation by a circuit of size at most $g$. Then

$\lim_{N\rightarrow\infty}r_{N}\leq(4e)\exp\left[-\frac{d^{n}}{16}\right].$
(34)

###### Proof.

(sketch) Copying the proof of Thm.6 we obtain that
$r_{N}\rightarrow\mu(\mathcal{S}_{g})$ from which the result follows by
inserting the upper bound on $\mu(\mathcal{S}_{g})$ from Thm.5. ∎

Despite the intended greater physical relevance, the set-based approximation
results of Thm.6 and Thm.7 lose some of their appeal compared to the
individual exact-generation result of Cor.1. First, there is the statistical
nature of the results, which misses our goal to pinpoint explicit examples.
Second, while Cor.1 clearly produces examples of exponential circuit
complexity with constant description complexity, the hardness-of-approximation
results require asymptotically large $t$ so that the description complexity of
individual hard instances is not under control.

It should also be noted that not all unitaries $U_{t}$ or states $\psi_{t}$
are hard to approximate—precisely due to the uniform density argument used in
the proofs. For instance, for every $\epsilon>0$ there is a $t\in\mathbb{N}$
such that $\|U_{t}-\mathbbm{1}\|\leq\epsilon$ and similarly
$\|\psi_{t}-\psi_{0}\|\leq\epsilon$, where $\psi_{0}$ is a product state.

Remedying these shortcomings would be desirable, but might run up against
complexity-theoretic obstacles.

Acknowledgments. YJ thanks Aram Harrow for an insightful discussion, in
particular for pointing to ‘algebraic independence’.

Statements and Declarations. This work has been partially supported by the
Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under
Germany’s Excellence Strategy EXC-2111 390814868. YJ acknowledges support from
the TopMath Graduate Center of the TUM Graduate School and the TopMath Program
of the Elite Network of Bavaria.

##  Appendix A Results in transcendental number theory

In this section we collect results in transcendental number theory that are
used in the main text. For a general overview of the topic we refer to the
textbooks of Baker [Bak75] or Murty and Rath [MR14].

######  Theorem A.1 (Lindemann-Weierstrass, Thm. 1.4 in [Bak75])

If $\alpha_{1},\dots,\alpha_{n}$ are algebraic numbers that are linearly
independent over $\mathbb{Q}$, then $e^{\alpha_{1}},\dots,e^{\alpha_{n}}$ are
algebraically independent.

###### Corollary A.2

If $S\subset\overline{\mathbb{Q}}$ is an $n$-dimensional vector space over
$\mathbb{Q}$ and $E:=\\{e^{\lambda}|\lambda\in S\\}$, then $\gamma(E)=n$.

###### Proof.

The Lindemann-Weierstrass theorem A.1 implies that $\gamma(E)\geq n$. For the
converse inequality, suppose that $\\{a_{1},\ldots,a_{m}\\}\subset S$ fulfill
a non-trivial linear relation $\sum_{k=1}^{m}c_{k}a_{k}=0$ for some
$c_{k}\in\mathbb{Q}$. Then

$\prod_{k=1}^{m}\left(e^{a_{k}}\right)^{c_{k}}=1,$

which implies that the $\\{e^{a_{k}}\\}_{k=1}^{m}$ are algebraically
dependent. Therefore, $\gamma(E)$ cannot exceed $n$. ∎

######  Theorem A.3 (Besicovitch, [Bes40])

Let $p_{1},p_{2},\dots,p_{s}$ be distinct primes, $b_{1},b_{2},\dots,b_{s}$
positive integers not divisible by any of these primes and
$a_{i}:=(b_{i}p_{i})^{1/n_{i}}$ positive roots for $i=1,\ldots,s$ and
$n_{i}\in\mathbb{N}$. If $P\in\mathbb{Q}[x_{1},x_{2},\dots,x_{s}]$ is a
polynomial with rational coefficients of degree less than or equal to
$n_{1}-1$ with respect to $x_{1}$, less than or equal to $n_{2}-1$ with
respect to $x_{2}$, and so on, then $P(a_{1},a_{2},\dots,a_{s})=0$ can hold
only if $P=0$.

######  Corollary A.4 (see [Ric74] for a proof based on Galois theory)

Let $n,d\in\mathbb{N}$. For distinct prime numbers $p_{1},\dots,p_{n}$, the
following $d^{n}$ algebraic numbers are linearly independent over
$\mathbb{Q}$:

$\displaystyle\phi(j):=\left(\prod\limits_{k=1}^{n}p_{k}^{j_{k}}\right)^{\frac{1}{d}},\quad
j\in\mathbb{Z}_{d}^{n}.$ (35)

###### Proof.

This follows immediately from Besicovitch’s theorem (A.3) when setting
$b_{i}=1$ and arguing by contradiction: suppose there would be a non-trivial
linear relation of the form $\sum_{j\in\mathbb{Z}_{d}^{n}}c_{j}\phi(j)=0$ with
$c_{j}\in\mathbb{Q}$, then a non-zero polynomial $P$ of the form that is
excluded by Thm.A.3 would exist. ∎

For the following theorem, recall that the _degree_ of an algebraic number is
the minimal degree of a monic polynomial $p\in\mathbb{Q}[x]$ that has the
number as a root.

######  Theorem A.5 (Diaz [Dia89], Philippon [Phi86])

If $\alpha\neq 0,1$ is algebraic and $\beta\in\overline{\mathbb{Q}}$ has
degree $d\geq 2$, then $S:=\\{\alpha^{\beta},\ldots,\alpha^{\beta^{d-1}}\\}$
has $\gamma(S)\geq d/2$.

In fact, according to the Gel’fond-Schneider conjecture (see Chap.24 in
[MR14]) it might be $\gamma(S)\geq d$.

##  Appendix B Transcendence degree of Gibbs states

We will have a brief look at the transcendence degree of density matrices that
are represented as _Gibbs states_ of algebraic Hamiltonians. In this case the
transcendence degree of the density matrix is essentially equal to the
dimension of the spectrum of the Hamiltonian (as a basis of a vector space
over $\mathbb{Q}$):

######  Proposition B.1 (Transcendence degree of Gibbs states)

If $H\in\overline{\mathbb{Q}}^{d\times d}$ is Hermitian, and its spectrum
spans a $\mathbb{Q}$-vector space of dimension
$\dim_{\mathbb{Q}}\big{(}{\mathrm{s}pec}(H)\big{)}$, then
$\rho:=e^{H}/\tr[e^{H}]$ satisfies

$\gamma\left(\rho\right)\leq\dim_{\mathbb{Q}}\big{(}{\mathrm{s}pec}(H)\big{)}\leq\gamma\left(\rho\right)+1.$
(36)

###### Proof.

With $E:=\\{e^{\lambda}|\lambda\in{\mathrm{s}pec}(H)\\}$ and
$c:=\tr[e^{H}]^{-1}\in\mathbb{Q}(E)$ we use the spectral decomposition
$\rho=c\;UDU^{*}$, where the diagonal matrix $D$ has entries in $E$ and the
unitaries $U,U^{*}$ have entries in
$\overline{\mathbb{Q}(H)}=\overline{\mathbb{Q}}$. So
$\gamma(\rho)=\gamma(cD)$. Moreover, Cor.A.2 implies that
$\gamma(D)=\dim_{\mathbb{Q}}\big{(}{\mathrm{s}pec}(H)\big{)}$. From here the
claim follows since

$\displaystyle\gamma(cD)$ $\displaystyle\leq$
$\displaystyle\gamma\big{(}\mathbb{Q}(E)\big{)}=\gamma(D),$ (37)
$\displaystyle\gamma(D)$ $\displaystyle\leq$
$\displaystyle\gamma(c^{-1})+\gamma(cD)=1+\gamma(cD).$ (38)

Here, Eq.(37) has used that $c\in\mathbb{Q}(E)$ and Eq.(38) is based on
writing $D=c^{-1}cD$ and using the sub-additivity of the transcendence degree
specified in Eq.(8). ∎

## References

  * [Aar16] S. Aaronson.  The complexity of quantum states and transformations: From quantum money to black holes.  In Lecture Notes, 28th McGill Invitational Workshop on Computational Complexity, Holetown, Barbados, 2016. Bellairs Institute.
  * [Bak75] Alan Baker.  Transcendental Number Theory.  Cambridge Mathematical Library. Cambridge University Press, 1975.
  * [Bes40] Abram S Besicovitch.  On the linear independence of fractional powers of integers.  Journal of the London Mathematical Society, 1(1):3–6, 1940.
  * [BGT21] Adam Bouland and Tudor Giurgica-Tiron.  Efficient Universal Quantum Compilation: An Inverse-free Solovay-Kitaev Algorithm.  arXiv preprint arXiv:2112.02040, 2021.
  * [BHV06] S. Bravyi, M. B. Hastings, and F. Verstraete.  Lieb-Robinson Bounds and the Generation of Correlations and Topological Quantum Order.  Phys. Rev. Lett., 97:050401, July 2006.
  * [Blu83] Norbert Blum.  A Boolean function requiring 3n network size.  Theoretical Computer Science, 28(3):337–345, 1983.
  * [BOB05] Stephen S. Bullock, Dianne P. O’Leary, and Gavin K. Brennen.  Asymptotically optimal quantum circuits for $d$-level systems.  Phys. Rev. Lett., 94:230502, Jun 2005.
  * [Dia89] Guy Diaz.  Grands degrés de transcendance pour des familles d’exponentielles.  Journal of Number Theory, 31(1):1–23, 1989.
  * [DN06] Christopher M Dawson and Michael A Nielsen.  The Solovay-Kitaev algorithm.  Quantum Information and Computation, pages 81–95, 2006, arXiv preprint quant-ph/0505030.
  * [FGHK16] Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, and Alexander S. Kulikov.  A better-than-3n lower bound for the circuit complexity of an explicit function.  In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 89–98, 2016.
  * [FR13] S. Foucart and H. Rauhut.  A Mathematical Introduction to Compressive Sensing.  Applied and Numerical Harmonic Analysis. Springer New York, 2013.
  * [HRC02] Aram W Harrow, Benjamin Recht, and Isaac L Chuang.  Efficient discrete approximations of quantum gates.  Journal of Mathematical Physics, 43(9):4445–4451, 2002.
  * [Kal85] K. A. Kalorkoti.  A lower bound for the formula size of rational functions.  SIAM Journal on Computing, 14(3):678–687, 1985.
  * [KN12] L. Kuipers and H. Niederreiter.  Uniform Distribution of Sequences.  Dover Books on Mathematics. Dover Publications, 2012.
  * [Kni95] E. Knill.  Approximation by quantum circuits, 1995, quant-ph/9508006.
  * [KP14] Robert König and Fernando Pastawski.  Generating topological order: No speedup by dissipation.  Phys. Rev. B, 90:045101, July 2014.
  * [KSV02] A. Yu. Kitaev, A. H. Shen, and M. N. Vyalyi.  Classical and Quantum Computation.  American Mathematical Society, USA, 2002.
  * [Mor96] P. Morandi.  Field and Galois Theory.  Graduate Texts in Mathematics. Springer New York, 1996.
  * [MR14] Ram Murty and Purusottam Rath.  Transcendental Numbers.  Springer, 2014.
  * [NC02] Michael A Nielsen and Isaac Chuang.  Quantum computation and quantum information, 2002.
  * [Nie06] Michael A. Nielsen.  A geometric approach to quantum circuit lower bounds.  Quantum Info. Comput., 6(3):213–262, 2006.
  * [OSH22] Michał Oszmaniec, Adam Sawicki, and Michał Horodecki.  Epsilon-nets, unitary designs, and random quantum circuits.  IEEE Transactions on Information Theory, 68(2):989–1015, 2022.
  * [Phi86] Patrice Philippon.  Critères pour l’indépendance algébrique.  Publications Mathématiques de l’IHÉS, 64:5–52, 1986.
  * [Ric74] Ian Richards.  An application of Galois theory to elementary arithmetic.  Advances in Mathematics, 13(3):268–273, 1974.
  * [Sha49] Claude E Shannon.  The synthesis of two-terminal switching circuits.  The Bell System Technical Journal, 28(1):59–98, 1949.
  * [SS91] V. Shoup and R. Smolensky.  Lower bounds for polynomial evaluation and interpolation problems.  In [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science, pages 378–383, 1991.
  * [Sus16] Leonard Susskind.  Computational complexity and black hole horizons.  Fortschritte der Physik, 64:24–43, 2016.
  * [Wey16] H. Weyl.  Über die Gleichverteilung von Zahlen mod. Eins.  Mathematische Annalen, 77:313–352, 1916.


# On a limit behaviour of a random walk penalised in the lower half-plane

A. Pilipenko  Institute of Mathematics, National Academy of Sciences of
Ukraine, 3 Tereshchenkivska str., 01601, Kyiv, Ukraine; National Technical
University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Kyiv,
Ukraine<EMAIL_ADDRESS>and  Ben Povar  National Technical University
of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Department of Physics
and Mathematics, 03056, Kyiv, Ukraine, 37, Peremohy ave.
<EMAIL_ADDRESS>
###### Abstract.

We consider a random walk $\tilde{S}$ which has different increment
distributions in positive and negative half-planes. In the upper half-plane
the increments are mean-zero i.i.d. with finite variance. In the lower half-
plane we consider two cases: increments are positive i.i.d. random variables
with either a slowly varying tail or with a finite expectation. For the
distributions with a slowly varying tails, we show that
$\\{\frac{1}{\sqrt{n}}\tilde{S}(nt)\\}$ has no weak limit in
$\mathcal{D}[0,1]$; alternatively, the weak limit is a reflected Brownian
motion.

###### Key words and phrases:

Invariance principle, Reflected Brownian motion

###### 2000 Mathematics Subject Classification:

60F17; 60G50

A.Pilipenko was partially supported by the Alexander von Humboldt Foundation
within the Research Group Linkage Programme Singular diffusions: analytic and
stochastic approaches, the DFG Project _Stochastic Dynamics with Interfaces_
(PA 2123/7-1), and the National Research Foundation of Ukraine (project
2020.02/0014 “Asymptotic regimes of perturbed random walks: on the edge of
modern and classical probability”).

##  1\. Introduction and main results

Let random variables $\\{\xi_{n}\\}_{n\geq 1}$ be i.i.d. with a generic copy
$\xi$ and ${\mathbb{E}}\xi=0,\ {\mathbb{E}}\xi^{2}=\sigma^{2}$;
$\\{\eta_{n}\\}_{n\geq 1}$ are positive i.i.d., independent from the previous
ones and with a generic copy $\eta$. We consider a random walk $\tilde{S}$:

(1) $\tilde{S}(0)=0,\ \tilde{S}(n+1)=\begin{cases}\tilde{S}(n)+\xi_{n+1}\
\text{if}\ \tilde{S}(n)>0,\\\ \tilde{S}(n)+\eta_{n+1}\ \text{if}\
\tilde{S}(n)\leq 0.\end{cases}$

Figure 1. Sample path of $\tilde{S}$ (up to interpolation). Red vertical lines
show when the jump is distributed as $\eta$.

If $\tilde{S}(n)\in(0,\infty)$, then the random walk has increments
distributed as $\xi$ and on $(-\infty,0]$ as $\eta$. Jumps $\\{\eta_{n}\\}$
pushes the random walk up from the negative half-plane. This can be
interpreted as some non-immediate reflection to the positive half-plane.
Similar approach for stochastic differential equations is called the
penalization method and leads to a reflected diffusion if penalizations below
zero are big enough, see for example [Men83] or [Pil14, §1.4].

An interpretation of this model comes from the evaporation of gas from liquid
in physics, for example, a model of ballistic evaporation [JLF14]. The usual
form of speed distribution of a particle in a medium is Maxwell distribution.
But in case when there is a medium change (a particle bounces off liquid)
several papers have indicated that super- or sub-Maxwell distributions could
apply [JLF14], [HKF16], [KS16].

Another interpretation is the following. Consider an online shop with a
warehouse. Assume that the warehouse is replenished every day (e.g. under a
long-term contract) and also that the expectation of supply equals the
expectation of demand. So, the increments of the number of goods in the
warehouse are mean-zero random variables $\\{\xi_{k}\\}$ if the warehouse is
non-empty. In case when the virtual amount of goods in stock is negative,
i.e., the warehouse is empty and we have unsatisfied orders, the shop seeks to
refill the warehouse by buying batches of goods until it has a positive
balance. In our model this refilling corresponds to the sequence
$\\{\eta_{k}\\}$. If we consider a regular shop or a traditional queueing
model, then the unsatisfied orders would be discarded and the walk couldn’t
overjump a zero-level. While the shortage is not overcome (which may take some
time), the shop does not sell any goods.

Our goal is to analyse the limit of the scaled sequence of the processes
$\Big{\\{}\frac{1}{\sqrt{n}}\tilde{S}(nt),\ t\in[0,1]\Big{\\}}_{n\geq 1}$ as
$n\to\infty$. Depending on the distribution of $\eta$ we want to distinguish
two cases:

  1. (1)

$\eta$ has a finite expectation:

${\mathbb{E}}\eta<\infty.$

  2. (2)

the distribution of $\eta$ has a slowly varying tail

${\mathbb{P}}(\eta>x)\sim l(x),\ l\in R_{0},$

where $R_{0}$ a set of slowly varying functions (check definition 1.4.2 in
[BGT87]).

######  Remark 1.

Another interesting case is when the tail of $\eta$ is regularly varying,
i.e., $\eta$ belongs to the domain of attraction of an $\alpha$-stable
distribution. This case was studied in [PP14] with the restriction on $\xi$ to
be in $\mathbb{Z}$ and greater than or equal to $-1$. We conjecture that the
limit process should be the same as in [PP14], although we postpone the proof
for the future paper.

For the case $\mathrm{E}\eta<\infty$ we assume that $\tilde{S}$ is linearly
interpolated for $t\geq 0$:

$\tilde{S}(t)=\tilde{S}(\left\lfloor t\right\rfloor)+(t-\left\lfloor
t\right\rfloor)\tilde{S}(\left\lceil t\right\rceil).$

######  Theorem 1.

A sequence of processes

$\Big{(}\frac{\tilde{S}(nt)}{\sqrt{n}},\ t\in[0,1]\Big{)}_{n\geq 1}$

converges weakly in $\mathrm{C}[0,1]$ to a reflected Brownian motion:

$W_{\text{reflected}}(t):=W(t)-\min_{s\leq t}W(s).$

######  Remark 2.

It is well-known that $W_{\text{reflected}}$ has the same distribution as the
absolute value of a Brownian motion $|W|$, see for example Theorem 1.3.2 in
[Pil14].

For the second case we assume $\tilde{S}$ has a flat-right interpolation for
$t\geq 0$:

$\tilde{S}(t)=\tilde{S}(\left\lfloor t\right\rfloor).$

######  Theorem 2.

For a sequence of processes

$\Big{(}\frac{\tilde{S}(nt)}{\sqrt{n}},\ t\in[0,1]\Big{)}_{n\geq 1}$

there is no weak limit in $\mathcal{D}[0,1]$. Moreover for any $t>0$

(2) $\max_{s\leq
t}\frac{\tilde{S}(ns)}{\sqrt{n}}\stackrel{{\scriptstyle{\mathbb{P}}}}{{\to}}\infty,\
n\to\infty.$

Our results show that intuitively understandable things happen: when $\eta$
has an expectation, the process behaves like a Brownian motion with a
reflection; otherwise when $\eta$ has a slowly varying tail, the process blows
up at the beginning.

Note that model (1) is equivalent (up to recounting of $\xi_{i}$ and
$\eta_{i}$) to the following

(3) $\tilde{S}(0)=0,\
\tilde{S}(n)=\sum_{i=1}^{n-T(n)}\xi_{i}+\sum_{i=1}^{T(n)}\eta_{i},\ n\geq 1,$

where $T(n)$ is the number of visits to $(-\infty,0]$ before the time $n$:

(4) $T(n)=\\#\\{k<n:\tilde{S}(k)\leq 0\\},\ n\geq 1.$

We work only with this representation in the paper further.

Denote

(5) $S_{\xi}(n)=\sum_{i=1}^{n}\xi_{i},\ S_{\eta}(n)=\sum_{i=1}^{n}\eta_{i}.$

So

(6) $\tilde{S}(n)=S_{\xi}(n-T(n))+S_{\eta}(T(n)).$

We set by definition $S_{\xi}(t):=S_{\xi}(\left\lfloor t\right\rfloor),\
S_{\eta}(t):=S_{\eta}(\left\lfloor t\right\rfloor),T(t):=T(\left\lfloor
t\right\rfloor)$ for all $t\geq 0.$

Although the cases we discuss are very different, we tried to pick out common
traits in Section 2.

In Section 3 we prove Theorem 1. We aim to show that
$\frac{1}{\sqrt{n}}S_{\eta}(T(nt))$ converges to $-\min_{s\leq t}W(s)$ and do
so by showing that the latter lies neatly between
$\frac{1}{\sqrt{n}}S_{\eta}(T(nt)-1)$ and
$\frac{1}{\sqrt{n}}S_{\eta}(T(nt))+\frac{1}{\sqrt{n}}\max_{i\leq
nt}|\xi_{i}|$.

The proof of the second case can be found in Section 4 and is based on the
observation that the overshoots above level $n$ of the random walk $S_{\eta}$
are much larger than $n$. This is a known property, proved by Rogozin, see for
example Theorem 8.8.2 in [BGT87]. Thus we need to show that this overshoot
happens before $T(n)$ because only in this way it could affect $\tilde{S}$.

##  2\. Proof: shared part

Let $m$ be a (sign flipped) running minimum of $S_{\xi}$:

(7) $m(n)=-\min_{k\leq n}S_{\xi}(k).$

######  Lemma 1.

For each $n\geq 1$

(8) $S_{\eta}(T(n)-1)\leq m(n-T(n))<S_{\eta}(T(n))+\max_{i\leq n}|\xi_{i}|$

###### Proof.

The left inequality is trivial when $T(n)=1$. Assume that $T(n)>1$ and that
for some $n\geq 1$

(9) $S_{\eta}(T(n)-1)>m(n-T(n)).$

Take $k<n$, such that $T(n)=T(k+1)$ and $T(k)+1=T(n)$. This is always possible
since $T(n)>1$. Thus

$\tilde{S}(k)=S_{\xi}(k-T(k))+S_{\eta}(T(k))>-m(k-T(k))+S_{\eta}(T(n)-1).$

From (9) we infer that $\tilde{S}(k)>0$. Therefore $T(k)=T(k+1)$ which
contradicts with our choice of $k$.

As for the right hand side inequality, observe that $\tilde{S}$ jumps
downwards at $k\geq 1$ only when $\tilde{S}(k-1)>0$ and $S_{\xi}(k-T(k))$
jumps downwards. Thus for every $k\geq 1$

$-\max_{i\leq
k-T(k)}|\xi_{i}|\leq\tilde{S}(k)-\tilde{S}(k-1)<\tilde{S}(k)=S_{\xi}(k-T(k))+S_{\eta}(T(k)).$

Hence

$S_{\eta}(T(k))+\max_{i\leq k-T(k)}|\xi_{i}|\geq-S_{\xi}(k-T(k)).$

Taking maximum over $k\leq n$ of both sides of the last inequality we get

$S_{\eta}(T(n))+\max_{i\leq n}|\xi_{i}|\geq-\min_{k\leq
n}S_{\xi}(k-T(k))=-\min_{k\leq n-T(n)}S_{\xi}(k)=m(n-T(n)).$

∎

By the Donsker theorem

$\frac{1}{\sqrt{n}}S_{\xi}(n\cdot)\stackrel{{\scriptstyle w}}{{\to}}W(\cdot),\
n\to\infty,$

meaning a weak convergence in $\mathrm{C}[0,1]$. By the Skorokhod
Representation theorem (Theorem 6.7 in [Bil99]) we can construct a probability
space which supports random elements $\hat{S}_{\xi}^{(n)}$ and $\hat{W}$ such
that

$\hat{S}_{\xi}^{(n)}\stackrel{{\scriptstyle d}}{{=}}S_{\xi},\
\hat{W}\stackrel{{\scriptstyle d}}{{=}}W,\ n\geq 1$

and the uniform convergence holds

(10) $\frac{1}{\sqrt{n}}\hat{S}_{\xi}^{(n)}(nt)\rightrightarrows\hat{W}(t)\
\text{as}\ n\to\infty\ \text{a.s.}$

for $t\in[0,1]$.

To emphasize that we work on this new space we will write a $\hat{\text{hat}}$
whenever we use random variables dependent on $\hat{S}_{\xi}^{(n)}$. Without
loss of generality we may assume that this new probability space is reach
enough and contains a copy of the sequence $\\{\eta_{k}\\}_{k\geq 1}$. We
leave the same notation and assume that the original sequence
$\\{\eta_{k}\\}_{k\geq 1}$ belongs to this probability space. Using sequences
$\\{\hat{S}_{\xi}^{(n)}(k)\\}$ and $\\{S_{\eta}(k)\\}$ we construct copies
$\\{\hat{T}^{(n)}(k)\\},\ \\{\hat{\tilde{S}}^{(n)}(k)\\},\
\\{\hat{m}^{(n)}(k)\\}$ of $\\{T(k)\\},\ \\{{\tilde{S}}(k)\\},\\{m(k)\\}$
similarly to formulas (4), (7), (6). Note that in this constructions sequences
$\\{\hat{S}_{\xi}^{(n)}(k)\\}$ depend on $n$ but $\\{S_{\eta}(k)\\}$ does not.
Often we will leave out indexing by $n$, that is $\hat{S}_{\xi}^{(n)}$ becomes
$\hat{S}_{\xi}$.

It follows from inequality (8) that

(11) $S_{\eta}(\hat{T}(nt)-1)\leq\hat{m}(nt)\ \text{a.s.}$

for all $t\geq 0$.

Divide both sides by $\sqrt{n}$. By (10) we have

(12) $\forall\varepsilon_{1}>0\ \exists n_{1}\ \forall
n>n_{1}\quad\frac{1}{\sqrt{n}}S_{\eta}(\hat{T}(nt)-1)\leq-\min_{s\leq
t}\hat{W}(s)+\varepsilon_{1}\ \text{a.s.}$

Note that $\lim_{k\to\infty}\hat{T}(k)=+\infty$ a.s. because
$\liminf_{k\to\infty}S_{\xi}(k)=-\infty$ a.s. Thus

(13) $\forall\varepsilon_{1}>0\ \exists n^{\prime}_{1}\ \forall
n>n^{\prime}_{1}\quad\frac{\hat{T}(nt)-1}{\sqrt{n}}\leq\frac{\hat{T}(nt)-1}{S_{\eta}(\hat{T}(nt)-1)}(-\min_{s\leq
t}\hat{W}(s)+\varepsilon_{1})\ \text{a.s.}$

The strong law of the large numbers for $S_{\eta}$ implies

(14) $\limsup_{n\to\infty}\frac{\hat{T}(nt)}{\sqrt{n}}\leq\frac{-\min_{s\leq
t}\hat{W}(s)}{{\mathbb{E}}\eta}\ \text{a.s.}$

When ${\mathbb{E}}\eta=\infty$, the right hand side is $0$.

######  Corollary 1.

$\sup_{0\leq t\leq
1}\frac{T(nt)}{n}\stackrel{{\scriptstyle{\mathbb{P}}}}{{\to}}0,\ n\to\infty.$

###### Proof.

Since $\hat{T}$ is non-decreasing we have

$\sup_{0\leq t\leq 1}\frac{\hat{T}(nt)}{n}\leq\frac{\hat{T}(n)}{n}.$

Recall that $\hat{T}\stackrel{{\scriptstyle d}}{{=}}T$, hence the corollary
follows from (14). ∎

######  Lemma 2.

The uniform convergence on $[0,1]$ holds as $n\to\infty$

$\frac{\hat{m}(nt-\hat{T}(nt))}{\sqrt{n}}\rightrightarrows-\min_{s\leq
t}\hat{W}(t)\ \text{a.s.}$

###### Proof.

Equations (10) and (14) yield the uniform convergences on $[0,1]$

$\frac{1}{\sqrt{n}}\hat{m}(nt)=\frac{1}{\sqrt{n}}\hat{m}^{(n)}(nt)\rightrightarrows-\min_{s\leq
t}\hat{W}(t),\ \ n\to\infty,$

and

$t-\frac{\hat{T}(nt)}{n}=t-\frac{\hat{T}^{(n)}(nt)}{n}\rightrightarrows t,\ \
n\to\infty,$

with probability 1.

Since $t-\frac{\hat{T}(nt)}{n}\in[0,1]$ and the limit functions are
continuous, their compositions a.s. uniformly converge to the composition of
limits. ∎

######  Remark 3.

In Lemma 2 we may use both linear and piecewise constant approximation of the
corresponding processes.

##  3\. Proof of Theorem 1

It suffices to prove uniform convergence over $t\in[0,1]$ as $n\to\infty$

(15) $\frac{1}{\sqrt{n}}S_{\eta}(\hat{T}(nt))\rightrightarrows-\min_{s\leq
t}\hat{W}(s)\ \text{a.s.}$

The other part of the statement of Theorem 1 is provided by (10).

From Lemma 1 and Lemma 2 we infer that

(16)
$\displaystyle\limsup_{n\to\infty}\frac{1}{\sqrt{n}}S_{\eta}(\hat{T}(nt)-1)\leq-\min_{s\leq
t}\hat{W}(s)\ \text{a.s.}$ (17)
$\displaystyle\liminf_{n\to\infty}\Bigg{(}\frac{1}{\sqrt{n}}S_{\eta}(\hat{T}(nt))+\frac{\max_{i\leq
n}|\hat{\xi}_{i}|}{\sqrt{n}}\Bigg{)}\geq-\min_{s\leq t}\hat{W}(s)\
\text{a.s.}$

To prove (15) it suffices to show

(18) $\frac{\max_{i\leq
n}|\hat{\xi}_{i}|}{\sqrt{n}}\stackrel{{\scriptstyle{\mathbb{P}}}}{{\to}}0,\
n\to\infty.$

and

(19)
$\frac{1}{\sqrt{n}}|S_{\eta}(\hat{T}(nt))-S_{\eta}(\hat{T}(nt)-1)|=\frac{1}{\sqrt{n}}\eta_{\hat{T}(nt)}\stackrel{{\scriptstyle{\mathbb{P}}}}{{\to}}0,\
n\to\infty,$

Observe that for a given $\delta>0$ due to (14) it is always possible to
choose $K>0$ such that

${\mathbb{P}}(\hat{T}(n)\leq K\sqrt{n})>1-\delta.$

Hence both (18) and (19) follow from Theorem 6.2.1 in [Gut13].

##  4\. Proof of Theorem 2

It suffices to prove (2). Set

$N_{\eta}(x)=\inf\\{k:S_{\eta}(k)>x\\},\ x\geq 0.$

Let $c>0$, $K>0$, $0<\varepsilon<K$ and $0<t\leq 1$ be arbitrary real numbers,
then

(20) $\displaystyle\begin{split}\Big{\\{}\max_{i\leq
nt}\frac{\tilde{S}(i)}{\sqrt{n}}\geq c\Big{\\}}&=\Big{\\{}\max_{i\leq
nt}\Big{(}S_{\xi}(i-T(i))+S_{\eta}(T(i))\Big{)}\geq c\sqrt{n}\Big{\\}}\\\
&\supset\Big{\\{}\min_{i\leq
n}S_{\xi}(i)\geq-K\sqrt{n}\Big{\\}}\cap\Big{\\{}S_{\eta}(T(nt))>(K+c)\sqrt{n}\Big{\\}}\\\
&=\Big{\\{}\min_{i\leq
n}S_{\xi}(i)\geq-K\sqrt{n}\Big{\\}}\cap\Big{\\{}N_{\eta}((K+c)\sqrt{n})\leq
T(nt)\Big{\\}}\\\ &\supset\Big{\\{}\min_{i\leq
n}S_{\xi}(i)\geq-K\sqrt{n}\Big{\\}}\cap\Big{\\{}N_{\eta}(\varepsilon\sqrt{n})\leq
T(nt)\Big{\\}}\\\
&\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\cap\Big{\\{}\eta_{N_{\eta}(\varepsilon\sqrt{n})}>(K+c)\sqrt{n}\Big{\\}}.\end{split}$

For the second inclusion observe that if

$\eta_{N_{\eta}(\varepsilon\sqrt{n})}>(K+c)\sqrt{n},$

then automatically

$N_{\eta}((K+c)\sqrt{n})=N_{\eta}(\varepsilon\sqrt{n}).$

######  Lemma 3.

Let $j,l,a>0$ be real numbers such that $j+l<n$, then

$\Big{\\{}\min_{i\leq
j}S_{\xi}(i)\leq-a\Big{\\}}\cap\Big{\\{}T(n)<l\Big{\\}}\subset\Big{\\{}N_{\eta}(a)\leq
T(j+l)\Big{\\}}.$

###### Proof.

Suppose $\min_{i\leq j}S_{\xi}(i)=-A\leq-a$ and it is firstly attained at
$i=i^{*}\leq j$. Denote by $u$ the smallest solution of

$u-T(u)=i^{*}.$

Let $k$ be such that

$\tilde{S}(u)\leq\tilde{S}(u+1)\leq\dots\leq\tilde{S}(u+k-1)\leq
0<\tilde{S}(u+k),$

meaning that $\tilde{S}$ needs $k$ jumps to become positive. Observe that
$T(u)+k=T(u+k)$.

Assume $T(n)<l$. Then $k<l$. Thus

$u+k<j+l<n.$

As $k$ is such that $\tilde{S}(u+k)>0$, then from definition of $\tilde{S}$ we
deduce that $S_{\eta}(T(u+k))>A$ and so

$N_{\eta}(a)\leq N_{\eta}(A)\leq T(u+k)=T(i^{*}+T(u)+k)=T(i^{*}+T(u+k))\leq
T(j+l).$

∎

Apply Lemma 3 with $j=l=\frac{nt}{2}$ and $a=\varepsilon\sqrt{n}$ to further
inclusion (20)

(21) $\begin{split}&\Big{\\{}\max_{i\leq nt}\frac{\tilde{S}(i)}{\sqrt{n}}\geq
c\Big{\\}}\\\ \supset\Big{\\{}\min_{i\leq
n}S_{\xi}(i)\geq-K\sqrt{n}\Big{\\}}&\cap\Big{\\{}N_{\eta}(\varepsilon\sqrt{n})\geq
T(nt)\Big{\\}}\cap\Big{\\{}\eta_{N_{\eta}(\varepsilon\sqrt{n})}>(K+c)\sqrt{n}\Big{\\}}\\\
\supset\Big{\\{}\min_{i\leq
n}S_{\xi}(i)\geq-K\sqrt{n}\Big{\\}}&\cap\Big{\\{}\min_{i\leq
nt/2}S_{\xi}(i)\leq-\varepsilon\sqrt{n}\Big{\\}}\cap\Big{\\{}T(n)<\frac{nt}{2}\Big{\\}}\\\
&\cap\Big{\\{}\eta_{N_{\eta}(\varepsilon\sqrt{n})}>(K+c)\sqrt{n}\Big{\\}}.\\\
\end{split}$

Hence

(22) $\displaystyle\begin{split}\mathbbP\Big{(}\max_{i\leq
nt}\frac{\tilde{S}(i)}{\sqrt{n}}\geq c\Big{)}&\geq\mathbbP\Big{(}\text{r.h.s.
of \eqref{broader_road}}\Big{)}\\\ &=1-\mathbbP\Big{(}\text{complement to the
r.h.s. of \eqref{broader_road}}\Big{)}\\\ &\geq 1-\mathbbP\Big{(}\min_{i\leq
n}S_{\xi}(i)\leq-K\sqrt{n}\Big{)}-\mathbbP\Big{(}\min_{i\leq
nt/2}S_{\xi}(i)\geq-\varepsilon\sqrt{n}\Big{)}\\\
&-\mathbbP\Big{(}T(n)>\frac{nt}{2}\Big{)}-\mathbbP\Big{(}\eta_{N_{\eta}(\varepsilon\sqrt{n})}<(K+c)\sqrt{n}\Big{)}.\end{split}$

Let $\delta>0$ be an arbitrary small number. We proceed by proving that every
negative term in the r.h.s. of the last inequality is greater than $-\delta$
for $n$ big enough.

Choose $K>0$ and $0<\varepsilon<K$ so that

$\mathbbP\Big{(}|N_{\eta}(0,1)|>K\Big{)}<\delta,\quad\mathbbP\Big{(}|N_{\eta}(0,1)|<\varepsilon\sqrt{\frac{2}{t}}\Big{)}<\delta.$

Since

$-\min_{i\leq nt}\frac{S_{\xi}(i)}{\sqrt{n}}\overset{w}{\to}|N_{\eta}(0,t)|,\
n\to\infty,$

we get

$\limsup_{n\to\infty}\Bigg{(}\mathbbP\Big{(}\min_{i\leq
n}S_{\xi}(i)\leq-K\sqrt{n}\Big{)}+\mathbbP\Big{(}\min_{i\leq
nt/2}S_{\xi}(i)\leq-\varepsilon\sqrt{n}\Big{)}\Bigg{)}\leq 2\delta.$

It follows from Theorem 8.8.2 in [BGT87] that

(23)
$\frac{\eta_{N_{\eta}(\varepsilon\sqrt{n})}}{\sqrt{n}}\stackrel{{\scriptstyle{\mathbb{P}}}}{{\to}}\infty,\
n\to\infty.$

So the last term in the right hand side of (22) converges to 0.

Corollary 1 concludes the proof.

## References

  * [BGT87] N. H. Bingham, C. M. Goldie, and J. L. Teugels.  Regular variation.  Cambridge University Press, Cambridge, 1987.
  * [Bil99] P. Billingsley.  Convergence of Probability Measures.  Wiley, 1999.
  * [Gut13] A. Gut.  Probability: A Graduate Course.  Springer New York, 2013.
  * [HKF16] C. Hahn, Z. R. Kann, J. A. Faust, J. L. Skinner, and G. M. Nathanson.  Super-Maxwellian helium evaporation from pure and salty water.  The Journal of Chemical Physics, 144(4):044707, January 2016.
  * [JLF14] A. M. Johnson, D. K. Lancaster, J. A. Faust, C. Hahn, A. Reznickova, and G. M. Nathanson.  Ballistic evaporation and solvation of helium atoms at the surfaces of protic and hydrocarbon liquids.  The Journal of Physical Chemistry Letters, 5(21):3914–3918, October 2014.
  * [KS16] Z. R. Kann and J. L. Skinner.  Sub- and super-Maxwellian evaporation of simple gases from liquid water.  The Journal of Chemical Physics, 144(15):154701, April 2016.
  * [Men83] J. L. Menaldi.  Stochastic variational inequality for reflected diffusion.  Indiana University mathematics journal, 32(5):733–744, 1983.
  * [Pil14] A. Pilipenko.  An introduction to stochastic differential equations with reflection.  Potsdam:Universitatsverlag, 09 2014.
  * [PP14] A. Pilipenko and Yu. Prykhodko.  Limit behaviour of a simple random walk with non-integrable jump from a barrier.  Theory of Stochastic Processes, 19 (35)(1):52–61, 2014.