# Square-free reducts of words

Jarosław Grytczuk  Faculty of Mathematics and Information Science, Warsaw
University of Technology, 00-662 Warsaw, Poland<EMAIL_ADDRESS>and
Szymon Stankiewicz  Zürich, Switzerland<EMAIL_ADDRESS>
###### Abstract.

A _square_ is a finite non-empty word consisting of two identical adjacent
blocks. A word is _square-free_ if it does not contain a square as a factor.
In any finite word one may delete the repeated block of a square, obtaining
thereby a shorter word. By repeating this process, a square-free word is
eventually reached, which we call a _reduct_ of the original word.

How many different reducts a single word may have? It is not hard to prove
that any binary word has exactly one reduct. We prove that there exist ternary
words with arbitrarily many reducts. Moreover, the function counting the
maximum number of reducts a ternary word of length $n$ may have grows
exponentially. We also prove that over four letters, there exist words with
any given number of reducts, which does not seem to be the case for ternary
words. Finally, we demonstrate that the set of all finite ternary words splits
into finitely many classes of _related_ words (one may get from one word to
the other by a sequence of square reductions and factor duplications). A few
open questions are posed concerning some structures on words defined with the
use of the square reduction.

Research supported by the National Science Center of Poland, grant
2015/17/B/ST1/02660.

##  1\. Introduction

A _square_ is a finite non-empty word built of two identical adjacent blocks.
For instance, the word $\mathtt{hotshots}$ is a square. A word $W$ _contains_
a square if it can be written as $W=UXXV$ for some words $U,V$, and a non-
empty word $X$. A word is _square-free_ if it does not contain any squares.
For instance, the word $\mathtt{repetition}$ contains the square
$\mathtt{titi}$, while $\mathtt{reincarnation}$ is square-free.

It is easy to check that any binary square-free word has length at most $3$.
However, there exist ternary square-free words of any length, as proved by
Thue in [14] (see [4]). This result inspired a lot of further research,
leading to the birth of Combinatorics on Words, a wide discipline with lots of
exciting problems, deep results, and important applications (see [1, 3, 5, 7,
9, 10, 11]).

In this paper we consider the following problem concerning squares in words.
Let $W$ be any finite word with a square, so $W=UXXV$. We may delete one of
the two blocks of a square, which gives a shorter word $W^{\prime}=UXV$. If
$W^{\prime}$ contains a square, say $W^{\prime}=U^{\prime}YYV^{\prime}$, then
we may repeat this operation of _square reduction_ to get another word
$W^{\prime\prime}=U^{\prime}YV^{\prime}$. And so on, until we finally get a
square-free word. Since a word may have many squares situated in different
positions, this process depends on our choice of a square to be reduced in
every single step. Any final word that can be obtained from a word $W$ by a
sequence of square reductions is called a _square-free reduct_ of $W$, or just
a _reduct_ , for short.

How many reducts a single word may have? It is not hard to demonstrate that
every binary word has exactly one reduct (Proposition 1). However, for ternary
words the situation changes dramatically. We prove (Theorem 1) that for every
positive integer $k$ there exists a ternary word with at least $k$ distinct
reducts. Furthermore, there exist ternary words of length $n$ with
exponentially many reducts (Theorem 2). Also, for every integer $k\geqslant 1$
there exists a word over a $4$-letter alphabet with exactly $k$ distinct
reducts (Theorem 3). Finally, we consider a naturally defined graph on the set
of ternary words, in which two words are adjacent if one can be obtained from
the other by a single square reduction. We prove (Theorem 5) that this graph
has finitely many connected components. In other words, we may define two
words as _related_ if one can be obtained from the other by a finite sequence
of square reductions and factor _duplications_ (the reverse operation to the
square reduction). Then Theorem 5 asserts that all ternary words form a finite
number of families of mutually related words.

All these results are proved in the next section. The last section of the
paoer is devoted to some open problems.

The idea of square reduction in words is not new. Indeed, the reverse
operation is intensively studied in Genetics, where it is called the _tandem
duplication_ , as the fundamental mechanism in the evolution of organisms (see
[12],[15]). Naturally, some computational or language theoretic aspects are
also widely studied (see [2], [8]).

##  2\. The results

Let $W$ be a finite word. Denote by $\mathcal{R}(W)$ the set of all reducts of
$W$ and let $r(W)$ be the cardinality of $\mathcal{R}(W)$. We start with a
simple result concerning binary words.

######  Proposition 1.

Every binary word $W$ satisfies $r(W)=1$.

###### Proof.

There exist only six square-free binary words, namely

$\mathtt{0,1,01,10,010,101}.$

The first two are the reducts of only two types of words, namely,
$\mathtt{00\cdots 0}$ and $\mathtt{11\cdots 1}$.

Now, notice that any reduct of a word $W$ must have the same initial and final
letter as $W$. This completes the proof, since the remaining four square-free
binary words have four different pairs consisting of the initial and the final
letter. ∎

###  2.1. Ternary words with many reducts

The above proposition is no longer true for words over a $3$-letter alphabet.
For instance, the word $\mathtt{abcbabcbc}$ has two different reducts:
$\mathtt{abc}$ and $\mathtt{abcbabc}$. We shall prove that for every
$k\geqslant 1$, there exists a ternary word with at least $k$ distinct
reducts. The proof is based on two lemmas involving specifically defined
morphisms.

Let us define the following morphism $\varphi$ over the alphabet
$\\{\mathtt{a,b,c}\\}$:

$\mathtt{a}\mapsto\mathtt{abacabcbacabacbabc}$
$\mathtt{b}\mapsto\mathtt{abacabcbacbcacbabc}$
$\mathtt{c}\mapsto\mathtt{abacbcacbacabcbabc}.$

Let us also denote $\varphi(\mathtt{a})=A$, $\varphi(\mathtt{b})=B$, and
$\varphi(\mathtt{c})=C$. Recall that a morphism is _square-free_ if the image
of every square-free word is square-free.

######  Lemma 1.

The morphism $\varphi$ is square-free.

###### Proof.

By the result of Crochemore, to prove that a morphism is square-free it
suffices to check its images on the set of square-free words of length at most
$3$. This can be verified by computer, or by hand, provided you have a lot of
patience. ∎

We write $X\leadsto Y$ to state that starting from the word $X$ one may reach
the word $Y$ by a sequence of square reductions. Let

$D=\mathtt{abacabcbabcbabacabacacbcacbabcbababc}.$

######  Lemma 2.

We have $D\leadsto A$ and $D\leadsto B$.

###### Proof.

This can be checked by hand. Below both reductions are depicted, where blocks
of the reduced squares are distinguished with red and blue, while gray part is
never used.

######  Case 1.

$D\leadsto A$.

$\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\mathtt{abacab}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathtt{cbab}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathtt{cbab}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathtt{acabacacbcacbabcbaba}\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>
$\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\mathtt{abacab}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathtt{c}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathtt{ba}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathtt{ba}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathtt{cabacacbcacbabcbaba}\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>
$\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\mathtt{abacab}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathtt{cbacaba}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathtt{cacb}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathtt{cacb}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathtt{abcbaba}\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>
$\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\mathtt{abacab}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathtt{cbacab}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathtt{ac}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathtt{ac}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathtt{babcbaba}\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>
$\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\mathtt{abacab}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathtt{cbacaba}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathtt{cbab}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathtt{cbab}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathtt{a}\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>
$\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\mathtt{abacab}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathtt{cbacabac}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathtt{ba}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathtt{ba}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathtt{}\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>
$\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\mathtt{abacab}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathtt{cbacabacba}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathtt{}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathtt{}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathtt{}\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>
######  Case 2.

$D\leadsto B$.

$\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\mathtt{abacab}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathtt{cbab}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathtt{cbab}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathtt{acabacacbcacbabcbaba}\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>
$\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\mathtt{abacab}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathtt{c}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathtt{ba}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathtt{ba}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathtt{cabacacbcacbabcbaba}\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>
$\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\mathtt{abacab}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathtt{c}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathtt{baca}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathtt{baca}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathtt{cbcacbabcbaba}\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>
$\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\mathtt{abacab}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathtt{cb}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathtt{ac}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathtt{ac}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathtt{bcacbabcbaba}\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>
$\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\mathtt{abacab}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathtt{cbacbca}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathtt{cbab}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathtt{cbab}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathtt{a}\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>
$\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\mathtt{abacab}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathtt{cbacbcac}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathtt{ba}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathtt{ba}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathtt{}\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>
$\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\mathtt{abacab}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathtt{cbacbcacba}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathtt{}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathtt{}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\mathtt{}\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>
∎

Now we are ready to prove the aforementioned result.

######  Theorem 1.

For every integer $k\geqslant 1$, there exists a ternary word $W$ with
$r(W)\geqslant k$.

###### Proof.

Consider the following three morphisms, where the words $A,B,C$ are defined
above:

$\varphi:\mathtt{a}\mapsto A,\mathtt{b}\mapsto B,\mathtt{c}\mapsto C$
$\varphi^{\prime}:\mathtt{a}\mapsto B,\mathtt{b}\mapsto A,\mathtt{c}\mapsto C$
$\psi:\mathtt{a}\mapsto D,\mathtt{b}\mapsto D,\mathtt{c}\mapsto C.$

Let $S$ be any word over the alphabet $\\{\mathtt{a,b,c}\\}$ starting with the
letter $\mathtt{a}$. We shall demonstrate that

(2.1) $r(\psi(S))\geqslant 2r(S),$

which implies the assertion of the theorem.

By Lemma 2, we have $D\leadsto A$ and $D\leadsto B$, and therefore
$\psi(S)\leadsto\varphi(S)$ and $\psi(S)\leadsto\varphi^{\prime}(S)$. Notice
that for any two words $X,Y$ and any non-erasing morphism $\sigma$, the
relation $X\leadsto Y$ implies $\sigma(X)\leadsto\sigma(Y)$. In consequence,
for every square-free reduct $R$ of $S$, we have:

$\psi(S)\leadsto\varphi(R)$ $\psi(S)\leadsto\varphi^{\prime}(R).$

Since both morphisms $\varphi,\varphi^{\prime}$ are square-free (by Lemma 1),
both words $\varphi(R)$ and $\varphi^{\prime}(R)$ are reducts of the word
$\psi(S)$. Moreover, this reducts are different because the first letter of
$S$, and the same of $R$, is the letter $\mathtt{a}$, while
$\varphi(\mathtt{a})=A\neq B=\varphi^{\prime}(\mathtt{a})$.

We have seen that one reduct $R$ of $S$ gives rise to two distinct reducts
$\varphi(R),\varphi^{\prime}(R)$ of $\psi(S)$. Since both morphisms $\varphi$
and $\varphi^{\prime}$ are injective, this proves the inequality (2.1), which
completes the proof. ∎

We will now demonstrate that there are ternary words whose number of reducts
is exponential in their length. This will provide also an alternative proof of
Theorem 1. We will make use of the following well-known fact (see [13]).

######  Lemma 3.

The number of square-free words of length $n$ over a $3$-letter alphabet is at
least $c^{n}$, for some constant $c>1$.

Let $f_{k}(n)$ be defined as the maximum value of $r(W)$ over all words of
length $n$ over alphabet of size $k$.

######  Theorem 2.

There exists a constant $\alpha>1$ such that $f_{3}(n)\geqslant\alpha^{n}$.

###### Proof.

Let $A,B,C$, and $D$ be the same four words used in the proof of Theorem 1.
Consider a word $W_{m}=CDDDCDDD\cdots CDDD=(CDDD)^{m}$, with $m\geqslant 1$.
By Lemma 2, each cube $DDD$ can be reduced to any of the words
$A,B,AB,BA,ABA,BAB$. So, the word $W_{m}$ can be reduced to any square-free
word over alphabet $\\{A,B,C\\}$ having $m$ letters $C$ and starting with $CA$
or $CB$. The number of such words is at least $c^{m}$, by Lemma 3. By Lemma 1,
each such reduct is also a square-free word over alphabet
$\\{\mathtt{a,b,c}\\}$. Thus, $W_{m}$ has at least $c^{m}$ distinct reducts.
Since the length of $W_{m}$ is at most $36m$, the assertion of the theorem
follows for $\alpha=c^{1/36}$. ∎

The best possible value of the constant $c$ from Lemma 3 is roughly $1.3$ (see
[13]), so, for the second constant we get roughly $\alpha\approx 1.0073$.

###  2.2. Words over four letters

We first prove the following result.

######  Theorem 3.

For every integer $k\geqslant 1$, there exists a word over a $4$-letter
alphabet with exactly $k$ distinct reducts.

###### Proof.

