# Homogeneous continuous images of smaller weight

István Juhász  Alfréd Rényi Institute of Mathematics<EMAIL_ADDRESS>and  Jan
van Mill  University of Amsterdam<EMAIL_ADDRESS>
###### Abstract.

We show that every infinite crowded space can be mapped onto a homogeneous
space of countable weight, and that there is a homogeneous space of weight
$\mathfrak{c}$ that cannot be mapped onto a homogeneous space of weight
strictly between $\omega$ and $\mathfrak{c}$.

###### Key words and phrases:

Homogeneous space, topological group, weight, continuous image.

###### 2020 Mathematics Subject Classification:

54A25, 54C05, 54D30

The first author was supported by NKFIH grant no. K129211.

##  1\. Introduction

For a space $X$, we let $w(X)$ denote its weight. Tkachenko [14] proved that
if $X$ is a Tychonoff space, then for every infinite regular cardinal
$\tau\leq w(X)$, there is a continuous image of $X$ of weight $\tau$. The same
result was obtained independently but later by Juhász in [9]. Several related
‘reflecting’ properties were found for the class of $\omega$-narrow
topological groups in [6]. It was shown there for example that every
$\omega$-narrow topological group $G$ admits a continuous homomorphism onto a
topological group of weight $\tau$, where $\tau\leq w(G)$ is any infinite
regular cardinal. See [6] for more results and references. It is an intriguing
problem whether the assumption about the regularity of $\tau$ is essential in
these results.

Although it is not stated explicitly in [6], their assumption on
$\omega$-narrowness is essential. Examples are easily found. Koppelberg [11]
proved that the homeomorphism group of any $D(2)^{\kappa}$,
$\kappa\geq\omega$, is algebraically simple (for $\kappa=\omega$, this is due
to Anderson [1]). Hence the homeomorphism group of $D(2)^{\omega_{1}}$ endowed
with the compact-open topology, being of weight $\omega_{1}$, does not admit a
continuous homomorphic image of weight $\omega$.

As far as we know, for the class of topologically homogeneous spaces no
‘reflecting’ properties were obtained in the literature. Since there are many
for topological groups, it is a natural question whether these can be extended
to the more general class of homogeneous spaces. See [3] for a survey
containing old and new problems on homogeneous spaces. We show that the
results on topological groups mentioned above cannot be extended in
$\mathsf{ZFC}$ to homogeneous spaces by proving that every infinite crowded
space can be mapped onto an infinite homogeneous space of countable weight,
and that there is a homogeneous space of weight $\mathfrak{c}$ that cannot be
mapped onto any homogeneous space of weight strictly between $\omega$ and
$\mathfrak{c}$. We also comment on the cardinality of (generalizations of)
almost-compact spaces.

##  2\. Continuous images of countable weight

In this and the next section, all spaces under discussion are Tychonoff.

As usual, $\mathbb{N}$, $\mathbb{R}$ and $\mathbb{I}$ denote the spaces of
natural numbers, real numbers and the closed interval $[0,1]$, respectively.

######  Lemma 2.1.

Every infinite crowded space maps onto $\mathbb{N}$ or $\mathbb{I}$.

###### Proof.

Assume that there is a continuous map $f\colon X\to\mathbb{R}$ such that
$f(X)$ is not zero-dimensional. Then $f(X)$ contains a nontrivial closed
interval $J$ on which $f(X)$ can be retracted. Hence we may assume that for
all continuous functions $f\colon X\to\mathbb{R}$, $f(X)$ is zero-dimensional.
As a consequence, $X$ is zero-dimensional.

Assume that there is a continuous function $f\colon X\to\mathbb{R}$ such that
$f(X)$ is not compact. Then $f(X)$ contains a closed copy of $\mathbb{N}$ on
which $f(X)$, being zero-dimensional, can be retracted. Hence we can assume
that for all continuous functions $f\colon X\to\mathbb{R}$, $f(X)$ is compact;
that is, $X$ is pseudocompact.

Assume that there is a continuous function $f\colon X\to\mathbb{R}$ such that
$f(X)$ is uncountable. Then $f(X)$, being compact, contains a Cantor set $K$.
And since $f(X)$ is zero-dimensional, it can be retracted onto $K$. Now it
suffices to observe that $K$ can be mapped onto $\mathbb{I}$.

Let $bX$ be a zero-dimensional compactification of $X$. Since $bX$ is crowded
and zero-dimensional, there is a continuous surjection $f\colon bX\to
D(2)^{\omega}$. But then by pseudocompactness of $X$, $f(X)=D(2)^{\omega}$,
and so we are done by what we just observed. ∎

######  Corollary 2.2.

Every infinite crowded space can be mapped onto an infinite homogeneous space
of countable weight.

###### Proof.

Simply observe that by collapsing the two endpoints of $\mathbb{I}$ to a
single point, we obtain a homogeneous space. ∎

The lemma and corollary are not true if $X$ is not crowded. For let
$X=W(\omega_{1})$, the space of all countable ordinal numbers. Then every
continuous image of $X$ of countable weight, is compact and countable. Hence
has an isolated point. Hence if it is infinite, it is neither $\mathbb{N}$ nor
$\mathbb{I}$, and not homogeneous.

##  3\. Continuous images of uncountable weight

We now formulate and prove the main result in this note.

######  Theorem 3.1.

There is a homogeneous space of weight $\mathfrak{c}$ such that if $f\colon
X\to Y$ is a continuous surjection and $\omega<w(Y)<\mathfrak{c}$, then $Y$ is
not homogeneous.

Let $\mathcal{A}$ be a Mrówka family on $\omega$. That is, $\mathcal{A}$ is a
MAD-family such that the Čech-Stone compactification of $\Psi(\mathcal{A})$,
the $\Psi$-space $\omega\cup\mathcal{A}$ of $\mathcal{A}$, coincides with its
1-point compactification. That is, $\Psi(\mathcal{A})$ is _almost-compact_.
That such a family exists is well-known, Mrówka [12] (see also [7, 8.6.1]).
The family $\mathcal{A}$ has cardinality $\mathfrak{c}$ by construction, hence
$w(\Psi(\mathcal{A}))=\mathfrak{c}$.

Now in $\Psi(\mathcal{A})$ we replace every point of $\omega$ by a copy of the
Cantor set $K=D(2)^{\omega}$ to obtain a space $X$, as follows. The underlying
set of $X$ is $(\omega\times K)\cup\mathcal{A}$. A basic neighborhood of a
point $\langle n,k\rangle$, where $n\in\omega$ and $k\in K$, has the form
$\\{n\\}\times C$, where $C$ is any open neighborhood of $k$ in $K$. And a
basic neighborhood of $A\in\mathcal{A}$ in $X$ has for $n\in\omega$ the form
$U_{n}(A)=\\{A\\}\cup\bigcup\\{\\{m\\}\times K:m\in A,m\geq n\\}$. It is clear
that $X$ is zero-dimensional and locally homeomorphic to $K$, hence $X$ is
homogeneous.

Let $f\colon X\to\Psi(\mathcal{A})$ be the function that sends $A$ in $X$ to
$A$ in $\Psi(\mathcal{A})$, for every $A\in\mathcal{A}$, and every
$\\{n\\}\times K$ to $\\{n\\}$, for $n\in\omega$.

######  Lemma 3.2.

$f$ is perfect and open.

###### Proof.

It is clear that $f$ is continuous and has compact fibers. It is also clear
that $f$ is open. Hence it suffices to prove that $f$ is closed. To this end,
let $E$ be any closed subset of $X$. We claim that that $\Psi(A)\setminus
f(E)$ is open. If $p\in(\Psi(\mathcal{A})\setminus f(E))\cap\omega$, then
$\\{p\\}$ is a neighborhood of $p$ that is contained in
$\Psi(\mathcal{A})\setminus f(E)$. Now assume that $p=A\in\mathcal{A}$. Then
$A$ in $X$ does not belong to $E$. Hence there exists $n$ such that
$U_{n}(A)\cap E=\emptyset$. But $f^{-1}(f(U_{n}(A))=U_{n}(A)$, hence
$f(U_{n}(A))\cap f(E)=\emptyset$. But $f(U_{n}(A))$ is a neighborhood of $A$
in $\Psi(\mathcal{A})$, hence we are done. ∎

######  Lemma 3.3.

If $Z$ is a zero-set $X$, then $f(Z)$ is a zero-set in $\Psi(\mathcal{A})$.

###### Proof.

Let $\xi\colon X\to[0,1]$ be continuous such that $\xi^{-1}(0)=Z$. Define
$\eta\colon\Psi(\mathcal{A})\to[0,1]$ as follows:
$\eta(p)=\min\xi(f^{-1}(p))$. It is clear that $\eta$ is well-defined since
$f$ is perfect (Lemma 3.2). To prove it is continuous, we only need to check
that at some $A\in\mathcal{A}$. By first-countability, we can check that by
considering convergent sequences. A typical sequence that converges to $A$ in
$\Psi(\mathcal{A})$ has the form $C=\\{m\in A:m\geq n\\}$ for some $n$. By the
definition of the topology on $X$, $\\{f^{-1}(c):c\in C\\}$ converges to $A$
in $X$. Hence $\\{\xi(f^{-1}(c)):c\in C\\}$ converges to $\eta(A)=\xi(A)$ in
$[0,1]$. But then so do the minima of these compact sets.

We will shows that $\eta^{-1}(0)=f(Z)$, which does the job. Indeed, pick an
arbitrary $p\in\eta^{-1}(0)$. Assume first that $p=A\in\mathcal{A}$. Then
since $\eta(A)=\xi(A)$, $A\in Z$, hence $A=f(A)\in f(Z)$. Assume next that
$p=n\in\omega$. Then $f^{-1}(p)=\\{n\\}\times K$, hence there exists $k\in K$
such that $\xi(\langle n,k\rangle)=0$. Hence $\langle n,k\rangle\in Z$, so
that $n=f(\langle n,k\rangle)\in f(Z)$. From this we conclude that
$\eta^{-1}(0)\subseteq f(Z)$. For the reverse inclusion, take an arbitrary
$z\in Z$, and consider $f(z)$. Again, there are two cases. Assume first that
$f(z)=A\in\mathcal{A}$. Then $z=A$, hence $\eta(f(z))=\xi(A)=0$. Assume next
that $f(z)=n\in\omega$. Then $z\in\\{n\\}\times K$, hence
$\min(\xi(\\{n\\}\times K))=0$. That is, $\eta(f(z))=\eta(n)=0$. ∎

######  Corollary 3.4.

$X$ is almost compact.

###### Proof.

By Gillman and Jerison [5, 6J] we must show that of any two disjoint zero-sets
in $X$, at least one of them is compact. Hence, assume that $Z_{0}$ and
$Z_{1}$ are disjoint zero-sets in $X$ such that neither $Z_{0}$ nor $Z_{1}$ is
compact.

Assume that $Z_{0}\cap\mathcal{A}$ is finite. There is a clopen compact $C$ in
$X$ that contains $Z_{0}\cap\mathcal{A}$. Hence $S_{0}=Z_{0}\setminus C$ is a
noncompact zero-set in $X$ that misses $\mathcal{A}$. But then $f(S_{0})$ is
by Lemma 3.2 an infinite closed subset of $\Psi(\mathcal{A})$ that misses
$\mathcal{A}$. But every infinite closed subset of $\Psi(\mathcal{A})$
intersects $\mathcal{A}$ since $\mathcal{A}$ is MAD.

We may consequently assume without loss of generality that
$Z_{0}\cap\mathcal{A}$ and $Z_{1}\cap\mathcal{A}$ are both infinite. But they
are clearly zero-sets of $X$. But then by Lemma 3.3, $\mathcal{A}$ contains
two disjoint infinite zero-sets of $\Psi(\mathcal{A})$, which contradicts
$\Psi(\mathcal{A})$ being almost compact. ∎

Write $\beta\Psi(\mathcal{A})=\Psi(\mathcal{A})\cup\\{\infty\\}$.

We are now in a position to present the proof of Theorem 3.1. To this end, let
$g\colon X\to Y$ be continuous, where $\omega<w(Y)<\mathfrak{c}$ and $Y$ is
homogeneous. We will show that this leads to a contradiction.

The space $Y$ is almost compact (hence locally compact) by Gillman and Jerison
[5, 6J].

Write $\beta X=X\cup\\{\infty_{X}\\}$, $\beta Y=Y\cup\\{\infty_{Y}\\}$, and
let $h=\beta g\colon\beta X\to\beta Y$ be the Stone extension of $g$.

######  Lemma 3.5.

$Y$ is compact.

###### Proof.

Assume that $Y$ is not compact. Then $h(\infty_{X})=\infty_{Y}$, and since
$h(X)=Y$, we get $h^{-1}(\\{\infty_{Y}\\})=\\{\infty_{X}\\}$. Since $Y$ is
locally compact, $w(\beta Y)<\mathfrak{c}$ from which it follows that the
character of $\infty_{X}$ in $X$ is less than $\mathfrak{c}$. But then the
character of $\infty$ in $\beta\Psi(\mathcal{A})$ is less than $\mathfrak{c}$,
which is a contradiction. ∎

Put $y_{0}=h(\infty_{X})$. Take an arbitrary $y_{1}\in X\setminus\\{y_{0}\\}$.
Let $U$ be a compact neighborhood of $y_{1}$ in $Y$ that misses $y_{0}$. Then
$h^{-1}(U)$ is a compact subset of $X$ and hence is of countable weight. But
then $U$ is of countable weight. By homogeneity, every point of $Y$ has a
compact neighborhood of countable weight. But then by compactness, $Y$ has
countable weight, which is a contradiction.

##  4\. On locally $\mathfrak{c}$ and $\mathfrak{c}$-fair spaces

In the previous section, we constructed an almost-compact first-countable and
homogeneous space of weight and cardinality $\mathfrak{c}$. By Arhangel’skii’s
celebrated result from [2], every first-countable Lindelöf space has
cardinality at most $\mathfrak{c}$. In the light of this it is natural to
wonder whether there is a bound on the cardinality of first-countable almost-
compact spaces. Our following general results answer this, but we think they
are of independent interest in themselves.

For the spaces in this section, unless otherwise stated, no separation axiom
is assumed.

######  Definition 4.1.

A topological space $X$ is

  1. (i)

locally $\mathfrak{c}$ if every point in $X$ has a neighborhood of cardinality
$\leq\,\mathfrak{c}$;

  2. (ii)

$\mathfrak{c}$-fair if the closure of every subset of $X$ of cardinality
$\mathfrak{c}$ also has cardinality $\mathfrak{c}$.

  3. (iii)

We call a $\kappa$-sequence $\\{F_{\alpha}:\alpha<\kappa\\}$ of subsets of $X$
strongly increasing if $F_{\alpha}\subset\mathop{\operator@font int}\nolimits
F_{\alpha+1}$ for all $\alpha<\kappa$.

We now present the main result of this section.

######  Theorem 4.2.

(i) Assume that the space $X$ is both locally $\mathfrak{c}$ and
$\mathfrak{c}$-fair, moreover $\kappa\leq\mathfrak{c}$ is a regular cardinal
such that for every strongly increasing $\kappa$-sequence
$\\{F_{\alpha}:\alpha<\kappa\\}$ of closed subsets of $X$ their union
$\bigcup\\{F_{\alpha}:\alpha<\kappa\\}$ is closed in $X$. Then
$|X|>\mathfrak{c}$ implies that for every subset $A$ of $X$ with
$|A|\leq\mathfrak{c}$ there exists a clopen subset $U$ of $X$ with $A\subset
U$ and $|U|=\mathfrak{c}$ such that $L(U)\geq\kappa$.

(ii) If $X$ is both locally $\mathfrak{c}$ and $\mathfrak{c}$-fair, moreover
we have $t(x,X)<cf(\mathfrak{c})$ for all points $x\in X$, then
$|X|>\mathfrak{c}$ implies the existence of a clopen subset $U$ of $X$ with
$|U|=L(U)=\mathfrak{c}$.

###### Proof.

(i) It is straightforward from $|X|>\mathfrak{c}$ and $X$ being locally
$\mathfrak{c}$ and $\mathfrak{c}$-fair, that we may define by transfinite
recursion a strongly increasing $\kappa$-sequence
$\\{F_{\alpha}:\alpha<\kappa\\}$ of closed subsets of $X$ such that
$F_{0}=\overline{A}$ and $\\{\mathop{\operator@font int}\nolimits
F_{\alpha}:\alpha<\kappa\\}$ is strictly increasing, moreover
$|F_{\alpha}|=\mathfrak{c}$ for all $\alpha<\kappa$. It is clear that then

$U=\bigcup\\{F_{\alpha}:\alpha<\kappa\\}=\bigcup\\{\mathop{\operator@font
int}\nolimits F_{\alpha}:\alpha<\kappa\\}.$

Hence, by our assumption, $U$ is clopen with $A\subset U$ and
$|U|=\mathfrak{c}$, moreover the strictly increasing open cover
$\\{\mathop{\operator@font int}\nolimits F_{\alpha}:\alpha<\kappa\\}$ of $U$
witnesses $L(U)\geq\kappa$ because $\kappa$ is regular.

(ii) If $\mathfrak{c}$ is regular then we may just use part (i) for
$\kappa=\mathfrak{c}$ to get the clopen $U$ with $|U|=L(U)=\mathfrak{c}$
because by our assumption the union of every increasing
$\mathfrak{c}$-sequence of closed subsets of $X$ is closed.

If, however, $\mathfrak{c}$ is singular then we first fix a sequence
$\\{\kappa_{\xi}:\xi<cf(\mathfrak{c})\\}$ of regular cardinals
$\kappa_{\xi}\geq cf(\mathfrak{\mathfrak{c}})$ that converges to
$\mathfrak{c}$. Then we may repeatedly apply part (i) to obtain an increasing
sequence $\\{U_{\xi}:\xi<cf(\mathfrak{c})\\}$ of clopen sets in $X$ such that
$|U_{\xi}|=\mathfrak{c}$ and $L(U_{\xi})\geq\kappa_{\xi}$ for all
$\xi<cf(\mathfrak{c})\\}$. In fact, what we do to get $U_{\xi}$ given
$\\{U_{\eta}:\eta<\xi\\}$, is using part (i) with the choice
$A=\bigcup\\{U_{\eta}:\eta<\xi\\}$.

