x

# Free Fermion Distributions Are Hard to Learn

Alexander Nietner Email<EMAIL_ADDRESS>Dahlem Center for Complex
Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany

###### Abstract

Free fermions are some of the best studied quantum systems. However, little is
known about the complexity of learning free-fermion distributions. In this
work we establish the hardness of this task in the particle number non-
preserving case. In particular, we give an information theoretical hardness
result for the general task of learning from expectation values and, in the
more general case when the algorithm is given access to samples, we give a
computational hardness result based on the LPN assumption for learning the
probability density function.

##  1 Introduction

In this note we investigate the learnability of the output distributions of
free fermion systems after measuring in the occupation number basis. We refer
to those distributions simply as _free fermion distributions_. This learning
task can be seen as the analogue to tomography of free fermion states from a
classical perspective.

Due to Wicks theorem it is known that tomography of free fermion states can be
done efficiently: the $n$-point correlators are fully determined by the
$2$-point correlators. In particular, a free fermion state is robustly
determined via its covariance matrix, which in turn is determined by the two
point correlators [GKE+18, SW19].

Here we establish the hardness of learning free fermion distributions. In
particular we focus on the general case, where the global particle number is
not fixed. This is, our results do not imply hardness of learning free fermion
distributions with a fixed particle number. While this work brings the
hardness-of-learning transition closer to the latter family of distributions,
our technique can not easily be applied to fixed particle number free fermion
distributions.

As established by [TD02], free fermions are closely related to local match
gate circuits as introduced in [Val02]. In particular, nearest neighbour one
dimensional match gate circuits are equivalent to nearest neighbour one
dimensional free fermionic circuits. Thus, the free fermion formalism mildly
generalizes the match gate formalism since the former can also be classically
simulated when the nearest neighbor criterion is dropped. This however can
also be emulated via match gates using a network of fermionic $\mathtt{SWAP}$
operations (i.e. $\mathtt{FSWAP}$) which comes at an at most linear overhead
in the system size. Thus the difference is only a mild one. We will use the
match gate formalism for our technical formulae and give the free fermion
interpretation in words.

###  1.1 Our Contribution

Our first result is concerned with learning algorithms that make use of
statistical averages, only.

######  Informal Theorem 1: (C.f. Corollary 1 and Corollary 2)

Free fermion distributions are exponentially hard to learn from empirical
expectation values.

Interestingly, this result is of information theoretic nature: the hardness is
due to the fact that any algorithm requires the values of exponentially many
expectation values in order to determine the underlying distribution. This is
in stark contrast to free fermion states: By Wick’s theorem all $k$-point
functions can be decomposed into combinations of $2$-point functions. Thus,
the linearly many $2$-point functions, which can be estimated from expectation
values, suffice to determine the corresponding quantum state2point.

2pointWe note that it is actually easy to see that any algorithm that tries to
learn free fermion distributions by means of two point functions only must
have some blind spots: The set of free fermion distributions contains all
tensor products of even parity distributions (c.f. Lemma 4). The even parity
distribution, on the other hand, has uniform marginals. Thus, there exist
pairs of distributions that can not be distinguished by the knowledge of all
two point functions.

Since Wicks theorem is at the core of the free fermion formalism, the lack of
its applicability for distribution learning hints at the possibility of a
stronger statement. The next statement goes into this direction as that it
allows the learner to have more general sample access to the true distribution
(instead of only empirical expectation values). It relies on the learning
parities with noise assumption, a standard assumption in cryptography [Reg09,
Pie12], and only applies with respect to an evaluator. This means, that we can
show hardness only when the algorithm is required to learn a program that is
able to compute the probability density function of the underlying
distribution (c.f. Section 2).

######  Informal Theorem 2: (C.f. Corollary 3 and Corollary 4)

Free fermion distributions are hard to learn from samples under the learning
parity with noise assumption.

The proofs of 1 and 2 follow closely those of Theorem 4 and Theorem 2 in
[HIN+22], respectively. In particular, we give a description for embedding
parities as well as noisy parities into free fermion distributions. The core
technical difficulty is that fermion distributions themselves carry a parity
constraint. It is not hard however to alleviate this by means of an additional
auxiliary mode.

##  2 Preliminaries

These preliminaries are sectioned into two parts. The first part is about
distribution learning and the second part is about free fermion, respectively
match gate distributions. While this may be safely skipped by readers familiar
with the topic we believe it is handy to align with our notation.

###  2.1 Distribution Learning

We denote by $\mathcal{F}_{n}$ the set of Boolean functions from
$\left\\{0,1\right\\}^{n}$ to $\left\\{0,1\right\\}$ and by $\mathcal{D}_{n}$
the set of probability distributions over $\left\\{0,1\right\\}^{n}$. The
parity of a bitstring $x$ is denoted by $\absolutevalue{x}$ and is given by
$\absolutevalue{x}=\sum_{i}x_{i}\mod 2$. A subset
$\mathcal{D}\subset\mathcal{D}_{n}$ is referred to as a distribution class.
For two probability distributions $P,Q:\\{0,1\\}^{n}\rightarrow[0,1]$, we
denote by
${\mathrm{d}_{\mathrm{TV}}(P,Q):=\frac{1}{2}\sum_{x\in\\{0,1\\}^{n}}|P(x)-Q(x)|}$
the total variation distance between them. Access to distributions is
formalized by an oracle with a specific operational structure. In this work,
we consider the sample and the statistical query oracle (see also [KMR+94,
Kea98, FGR+17]).

######  Definition 1: (Distribution oracles)

Given $P\in\mathcal{D}_{n}$ and some $\tau\in(0,1)$. We define:

  1. 1.