Let us fix the $4$-letter alphabet as $\\{\mathtt{a,b,x,y}\\}$. Take the word

$F=\mathtt{xabaxababx}$

and notice that it has exactly two distinct reducts, namely, $P=\mathtt{xabx}$
and $Q=\mathtt{xabaxabx}=Q^{\prime}P$. Let $W_{\infty}$ be any infinite
square-free word over the alphabet $\\{\mathtt{a,b,y}\\}$ starting with the
letter $\mathtt{y}$. Let $W_{1},W_{2},\dots$ be any sequence of prefixes of
the word $W_{\infty}$ with strictly growing lengths. We may assume that each
word $W_{i}$ also ends with the letter $\mathtt{y}$. Define the sequence of
words $S_{i}$ by

$S_{i}=FW_{1}FW_{2}\cdots FW_{i},$

for all $i\geqslant 1$.

We are going to prove that $r(S_{i})=i+1$ for every $i\geqslant 1$. More
precisely, we will demonstrate that the set of reducts of each word $S_{i}$
consists of the following elements:

(2.2)
$\mathcal{R}(S_{i})=\\{PW_{i},QW_{i}\\}\cup\\{PW_{1}QW_{i},PW_{2}QW_{i},\dots,PW_{i-1}QW_{i}\\}.$

First notice that all the above words are indeed square-free. It is also not
hard to check that all can be obtained from $S_{i}$ by square reductions. For
example, since $W_{j+1}=W_{j}Y_{j}$, we may write

(2.3) $S_{i}=FW_{1}FW_{2}\cdots FW_{i}=FW_{1}FW_{1}Y_{1}FW_{1}Y_{1}Y_{2}\cdots
FW_{1}Y_{1}Y_{2}\cdots Y_{i-1},$

which clearly reduces to $FW_{i}$, and in turn to $PW_{i}$ and $QW_{i}$. To
get the words from the second part of the union (2.2), just write
$S_{i}=S_{i-1}FW_{i}$ and apply the induction.

To prove the statement of (2.2) we apply the induction. The first word
$S_{1}=FW_{1}$ can be written as $S_{1}=F^{\prime}\mathtt{xy}W_{1}^{\prime}$
and we see that the word $\mathtt{xy}$ occurs only once in $S_{1}$. Hence,
there are no squares in $S_{1}$ except those contained in $F$ and therefore
$\mathcal{R}(S_{1})=\\{PW_{1},QW_{1}\\}$, as asserted in (2.2). Similarly, the
word $S_{2}=FW_{1}FW_{2}$ can be written as
$S_{2}=FW_{1}^{\prime\prime}\mathtt{yx}F^{\prime\prime}W_{2}$ and we see that
the word $\mathtt{yx}$ occurs only once in $S_{2}$. Hence, there are no other
squares in $S_{2}$ beyond those contained entirely in $FW_{1}$ and $FW_{2}$,
and the square $FW_{1}FW_{1}$. Since $P$ is a suffix of $Q$, the only possible
new reduct is $PW_{1}QW_{2}$.

Now, we shall analyze possible square reductions in the word
$S_{3}=FW_{1}FW_{2}FW_{3}$. The only essential case is when a square overlaps
all three words $W_{1},W_{2},W_{3}$. Notice that it cannot entirely contain
any two of them since they all have different lengths. So, the only
possibility is that $S_{3}=FW_{1}^{\prime}XFYXFYW_{3}^{\prime}$, where
$W_{1}=W_{1}^{\prime}X$, $W_{2}=YX$ and $W_{3}=YW_{3}^{\prime}$. Deleting the
block $XFY$ gives $FW_{1}^{\prime}XFYW_{3}^{\prime}=FW_{1}FW_{3}$. Thus, we
see that such reductions cannot produce anything new beyond words presented in
(2.2).

For the general case, notice that any square reduction in $S_{i}$ either takes
place in some factor $FW_{j}FW_{j+1}$, or must delete one word $W_{j}$
(remember that no square may contain entirely any two of the words $W_{j}$).
In the later case we obtain a word with the smaller number of words $W_{j}$,
which completes the proof by the induction. ∎

Notice that the construction of words $S_{i}$ from the above proof actually
shows that for every $k\geqslant 1$, there exist infinitely many words over a
$4$-letter alphabet, each with exactly $k$ distinct reducts.

Our next theorem gives an exponential lower bound for the function $f_{4}(n)$
(better than the one following trivially from Theorem 2). We will need the
following simple lemma.

######  Lemma 4.

Let $W=a_{1}a_{2}\dots a_{n}$ be any square-free word, where each $a_{i}$ is a
single letter. Let $V=a_{1}^{k_{1}}a_{2}^{k_{2}}\dots a_{n}^{k_{n}}$, where
each $k_{i}$ is a positive integer. Then every square in $V$ is of the form
$x^{2k}$, where $x=a_{i}$ for some $i=1,2,\dots,n$.

###### Proof.

Let $XX$ be a square in the word $V$ and assume that $X$ contains at least two
distinct letters. Let $X_{0}$ be the word obtained from $X$ by reducing all
single letter repetitions. We have two possibilities: the first and the last
letter of $X_{0}$ are the same, or they are different. In the later case, the
square $X_{0}X_{0}$ is contained in $W$, a contradiction. In the former case,
the square $X_{0}^{\prime}X_{0}^{\prime}$ is contained in $W$, where
$X_{0}^{\prime}$ is obtained from $X_{0}$ by erasing the last letter. This
proves the lemma. ∎

######  Theorem 4.

Let $U$ be a word over alphabet $\\{\mathtt{a,b,x}\\}$ starting and ending
with the letter $\mathtt{x}$. Let $\alpha=r(U)^{\frac{1}{\lvert U\rvert+5}}$.
Then there exists a constant $c>0$ such that $f_{4}(n)\geqslant c\alpha^{n}$,
for all $n\in\mathbb{N}$.

###### Proof.

Let $S$ be any infinite square-free word over alphabet $\\{\mathtt{a,b,y}\\}$
starting with the letter $\mathtt{y}$. Let $T$ be a word obtained form $S$ by
duplicating every occurrence of the letter $\mathtt{y}$ in $S$, except the
first one. Hence, the word $T$ can be written uniquely as
$T=T_{1}T_{2}T_{3}\cdots$, where each factor $T_{i}$ starts and ends with the
letter $\mathtt{y}$, and these are the only occurrences of this letter in
$T_{i}$. Finally, let us define $V_{j}=UT_{1}UT_{2}\cdots UT_{j}$, for each
$j\geqslant 1$.

We claim that $r(V_{j})=r(U)^{j}$, for every $j\geqslant 1$. Indeed, there are
exactly $j$ copies of $U$ in $V_{j}$ and each copy can be reduced to $r(U)$
distinct reducts. Moreover, there are no other squares in $V_{j}$ than those
entirely contained in copies of $U$. To see this, suppose that $XX$ is a
square intersecting some factors $T_{i}$. Then the word obtained from $XX$ by
erasing all letters from the copies of $U$ must have the form of a square, say
$X^{\prime}X^{\prime}$. This square is contained in the word $T$ and has at
least two distinct letters, which contradicts Lemma 4.

To finish the proof, just notice that each word $T_{i}$ has length at most
$5$, thus, $\lvert V_{j}\rvert\leqslant j(\lvert U\rvert+5)$. In consequence,
we have

$r(V_{j})=r(U)^{j}\geqslant(r(U)^{\frac{1}{\lvert U\rvert+5}})^{\lvert
V_{j}\rvert}=\alpha^{\lvert V_{j}\rvert}.$

This completes the proof (with $c=1$) for $n=\lvert V_{j}\rvert$. For the
intermediate values of $n\in(\lvert V_{j}\rvert,\lvert V_{j+1}\rvert)$, notice
that $f_{4}(n)$ is at least $r(V_{j})$, as we may append sufficiently many
letters $\mathtt{y}$ to the word $V_{j}$ to get a word with the same number of
reducts as $V_{j}$. Since ${\lvert V_{i+1}\rvert}-{\lvert
V_{i}\rvert}\leqslant{\lvert U\rvert}+5$, we may take $c=\alpha^{-(\lvert
U\rvert+5)}$ to get the asserted inequality for all $n\in\mathbb{N}$. ∎

One may check that the word $U=\mathtt{xabaxababxbabx}$ satisfies $r(U)=4$ and
$\lvert U\rvert=14$. Hence, in the above theorem we may take
$\alpha=4^{\frac{1}{19}}\approx 1.075$.

###  2.3. Kinship of words

For a fixed integer $k\geqslant 1$, let us consider the directed graph
${\overrightarrow{\mathcal{G}}}_{k}$ defined on the set of all finite non-
empty words over an alphabet of size $k$, with $U$ joined to $W$ by an
oriented edge $(U,W)$ whenever $W$ can be obtained from $U$ in a single square
reduction. Let ${\mathcal{G}}_{k}$ denote the underlying _undirected_ graph
obtained from ${\overrightarrow{\mathcal{G}}}_{k}$ by ignoring orientations of
the edges.

One may ask many natural questions about these graphs. Perhaps the most
fundamental concerns connectedness of ${\mathcal{G}}_{k}$. By Proposition 1,
it is easy to see that ${\mathcal{G}}_{2}$ has exactly six different
components. Indeed, there are exactly six square-free words over a binary
alphabet and every binary word reduces to exactly one of them. As there are
infinitely many square-free words over a $3$-letter alphabet, one may expect
that the number of components in ${\mathcal{G}}_{3}$ is also infinite.
However, we shall demonstrate that this is not the case.

######  Theorem 5.

The graph ${\mathcal{G}}_{3}$ has finitely many connected components.

###### Proof.

First we observe that every square-free word over alphabet
$\\{\mathtt{a,b,c}\\}$ of length exactly $9$ contains as a factor one of the
following five words (up to a permutation of the alphabet):

(2.4)
$X_{1}=\mathtt{abcabac},X_{2}=\mathtt{abcacba},X_{3}=\mathtt{abcbabc},X_{4}=\mathtt{abcbacab},X_{5}=\mathtt{abcbacb}.$

These words are reducts of the following five words, respectively:

$S_{1}=\mathtt{abcbabcbcacbcacabacabcbacabcabacacbcabacac}$

$S_{2}=\mathtt{abcbabcbcacbcabacbcabcbacbcabcacbcbabcba}$

$S_{3}=\mathtt{abcbabcbcacbcacabacabcbabcbc}$

$S_{4}=\mathtt{abcbabcbcacbcacabacabcbacabcabacacbcacbacab}$

$S_{5}=\mathtt{abcbabcbcacbcabacbcabcbacbcabcacbabcacbcb}$.

Now, it can be checked that each word $S_{i}$ has another reduct $Y_{i}$,
which is strictly shorter than the corresponding word $X_{i}$:

(2.5)
$Y_{1}=\mathtt{abcbac},Y_{2}=\mathtt{abcba},Y_{3}=\mathtt{abc},Y_{4}=\mathtt{abcab},Y_{5}=\mathtt{abcacb}.$

It follows that for every ternary word $W$ there is a path in the graph
${\mathcal{G}}_{3}$ to some square-free word of length at most $8$. Indeed,
suppose that $W$ has no reducts of length at most $8$. If $R=AX_{i}B$ is any
reduct of $W$, then we may go up to the word $R^{\prime}=AS_{i}B$, and then go
down to the shorter word $R^{\prime\prime}=AY_{i}B$. After a finite number of
such operations we must reach a word of length smaller than $9$.

We see that, in consequence, the number of connected components in the graph
${\mathcal{G}}_{3}$ does not exceed the number of square-free ternary words of
length at most $8$, which completes the proof. ∎

##  3\. Discussion

Let us conclude the paper with some observations and open problems. First, let
us point on a strange phenomenon concerning possible numbers of reducts of
ternary words. We checked by a computer that for every $m\leqslant 79$, there
exist ternary words $W$ with $|\mathcal{R}(W)|=m$. However, it seems that
there is no ternary word having exactly $80$ reducts (see Table 1).

######  Problem 1.

Is there a ternary word $W$ with $|\mathcal{R}(W)|=80$?

Other missing values up to $120$ are:

$95,97,101,102,104,105,107,117,119,$

and it looks like these numbers become more and more frequent. For instance,
we have not found words having the number of reducts in the interval from
$182$ up to $192$.

######  Conjecture 1.

There exist infinitely many positive integers $m$ such that no ternary word
have exactly $m$ distinct reducts.

Of course, we have examined only words of some bounded length. So, it may
potentially happen that every missing value is eventually realized by some
very long word. Let us stress, however, that actually we do not have a proof
that any single value is really missing.