Then, using again that $t(x,X)<cf(\mathfrak{c})$ for all $x\in X$, the set
$U=\bigcup\\{U_{\xi}:\xi<cf(\mathfrak{c})\\}$ is clopen with
$|U|=\mathfrak{c}$, moreover we have $L(U)\geq L(U_{\xi})\geq\kappa_{\xi}$ for
all $\xi<cf(\mathfrak{c})\\}$, hence $L(U)=\mathfrak{c}$. ∎

We note that by $|X\setminus U|=|X|>\mathfrak{c}$ and $X$ being locally
$\mathfrak{c}$, we trivially have $L(X\setminus U)=|X|>\mathfrak{c}$.

######  Corollary 4.3.

Assume that $X$ is a locally Lindelöf regular space with $\psi(X)=t(X)=\omega$
and $|X|>\mathfrak{c}$. Then there is a clopen subset $U$ of $X$ with
$|U|=L(U)=\mathfrak{c}$.

###### Proof.

It follows from Shapirovskii’s strengthening of Arhangel’skii’s theorem in
[13], see also 2.27 of [8], that $X$ is locally $\mathfrak{c}$.

Since we have $t(X)=\omega$, the $\mathfrak{c}$-fair property of $X$ follows
if we can show that $|\overline{S}|\leq\mathfrak{c}$ whenever $S$ is any
countable subset of $X$. But for such a set $S$ we have $L(\overline{S})\leq
w(X)\leq\mathfrak{c}$ by the regularity of $X$, and then
$|\overline{S}|\leq\mathfrak{c}$ follows since we already know that $X$ is
locally $\mathfrak{c}$.

Finally, the assumption $t(X)=\omega<cf(\mathfrak{c})$ implies that we may
apply part (ii) of Theorem 4.2 to conclude that there is a clopen subset $U$
of $X$ with $|U|=L(U)=\mathfrak{c}$. ∎

Now, if $X$ is almost compact and first countable then it is locally compact,
$\psi(X)=t(X)=\omega$, and for every clopen $U\subset X$ either $U$ or
$X\setminus U$ is compact, hence it is immediate from Corollary 4.3 that
$|X|\leq\mathfrak{c}$. This shows that Arhangel’skii’s theorem may be extended
to almost compact spaces, giving the answer to our motivating question.

If, in addition to the assumptions of Corollary 4.3, $X$ is also connected
then $|X|>\mathfrak{c}$ would lead to a contradiction, hence we get that any
locally Lindelöf and connected regular space $X$ with $\psi(X)=t(X)=\omega$
has cardinality $\leq\mathfrak{c}$.

We note that the assumption of regularity of $X$ in the last statement, and
hence in Corollary 4.3 as well, cannot be weakened to the Hausdorff property.
Indeed, by Corollary 2.6 of [10] there is a locally countable anti-Urysohn
space $X$ with $|X|=2^{\mathfrak{c}}$, and any anti-Urysohn space is connected
in a strong sense. (We recall that a Hausdorff space is anti-Urysohn if any
two non-empty regular closed sets in it intersect.) But any locally countable
space clearly satisfies all the other assumptions of Corollary 4.3.

In contrast to this, the following corollary of Theorem 4.2 for connected
spaces requires only the Hausdorff property.

######  Corollary 4.4.

If $X$ is any connected, locally $\mathfrak{c}$ and sequential Hausdorff
space, then $|X|\leq\mathfrak{c}$.

###### Proof.

Assume, on the contrary, that $|X|>\mathfrak{c}$. It is well-known that
sequential spaces have countable tightness, moreover the closure of any
countable set in a sequential Hausdorff space has cardinality
$\leq\mathfrak{c}$, and these clearly imply that $X$ is $\mathfrak{c}$-fair.
Moreover, $t(X)=\omega$ also implies that the union of every increasing
$\omega_{1}$-sequence of closed sets in $X$ is closed. Thus we may apply
Theorem 4.2 to obtain a clopen subset $U$ of $X$ with $|U|=\mathfrak{c}$. But
as $X$ is connected, then we would have $X=U$, contradicting
$|X|>\mathfrak{c}$. ∎

## References

  * [1] R. D. Anderson, The algebraic simplicity of certain groups of homeomorphisms, Amer. J. Math. 80 (1958), 955–963.
  * [2] A. V. Arhangel’skii, On the cardinality of bicompacta satisfying the first axiom of countability, Sov. Math. Dokl. 10 (1969), 951–955.
  * [3] A. V. Arhangel’skii and J. van Mill, Topological homogeneity, Recent progress in general topology. III, Atlantis Press, Paris, 2014, pp. 1–68.
  * [4] R. Engelking, General topology, Heldermann Verlag, Berlin, second ed., 1989\.
  * [5] L. Gillman and M. Jerison, Rings of continuous functions, Van Nostrand, Princeton, 1960.
  * [6] C. Hernández and M. Tkachenko, Reflecting some properties of topological groups, Topology Appl. 221 (2017), 501–516.
  * [7] F. Hernández-Hernández and M. Hrušák, Topology of Mrówka-Isbell spaces, Pseudocompact topological spaces, Dev. Math., vol. 55, Springer, Cham, 2018, pp. 253–289.
  * [8] I. Juhász, Cardinal functions in topology – ten years later, Math. Centre Tracts 123, Amsterdam, 1980
  * [9] I. Juhász, Cardinal functions on continuous images, Proceedings of the Tennessee Topology Conference, World Scientific, 1996, pp. 89–94.
  * [10] I. Juhász, L. Soukup, and Z. Szentmiklóssy, Anti-Urysohn spaces, Topology and its Applications, 213 (2016), 8–-23.
  * [11] S. Koppelberg, Homogeneous Boolean algebras may have nonsimple automorphism groups, Topology Appl. 21 (1985), no. 2, 103–120.
  * [12] S. Mrówka, Some set-theoretic constructions in topology, Fund. Math. 94 (1977), 83–92.
  * [13] B. Shapirovskii, Canonical sets and character. Density and weight in compact spaces, Soviet Math. Dokl. 15 (1974), 1282-1287.
  * [14] M. G. Tkačenko, Continuous mappings onto spaces of smaller weight, Vestnik Moskov. Univ. Ser. I Mat. Mekh. (1980), no. 2, 37–40, 102–103.


# Hardware Implementation of Fano Decoder for Polarization-adjusted
Convolutional (PAC) Codes

Amir Mozammel The author is with the Department of Electrical-Electronics
Engineering, Bilkent University, Ankara TR-06800, Turkey (e-mail:
a.mozammel@ee.bilkent.edu.tr).

###### Abstract

This brief proposes a hardware implementation architecture for Fano decoding
of polarization-adjusted convolutional (PAC) codes. This architecture uses a
novel branch metric unit specific to PAC codes. The proposed decoder is tested
on FPGA, and its performance is evaluated on ASIC using TSMC 28 nm 0.72 V
library. The decoder can be clocked at 500 MHz and reach an average
information throughput of 38 Mb/s at 3.5 dB signal-to-noise ratio for a block
length of 128 and a code rate of 1/2.

###### Index Terms:

PAC codes, sequential decoding, Fano, polar coding, VLSI.

##  I Introduction

This brief presents a hardware implementation study of Fano decoding for
polarization-adjusted convolutional (PAC) codes, which are a new class of
error-correcting codes introduced in [1]. PAC codes combine ideas from polar
coding [2] and convolutional coding and have been shown to perform near the
dispersion approximation [3] in certain cases [1]. Fano decoding [4] is a
depth-first tree search algorithm which was originally developed for
convolutional codes. PAC codes can be decoded using any tree search algorithm
such as depth-first, breadth-first, and beam (constrained breadth-first)
search algorithms.

Depth-first search decoders for convolutional codes are in general known as
sequential decoding [5] algorithms. Two well-known sequential decoders are
Fano and stack algorithms [6, 7]. Compared to stack algorithm, Fano decoder
requires a smaller memory size and is more suitable for hardware
implementations. For this reason, in this brief, we focus on the Fano version
of sequential decoding. Various architectures for hardware implementation of
sequential decoding of convolutional codes have been reported in the
literature [8, 9, 10, 11], but to the best of the author’s knowledge, the
suitability of sequential decoding for PAC codes has never been studied from a
hardware implementation perspective. Motivated by this, we implement a Fano
decoder for PAC codes by introducing a new hardware-friendly variant of Fano
algorithm for PAC codes and designing a novel branch metric unit capable of
calculating the current and previous branch metrics without requiring any
storage element or comparator.