The sample oracle $\mathtt{Sample}(P)$ as the oracle which, when queried,
provides a sample $x\sim P$.

  2. 2.

The statistical query oracle $\mathtt{Stat}_{\tau}(P)$ as the oracle which,
when queried with a function $\phi:\\{0,1\\}^{n}\rightarrow[-1,1]$, responds
with some $v$ such that $|\operatorname*{\mathbf{E}}_{x\sim
P}[\phi(x)]-v|\leq\tau$.

We say that an oracle presents a distribution.

A learning algorithm has to output the distribution in the sense of some
representation. In this work we mainly focus on the two most popular
representations: generators and evaluators. These are formalizations of
generative and density models, respectively, and are defined as follows.

######  Definition 2: (Representations of a distribution)

Given $P\in\mathcal{D}_{n}$, we say that

  1. 1.

a probabilistic (or quantum) algorithm ${\mathtt{Gen}}(P)$ is a generator for
$P$ if it produces samples according to $x\sim P$.

  2. 2.

an algorithm $\mathtt{Eval}(P):\left\\{0,1\right\\}^{n}\to[0,1]$ is an
evaluator for $P$ if, on input $x\in\left\\{0,1\right\\}^{n}$ it outputs
$\mathtt{Eval}(P)[x]=P(x)$.

We say that a generator (evaluator) represents a distribution.

To formalize the notion of distribution learning, we use the framework
introduced in Ref. [KMR+94]. This definition is analogous to the definition of
probably-approximately correct function learning, in that it introduces
parameters $\epsilon$ and $\delta$ to quantify approximation error and
probability of success.

######  Problem 1: ($(\epsilon,\delta)$-distribution-learning)

Let $\epsilon,\delta\in(0,1)$ and let $\mathcal{D}$ be a distribution class.
Let $\mathcal{O}$ be a distribution oracle. The following task is called
$(\epsilon,\delta)$-distribution-learning $\mathcal{D}$ from $\mathcal{O}$
with respect to a generator (evaluator): Given access to oracle
$\mathcal{O}(P)$ for any unknown $P\in\mathcal{D}$, output with probability at
least $1-\delta$ a generator (evaluator) of a distribution $Q$ such that
$\mathrm{d}_{\mathrm{TV}}(P,Q)<\epsilon$.

######  Definition 3: (Efficiently learnable distribution classes)

Let $\mathcal{D}$ be a distribution class, and let $\mathcal{O}$ be a
distribution oracle. We say that $\mathcal{D}$ is computationally (query)
efficiently learnable from $\mathcal{O}$ with respect to a
generator/evaluator, if there exists an algorithm $\mathcal{A}$ which for all
$(\epsilon,\delta)\in(0,1)$ solves the problem of
$(\epsilon,\delta)$-distribution learning $\mathcal{D}$ from $\mathcal{O}$
with respect to a generator/evaluator, using
$O(\mathrm{poly}(n,1/\epsilon,1/\delta))$ computational steps (oracle
queries). Moreover, the generator/evaluator which is learned must itself be an
efficient algorithm, i.e. terminates after $O(\mathrm{poly}(n))$ many steps.

As we are most often concerned with computational efficiency and with the
sample oracle, we often omit these qualifiers in this case, and simply say
“$\mathcal{D}$ is efficiently learnable". If a distribution class is not
efficiently learnable, then we say it is hard to learn.

###  2.2 Free Fermion and Match Gate Distributions

Free fermion states are states that can be written as gaussian states in the
fermionic creation operators

$\displaystyle\ket{\psi}=\mathcal{N}\exp\left(\sum_{ij}G_{ij}c^{\dagger}_{i}c^{\dagger}_{j}\right)\ket{0}\,,$
(1)

where $G$ is an anti-symmetric generating matrix, $\mathcal{N}$ a
normalization term and the $c_{i}^{\dagger}$ are the fermionic creation
operators while $\ket{0}$ is the vacuum state. The amplitudes in the mode
basis are then given by

$\displaystyle\innerproduct{x}{\psi}=\mathcal{N}\mathrm{Pf}\left(G|_{x}\right)\,.$
(2)

Here, $\mathrm{Pf}$ is the Pfaffian and $G|_{x}$ denotes the anti symmetric
sub-matrix of $G$ indicated by the $1$’s in the bitstring $x$. Equivalently,
these states can be created by circuits of (particle number non-preserving)
free fermion unitaries. As shown in [TD02], on the level of qubits these
correspond to nearest neighbor match gate circuits on a line.

######  Definition 4: (Match Gate)

We say a $2$-qubit unitary of the form

$\displaystyle U=e^{i\phi}\begin{pmatrix}W_{11}&0&0&W_{12}\\\
0&Q_{11}&Q_{12}&0\\\ 0&Q_{21}&Q_{22}&0\\\ W_{21}&0&0&W_{22}\end{pmatrix}$ (3)

is a match gate if $W,Q\in\mathrm{SU}(2)$ and $\phi\in[0,2\pi)$. We denote by
$\mathcal{G}$ the set of all match gates. Quantum circuits composed of match
gates are referred to as match gate circuits.

Let us define two particularly important match gates in the context of this
work.

###### Definition 5:

The fermionic swap gate $\mathtt{FSWAP}$ is defined as

$\displaystyle\mathtt{FSWAP}=\begin{pmatrix}1&0&0&0\\\ 0&0&1&0\\\ 0&1&0&0\\\
0&0&0&-1\end{pmatrix}\,.$ (4)

Moreover we define