$W$ | $|W|$ | $|\mathcal{R}(W)|$
---|---|---
$\mathtt{abcbabcbc}$ | $9$ | $2$
$\mathtt{abcbabcbcacbcabcb}$ | $17$ | $3$
$\mathtt{abcbabcbcacbca}$ | $14$ | $4$
$\mathtt{abcbabcbcacbcabacbcabcb}$ | $23$ | $5$
… | … | …
$\mathtt{abcbabcbcacbcacabacabcbabcbcacbcabacababcbabcacbabcabc}$ | $54$ | $79$
$\mathtt{abcbabcbcacbcacabacabcbacabcabacacbcacbabcbcacbca}$ | $49$ | $81$
Table 1. Words with growing number of reducts

Many natural question can be asked about the structure of graphs
${\overrightarrow{\mathcal{G}}}_{k}$. For instance, how long is a shortest
directed path from a word $W$ to some of its reducts? This is the same as the
minimum number of single square reductions needed to turn $W$ into a square-
free word. Let us denote this parameter by $d(W)$, and let $d_{k}(n)$ denote
the maximum value of $d(W)$ over all words of length $n$ over a $k$-letter
alphabet.

These parameters for $k=2$ were introduced and studied by Alon, Bruck,
Farnoud, and Jain in [2] under the name of the _duplication distance_. Among
many interesting results, it is proved in [2] that the limit
$\lim_{n\rightarrow\infty}\frac{d_{2}(n)}{n}$ exists and satisfies the
following inequalities:

$0.045\leqslant\lim_{n\rightarrow\infty}\frac{d_{2}(n)}{n}\leqslant 0.4.$

It would be nice to investigate this quantity for larger alphabets, in
particular for $k=3$.

######  Conjecture 2.

For every $k\geqslant 2$, the limit
$\lim_{n\rightarrow\infty}\frac{d_{k}(n)}{n}$ exists.

It is not hard to demonstrate that if any of the above limits exist, then it
must be strictly positive.

Another parameter one could study in this topic is the out-degree of a vertex
in the graph ${\overrightarrow{\mathcal{G}}}_{k}$. This is the same as the
number of words that can be obtained from a given word $W$ in a single square
reduction. Let us denote this quantity by $\deg^{+}(W)$, and let
$\deg_{k}^{+}(n)$ be the maximum value of $\deg^{+}(W)$ over all words of
length $n$ over a $k$-letter alphabet.

######  Conjecture 3.

For every $k\geqslant 2$, we have $\deg_{k}^{+}(n)\leqslant n$.

This problem resembles one of the most famous conjectures in Combinatorics on
Words, made by Fraenkel and Simpson [6], stating that every word of length $n$
contains at most $n$ _distinct_ squares. Let us point however, that reduction
of the same square in a word may give different results, as well as reduction
of distinct squares may give the same word.

Finally, it would be nice to know if Theorem 5 holds for every $k\geqslant 2$.
The following Conjecture seems plausible.

######  Conjecture 4.

For every $k\geqslant 2$, the graph $\mathcal{G}_{k}$ has finitely many
connected components.

## References

  * [1] J.-P. Allouche, J. Shallit. Automatic Sequences. Theory, Applications, Generalizations, Cambridge University Press, Cambridge, 2003.
  * [2] N. Alon, J. Bruck, F. Farnoud, S. Jain, N. Alon, J. Bruck, F. F. Hassanzadeh, and S. Jain, Duplication distance to the root for binary sequences, IEEE Trans. Inf. Theory, 63 (2017) 7793–7803.
  * [3] D. R. Bean, A. Ehrenfeucht, G. F. McNulty, Avoidable patterns in strings of symbols, Pacific J. Math. 85 (1979) 261–294.
  * [4] J. Berstel, Axel Thue’s papers on repetitions in words: a translation, Publications du LaCIM, vol. 20, Université du Québec a Montréal, 1995.
  * [5] J. Berstel, D. Perrin, The origins of combinatorics on words, Europ. J. Combin. 28 (2007) 996–1022.
  * [6] A. S. Fraenkel, J. Simpson, How many squares can a string contain?, J. Combin. Theory, Ser. A, 82 (1998) 112–120.
  * [7] J. Grytczuk, Thue type problems for graphs, points, and numbers. Discrete Math. 308 (2008) 4419–4429.
  * [8] P. Leupold, C. Martín-Vide, V. Mitrana. Uniformly bounded duplication languages, Discrete Applied Mathematics, 146 (2005) 301–310.
  * [9] M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading, MA, 1983.
  * [10] M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press, Cambridge, UK, 2002.
  * [11] J. Nešetřil, P. Ossona de Mendez, Sparsity, Springer, 2012.
  * [12] S. Ohno, Evolution by gene duplication, Springer, 1970.
  * [13] A. M. Shur, Growth properties of power-free languages, Computer Sci. Rev. 6 (2012) 187–208.
  * [14] A. Thue, Über unendliche Zeichenreichen, Norske Vid. Selsk. Skr., I Mat. Nat. Kl., Christiania 7 (1906) 1–22.
  * [15] J. Zhang, Evolution by gene duplication: an update, Trends in Ecology and Evolution, 18 (2003) 292–298.


denotes the average of $f$ over $\mathbb{S}^{k}$.

######  Lemma 6.8.

Let $\omega$ be the overlap of $\ket{\psi}$ with the closest product state as
defined in Theorem 6.1. If $\rho=\operatorname{Tr}_{1}(\ket{\psi}\bra{\psi})$
was the reduced density matrix of $\ket{\psi}$, then

$\omega^{2}\leq\operatorname{Tr}(\rho^{2})\leq\omega.$

###### Proof.

Let $\lambda_{1}\geq\lambda_{2}\geq\dots\geq\lambda_{d}$ be the eigenvalues of
$\rho$. Then [HM13, Lemma 2] shows that $\omega=\lambda_{1}.$ Therefore, since
$\sum_{i=1}^{d}\lambda_{i}=1$ and each $\lambda_{i}$ is non-negative, we have

$\lambda_{1}^{2}\leq\operatorname{Tr}(\rho^{2})=\sum_{i=1}^{d}\lambda_{i}^{2}\leq\sum_{i=1}^{d}\lambda_{1}\lambda_{i}=\lambda_{1}.$

∎

######  Theorem 6.9.

Let $S\subseteq\mathbb{C}^{d}\otimes\mathbb{C}^{d}$ be a Haar-random subspace
of dimension $s$, and let $\ket{\psi}\in S$ and let $C$ be the constant from
Levy’s Lemma. Then

  1. 1.

For all constant $\delta>0$, if $d\geq\frac{4}{\delta}$ and
$s\leq\frac{C\delta^{2}}{1024\log(\frac{40}{\delta})}d^{2},$ then all states
in $S$ have purity at most $\delta$ with high probability. In particular,

$\Pr_{\ket{\psi}\in
S}[\omega_{\ket{\psi}}\geq\sqrt{\delta}]\leq\exp(-O(d^{2})).$

  2. 2.

For all constant $\delta>0,$ if $s\geq 2\sqrt{\delta}d^{2}$, then $S$ contains
a state with overlap with the closest product state $\delta$ with high
probability. In particular,

$\Pr_{\ket{\psi}\in S}[\sup_{\ket{\psi}\in
S}\omega_{\ket{\psi}}\leq\delta]\leq\exp(-O(d^{2})).$

###### Proof.

To show the first part, let $f(\ket{\psi})=\operatorname{Tr}(\rho^{2})$ denote
the purity of the reduced density matrix of $\ket{\psi}$ on the first
$\mathbb{C}^{d}$ factor. The Lipschitz constant of $f$ is $4$ by [HLW06, Lemma
III.8].

Let $P$ be a fixed projector onto the first $s$ basis states (according to
some canonical ordering) of $\mathbb{C}^{d}\otimes\mathbb{C}^{d}$, and $U$ is
a Haar-random unitary on $\mathbb{C}^{d}\otimes\mathbb{C}^{d}$. Let
$\mathcal{N}$ denote an $\epsilon$-net for the image of the projector $P$ of
size $(5/\epsilon)^{2s}$, which exists by [HLW06, Lemma III.6]. Note that
$U\mathcal{N}$ is an $\epsilon$-net for the image of the projector
$P_{S}=UPU^{*}$, which is a uniformly random subspace of dimension $s$ when
$U$ is choosen to be Haar-random.

We want to bound the probability that there exists a state $\ket{\psi}\in S$
whose purity is large.

$\displaystyle\Pr\Big{(}\exists\,\ket{\psi}\in S\,\text{ such that
}f(\ket{\psi})\geq\delta\Big{)}$
$\displaystyle\leq\Pr\Big{(}\exists\,\ket{\varphi}\in U\mathcal{N}\,\text{
such that }f(\ket{\varphi})\geq\delta-4\epsilon\Big{)}$
$\displaystyle\leq\sum_{\ket{\phi}\in\mathcal{N}}\Pr\Big{(}f(U\ket{\phi})\geq\delta-4\epsilon\Big{)}$
$\displaystyle=\Big{(}\frac{5}{\epsilon}\Big{)}^{2s}\cdot\Pr_{\ket{\phi}\sim\text{Haar}(d^{2})}\Big{(}f(\ket{\phi})\geq\delta-4\epsilon\Big{)}.$

On average, the purity of a Haar-random state in
$\mathbb{C}^{d}\otimes\mathbb{C}^{d}$ is $\beta:=2d/(d^{2}+1)$ by [CN16,
Proposition 4.14].

Thus by Levy’s Lemma we have that

$\Pr_{\ket{\phi}\sim\text{Haar}(d^{2})}\Big{(}f(\ket{\phi})\geq\delta-4\epsilon\Big{)}\leq
2\exp\Big{(}-\frac{C}{16}(d^{2}+1)(\delta-4\epsilon-\beta)^{2}\Big{)}$

where $C$ was the constant from Lemma 6.7. Now choosing
$\epsilon=\frac{\delta}{8}$ and $d$ sufficiently large so that
$\frac{1}{d}\leq\frac{2d}{d^{2}+1}\leq\frac{\delta}{4},$ we have

$\displaystyle\Pr\Big{(}\exists\,\ket{\psi}\in S\,\text{ such that
}f(\ket{\psi})\geq\delta\Big{)}$ $\displaystyle\leq
2\Big{(}\frac{40}{\delta}\Big{)}^{2s}\exp\Big{(}-\frac{C}{16}(d^{2}+1)(\frac{\delta}{4})^{2}\Big{)}$
$\displaystyle=2\exp\Big{(}-\frac{C}{256}(d^{2}+1)\delta^{2}+2s\log(\frac{40}{\delta})\Big{)}$

by combining the above bounds. Hence the claimed choice of $s$ makes this
probability exponentially small in $d^{2}$. Furthermore, by Lemma 6.8, we have
$\Pr[\operatorname{Tr}(\rho^{2})\geq\delta]\geq\Pr[\omega_{\ket{\psi}}\geq\sqrt{\delta}]$,
and hence the probability that the overlap with a product state is at least
$\sqrt{\delta}$ is exponentially small.

To show the second part, fix a product state
$\ket{v}=\ket{a}\otimes\ket{b}\in\mathbb{C}^{d}\otimes\mathbb{C}^{d}$. The
overlap between $\ket{v}$ and the subspace $S$ is captured by the quantity

$f(U)=\bra{v}P_{S}\ket{v}=\bra{v}UPU^{*}\ket{v}~{}.$

Equivalently, the overlap is

$f(\ket{\psi})=\bra{\psi}P\ket{\psi}$

where $\ket{\psi}$ is a Haar-random state since $\ket{v}$ was a fixed vector.
The average of $f(\ket{\psi})$ can be computed as