Despite its near-optimal performance, PAC codes under sequential decoding
exhibit variable time complexity, resulting in variable decoding latency.
Although the depth-first search algorithms have variable search complexity,
their average search complexity is low at a high signal-to-noise ratio (SNR)
regime. On the other hand, breadth-first search algorithms have fixed but
higher search complexity. List decoding [12] of PAC codes is an example of
beam search decoder. However, the list decoder requires a large list size to
achieve the error-correction performance of the PAC sequential decoder.

Throughout this brief, we denote vectors by boldface letters. For any set
$\mathcal{A}\subseteq\\{0,1,...,N-1\\}$, we denote its complement by
$\mathcal{A}^{c}=\\{i:i\notin A\\}$. For any vector $\mathbf{y}$ and set
$\mathcal{A}$, $\mathbf{y}_{\mathcal{A}}$ denotes the sub-vector
$(y_{i}:i\in\mathcal{A})$. For any vector $\mathbf{y}$,
$\mathbf{y}^{j}=(y_{0},y_{2},...,y_{j})$. We define a sign function $s(l)$
such that $s(l)=0$ if $l\geq 0$ and $s(l)=1$, otherwise.

The rest of this brief is organized as follows. Section II gives a brief
discussion of PAC codes. Section III introduces a new variant of Fano decoder
for PAC codes. In Section IV we introduce a hardware architecture for Fano
decoding of PAC codes. Implementation results of the proposed PAC Fano decoder
are presented in Section V. Section VI concludes this brief.

Figure 1: PAC coding scheme.

##  II PAC Codes

Fig. 1 shows a block diagram of PAC coding scheme. The data insertion block
receives a source word $\mathbf{d}$ of length $K$ and inserts it into a data
carrier word $\mathbf{v}$ of length $N$ in accordance with a data index set
$\mathcal{A}$ such that $\mathbf{v}_{\mathcal{A}}=\mathbf{d}$ and
$\mathbf{v}_{\mathcal{A}^{c}}=\mathbf{0}$. The bits fixed to zero are called
frozen, whereas all the other bits are called non-frozen. The data carrier
word $\mathbf{v}$ goes through a convolution block with generator matrix
$\mathbf{G}$ which is a Toeplitz matrix whose first row is $\mathbf{c}$ (the
generator polynomial). The resulting word $\mathbf{u}$ goes through a polar
mapper and the overall encoding process of PAC codes can be expressed by
$\mathbf{x}=\mathbf{v}\mathbf{G}\mathbf{F}^{\otimes n}$, where
$\mathbf{F}^{\otimes n}$ is the generator matrix of polar codes with
$\mathbf{F}^{\otimes n}$ being the $n$-th Kronecker product of the kernel
matrix $\mathbf{F}=\begin{bmatrix}1&0\\\ 1&1\end{bmatrix}$.

At the receiver side, the PAC decoder receives the channel output $\mathbf{y}$
and generates an estimate $\hat{\mathbf{v}}$ of $\mathbf{v}$. Then, a data
extractor extracts an estimate $\hat{\mathbf{d}}$ of $\mathbf{d}$ from
$\hat{\mathbf{v}}$ using $\hat{\mathbf{d}}=\hat{\mathbf{v}}_{\mathcal{A}}$.
The performance of the system is measured by the probability of frame error
$P_{e}=P(\hat{\mathbf{d}}\neq\mathbf{d})$. A PAC sequential decoder consists
of two blocks: polar demapper and sequential decoder. The polar demapper
receives the channel output $\mathbf{y}$ and calculates a log-likelihood ratio
(LLR) vector $\boldsymbol{l}$. Then, based on the prior bit-estimates
$\hat{\mathbf{u}}^{i-1}$ received from sequential decoder, it generates the
demapped LLR value
$z_{i}\triangleq\ln{\frac{P(\mathbf{y},\hat{\mathbf{u}}^{i-1}|\hat{u}_{i}=0)}{P(\mathbf{y},\hat{\mathbf{u}}^{i-1}|\hat{u}_{i}=1)}}$
of $i$th bit. Polar demapper operates similar to successive cancellation (SC)
decoder of polar codes with a difference that the polar demapper does not
generate any bit-estimate output $\hat{u}_{i}$. Instead, it receives the prior
bit-estimates $\hat{\mathbf{u}}^{i-1}$ from the sequential decoder and passes
back the soft value of $z_{i}$. The sequential decoder uses $z_{i}$ to
calculate a path metric which helps the decoder to generate an estimate
$\hat{\mathbf{v}}$ of $\mathbf{v}$.

##  III Fano Algorithm for PAC Codes

Fano algorithm uses a path metric and a metric threshold $T$ to identify the
correct path in the code tree. The threshold can only take integer multiples
of threshold spacing $\Delta$. If the path metric grows along a given path,
the algorithm considers it as a correct path and continues to search further
along it. But if the metric drops significantly, the algorithm moves back
(backtracks) and searches other paths. Upon a backward move, if the currently
reached node is frozen or all of its children are examined, the decoder moves
back one more. An extensive study of the Fano decoder may be found in [13].

Figure 2: Fano decoding tree, reproduced from [8].

Fig. 2 shows a local node diagram of the Fano decoding tree. Assume that N1 is
the current node, N2 is the most likely node (with larger metric), N3 is the
least likely node (with smaller metric), and N4 is the previous node. M2 and
M3 denote the metrics of branches from current node to N2 and N3,
respectively, and M1 is the metric of the branch from previous node to the
current node. To avoid branch metric overflow, we use relative branch metric
computation instead of absolute branch metric value [8]. Adopting this method
lets the current node’s branch metric be zero and all other branch metrics
relative to the current node’s metric.

We modify the conventional Fano algorithm to make it suitable for decoding PAC
codes and state it as the following set of rules. We define a variable $\Psi$
such that $\Psi=1$ when the Fano decoder backtracks to a frozen node or to a
node whose both children are examined; otherwise, $\Psi=0$. N23 is a node that
corresponds to N2 when the most likely node is being examined or N3 when the
least likely node is being examined. Similarly, M23 corresponds to M2 when N2
is being examined or M3 when N3 is being examined. A node is considered as a
new node if it is being visited for the first time.

$\bullet$ Rule 0
Conditions: $\Psi=0$, N23 is new node, $\text{M23}\geq T$.
Actions: Move to N23, update $T$ to $T+\Delta-\text{M23}$, examine the most
likely node leading from N23 at the next step.
$\bullet$ Rule 1
Conditions: $\Psi=0$, N23 is old node, $\text{M23}\geq T$.
Actions: Move to N23, update $T$ to $T-\text{M23}$, examine the most likely
node leading from N23 at the next step.
$\bullet$ Rule 2
Conditions: $\Psi=0$, $\text{M23}<T$, N1 is root node; or $\Psi=0$,
$\text{M23}<T$, N1 is not root node, $\text{M1}+T>0$; or $\Psi=1$, N1 is root
node; or $\Psi=1$, N1 is not root node, $\text{M1}+T>0$
Actions: Make no move, update $T$ to $T-\Delta$, assign $\Psi=0$, examine N2
again at the next step
$\bullet$ Rule 3
Conditions: $\Psi=0$, $\text{M23}<T$, N1 is not root node, $\text{M1}+T\leq
0$, N4 is not frozen, N1 is the most likely node leading from N4; or $\Psi=1$,
N1 is not root node, N4 is not frozen, N1 is the most likely node leading from
N4.
Actions: Move to N4, update $T$ to $T+\text{M1}$, assign $\Psi=0$, examine the
lateral node of N1 at the next step.
$\bullet$ Rule 4
Conditions: $\Psi=0$, $\text{M23}<T$, N1 is not root node, $\text{M1}+T\leq
0$, N4 is frozen or N1 is the least likely node leading from N4; or $\Psi=1$,
N1 is not root node, N4 is frozen or N1 is the most likely node leading from
N4.
Actions: Move to N4, update $T$ to $T+\text{M1}$, assign $\Psi=1$, perform
backward check at the next step.

Fig. 3 shows the corresponding flowchart of the Fano decoder. Note that
whenever $\Psi=1$, the Fano algorithm performs a backward check and does not
require any new $z_{i}$ value. Thus, by storing the previously generated
$z_{i}$ values, we can avoid activating the polar demapper when $\Psi=1$ and
significantly reduce the decoder’s latency (especially at low SNR regime).

Figure 3: Flowchart of Fano rules.

##  IV Architecture of Fano Decoder for PAC Codes

Fig. 4 shows the hardware architecture of the proposed PAC Fano decoder. The
input buffer stores the channel output LLR values, and the output buffer
stores the final estimate $\hat{\mathbf{v}}$ of $\mathbf{v}$. The Fano control
unit (FCU) implements the flowchart of Fig. 3. The branch metric unit (BMU) is
responsible for providing the FCU with the current branch metric M23 and
previous branch metric M1. Vreg is a bidirectional shift register used to
store the prior convolution input estimates $\hat{\mathbf{v}}$. Whenever the
Fano decoder moves forward, the current convolution input estimate
$\hat{v}_{i}$ is stored in Vreg. To allow a maximum backtracking depth of $N$,
the size of Vreg is chosen to be $N+h$, where $h$ is the memory size of the
convolution. The first $h$ part of Vreg provides the convolution state (CS)
for the BMU. The Ureg register is used to store the prior convolution output
estimates $\hat{\mathbf{u}}$. When the Fano decoder moves forward, depending
on the proceeding branch, the corresponding $\hat{u}_{i}$ is stored in the
Ureg. A clock cycle (CC) counter is used to count the number of clock cycles
consumed for decoding a single codeword. The decoding of a codeword is
terminated whenever the value of the CC counter exceeds a predefined maximum
cycle (MC). In this case, a timeout (TO) signal is generated, and a new LLR
vector $\boldsymbol{l}$ is loaded to the input buffer. The input
$\boldsymbol{a}$ determines the frozen and non-frozen nodes such that
$a_{i}=0$ for frozen nodes ($i\in\mathcal{A}^{c}$) and $a_{i}=1$ for non-
frozen nodes ($i\in\mathcal{A}$).

Figure 4: PAC Fano decoder.

To implement the polar demapper (PD), we adopt the FFT-like architecture of
[14] and apply the following modifications to make it operate as a polar
demapper:  1. We remove the decision unit and pass the soft values of LLR
vector $\mathbf{z}$ to the output;  2. We remove the bit-estimates update unit
and corresponding registers and implement the bit-estimates update network
using a combinational circuit that receives $\hat{\mathbf{u}}$ from Ureg and
updates the intermediate bit-estimate values;  3. We modify the bit-reversal
architecture of [14] to output the LLR values in a natural order.  Despite the
similarity in architecture, the timing schedule of PD is different from the
one of SC decoder. Once the PD generates the LLR value of a node $z_{i}$, it
remains idle until another node LLR value is requested. Note that the next LLR
value request may be for the immediate forward node or any other backward
node. Hence, the PD must be able to follow the Fano algorithm whenever it
backtracks. To fulfill this requirement, all the intermediate LLR values are
required to be stored and kept until the end of each decoding session. The
FFT-like architecture of [14] uses distributed registers to stores the
intermediate LLR values. Any SC decoder that is capable of storing the
intermediate LLR values can be used as a polar demapper.

The BMU block is a fundamental block which makes the Fano decoding of PAC
codes different from Fano decoding of convolutional codes. The metric function
that BMU of PAC Fano decoder uses must be compatible with the polarized
channel (created by the polar mapper and demapper) seen by the convolution
block of PAC codes. For PAC codes, the well-known branch metric function of
Fano [4, 15] becomes

$\gamma_{i}(\hat{u}_{i})=\log_{2}\frac{P(\mathbf{y},\hat{\mathbf{u}}^{i-1}|\hat{u}_{i})}{P(\mathbf{y},\hat{\mathbf{u}}^{i-1})}-b_{i},$
(1)

where $P(\mathbf{y},\hat{\mathbf{u}}^{i-1}|\hat{u}_{i})$ and
$P(\mathbf{y},\hat{\mathbf{u}}^{i-1})$ are transition and output probabilities
of the $i$th bit-channel, respectively, and $b_{i}$ is a bias term. For a
binary input channel with uniform input distribution, we have

$P(\mathbf{y},\hat{\mathbf{u}}^{i-1})=\frac{1}{2}\left[P(\mathbf{y},\hat{\mathbf{u}}^{i-1}|\hat{u}_{i}=0)+P(\mathbf{y},\hat{\mathbf{u}}^{i-1}|\hat{u}_{i}=1)\right].$
(2)

By using (2) and dividing the numerator and denominator of the fractional part
of (1) by $P(\mathbf{y},\hat{\mathbf{u}}^{i-1}|\hat{u}_{i})$, after some
calculus, we obtain

$\gamma_{i}(\hat{u}_{i})=1-\log_{2}(1+e^{-(1-2\hat{u}_{i})z_{i}})-b_{i},$ (3)

where $z_{i}$ is the output of PD. To obtain a hardware-friendly version of
(3), we apply the approximation $\log_{2}(1+e^{-(1-2\hat{u}_{i})z_{i}})\approx
0$, if $\hat{u}_{i}=s(z_{i})$, and
$\log_{2}(1+e^{-(1-2\hat{u}_{i})z_{i}})\approx|z_{i}|$, otherwise, and obtain