$\displaystyle U_{X}(t)=e^{itX\otimes
X}=\begin{pmatrix}\cos(t/2)&0&0&i\sin(t/2)\\\ 0&\cos(t/2)&i\sin(t/2)&0\\\
0&i\sin(t/2)&\cos(t/2)&0\\\
i\sin(t/2)&0&0&\cos(t/2)\end{pmatrix}=\cos(t/2)\mathds{1}_{4}+i\sin(t/2)X\otimes
X\,,$ (5)

where $X$ is the usual Pauli-$X$ gate.

The $\mathtt{FSWAP}$ gate is identical to the $\mathtt{SWAP}$ gate except for
the $-1$ phase in the $((11),(11))$ entry. This phase corresponds to the
fermionic statistics when swapping two occupied modes, thus the name fermionic
swap. Any non-local two body interaction in the fermionic formalism can be
represented by a circuit of local intereactions in the match gate formalism at
the price of a linear increase in the depth of the circuit.

Finally, we define the actual class of distributions we are interested in: the
Born distributions corresponding to free fermion states when measured in the
occupation umber basis. This is equivalent to measuring match gate states in
the computational basis. Thus we define the following.

######  Definition 6: (Match Gate Distributions)

We define the class of (nearest neighbour one dimensional) match gate
distributions on $n$ qubits at depth $d$ to contain all $n$-bit distributions
of the form

$\displaystyle P(x)=\absolutevalue{\matrixelement{x}{U}{0^{n}}}^{2}$ (6)

where $U$ is any nearest neighbour one dimensional match gate circuit on $n$
qubits of depth $d$. The set of all such distributions is denoted by
$\mathcal{M}(n,d)$ or simply $\mathcal{M}$.

The set of one dimensional nearest neighbor free fermion distributions is
identical to the set of match gate distributinos at the corresponding depth
and particle number. Similarly, we identify the set of non-local free fermion
distributions at a given depth with the set of local match gate distributions
at the same depth without the $\mathtt{FSWAP}$ gates taken into account.

##  3 Results

In this section we will show the hardness of learning $\mathcal{M}$ both, from
statistical queries as well as from samples. To this end we will embed
parities and then noisy parities. The hardness of learning then follows in
analogy to [HIN+22]. We begin with the following definition.

######  Definition 7: (Parity)

For any $s\in\\{0,1\\}^{n}$ denote by
$\chi_{s}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ the party function defined as

$\displaystyle\chi_{s}(x)=x\cdot s\,,$ (7)

where the scalar product is taken in $\mathds{F}_{2}^{n}$. Moreover the
corresponding parity distribution $D_{s}\in\mathcal{D}_{n+1}$ is defined as

$\displaystyle D_{s}(x,y)=\begin{cases}2^{-n}\,,&\chi_{s}(x)=y\\\
0\,&\text{else,}\end{cases}$ (8)

with $(x,y)\in\\{0,1\\}^{n}\times\\{0,1\\}$ and denote by $\mathcal{D}_{\chi}$
the set of all such distributions. For any noise rate $\eta\in[0,1]$ we define
the noisy parity distribution as

$\displaystyle D_{s}^{\eta}(x,y)=\begin{cases}(1-\eta)\cdot
2^{-n}\,,&\chi_{s}(x)=y\\\ \eta\cdot 2^{-n}\,&\text{else.}\end{cases}$ (9)

Denote the set of all such distributions by $\mathcal{D}_{\chi}^{\eta}$.

In this work we will focus on two distribution classes derived from those.
First consider the “fermionized” version of $\mathcal{D}_{\chi}$ (note that
this “fermionization” is not unique). Here, $\absolutevalue{x}$ denotes the
parity of $x$ and addition of bits refers to the modulo two addition as in
$\mathds{F}_{2}$ (such as $\absolutevalue{x}+y$ for bit string $x$ and bit
$y$).

###### Definition 8:

For any $s\in\\{0,1\\}^{n}$ define the fermionized parity function
$\xi_{s}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{2}$ as

$\displaystyle\xi_{s}(x)=\begin{pmatrix}\chi_{s}(x)\\\
\chi_{s}(x)+\absolutevalue{x}\end{pmatrix}\,.$ (10)

Next, we define the fermionized parity distribution
$M_{s}\in\mathcal{D}_{n+2}$ as

$\displaystyle
M_{s}(x,y,z)=\begin{cases}2^{-n}\,,&\chi_{s}(x)=y\,\text{and}\,\absolutevalue{x}+y=z\\\
0\,&\text{else.}\end{cases}=\begin{cases}2^{-n}\,,&\xi_{s}(x)=(y,z)\\\
0\,&\text{else.}\end{cases}$ (11)

The set of all such distributions is denoted by $\mathcal{M}_{\chi}$

The interpretation of $\xi_{s}$ and $M_{s}$ is as follows: Any fermionic state
has a parity constraint. Thus, we can not encode the distributions $D_{s}$
corresponding to a random example oracle for the parity function $\chi_{s}$
directly into a state on $n+1$ qubits. Rather, we need an auxiliary qubit that
takes care of the global parity constraint. This is done via Definition 8.

The following lemma states an equivalence between $M_{s}$ and $D_{s}$.

###### Lemma 1:

An evaluator (generator) for $M_{s}$ for some unknown $s$ implies an evaluator
(generator) for $D_{s}$ and vice versa.

###### Proof.

In case of an evaluator: Assume an evaluator for $M_{s}$, let
$(x,y)\in\\{0,1\\}^{n}\times\\{0,1\\}$. Define $z=\absolutevalue{x}+y$. Then
we can simulate an evaluator for $D_{s}$ as
$\mathtt{Eval}_{D_{s}}(x,y)=\mathtt{Eval}_{M_{s}}(x,y,z)$. Conversely,
assuming an evaluator for $D_{s}$, let
$(x,y,z)\in\\{0,1\\}^{n}\times\\{0,1\\}^{2}$. We first check whether
$\absolutevalue{x}+y=z$. If this is the case we compute
$\mathtt{Eval}_{M_{s}}(x,y,z)$ from $\mathtt{Eval}_{D_{s}}(x,y)$. Else we
return $0$.