$\int
f(\ket{\psi}\,\mathrm{d}\ket{\psi}=\operatorname{Tr}\Big{(}P\,\int\ket{\psi}\bra{\psi}\,\mathrm{d}\ket{\psi}\Big{)}=\frac{1}{d^{2}}\operatorname{Tr}(P)=\frac{s}{d^{2}}~{}.$

We compute the Lipschitz constant of $f$ since $P$ is a projector:

$\displaystyle\sup_{\ket{\psi},\ket{\varphi}}\frac{|f(\ket{\psi})-f(\ket{\varphi})|}{\|\ket{\psi}-\ket{\varphi}\|}$
$\displaystyle=\sup_{\ket{\psi},\ket{\varphi}}\frac{\Big{|}\|P\ket{\psi}\|^{2}-\|P\ket{\varphi}\|^{2}\Big{|}}{\|\ket{\psi}-\ket{\varphi}\|}$
$\displaystyle=\sup_{\ket{\psi},\ket{\varphi}}\frac{\Big{|}\|P\ket{\psi}\|+\|P\ket{\varphi}\|\Big{|}\cdot\Big{|}\|P\ket{\psi}\|-\|P\ket{\varphi}\|\Big{|}}{\|\ket{\psi}-\ket{\varphi}\|}$
$\displaystyle\leq\sup_{\ket{\psi},\ket{\varphi}}\frac{2\Big{|}\|P\ket{\psi}\|-\|P\ket{\varphi}\|\Big{|}}{\|\ket{\psi}-\ket{\varphi}\|}$
$\displaystyle\leq\sup_{\ket{\psi},\ket{\varphi}}\frac{2\|P(\ket{\psi}-\ket{\varphi})\|}{\|\ket{\psi}-\ket{\varphi}\|}$
$\displaystyle\leq 2~{}.$

We now apply Levy’s Lemma to conclude that

$\Pr\Big{(}f(\ket{\psi})<\frac{s}{d^{2}}-\delta\Big{)}\leq
2\exp\Big{(}-\frac{C}{4}(d^{2}+1)\delta^{2}\Big{)}$

Hence as long as $s\geq 2\sqrt{\delta}d^{2},$ we have for
$\ket{w}=P_{S}\ket{v},$

$\displaystyle\Pr[|\langle v|w\rangle|^{2}\geq\delta]$
$\displaystyle=\Pr[|\langle v|w\rangle|\geq\sqrt{\delta}]=1-\Pr[|\langle
v|w\rangle|\leq\sqrt{\delta}]$ $\displaystyle\geq 1-\Pr[|\langle
v|w\rangle|\leq\frac{s}{d^{2}}-\sqrt{\delta}]$ $\displaystyle\geq
1-2\exp\Big{(}-\frac{C\delta}{4}(d^{2}+1)\Big{)}$

and therefore $S$ contains a state with overlap at least $\delta$ with
probability 1 - $\exp(-O(d^{2})).$ ∎

We note that the above bounds in Theorem 6.9 are likely not tight, and finding
tight bounds would be an interesting open problem. However, we are also now
able to show Proposition 1.15 and Proposition 1.16 using this result.

See 1.15

###### Proof.

Clearly in the yes case, the subspace $S$ contains a product state. Otherwise,
given $\epsilon>0$, choosing $\delta=(1-\epsilon^{2})^{2}$ in Theorem 6.9 (1)
implies that there is some constant $C$ such that a Haar-random subspace of
dimension $s\leq Cd^{2}$ is $\epsilon$-completely entangled. Hence setting
choosing any $s$ in this range gives a no instance with probability at least
$1-\exp(-O(d^{2})).$ ∎

See 1.16

###### Proof.

Let $a<b$ be the two parameters in the Entangled Subspace problem where yes
instances have a state that is $a$-close to product and otherwise no instances
are $b$-completely entangled. Choose $C_{1}$ using $\delta=(1-b^{2})^{2}$ from
Theorem 6.9 (1), and $C_{2}$ using $\delta=1-a^{2}$ from Theorem 6.9 (2). Then
with probability at least $1-\exp(-O(d^{2})),$ a Haar-random subspace of
dimension $\leq C_{1}t^{2}$ is $b$-completely entangled, and a subspace of
dimension $\geq C_{2}t^{2}$ contains a state that is $a$-close to a product
state. ∎

Hence, having observed that our average-case problems can be reduced to the
Entangled Subspace problem with overwhelming probability, we use our results
from Section 6.1 to show that they can be solved by a $\mathsf{QMA(2)}$ tester
with high probability. Furthermore, we conjecture that a lower bound for a
$\mathsf{QMA}$ tester for the Entangled Subspace problem extends to this
average case setting.

###  6.5 Connections to Invariant Theory

Observe that all of our candidate problems, being special cases of the
Entangled Subspace problem, have local unitary symmetries. This follows from
product states being preserved under local unitary transformations, and the
unitary invariance of the trace distance.

This opens up the possibly of using the generalized polynomial method to prove
a $\mathsf{QMA}$ lower bound for our candidate problems. While these problems
are similar in spirit to the entanglement entropy problem that also has a
local unitary symmetry introduced in Section 5, the main barrier to applying
the polynomial method in this case is that we do not appear to have a good
characterization of the invariant polynomials in Footnote 6 in the case where
$P$ is a projector onto a high-dimensional subspace. While Theorem 5.2
characterizes these polynomials in the case where $P$ is a one-dimensional
projector, we have seen in the previous section that one-dimensional
properties cannot be used to separate $\mathsf{QMA}$ and $\mathsf{QMA(2)}.$ We
are not aware of a good characterization of these invariants even in the case
where $P$ is a projector onto a two-dimensional subspace. A deeper
understanding of these invariants appears necessary to make further progress
on these questions.

###  6.6 $\mathsf{QCMA}$ Lower Bound for the Entangled Subspace Problem

As described in the previous section, we are not currently able to prove a
strong $\mathsf{QMA}$ lower bound on the query complexity of the entangled
subspace problem. However, using a similar proof strategy as Aaronson and
Kuperberg in [AK07], we show a lower bound against QCMA, which is the subclass
of $\mathsf{QMA}$ of problems verifiable by a polynomial time quantum verifier
with a classical proof string.

To present this lower bound, we first recall the definition of a $p$-uniform
measure over quantum states from [AK07].

######  Definition 13.

Let $\mu$ be the Haar measure over $n$-dimensional sphere $\mathbb{S}^{n}$. A
measure $\sigma$ is $p$-uniform if it can be obtained from $\mu$ by
conditioning on an event $A$ with measure $\mu(A)\geq p.$

Using Lévy’s lemma, we can observe the following property of $p$-uniform
measures.

######  Lemma 6.10.

Let $f(\ket{\psi}):\mathbb{S}^{d}\rightarrow\mathbb{R}$ be a non-negative,
Lipschitz function on the sphere bounded by 1. Let
$\operatorname{\mathop{\mathbb{E}}}_{\mu}[f]$ be its expectation over the Haar
measure. Then if $\sigma$ is a $p$-uniform measure, then

$\operatorname{\mathop{\mathbb{E}}}_{\sigma}[f]\leq\operatorname{\mathop{\mathbb{E}}}_{\mu}[f]+O\left(\sqrt{\frac{\log\frac{1}{p}+\log
d}{d}}\right).$

###### Proof.

Let $\bar{f}=\mathbb{E}_{\mu}[f]$, $X=f(\ket{\psi}),$ and $a>0.$ By the
definition of $p$-uniform measure, we have

$\Pr_{\sigma}[|X-\bar{f}|\geq a]\leq\frac{1}{p}\Pr_{\mu}[|X-\bar{f}|\geq a],$

and by Lévy’s lemma there exists a constant $C$ such that,

$\Pr_{\mu}[|X-\bar{f}|\geq a]\leq 2\exp(-Cda^{2}).$

Hence, for every $a>0$, we get

$\operatorname{\mathop{\mathbb{E}}}_{\sigma}[f]\leq(\bar{f}+a)\Pr_{\sigma}[|X-\bar{f}|\leq
a]+\Pr_{\sigma}[|X-\bar{f}|\geq a]\leq\bar{f}+a+\frac{2}{p}\exp(-Cda^{2}).$

To minimize the expectation, we choose $a=\sqrt{\frac{\log\frac{2}{p}+\log
d}{Cd}}=O\left(\sqrt{\frac{\log\frac{1}{p}+\log d}{d}}\right).$ This choice of
$a$ ensures that $\frac{2}{p}\exp(-Cda^{2})=\frac{2}{d}\leq\sqrt{\frac{\log
d}{d}}\leq a$ for sufficiently large $d$. Hence,

$\mathbb{E}_{\sigma}[f]\leq\bar{f}+O(a)=\mathbb{E}_{\mu}[f]+O\left(\sqrt{\frac{\log\frac{1}{p}+\log
d}{d}}\right).$

∎

We also require the following observation about the Haar measure.

######  Lemma 6.11.

Let $\ket{\theta}$ be a Haar random state in $\mathbb{C}^{d}$. For every
density matrix $\rho$ on $\mathbb{C}^{d}\otimes\mathbb{C}^{d}$, we have

$\operatorname{\mathop{\mathbb{E}}}_{\ket{\theta}}[\operatorname{Tr}(|\theta\rangle\langle\theta|^{\otimes
2}\rho)]\leq\frac{2}{d(d+1)}.$

.

###### Proof.

Since
$\operatorname{\mathop{\mathbb{E}}}[|\theta\rangle\langle\theta|^{\otimes
2}]=\frac{2\Pi}{d(d+1)}$ where $\Pi$ is the projector onto the symmetric
subspace of $\mathbb{C}^{d}\otimes\mathbb{C}^{d}$, then for any density matrix
$\rho:$

$\operatorname{\mathop{\mathbb{E}}}_{\ket{\theta}}[\operatorname{Tr}(|\theta\rangle\langle\theta|^{\otimes
2}\rho)]=\frac{2}{d(d+1)}\operatorname{Tr}(\Pi\rho)\leq\frac{2}{d(d+1)}.$

∎

We are now ready to prove the lower bound. In fact, we will prove the lower
bound on the average case version of the Entangled Subspace problem, which is
the Planted Product State problem, introduced in the previous sections. In
this section, we modify the definition of the problem to ensure that the
planted product state is always a symmetric state $\ket{\theta}^{\otimes 2}$.
However, the modified problem is clearly also a special case of the Entangled
Subspace problem.

######  Theorem 6.12.

Any quantum algorithm solving the Planted Product State problem using $T$
queries and an $m$-bit classical witness must use

$T\geq\Omega\left(\sqrt[4]{\frac{d}{m+\log d}}\right)$

queries to the oracle.

###### Proof.

We apply the hybrid method variant introduced in [AK07]. Let $O_{1}$ be the
entangled oracle and $O_{2}=O_{1}-2|\theta\rangle\langle\theta|^{\otimes 2}$
be the oracle with a hidden product state $\ket{\theta}^{\otimes 2}$, given
$\ket{\theta}\in\mathbb{C}^{d}$.

Suppose we have a quantum algorithm $A$ that solves the Planted Product State
problem with $T$ queries with the help of an $m$-bit classical witness. For
each $\ket{\theta},$ fix the string $w$ that maximizes the probability that
algorithm accepts $O_{2}$. Let $S(w)\subseteq S^{d}$ be the set of states
associated with witness string $w$. Since $S(w)$ form a partition, then there
must be one set $S(w^{*})$ with measure at least $\frac{1}{2^{m}}$.

Let $\sigma$ be the uniform measure over $S(w^{*})$. Hence, fix $w^{*}$ as the
witness in the algorithm, and choose $O_{2}$ where $\ket{\theta}$ is selected
from $\sigma$. We claim that the algorithm still requires a large number of
queries $T$ to distinguish between oracles $O_{1}$ and $O_{2}$ in this case.
To establish the lower bound, let $\ket{\psi_{t}}$ be the result of the
algorithm $A$ with oracle $O_{2}$ applied $t$ times followed by oracle $O_{1}$
applied $T-t$ times. By [AK07], We can bound the difference in Euclidean norm
between successive hybrids by:

$\|\ket{\psi_{t+1}}-\ket{\psi_{t}}\|_{2}\leq\sqrt{\operatorname{Tr}((O_{1}-O_{2})^{*}(O_{1}-O_{2})\rho_{t})}=2\sqrt{\operatorname{Tr}(|\theta\rangle\langle\theta|^{\otimes
2}\rho_{t})},$

where $\rho_{t}$ is the marginal state of the query register before the
$t^{th}$ query since $O_{1}-O_{2}=2|\theta\rangle\langle\theta|^{\otimes 2}$.
Hence, the Cauchy-Schwartz inequality implies that over a randomly selected
$\ket{\theta}$ from $\sigma$:

$\operatorname{\mathop{\mathbb{E}}}_{\sigma}[\|\ket{\psi_{t+1}}-\ket{\psi_{t}}\|_{2}]\leq
2\sqrt{\operatorname{\mathop{\mathbb{E}}}_{\sigma}[\operatorname{Tr}(|\theta\rangle\langle\theta|^{\otimes
2}\rho_{t})]}.$

Since $\sigma$ is $2^{-m}$-uniform, and the function
$f(\ket{\psi})=\operatorname{Tr}(|\psi\rangle\langle\psi|^{\otimes 2}\rho)$ is
a non-negative, bounded, Lipschitz function, then we can bound by Lemma 6.10
and Lemma 6.11 that:

$\begin{split}\operatorname{\mathop{\mathbb{E}}}_{\sigma}[\operatorname{Tr}(|\theta\rangle\langle\theta|^{\otimes
2}\rho_{t})]&\leq\operatorname{\mathop{\mathbb{E}}}_{\mu}[\operatorname{Tr}(|\theta\rangle\langle\theta|^{\otimes
2}\rho_{t})]+O\left(\sqrt{\frac{m+\log d}{d}}\right)\\\
&\leq\frac{2}{d(d+1)}+O\left(\sqrt{\frac{m+\log d}{d}}\right)\\\ &\leq
O\left(\sqrt{\frac{m+\log d}{d}}\right),\end{split}$

since $\frac{2}{d^{2}}\leq\sqrt{\frac{\log d}{d}}$ for sufficiently large $d$.
Hence,

$\operatorname{\mathop{\mathbb{E}}}_{\sigma}[\|\ket{\psi_{t+1}}-\ket{\psi_{t}}\|_{2}]\leq
2\sqrt{\operatorname{\mathop{\mathbb{E}}}_{\sigma}[\operatorname{Tr}(|\theta\rangle\langle\theta|^{\otimes
2}\rho_{t})]}\leq O\left(\sqrt[4]{\frac{m+\log d}{d}}\right).$

Hence, if $\ket{\psi_{0}}$ was the final state where all oracle calls were to
$O_{1},$ and $\ket{\psi_{T}}$ was the final state where all oracle calls were
to $O_{2},$ then the triangle inequality implies that

$\operatorname{\mathop{\mathbb{E}}}_{\sigma}[\|\ket{\psi_{T}}-\ket{\psi_{0}}\|_{2}]\leq
O\left(T\sqrt[4]{\frac{m+\log d}{d}}\right).$

If the algorithm $A$ correctly distinguishes between the two cases, then
$\operatorname{\mathop{\mathbb{E}}}_{\sigma}[\|\ket{\psi_{T}}-\ket{\psi_{0}}\|_{2}]=\Omega(1).$
Hence the number of queries $T$ satisfies

$T\geq\Omega\left(\sqrt[4]{\frac{d}{m+\log d}}\right)$

. ∎

In particular, this bound shows that a polynomial sized classical witness is
not sufficient to help a quantum verifier solve the Entangled Subspace Problem
efficiently, since any quantum verifier that solves the Entangled Subspace
problem can also be used to solve the Planted Product State problem.

##  7 Open Questions

We end by describing some open problems and future directions.

##### Strong $\mathsf{QMA}$ Lower Bounds for the Entangled Subspace Problem.

Can one show that any $\mathsf{QMA}$ tester for the Entangled Subspace problem
requires either a superpolynomial number of queries, or a superpolynomial
sized witness? This would yield a (quantum) oracle separation between
$\mathsf{QMA}$ and $\mathsf{QMA(2)}$, and in particular would rule out the
existence of so-called “disentanglers” [ABD+08].

##### Better Query Upper Bounds.

Are the bounds proven using the generalized polynomial method tight? In
particular, the following gaps remain:

  * •

We have shown that there is a $O(\frac{t\sqrt{d}}{\epsilon})$ upper bound and
a $\Omega(\max(\frac{t}{\epsilon},\sqrt{d}))$ lower bound in the
$\mathsf{BQP}$ setting for the recurrence problem and used this bound to prove
a similar lower bound in the $\mathsf{QMA}$ setting. Is there a better lower
or upper bound in either the $\mathsf{BQP}$ or $\mathsf{QMA}$ settings?
However, a more sophisticated symmetrization technique may be required to
improve the lower bound.

  * •

We expect the $\mathsf{BQP}$ lower bound in Theorem 1.8 for the entanglement
entropy can be improved by using a more creative application of the polynomial
method.

##### Improving Proposition 6.6.

Is the counterexample of Proposition 6.6 tight, in the sense that there are no
examples that fool the verifier in dimensions 2, 3, 4, or 5? Otherwise, if
there was an example that fools the verifier in dimension 2, this would give
additional evidence that the Entangled Subspace problem in low dimensions is
already hard for $\mathsf{QMA}.$

##### Other Applications of the Generalized Polynomial Method.

What are other applications of the generalized polynomial method? For
instance, Procesi [Pro76] has characterized the invariants of matrix tuples
under conjugation by the general linear, unitary, orthogonal, and symplectic
groups. Are there natural problems in quantum query complexity that display
other, non-unitary symmetries?

##### Applications of Weingarten Calculus.

Can the Weingarten calculus techniques introduced in Section 3 be used to
prove lower bounds on unitary property testing problems? In particular, could
it be used to prove degree lower bounds for acceptance probability
polynomials?

##### A Generalized Dual Polynomial Method?

A line of works established tight quantum query lower bounds on classical
problems by employing a method of _dual polynomials_ [She13, Spa08, BKT18].
The goal of this method is to prove degree lower bounds of acceptance
probability polynomials, but instead of symmetrizing the polynomials to obtain
a polynomial of one or two variables, one instead takes advantage of _linear
programming duality_ to prove the degree lower bounds; this involves
constructing objects known as dual polynomials. A natural question would be to
investigate whether the method of dual polynomials can be extended to prove
query lower bounds for unitary property testing.

## References

  * [Aar11] Scott Aaronson.  Impossibility of succinct quantum proofs for collision-freeness.  arXiv preprint arXiv:1101.0403, 2011.
  * [Aar21] Scott Aaronson.  Open problems related to quantum query complexity.  ACM Transactions on Quantum Computing, 2(4):1–9, 2021.
  * [ABD+08] Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, and Peter Shor.  The power of unentanglement.  In 2008 23rd Annual IEEE Conference on Computational Complexity, pages 223–236. IEEE, 2008.
  * [ACQ22] Dorit Aharonov, Jordan Cotler, and Xiao-Liang Qi.  Quantum algorithmic measurement.  Nature communications, 13(1):1–9, 2022.
  * [AK07] Scott Aaronson and Greg Kuperberg.  Quantum versus classical proofs and advice.  Theory of Computing, 3:129–157, 2007.
  * [AKKT20] Scott Aaronson, Robin Kothari, William Kretschmer, and Justin Thaler.  Quantum lower bounds for approximate counting via Laurent polynomials.  In 35th Computational Complexity Conference (CCC 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020.
  * [Amb06] Andris Ambainis.  Polynomial degree vs. quantum query complexity.  Journal of Computer and System Sciences, 72(2):220–238, 2006.
  * [Amb18] Andris Ambainis.  Understanding quantum algorithms via query complexity.  In Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, pages 3265–3285. World Scientific, 2018.
  * [AS04] Scott Aaronson and Yaoyun Shi.  Quantum lower bounds for the collision and the element distinctness problems.  Journal of the ACM (JACM), 51(4):595–605, 2004.
  * [BBBV97] Charles H Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani.  Strengths and weaknesses of quantum computing.  SIAM journal on Computing, 26(5):1510–1523, 1997.
  * [BBC+01] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf.  Quantum lower bounds by polynomials.  Journal of the ACM (JACM), 48(4):778–797, 2001.
  * [BBD+97] Adriano Barenco, Andre Berthiaume, David Deutsch, Artur Ekert, Richard Jozsa, and Chiara Macchiavello.  Stabilization of quantum computations by symmetrization.  SIAM Journal on Computing, 26(5):1541–1557, 1997.
  * [BBL13] Jacob Biamonte, Ville Bergholm, and Marco Lanzagorta.  Tensor network methods for invariant theory.  Journal of Physics A: Mathematical and Theoretical, 46(47):475301, 2013.
  * [BCHJ+21] Fernando G.S.L. Brandão, Wissam Chemissany, Nicholas Hunter-Jones, Richard Kueng, and John Preskill.  Models of quantum complexity growth.  PRX Quantum, 2(3), July 2021.
  * [Bel15] Aleksandrs Belovs.  Variations on quantum adversary.  arXiv preprint arXiv:1504.06943, 2015.
  * [Ber09] Andrew Schaffer Berget.  Symmetries of tensors.  University of Minnesota, 2009.
  * [BHMT02] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp.  Quantum amplitude amplification and estimation.  Contemporary Mathematics, 305:53–74, 2002.
  * [BHT98] Gilles Brassard, Peter Høyer, and Alain Tapp.  Quantum counting.  In International Colloquium on Automata, Languages, and Programming, pages 820–831. Springer, 1998.
  * [BKT18] Mark Bun, Robin Kothari, and Justin Thaler.  The polynomial method strikes back: Tight quantum query bounds via dual polynomials.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 297–310, 2018.
  * [BL57] P Bocchieri and A Loinger.  Quantum recurrence theorem.  Physical Review, 107(2):337, 1957.
  * [BR20] Aleksandrs Belovs and Ansis Rosmanis.  Tight quantum lower bound for approximate with quantum states.  arXiv preprint arXiv:2002.06879, 2020.
  * [Bra37] Richard Brauer.  On algebras which are connected with the semisimple continuous groups.  Annals of Mathematics, pages 857–872, 1937.
  * [BSW21] Zvika Brakerski, Devika Sharma, and Guy Weissenberg.  Unitary subgroup testing.  arXiv preprint arXiv:2104.03591, 2021.
  * [BT09] Hugue Blier and Alain Tapp.  All languages in $\mathsf{NP}$ have very short quantum proofs.  In 2009 Third International Conference on Quantum, Nano and Micro Technologies, pages 34–37, 2009.
  * [CCHL21] Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li.  A hierarchy for replica quantum advantage.  arXiv preprint arXiv:2111.05874, 2021.
  * [CCHL22] Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li.  Exponential separations between learning with and without quantum memory.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 574–585. IEEE, 2022.
  * [CD10] Jing Chen and Andrew Drucker.  Short multi-prover quantum proofs for SAT without entangled measurements.  arXiv preprint arXiv:1011.0716, 2010.
  * [CN16] Benoit Collins and Ion Nechita.  Random matrix techniques in quantum information theory.  Journal of Mathematical Physics, 57(1):015215, 2016.
  * [CNY22] Thomas Chen, Shivam Nadimpalli, and Henry Yuen.  Testing and learning quantum juntas nearly optimally.  arXiv preprint arXiv:2207.05898, 2022.
  * [CP21] Daniel Copeland and Jamie Pommersheim.  Quantum query complexity of symmetric oracle problems.  Quantum, 5:403, 2021.
  * [DGMT21] Marcel Dall’Agnol, Tom Gur, Subhayan Roy Moulik, and Justin Thaler.  Quantum proofs of proximity.  arXiv preprint arXiv:2105.03697, 2021.
  * [dW08] Ronald de Wolf.  A note on quantum algorithms and the minimal degree of epsilon-error polynomials for symmetric functions.  arXiv preprint arXiv:0802.1816, 2008.
  * [GHS21] Tom Gur, Min-Hsiu Hsieh, and Sathyawageeswar Subramanian.  Sublinear quantum algorithms for estimating von Neumann entropy.  arXiv preprint arXiv:2111.11139, 2021.
  * [GRB98] Markus Grassl, Martin Rötteler, and Thomas Beth.  Computing local invariants of quantum-bit systems.  Physical Review A, 58(3):1833, 1998.
  * [Gu13] Yinzheng Gu.  Moments of random matrices and Weingarten functions.  PhD thesis, Queen’s University, 2013.
  * [Ham21] Yassine Hamoudi.  Quantum Sub-Gaussian mean estimator.  arXiv preprint arXiv:2108.12172, 2021.
  * [HLW06] Patrick Hayden, Debbie W. Leung, and Andreas Winter.  Aspects of generic entanglement.  Communications in Mathematical Physics, 265(1):95–117, Mar 2006\.
  * [HM13] Aram W Harrow and Ashley Montanaro.  Testing product states, quantum Merlin-Arthur games and tensor optimization.  Journal of the ACM (JACM), 60(1):3, 2013.
  * [HMM+08] Masahito Hayashi, Damian Markham, Mio Murao, Masaki Owari, and Shashank Virmani.  Entanglement of multiparty-stabilizer, symmetric, and antisymmetric states.  Physical Review A, 77(1):012104, 2008.
  * [KO22] Robin Kothari and Ryan O’Donnell.  Mean estimation when you have the source code; or, quantum Monte Carlo methods.  arXiv preprint arXiv:2208.07544, 2022.
  * [KP96] Hanspeter Kraft and Claudio Procesi.  Classical invariant theory, a primer.  Lecture Notes. Preliminary version, 1996.
  * [Kre21] William Kretschmer.  The Quantum Supremacy Tsirelson Inequality.  Quantum, 5:560, October 2021.
  * [Kut03] Samuel Kutin.  A quantum lower bound for the collision problem.  arXiv preprint quant-ph/0304162, 2003.
  * [LCV07] Yi-Kai Liu, Matthias Christandl, and Frank Verstraete.  Quantum computational complexity of the $n$-Representability Problem: $\mathsf{QMA}$ complete.  Physical Review Letters, 98(11), Mar 2007.
  * [Led01] Michel Ledoux.  The concentration of measure phenomenon.  Number 89. American Mathematical Soc., 2001.
  * [Mar89] AA Markov.  Sur une question posée par Mendeleieff.  IAN, 62:1–24, 1889.
  * [Mar14] Olivier Marchal.  Matrix models, Toeplitz determinants and recurrence times for powers of random unitary matrices, 2014.
  * [MdW13] Ashley Montanaro and Ronald de Wolf.  A survey of quantum property testing.  arXiv preprint arXiv:1310.2035, 2013.
  * [Mon13] Ashley Montanaro.  Weak multiplicativity for random quantum channels.  Communications in Mathematical Physics, 319(2):535–555, 2013.
  * [MP17] Marvin Minsky and Seymour Papert.  Perceptrons.  MIT press, 2017.
  * [MS86] Vitali D Milman and Gideon Schechtman.  Asymptotic Theory of Finite Dimensional Normed Spaced, volume 1200\.  Springer Berlin, 1986.
  * [MW05] Chris Marriott and John Watrous.  Quantum Arthur–Merlin games.  Computational Complexity, 14(2):122–152, 2005.
  * [NC10] Michael Nielsen and Isaac Chuang.  Quantum Computation and Quantum Information.  Cambridge University Press, 2010.
  * [NS94] Noam Nisan and Mario Szegedy.  On the degree of Boolean functions as real polynomials.  Computational complexity, 4(4):301–313, 1994.
  * [Pat92] Ramamohan Paturi.  On the degree of polynomials that approximate symmetric Boolean functions (preliminary version).  In Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, STOC ’92, page 468–474, New York, NY, USA, 1992. Association for Computing Machinery.
  * [Pro76] C Procesi.  The invariant theory of $n\times n$ matrices.  Advances in Mathematics, 19(3):306–381, 1976.
  * [QSY20] Youming Qiao, Xiaoming Sun, and Nengkun Yu.  Local equivalence of multipartite entanglement.  IEEE Journal on Selected Areas in Communications, 38(3):568–574, 2020.
  * [Rei11] Ben W Reichardt.  Reflections for quantum query algorithms.  In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 560–569. SIAM, 2011.
  * [Sau09] Benoit Saussol.  An introduction to quantitative Poincaré recurrence in dynamical systems.  Reviews in Mathematical Physics, 21(08):949–979, 2009.
  * [She13] Alexander A Sherstov.  The intersection of two halfspaces has high threshold degree.  SIAM Journal on Computing, 42(6):2329–2374, 2013.
  * [Spa08] Robert Spalek.  A dual polynomial for OR.  arXiv preprint arXiv:0803.4516, 2008.
  * [ŠS05] Robert Špalek and Mario Szegedy.  All quantum adversary methods are equivalent.  In International Colloquium on Automata, Languages, and Programming, pages 1299–1311. Springer, 2005.
  * [SW22] Mehdi Soleimanifar and John Wright.  Testing matrix product states.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1679–1701. SIAM, 2022.
  * [TM+17] Jacob Turner, Jason Morton, et al.  A complete set of invariants for LU-equivalence of density operators.  SIGMA. Symmetry, Integrability and Geometry: Methods and Applications, 13:028, 2017.
  * [Wan11] Guoming Wang.  Property testing of unitary operators.  Physical Review A, 84(5):052328, 2011.
  * [Wes11] Quinton Westrich.  Young’s natural representations of $\mathcal{S}_{4}$.  arXiv preprint arXiv:1112.0687, 2011.

##  Appendix A A Generalized Product Test Analysis

Our goal in this section is to prove Theorem 6.4. Let
$\ket{\psi}\in\mathbb{C}^{d}\otimes\mathbb{C}^{d}$ be a bipartite state.
Recall that the $k$-copy product test uses as input $k$-copies of the state
$\ket{\psi}^{\otimes k}$, where each copy is on registers $A_{i}$ and $B_{i}$,
and then performs the measurement $\\{P=\Pi_{A}\otimes\Pi_{B},I-P\\},$ where
$\Pi_{A}$ is the projection onto the symmetric subspace among registers
$A_{1},\dots,A_{k}$ and $\Pi_{B}$ is the projection onto the symmetric
subspace among registers $B_{1},\dots,B_{k}.$ Recall from Theorem 6.1 that we
defined

$\omega_{\ket{\psi}}=\max_{\ket{\phi_{1}},\ket{\phi_{2}}}\\{\lvert\braket{\psi}{\phi_{1}\otimes\phi_{2}}\rvert^{2},\ket{\phi_{1}},\ket{\phi_{2}}\in\mathbb{C}^{d}\\}$

be the overlap with the closest product state. In particular, from Lemma 6.8,
we have that $\omega_{\ket{\psi}}=\lambda_{1}$ where $\lambda_{1}$ is the
largest eigenvalue of the reduced density matrix $\rho$ of
$\ket{\psi}\bra{\psi}.$

We establish the following bound on the performance of the product test for
any constant $k\geq 2$, using the techniques of [SW22].

See 6.4

Before proceeding with the proof, we fix some notation we will use throughout
the rest of this section. Let $[n]=\\{1,\dots,n\\}$,
$\lambda=(\lambda_{1},\dots,\lambda_{m})$ be a list of real numbers and
$\alpha=(\alpha_{1},\dots,\alpha_{l})$ be a list of non-negative integers.
Whenever well-defined, let
$\lambda_{\alpha}=\prod_{i=1}^{l}\lambda_{\alpha_{i}}$ and
$\lambda^{\alpha}=\prod_{i=1}^{m}\lambda_{i}^{\alpha_{i}}.$ Similarly if
$a=\\{a_{1},\dots,a_{n}\\}$ is a set of vectors, then
$\ket{a}_{\alpha}=\ket{a_{\alpha_{1}}}\otimes\dots\otimes\ket{a_{\alpha_{l}}}.$
Next, for the list $\alpha$, let $n(\alpha)$ be the number of non-zero entries
in $\alpha$ and $\text{type}(\alpha)$ be the list
$(\beta_{1},\dots,\beta_{j})$ where $\beta_{j}$ is the number of times integer
$j$ appears in the list $\alpha$. We will also write $\alpha\vdash k$ if
$\alpha=(\alpha_{1},\dots,\alpha_{l})$ is a list with
$\sum_{i=1}^{l}\alpha_{i}=k$, and $\binom{k}{\alpha}$ for the multinomial
coefficient $\frac{k!}{\prod_{i=1}^{l}\alpha_{i}!}.$

We first establish the exact probability the product test passes given the
state $\ket{\psi}^{\otimes k}$ as input.

######  Lemma A.1.

Let
$h_{k}(x_{1},\dots,x_{d})=\sum_{\begin{subarray}{c}\beta_{1}+\dots+\beta_{d}=k\\\
\beta_{i}\geq 0\end{subarray}}\prod_{i=1}^{d}x_{i}^{\beta_{i}}$ be the
homogenous symmetric polynomial of degree $k$ in $d$ variables. Then the
probability that the $k$-copy product state passes when run on state
$\ket{\psi}^{\otimes k}$ is equal to $h_{k}(\lambda_{1},\dots,\lambda_{d}),$
where $\lambda_{1},\dots,\lambda_{d}$ are the eigenvalues of the reduced
density matrix $\rho$ of $\ket{\psi}\bra{\psi}.$

###### Proof.

Let $k\geq 2$ be given. Consider the Schmidt decomposition of
$\ket{\phi}=\sum_{i=1}^{d}\sqrt{\lambda_{i}}\ket{a_{i}}\ket{b_{i}}$ across the
two subsystems, ordered so that $\lambda_{j}\geq\lambda_{j+1}$ for every index
$1\leq j<d.$ Letting $\Lambda=(\sqrt{\lambda_{1}},\dots,\sqrt{\lambda_{n}})$
be the list of Schmidt coefficients, then

$\ket{\phi}^{\otimes
k}=\sum_{\begin{subarray}{c}\alpha=(\alpha_{1},\dots,\alpha_{k})\\\
\alpha_{i}\in[d]\end{subarray}}\Lambda_{\alpha}\ket{a}_{\alpha}\ket{b}_{\alpha}.$
(2)

Now, note that if $\alpha,\alpha^{\prime}$ are two sequences with the same
type $\beta$, then
$\Lambda_{\alpha}=\Lambda_{\alpha^{\prime}}=\Lambda^{\beta}$. So rewrite
Equation 2, combining sequences of the same type.

$\ket{\phi}^{\otimes
k}=\sum_{\begin{subarray}{c}\beta=(\beta_{1},\dots,\beta_{d})\\\
\beta_{1}+\dots+\beta_{d}=k\end{subarray}}\Lambda^{\beta}\sum_{\begin{subarray}{c}\alpha=(\alpha_{1},\dots,\alpha_{k})\\\
\text{type}(\alpha)=\beta\end{subarray}}\ket{a}_{\alpha}\ket{b}_{\alpha}.$ (3)

We now consider the action of the projection $\Pi_{A}$ on the state
$\ket{\phi}^{\otimes k}.$ Write the projection as
$\Pi_{A}=\frac{1}{k!}\sum_{\sigma\in S_{k}}P_{\sigma}$ where $P_{\sigma}$
permutes vectors in $(\mathbb{C}^{d})^{k}.$ Note that if $\alpha$ and
$\alpha^{\prime}$ have the same type $\beta=(\beta_{1},\dots,\beta_{d})$,
there is some permutation $P_{\sigma}$ for which
$P_{\sigma}\ket{a}_{\alpha}=\ket{a}_{\alpha^{\prime}}$ and that there is a
subgroup $S_{\beta}=S_{\beta_{1}}\times\dots\times S_{\beta_{d}}\leq S_{k}$ of
permutations fixing $\ket{a}_{\alpha}$ of size $\prod_{i=1}^{d}\beta_{i}!.$
Hence, for every $\ket{a}_{\alpha},$

$\Pi_{A}\ket{a}_{\alpha}=\frac{1}{k!}\sum_{\text{cosets }\sigma
S_{\beta}}|S_{\beta}|P_{\sigma}\ket{a}_{\alpha}=\frac{1}{\binom{k}{\beta}}\sum_{\begin{subarray}{c}\text{all
}\alpha^{\prime}=(\alpha_{1},\dots,\alpha_{k})\\\
\text{type}(\alpha)=\alpha^{\prime}\end{subarray}}\ket{a}_{\alpha^{\prime}}.$

Therefore,

$\begin{split}(\Pi_{A}\otimes I)\ket{\phi}^{\otimes
k}&=\sum_{\begin{subarray}{c}\beta=(\beta_{1},\dots,\beta_{d})\\\
\beta_{1}+\dots+\beta_{d}=k\end{subarray}}\frac{\Lambda^{\beta}}{\binom{k}{\beta}}\sum_{\begin{subarray}{c}\alpha=(\alpha_{1},\dots,\alpha_{k})\\\
\text{type}(\alpha)=\beta\end{subarray}}\sum_{\begin{subarray}{c}\alpha^{\prime}=(\alpha_{1},\dots,\alpha_{k})\\\
\text{type}(\alpha^{\prime})=\beta\end{subarray}}\ket{a}_{\alpha^{\prime}}\ket{b}_{\alpha}.\\\
&=\sum_{\begin{subarray}{c}\beta=(\beta_{1},\dots,\beta_{d})\\\
\beta_{1}+\dots+\beta_{d}=k\end{subarray}}\Lambda^{\beta}\left(\frac{\displaystyle\sum_{\begin{subarray}{c}\alpha=(\alpha_{1},\dots,\alpha_{k})\\\
\text{type}(\alpha)=\beta\end{subarray}}\ket{a}_{\alpha}}{\sqrt{\binom{k}{\beta}}}\right)\left(\frac{\displaystyle\sum_{\begin{subarray}{c}\alpha=(\alpha_{1},\dots,\alpha_{k})\\\
\text{type}(\alpha)=\beta\end{subarray}}\ket{b}_{\alpha}}{\sqrt{\binom{k}{\beta}}}\right)\end{split}$
(4)

We will write
$\ket{a}^{\beta}=\left(\frac{\displaystyle\sum_{\begin{subarray}{c}\alpha=(\alpha_{1},\dots,\alpha_{k})\\\
\text{type}(\alpha)=\beta\end{subarray}}\ket{a}_{\alpha}}{\sqrt{\binom{k}{\beta}}}\right)$
and note that the set of all $\\{\ket{a}^{\beta}\\}$ over all $\beta\vdash k$
is an orthonormal basis for the symmetric subspace
$(\text{Sym}^{k}\mathbb{C}^{d}).$ Hence the probability that the product test
applied to the first subsystem passes is $\mu=\sum_{\beta\vdash
k}(\Lambda^{\beta})^{2},$ and conditioned on this, the post-measurement mixed
state is $\ket{a}^{\beta}\ket{b}^{\beta}$ with probability
$\frac{(\Lambda^{\beta})^{2}}{\mu}$. At this point, the second subsystem
becomes a symmetric state, and hence the projection onto the $B$ registers
passes with probability one. Hence, we obtain that the probability that the
product test passes is

$\mu=\sum_{\beta\vdash
k}(\Lambda^{\beta})^{2}=\sum_{\begin{subarray}{c}\beta_{1}+\dots+\beta_{d}=k\\\
\beta_{i}\geq
0\end{subarray}}\prod_{i=1}^{d}\lambda_{i}^{\beta_{i}}=h_{k}(\lambda_{1},\dots,\lambda_{d}).$
(5)

∎

###### Proof of Theorem 6.4.

Firstly, we claim that

$\frac{2}{k+1}\lambda_{1}^{k}+\sum_{\beta\vdash
k,\beta_{1}<k}(\Lambda^{\beta})^{2}\leq\frac{2}{k+1}.$ (6)

From Equation 3, we observe that

$1=\sum_{\beta\vdash
k}\binom{k}{\beta}(\Lambda^{\beta})^{2}=\lambda_{1}^{k}+\sum_{\beta\vdash
k.\beta_{1}<k}\binom{k}{\beta}(\Lambda^{\beta})^{2}.$ (7)

Therefore, we can divide the sum into three cases depending on the length
$n(\beta)$ and the the value of $\beta_{1},$

$\begin{split}&\frac{2}{k+1}\lambda_{1}^{k}+\sum_{\beta\vdash
k,\beta_{1}<k}(\Lambda^{\beta})^{2}=\frac{2}{k+1}\left[1-\sum_{\beta\vdash
k,\beta_{1}<k}\binom{k}{\beta}(\Lambda^{\beta})^{2}\right]+\sum_{\beta\vdash
k,\beta_{1}<k}(\Lambda^{\beta})^{2}\\\ &=\frac{2}{k+1}+\sum_{\beta\vdash
k,\beta_{1}<k}\left[1-\frac{2}{k+1}\binom{k}{\beta}\right](\Lambda^{\beta})^{2}\\\
&=\frac{2}{k+1}+\sum_{n(\beta)=1,\beta_{1}<k}\left[1-\frac{2}{k+1}\binom{k}{\beta}\right](\Lambda^{\beta})^{2}+\sum_{n(\beta)=2,\beta_{1}=k-1}\left[1-\frac{2}{k+1}\binom{k}{\beta}\right](\Lambda^{\beta})^{2}\\\
&+\sum_{\beta\vdash k,\beta_{1}<k-1,n(\beta)\geq
2}\left[1-\frac{2}{k+1}\binom{k}{\beta}\right](\Lambda^{\beta})^{2}.\end{split}$
(8)

Observe firstly that if $n(\beta)\geq 2$,
$\binom{k}{\beta}\geq\binom{k}{\beta_{i}}\geq k$ since $\beta_{i}\leq k-1$ is
the largest entry in the list $\beta.$ Hence in all these cases
$\left[1-\frac{2}{k+1}\binom{k}{\beta}\right](\Lambda^{\beta})^{2}\leq 0$
since $1-\frac{2}{k+1}\binom{k}{\beta}<0.$ This shows that the third case is
always negative.

Next, to bound the first and second cases:

$\begin{split}&\sum_{n(\beta)=1,\beta_{1}<k}\left[1-\frac{2}{k+1}\binom{k}{\beta}\right](\Lambda^{\beta})^{2}+\sum_{n(\beta)=2,\beta_{1}=k-1}\left[1-\frac{2}{k+1}\binom{k}{\beta}\right](\Lambda^{\beta})^{2}\\\
&=(1-\frac{2}{k+1})\sum_{i=2}^{d}\lambda_{i}^{k}+[1-\frac{2k}{k+1}]\sum_{i=2}^{d}\lambda_{1}^{k-1}\lambda_{i}\\\
&=\frac{k-1}{k+1}\sum_{i=2}^{d}\lambda_{i}^{k}-\frac{k-1}{k+1}\sum_{i=2}^{d}\lambda_{1}^{k-1}\lambda_{i}=\frac{k-1}{k+1}[\sum_{i=2}^{d}(\lambda_{i}(\lambda_{i}^{k-1}-\lambda_{1}^{k-1})]\leq
0\end{split}$ (9)

since each $\lambda_{i}$ is positive and $\lambda_{1}$ is the greatest of all
of the Schmidt coefficients. Therefore, we have established Equation 6 since
we have shown all of the sums in Equation 8 are negative.

Equation 6 and Lemma A.1 implies our bound since the probability that the
product test passes is

$\begin{split}h_{k}(\lambda_{1},\dots,\lambda_{d})&=\sum_{\beta\vdash
k}(\Lambda^{\beta})^{2}=\lambda_{1}^{k}+\sum_{\beta\vdash
k,\beta_{1}<k}(\Lambda^{\beta})^{2}\\\
&\leq\lambda_{1}^{k}+\frac{2}{k+1}-\frac{2}{k+1}\lambda_{1}^{k}=\frac{k-1}{k+1}\lambda_{1}^{k}+\frac{2}{k+1}=\frac{k-1}{k+1}\omega_{\ket{\psi}}^{k}+\frac{2}{k+1}.\end{split}$
(10)

where we have used the fact that for bipartite states,
$\omega_{\ket{\psi}}=\lambda_{1}$ from Lemma 6.8.

∎

##  Appendix B A $\mathsf{SymQMA}$ Verifier for the Entangled Subspace Problem

We now ready to apply Theorem 6.4 to prove Theorem 6.5.

See 6.5

The verifier $V_{k+1}$ has $k+1$ proof registers $\ket{\psi}^{\otimes k+1}$.
The $k$-copy product test is performed on registers 1 to $k$. Finally, the
circuit performs a controlled $U$ operation on the $k+1$(st) proof state. The
verifier accepts if and only if the product test passes and the ancilla qubit
for the controlled $U$ measures to be $1$. The verifier $V_{3}$ is depicted in
Figure 4.

@C=1.4em @R=1.4em & —ψ_1⟩_A_1 B_1 1Swap_A_1 A_2 1Swap_B_1 B_2
—ψ_2⟩_A_2 B_2 Swap_A_1 A_2 Swap_B_1 B_2
—ψ_3⟩_A_3 B_3 U
—+⟩_1 -2 H
—+⟩_2 -3 H
—+⟩_3 -3 H

Figure 4: $\mathsf{SymQMA(3)}$ verifier

###### Proof.

By assumption there exists a constant $\epsilon$ such that
$b^{2}-a^{2}=\epsilon>0$. Choose $k$ sufficiently large so that
$\frac{k-1}{k+1}(1-\frac{\epsilon^{2}}{4})^{k}+\frac{2}{k+1}\leq 1-b^{2}.$
Such $k$ exists if $\epsilon>0$ and $0\leq b<1$. We claim that the verifier
$V_{k+1}$ suffices to distinguishes between the two cases.

Suppose we are given a _yes_ instance $U$ of the Entangled Subspace problem.
This means that $U$ encodes a subspace $S$ containing a state
$\ket{\psi}\in\mathbb{C}^{d}\otimes\mathbb{C}^{d}$ that is $a$-close to a
product state $\ket{\varphi}\otimes\ket{\xi}$ in trace distance. Suppose we
run the verifier on the following proof state: $\ket{\theta}^{\otimes(k+1)}$
where $\ket{\theta}=\ket{\varphi}\otimes\ket{\xi}$. Clearly, this proof will
pass the product test with probability $1$ for any $k\geq 2$. Furthermore, the
acceptance probability of the subspace membership test is
$\Big{\|}\Pi\Big{(}\ket{\varphi}\otimes\ket{\xi}\Big{)}\Big{\|}^{2}=|\braket{\psi}{\varphi\otimes\xi}|^{2}\geq
1-a^{2}$, by assumption that $S$ contains a state that is $a$-close to
product.

Now suppose $U$ is a _no_ instance, and suppose for contradiction there exists
a proof $\ket{\psi}^{\otimes(k+1)}$ that is accepted by the verifier with
probability greater than $1-\frac{\epsilon}{2}-a^{2}$. Then in particular this
means that the product test with $\ket{\psi}^{\otimes k}$ accepts with
probability at least $1-\frac{\epsilon}{2}-a^{2}$. Hence, by Theorem 6.4, if
the witness causes the verifier to accept with probability at least
$1-\frac{\epsilon}{2}-a^{2},$ then by the choice of $k$, there exists a
product state $\ket{\theta}=\ket{\varphi}\otimes\ket{\xi}$ such that
$|\braket{\phi}{\theta}|^{2}\geq 1-\frac{\epsilon^{2}}{4}$ since
$b^{2}-a^{2}=\epsilon$ implies that $1-\frac{\epsilon}{2}-a^{2}\geq 1-b^{2}.$

Let $P_{S}$ be the projector onto the hidden subspace $S$. Since the
definition of trace distance implies that:

$|\operatorname{Tr}(P_{S}(\ket{\psi}\bra{\psi}-\ket{\theta}\bra{\theta}))|\leq\|\ket{\phi}\bra{\phi}-\ket{\theta}\bra{\theta}\|\leq\sqrt{1-(1-\frac{\epsilon^{2}}{4})}=\frac{\epsilon}{2}.$

Then since
$\operatorname{Tr}(P_{S}\ket{\psi}\bra{\psi})>1-\frac{\epsilon}{2}-a^{2},$ by
assumption we have

$\operatorname{Tr}(P_{S}\ket{\theta}\bra{\theta})>1-\epsilon-a^{2}=1-(\epsilon+a^{2})=1-b^{2}.$

which is a contradiction since $S$ was $b$-completely entangled. Therefore,
the verifier must accept with probability at most $1-\frac{\epsilon}{2}-a^{2}$
in the no case. Hence, there is a gap of at least
$1-a^{2}-(1-\frac{\epsilon}{2}-a^{2})=\frac{\epsilon}{2}$ in distinguishing
between the yes and no cases. Thus, there is a constant gap between the
acceptance probabilities of the _yes_ and _no_ instances, showing that the
$(a,b)$-Entangled Subspace problem is in SymQMA(k+1). ∎

##  Appendix C Characterization of Product Test Witnesses

In this section, we characterize all witness states that “fool” the two-copy
product test. This characterization enables us to construct additional
counterexamples that fool the two-copy product test verifier, in addition to
the one example presented in Section 6.3. To do this, we first translate our
problem in the language of representation theory.

###  C.1 Background

To construct the necessary states and subspaces, we use the theory of Schur-
Weyl duality, which states that there is an isomorphism

$(\mathbb{C}^{d})^{\otimes k}\cong\bigoplus_{\lambda\vdash
k}(V_{\lambda}\otimes W_{\lambda}),$

where $\lambda$ is a partition of $k$, $V_{\lambda}$ is a Specht module (an
irreducible representation of the symmetric group $S_{k}$) and $W_{\lambda}$
is a Weyl module (an irreducible representation of $GL(d).$) We focus on the
action of $S_{k}$ on $(\mathbb{C}^{d})^{\otimes k},$ which acts by permuting
registers, so we only need to consider the structure of $V_{\lambda}$.

There is a basis of $V_{\lambda}$ given explicitly by tableau states. Recall
that a standard Young tableau (SYT) of shape $\lambda$ is a filling of a
diagram of shape $\lambda$ in such a way that rows and columns increase
strictly. A semistandard Young tableau (SSYT) is a filling such that rows
weakly increase and columns strictly increase. An SYT and SSYT of shape
$(3,2)$ is shown in the figure below.

1 & 2 5 3 4 1 & 2 2 3 5

Figure 5: SYT and SSYT of shape $(3,2)$

Given an SYT $T$ with $n$ cells, let $P_{T}$ and $Q_{T}$ be the row and column
preserving subgroups of $T$. Let $a_{T}=\sum_{\sigma\in P_{T}}\Pi_{\sigma}$
and $b_{T}=\sum_{\sigma\in Q_{T}}\text{sgn}(\sigma)\Pi_{\sigma}$ be the row
symmeterization operator and column anti-symmeterization operators associated
tableau $T$. The Young symmeterizer is defined to be the product
$c_{T}=b_{T}a_{T}.$

The following theorem expresses Schur-Weyl theorem combinatorially.

######  Theorem C.1 ([Ber09], Appendix).

Let $\lambda$ be a partition of $k$ and let $(P,Q)$ be tableau of shape
$\lambda$. Let $e_{P,Q}$ be the tensor product of the basis elements in $Q$ in
the order given by $P$. Then the set of tensors $e_{P,Q}c_{P}$ where $Q$ is
fixed and $P$ varies across all possible SYTs is a basis for $V_{\lambda}.$

We call each basis vector $e_{P,Q}c_{P}$ a tableau state.

Let $\Pi_{ij}$ be a swap operator among registers $i$ and $j$. We observe that
a state $\ket{\psi}\in(\mathbb{C}^{d})^{\otimes 4}$ passes the product test
with probability one if and only if $\Pi_{13}\ket{\psi}=\ket{\psi}$ and
$\Pi_{24}\ket{\psi}=\ket{\psi}.$ Let $G=\\{e,(13),(24),(13)(24)\\}$ be the
subgroup of $S_{4}$ generated by these swap operators. Therefore, the
condition that $\ket{\psi}$ passes the product test with probability one is
equivalent to the condition that the one-dimensional subspace spanned by
$\ket{\psi}$ is a trivial representation of the group $G$.

Therefore, the Schur-Weyl isomorphism gives us a way to classify all states
that pass the product test with probability one. First we identify which
representations $V_{\lambda}$ of $S_{4}$ restrict to the trivial
representation of the group $G$. Then, we construct a basis of $G$-invariant
states by using the tableau state construction. This allows us to identify the
set of all states that fool the product test.

###  C.2 Calculations

######  Lemma C.2.

Let $V_{\lambda}$ be an irreducible $S_{4}$-representation. Then $V_{\lambda}$
contains a trivial representation of $G$ if and only if $\lambda=(4),(3,1)$ or
$(2,2).$ Furthermore, the restricted representation is a one-dimensional
subspace of $V_{\lambda}.$

###### Proof.

Let $\chi_{\lambda}$ be the character of the irreducible representation
$V_{\lambda}$. Using the character table of $S_{4}$, computed on [Wes11, Page
13], the sum

$\frac{1}{4}(\chi_{\lambda}(e)+\chi_{\lambda}((13))+\chi_{\lambda}((24))+\chi_{\lambda}((13)(24)))$

is non-zero (and equal to one) if and only if $\lambda=(4),(3,1)$ or $(2,2)$.
∎

1 & 2 3 4 1 & 2 4 3 1 & 3 4 2 a & b c d

Figure 6: SYT and SSYT of shape $(3,1)$

######  Lemma C.3.

Each copy of $V_{4}$ in $(\mathbb{C}^{d})^{\otimes 4}$ is one-dimensional and
symmetric under all permutations, given by the span of

$\begin{split}\ket{\psi_{abcd}^{4}}&=(\ket{ab}+\ket{ba})(\ket{cd}+\ket{dc})+(\ket{cd}+\ket{dc})(\ket{ab}+\ket{ba})\\\
&+(\ket{ac}+\ket{ca})(\ket{bd}+\ket{db})+(\ket{bd}+\ket{db})(\ket{ac}+\ket{ca})\\\
&+(\ket{ad}+\ket{da})(\ket{bc}+\ket{cb})+(\ket{bc}+\ket{cb})(\ket{ad}+\ket{da}).\end{split}$
(11)

where $a\leq b\leq c\leq d.$

###### Proof.

Follows from the definition of Young symmetrizer. ∎

######  Lemma C.4.

The unique $G$-invariant subspace in each copy of $V_{3,1}$ in
$(\mathbb{C}^{d})^{\otimes 4}$ is spanned by the vector

$\begin{split}\ket{\psi_{abcd}^{(3,1)}}&=(\ket{ab}+\ket{ba})(\ket{cd}-\ket{dc})+(\ket{ac}+\ket{ca})(\ket{bd}-\ket{db})+(\ket{bc}+\ket{cb})(\ket{ad}-\ket{da})\\\
&+(\ket{cd}-\ket{dc})(\ket{ab}+\ket{ba})+(\ket{bd}-\ket{db})(\ket{ac}+\ket{ca})+(\ket{ad}-\ket{da})(\ket{bc}+\ket{cb})\end{split}$
(12)

for some SSYT of shape $(3,1)$ containing elements $abcd.$

###### Proof.

Let $T$ be the leftmost tableau in Figure 6 and let $c_{T}=b_{T}a_{T}$ be the
corresponding Young symmeterizer. Since the row-preserving subgroup consists
of all permutations of $\\{1,2,3\\}$ and the column-preserving subgroup
consists of all permutations of $\\{1,4\\},$ then

$a_{T}\ket{abcd}=\ket{abcd}+\ket{bacd}+\ket{acbd}+\ket{cabd}+\ket{bcad}+\ket{cbad},$

and therefore

$\begin{split}c_{T}\ket{abcd}&=b_{T}a_{T}\ket{abcd}\\\
&=\ket{abcd}-\ket{dbca}+\ket{bacd}-\ket{dacb}+\ket{acbd}-\ket{dcba}\\\
&+\ket{cabd}-\ket{dabc}+\ket{bcad}-\ket{dcab}+\ket{cbad}-\ket{dbac}.\end{split}$

Call this vector $v_{1}.$ To obtain the other two vectors in $V_{3,1}$, we
compute

$\begin{split}v_{2}=c_{T}\ket{abdc}&=\ket{abdc}-\ket{dbac}+\ket{acdb}-\ket{dcab}+\ket{badc}-\ket{dabc}\\\
&+\ket{bcda}-\ket{dcba}+\ket{cadb}-\ket{dacb}+\ket{cbda}-\ket{dbca}.\end{split}$

using the second tableau in Figure 6, and finally

$\begin{split}v_{3}=c_{T}\ket{adbc}&=\ket{adbc}-\ket{dabc}+\ket{adcb}-\ket{dacb}+\ket{bdac}-\ket{dbac}\\\
&+\ket{bdca}-\ket{dbca}+\ket{cdab}-\ket{dcab}+\ket{cdba}-\ket{dcba}.\end{split}$

using the third and final tableau.

In the basis $\\{v_{1},v_{2},v_{3}\\}$ of $V_{3,1},$ the representation
matrices of permutations $(13)$ and $(24)$ are

$\begin{bmatrix}1&0&0\\\ -1&-1&-1\\\
0&0&1\end{bmatrix}\quad\begin{bmatrix}0&0&1\\\ 0&1&0\\\ 1&0&0\end{bmatrix}$

respectively. One can verify this directly or using the computations in
[Wes11]. Therefore, a vector that is invariant under simultaneous $(13)$ and
$(24)$ permutations is a common eigenvector of both matrices of eigenvalue 1,
which is $\begin{bmatrix}1\\\ -1\\\ 1\end{bmatrix}.$ Hence setting
$\ket{\psi_{abcd}^{(3,1)}}=v_{1}-v_{2}+v_{3}$ completes the proof. ∎

1 & 2 3 4 1 & 3 2 4 a & b c d

Figure 7: SYT and SSYT of shape $(2,2)$

######  Lemma C.5.

The unique $G$-invariant subspace in each copy of $V_{2,2}$ is spanned by the
vector

$\begin{split}\ket{\psi_{abcd}^{(2,2)}}&=(\ket{ab}+\ket{ba})(\ket{cd}+\ket{dc})+(\ket{cd}+\ket{dc})(\ket{ab}+\ket{ba})\\\
&+\ket{acdb}+\ket{cabd}-2\ket{acbd}-2\ket{cadb}\\\
&+\ket{bcda}+\ket{cbad}-2\ket{bcad}-2\ket{cbda}\\\
&+\ket{adcb}+\ket{dabc}-2\ket{adbc}-2\ket{dacb}\\\
&+\ket{bdca}+\ket{dbac}-2\ket{bdac}-2\ket{dbca}.\end{split}$ (13)

for some SSYT of shape $(2,2)$ containing elements $abcd.$

###### Proof.

The SYT of shape $(2,2)$ are listed in Figure 7. Using the first tableau with
row-preserving subgroup is $\\{e,(12),(34),(12)(34)\\}$ and the column-
preserving subgroup is $\\{e,(13),(24),(13)(24)\\}$, we have

$\begin{split}v_{1}=c_{T}\ket{abcd}&=\ket{abcd}-\ket{cbad}-\ket{adcb}+\ket{cdab}\\\
&+\ket{bacd}-\ket{cabd}-\ket{bdca}+\ket{cdba}\\\
&+\ket{abdc}-\ket{dbac}-\ket{acdb}+\ket{dcab}\\\
&+\ket{badc}-\ket{dabc}-\ket{bcda}+\ket{dcba}.\end{split}$

Similarly, using the second tableau, we get that

$\begin{split}v_{2}=c_{T}\ket{acbd}&=\ket{acbd}-\ket{cabd}-\ket{acdb}+\ket{cadb}\\\
&+\ket{bcad}-\ket{cbad}-\ket{bcda}+\ket{cbda}\\\
&+\ket{adbc}-\ket{dabc}-\ket{adcb}+\ket{dacb}\\\
&+\ket{bdac}-\ket{dbac}-\ket{bdca}+\ket{dbca}.\end{split}$

In the basis $\\{v_{1},v_{2}\\}$ of $V_{2,2},$ the matrices for $(13)$ and
$(24)$ are the same, and equal to $\begin{bmatrix}-1&-1\\\ 0&1\end{bmatrix}.$
An eigenvector of eigenvalue one is $\begin{bmatrix}1\\\ -2\end{bmatrix}.$
Setting $\ket{\psi_{abcd}^{(2,2)}}=v_{1}-2v_{2}$ completes the proof. ∎

######  Theorem C.6.

There exists a basis for the $G$-invariant subspace $V$ of
$(\mathbb{C}^{d})^{\otimes 4}$ consisting where each $\ket{\psi}\in V$ is in
the span of states $\ket{\psi_{1}}\otimes\ket{\psi_{2}},$ where
$\ket{\psi_{1}},\ket{\psi_{2}}\in(\mathbb{C}^{d})^{\otimes 2}.$

###### Proof.

We have already computed that
$\\{\ket{\psi_{abcd}^{4}},\ket{\psi_{abcd}^{(3,1)}},\ket{\psi_{abcd}^{(2,2)}}\\}$
is a basis for $V$ ranging over all tableau of the appropriate shape with
fillings $abcd.$ Observe that states of the form $\ket{\psi_{abcd}^{4}}$ and
$\ket{\psi_{abcd}^{(3,1)}}$ already have the desired property. Now defining

$\ket{\psi_{abcd}^{(2,2)}}^{\prime}=\frac{1}{3}\ket{\psi_{abcd}^{4}}+\frac{2}{3}\ket{\psi_{abcd}^{(2,2)}},$

we can compute that

$\begin{split}\ket{\psi_{abcd}^{(2,2)}}^{\prime}&=(\ket{ab}+\ket{ba})(\ket{cd}+\ket{dc})+(\ket{cd}+\ket{dc})(\ket{ab}+\ket{ba})\\\
&+\ket{acdb}+\ket{cabd}-\ket{acbd}-\ket{cadb}\\\
&+\ket{bcda}+\ket{cbad}-\ket{bcad}-\ket{cbda}\\\
&+\ket{adcb}+\ket{dabc}-\ket{adbc}-\ket{dacb}\\\
&+\ket{bdca}+\ket{dbac}-\ket{bdac}-\ket{dbca}\\\
&=(\ket{ab}+\ket{ba})(\ket{cd}+\ket{dc})+(\ket{cd}+\ket{dc})(\ket{ab}+\ket{ba})\\\
&+(\ket{ac}-\ket{ca})(\ket{db}-\ket{bd})+(\ket{bd}-\ket{db})(\ket{ca}-\ket{ac})\\\
&+(\ket{bc}-\ket{cb})(\ket{da}-\ket{ad})+(\ket{ad}-\ket{da})(\ket{cb}-\ket{bc})\end{split}$

has the desired property, and
$\\{\ket{\psi_{abcd}^{4}},\ket{\psi_{abcd}^{(3,1)}},\ket{\psi_{abcd}^{(2,2)}}^{\prime}\\}$
ranging over all tableau remains a basis of $V$. ∎

Therefore, Theorem C.6 enables us to construct subspaces $S$ where there
exists an witness on which the product test part of the verifier passes with
probability one. This can be done, for instance, by taking $\ket{\psi}\in V$
in Theorem C.6 and letting $S$ be supported on the partial trace of
$\ket{\psi}$ on the first two registers. In particular, $S$ could be an
completed entangled subspace, for instance by considering the symmetric
subspaces as in Proposition 6.6.