$\displaystyle\gamma_{i}(\hat{u}_{i})=\begin{cases}1-b_{i},&\text{if}~{}\hat{u}_{i}=s(z_{i}),\\\
1-|z_{i}|-b_{i},&\text{otherwise}.\end{cases}$ (4)

To simplify (4) further, we assume $b_{i}$ can take only binary values. As a
result, we can tabulate $\gamma_{i}(0)$ and $\gamma_{i}(1)$ for all the
possible values of $b_{i}$ and $s(z_{i})$ in Table I.

Figure 5: Hardware implementation of Table I (metric calculator). TABLE I: $\gamma_{i}(\hat{u}_{i})$ for Different Values of $s(z_{i})$ and $b_{i}$. $s(z_{i})$ | $b_{i}$ | $\gamma_{i}(0)$ | $\gamma_{i}(1)$
---|---|---|---
0 | 0 | 1 | $1-|z_{i}|$
0 | 1 | 0 | $-|z_{i}|$
1 | 0 | $1-|z_{i}|$ | 1
1 | 1 | $-|z_{i}|$ | 0

We can implement this table using two 4-to-1 multiplexers and one adder. Fig.
5 shows the hardware implementation of Table I (metric calculator). The number
of quantization bits for LLRs is denoted by $Q$. The metric calculator
receives $z_{i}$ and $b_{i}$ and generates the branch metric
$\gamma_{i}(\hat{u}_{i})$ for the two possible values of $\hat{u}_{i}=0$ and
$\hat{u}_{i}=1$. The constant ’0’ and ’1’ inputs to the adder and multiplexers
are padded with zeros to have $Q$-bit width (not shown in the figure for
clarity).

Fig. 6 shows the hardware diagram of BMU, which uses two metric calculator
blocks to generate the current and previous branch metrics. With a careful
observation of Table I we realize that $\gamma_{i}(0)\geq\gamma_{i}(1)$ when
$s(z_{i})=0$ and $\gamma_{i}(0)\leq\gamma_{i}(1)$ when $s(z_{i})=1$. Hence,
the most likely branch can be distinguished from the least likely branch
without using an actual comparator. The input $t_{i}$ is provided by FCU and
is used to request the most likely branch metric (M2) when $t_{i}=0$ or the
least likely branch metric (M3) when $t_{i}=1$ from BMU. Additionally, when
the current node N1 is frozen (i.e. $a_{i}=0$) the BMU is forced to output the
branch metric which corresponds to $\hat{v}_{i}=0$. We use a convolutional
encoder to generate $u_{i,0}$ which is the convolution output for the
assumption $\hat{v}_{i}=0$. In addition to M1 and M23 metrics, the BMU block
provides FCU with the selected branch $\hat{v}_{i}$ and its corresponding
convolution output $\hat{u}_{i}$.

Figure 6: Hardware diagram of branch metric unit (BMU).

##  V Implementation Results

In this section, FPGA and ASIC implementation results of the proposed PAC Fano
decoder are presented for block length $N=128$ and message length $K=64$. We
use $Q=7$, $\Delta=2$, $\mathbf{c}=(1,0,1,1,0,1,1)$, and choose $\mathcal{A}$
according to the Reed-Muller scoring rule as explained in [1]. We use the hard
quantized (1-bit quantization) values of bit-channel capacities [16] as the
bias vector $\mathbf{b}$. The channel output LLR values are calculated at
$E_{b}/N_{0}=3.5$ dB.

###  V-A FPGA Implementation Results

The proposed PAC Fano decoder is successfully implemented onto Xilinx Nexys 4
Artix®-7 ($28$ nm) FPGA. The place-and-route results show that the decoder
uses $16443$ lookup tables (LUTs) and $8306$ registers. To evaluate the FER
performance and measure the search complexity of the PAC Fano decoder, using
MATLAB® software, pseudorandom messages are generated, encoded, modulated
using a binary phase-shift keying (BPSK) modulator, and transmitted to FPGA
after white Gaussian noise is added. The decoded carrier word
$\hat{\mathbf{v}}$ is received from FPGA, $\hat{\mathbf{d}}$ is extracted from
$\hat{\mathbf{v}}$ using $\hat{\mathbf{d}}=\hat{\mathbf{v}}_{\mathcal{A}}$,
and compared with the actual transmitted message $\mathbf{d}$. Also
transmitted by the FPGA is the number of clock cycles consumed to decode each
codeword which is measured by the CC counter.

Figure 7: Complexity and FER performance of PAC Fano decoder.

Fig. 7 (left) plots the FER performance of the proposed PAC Fano decoder for
different MC values. The FER performance of software simulation of original
PAC codes reported in [1] and the dispersion approximation are also plotted in
this figure. As expected, increasing the value of MC allows the Fano algorithm
to perform more searches and maintain better FER performance. With
$\text{MC}=2^{18}$, the proposed PAC Fano decoder obtains a FER performance
close to the FER performance of software implementation at high SNR regime; At
$E_{b}/N_{0}=3.5$ dB the decoder achieves $\text{FER}=1.6\times 10^{-5}$. The
performance loss is majorly due to the quantization of LLRs and approximation
of the Fano metric. In low SNR regime, the metric approximation error is large
since the term $\log_{2}(1+e^{-(1-2\hat{u}_{i})z_{i}})$ diverges from
$|z_{i}|$ as SNR decreases. But as SNR increases, this error becomes
negligible.

Fig. 7 (right) shows the average number of clock cycles consumed by the
decoder for decoding a single codeword for different MC values. The effect of
MC value on average CC is significant at low SNR regime; as SNR increases,
this effect fades out. This is due to the Pareto distribution of Fano
decoder’s search complexity such that for high SNR values, only a small
fraction of codewords require a very large search complexity [17]. With
$\text{MC}=2^{14}$, the average number of CCs per codeword drops by $51\%$ at
$E_{b}/N_{0}=1$ dB at a cost of FER performance drop at high SNR values
(significantly at $E_{b}/N_{0}=3.5$ dB). At $E_{b}/N_{0}=3.5$, regardless of
MC value, the decoder consumes an average of approximately $840$ CCs to decode
a single codeword. It is worth mentioning that for a noise-free channel (when
no backtracking is done), the proposed PAC Fano decoder consumes $638$ CCs
which corresponds to $5N-2$ CCs, of which $2N-2$, $2N$, and $N$ is consumed by
PD, FCU, and BMU, respectively.

###  V-B Post-Synthesis Results

Table II lists the post-synthesis results of the proposed PAC Fano decoder
using Cadence® InnovusTM Implementation System with TSMC 28 nm 0.72 V library.
We present the results for the PAC Fano decoder with $\text{MC}=2^{18}$. The
decoder occupies an area of 0.059 mm2 and can operate at 500 MHz consuming
3.85 mW power. The power value is estimated with Cadence® VoltusTM IC Power
Integrity Solution using $10^{4}$ pseudorandom input vectors. The performance
values are reported at $E_{b}/N_{0}=3.5$ dB, and the average values are
calculated from $10^{7}$ decoding trials. The average information throughput
(TP) of the decoder is estimated using
$\text{TP}=(f_{\text{clk}}/\text{ACC})\times K$, where $f_{\text{clk}}$ is the
operating frequency and ACC is the average number of CCs consumed for decoding
a frame and is obtained from Fig. 7. The worst-case (W.-C.) latency of the
decoder is determined by the value of MC. The proposed PAC Fano decoder
reaches an average information throughput of 38.1 Mb/s with an average latency
of 839 CCs (1.68 $\mu$s).

TABLE II: ASIC Implementation Results Technology | 28 nm
---|---
N | 128
K | 64
Supply Voltage (V) | 0.72
Frequency (MHz) | 500
Area (mm2) | 0.059
Power (mW) | 3.85
Avg. Info. TP† (Mb/s) | 38.1
W.-C. Info. TP∗ (Mb/s) | 0.12
Avg. Latency† ($\mu$s) | 1.68
Avg. Latency† (CCs) | 839
W.-C. Latency ($\mu$s) | 524
W.-C. Latency (CCs) | $2^{18}$
Area Efficiency† (Mb/s/mm2) | 646
Power Density (W/mm2) | 0.065
Energy Efficiency† (PJ/bit) | 101
†Average value at $E_{b}/N_{0}=3.5$ dB.

##  VI Conclusion

In this brief, we proposed a hardware architecture for Fano decoding of PAC
codes. We introduced a new variant of Fano algorithm suitable for decoding PAC
codes. We also introduced a novel branch metric unit specific to PAC codes
that can be implemented using simple logic gates. Post-synthesis results
showed that the decoder could provide an average information throughput of
approximately 38 Mb/s at 3.5 dB with a power consumption of 3.85 mW and an
area of 0.059 mm2 for a block length of 128 and a code rate of $1/2$. Due to
its backtracking feature, the PAC Fano decoder has lower throughput than the
state-of-the-art polar decoders (such as decoders of [18]), but it exhibits
better FER performance. Because of their excellent FER performance at short
block lengths and low encoding complexity, one of the potential use cases of
PAC codes could be the Internet of Things (IoT), for which reliable
communication is of great interest and low throughput and high decoding
latency is tolerable.

## References

  * [1] E. Arıkan, “From sequential decoding to channel polarization and back again,” _arXiv preprint arXiv:1908.09594_ , 2019.
  * [2] ——, “Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels,” _IEEE Transactions on information Theory_ , vol. 55, no. 7, pp. 3051–3073, 2009.
  * [3] Y. Polyanskiy, H. V. Poor, and S. Verdú, “Channel coding rate in the finite blocklength regime,” _IEEE Transactions on Information Theory_ , vol. 56, no. 5, pp. 2307–2359, 2010.
  * [4] R. Fano, “A heuristic discussion of probabilistic decoding,” _IEEE Transactions on Information Theory_ , vol. 9, no. 2, pp. 64–74, 1963.
  * [5] J. M. Wozencraft, “Sequential decoding for reliable communication,” Research Laboratory of Electronics, MIT, Cambridge, Tech. Rep., 1957.
  * [6] K. Zigangirov, “Some sequential decoding procedures,” _Problemy Peredachi Informatsii_ , vol. 2, no. 4, pp. 13–25, 1966.
  * [7] F. Jelinek, “Fast sequential decoding algorithm using a stack,” _IBM journal of research and development_ , vol. 13, no. 6, pp. 675–685, 1969.
  * [8] M. Benaissa and Y. Zhu, “Reconfigurable hardware architectures for sequential and hybrid decoding,” _IEEE Transactions on Circuits and Systems I: Regular Papers_ , vol. 54, no. 3, pp. 555–565, 2007.
  * [9] G. Forney and E. Bower, “A high-speed sequential decoder: Prototype design and test,” _IEEE Transactions on Communication Technology_ , vol. 19, no. 5, pp. 821–835, 1971.
  * [10] I. Jacobs, “Sequential decoding for efficient communication from deep space,” _IEEE Transactions on Communication Technology_ , vol. 15, no. 4, pp. 492–501, 1967.
  * [11] J. Layland and W. Lushbaugh, “A flexible high-speed sequential decoder for deep space channels,” _IEEE Transactions on Communication Technology_ , vol. 19, no. 5, pp. 813–820, 1971.
  * [12] H. Yao, A. Fazeli, and A. Vardy, “List decoding of Arıkan’s PAC codes,” _Preprints: 2021050235_ , 2021.
  * [13] R. G. Gallager, _Information theory and reliable communication_. New York: Wiley, 1968, vol. 2.
  * [14] C. Leroux, I. Tal, A. Vardy, and W. J. Gross, “Hardware architectures for successive cancellation decoding of polar codes,” in _2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2011, pp. 1665–1668.
  * [15] J. Massey, “Variable-length codes and the Fano metric,” _IEEE Transactions on Information Theory_ , vol. 18, no. 1, pp. 196–198, 1972.
  * [16] M. Moradi, “On the metric and computation of PAC codes,” _arXiv preprint arXiv:2012.05511_ , 2020.
  * [17] M. Moradi, A. Mozammel, K. Qin, and E. Arıkan, “Performance and complexity of sequential decoding of PAC codes,” _arXiv preprint arXiv:2012.04990_ , 2020.
  * [18] C. Kestel, L. Johannsen, O. Griebel, J. Jimenez, T. Vogt, T. Lehnigk-Emden, and N. Wehn, “A 506 Gbit/s polar successive cancellation list decoder with CRC,” in _2020 IEEE 31st Annual International Symposium on Personal, Indoor and Mobile Radio Communications_ , 2020, pp. 1–7.


# Subsystem Trace-Distances of Two Random States

Joaquim Telles de Miranda  Centro Brasileiro de Pesquisas Físicas, Rua Xavier
Sigaud 150, 22290-180, Rio de Janeiro, Brazil  Tobias Micklitz  Centro
Brasileiro de Pesquisas Físicas, Rua Xavier Sigaud 150, 22290-180, Rio de
Janeiro, Brazil

###### Abstract