In case of a generator we can simulate ${\mathtt{Gen}}_{D_{s}}$ by simply
discarding the last bit of the output of ${\mathtt{Gen}}_{M_{s}}$. Conversely,
we can simulate ${\mathtt{Gen}}_{M_{s}}$ from ${\mathtt{Gen}}_{D_{s}}$ by
sampling a bit string $(x,y)$ and appending $\absolutevalue{x}+y$. ∎

###  3.1 Statistical Query Lower Bound

With this in mind the following lemma the leads to hardness of learning
$\mathcal{M}_{\chi}$ in the statistical query setting.

######  Lemma 2: (Statistical Query Reduction)

Any statistical query to $\xi_{s}$ ($M_{s}$) with tolerance $\tau$ can be
simulated via two statistical queries to $\chi_{s}$ ($D_{s}$) with tolerance
$\frac{\tau}{2}$.

###### Proof.

Let $\phi:\\{0,1\\}^{n}\times\\{0,1\\}^{2}\rightarrow[-1,1]$ be a function
which we want to query. Then $\phi$ can be decomposed in three parts
$\phi=\phi_{e}+\phi_{o}+\phi_{0}$ where:

  * •

$\phi_{e}(x,y,z)=\vcentcolon\hat{\phi}_{e}(x,y)$ is non-zero only when
$(x,y,z)$ is such that $\absolutevalue{x}+y=z=0$.

  * •

$\phi_{o}(x,y,z)=\vcentcolon\hat{\phi}_{o}(x,y)$ is non-zero only when
$(x,y,z)$ is such that $\absolutevalue{x}+y=z=1$.

  * •

$\phi_{0}$ is such that $\operatorname*{\mathbf{E}}_{M_{s}}[\phi_{0}]=0$ for
all $s$.

Thus

$\displaystyle\operatorname*{\mathbf{E}}_{(x,y,z)\sim
M_{s}}\left[\phi(x,z,y)\right]=\operatorname*{\mathbf{E}}_{(x,z)\sim
D_{s}}\left[\hat{\phi}_{e}(x,y)\right]+\operatorname*{\mathbf{E}}_{(x,z)\sim
D_{s}}\left[\hat{\phi}_{o}(x,y)\right]\,,$ (12)

which implies that two statistical queries to $D_{s}$ with tolerance
$\frac{\tau}{2}$ suffice to simulate a statistical query to $M_{s}$ with
tolerance $\tau$. ∎

Thus, any statistical query algorithm for learning $\mathcal{M}_{\chi}$
implies a statistical query algorithm for learning $\mathcal{D}_{\chi}$ with
twice the query complexity. The latter is known to be exponentially hard
[BFJ+94] thus the former must be hard, too. This gives the following lemma.

###### Lemma 3:

Let $\epsilon<1/4$ and $\delta<1/2-2^{-3n}$. $(\epsilon,\delta)$-learning
$\mathcal{M}_{\chi}$ requires at least $\Omega(2^{n/3-2})$ statistical queries
with tolerance $\tau=\Omega(2^{-n/3+1})$.

Note, that we did not clarify the representation with respect to which the
learner has to learn. This is, because the proof is of information theoretic
nature and thus holds for any representation.

###### Proof.

The proof is analogous to the proof of Theorem 4 in [HIN+22]. Assume an
algorithm $\mathcal{A}$ which is able to $(\epsilon,\delta)$-learn
$\mathcal{M}_{\chi}$ for $\epsilon,\delta<1/2$ using $q$ many statistical
queries with tolerance $\tau$ and with respect to some representation. Using
Lemma 2 we obtain an algorithm $\mathcal{B}$ that given statistical query
access with tolerance $\tau/2$ to some
$D_{s}\in\mathcal{D}_{\chi}\subset\mathcal{D}_{n+1}$ learns the corresponding
representation for some $M\in\mathcal{D}_{n+2}$ such that
$\mathrm{d}_{\mathrm{TV}}(M,M_{s})<\epsilon$. We can use this representation
of $M$ to compute the corresponding underlying parity function without any
further statistical queries. To see this, note that for any $r\neq t$ it holds
$\mathrm{d}_{\mathrm{TV}}(M_{r},M_{t})\geq 1/2$. Thus, $s$ is the unique bit
string for which $M_{s}$ is at most $1/2-\epsilon<1/4$ far from $M$, which can
be found by brute force without any query to $D_{s}$.

In particular, algorithm $\mathcal{B}$ makes $2q$ statistical queries with
tolerance $\tau^{\prime}=\tau/2$ to $\mathcal{D}_{\chi}$ in order to learn the
correct parity function. Hence, for $\tau=\Omega(2^{-n/3+1})$ it must hold
that $q=\Omega(2^{n/3-2})$ [BFJ+94, Theorem 12]. ∎

With the following observation we can thus conclude that learning the
corresponding match gate distributions is hard.

###### Lemma 4:

$\displaystyle\mathcal{M}_{\chi}\subset\mathcal{M}(n,O(n))$ (13)

###### Proof.

Let $\mathrm{par}_{k}$ denote the uniform distribution on even parity bit
strings on $k$ bits

$\displaystyle\mathrm{par}_{k}(x)=\begin{cases}2^{-n+1}\,,\quad&\absolutevalue{x}=0\\\
0\,,&\text{else}\,.\end{cases}$ (14)

Every distribution $M_{s}$ can be written as

$\displaystyle M_{s}=\Pi\cdot(\mathrm{par}_{m}\otimes\mathrm{par}_{n+2-m})\,,$
(15)

where $\Pi$ is a permutation on $n+2$ bits consisting of swaps of bits only
and thus can be written as a linear depth network of $\mathtt{SWAP}$ gates,
and where $m-1\leq n$ is the number of $1$’s in $s$. To see this we note that
the parity constraint $z=\absolutevalue{x}+y$ is equivalent to
$z=\absolutevalue{x|_{\neg s}}$ where $x|_{\neg s}$ denotes the sub string of
$x$ labelled by the $0$’s in $s$.

Next we note that $\mathrm{par}_{k}$ can be realized as the Born distribution
of a depth $2$ match gate circuit on $k$ qubits. The corresponding circuit
consists only of $U_{X}(\pi/2)$ gates. To see this we note that $U_{X}(\pi/2)$
applied to $\ket{ij}$ flips with probability $0.5$ both bits to the state
$\ket{\neg i\neg j}$ and leaves both in the $\ket{ij}$ state with probability
$0.5$ (up to a phase). Thus, the depth two brick work circuit composed of
those gates applied to the all zero state creates every even parity bit string
with an equal probability.

Finally, we observe that applying an $\mathtt{FSWAP}$ before the measurement
has the same effect as applying a $\mathtt{SWAP}$ on the post measurement
distribution. In particular,

$\displaystyle D^{\otimes
2}\circ(\mathtt{FSWAP}\otimes\mathtt{FSWAP}^{\dagger})=\mathtt{SWAP}\circ
D^{\otimes 2}\,,$ (16)

where $\mathtt{FSWAP}\otimes\mathtt{FSWAP}^{\dagger}$ is the quantum channel
corresponding to $\mathtt{FSWAP}$ and $D$ is the local computational basis
measurement operator which maps the quantum state to its diagonal vector

$\displaystyle D(\outerproduct{i}{j})=\delta_{ij}\ket{i}\,.$ (17)

Combining this with Equation 15 we find that any $M_{s}$ can be implemented by
a depth $O(n)$ match gate circuit. ∎

Together with Lemma 7 in analogy to Theorem 4, both from [HIN+22], we obtain
the following corollary.

######  Corollary 1: (Local Free Fermion Distributions: Formal version of 1)

There is no efficient algorithm for learning $\mathcal{M}$ at depth
$d=\omega(\log(n))$ from inverse polynomial accurate queries. Equivalently,
learning $\mathcal{M}$ at depth $\Omega(n)$ from statistical queries with
tolerance $\tau=\Omega(2^{-n/3+1})$ requires $\Omega(2^{n/3-1})$ many queries.

From the perspective of free fermions it is also natural to consider the same
question without a locality constraint. On the level of match gates this
amounts as counting the $\mathtt{FSWAP}$ as a free resource. Comparing with
the proof of Lemma 4 we then find the following corollary which is probably
the strongest formulation of our result.

######  Corollary 2: (Non-local Free Fermion Distributions: Formal version of
1)

Learning non-local free fermion distributions at constant depth $d\geq 2$ from
statistical queries with tolerance $\tau=\Omega(2^{-n/3+1})$ requires
$\Omega(2^{n/3-1})$ many queries.

###  3.2 Hardness for Learning from Samples

Let us now consider the sample oracle. To this end we are going to embed the
learning parities with noise (LPN) problem into $\mathcal{M}$. The LPN problem
is defined in the context of probably approximately correct (PAC) learning.

######  Definition 9: (PAC learning)

Let $\epsilon,\delta>0$, let $\mathcal{C}$ be a class of boolean functions
$f:\\{0,1\\}^{n}\to\\{0,1\\}$ and let $D$ be a distribution over
$\\{0,1\\}^{n}$. We say an algorithm $\mathcal{A}$ efficiently
$(\epsilon,\delta)$-PAC learns $\mathcal{C}$ with respect to $D$ if, for any
$f\in\mathcal{C}$, the algorithm receives $N$ samples
$(x_{1},f(x_{1})),\dots,(x_{N},f(x_{N}))$ with $x\sim D$, and, with
probability $1-\delta$ returns a boolean function $h$, such that

$\displaystyle\operatorname*{\mathbf{Pr}}_{x\sim D}\left[f(x)\neq
h(x)\right]<\epsilon\,.,$ (18)

where the run time of $\mathcal{A}$ (and thus also the number of samples $N$)
is bounded by $O(\mathrm{poly}(n,1/\epsilon,1/\delta))$

######  Conjecture 1: (Learning Parities With Noise)

There is a constant $0<\eta<1/2$ such that there is no efficient algorithm for
learning parity functions under the uniform distribution in the PAC model with
classification noise rate $\eta$.

Thus, LPN states that there is a constant $\eta$ such that it is hard to learn
$s$ when given access to $D_{s}^{\eta}$. In [KMR+94] it is shown how this
implies hardness of learning $D_{s}^{\eta}$ with respect to an evaluator in
the sense of distribution learning. In particular, learning
$\mathcal{D}_{\chi}^{\eta}$ is at least as hard as LPN.

We will now embed $\mathcal{D}_{\chi}^{\eta}$ into $\mathcal{M}$ in order to
obtain the corresponding hardness result for match gates. Again we start by
defining the “fermionized” LPN distribution.

###### Definition 10:

For any $s\in\\{0,1\\}^{n}$ and noise rate $0\leq\eta\leq 1$ we define the
fermionized noisy parity distribution $M_{s}^{\eta}$ over $\\{0,1\\}^{n+2}$ as