We study two-state discrimination in chaotic quantum systems. Assuming that
one of two $N$-qubit pure states has been randomly selected, the probability
to correctly identify the selected state from an optimally chosen experiment
involving a subset of $N-N_{B}$ qubits is given by the trace-distance of the
states, with $N_{B}$ qubits partially traced out. In the thermodynamic limit
$N\to\infty$, the average subsystem trace-distance for random pure states
makes a sharp, first order transition from unity to zero at $f=1/2$, as the
fraction $f=N_{B}/N$ of unmeasured qubits is increased. We analytically
calculate the corresponding crossover for finite numbers $N$ of qubits, study
how it is affected by the presence of local conservation laws, and test our
predictions against exact diagonalization of models for many-body chaos.

##  I  Introduction

The capability for storing and processing quantum information relies on the
ability to discriminate between quantum states. Quantifying distinguishability
of quantum states, specifically when only access to subregions is available,
is thus a problem of fundamental and practical interest. In chaotic systems
initially localized information is ‘scrambled’ into the many degrees of
freedom of the system, and subsystem density matrices of generic pure states
are nearly indistinguishable from fully thermal states. The ‘nearly’ was
specified by Page for pure random states, which also serve as proxies for
eigenstates of chaotic systems, in his classic paper Page (1993). There he
showed that for these states the information stored in the smaller subsystem,
defined as the deficit of the subsystem entanglement entropy $S_{A}$ from the
maximum entropy of a fully mixed state, is on average $I_{A}\equiv\ln
D_{A}-S_{A}=D^{2}_{A}/2D$. Here $D_{A}$, and $D$ are the Hilbert space
dimensions of the smaller subsystem, respectively, the joint system, and
corrections small in $1/D$ have been neglected. For reasonably large systems
the entanglement entropy is self averaging and the average $S_{A}$ is also
typical Bianchi and Donà (2019); Bianchi et al. (2021). Conservation laws
generally reduce entanglement, increasing thus the capability to store
information Bianchi and Donà (2019); Rigol et al. (2008); Lau et al. (2022);
Ares et al. (2022); Vidmar and Rigol (2017); Nakagawa et al. (2018); Sugiura
and Shimizu (2012, 2013); Murciano et al. (2022). If multiple charges are
conserved, entanglement is (on average) promoted if the charges fail to
commute with each other. That is, Page curves for non-commuting charges lie
above that of commuting charges, as recently pointed out in Ref. Majidy et al.
(2022). Morevover, in the presence of locally conserved charges, the entire
charge distributions of initial states are conserved. The largest amount of
information can then be stored in states with the broadest charge distribution
Altland et al. (2022).

While Page’s formula provides information on subsystems, it does not give an
answer to state-discrimination in fully information scrambling systems.
Specifically, imagine one of two known random pure states $\rho$, $\sigma$,
both composed of $N$ qubits, has been randomly selected. What is the (average)
probability $P_{\rho\sigma}$ that performing an optimally chosen experiment on
$N_{A}$ of the qubits we correctly identify the selected state, and how is
$P_{\rho\sigma}$ affected by conservation laws? In this paper we want to
investigate these questions, and the outline is as follows: We start briefly
reviewing in Section II the concepts of the trace-distance $D_{1}$, its
generalization the Schatten $n$-distances $D_{n}$, Page states, and the
calculation of $D_{1}$ from $D_{n}$ via the replica trick. We then discuss in
Section III the combinatorics involved in the calculation of average subsystem
Schatten $n$-distances of random pure states. In Section IV we analyze the
average subsystem trace-distances of random pure states and consequences of
local conservation laws. We conclude in Section V with a summary and
discussion, and give further technical details in the Appendices.

##  II  Schatten-distances, Page states, and replica trick

Optimal quantum state discrimination is generally challenging, and the only
completely analyzed case is for two states, see e.g. Ref. Bae and Kwek (2015)
for a review. The trace-distance provides a natural metric for two-state
discrimination. According to the Holevo–Helstrom theorem the best success
probability for the latter is encoded in the $1$-Schatten- or trace-distance
as $P_{\rho\sigma}=\frac{1}{2}\left(1+D_{1}(\rho,\sigma)\right)$ foo (a).
General Schatten $n$-distances here are defined as
$D_{n}(\rho,\sigma)\equiv\frac{1}{2^{1/n}}||\rho-\sigma||_{n}$, with $n$-norm
of a matrix $\Lambda$ determined by its singular values $\lambda_{i}$ as
$||\Lambda||_{n}=\left(\sum_{i}\lambda^{n}_{i}\right)^{1/n}$ foo (b). Notice
that all Schatten distances are symmetric in the inputs, positive semi-
definite, equal to zero if and only if inputs are identical, and obey the
triangular inequality. That is, they all satisfy the properties of a metric,
with normalization here chosen such that $0\leq D_{n}\leq 1$. Our focus here
is on two-state discrimination and we thus concentrate on the $1$-distance.

Consider then a $D$-dimensional Hilbert space with entanglement-cut bi-
partitioning the total system into subsystems $A$, $B$ of dimensions $D_{A}$
and $D_{B}$, respectively, with $D_{A}D_{B}=D$. Without much loss of
generality, we focus here on $N$ qubit systems parametrized by $(a,b)$, where
the $N_{A}$-bit vector $a$ labels the $D_{A}=2^{N_{A}}$ states of subsystem
$A$ and $b$ the $D_{B}=2^{N_{B}}$ states of $B$, with $N_{B}=N-N_{A}$.
Following Page, we then consider two random pure states
$|\psi^{\alpha}\rangle=\sum_{a,b}\psi^{\alpha}_{ab}|a,b\rangle$,
$\alpha=\rho,\sigma$, with Gaussian distributed complex amplitudes
$\psi^{\alpha}_{ab}$, chosen to have zero mean and variances

$\displaystyle\langle\psi_{ab}^{\alpha}\bar{\psi}_{cd}^{\beta}\rangle$
$\displaystyle=\frac{1}{D}\delta_{ac}\delta_{bd}\delta_{\alpha\beta}.$ (1)

$|\psi^{\alpha}\rangle$ describe infinite temperature thermal states of
generic chaotic systems, and using Eq. (1) we employ that correlations induced
by the normalization constraint are negligible for reasonable large systems
$D\gg 1$. Tracing out subsystem $B$, information is lost and mixedness of the
reduced density matrices,

$\displaystyle\rho_{A}$ $\displaystyle={\rm
tr}_{B}(|\psi^{\rho}\rangle\langle\psi^{\rho}|),\quad\sigma_{A}={\rm
tr}_{B}(|\psi^{\sigma}\rangle\langle\psi^{\sigma}|),$ (2)

increases with the number of partially traced qubits $N_{B}$.

To find trace-distances of Eq. (2) we employ the replica trick recently
discussed in Ref. Zhang et al. (2019). We first calculate Schatten-distances
for general even integer $n$, analytically continue to real $n$, and finally
take the limit $n$ to unity,

$\displaystyle\langle D_{1}(\rho_{A},\sigma_{A})\rangle$
$\displaystyle=\frac{1}{2}\lim_{n\to 1}\langle{\rm
tr}\left(\rho_{A}-\sigma_{A}\right)^{n}\rangle.$ (3)

Restricting to even integers here is important, since corresponding expression
for odd integers vanish (see also below), and a replica limit for the latter
is thus trivially zero Zhang et al. (2019). Expanding powers in Eq. (3), we
are confronted with the averages

$\displaystyle\langle{\rm tr}_{A}(\rho_{A}-\sigma_{A})^{n}\rangle$
$\displaystyle\,\,={\rm
sgn}(\sigma)\langle\psi_{a^{1}b^{1}}^{\alpha_{1}}\bar{\psi}_{a^{2}b^{1}}^{\alpha_{1}}\psi_{a^{2}b^{2}}^{\alpha_{2}}\bar{\psi}_{a^{3}b^{2}}^{\alpha_{2}}\cdot\cdot\cdot\psi_{a^{n}b^{n}}^{\alpha_{n}}\bar{\psi}_{a^{1}b^{n}}^{\alpha_{n}}\rangle,$
(4)

where sums over repeated indices $\alpha_{i}=\rho,\sigma$, $a_{i}=1,..,D_{A}$,
$b_{i}=1,...,D_{B}$ are implicit, and the sign-factor is ${\rm
sgn}(\sigma)=\pm 1$ if an even/odd number of density matrices $\sigma_{A}$ is
involved in the product. Following previous works Monteiro et al. (2021) the
bookkeeping of index configurations entering the products is conveniently done
in a tensor network representation shown in Fig. 1. The solid lines here
indicate how the indices of matrices
$\left(\psi\bar{\psi}\right)^{\alpha\beta}_{ab;a^{\prime}b^{\prime}}=\psi^{\alpha}_{ab}\bar{\psi}^{\beta}_{a^{\prime}b^{\prime}}$
are constrained due to matrix multiplication in subspace $A$, subsystem-traces
over $B$, and state indices $\alpha=\rho,\sigma$, respectively (see also
figure caption). Further constraints then arise from Gaussian averages Eq.
(1). These are indicated by the red lines, keeping track of Hilbert space and
state indices after contractions. For Page states, each of the $n!$
contributions resulting from the Gaussian averages of the $2n$ complex
amplitudes in Eq. (II) is weighted by an overall factor $1/D^{n}$, and terms
can be organized according to the numbers of free subspace summations, or
‘cycles’, as we discuss next.

Figure 1:  Tensor network representation of averages Eq. (II). Top left:
Representation of a pair of amplitudes from the expansion
$\alpha_{A}=\sum_{a,a^{\prime}}\sum_{b}\psi^{\alpha}_{ab}\bar{\psi}^{\alpha}_{a^{\prime}b}|a\rangle\langle
a^{\prime}|$, with $\alpha=\rho,\sigma$. Each dot represents an index to be
contracted, and contractions must be between right- and left-side indices. Top
right: Structure of $\mathrm{tr}(\rho_{A}-\sigma_{A})^{4}$, with black lines
representing index contractions resulting from matrix multiplication in
subspace $A$ (top line), traces in subspace $B$ (middle line), and state
indices $\alpha=\rho,\sigma$ (bottom line). Notice that the index structure of
states follows that of subspace $B$. When averaging the trace we only consider
leading order contributions in $1/D$ resulting from non-crossing permutations.
Gaussian averages then impose further contractions upon the structural ones,
indicated by the red lines. Middle: Resulting index structure for $n=6$ and
identity permuation $p=id$. This establishes six $B$-cycles each consisting of
one element, i.e. in the notation of main text
$\Lambda_{6}=(1^{6},2^{0},3^{0},4^{0},5^{0},6^{0})$. Bottom: Another example
of a non-crossing permutation for $n=6$, $p=(4,3,2,1,6,5)$. This permutation
establishes three $B$-cycles each consisting of two elements,
$\Lambda_{6}=(1^{0},2^{3},3^{0},4^{0},5^{0},6^{0})$. In the middle diagram,
contributions from states $\rho$ (positive sign) and $\sigma$ (negative sign)
sum to zero in each of the one-element cycles. In the bottom diagram
contributions from $\rho$ and $\sigma$ both come with positive sign and sum to
two, i.e. contributions from the three cycles add up to $2^{3}=8$.

##  III  Combinatorics of averages

It is instructive to first focus on the contribution involving only a single
state density matrix, say $\rho_{A}$,

$\displaystyle\langle\mathrm{tr}_{A}(\rho_{A}^{n})\rangle$
$\displaystyle=\langle\psi^{\rho}_{a^{1}b^{1}}\bar{\psi}^{\rho}_{a^{2}b^{1}}\psi^{\rho}_{a^{2}b^{2}}\dots\psi^{\rho}_{a^{n}b^{n}}\bar{\psi}^{\rho}_{a^{1}b^{n}}\rangle.$
(5)

These averages have been recently discussed in the context of the entanglement
entropy foo (c), and the main observations are Penington et al. (2019); Liu
and Vardhan (2020): (i) the $n!$ contributions resulting from the average of
$2n$ Gaussian distributed complex variables can be organized as a sum over the
permutation group
$\langle\mathrm{tr}_{A}(\rho_{A}^{n})\rangle=\frac{1}{D^{n}}\sum_{p\in
S_{n}}D_{A}^{C(\pi^{-1}\circ p)}D_{B}^{C(p)}$, where $C(p)$ is the number of
cycles in the permutation $p$ and $\pi$ defined by $\pi(i)=(i+1){\rm mod}(n)$,
(ii) the maximal number of cycles is $C(\pi^{-1}\circ p)+C(p)=n+1$ and is
realized by the non-crossing permutations, (iii) their combinatorics is
encoded in the Narayana numbers $N(n,k)$ where $k$ the number of cycles in
$B$, and (iv) contributions of crossing permutations are suppressed in powers
of $1/D$. Neglecting the latter, one thus arrives at
$\langle\mathrm{tr}_{A}(\rho_{A}^{n})\rangle=\frac{1}{D^{n}}\sum_{k=1}^{n}N(n,k)D_{A}^{n-k+1}D_{B}^{k}$,
which can be further organized in power-series defining hypergeometric
functions. The calculation of Eq. (5) has thus been succeeded once the
Narayana numbers have been identified as the combinatorial coefficients
summing all possible non-crossing permutations of the $n$ elements containing
$k$ $B$-cycles.

To extend the calculation to all terms Eq. (II) we introduce the Kreweras
numbers,

$\displaystyle{\rm Krew}(\Lambda_{n})$
$\displaystyle=\frac{n!}{\lambda_{1}!...\lambda_{n}!(n+1-l(\Lambda_{n}))!},$
(6)

with $l(\Lambda_{n})\equiv\sum_{i=1}^{n}\lambda_{i}$. They count the number of
non-crossing permutations composed of $\lambda_{i}$ $B$-cycles formed of $i$
elements, $\Lambda_{n}=(1^{\lambda_{1}},2^{\lambda_{2}},...,n^{\lambda_{n}})$,
and thus provide more detailed information than the Narayana numbers Kreweras
(1972); Simion (2000). Specifically, Narayana numbers sum all Kreweras numbers
specified by $l(\Lambda_{n})=k$ and $\sum_{i=1}^{n}i\lambda_{i}=n$ (see also
Appendix A). With this additional information we are now ready to tackle the
combinatorics required for the calculation of average Schatten $n$-distances.

Cycles in Eq. (II) can be formed from states $\rho$ or $\sigma$. Both
contribute the same in absolute value, however, not always with same sign.
That is, while the sign is always positive for $\rho$-cycles it alternates for
$\sigma$-cycles depending on whether the number of elements involved in the
cycle is even/odd foo (d). For permutations with odd element cycles the
contributions from $\rho$-cycles and $\sigma$-cycles thus cancel, and
therefore only those consisting of even elements contribute. Noting that
$b$-indices follow that of state-indices (see also Fig. 1) we arrive at the
same conclusion for $B$-cycles. That is, for non-crossing permutations with
$k$ $B$-cycles only
$\Lambda_{n}=(1^{0},2^{\lambda_{2}},3^{0}...,n^{\lambda_{n}})$ with all cycles
composed of even elements contribute, and summing the two choices
$\alpha=\rho,\sigma$ for each of the $k$ cycles adds up to a factor $2^{k}$.
As a corollary we notice that moments in Eq. (II) involving odd powers $n$
vanish, as anticipated above. We are then left with the combinatorical task of
counting the number of $k$-cycles consisting only of even elements. Summing
the corresponding Kreweras numbers (see Appendix A for details), we find

$\displaystyle N_{e}(n,k)$
$\displaystyle=\frac{2}{n}\binom{n/2}{k}\binom{n}{k-1}.$ (7)

##  IV  Average trace-distances

Joining parts, we find the average Schatten $n$-distances of two random Page
states $\langle
D_{n}(\rho_{A},\sigma_{A})\rangle=\frac{1}{2D^{n}}\sum_{k=1}^{n/2}2^{k}N_{e}(n,k)D_{A}^{n-k+1}D_{B}^{k}$,
which can be organized into a hypergeometric function (see Appendix B for
details). For the latter the replica limit can be taken, and we arrive at the
average trace-distance of two random Page states,

$\displaystyle\langle D_{1}(\rho_{A},\sigma_{A})\rangle$
$\displaystyle=\begin{cases}1-\frac{1}{4x},&\quad x\geq 1,\\\
\frac{8\sqrt{x}}{3\pi}\,{\cal F}(x),&\quad x\leq 1,\end{cases}$ (8)

where $x=\frac{D_{A}}{2D_{B}}$, and ${\cal
F}(x)={}_{2}F_{1}(\frac{1}{2},-\frac{1}{2},\frac{5}{2},x)$ a hypergeometric
function. Similar results have been recently derived in Ref. Kudler-Flam et
al. (2021) using free probability techniques, and Eq. (8) agrees with their
asymptotic expressions.

Fig. 2 shows the trace-distance of Page states for different numbers of qubits
$N$ (solid lines) as a function of the fraction $f\equiv N_{B}/N$ of partially
traced qubits, and $x=\frac{1}{2}D^{1-2f}$. Increasing $N$, one observes a
sharp transition from $\langle D_{1}\rangle\simeq 1$ to $\langle
D_{1}\rangle\simeq 0$ once the partially traced system contains more than half
of all qubits, $f>1/2$, where ‘$\simeq$’ indicates equality up to corrections
${\cal O}(1/D)$ exponentially small in the number of qubits. In the
thermodynamic limit, this becomes a first order transition, describing the
emergence of self-averaging of the reduced density matrix of random pure
states once more than half of the qubits are partially traced out. Two-state
discrimination of Page states for $N\to\infty$ is therefore possible with unit
probability $P_{\rho\sigma}=1$ if the measurement is performed on more than
half of the qubits, but becomes essentially impossible, $P_{\rho\sigma}=1/2$,
for measurements involving fractions smaller than half of the qubits. Finite
$N$ curves all intersect in $f=1/2$, and the probability for two-state
discrimination using measurements on half of the qubits is
$P_{\rho\sigma}=\frac{5\pi+4}{8\pi}\simeq 0.78$, in agreement with previous
work Ref. Puchała et al. (2016). Expanding the trace-distance around $f=1/2$
one finds $\langle
D_{1}\rangle\simeq\frac{4+\pi}{4\pi}+\frac{1}{4}(D^{1-2f}-1)$, i.e. the
probability of two-state discrimination decays with the number of unmeasured
qubits as $P_{\rho\sigma}={\rm const.}-N\ln 2/4\times(1-2f)$. At $f=1$ the
trace-distance is trivially zero for any realization of states, while Eq. (8)
predicts a value ${\cal O}(1/\sqrt{D})$, of the same order as the value at
$f=1-1/N$. The erroneous finite value at $f=1$ reflects that Page states Eq.
(1) realize state-normalization only on average, rather than for each
realization. We next turn to a discussion on the consequences of local
conservation laws.

###  Conservation laws

Page’s random pure states describe generic quantum states in chaotic systems
lacking any structure e.g. induced by conservation laws. For these information
scrambling is most efficient, and we next discuss how local conservation of
scalar charges, e.g. particle number, uni-axial magnetization, etc., affects
two-state discrimination in chaotic systems. More specifically, we consider
the presence of a single, extensive conserved scalar operator $\hat{Q}$ that
is subsystem additive: A partition of the system into the two subsystems $A$
and $B$ implies a decomposition $\hat{Q}=\hat{Q}_{A}+\hat{Q}_{B}$, and
eigenstates $\hat{Q}|n\rangle=Q(n)|n\rangle$ can be labeled by $n=(a,b)$ with
$Q(n)=Q_{A}(a)+Q_{B}(b)$. It is then convenient to introduce the spectral
distribution of $\hat{Q}$, $F(Q)\equiv D\Omega(Q)=\sum_{n}\delta_{Q,Q(n)}$,
and corresponding subsystem spectral densities, $F_{S}(Q_{S})\equiv
D_{S}\Omega_{S}(Q_{S})$, with $S=A,B$. For most cases we can assume that
(except from the far tails of the spectrum irrelevant for our considerations)
the unit normalized spectral densities are well approximated by Gaussians,

$\displaystyle\Omega(Q)$
$\displaystyle=\Omega(Q,N)=\frac{1}{\sqrt{2\pi\gamma^{2}N}}e^{-\frac{Q^{2}}{2\gamma^{2}N}},$
(9)

with $\gamma$ some $N$-independent scale, and correspondingly for subsystem
densities $\Omega_{S}(Q_{S})=\Omega(Q_{S},N_{S})$. For convenience we here
choose $Q=0$ as the value with largest spectral weight.

Focusing then on the two-state discrimination of charge eigenstates, we
substitute the average for Page states, Eq. (1), for the symmetry refined
version,

$\displaystyle\langle\psi^{\alpha}_{ab}\bar{\psi}^{\beta}_{cd}\rangle$
$\displaystyle=\frac{1}{F(Q)}\delta_{Q_{A}(a)+Q_{B}(b),Q}\delta_{ac}\delta_{bd}\delta_{\alpha\beta}.$
(10)

Eq. (10) describes random wave functions in the subspace of dimension $F(Q)$
fixed by total charge $Q$, and $\delta_{Q_{A}(a)+Q_{B}(b),Q}$ introduces non
trivial correlations between the subsystems. We first concentrate on the value
with largest spectral weight $Q=0$ for which the most universal behaviour can
be expected. Following then the previous calculation for Page states, we find
(see Appendix C for details)

$\displaystyle\langle D_{1}(\rho_{A},\sigma_{A})\rangle$
$\displaystyle=\begin{cases}1-\frac{1}{4x\sqrt{2f}},&x\geq 1,\\\
\frac{8\sqrt{x_{f}}}{3\pi}{\cal G}(x_{f},f),&x\leq 1,\end{cases}$ (11)

where we introduced $x_{f}\equiv x\sqrt{f/(1-f)}$ with
$x=\frac{D_{A}}{2D_{B}}$ as before, and ${\cal
G}(x,f)=\frac{3\pi}{4}\sum_{k=0}^{\infty}c_{k}x^{k}\binom{1/2}{k}\binom{1}{k+3/2}$
with $c_{k}=\left((1+2k)f+1/2-k\right)^{-1/2}$. As anticipated, the result Eq.
(11) is unviversal in the sense that it only depends on the numbers of qubits
$N$, $N_{B}$.

Figure 2:  Average trace-distance of pure random states, Eq. (8), (solid
lines) and charge eigenstates for $Q=0$, Eq. (11), (dashed lines) as functions
of the relative number of traced qubits $f\equiv N_{B}/N$. System sizes are
$N=6,10,20,50,400$.

Fig. 2 shows the trace-distance between two random charge eigenstates states,
Eq. (11), for different numbers of qubits $N$ (dashed lines) as a function of
the fraction $f\equiv N_{B}/N$ of partially traced qubits. Differences between
trace-distances of charge eigenstates and Page states are notable for small
systems sizes. They are most pronounced for $f\to 1/N$ and $f\to 1-1/N$, with
charge eigenstates slightly above, respectively, below that of structureless
Page states foo (e). At half-partition $f=1/2$, $x_{f}=x$ and ${\cal
G}(x,f)={\cal F}(x)$, and trace-distances of eigenstates of charges with
largest spectral weight and Page states are thus identical. This contrasts the
entanglement entropy, for which the largest difference between Page and
corresponding charge eigenstates are at half partition Bianchi and Donà
(2019); Lau et al. (2022); Monteiro et al. (2021).

Turning to eigenstates at finite charges $Q$ different from the value of
largest spectral weight, we focus on trace-distances at half-partition $f=1/2$
and the limits $f\to 1/N$, respectively, $f\to 1-1/N$. For $f=1/2$ we find a
weak non-monotonous $Q$-dependence of the average trace-distance of charge
eigenstates. Starting at the value $\langle D_{1}\rangle\simeq 0.57$ at $Q=0$,
it increases to a maximum value $\langle D_{1}\rangle\simeq 0.58$ at
$Q=\gamma\sqrt{N}$, before converging to the value $\langle D_{1}\rangle\simeq
0.50$ as $Q$ is further increased. In the limit $f\to 1/N$ we find that the
average trace-distances decreases with $Q$ as $\langle
D_{1}\rangle-1\sim-(\sqrt{N}/D)e^{Q^{2}/2\gamma^{2}N}$, while the leading
$Q$-dependence for $f\to 1-1/N$ is given by $\langle
D_{1}\rangle\sim(N^{1/4}/\sqrt{D})e^{Q^{2}/4\gamma^{2}N}$. In both limits this
corresponds to a substitution of $D_{S}\mapsto F_{S}(Q)$ in the result for
Page states, accounting for the reduced phase space volume of charge
eigenstates (see Appendix C for more detailed expression).

### Numerical analysis

Fig. 3 shows a comparison of the analytical predictions Eqs. (8) and (11) with
numerical results obtained from exact diagonalization of Hamiltonians
generating many-body chaos. The left panel shows eigenstates of an Sachdev-Ye-
Kitaev (SYK) model with all-to-all interaction Sachdev and Ye (1993); Kit ,
$\hat{H}_{\rm
SYK}=\frac{1}{4!}\sum_{i,j,k,l=1}^{N}J_{ijkl}\hat{\chi}_{i}\hat{\chi}_{j}\hat{\chi}_{k}\hat{\chi}_{l}$,
and the right pannel of a spin-$1/2$ Ising chain with nearest neighbor
interaction and longitudinal and transversal fields Kim and Huse (2013); Kim
et al. (2014); Zhang et al. (2015),
$\hat{H}_{S}=\sum_{i=1}^{N}\left(g\hat{\sigma}_{i}^{x}+h\hat{\sigma}_{i}^{z}+J\hat{\sigma}_{i}^{z}\hat{\sigma}_{i+1}^{z}\right)$,
and periodic boundary condition $\sigma_{N+1}^{z}=\sigma_{1}^{z}$. Here
$\\{\hat{\chi}_{l}\\}$ are Majorana operators and
$\\{\hat{\sigma}_{i}^{x},\hat{\sigma}_{i}^{z}\\}$ Pauli matrices. In both
cases we have chosen eigenstates from the center of the band, to calculate
their subsystem trace distances foo (f). In the SYK-model we average over $50$
realizations of couplings $J_{ijkl}$ (respectively $10$ for the largest system
size), randomly drawn from a Gaussian distribution with vanishing mean and
variance $\langle|J_{ijkl}|^{2}\rangle=6J^{2}/N^{3}$ where we set
$J=2/\sqrt{N}$. For the spin chain we follow Ref. Kim and Huse (2013); Kim et
al. (2014); Zhang et al. (2015), and use parameters
$(g,h,J)=(0.9045,0.8090,1.0)$ for which the sytem has been shown to be
thermalizing for small system sizes. Since $\hat{H}_{S}$ is translational
invariant, we first block diagonalize and then average over $7$ eigenstates
from a given momentum sector with energies near the band center, see also
Appendix D for further details.