$\displaystyle M_{s}^{\eta}(x,y,z)=\begin{cases}(1-\eta)\cdot
2^{-n}\,,&\chi_{s}(x)=y\,\text{and}\,\absolutevalue{x}+y=z\\\ \eta\cdot
2^{-n}\,,&\chi_{s}(x)=\neg y\,\text{and}\,\absolutevalue{x}+y=z\\\
0\,&\text{else.}\end{cases}=\begin{cases}(1-\eta)\cdot
2^{-n}\,,&\xi_{s}(x)=(y,z)\\\ \eta\cdot 2^{-n}\,,&\xi_{s}(x)=(\neg y,\neg
z)\\\ 0\,&\text{else.}\end{cases}$ (19)

The set of all such distributions is denoted by $\mathcal{M}_{\chi}^{\eta}$.

Again, the structure is such that, by definition, the distribution
$M_{s}^{\eta}$ is supported only on even parity strings and, on those, encodes
$D_{s}^{\eta}$. This is made clear in the following lemma similar to Lemma 1.

###### Lemma 5:

The generators ${\mathtt{Gen}}(D_{s}^{\eta})$ and
${\mathtt{Gen}}(M_{s}^{\eta})$ simulate each other, and hence the
corresponding sample oracles simulate each other. Similarly,
$\mathtt{Eval}(D_{s}^{\eta})$ and $\mathtt{Eval}(M_{s}^{\eta})$ simulate each
other.

###### Proof.

Let $(x,y)\sim D_{s}^{\eta}$. Then $(x,y,\absolutevalue{x}+y)\sim
M_{s}^{\eta}$. Contrarily, let $(x,y,z)\sim M_{s}^{\eta}$. Then $(x,y)\sim
D_{s}^{\eta}$.

The statement on evaluators follows in both directions from the defining
equation $D_{s}^{\eta}(x,y)=M_{s}^{\eta}(x,y,\absolutevalue{x}+y)$ together
with $M_{s}^{\eta}(x,y,\neg(\absolutevalue{x}+y))=0$. ∎

We are now able to show hardness of learning $\mathcal{M}_{\chi}^{\eta}$ with
respect to an evaluator.

###### Lemma 6:

Under the LPN assumption there is no efficient algorithm for learning
$\mathcal{M}_{\chi}^{\eta}$.

###### Proof.

The proof is analogous to the proof of Theorem 16 in [KMR+94]. Let
$\mathcal{A}$ be an algorithm that efficiently $(\epsilon,\delta)$-learns
$\mathcal{M}_{\chi}^{\eta}$. We will now construct an algorithm $\mathcal{B}$
that solves LPN. We first use Lemma 5 in order to efficiently transform the
noisy parity oracle to a sample oracle for some unknown $M_{s}^{\eta}$. We
then run $\mathcal{A}$ in order to obtain, with probability $1-\delta$ an
evaluator for a distribution $M$ with
$\mathrm{d}_{\mathrm{TV}}(M,M_{s}^{\eta})<\epsilon$. For a uniform random $x$
we can, with probability $1-\epsilon$ over the choice of $x$, compute
$\chi_{s}(x)$ by checking whether $M(x,0,\absolutevalue{x})$ or
$M(x,1,\absolutevalue{x}+1)$ is larger and return accordingly. Thus we can
$(\epsilon,\delta)$-PAC learn $\chi_{s}$ with respect to the uniform
distribution. We conclude, by 1 that $\mathcal{A}$ must be inefficient. ∎

We now show that the fermionized noisy parity distribution actually is
contained in $\mathcal{M}$.

###### Lemma 7:

$\displaystyle\mathcal{M}_{\chi}^{\eta}\subset\mathcal{M}(n,O(n))\,.$ (20)

###### Proof.

Let $\ket{\psi_{s}}$ be some match gate state that has $M_{s}$ as its Born
distribution (c.f. Lemma 4). Then, applying $U_{X}(t)$ to the $y,z$ register
of $\ket{\psi_{s}}$ with $\sin^{2}(t/2)=\eta$ results in a state
$\ket{\psi^{\prime}_{s}}$ with $M_{s}^{\eta}$ as corresponding Born
distribution. In particular

$\displaystyle\absolutevalue{\matrixelement{x,y,z}{\mathds{1}_{n}\otimes
U_{X}(t)}{\psi_{s}}}^{2}=\cos(t/2)^{2}\absolutevalue{\innerproduct{x,y,z}{\psi_{s}}}^{2}+\sin(t/2)^{2}\absolutevalue{\innerproduct{x,\neg
y,\neg z}{\psi_{s}}}^{2}=M_{s}^{\eta}(x,y,z)$ (21)

∎

This leads us to the following concluding corollary:

######  Corollary 3: (Local Free Fermion Distributions: Formal version of 2)

Assuming LPN, then for any $d=n^{\Omega(1)}$ there is no efficient algorithm
for learning $\mathcal{M}(n,d)$ with respect to an evaluator from samples.

Similarly to Corollary 2 we can make an even stronger statement in terms of
non-local free fermion distributions.

######  Corollary 4: (Non-local Free Fermion Distributions: Formal version of
2)

Assuming LPN there is no efficient algorithm for learning non-local free
fermion distributions with respect to an evaluator from samples at any
constant depth $d\geq 2$.

##  4 Conclusion and Discussion

In this work we have shown that it is hard to learn free fermion, or match
gate distributions. We have shown that algorithms with access only to
empirical expectation values require exponentially many queries to learn the
underlying distribution. Moreover, if the algorithm is given general sample
access to the underlying distribution the problem is still hard. In
particular, learning the probability density function, or an evaluator, is
still at least as hard as learning parity with noise. A problem that is
believed to be computationally hard.