The SYK model lacks local conservation laws, and we find excellent agreement
with Eq. (8) for Page states. For the spin chain with short-range interaction,
on the other hand, energy is locally conserved and has to be taken into
account as a locally conserved charge. Notice that translational invariance
also implies conservation of momentum. This is, however, not subsystem
additive and thus does not count as a locally conserved charge. Rather, we
restrict to a given momentum sector, as described above, and then find good
agreement with Eq. (11) for systems with a single conserved charge that is
subsystem additive. Deviations from analytical predictions are larger for the
spin chain, which we relate to eigenstates in the average that are not at
energies with largest spectral weight and deviations of the density of states
from Eq. (9). Overall the agreement with our analytical predictions for
subsystem trace distances in absence and presence of locally conserved scalar
charges, Eqs. (8) and (11), is very good even for the smallest systems with
Hilbert-space dimensions $D=2^{6}$.

Figure 3:  Left: Comparison of analytical prediction Eq. (8) (solid lines) and
numerical simulations of the SYK model (symbols), here for systems of
$N=14,18$ and $26$ Majorana fermions, corresponding to $N=6,8$ and $12$ qubit
systems, viz., the fermion occupations in even parity sector. Right:
Comparison of analytical prediction Eq. (11) (dashed lines) and numerical
simulations of the spin-$1/2$ Ising chain discussed in the main text
(symbols), here for $N=6$, $8$ and $12$ spins. Error bars indicate standard
deviation, and for deviations at $f=1$, where $\langle D_{1}\rangle=0$, see
discussion in main text.

##  V Summary and Discussion

We have studied two-state discrimination in chaotic quantum systems. Assuming
that one of two generic $N$-qubit random pure states $\rho$, $\sigma$ has been
randomly selected, we investigated the average two-state discrimination
probability
$P_{\rho\sigma}=\frac{1}{2}\left(1+D_{1}(\rho_{A},\sigma_{A})\right)$ that the
selected state is correctly identified from an optimally chosen experiment on
$N_{A}=N-N_{B}$ of the qubits. Here $D_{1}(\rho_{A},\sigma_{A})$ are the
subsystem trace distances of random pure states with $N_{B}$ of the qubits
partially traced out. In the thermodynamic limit $N\to\infty$, the latter
makes a sharp, first order transition from unity to zero at $f=1/2$, as the
fraction $f=N_{B}/N$ of unmeasured qubits is increased. We have given closed
analytic expression for the corresponding crossover at finite system sizes
$N$, valid up to corrections small in $1/D$.

We further studied the consequences of local conservation laws on two-state
discrimination. Specifically, we calculated the average subsystem trace-
distances for eigenstates of a single conserved scalar charge. Focusing on the
charge $Q=0$ with largest spectral weight we obtained a closed universal
expression for the trace distance that only depends on the numbers of qubits
$N$, $N_{B}$. We found that state discrimination at the specific point
$f=1/2$, i.e. involving measurements on half of the qubits, is not affected by
local conservation laws and the same as for Page states. Away from this point,
state discrimination in the presence of conservation laws becomes less/more
likely than in absence of the latter for measurements involving more/less than
half of the qubits. For eigenstates of general charges $Q$, state
discrimination at $f=1/2$ shows a weak non-monotonous behavior as $Q$ is
varied, while the behavior for different values of $f$ is similar as for
$Q=0$, as we checked in the limits $f\to 1/N$ and $1-1/N$, respectively. In
all cases, the probability for two-state discrimination involving local
measurements on non-extensive fractions of the $N$ qubits is 1/2 up to
corrections $1/D$ for Page states, respectively, $1/F(Q)$ for charge
eigenstates. The exponentially small trace-distance for $f\sim{\cal O}(1)$ is
expected from Eigenstate Thermalization Hypothesis (ETH) Srednicki (1994);
Rigol et al. (2008); Kaufman et al. (2016), and also in accordance with
subsystem ETH, its refined formulation applicable if the entire reduced
density matrix appears thermal Dymarsky et al. (2018). The trace distance
bounds other measures for distinguishability of quantum states, such as the
relative entropy and fidelity via Pinsker’s and Fuchs-van de Graaf’s
inequalities, respectively. Similar results e.g. for the consequences of
conservation laws on the latter may thus be expected.

We tested our predictions against exact diagonalization of Hamiltonians for
many-body chaotic systems. Specifically, we numerically calculated subsystem
trace distances of eigenstates of the SYK model, lacking any local
conservation laws, and an Ising spin chain with local energy conservation,
respectively, and found in both cases very good agreement with our analytial
predictions.

We here focused on charge eigenstates and generalizations to other pure states
in chaotic systems with locally conserved charges Nakagawa et al. (2018);
Sugiura and Shimizu (2012, 2013) should be interesting. Based on recent work
Altland et al. (2022), we expect that pure states conditioned by broad charge
distributions can be discriminated by local measurements (i.e. with
probability not exponentially small in $N$) even in the presence of strong
information scrambling. Finally, our results may be interesting in the context
of the black hole information paradox. Specifically, one may verify whether
the analogy between fixed-area states and random tensor networks, encountered
for the entanglement entropy Penington et al. (2019), continues to hold for
two-state discrimination of black hole micro-states.

_Acknowledgments:—_ We thank Fernando de Mello for discussions. T. M.
acknowledges collaborations with Alex Altland and David Huse on related
topics, and financial support by Brazilian agencies CNPq and FAPERJ. J. T. M.
acknowledges financial support by Brazilian agency CAPES.

##  Appendix A Summing Kreweras numbers

From Kreweras to Narayanas:—It is instructive to first review how Narayana
numbers result from summing Kreweras numbers $\Lambda_{n}$ with a fixed number
of cycles $l(\Lambda_{n})=k$. Substituting the explicit expression discussed
in the main text, we can organize this counting as

$\displaystyle N(n,k)$
$\displaystyle=\sum_{\lambda_{1}=0}^{\infty}\sum_{\lambda_{2}=0}^{\infty}\cdot\cdot\cdot\sum_{\lambda_{n}=0}^{\infty}\frac{n!\,\delta_{\sum_{i=1}^{n}\lambda_{i},k}\,\delta_{\sum_{i=1}^{n}i\lambda_{i},n}}{(n-k+1)!\lambda_{1}!\lambda_{2}!...\lambda_{n}!},$
(12)

where the two Kronecker-deltas fix the number of cycles to $k$ and total
number of elements to $n$, respectively. Implementing the latter in terms of
integrals $\delta_{x,n}=\frac{1}{2\pi}\int_{0}^{2\pi}e^{i(x-n)\phi}d\phi$, we
exchange integration and summation and arrive at,

$\displaystyle N(n,k)$ $\displaystyle=\frac{n!}{(n-k+1)!}\oint\frac{dz}{2\pi
i}\oint\frac{dw}{2\pi i}\frac{e^{z(w+w^{2}+...+w^{n})}}{z^{k+1}w^{n+1}},$ (13)

which, performing pole integrals gives

$\displaystyle N(n,k)$
$\displaystyle=\frac{\left(\partial_{w}^{n}(w+w^{2}+...+w^{n})^{k}\right)|_{w=0}}{k!(n-k+1)!}.$
(14)

Summing the finite geometric series one then arrives, upon performing the $n$
fold derivative and setting $w=0$, at the Narayana numbers

$\displaystyle N(n,k)$ $\displaystyle=\frac{1}{n}\binom{n}{k}\binom{n}{k-1}.$
(15)

From Kreweras to ‘even-element’ Narayanas:—We can now extend the calculation
to Kreweras numbers
$\Lambda_{n}=(1^{0},2^{\lambda_{2}},3^{0}...,n^{\lambda_{n}})$, for which all
cycles are composed of even elements,

$\displaystyle N_{e}(n,k)$
$\displaystyle=\sum_{\lambda_{2}=0}^{\infty}\sum_{\lambda_{4}=0}^{\infty}\cdot\cdot\cdot\sum_{\lambda_{n}=0}^{\infty}\frac{n!\,\delta_{\sum_{i=1}^{n}\lambda_{i},k}\,\delta_{\sum_{i=1}^{n}i\lambda_{i},n}}{(n-k+1)!\lambda_{2}!\lambda_{4}!...\lambda_{n}!},$
(16)

where $n$ is even. Proceeding then as previously, we find

$\displaystyle N_{e}(n,k)$
$\displaystyle=\frac{n!}{(n-k+1)!}\oint\frac{dz}{2\pi i}\oint\frac{dw}{2\pi
i}\frac{e^{z(w^{2}+w^{4}+...+w^{n})}}{z^{k+1}w^{n+1}},$ (17)

which performing pole integrals gives,

$\displaystyle N_{e}(n,k)$
$\displaystyle=\frac{\left(\partial_{w}^{n}(w^{2}+w^{4}+...+w^{n})^{k}\right)|_{w=0}}{k!(n-k+1)!}.$
(18)

Summing again the finite geometric series, performing the $n$ fold derivative
and setting $w=0$, one then arrives at the ‘even-element’ Narayana numbers,

$\displaystyle N_{e}(n,k)$
$\displaystyle=\frac{2}{n}\binom{n/2}{k}\binom{n}{k-1},$ (19)

stated in the main text.

##  Appendix B Subsystem trace-distance

Re-organizing the expression in the main text we find for even $n$-Schatten
distances

$\displaystyle\langle D_{n}(\rho_{A},\sigma_{A})\rangle$
$\displaystyle=\frac{D_{A}}{nD_{B}^{n}}\sum_{k=1}^{\infty}\binom{n/2}{k}\binom{n}{k-1}\left(\frac{2D_{B}}{D_{A}}\right)^{k},$
(20)

where we extended the summation to infinity since the binomial restricts
$k\leq n/2$. For $x\equiv 2D_{B}/D_{A}\leq 1$ the sum is the hypergeometric
function ${\cal F}(x)={}_{2}F_{1}\left(1-\frac{n}{2},-n,2,x\right)$ which can
be generalized to real $n$. Taking then the replica limit $n\to 1$,

$\displaystyle\langle D_{n}(\rho_{A},\sigma_{A})\rangle$
$\displaystyle={}_{2}F_{1}\left(\frac{1}{2},-1,2,x\right)=1-\frac{1}{4x},$
(21)

and we recall that $x\leq 1$. For the complementary case $x>1$, we need to
first reorganize the sum (20), changing $k\mapsto n/2-k+1$,

$\displaystyle\langle
D_{n}(\rho_{A},\sigma_{A})\rangle=\frac{2^{\frac{n}{2}}D_{A}}{nD^{\frac{n}{2}}}\sum_{k=0}^{\infty}\binom{n/2}{k}\binom{n}{n/2+1+k}\left(\frac{D_{A}}{2D_{B}}\right)^{k},$
(22)

where we employed that $\binom{n}{k}=\binom{n}{n-k}$. The sum defines the
hypergeometric function ${\cal
F}(x)={}_{2}F_{1}\left(-\frac{n}{2},1-\frac{n}{2},2+\frac{n}{2},x\right)$,
with $x=\frac{D_{A}}{2D_{B}}$ and can be extended to real $n$. Taking the
replica limit $n\to 1$ we then arrive at Eq. (8) in the main text.

##  Appendix C Charge eigenstates

Straightforward generalization to charge eigenstates defined in the main text,
we arrive at

$\displaystyle\langle D_{1}$
$\displaystyle(\rho_{A},\sigma_{A})\rangle=\frac{1}{F(Q)}\sum_{Q_{A}Q_{B}}\delta_{Q,Q_{A}+Q_{B}}\Bigg{\\{}$
$\displaystyle\quad\left(F_{A}(Q_{A})F_{B}(Q_{B})-\frac{1}{2}F_{B}^{2}(Q_{B})\right)\Theta_{<}$
$\displaystyle+\frac{4\sqrt{2}}{3\pi}F_{A}^{3/2}(Q_{A})F^{1/2}_{B}(Q_{B}){}_{2}F_{1}\left(-\frac{1}{2},\frac{1}{2},\frac{5}{2},x\right)\Theta_{>}\Bigg{\\}},$
(23)

where $\Theta_{<}\equiv\theta\left(x-1\right)$,
$\Theta_{>}\equiv\theta\left(1-x\right)$, with $x\equiv
F_{A}(Q_{A})/(2F_{B}(Q_{B}))$, $F_{S}(Q)=D_{S}\Omega_{S}(Q)$, and
$\Omega_{S}(Q)=\frac{1}{\sqrt{2\pi\gamma^{2}N_{S}}}\exp\left(-Q_{S}^{2}/(2\gamma^{2}N_{S})\right)$.

$Q=0$:—Concentrating first on the charge with largest spectral weight $Q=0$
where the density of states is peaked, we can substitute ($N_{A}$, $N_{B}$ are
integers), $\Theta_{<}=\theta(N_{A}-N_{B})$ and
$\Theta_{>}=\theta(N_{B}-N_{A})$. Using further that

$\displaystyle\frac{1}{F(0)}\sum_{Q_{A}}F_{A}^{k}(Q_{A})F_{B}^{m}(-Q_{A})$
$\displaystyle=\frac{D^{k}_{A}D^{m}_{B}}{(2\pi\gamma^{2})^{\frac{k+m}{2}-1}D}\sqrt{\frac{N_{A}N_{B}}{N_{A}^{k}N^{m}_{B}}}\sqrt{\frac{N}{mN_{A}+kN_{B}}},$
(24)

we arrive at,

$\displaystyle\langle D_{1}(\rho_{A},\sigma_{A})\rangle$
$\displaystyle=\begin{cases}1-\frac{1}{4x\sqrt{2f}}&x\geq 1,\\\
\sum_{k=0}^{\infty}\frac{2\sqrt{x_{f}}x_{f}^{k}}{\sqrt{(1+2k)f+(1/2-k)}}\binom{1/2}{k}\binom{1}{k+3/2},&x\leq
1,\end{cases}$ (25)

where $x_{f}\equiv x\sqrt{f/(1-f)}$, $x=D_{A}/(2D_{B})$, and $f=N_{B}/N$, as
stated in Eq. (11) in the main text.

Finite charges:—Expressions for finite charges $Q>0$ can be derived in a
similar way. We here concentrate on half partitions $N_{A}=N_{B}=N/2$, and the
limits $f\to 1/N$, respectively, $f\to 1-1/N$. For half partitions
$N_{A}=N_{B}=N/2$, we can use that

$\displaystyle\frac{1}{F(Q)}$
$\displaystyle\sum_{Q_{A}}F_{A}^{k}(Q_{A})F_{B}^{m}(Q-Q_{A})\theta_{S}(Q_{A})$
$\displaystyle=$
$\displaystyle\frac{D_{A}^{k}D_{B}^{m}}{D}\frac{\sqrt{2\pi\gamma^{2}N}}{(\pi\gamma^{2}N)^{\frac{k+m}{2}}}e^{-\frac{2km-
k-m}{k+m}\frac{Q^{2}}{2\gamma^{2}N}}\times$
$\displaystyle\times\sum_{Q_{A}}e^{-\frac{(k+m)Q_{A}^{2}}{\gamma^{2}N}}\theta_{S}(Q_{A}+\frac{m}{k+m}Q),$
(26)

where
$\theta_{<}(Q_{A}+\frac{m}{k+m}Q)\equiv\theta(Q/2-\frac{NC}{2Q}-\frac{m}{k+m}Q-Q_{A})$,
$\theta_{>}(Q_{A}+\frac{m}{k+m}Q)\equiv\theta(Q_{A}-Q/2+\frac{NC}{2Q}+\frac{m}{k+m}Q)$,
and $C\equiv\gamma^{2}\ln 2$. With this we then arrive at the following
expression for the trace-distance at half partition,

$\displaystyle\langle D_{1}(\rho_{A},$
$\displaystyle\sigma_{A})\rangle=\frac{1}{2}\operatorname{erfc}\Bigg{(}\sqrt{\frac{N}{2\gamma^{2}}}\frac{C}{Q}\Bigg{)}$
$\displaystyle-\frac{1}{4}e^{\frac{Q^{2}}{2\gamma^{2}N}}\operatorname{erfc}\Bigg{(}\frac{NC+Q^{2}}{Q\sqrt{2\gamma^{2}N}}\Bigg{)}$
$\displaystyle+\sum_{k=0}^{\infty}\binom{1/2}{k}\binom{1}{k+3/2}\Bigg{[}\frac{e^{\frac{(k+1/2)Q^{2}}{2\gamma^{2}N}}}{2}\Bigg{]}^{k+1/2}\times$
$\displaystyle\times\operatorname{erfc}\Bigg{(}\frac{(1+2k)Q^{2}-2NC}{2Q\sqrt{2\gamma^{2}N}}\Bigg{)},$
(27)

where $\operatorname{erfc}(x)=(2/\sqrt{\pi})\int_{x}^{\infty}e^{-t^{2}}dt$.
This can be evaluated numerically and shows the $Q$-dependence discussed in
the main text.

For $f\to 1/N$ we can neglect the contribution involving $\Theta_{>}$, and
find $\langle D_{1}\rangle-1\sim-\sqrt{N}e^{Q^{2}/2\gamma^{2}N}/D$. Proceeding
similarly in the opposite limit $f\to 1-1/N$, we arrive at $\langle
D_{1}\rangle\sim N^{1/4}e^{Q^{2}/4\gamma^{2}N}/\sqrt{D}$, as also stated in
the main text.

Figure 4:  Subsystem trace-distances from exact diagoanlization for a chain of
$10$ spins. Solid and dashed lines are the analytical predictions in absence
and presence of conservation laws, Eqs. (8) and Eq. (11), respectively. Inset:
Density of states for zero momentum eigenstates with Gaussian fit (solid
line).

##  Appendix D Exact diagonaliztion

We numerically calculate eigenstates of the spin chain Hamiltonian first block
diagonalizing $\hat{H}_{S}$ into momentum sectors, and then concentrating on
eigenfunctions within the zero momentum eigenspace. To determine the energy
window from which to choose eigenstates we calculate the density of states,
see inset of Fig. 4 for the example of the chain with 10 spins. The latter is
e.g. peaked at $-0.4\pm 0.3$ and reasonably well described by a Gaussian
profile (solid line). Taking in this case $5$ eigenstates from the window
$\sim(-0.8,0.0)$ centered around $\sim-0.4$ we arrive at the subsystem trace
distance shown in Fig. 4, and compared to the analytical prediction in
presence (dashed line) and absence (solid line) of a local conservation law.

## References

  * Page (1993) D. N. Page, Phys. Rev. Lett. 71, 1291 (1993), URL https://link.aps.org/doi/10.1103/PhysRevLett.71.1291.
  * Bianchi and Donà (2019) E. Bianchi and P. Donà, Phys. Rev. D 100, 105010 (2019), URL https://link.aps.org/doi/10.1103/PhysRevD.100.105010.
  * Bianchi et al. (2021) E. Bianchi, L. Hackl, M. Kieburg, M. Rigol, and L. Vidmar, _Volume-law entanglement entropy of typical pure quantum states_ (2021), URL https://arxiv.org/abs/2112.06959.
  * Rigol et al. (2008) M. Rigol, V. Dunjko, and M. Olshanii, Nature 452, 854 (2008), URL https://doi.org/10.1038/nature06838.
  * Lau et al. (2022) P. H. C. Lau, T. Noumi, Y. Takii, and K. Tamaoka, _Page curve and symmetries_ (2022), URL https://arxiv.org/abs/2206.09633.
  * Ares et al. (2022) F. Ares, S. Murciano, and P. Calabrese, Journal of Statistical Mechanics: Theory and Experiment 2022, 063104 (2022), URL https://doi.org/10.1088.
  * Vidmar and Rigol (2017) L. Vidmar and M. Rigol, Phys. Rev. Lett. 119, 220603 (2017), URL https://link.aps.org/doi/10.1103/PhysRevLett.119.220603.
  * Nakagawa et al. (2018) Y. O. Nakagawa, M. Watanabe, H. Fujita, and S. Sugiura, Nature Communications 9, 1635 (2018).
  * Sugiura and Shimizu (2012) S. Sugiura and A. Shimizu, Phys. Rev. Lett. 108, 240401 (2012), URL https://link.aps.org/doi/10.1103/PhysRevLett.108.240401.
  * Sugiura and Shimizu (2013) S. Sugiura and A. Shimizu, Phys. Rev. Lett. 111, 010401 (2013), URL https://link.aps.org/doi/10.1103/PhysRevLett.111.010401.
  * Murciano et al. (2022) S. Murciano, P. Calabrese, and L. Piroli, Phys. Rev. D 106, 046015 (2022), URL https://link.aps.org/doi/10.1103/PhysRevD.106.046015.
  * Majidy et al. (2022) S. Majidy, A. Lasek, D. A. Huse, and N. Y. Halpern, _Non-abelian symmetry can increase entanglement entropy_ (2022), URL https://arxiv.org/abs/2209.14303.
  * Altland et al. (2022) A. Altland, D. A. Huse, and T. Micklitz, _Maximum entropy quantum state distributions_ (2022), URL https://arxiv.org/abs/2203.12580.
  * Bae and Kwek (2015) J. Bae and L.-C. Kwek, Journal of Physics A: Mathematical and Theoretical 48, 083001 (2015), URL https://doi.org/10.1088.
  * foo (a) There are two kinds of errors i.e. the probability $p_{\rho}$ one guesses wrong when it is $\rho$, and the probability $p_{\sigma}$ one guess wrong when it is $\sigma$, respectively. The best success probability minimizes the maximum $\max(p_{\rho},p_{\sigma})$.
  * foo (b) That is, the eigenvalues of $\sqrt{\Lambda^{\dagger}\Lambda}$, and when $\Lambda$ is hermitean, singular values $\lambda_{i}$ are just the absolute values of the eigenvalues.
  * Zhang et al. (2019) J. Zhang, P. Ruggiero, and P. Calabrese, Phys. Rev. Lett. 122, 141602 (2019), URL https://link.aps.org/doi/10.1103/PhysRevLett.122.141602.
  * Monteiro et al. (2021) F. Monteiro, M. Tezuka, A. Altland, D. A. Huse, and T. Micklitz, Phys. Rev. Lett. 127, 030601 (2021), URL https://link.aps.org/doi/10.1103/PhysRevLett.127.030601.
  * foo (c) Application of the replica trick allows for a calculation of the entanglement entropy from average moments of the reduced density matrix, $M_{r}=\langle\mathrm{tr}_{A}(\rho_{A}^{r})\rangle$, as $S_{A}=-\partial_{r}M_{r}|_{r=1}$.
  * Penington et al. (2019) G. Penington, S. H. Shenker, D. Stanford, and Z. Yang, _Replica wormholes and the black hole interior_ (2019), eprint arXiv:1911.11977.
  * Liu and Vardhan (2020) H. Liu and S. Vardhan, _Entanglement entropies of equilibrated pure states in quantum many-body systems and gravity_ (2020), eprint arXiv:2008.01089.
  * Kreweras (1972) G. Kreweras, Discrete Mathematics 1, 333 (1972), ISSN 0012-365X, URL https://www.sciencedirect.com/science/article/pii/0012365X72900416.
  * Simion (2000) R. Simion, Discrete Mathematics 217, 367 (2000), ISSN 0012-365X, URL https://www.sciencedirect.com/science/article/pii/S0012365X99002733.
  * foo (d) The simplest way to see this, is to account for the sign factor ${\rm sgn}(\sigma)$ in Eq. (4) by defining averages for states $\sigma$ with a minus sign, i.e. $\langle\psi^{\sigma}_{ab}\bar{\psi}^{\sigma}_{cd}\rangle=-\frac{1}{D}\delta_{ac}\delta_{bd}$. Then every $\sigma$ cycle containing odd/even elements contributes with a negative/positive sign.
  * Kudler-Flam et al. (2021) J. Kudler-Flam, V. Narovlansky, and S. Ryu, PRX Quantum 2, 040340 (2021), URL https://link.aps.org/doi/10.1103/PRXQuantum.2.040340.
  * Puchała et al. (2016) Z. Puchała, Ł. Pawela, and K. Życzkowski, Phys. Rev. A 93, 062112 (2016), URL https://link.aps.org/doi/10.1103/PhysRevA.93.062112.
  * foo (e) Notice that Eq. (11) diverges in the limits $f=0$ and $f=1$, where $F_{B}$ and $F_{A}$ become $\delta$-functions. In Fig. 2 we have interpolated with a quadratic polynomial to values from Eq. (C1) (Appendix C), with $F_{B}=1$, $F_{A}(Q_{A})=F(Q)$ and $F_{A}=1$, $F_{B}(Q_{B})=F(Q)$, respectively, with an error of order ${\cal O}(1/F(0))$.
  * Sachdev and Ye (1993) S. Sachdev and J. Ye, Phys. Rev. Lett. 70, 3339 (1993), URL https://link.aps.org/doi/10.1103/PhysRevLett.70.3339.
  * (29) A. Kitaev, http://online.kitp.ucsb.edu/online/ entangled15/kitaev/ …. /kitaev2/ (Talks at KITP on April 7th and May 27th 2015).
  * Kim and Huse (2013) H. Kim and D. A. Huse, Phys. Rev. Lett. 111, 127205 (2013), URL https://link.aps.org/doi/10.1103/PhysRevLett.111.127205.
  * Kim et al. (2014) H. Kim, T. N. Ikeda, and D. A. Huse, Phys. Rev. E 90, 052105 (2014), URL https://link.aps.org/doi/10.1103/PhysRevE.90.052105.
  * Zhang et al. (2015) L. Zhang, H. Kim, and D. A. Huse, Phys. Rev. E 91, 062128 (2015), URL https://link.aps.org/doi/10.1103/PhysRevE.91.062128.
  * foo (f) The SYK model preserves fermion parity and (without loss of generality) we have chosen eigenstates from the even parity sector.
  * Srednicki (1994) M. Srednicki, Phys. Rev. E 50, 888 (1994), URL https://link.aps.org/doi/10.1103/PhysRevE.50.888.
  * Kaufman et al. (2016) A. M. Kaufman, M. E. Tai, A. Lukin, M. Rispoli, R. Schittko, P. M. Preiss, and M. Greiner, Science 353, 794 (2016), URL https://www.science.org/doi/abs/10.1126/science.aaf6725.
  * Dymarsky et al. (2018) A. Dymarsky, N. Lashkari, and H. Liu, Physical Review E 97 (2018), URL https://doi.org/10.1103/PhysRevE.97.012140.