Our work gives first results about the (non)-learnability of free fermion
distributions. However, many questions remain open. Two immediate questions
regard (1) the average case hardness of free fermion distributions in the
statistical query setting, similar to the analysis in [NIS+23] and (2) the
hardness of learning free fermion distributions with a fixed particle number.

## Acknowledgements

I am thankful to many fruitfull discussions with, in random order, Andreas
Bauer, Marek Gluza, Marcel Hinsche, Marios Ioannu, Lennart Bittel, Ryan Sweke,
Jonas Haferkamp and Jens Eisert. This work was supported by the BMBF (QPIC-1,
Hybrid), DFG (CRC 183), the BMBK (EniQmA), and the Munich Quantum Valley
(K-8).

## Notes

## References

  * [BFJ+94] A. Blum et al.  “Weakly learning DNF and characterizing statistical query learning using Fourier analysis”  In _Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC ’94_ Montreal, Quebec, Canada: ACM Press, 1994, pp. 253–262  DOI: 10.1145/195058.195147
  * [FGR+17] V. Feldman et al.  “Statistical algorithms and a lower bound for detecting planted cliques”  In _Journal of the ACM (JACM)_ 64 ACM New York, NY, USA, 2017, pp. 1–37  DOI: doi.org/10.1145/3046674
  * [GKE+18] M. Gluza, M. Kliesch, J. Eisert and L. Aolita  “Fidelity Witnesses for Fermionic Quantum Simulations”  In _Physical Review Letters_ 120.19, 2018, pp. 190501  DOI: 10.1103/PhysRevLett.120.190501
  * [HIN+22] Marcel Hinsche et al.  “A single $T$-gate makes distribution learning hard”  arXiv, 2022  arXiv:2207.03140
  * [Kea98] Michael Kearns  “Efficient noise-tolerant learning from statistical queries”  In _Journal of the ACM_ 45.6, 1998, pp. 983–1006  DOI: 10.1145/293347.293351
  * [KMR+94] M. Kearns et al.  “On the Learnability of Discrete Distributions”  In _Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing_ , STOC ’94  Montreal, Quebec, Canada: ACM, 1994, pp. 273–282  DOI: 10.1145/195058.195155
  * [NIS+23] Alexander Nietner et al.  “On the Average-Case Complexity of Learning Output Distributions of Quantum Circuits”  arXiv, 2023  arXiv:2305.05765
  * [Pie12] K. Pietrzak  “Cryptography from Learning Parity with Noise”  In _SOFSEM 2012: Theory and Practice of Computer Science_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 99–114  DOI: 10.1007/978-3-642-27660-6_9
  * [Reg09] O. Regev  “On Lattices, Learning with Errors, Random Linear Codes, and Cryptography”  In _J. ACM_ 56 New York, NY, USA: Association for Computing Machinery, 2009  DOI: 10.1145/1568318.1568324
  * [SW19] Brian G. Swingle and Yixu Wang  “Recovery Map for Fermionic Gaussian Channels”  In _Journal of Mathematical Physics_ 60.7, 2019, pp. 072202  DOI: 10.1063/1.5093326
  * [TD02] Barbara M. Terhal and David P. DiVincenzo  “Classical simulation of noninteracting-fermion quantum circuits” Publisher: American Physical Society  In _Physical Review A_ 65.3, 2002, pp. 032325  DOI: 10.1103/PhysRevA.65.032325
  * [Val02] L.. Valiant  “Quantum Circuits That Can Be Simulated Classically in Polynomial Time” Publisher: Society for Industrial and Applied Mathematics  In _SIAM Journal on Computing_ 31.4, 2002, pp. 1229–1254  DOI: 10.1137/S0097539700377025


Simple way to prove compactness of closed intervals in simply ordered set with
order topology
Sachin B. Bhalekar
Department of Mathematics,
Shivaji University,
Vidyanagar, Kolhapur - 416004, India
Email Address<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In this note, we present a simpler way to prove the compactness of the closed
intervals in simply ordered set with order topology.

Keywords: Compact set, simply order set, order topology.

##  1 Introduction

Compactness of a space is described using open sets only and it is preserved
under continuous functions. Hence it is a topological property. These spaces
are very important in Mathematical analysis ([1], Page 147). The historical
developments and original motivation of compactness is discussed in a nice
paper [2] by Sundstr’́om. This article deals with a simple proof of
compactness of closed intervals in a simply ordered set with order topology.

##  2 Preliminaries

In this section, we discuss some basic definitions and results from the
literature [1, 3].

###### Definition 2.1

Let $X$ be a set. A topology on $X$ is a collection $\tau$ of subsets of $X$
which is closed under arbitrary unions and finite intersections and contains
an empty set $\phi$ and the set $X$. Elements of $\tau$ are called open sets
in $X$.

###### Definition 2.2

A set $X$ is called simply ordered if there is a relation $``<"$ on $X$
satisfying the following properties:
1\. If $x,y\in X$ with $x\neq y$ then either $x<y$ or $y<x$.
2\. The relation $x<x$ does not hold for any $x\in X$.
3\. If $x<y$ and $y<z$ the $x<z$.

###### Definition 2.3

If $X$ is simply ordered set with the order relation $<$ and if $a$ and $b$
are elements in $X$ with $a<b$ then the open interval $(a,b)$ in $X$ is a set
$\left\\{x\in X|a<x<b\right\\}$ and closed interval $[a,b]$ in $X$ is a set
$\left\\{x\in X|a\leq x\leq b\right\\}$.

###### Definition 2.4

An ordered set $X$ is said to have the least upper bound (lub) property if
every nonempty subset of $X$ that is bounded above has lub.

###### Definition 2.5

Let $X$ be a simply ordered set with more than one elements. If $\mathcal{B}$
is collection of
1\. all open intervals $(a,b)$ in $X$,
2\. all intervals of the form $[a_{0},b)$ (respectively, $(a,b_{0}]$), where
$a_{0}$ (respectively, $b_{0}$) is the smallest (respectively, largest)
element, if any, of $X$
then it is a basis for a topology on $X$, called the order topology.

###### Definition 2.6

A sequence $\left\\{x_{n}\right\\}_{n=1}^{\infty}$ of points of the
topological space $X$ is said to converge to the point $x$ of $X$ if for each
open set $U$ containing $x$, $\exists$ $n_{0}\in\mathbb{Z}_{+}$ such that
$x_{n}\in U,$ $\forall$ $n>n_{0}$.

###### Lemma 2.1

Let $Y$ be a subspace of topological space $X$. Then $Y$ is compact if and
only if every covering of $Y$ by sets open in $X$ contains a finite
subcollection covering $Y$.

###### Theorem 2.1

A topological space is compact if every open cover by basis elements has a
finite subcover.

##  3 Main Result

Heine-Borel theorem shows that every closed and bounded interval of real line
is compact in standard topology. There is another way discussed in [4] which
divides the interval in two parts and uses the nested intervals theorem.
However, if we have arbitrary topological space with order topology then we
don’t have a metric on it. These approaches will not help us to prove the
compactness of closed intervals in such spaces. In [1], the proof is given in
four steps which is not easy. In this section, we present a new and simple way
to prove this Theorem 27.1 in [1].

###### Theorem 3.1

[1] Let $X$ be a simply ordered set having least upper bound property. In the
order topology, each closed interval in X is compact.

Proof: Suppose that the interval $[a,b]\in X$ is covered by the collection of
basis elements $\left\\{I_{\alpha}\right\\}_{\alpha\in J}$ in $X$, where
$I_{\alpha}=\left(a_{\alpha},b_{\alpha}\right)$ and $J$ is an index set.

Since $a,b\in[a,b]\subset\cup_{\alpha\in J}I_{\alpha}$, there exist indices
$\alpha_{1}$ and $\alpha_{2}$ in $J$ such that $a\in I_{\alpha_{1}}$ and $b\in
I_{\alpha_{2}}$. If $I_{\alpha_{1}}\cap I_{\alpha_{2}}$ is not empty then
$[a,b]\subseteq I_{\alpha_{1}}\cup I_{\alpha_{2}}$ and we are done. If not,
then as shown in Figure 1, $[a,b]\subseteq I_{\alpha_{1}}\cup
I_{\alpha_{2}}\cup\left[b_{\alpha_{1}},a_{\alpha_{2}}\right]$.

Figure 1: $[a,b]\subseteq I_{\alpha_{1}}\cup
I_{\alpha_{2}}\cup\left[b_{\alpha_{1}},a_{\alpha_{2}}\right]$

Now, consider the interval $\left[b_{\alpha_{1}},a_{\alpha_{2}}\right]$ which
is proper subset of $[a,b]$. By similar arguments, there exist indices
$\alpha_{3}$ and $\alpha_{4}$ in $J$ such that $b_{\alpha_{1}}\in
I_{\alpha_{3}}$ and $a_{\alpha_{2}}\in I_{\alpha_{4}}$. If $I_{\alpha_{3}}\cap
I_{\alpha_{4}}$ is not empty then $[a,b]\subseteq\cup_{j=1}^{4}I_{\alpha_{j}}$
and we are done. If not, then
$[a,b]\subseteq\cup_{j=1}^{4}I_{\alpha_{j}}\cup\left[b_{\alpha_{3}},a_{\alpha_{4}}\right]$.

Continuing this procedure, we construct a bounded sequence
$b_{\alpha_{1}}<b_{\alpha_{3}}<b_{\alpha_{5}}<\cdots$ in $[a,b]$. Since $X$
has least upper bound (lub) property, there exists lub $b_{*}$ of the set
$\left\\{b_{\alpha_{1}},b_{\alpha_{3}},b_{\alpha_{5}},\cdots\right\\}$. Note
that

$\lim_{j\longrightarrow\infty}b_{\alpha_{2j-1}}=b_{*}<b.$

Since $b_{*}\in[a,b]$, there exists $\alpha_{*}\in J$ such that $b_{*}\in
I_{\alpha_{*}}$. By definition of convergence of sequence, $\exists\,n_{0}$
such that

$b_{\alpha_{2j-1}}\in I_{\alpha_{*}},\quad\forall j>n_{0}.$

Therefore,

$[a,b]\subseteq\cup_{j=1}^{2n_{0}+1}I_{\alpha_{j}}\cup I_{\alpha_{*}}.$

Thus, $[a,b]$ is covered by finitely many basis elements. Hence, $[a,b]$ is
compact set in $X$.

##  4 Conclusion

In this article, we provided a simple proof of compactness of closed intervals
in simply order set with order topology. We hope that the students will find
this alternate way simpler than the one available in the literature.

## References

  * [1] J. R. Munkres, Topology, Second Edition, Prentice Hall of India, New Delhi, 2000.
  * [2] M. R. Sundstr’́om, A pedagogical history of compactness, The American mathematical monthly, 122(7), 619–635, (2015).
  * [3] G. F. Simmons, Introduction to topology and modern analysis, McGraw-Hill, New York, 1963.
  * [4] Xena, How to prove every closed interval in R is compact, URL (version: 2015-09-20): https://math.stackexchange.com/q/368172