# APPROXIMATING SINGULARITIES BY A CUSPIDAL-EDGE ON A MAXFACE

PRADIP KUMAR Department of Mathematics, Shiv Nadar University, Dadri 201314,
Uttar pradesh, India.
Email Address<EMAIL_ADDRESS>and  SAI RASMI RANJAN MOHANTY
Department of Mathematics, Shiv Nadar University, Dadri 201314, Uttar pradesh,
India.
Email Address<EMAIL_ADDRESS>
###### Abstract.

We give necessary and sufficient conditions on the singular Björling data to
the singular Björling problem’s solution has a prescribed nature of
singularity. As an application, for a given maxface with a particular type of
singularity, we find a sequence of maxfaces, all having a cuspidal edge.

###### Key words and phrases:

Maxface singularities, Cuspidal-edge.

###### 2010 Mathematics Subject Classification:

53A35

##  1\. Introduction

Maximal immersions are zero mean curvature immersions in the Lorentz-Minkowski
space $\mathbb{E}_{1}^{3}$. These are very similar to the minimal surface in
$\mathbb{R}^{3}$, but if we allow some singularities (where maps are not
immersions), the theory of these two differs. Maximal surfaces with
singularity are called generalized maximal surfaces. Singularity on the
generalized maximal surface is branched and non-branched. Non-branched
singular points are those points where limiting tangent space does not
collapse, and it contains a light-like vector. Various aspects of non branched
singularities have been studied in [Estudillo1992], [Fujimori2007],
[imaizumi2008], [Kim2007], [KOBAYASHI1984], [OT2018], [UMEHARA2006] etc.

Umehara and Yamada in [UMEHARA2006], proved that every non branched maximal
immersions as a map in $\mathbb{R}^{3}$ turn out to be frontal. They called
non branched maximal immersions as maxface and discussed when this becomes the
front near a singular point. Cuspidal-edge, swallowtails, cuspidal crosscaps,
cuspidal butterflies, and cuspidal $S_{1}^{-}$ are few singularities that
appear on a maxface $X$ as front or frontal.

On cuspidal-edges of the front, Saji, Umehara, and Yamada [Saji2009]
introduced the singular curvature function which is closely related to the
behavior of the Gaussian curvature of a surface near cuspidal edges. Further,
Martins and Saji [MARTINS2018209], study differential geometric properties of
cuspidal edges with boundary and given several differential geometric
invariants. Toshizumi Fukui [FukuiCuspidaledge] also studied the local
differential geometry of cuspidal edges.

Not all maxfaces are front but if we approximate singularities on maxfaces
with a cuspidal-edge (that is the first kind of singularities of fronts) then
it may help us to understand the existence of some invariant related to other
types of singularities as we have for the cuspidal-edge ([FukuiCuspidaledge],
[MARTINS2018209],[Saji2009]). This idea motivates us to approximate
singularities by a cuspidal-edge.

In this article in section 4, we construct a sequence (there may be many
others) of maxfaces with a cuspidal edge that “converges" to other
singularities like shrinking or folded or as in the table 1. To prove this, we
shall give necessary and sufficient conditions on the singular Björling data
$\\{\gamma,L\\}$ such that it has a cuspidal-edge at some point.

Along with the cuspidal edge, in this article, we find the necessary and
sufficient conditions on the singular Björling data $\\{\gamma,L\\}$ such that
its corresponding maxface has swallowtails, cuspidal crosscaps, cuspidal
butterflies, and cuspidal $S_{1}^{-}$. We summarize the conditions (given in
the propositions: 3.1, 3.2, and 3.3 ) here in the table 1.

Nature of singularities at $p$ Function’s value at $p$ | $\gamma^{\prime}$ | $L$ | $\gamma^{\prime\prime}$ | $\gamma^{\prime\prime\prime}$ | $L^{\prime}$ | $L^{\prime\prime}$ | $\gamma_{1}^{\prime}\gamma_{2}^{\prime\prime}-\gamma_{1}^{\prime\prime}\gamma_{2}^{\prime}$ | $L_{1}L_{2}^{\prime}-L_{1}^{\prime}L_{2}$
---|---|---|---|---|---|---|---|---
Cuspidal-edge | $\neq 0$ | $\neq 0$ | – | – | – | – | $\neq 0$ | $\neq 0$
Swallowtails | $=0$ | $\neq 0$ | $\neq 0$ | – | – | – | – | $\neq 0$
Cuspidal butterflies | $=0$ | $\neq 0$ | $=0$ | $\neq 0$ | – | – | – | $\neq 0$
Cuspidal $S_{1}^{-}$ | $\neq 0$ | $=0$ | – | – | $=0$ | $\neq 0$ | $\neq 0$ | –
Cuspidal-Crosscaps | $\neq 0$ | $=0$ | – | – | $\neq 0$ | – | $\neq 0$ | –
Table 1.

We believe the above table is very useful and apart from finding required
convergent sequence, it may be a starting point of studying suitable
interpolation problem (finding a maxface containing two disjoint curves with
prescribed nature of singularities along the curve). In [LOPEZ20072178], López
discussed a kind of interpolation problem where he proves the existence of
maximal immersion (not the generalized) spanning two disjoint circular
contours. Some discussion about finding maxface with two interpolating
singular curve can be found in [RPR2016]. But we believe, a general discussion
requires an initial setup like the conditions as in the table 1. In article
[brander_2011], David Brander has discussed similar conditions for the case of
the non-maximal CMC surfaces with the special data.

The discussion of this article is close to [brander_2011], [Kim2007], and
[UMEHARA2006].

##  2\. Preliminary

This section reviews the definition of maxface, Weierstrass-Enneper
representation, and the singular Björling problem.

The Lorentz-Minkowski space $\mathbb{E}_{1}^{3}$ is a vector space
$\mathbb{R}^{3}$ with metric
$\langle,\rangle:\mathbb{R}^{3}\times\mathbb{R}^{3}\to\mathbb{R}$ defined by
$\langle(a_{1},b_{1},c_{1}),(a_{2},b_{2},c_{2})\rangle:=a_{1}a_{2}+b_{1}b_{2}-c_{1}c_{2}$
and the generalised maximal immersion is an immersion of a Riemann surface
(with boundary) $M$ to $\mathbb{E}_{1}^{3}$, such that pullback metric on $M$
does not vanish identically and it is positive definite wherever metric does’t
vanish. Moreover at non degenerate points mean curvature is zero. Maxfaces are
those generalized maximal immersions where singularities are only those points
of $M$ where the limiting tangent plane has a light-like vector. We have the
following representation of the maxface.

###  2.1. Weierstrass-Enneper representation [UMEHARA2006]

For a maxface $X:M\to\mathbb{E}_{1}^{3}$, there is a pair $(g,\omega)$ of
meromorphic function and a holomorphic 1-form on $M$ such that $|g|$ is not
identically equal 1 and for $\Phi:=(1+g^{2},i(1-g^{2}),-2g)\omega$, the map
$X$ is given by $X(p):=Re\int_{0}^{p}\Phi.$

For a maxface, with the help of Weierstrass data $(g,\omega)$, below we define
functions $\alpha,\beta,$ and $\eta$ as in [Fujimori2007], [OT2018], and
[UMEHARA2006].

######  Definition 2.1.

At $p\in M,$ let $(U,z)$ be a coordinate chart and $\omega=f\,dz$, we define

$\alpha(z)=\frac{g^{\prime}(z)}{g^{2}(z)f(z)},\;\beta(z)=\frac{g(z)}{g^{\prime}(z)}\alpha^{\prime}(z),\,\,{\rm
and}\,\,\eta(z)=\frac{g(z)}{g^{\prime}(z)}\beta^{\prime}(z).$

These functions help us to check the nature of singularity on a maxface. In
[Fujimori2007], [OT2018], and [UMEHARA2006], we find criterion to check the
nature of singularity. We mention it here.

Re$(\alpha)\neq 0$ |  Im$(\alpha)\neq 0$ |  |  |  $\Leftrightarrow p$ is a cuspidal-edge
---|---|---|---|---
Re$(\alpha)\neq 0$ |  Im$(\alpha)=0$ |  Re $(\beta)\neq 0$ |  |  $\Leftrightarrow p$ is a swallowtails
Re$(\alpha)\neq 0$ |  Im$(\alpha)=0$ |  Re $(\beta)=0$ |  Im$(\eta)\neq 0$ |  $\Leftrightarrow p$ is a cuspidal butterlflies
Re$(\alpha)=0$ |  Im$(\alpha)\neq 0$ |  Im$(\beta)=0$ |  Re$(\eta)\neq 0$ |  $\Leftrightarrow p$ is a cuspidal $S_{1}^{-}$
Re$(\alpha)=0$ |  Im$(\alpha)\neq~0$ |  Im $(\beta)\neq 0$ |  |  $\Leftrightarrow p$ is a cuspidal crosscaps
Table 2.

###  2.2. Singular Björling problem [Kim2007]

We explain the singular Björling problem in the following.

######  Definition 2.2.

(Singular Björling data [Kim2007]). Let $\gamma:I\to\mathbb{E}_{1}^{3}$ be a
real analytic null curve and $L:I\to\mathbb{E}_{1}^{3}$ be a real analytic
null vector field such that for all $u\in I$, $\gamma^{\prime}(u)$ and $L(u)$
are proportional, and $\gamma^{\prime}(u)$ and $L(u)$ do not vanish
simultaneously. Such $\\{\gamma,L\\}$ is said to be a singular Björling data.

If the analytic extension of the function $g:I\to\mathbb{C}$,

(2.1) $g(u):=\begin{cases}\dfrac{L_{1}+iL_{2}}{L_{3}};\;\text{ if
}\gamma^{\prime}\text{ vanishes identically}\\\
\dfrac{{\gamma_{1}}^{\prime}+i{\gamma_{2}}^{\prime}}{{\gamma_{3}}^{\prime}};\;\text{
if }~L\text{ vanishes identically}\end{cases}$

satisfies $|g(z)|\not\equiv 1$ on some simply connected domain
$\Omega\subset\mathbb{C}$, where $z=u+iv\in\Omega$ and $I\subset\Omega$. Then
there is a unique generalized maximal immersion
$X:\Omega\to\mathbb{E}_{1}^{3}$ is given by (for $u_{0}\in I$ fixed),
$X(z)=\gamma(u_{0})+{Re}\left(\int_{u_{0}}^{z}(\gamma^{\prime}(w)-iL(w))dw\right)$
such that $X(u,0)=\gamma(u)$ and $X_{v}(u,0)=L(u)$. Moreover it has
singularity set at least $I$. After a translation we can assume that
$\gamma(u_{0})=0$, so we consider the solution as

(2.2)
$X_{\gamma,L}(z)={Re}\left(\int_{u_{0}}^{z}(\gamma^{\prime}(w)-iL(w))dw\right).$

The way singular Björling data is taken, the singularity set contains an
interval $I$ and for all $u$, $\gamma^{\prime}(u)$ and $L(u)$ do not vanish
simultaneously. Therefore $X_{\gamma,L}$ turns out to be a maxface in a
neighborhood of singular points. In fact the Weierstrass data for the maxface
as in the equation 2.2 is given by the analytic extension of
$f(u)=(\gamma_{1}^{\prime}-iL_{1})-i(\gamma_{2}^{\prime}-iL_{2})$ and $g$ as
in the equation 2.1.

##  3\. Necessary and sufficient conditions on the singular Björling data for
prescribed type of singularity

In this section, we will calculate $\alpha,\beta$, and $\eta$ as in the
definition 2.1 for the maxface $X_{\gamma,L}$ at some singularity $t_{0}\in
I$. We get necessary and sufficient conditions on $\\{\gamma,L\\}$ so that
$X_{\gamma,L}$ have a cuspidal-edge, swallowtails, cuspidal cross caps,
cuspidal butterflies and cuspidal $S_{1}^{-}$ singularities.

###  3.1. For cuspidal-edge at $u\in I$.

Let $\\{\gamma,L\\}$ be the singular Björling data as in the definition 2.2.
With the Gauss map as in the equation 2.1, we calculate $\alpha$ as in the
definition 2.1.

At $u\in I,$ if $\gamma^{\prime}(u)\neq 0$, then there exist a real number $c$
such that $L(u)=c\gamma^{\prime}(u)$. So that
$f(u)=(1-ic)(\gamma_{1}^{\prime}(u)-i\gamma_{2}^{\prime}(u))$ and
$g(u)=\dfrac{\gamma_{1}^{\prime}(u)+i\gamma_{2}^{\prime}(u)}{\gamma_{3}^{\prime}(u)}$.
In this case, we have
$\alpha(u)=\dfrac{g^{\prime}}{g^{2}f}(u)=\dfrac{g^{\prime}}{g(1-ic)\gamma_{3}^{\prime}}(u)$.
Here replacing the value of f and g we get

$\alpha(u)=\frac{\gamma_{3}^{\prime}(\gamma_{1}^{\prime\prime}+i\gamma_{2}^{\prime\prime})-(\gamma_{1}^{\prime}+i\gamma_{2}^{\prime})\gamma_{3}^{\prime\prime}}{\gamma_{3}^{\prime
2}(1-ic)\gamma_{3}^{\prime}}\frac{\gamma_{3}^{\prime}}{\gamma_{1}^{\prime}+i\gamma_{2}^{\prime}}=-\frac{\gamma_{3}^{\prime\prime}}{\gamma_{3}^{\prime
2}(1-ic)}+\frac{(\gamma_{1}^{\prime\prime}+i\gamma_{2}^{\prime\prime})(\gamma_{1}^{\prime}-i\gamma_{2}^{\prime})}{\gamma_{3}^{\prime}(1-ic)(\gamma_{1}^{\prime
2}+\gamma_{2}^{\prime 2})}(u).$

That is we have,

$\alpha(u)=\frac{1}{\gamma_{3}^{\prime
3}(1-ic)}[-\gamma_{3}^{\prime\prime}\gamma_{3}^{\prime}+\gamma_{1}^{\prime\prime}\gamma_{1}^{\prime}+\gamma_{2}^{\prime\prime}\gamma_{2}^{\prime}+i(\gamma_{1}^{\prime}\gamma_{2}^{\prime\prime}-\gamma_{1}^{\prime\prime}\gamma_{2}^{\prime})](u).$

We denote:

(3.1)
$D(\gamma_{12}^{\prime},\gamma_{12}^{\prime\prime}):=\gamma_{1}^{\prime}\gamma_{2}^{\prime\prime}-\gamma_{1}^{\prime\prime}\gamma_{2}^{\prime};\quad
D(L_{12},L_{12}^{\prime}):=L_{1}L_{2}^{\prime}-L_{2}L_{1}^{\prime}.$

So that
$\alpha(u)=i\dfrac{D(\gamma_{12}^{\prime},\gamma_{12}^{\prime\prime})}{\gamma_{3}^{\prime
3}(1-ic)}$. Moreover $\gamma$ is a null curve and
$c=\dfrac{L_{3}}{\gamma_{3}^{\prime}}$, therefore at $u$, when
$\gamma^{\prime}(u)\neq 0$, we get:

(3.2)
$\alpha(u)=-\frac{L_{3}D(\gamma_{12}^{\prime},\gamma_{12}^{\prime\prime})}{(\gamma_{3}^{\prime
2}+L_{3}^{2})\gamma_{3}^{\prime
2}}+i\frac{D(\gamma_{12}^{\prime},\gamma_{12}^{\prime\prime})}{(\gamma_{3}^{\prime
2}+L_{3}^{2})\gamma_{3}^{\prime}}.$

Similarly, for the case when $L(u)\neq 0$, we get the following:

(3.3) $\alpha(u)=-\frac{D(L_{12},L_{12}^{\prime})}{(\gamma_{3}^{\prime
2}+L_{3}^{2})L_{3}}+i\frac{\gamma_{3}^{\prime}D(L_{12},L_{12}^{\prime})}{(\gamma_{3}^{\prime
2}+L_{3}^{2})L_{3}^{2}}.$

We know, $u$ is a cuspidal-edge for the maxface if and only if $Re(\alpha)$
and $Im(\alpha)$ at $u$ are non zero.

Therefore at those points $u\in I$, where $\gamma^{\prime}\neq 0$ and $u$ is
cuspidal-edge for the maxface (as in the equation 2.2), we must have
$\gamma^{\prime}\neq 0,L\neq 0$ and
$D(\gamma_{12}^{\prime},\gamma_{12}^{\prime\prime})\neq 0$ at $u$ and this
implies $D(L_{12},L_{12}^{\prime})\neq 0$ at $u$.

On the other hand, at those points $u\in I$, where $L\neq 0$ and $u$ is a
cuspidal-edge, we must have $\gamma^{\prime}\neq 0,L\neq 0$ and
$D(L_{12},L_{12}^{\prime})\neq 0$ at $u$, and this implies
$D(\gamma_{12}^{\prime},\gamma_{12}^{\prime\prime})\neq 0$ at $u$.

This proves the following;

######  Proposition 3.1.

Let $\\{\gamma,L\\}$ be the singular Björling data. Then the maxface
$X_{\gamma,L}$ as in the equation 2.2 has cuspidal-edge at $u\in I$, if and
only if at $u$, $\gamma^{\prime}\neq 0,L\neq 0$ and
$D(\gamma_{12}^{\prime},\gamma_{12}^{\prime\prime})\neq 0$ or
$D(L_{12},L_{12}^{\prime})\neq 0$.

This proposition has many applications, in particular, we will use it to prove
the theorem 4.3. Moreover, constructing examples having cuspidal-edge
singularity turns out be handy.

######  Example 3.1.

Let $\gamma(u)=(sin\,u,-cos\,u,u)$ and $L(u)=u(cos\,u,sin\,u,1)$ on $I=(0,1)$.
Then we have $L(u)=u\gamma^{\prime}(u)$ and
$D(\gamma_{12}^{\prime},\gamma_{12}^{\prime\prime})=1$.

It is clear that $\gamma^{\prime}\neq 0,\;L\neq 0$ and
$D(\gamma_{12}^{\prime},\gamma_{12}^{\prime\prime})\neq 0$ on $(0,1)$. So that
all are cuspidal-edge on $(0,1)$.

######  Example 3.2.

Let $\gamma(u)=(u-\frac{u^{3}}{3},u^{2},u+\frac{u^{3}}{3})$ and
$L(u)=u^{2}(1-u^{2},2u,1+u^{2})$ on $I=(0,1)$. Then
$L(u)=u^{2}\gamma^{\prime}(u)$ and
$D(\gamma_{12}^{\prime},\gamma_{12}^{\prime\prime})=2(u^{2}+1)$. It is clear
that $\gamma^{\prime}\neq 0,L\neq 0$ and
$D(\gamma_{12}^{\prime},\gamma_{12}^{\prime\prime})\neq 0$ on $(0,1)$. Hence
all points are cuspidal-edge on $(0,1)$.

In the following, we will find necessary and sufficient conditions on the
singular Björling data such that the maxface (as in the equation 2.2) has
swallowtails, cuspidal cross-caps etc, at $u\in I$.

###  3.2. For Swallowtails and cuspidal butterflies at $u$.

If $L\neq 0$ at $u$, then $\gamma^{\prime}=dL$, where $d$ is a function in a
neighborhood of $u$. In this case, from the equation 3.3, we have
$\alpha=i\dfrac{D(L_{12},L_{12}^{\prime})}{(d-i)L_{3}^{3}}$ therefore
$\alpha^{\prime}=i\frac{D(L_{12},L_{12}^{\prime\prime})(d-i)L_{3}^{3}-D(L_{12},L_{12}^{\prime})(d^{\prime}L_{3}^{3}+3(d-i)L_{3}^{2}L_{3}^{\prime})}{(d-i)^{2}L_{3}^{6}}$.

This gives

(3.4)
$\beta=\frac{\alpha^{\prime}}{(d-i)L_{3}\alpha}=\frac{D(L_{12},L_{12}^{\prime\prime})(d-i)L_{3}^{3}-D(L_{12},L_{12}^{\prime})(d^{\prime}L_{3}^{3}+3(d-i)L_{3}^{2}L_{3}^{\prime})}{(d-i)^{2}L_{3}^{4}D(L_{12},L_{12}^{\prime})},$
(3.5)
$\begin{split}\beta^{\prime}&=\frac{D(L_{12},L_{12}^{\prime})(d-i)L_{3}(D(L_{12},L_{12}^{\prime\prime})+D(L_{12},L_{12}^{\prime\prime\prime}))}{(d-i)^{2}L_{3}^{2}D^{2}(L_{12},L_{12}^{\prime})}\\\
&-\frac{D(L_{12},L_{12}^{\prime\prime})((d-i)L_{3}^{\prime}D(L_{12},L_{12}^{\prime})+(d-i)L_{3}D(L_{12},L_{12}^{\prime\prime})+d^{\prime}L_{3}D(L_{12},L_{12}^{\prime}))}{(d-i)^{2}L_{3}^{2}D^{2}(L_{12},L_{12}^{\prime})}\\\
&-\frac{(d-i)^{2}L_{3}^{2}(d^{\prime\prime}L_{3}+4d^{\prime}L_{3}^{\prime}+3(d-i)L_{3}^{\prime\prime})}{(d-i)^{4}L_{3}^{4}}\\\
&+\frac{(d^{\prime}L_{3}+3(d-i)L_{3}^{\prime})(2(d-i)d^{\prime}L_{3}^{2}+2(d-i)^{2}L_{3}L_{3}^{\prime})}{(d-i)^{4}L_{3}^{4}}.\end{split}$

Moreover

(3.6)
$\eta=\frac{g}{g^{\prime}}\beta^{\prime}=\frac{\beta^{\prime}}{(d-i)L_{3}\alpha}=-i\frac{\beta^{\prime}L_{3}^{2}}{D(L_{12},L_{12}^{\prime})}.$

We know $X_{\gamma,L}$ has swallowtails at $u\in I$ if and only if at $u$,
$Re\,\alpha\neq 0,Im\,\alpha=0$ and $Re\,\beta\neq 0$.

The first two conditions $Re\,\alpha\neq 0$ and $Im\,\alpha=0$ at $u$ if and
only if at $u$, $D(L_{12},L_{12}^{\prime})\neq 0,L\neq 0$ and
$\gamma^{\prime}=0$. Since at $u$, $d=\dfrac{\gamma^{\prime}}{L}=0$,

$\beta=\frac{D(L_{12},L_{12}^{\prime})d^{\prime}L_{3}^{3}+i(D(L_{12},L_{12}^{\prime\prime})L_{3}^{3}-3D(L_{12},L_{12}^{\prime})L_{3}^{2}L_{3}^{\prime})}{L_{3}^{4}D(L_{12},L_{12}^{\prime})}.$

Therefore at $u$, $Re\,\beta\neq 0$ if and only if $d^{\prime}\neq 0$ at $u$.
That is $Re\,\beta\neq 0$ if and only if $\gamma^{\prime\prime}\neq 0$ at $u$.

On the other hand, $X_{\gamma,L}$ as in the equation 2.2 has a cuspidal
butterflies at $u\in I$ if and only if at $u$, $Re\,\alpha\neq
0,Im\,\alpha=0,Re\,\beta=0$ and $Im\,\eta\neq 0$.

The first two conditions hold at $u$ if and only if at $u$,
$D(L_{12},L_{12}^{\prime})\neq 0,L\neq 0,\gamma^{\prime}=0$ and
$d^{\prime}=0$. Since at $u$, $d=0$ and $Re\,\beta=0$ if and only if
$d^{\prime}=0$, we get from the equation 3.5 and 3.6

$\displaystyle\eta=\frac{D(L_{12},L_{12}^{\prime})(D(L_{12}^{\prime},L_{12}^{\prime\prime})+D(L_{12},L_{12}^{\prime\prime\prime}))}{D^{2}(L_{12}^{\prime},L_{12}^{\prime})}$
$\displaystyle+\frac{D(L_{12}^{\prime},L_{12}^{\prime\prime})(L_{3}^{\prime}D(L_{12}^{\prime},L_{12}^{\prime})+L_{3}D(L_{12}^{\prime},L_{12}^{\prime\prime}))}{D^{2}(L_{12}^{\prime},L_{12}^{\prime})}$
$\displaystyle-i\frac{L_{3}(d^{\prime\prime}L_{3}-3iL_{3}^{\prime\prime})+6iL_{3}^{\prime
2}}{L_{3}D(L_{12}^{\prime},L_{12}^{\prime})}.$

Therefore at $u,Im\,\eta\neq 0$ if and only if $d^{\prime\prime}\neq 0$. That
implies at $u$, $Im\,\eta\neq 0$ if and only if
$\gamma^{\prime\prime\prime}\neq 0$. So we have the following:

######  Proposition 3.2.

$X_{\gamma,L}$ has swallowtails at $u$ if and only if at $u$,
$\gamma^{\prime}=0,\gamma^{\prime\prime}\neq 0,L\neq 0$, and
$D(L_{12},L_{12}^{\prime})\neq 0$. On the other hand, $X_{\gamma,L}$ has
cuspidal butterflies at $u$ if and only if
$\gamma^{\prime}=0,\gamma^{\prime\prime}=0,\gamma^{\prime\prime\prime}\neq
0,L\neq 0$, and $D(L_{12},L_{12}^{\prime})\neq 0$.

Similar calculation gives the following.

######  Proposition 3.3.

$X_{\gamma,L}$ has cuspidal cross caps at $u$ if and only if at $u$,
$\gamma^{\prime}\neq 0,L=0,L^{\prime}\neq 0$ and
$D(\gamma_{12}^{\prime},\gamma_{12}^{\prime\prime})\neq 0$. And $X_{\gamma,L}$
has cuspidal $S_{1}^{-}$ at $u$ if and only if at $u$, $\gamma^{\prime}\neq
0,L=0,L^{\prime}=0,L^{\prime\prime}\neq 0$ and
$D(\gamma_{12}^{\prime},\gamma_{12}^{\prime\prime})\neq 0$.

In the table 1, we summarized all conditions of propositions 3.1, 3.2 and 3.3.
Using the conditions, it is direct to find a maxface with singularities:
cuspidal-edge, cuspidal cross caps and cuspidal $S_{1}^{-}$ as in the
following:

######  Example 3.3.

Let $\delta$ be a null real analytic curve and $\mu$ be a null vector field
defined on the interval $I$ such that $\mu=\delta^{\prime}$,
$D(\delta_{12}^{\prime},\delta_{12}^{\prime\prime})\neq 0$, and both $\delta$
and $\mu$ are never zero on $I$. Let $a,b$ and $c$ be three different real
numbers on $I$. Now we construct $\gamma(u)=\delta(u)$ and
$L(u)=(u-b)(u-c)^{2}\mu(u)$. Then $\gamma$ and $L$ are Björling data for the
maxface $X_{\gamma,L}$ such that $L(u)=(u-b)(u-c)^{2}\gamma^{\prime}(u)$. We
see that

  * •

at $a$, $L\neq 0,\gamma^{\prime}\neq 0$ and
$D(\gamma_{12}^{\prime},\gamma_{12}^{\prime\prime})\neq 0,$

  * •

at $b$, $L=0,L^{\prime}\neq 0,\gamma^{\prime}\neq 0$ and
$D(\gamma_{12}^{\prime},\gamma_{12}^{\prime\prime})\neq 0$ and

  * •

at $c$, $L=0,L^{\prime}=0,L^{\prime\prime}\neq 0,\gamma^{\prime}\neq 0$ and
$D(\gamma_{12}^{\prime},\gamma_{12}^{\prime\prime})\neq 0$.

Therefore $a,b$ and $c$ are cuspidal-edge, cuspidal crosscaps and cuspidal
$S_{1}^{-}$ resp. for the maxface $X_{\gamma,L}$.

Similarly for three different real numbers $m,n$ and $p$ if we take
$\gamma^{\prime}(u)=(u-n)(u-p)^{2}\delta^{\prime}(u)$ and $L(u)=\mu(u)$, where
$\delta$ and $\mu$ are same as above, then $m,n$ and $p$ are cuspidal-edge,
swallowtails and cuspidal butterflies resp.

######  Example 3.4.

Let $\gamma(u)=(sin\,u,-cos\,u,u)$ and $L(u)=u(u-1)^{2}(cos\,u,sin\,u,1)$ be
the Björling data then $-1,0$ and $1$ are cuspidal-edge, cuspidal cross caps
and cuspidal $S_{1}^{-}$ resp.

We can construct many such examples. Moreover as we mentioned in the
introduction, other direct application of the table 1 is to find a sequence of
maxfaces converging to other types of singularities. We discuss this in the
next section.

##  4\. approximating various singularity by a cuspidal-edge

We start with an example, that will explain the essence of the main theorem
4.3 of this section.

Let $X_{\gamma,L}$ be the maxface with the singular Björling data given by

$\gamma(t)=(0,0,0),\;\;L(t)=(1-t^{2},2t,1+t^{2}).$

The maxface $X_{\gamma,L}$ has shrinking singularity on $I=(-1,1)$ (in fact on
$\mathbb{R})$. Moreover this is not a front, but below we will give a sequence
of maxface (front) converging to $X_{\gamma,L}$ and having cuspidal edge.

For $n>1$, we define

$\displaystyle
L_{n}(t)=\left(1-\frac{1}{n}\right)\left(1-t^{2},2t,1+t^{2}\right),$
$\displaystyle\gamma_{n}^{\prime}(t)=\frac{1}{n}L_{n}(t).$

[scale=0.4]approximatingcuspidal.png

Figure 1. Sequence of maxfaces having cuspidal edges that bends to shrinking
singularity

Then for each $n$, the data $\\{\gamma_{n},L_{n}\\}$ turns out to be a
singular Björling data. Let $X_{\gamma_{n},L_{n}}$ be the corresponding
maxface. Moreover for each $t\in\mathbb{R}$, we have
$\gamma_{n}^{\prime}(t)\neq 0$, $L_{n}(t)\neq 0$, and
$D(\gamma_{n12}^{\prime},\gamma_{n12}^{\prime\prime})\neq 0$. Therefore every
point on $\mathbb{R}$ is a cuspidal edge. In the figure 1, we have shown the
maxfaces $X_{\gamma_{n},L_{n}}$ for $n=3,5,15,$ and $50$.

In this example we start with a maxface having shrinking singularity and we
give a sequence of maxfaces having cuspidal edge “converging" to the
shrinking. Below we will give general discussion towards this. First we will
define the norm in which we talk about the convergence.

Let $\Omega\subset\mathbb{C}$ be a bounded simply connected domain,
$\overline{\Omega}$ be its closure. Let $X\in
C(\overline{\Omega},\mathbb{R}^{3})$, the space of continuous maps. For each
$z\in\overline{\Omega}$, we denote

$\|X(z)\|:={\rm max}\\{X_{1}(z),X_{2}(z),X_{3}(z)\\}\,{\rm
and}\,\|X\|_{\Omega}:=\sup_{z\in{\overline{\Omega}}}\|X(z)\|.$

Here $C(\overline{\Omega},\mathbb{R}^{3})$ becomes a Banach space under the
norm $\|.\|_{\Omega}$.

In the proposition below, we will give a sequence of maxfaces for general
$\\{\gamma,L\\}$.

######  Proposition 4.1.

Let $X_{\gamma,L}$ be a maxface and for $t_{0}\in I,\gamma^{\prime}\neq
0,D(\gamma_{12}^{\prime},\gamma_{12}^{\prime\prime})\neq 0$. Then there is a
sequence of maxfaces $X_{n}$ defined in a neighborhood $\Omega$ of $t_{0}$
such that each maxface $X_{n}$ has a cuspidal-edge at $t_{0}$ and $X_{n}\to
X_{\gamma,L}$ in the norm $\|.\|_{\Omega}$.

###### Proof.

As $\gamma^{\prime}(t_{0})\neq 0$, there is an interval $I_{1}$ containing
$t_{0}$ such that for all $t\in I_{1}$, $\gamma_{3}^{\prime}(t)\neq 0$.
Without loss of generality we can assume for all $t\in I_{1}$,
$\gamma_{3}^{\prime}(t)>0$. On $I_{1}$, we define
$c(t)=\dfrac{L_{3}(t)}{\gamma_{3}^{\prime}(t)}$.

For each $n$, we define $\delta_{n}$ and $\mu_{n}$ such that

$\displaystyle\delta_{n}^{\prime}=\gamma^{\prime}+\left(\frac{1}{n},\frac{1}{n},h_{n}\right);$
$\displaystyle\mu_{n}=\left(c(t)+\frac{1}{n}\right)\delta_{n}^{\prime}.$

Here
$h_{n}=-\gamma_{3}^{\prime}+\sqrt{{\gamma_{3}^{\prime}}^{2}+\color[rgb]{0,0,0}2\left(\frac{1}{n^{2}}+\frac{\gamma_{1}^{\prime}+\gamma_{2}^{\prime}}{n}\right)}$.

There is a $N$ and $I_{2}\subset I_{1}$ containing $t_{0}$ such that for all
$t\in I_{2}$ and $n>N$,
${\gamma_{3}^{\prime}}^{2}+\color[rgb]{0,0,0}2\left(\frac{1}{n^{2}}+\frac{\gamma_{1}^{\prime}+\gamma_{2}^{\prime}}{n}\right)\neq
0$, and $\frac{1}{n}\neq-c(t_{0})$.

For $n>N$, $\\{\delta_{n},\mu_{n}\\}$ turn out to be a singular Björling data
on $I_{2}$. These can be extended analytically on some domain $\mathcal{U}$
that contains $I_{2}$. We take $\Omega$ a bounded simply connected domain
containing $t_{0}$, such that $\overline{\Omega}\subset\mathcal{U}$.

Moreover we see that at $t_{0}$ and $n>N_{1}>N\color[rgb]{0,0,0}$,
$\delta_{n}^{\prime}\neq 0$, $\mu_{n}\neq 0$, and

$D(\delta_{n12}^{\prime},\delta_{n12}^{\prime\prime})\neq 0.$

Therefore for $n>N_{1}\color[rgb]{0,0,0}$, the maxfaces
$X_{\delta_{n},\mu_{n}}$ for the singular Björling data
$\\{\delta_{n},\mu_{n}\\}$, has cuspidal-edge at $t_{0}$ and hence cuspidal
edge in an interval containing $t_{0}$.

Let $z\in\Omega,$ we have
$X_{\delta_{n},\mu_{n}}(z)-X_{\gamma,L}(z)=Re\int_{u_{0}}^{z}(\delta_{n}^{\prime}(w)-\gamma^{\prime}(w))(1-i(c(w)+\frac{1}{n}))\,dw.$
It is direct to see that $\|X_{\delta_{n},\mu_{n}}-X_{\gamma,L}\|_{\Omega}\to
0$.

∎

######  Remark 4.1.

If we have a maxface $X_{\gamma,L}$ with $L\neq 0$ and
$D(L_{12},L_{12}^{\prime})\neq 0$ at $0$, then with a little change we have a
sequence of functions $g_{n}$ (similar to $h_{n}$ in the above proposition)
and we can take

$\mu_{n}=L+\left(\frac{1}{n},\frac{1}{n},g_{n}\right)\mbox{ and
}\delta_{n}^{\prime}=\left(d(t)+\frac{1}{n}\right)\mu_{n}.$

With similar argument as above we find a sequence of maxfaces
$X_{\delta_{n},\mu_{n}}$ with singular Björling data
$\\{\delta_{n},\mu_{n}\\}$ having cuspidal-edge at $0$ and
$X_{\delta_{n},\mu_{n}}\to X_{\gamma,L}$ in the norm $\|.\|_{\Omega}.$

######  Remark 4.2.

For a constant null curve $\gamma$ and a null vector field $L$ such that for
all $t$, $D(L_{12},L_{12}^{\prime})\neq 0$. The maxface $X_{\gamma,L}$ has
shrinking singularity. For this case we can choose $\gamma_{n}$ and $L_{n}$
similar to the example at the beginning of the section. Moreover little
variation will hold for the folded singularity as well.

We conclude the article with the following theorem which is a direct
consequence of the above proposition 4.1 and remarks 4.1, 4.2.

######  Theorem 4.3.

Let $X_{\gamma,L}$ be the maxface with singular Björling data $\\{\gamma,L\\}$
such that at $t_{0}\in I$, it has shrinking or folded singularity or any of
the singular point as in table 1. Then there is a sequence of maxfaces $X_{n}$
defined on a domain $\Omega$ containing $t_{0}$, such that each $X_{n}$ has
cuspidal-edge at $t_{0}$. Moreover $X_{n}\to X_{\gamma,L}$ in norm
$\|.\|_{\Omega}$.

##  5\. acknowledgement

Authors are very thankful to the anonymous referees for their valuable
comments which helped a lot to improve the article.

## References


# Permutation tests for quantum state identity

Harry Buhrman1<EMAIL_ADDRESS>1QuSoft, University of Amsterdam &
Quantinuum, Partnership House, Carlisle Place, London  ,  Dmitry Grinko2
<EMAIL_ADDRESS>2QuSoft, University of Amsterdam, Amsterdam, The
Netherlands  ,  Philip Verduyn Lunel3<EMAIL_ADDRESS>3QuSoft,
CWI, Amsterdam, The Netherlands  and  Jordi Weggemans3<EMAIL_ADDRESS>
###### Abstract.

The quantum analogue of the equality function, known as the quantum state
identity problem, is the task of deciding whether $n$ unknown quantum states
are equal or unequal, given the promise that all states are either pairwise
orthogonal or identical. Under the one-sided error requirement, it is known
that the permutation test is optimal for this task, and for two input states
this coincides with the well-known Swap test. Until now, the optimal
measurement in the general two-sided error regime was unknown. Under more
specific promises, the problem can be solved approximately or even optimally
with simpler tests, such as the circle test.

This work attempts to capture the underlying structure of (fine-grained
formulations of) the quantum state identity problem. Using tools from semi-
definite programming and representation theory, we (i) give an optimal test
for any input distribution without the one-sided error requirement by writing
the problem as an SDP, giving the exact solutions to the primal and dual
programs and showing that the two values coincide; (ii) propose a general
$G$-test which uses an arbitrary subgroup $G$ of $\operatorname{S}_{n}$,
giving an analytic expression of the performance of the specific test, and
(iii) give an approximation of the permutation test using only a classical
permutation and $n-1$ Swap tests.

###### Contents

  1. 1 Introduction
    1. 1.1 Our results
      1. 1.1.1 The optimal test
      2. 1.1.2 The $G$-test
      3. 1.1.3 Approximation by the Iterated Swap Tree
  2. 2 Preliminaries
    1. 2.1 Notation
    2. 2.2 Representation theory background
      1. 2.2.1 Weingarten calculus
    3. 2.3 Semidefinite programming
  3. 3 The permutation test
    1. 3.1 The SDP formulation of the optimal measurement for Haar-random inputs
    2. 3.2 Unknown is the same as Haar-random
    3. 3.3 Warm-up: optimality for $\mu=(n-h,h)$ with $p=1/2$
    4. 3.4 The general setting
  4. 4 The $G$-test
    1. 4.1 The Circle test
    2. 4.2 The Iterated Cyclic Wreath test
  5. 5 Approximation of the permutation test by the Iterated Swap Tree
    1. 5.1 The Iterated Swap Tree protocol
    2. 5.2 A recursive upper bound
  6. 6 Discussion and open problems

##  1\. Introduction

One of the most basic tasks in quantum information is to compare two or more
unknown quantum states. In particular, we will be interested in a quantum
version of the equality function, known as the quantum state identity problem
($\textup{QSI}_{n}$) [KNY08]. Here one is given $n$ unknown quantum states
$\ket{\psi_{1}},\ket{\psi_{2}}\dots,\ket{\psi_{n}}$, each of local dimension
$d$, with the promise that all states are either pairwise orthogonal or
identical. Given as an input such a collection of unknown states satisfying
the promise, the task is now to decide whether the input states are all equal
or not, with high probability.

For two input states, the corresponding problem $\textup{QSI}_{2}$ can be
solved by the so-called _Swap Test_ [BBD+97, BCWd01]. The Swap test applies,
controlled by a qubit in the $\ket{+}$ state in the first register, a
controlled Swap operation to the input states, followed by a Hadamard
operation and measurement in the computational basis of the first register.
The controlled swap operation can be viewed as applying in superposition all
permutations of the symmetric group $\operatorname{S}_{2}$ to the input
states, which consists of only the identity and swap of both input states. It
is known that under the so-called _one-sided error requirement_ , i.e. when
the algorithm has to be always correct on equal inputs, the Swap Test is
optimal for $\textup{QSI}_{2}$ [KMY01, dB04]. For arbitrary $n$, one can use
generalizations of the Swap test like the circle test or the permutation test
[BBD+97, BCWd01, KNY08]. Both tests extend the Swap test in the sense that
they perform in superposition all permutations from a subgroup of the
symmetric group $\operatorname{S}_{n}$: for the circle test this is the cyclic
group $\textup{C}_{n}$ and for the permutation test the subgroup is
$\operatorname{S}_{n}$ itself. Kada, Nishimura and Yamakami proved the
optimality of the permutation test for $\textup{QSI}_{n}$ for arbitrary $n$
under the one-sided error requirement [KNY08]. It was not known whether both
tests are still optimal once the one-sided error requirement is relaxed.

So even though the permutation test is optimal under the one-sided error
requirement, its circuit complexity is considerable as it uses the inverse
quantum Fourier transform. [KNY08] showed that when $n$ is prime, the circle
test achieves the same optimal soundness error for $\textup{QSI}_{n}$, but
saves an exponential number of gates as compared to the permutation test as
the Fourier transform is only applied to a register of exponentially smaller
dimension. This suggests that even though the permutation test is information-
theoretically optimal, there might be many specific instances of
$\textup{QSI}_{n}$ for which other tests have better circuit complexity whilst
still being optimal. Something similar was observed in [CDM+18], where a Swap
test-based circuit was shown to be optimal for $\textup{QSI}_{n}$ when the
problem satisfies the promise that there is just one state different and it
can only be at a known location.

Moreover, if one slightly relaxes the requirement of optimality, [KNY08]
showed that when one randomly permutes the input before the circle test is
performed, it approximates the permutation test in the sense that it retains
perfect completeness and the dominant term in the soundness error achieves the
same scaling up to a multiplicative factor smaller than $2$, which holds for
arbitrary $n$ instead of just prime numbers. They also gave an approximation
procedure based on the Swap test to approximate $\textup{QSI}_{3}$, for which
both the Circle test and Permutation test are optimal.

These results hint at some underlying mathematical structure in
$\textup{QSI}_{n}$, which is currently not fully understood. Using tools from
representation theory and semidefinite programming and by fine-graining the
promises of the quantum state identity problem, this work seeks to unravel
this structure, allowing us to answer some of the 15-year-old open questions
related to the quantum state identity problem.

###  1.1. Our results

Write $\mu\mathbin{\vdash}n$ for a partition of the number $n$, that is
$\mu=(\mu_{1},\dots,\mu_{d})$ such that $\mu_{1}\geq\dotsc\geq\mu_{d}\geq 0$
and $\sum_{i=1}^{d}\mu_{i}=n$. We also write $\lambda\mathbin{\vdash}_{d}n$ to
mean that $\lambda$ is a partition of at most $d$ parts, i.e. for every $i>d$
we have $\lambda_{i}=0$. We associate with $\mu$ corresponding quantum state
$\ket{1^{\mu_{1}}2^{\mu_{2}}\dotsc d^{\mu_{d}}}$, where
$\ket{i^{\mu_{1}}}\vcentcolon=\ket{i}^{\otimes\mu_{i}}$ for a basis state
$\ket{i}$ from a Hilbert space of local dimension $d$. Note that the number of
non-zero entries in $\mu$ specifies the total number of different basis states
in the input state. We can now define several formulations of the quantum
state identity problem.

######  Definition 1 (Quantum State Identity problems).

Let $d\in\mathbb{N}$, $p\in[0,1]$. We consider the following promise problems
given by the following input, promise and output:
Input: $n$ unknown quantum states
$\ket{\psi_{1}},\ket{\psi_{2}}\dots,\ket{\psi_{n}}$, each of local dimension
$d$ and pairwise orthogonal or identical.
Promise: We have that either

  1. (i)

All $\ket{\psi_{i}}$ are identical.

  2. (ii)

We have one of the promises for each of the following problems:

    1. $\textup{QSI}_{\mu}^{p}$:

One is given some $\mu\mathbin{\vdash}n$ with $\mu_{2}>0$ such that
$\ket{\psi_{1}}\ket{\psi_{2}}\dots\ket{\psi_{n}}=U^{\otimes
n}\ket{1^{\mu_{1}}2^{\mu_{2}}\dotsc d^{\mu_{d}}}$ for some unknown unitary $U$
of dimension $d$;

    2. $\widetilde{\textup{QSI}}_{\mu}^{p}$:

One is given some $\mu\mathbin{\vdash}n$ with $\mu_{2}>0$ such that
$\ket{\psi_{\sigma(1)}}\ket{\psi_{\sigma(2)}}\dots\ket{\psi_{\sigma(n)}}=U^{\otimes
n}\ket{1^{\mu_{1}}2^{\mu_{2}}\dotsc d^{\mu_{d}}}$ for some unknown unitary $U$
of dimension $d$ and some unknown permutation $\sigma$.

    3. ${\textup{QSI}}_{n}^{p}$:

There exist an $i,j\in[n]$ such that $\ket{\psi_{i}}$, $\ket{\psi_{j}}$ are
pairwise orthogonal.

Moreover, one is promised that (i) happens with probability $p$ and (ii) with
$1-p$. If $p$ is not specified (denoted ${\textup{QSI}_{\mu}}$), one can
assume that $p=1/2$.
Output: Return ‘ _equal_ ’ in case (i) and ‘ _not equal_ ’ in case (ii).

Similar to the type I and type II errors in hypothesis testing, we refer the
the probability of being correct in case (i) as the _completeness_ probability
and in case (ii) as _soundness_ probability. The overall success probability
is then the average over both the completeness and soundness cases, weighted
according to the prior $\\{p,1-p\\}$. When we say perfect completeness (or
soundness), we mean that the probability of being correct in this case is $1$.

Note that the quantum state identity problems are stated in such a way that
the promise in each formulation captures less information as we go from top to
bottom. QSIμp captures the setting where one has all the information on where
different states are located, as one can simply relabel the input states to
obtain this form. This captures for example the setting of [CDM+18] where
$\mu=(n-1,1,0,\dots,0)$. In ~QSIμp, all the information one has is in knowing
how many states $h$ out of $n$ are different, since this is given by the
number of non-zero entries in $\mu$. Finally, QSIn is the usually adopted
definition of the quantum state identity problem as given in [KNY08], where in
case (ii) one knows nothing of the location, nor how many of the states are
different, except that there is at least one.

As an interesting comparison, in [BLM+22] the authors give an optimal way to
compute any symmetric, equivariant Boolean function in an unknown quantum
basis, such as the majority and parity function. When we restrict ourselves to
the qubit case input, we see what we actually compute is the OR-function,
which is not an equivariant Boolean function, in a unknown quantum basis.

####  1.1.1. The optimal test

Our first result is a very general characterization of the optimality of the
Permutation Test for quantum state identity problems.

######  Theorem 1 (Informal, from Theorem 5).

Suppose that the unequal and equal cases of the quantum state identity
problems, as per Definition 1, occur equally likely. Then for any
$\mu\mathbin{\vdash}n$ (known or unknown), the permutation test is optimal for
all quantum state identity problems, satisfies perfect completeness, and has
soundness

$\displaystyle 1-\frac{1}{\binom{n}{\mu}},$

where $\binom{n}{\mu}\vcentcolon=\frac{n!}{\mu_{1}!\dotsc\mu_{d}!}$ is a
multinomial coefficient.

Several interesting conclusions can be drawn from Theorem 1:

  1. (1)

Relaxing the one-sided error requirement does not make the average success
probability (averaged over the unequal and equal cases) higher, answering an
open question by [KNY08].

  2. (2)

Similarly, knowing where the different states are located also does not
increase one’s capacity to increase the overall success probability.

  3. (3)

The permutation test will on most inputs perform much better than the worst-
case instances that have $1/n$ soundness error, which are the inputs where
only one state is different from all the others.

If $p\neq\frac{1}{2}$, then the permutation test is still optimal for all
$p\geq p^{*}(\mu)$, where $p^{*}(\mu):=\frac{1}{1+\binom{n}{\mu}}$. For all
$p<p^{*}(\mu)$ the optimal test is to always output ‘not equal’ (Theorem 5).

Our proof is based on an SDP formulation of finding the measurement that
maximizes the success probability given the ‘equal’ case with probability $p$.
Our SDP considers input states that have been acted upon by a Haar random
unitary. This is to some extent too strong an assumption: not only is the
basis unknown to the problem solver, the basis is also ‘unknown to the
universe’! In an adversarial setting, where an all-powerful entity could pick
any measure over the unitary group to be applied to the input states, the
input states would still be unknown but the Haar measure might not be the
hardest input distribution to solve. However, we show that this assumption can
be made without loss of generality, exploiting a special property of the
structure of the permutation test which is the optimal solution to our SDP
(Subsection 3.2)

####  1.1.2. The $G$-test

Whilst Theorem 1 fully resolves the quantum state identity problem in terms of
determining the optimal information-theoretic measurement, it might for some
be still ‘too blunt of a tool’ as its circuit complexity is considerable. In
that case, one might be able to resort to other tests with smaller circuit
complexity because (i) more is known about the type of inputs or (ii) one is
only interested in a sub-optimal performance guarantee. For example, the
circle test is optimal for $n$ is prime and a good approximation for arbitrary
$n$ when the circle test is preceded by a random (classical) permutation of
the input states [KNY08].

Using these ideas, we define a general notion of a so-called $G$-test, which
does the following.

  1. (1)

Randomly permute the labels of the input states.

  2. (2)

Apply the permutation test for a subgroup $G\subseteq\operatorname{S}_{n}$
(see Algorithm 3).

######  Theorem 2.

Let $G$ be any subgroup of $\operatorname{S}_{n}$. Then the $G$-test has
perfect completeness and soundness

$\mathbb{P}^{G}_{s}(\mu)=1-\frac{1}{\binom{n}{\mu}}\sum_{\begin{subarray}{c}\lambda\mathbin{\vdash}_{d}n\end{subarray}}K_{\lambda,\mu}r^{G}_{\lambda},$

where $K_{\lambda,\mu}$ are Kostka numbers, $r^{G}_{\lambda}$ is the
multiplicity of the trivial irrep of the subgroup
$G\subseteq\operatorname{S}_{n}$ inside the irrep $\lambda$ of the symmetric
group $\operatorname{S}_{n}$.

The derivation of Theorem 2 can be found in Section 4, where we also briefly
touch upon the cases of $G$ being the cyclic group $\textup{C}_{n}$ (which
captures the RCIR test of [KNY08]) as well as an iterated wreath product of
the cyclic groups.

####  1.1.3. Approximation by the Iterated Swap Tree

Whilst Theorem 2 in principle contains all the information to compute the
performance of any $G$-test, this might in practice be quite laborious for
most subgroups $G$. In particular, we will also consider a test that consists
solely of a classical permutation followed by Swap tests in a sort of tree
structure, which is captured by the iterated wreath product [OOR04, IW18].
This test, which we call the _Iterated Swap Tree_ (IST), works on any input
size that is a power of two and only uses a random classical permutation and
$n-1$ Swap tests. It can be viewed as a generalization of the test as proposed
in [CDM+18], with the extra advantage that it no longer needs to have in the
unequal case a promise that the different state is located in the first
register.

Using different techniques and ideas, we provide a recursive upper bound on
the error probability as a function of the number of different states $h$ and
the total number of input states $n$.

######  Theorem 3 (Informal, from Theorem 6 and Corollary 3).

For any $n$ that is a power of two the Iterated Swap Tree achieves perfect
completeness and has soundness lower bounded by

$\mathbb{P}^{\mathrm{IST}}_{s}(n,h)\geq
1-\frac{\gamma(h,\log_{2}(n))}{\binom{n}{h}},$ (1)

where $\gamma(h,m)$ satisfies a recurrence relation with the boundary
conditions $\gamma(0,m)=\gamma(1,m)=1$. Moreover, for any fixed $h$ we have
that $\gamma(h,\log_{2}(n))$ is a polynomial in $\log_{2}(n)$ of degree $h-1$,
which implies that there exists a $n_{0}\in\mathbb{N}$ such that for all
$n\geq n_{0}$ the test achieves the optimal soundness $\geq 1-1/n$.

Our proof is based on the combinatorics of what we call ‘clicks’, which are
potential detection locations where the inputs to a Swap test within the
Iterated Swap Tree have the possibility of being detected. Since for unequal
input states this happens with probability $\frac{1}{2}$, the problem boils
down to computing the expectation value
$\mathbb{E}_{\sigma}[\left(\frac{1}{2}\right)^{c(h,m,\sigma)}]$, where
$c(h,m,\sigma)$ is a function that gives the total number of clicks given
$n=2^{m}$ input states of which $h$ are different and a permutation $\sigma$.
The fact that we take the expectation value over all permutations comes from
the random permutation of the labels we perform, and this is necessary since
one can easily show that the test would otherwise have large soundness error
on some specific instances (in this case, it would be to have the first and
second half of the states different, but identical within the halves
themselves).

##  2\. Preliminaries

###  2.1. Notation

Let $n\geq 0$ be an integer. We write $\lambda\mathbin{\vdash}n$ to mean that
$\lambda$ is a _partition_ of $n$, i.e.,
$\lambda=(\lambda_{1},\dotsc,\lambda_{d})$ for some $d$ where
$\lambda_{1}+\dotsb+\lambda_{d}=n$ and
$\lambda_{1}\geq\dots\geq\lambda_{d}\geq 0$. The _size_ of partition $\lambda$
is $\absolutevalue{\lambda}=n$. We say that $\lambda$ has _length_
$\ell(\lambda)=k$ if $\lambda_{k}>0$ and $\lambda_{k+1}=0$. We use the
notation $\lambda\mathbin{\vdash}_{d}n$ to indicate that
$\lambda\mathbin{\vdash}n$ and $\ell(\lambda)\leq d$. The _Young diagram_ of
partition $\lambda$ is a collection of $n$ _cells_ arranged in $\ell(\lambda)$
rows, with $\lambda_{i}$ of them in the $i$-th row.

###  2.2. Representation theory background

Broadly speaking, representation theory studies how one can represent general
algebraic objects such as groups, associative algebras and Lie algebras as
linear operators with matrix multiplication preserving the original algebraic
operations. The fundamental concept here is of _irreducible representation_
(also simply called ”irrep”), i.e. a representation (also called ”module”)
which does not have (as a vector space) any invariant subspaces under the
action of the represented group or algebra. When studying the actions of
general groups on a given vector space it is useful to understand how this
representation decomposes into irreducible representations of the given group
and other relevant algebraic structures.

A canonical example of such an approach is _Schur–Weyl duality_ which
describes the following situation. Suppose that you study the diagonal action
of the unitary group $\mathrm{U}_{d}$ on the vector space
$(\operatorname{\mathbb{C}}^{d})^{\otimes n}$. It turns out that the commutant
of this action is spanned by permutation operators $\sigma$ from the symmetric
group $\operatorname{S}_{n}$ and vice versa: the commutant of
$\operatorname{S}_{n}$ in $(\operatorname{\mathbb{C}}^{d})^{\otimes n}$ is
spanned by $U^{\otimes n}$ where $U\in\mathrm{U}_{d}$. In turn, we can
decompose $(\operatorname{\mathbb{C}}^{d})^{\otimes n}$ into irreducible
representations of unitary and symmetric groups:

$(\operatorname{\mathbb{C}}^{d})^{\otimes
n}\cong\bigoplus_{\lambda\mathbin{\vdash}_{d}n}W_{\lambda}\otimes
V_{\lambda},$ (2)

where $W_{\lambda}$ is so-called _Weyl module_ , i.e. an irreducible
representation of $\mathrm{U}_{d}$, and $V_{\lambda}$ is so-called _Specht
module_ , i.e. an irreducible representation of $\operatorname{S}_{n}$. The
dimensions of these irreps we denote by

$d_{\lambda}\vcentcolon=\dim(V_{\lambda}),\qquad
m_{\lambda,d}\vcentcolon=\dim(W_{\lambda}).$ (3)

The isomorphism in eq. 2 can be achieved via a unitary $U_{\mathrm{Sch}}$
called _Schur transform_ [BCH06, Har05, KS18, WS23, GBO23, Ngu23]. In
particular, we can introduce the _isotypic projectors_ $\Pi_{\lambda}$ as
follows:

$U_{\mathrm{Sch}}\Pi_{\lambda}U_{\mathrm{Sch}}^{\dagger}=\bigoplus_{\mu\mathbin{\vdash}_{d}n}\delta_{\mu,\lambda}I_{\mu}\otimes
I_{\mu}.$ (4)

####  2.2.1. Weingarten calculus

One crucial tool which we need is _Weingarten calculus_ [CŚ06, CMN22]. It is a
set of results on integration with respect to the Haar measure of the unitary
group. In particular, we need the following result [CŚ06, Proposition 2.3]
regarding an integral of an arbitrary matrix
$X\in\operatorname{End}((\operatorname{\mathbb{C}}^{d})^{\otimes n})$:

$\int U^{\otimes n}XU^{\dagger\otimes
n}dU=\left\lparen\sum_{\sigma\in\operatorname{S}_{n}}\Tr[X\psi(\sigma^{-1})]\psi(\sigma)\right\rparen\Bigg{\lparen}\frac{1}{n!}\sum_{\begin{subarray}{c}\lambda\mathbin{\vdash}_{d}n\end{subarray}}\frac{d_{\lambda}}{m_{\lambda,d}}\Pi_{\lambda}\Bigg{\rparen},$
(5)

where we formally defined an action of $\operatorname{S}_{n}$ on
$(\operatorname{\mathbb{C}}^{d})^{\otimes n}$ which permutes the registers as
the representation
$\psi:\operatorname{S}_{n}\rightarrow\operatorname{End}((\operatorname{\mathbb{C}}^{d})^{\otimes
n})$.

###  2.3. Semidefinite programming

_Semidefinite programming_ is an important subfield of optimization [WSV12]
that has numerous applications in quantum information theory [ST21, Wat18]. A
typical formulation of a _semidefinite program_ (SDP) has the form [WSV12,
Section 1.1]:

$\displaystyle f\vcentcolon=\max_{X}$ $\displaystyle\Tr\lparen
C^{\mathsf{T}}X\rparen\quad\textrm{s.t.}\quad\Tr\lparen
A_{i}^{\mathsf{T}}X\rparen=b_{i}\quad\forall i\in[m],\quad X\succeq 0,$ (6)

where $X$ is a Hermitian matrix variable, $C$ and $A_{i}$ are constant
Hermitian matrices, and $b_{i}$ are real constants. For this _primal_
semidefinite program there always exists the _dual_ semidefinite program:

$\displaystyle f^{*}\vcentcolon=\min_{y\in\mathbb{R}^{m}}$ $\displaystyle
y^{\mathsf{T}}b\quad\textrm{s.t.}\quad\sum_{i=1}^{m}y_{i}A_{i}\succeq C.$ (7)

There is an important property called _weak duality_ which always holds:

$f^{*}\geq f.$ (8)

This property allows to prove the optimality of a candidate feasible solution
of the primal SDP by exhibiting a feasible solution of the dual program which
matches the value of the primal objective function. This method of proving
optimality is used in Section 3.

##  3\. The permutation test

For a subgroup $G\subseteq\operatorname{S}_{n}$, let $F_{G}$ be the quantum
Fourier transform that operates on a Hilbert space of dimension $|G|$, that is
the order of a permutation group $G$. Also, define the controlled permutation
operation $C$ as the map that implements

$\displaystyle
C:\ket{\sigma}\ket{\psi_{1}}\ket{\psi_{2}}\dots\ket{\psi_{n}}\mapsto\ket{\sigma}\ket{\psi_{\sigma^{-1}(1)}}\ket{\psi_{\sigma^{-1}(2)}}\dots\ket{\psi_{\sigma^{-1}(n)}}.$
(9)

Algorithm 1: The Permutation Test for a subgroup
$G\subseteq\operatorname{S}_{n}$. Input: $n$ quantum states
$\ket{\psi_{1}}\otimes\ket{\psi_{2}}\otimes\dots\otimes\ket{\psi_{n}}$, each
of local dimension $d$.
(1) Start with the initial state
$\ket{0}\ket{\psi_{1}}\ket{\psi_{2}}\dots\ket{\psi_{n}}$, where we denote the
$|G|$-dimensional register containing $\ket{0}$ as $P$ and the register with
the input states as $R$. (2) Apply $F_{G}$ to register $P$. (3) Apply $C$ to
register $R$, controlled by register $P$. (4) Apply $F_{G}^{\dagger}$ to $P$
and measure register $P$. If the outcome is $0$, return equal, otherwise
return not equal.

If $G=\operatorname{S}_{n}$ then the corresponding test is known as the
permutation test, for $G=\textup{C}_{n}$ the circle test [KNY08] and for
$G=\operatorname{S}_{2}$ the Swap test [BCWd01]. If the final measurement
outcome is $\ket{0}$, the circuit has projected the input state onto the
subspace containing all permutations $\sigma\in G$, a technique that was first
proposed in [BBD+97]. In this subsection, we will focus solely on
$G=\operatorname{S}_{n}$, and come back to the general setting of an arbitrary
subgroup $G$ in Section 4.

###  3.1. The SDP formulation of the optimal measurement for Haar-random
inputs

To prove that in general that the permutation test gives the best probability
of success for pure state equality testing we write the problem of finding the
optimal measurement as an SDP. We consider two cases of the inputs. One where
the order of the input in the unequal case is known, and one where the inputs
are randomly permuted. We then show that there exists a feasible solution to
the dual that coincides with the success probability of the permutation test
for the case where the input order is known. Furthermore, we see that the
permutation test is agnostic about the order of the inputs and achieves the
same success probability on the randomly permuted input as on the ordered
input. Therefore knowing the ordering in advance does not increase the optimal
success probability. We define these different cases for equal or unequal
qudit inputs as follows:

$\displaystyle\rho_{\neq}^{\mu}$ $\displaystyle:=\int U^{\otimes
n}\ket{1^{\mu_{1}}2^{\mu_{2}}\dotsc
d^{\mu_{d}}}\bra{1^{\mu_{1}}2^{\mu_{2}}\dotsc
d^{\mu_{d}}}(U^{\dagger})^{\otimes n}dU,$ (10)
$\displaystyle\tilde{\rho}_{\neq}^{\mu}$
$\displaystyle:=\frac{1}{n!}\sum_{\pi\in\operatorname{S}_{n}}\psi(\pi)\rho_{\neq}^{\mu}\psi(\pi^{-1}),$
(11) $\displaystyle\rho_{=}^{n}$ $\displaystyle:=\int U^{\otimes
n}\ket{1^{n}}\bra{1^{n}}(U^{\dagger})^{\otimes n}dU,$ (12)

where $\mu\mathbin{\vdash}n$ is some partition of $n$ with $\mu_{2}>0$,111The
condition $\mu_{2}>0$ is assumed automatically everywhere in this paper for
the state $\rho^{\mu}_{\neq}$. On the other hand, the state $\rho^{n}_{=}$
corresponds to $\mu=(n)$. Therefore, one can think about subscripts as
follows: ”$=$” means $\mu_{2}=0$, while ”$\neq$” means $\mu_{2}>0$. and we
integrate with respect to the Haar measure on the unitary group
$\mathbb{U}(d)$.222Without loss of generality, we consider the Haar-random
unitaries. The reason for that is explained in Section 3.2. The task is now to
find a POVM set that discriminates optimally between the two. We can exactly
find the optimal discrimination using an SDP [BV04]. The SDP that optimizes
over all POVMs for the ordered inputs can be written as follows:

Primal Program maximize: $\displaystyle
p\Tr[\Pi_{=}\rho_{=}^{n}]+(1-p)\Tr[\Pi_{\neq}\rho_{\neq}^{\mu}]$ subject to:
$\displaystyle\Pi_{=}+\Pi_{\neq}=\mathbbm{1}_{d^{n}}$
$\displaystyle\Pi_{=}\succeq 0,$ $\displaystyle\Pi_{\neq}\succeq 0.$

Dual Program minimize: $\displaystyle\Tr[Y]$ subject to: $\displaystyle
Y-p\rho_{=}^{n}\succeq 0,$ (13) $\displaystyle Y-(1-p)\rho_{\neq}^{\mu}\succeq
0,$ $\displaystyle Y\in\text{Herm}((\mathbb{C}^{d})^{\otimes n}).$

To solve the above SDP we would need the following crucial Lemma.

######  Lemma 1.

Let $\mu=(\mu_{1},\dotsc,\mu_{d})$ be some partition of $n$. Define

$\displaystyle\rho_{\neq}^{\mu}$ $\displaystyle\vcentcolon=\int U^{\otimes
n}\ket{1^{\mu_{1}}2^{\mu_{2}}\dotsc
d^{\mu_{d}}}\bra{1^{\mu_{1}}2^{\mu_{2}}\dotsc
d^{\mu_{d}}}(U^{\dagger})^{\otimes
n}dU,\qquad\tilde{\rho}_{\neq}^{\mu}\vcentcolon=\frac{1}{n!}\sum_{\pi\in\operatorname{S}_{n}}\psi(\pi)\rho_{\neq}^{\mu}\psi(\pi^{-1}).$

Then

$\displaystyle\rho_{\neq}^{\mu}$
$\displaystyle=\frac{1}{\binom{n}{\mu}}\sum_{\begin{subarray}{c}\lambda\mathbin{\vdash}_{d}n\end{subarray}}\frac{d_{\lambda}}{m_{\lambda,d}}\left\lparen\Pi_{(\mu_{1})}\otimes\dotsc\otimes\Pi_{(\mu_{d})}\right\rparen\Pi_{\lambda},\qquad\tilde{\rho}_{\neq}^{\mu}=\frac{1}{\binom{n}{\mu}}\sum_{\begin{subarray}{c}\lambda\mathbin{\vdash}_{d}n\end{subarray}}\frac{K_{\lambda\mu}}{m_{\lambda,d}}\Pi_{\lambda},$
(14)

where $\binom{n}{\mu}\vcentcolon=\frac{n!}{\mu_{1}!\dotsc\mu_{d}!}$ is a
multinomial coefficient, $K_{\lambda\mu}$ is the Kostka number and
$\Pi_{\lambda}\in\operatorname{End}\lparen(\operatorname{\mathbb{C}}^{d})^{\otimes
n}\rparen$ is the isotypic projector onto $\lambda$ irrep in the tensor
representation of the symmetric group $\operatorname{S}_{n}$. In particular,
$\Pi_{(n)}=\frac{1}{n!}\sum_{\pi\in\operatorname{S}_{n}}\psi(\pi)$ and
$\Pi_{(\mu_{i})}=\frac{1}{n!}\sum_{\pi\in\operatorname{S}_{\mu_{i}}}\psi(\pi)$,
where $\operatorname{S}_{\mu_{i}}$ is understood as a subgroup of
$\operatorname{S}_{n}$ acting on the corresponding systems from the partition
$\mu$ of $n$. In particular, for $\mu=(n)$ we have:

$\rho_{=}^{n}\vcentcolon=\rho_{\neq}^{(n)}=\tilde{\rho}_{\neq}^{(n)}=\frac{\Pi_{(n)}}{\binom{n+d-1}{n}},$
(15)

###### Proof.

Let $\chi^{\lambda}$ be the character of the irrep $\lambda$ of the symmetric
group $\operatorname{S}_{n}$ and $s_{\lambda}$ is the Schur polynomial in $d$
variables, i.e. it is the character of the unitary group $\mathbb{U}(d)$. The
dimensions of the irreps of symmetric and unitary groups are
$d_{\lambda}=\chi^{\lambda}(e)$ and $m_{\lambda,d}=s_{\lambda}(1,\dotsc,1)$.
Let
$\psi:\operatorname{\mathbb{C}S}_{n}\rightarrow\mathrm{End}\lparen(\operatorname{\mathbb{C}}^{d})^{\otimes
n}\rparen$ be the tensor representation of the symmetric group
$\operatorname{S}_{n}$ acting on $(\operatorname{\mathbb{C}}^{d})^{\otimes
n}$. Using the Weingarten calculus [CŚ06, Proposition 2.3] we get the
following:

$\displaystyle\rho_{\neq}^{\mu}$
$\displaystyle=\left\lparen\sum_{\sigma\in\operatorname{S}_{n}}\Tr[\ket{1^{\mu_{1}}\dotsc
d^{\mu_{d}}}\bra{1^{\mu_{1}}\dotsc
d^{\mu_{d}}}\psi(\sigma^{-1})]\psi(\sigma)\right\rparen\Bigg{\lparen}\frac{1}{n!}\sum_{\begin{subarray}{c}\lambda\mathbin{\vdash}_{d}n\end{subarray}}\frac{d_{\lambda}}{m_{\lambda,d}}\Pi_{\lambda}\Bigg{\rparen}$
(16) $\displaystyle=\Bigg{\lparen}\sum_{\sigma\in
S_{\mu_{1}}\times\dotsc\times
S_{\mu_{d}}}\psi(\sigma)\Bigg{\rparen}\Bigg{\lparen}\frac{1}{n!}\sum_{\begin{subarray}{c}\lambda\mathbin{\vdash}_{d}n\end{subarray}}\frac{d_{\lambda}}{m_{\lambda,d}}\Pi_{\lambda}\Bigg{\rparen}=\bigg{\lparen}\mu_{1}!\dotsc\mu_{d}!\,\Pi_{(\mu_{1})}\otimes\dotsc\otimes\Pi_{(\mu_{d})}\bigg{\rparen}\Bigg{\lparen}\frac{1}{n!}\sum_{\begin{subarray}{c}\lambda\mathbin{\vdash}_{d}n\end{subarray}}\frac{d_{\lambda}}{m_{\lambda,d}}\Pi_{\lambda}\Bigg{\rparen}$
(17)
$\displaystyle=\frac{\mu_{1}!\dotsc\mu_{d}!}{n!}\sum_{\begin{subarray}{c}\lambda\mathbin{\vdash}_{d}n\end{subarray}}\frac{d_{\lambda}}{m_{\lambda,d}}\left\lparen\Pi_{(\mu_{1})}\otimes\dotsc\otimes\Pi_{(\mu_{d})}\right\rparen\Pi_{\lambda}$
(18)

Therefore, the twirling of $\rho_{\neq}^{\mu}$ with respect to the symmetric
group $\operatorname{S}_{n}$ is

$\displaystyle\tilde{\rho}_{\neq}^{\mu}$
$\displaystyle=\frac{1}{n!}\sum_{\pi\in\operatorname{S}_{n}}\psi(\pi)\rho_{\neq}^{\mu}\psi(\pi^{-1})=\frac{\mu_{1}!\dotsc\mu_{d}!}{n!}\sum_{\begin{subarray}{c}\lambda\mathbin{\vdash}_{d}n\end{subarray}}\frac{K_{\lambda\mu}}{m_{\lambda,d}}\Pi_{\lambda},$
(19)

where we used Schur’s lemma, the definition of the _permutation module_ and
_Kostka numbers_ $K_{\lambda\mu}$ coming from the so-called Young’s Rule
[Sag13]. In particular, for $\mu=(n)$ we have

$\rho_{=}^{n}=\rho_{\neq}^{(n)}=\tilde{\rho}_{\neq}^{(n)}=\frac{\Pi_{(n)}}{\binom{n+d-1}{n}},$
(20)

where $\Pi_{(n)}$ is the projector onto the symmetric subspace of $n$ qudits,
$(n)$ denotes a Young diagram corresponding to the symmetric subspace and
$m_{(n),d}=\binom{n+d-1}{n}$ [Har13]. ∎

###  3.2. Unknown is the same as Haar-random

In the definition of $\mathsf{QSI}_{\mu}^{p}$, we assume that the input is
given via unknown $d$ dimensional unitary $U$. What this means is that the
underlying distribution over the unitaries is unknown in principle and can be
chosen adversarially, i.e. we aim to find a minimal value of the average
success probability over all possible distributions. More abstractly, if we
have some optimization problem

$f(q)\vcentcolon=\sup_{x}g(x,q),$ (21)

where $q$ is some measure over $d$ dimensional unitaries and $g(x,q)$ is some
objective function then we aiming to find

$\inf_{q}f(q).$ (22)

In the SDP (3.1), $g$ is the objective function, i.e. it is the average
probability of success, $x$ is a PVM $\\{\Pi_{=},\Pi_{\neq}\\}$ and $q$ is
considered to be the Haar measure $q_{\mathrm{Haar}}$. It is obvious from
definition that $\inf_{q}f(q)\leq f(q_{\mathrm{Haar}})$. On the other hand,
for every measure $q$ we have

$f(q)=\sup_{x}g(x,q)\geq g(y,q)=g(y,q_{\mathrm{Haar}})=f(q_{\mathrm{Haar}}),$
(23)

where $y\vcentcolon=\mathrm{argmax}_{x}g(x,q_{\mathrm{Haar}})$ and we used the
obvious property $g(y,q_{\mathrm{Haar}})=g(y,q)$ for every measure $q$.
Therefore, without loss of generality, we can assume that the input states in
the definition of $\mathsf{QSI}_{\mu}^{p}$ are twirled with respect to the
Haar measure. The same argument holds for
$\widetilde{\mathsf{QSI}}_{\mu}^{p}$: namely, the unknown permutation $\sigma$
can be assumed to be uniformly random.

###  3.3. Warm-up: optimality for $\mu=(n-h,h)$ with $p=1/2$

Next, consider the most common assumptions $\mu=(n-h,h)$ with $p=1/2$. The
$\mathsf{QSI}_{n}$ problem has then the following solution:

######  Theorem 4.

Given $n$ systems and a promise $\mu=(n-h,h)$ with $n/2\geq h\geq 1$, $p=1/2$,
the permutation test, defined by $\Pi_{=}:=\Pi_{(n)}$, is optimal and has an
average success probability equal

$\mathbb{P}_{succ}(n,h)=1-\frac{1}{2\binom{n}{h}}.$ (24)

One-sided success probabilities (completeness and soundness respectively) are

$\mathbb{P}_{c}(n,h)=1,\qquad\mathbb{P}_{s}(n,h)=1-\frac{1}{\binom{n}{h}}.$
(25)

###### Proof.

Note that the permutation test is always correct on equal inputs, meaning that
the completeness probability is

$\mathbb{P}_{c}(n,h)=\Tr[\Pi_{=}\rho_{=}^{n}]=\Tr[\Pi_{(n)}\rho_{=}^{n}]=1.$
(26)

It is only sometimes wrong on orthogonal inputs, the soundness probability is

$\mathbb{P}_{s}(n,h)=\Tr[\Pi_{\neq}\rho_{\neq}^{n,h}]=1-\Tr[\rho_{\neq}^{n,h}\Pi_{(n)}]=1-\frac{1}{\binom{n}{h}},$
(27)

where we used Lemma 1 and $\rho_{\neq}^{n,h}\vcentcolon=\rho_{\neq}^{\mu}$ for
$\mu=(n-h,h)$. Therefore the permutation test is a feasible solution to the
primal SDP (3.1) with the average success probability

$\mathbb{P}_{succ}(n,h)=1-\frac{1}{2\binom{n}{h}},$ (28)

which thus lower-bounds the SDP. We claim that the permutation test is the
optimal solution for the SDP. To show this, it suffices to find a feasible
solution to the dual problem that attains the value of the permutation test.

As an educated guess, we will show that

$\displaystyle
Y\vcentcolon=\frac{1}{2}\rho_{\neq}^{n,h}+\frac{1}{2}\left(1-\frac{1}{\binom{n}{h}}\right)\rho_{=}^{n}$
(29)

is a feasible solution to the dual SDP (3.1). Indeed $Y$ is Hermitian, and
trivially

$\displaystyle
Y-\frac{1}{2}\rho_{\neq}^{n,h}=\frac{1}{2}\left(1-\frac{1}{\binom{n}{h}}\right)\rho_{=}^{n}\succeq
0$ (30)

Now we need to show that

$\displaystyle
Y-\frac{1}{2}\rho_{=}^{n}=\frac{1}{2}\rho_{\neq}^{n,h}-\frac{1}{2\binom{n}{h}}\rho_{=}^{n}\succeq
0.$ (31)

We can use Lemma 1 for the case $\mu=(n-h,h)$ with $n/2\geq h$ to deduce that

$\displaystyle\rho_{\neq}^{n,h}$
$\displaystyle=\frac{1}{\binom{n}{h}}\sum_{\begin{subarray}{c}\lambda\mathbin{\vdash}_{d}n\end{subarray}}\frac{d_{\lambda}}{m_{\lambda,d}}\left\lparen\Pi_{(n-h)}\otimes\Pi_{(h)}\right\rparen\Pi_{\lambda}=\frac{1}{\binom{n}{h}}\frac{1}{\binom{n+d-1}{n}}\Pi_{(n)}+\frac{1}{\binom{n}{h}}\sum_{\begin{subarray}{c}\lambda\vdash_{d}n\\\
\lambda\neq(n)\end{subarray}}\frac{d_{\lambda}}{m_{\lambda,d}}\left\lparen\Pi_{(n-h)}\otimes\Pi_{(h)}\right\rparen\Pi_{\lambda},$

where we used the fact
$\left\lparen\Pi_{(n-h)}\otimes\Pi_{(h)}\right\rparen\Pi_{(n)}=\Pi_{(n)}$ and
$m_{(n),d}=\binom{n+d-1}{n}$. Therefore,

$Y-\frac{1}{2}\rho_{=}^{n}=\frac{1}{2}\rho_{\neq}^{n,h}-\frac{1}{2\binom{n}{h}}\rho_{=}^{n}=\frac{1}{2\binom{n}{h}}\sum_{\begin{subarray}{c}\lambda\vdash_{d}n\\\
\lambda\neq(n)\end{subarray}}\frac{d_{\lambda}}{m_{\lambda,d}}\left\lparen\Pi_{(n-h)}\otimes\Pi_{(h)}\right\rparen\Pi_{\lambda}\succeq
0,$ (32)

since all projectors
$\left\lparen\Pi_{(n-h)}\otimes\Pi_{(h)}\right\rparen\Pi_{\lambda}$ in the
expression are orthogonal. Therefore all the constraints of the dual SDP (3.1)
are satisfied and the objective value is the same as for the primal SDP.
Therefore from weak SDP duality, it follows that the permutation test is
optimal. ∎

The above proof shows an optimality of the permutation test in a relaxed _two-
sided error_ setting, thus solving an open problem from [KNY08].

###  3.4. The general setting

Now we consider a general situation: an arbitrary $p\in[0,1]$ and an arbitrary
$\mu\mathbin{\vdash}n$.

######  Theorem 5.

For QSIμp, given $n$ systems and a partition $\mu\mathbin{\vdash}n$, we define
$p^{*}(\mu)\vcentcolon=\frac{1}{1+\binom{n}{\mu}}$. Then the primal SDP (3.1)
has the following optimal solution:

$\Pi_{=}=\begin{cases}\Pi_{(n)}&\text{ if }p^{*}(\mu)\leq p\leq 1,\\\ 0&\text{
if }0\leq p\leq p^{*}(\mu),\end{cases}$ (33)

with average success probability

$\mathbb{P}_{succ}(\mu,p)=\begin{cases}1-\frac{1-p}{\binom{n}{\mu}}&\text{ if
}p^{*}(\mu)\leq p\leq 1,\\\ 1-p&\text{ if }0\leq p\leq p^{*}(\mu).\end{cases}$
(34)

One-sided success probabilities (completeness and soundness respectively) are

$\displaystyle\mathbb{P}_{c}(\mu,p)$ $\displaystyle=\begin{cases}1&\text{ if
}p^{*}(\mu)\leq p\leq 1,\\\ 0&\text{ if }0\leq p\leq
p^{*}(\mu),\end{cases}\qquad\mathbb{P}_{s}(\mu,p)=\begin{cases}1-\frac{1}{\binom{n}{\mu}}&\text{
if }p^{*}(\mu)\leq p\leq 1,\\\ 1&\text{ if }0\leq p\leq
p^{*}(\mu).\end{cases}$ (35)

###### Proof.

The idea for the proof is the same as for Theorem 4: we are going to present a
feasible solution for the dual, which matches the feasible solution for the
primal SDP, defined by eq. 33. Consider

$Y\vcentcolon=\begin{cases}(1-p)\rho^{\mu}_{\neq}+\left\lparen
p-\frac{1-p}{\binom{n}{\mu}}\right\rparen\rho^{n}_{=}&\text{ if
}p^{*}(\mu)\leq p\leq 1,\\\ (1-p)\rho^{\mu}_{\neq}&\text{ if }0\leq p\leq
p^{*}(\mu).\end{cases}$ (36)

We are going to show that this $Y$ is a feasible solution for the dual SDP.
Consider the two cases:

  * •

$0\leq p\leq p^{*}(\mu)$. Then from the definition (36)
$Y-(1-p)\rho^{\mu}_{\neq}\succeq 0$ is trivially satisfied. Checking another
constraint is also easy using Lemma 1.

$\displaystyle Y-p\rho^{n}_{=}$
$\displaystyle=\left\lparen\frac{1-p}{\binom{n}{\mu}}-p\right\rparen\frac{\Pi_{(n)}}{\binom{n+d-1}{n}}+\frac{1}{\binom{n}{h}}\sum_{\begin{subarray}{c}\lambda\vdash_{d}n\\\
\lambda\neq(n)\end{subarray}}\frac{d_{\lambda}}{m_{\lambda,d}}\left\lparen\Pi_{\mu_{1}}\otimes\dotsc\otimes\Pi_{\mu_{d}}\right\rparen\Pi_{\lambda},$
(37)

but it is easy to see that

$\frac{1-p}{\binom{n}{\mu}}-p=\frac{1}{\binom{n}{\mu}}\left\lparen
1-\frac{p}{p^{*}(\mu)}\right\rparen\geq 0,$ (38)

therefore $Y-p\rho^{n}_{=}\succeq 0$.

  * •

$p^{*}(\mu)\leq p\leq 1$. Again, it is obvious from the definition (36) that

$Y-(1-p)\rho^{\mu}_{\neq}=\frac{1}{\binom{n}{\mu}}\left\lparen\frac{p}{p^{*}(\mu)}-1\right\rparen\rho^{n}_{=}\succeq
0.$ (39)

Another constraint is similar to the previous case:

$\displaystyle Y-p\rho^{n}_{=}$
$\displaystyle=(1-p)\rho^{\mu}_{\neq}-\frac{1-p}{\binom{n}{\mu}}\rho^{n}_{=}=\frac{1}{\binom{n}{h}}\sum_{\begin{subarray}{c}\lambda\vdash_{d}n\\\
\lambda\neq(n)\end{subarray}}\frac{d_{\lambda}}{m_{\lambda,d}}\left\lparen\Pi_{\mu_{1}}\otimes\dotsc\otimes\Pi_{\mu_{d}}\right\rparen\Pi_{\lambda}\succeq
0$ (40)

Note that $\Tr[Y]$ matches the objective value (34) of the primal SDP solution
defined in eq. 33. Thus the weak SDP duality proves the optimality of the
solution eq. 33. ∎

As mentioned before, the permutation test does not use any information about
the order of the input state. Therefore we achieve the same success
probability on the permuted input $\tilde{\rho}_{\neq}^{\mu}$ as we did on the
ordered input ${\rho}_{\neq}^{\mu}$. Thus, surprisingly knowing the order of
the unequal inputs does not allow one to achieve a higher success probability.
Since the problem with randomly permuted inputs is a strictly harder problem
we immediately get the following corollary for ~QSIμp.

######  Corollary 1.

For ~QSIμp, given $n$ systems and a permuted partition
$\tilde{\mu}\mathbin{\vdash}n$, we define
$p^{*}(\tilde{\mu})\vcentcolon=\frac{1}{1+\binom{n}{\mu}}$. Then the same
measurement as in Theorem 5 is optimal, with the same success probabilities.

##  4\. The $G$-test

We can generalize the idea of the permutation test to an arbitrary subgroup
$G\subseteq\operatorname{S}_{n}$. Assuming that we want to distinguish between
$\tilde{\rho}_{\neq}^{\mu}$ and $\rho_{=}^{n}$, we call the _$G$ -test_ the
measurement given by

$\Pi_{=}=\Pi_{G},\quad\Pi_{\neq}=\mathbbm{1}-\Pi_{G},$ (41)

where $\Pi_{G}$ is the projector onto the trivial irrep of $G$:

$\Pi_{G}:=\frac{1}{\absolutevalue{G}}\sum_{\pi\in G}\psi(\pi).$ (42)

For $G=\operatorname{S}_{n}$ we recover the usual permutation test
$\Pi_{G}=\Pi_{(n)}$. The $G$-test has the perfect completeness probability:

$\mathbb{P}^{G}_{c}(\mu)=\Tr[\tilde{\rho}_{=}^{n}\Pi_{G}]=\frac{\Tr[\Pi_{(n)}\Pi_{G}]}{\binom{n+d-1}{n}}=\frac{\Tr[\Pi_{(n)}]}{\binom{n+d-1}{n}}=1,$
(43)

because for every $\pi\in G$ we have $\pi\Pi_{(n)}=\Pi_{(n)}$. Due to Lemma 1
we have

$\Tr[\tilde{\rho}_{\neq}^{\mu}\Pi_{G}]=\frac{1}{\binom{n}{\mu}}\sum_{\begin{subarray}{c}\lambda\mathbin{\vdash}_{d}n\end{subarray}}\frac{K_{\lambda,\mu}\Tr[\Pi_{\lambda}\Pi_{G}]}{m_{\lambda,d}},$
(44)

so the soundness probability of the $G$-test can be calculated to be

$\mathbb{P}^{G}_{s}(\mu)=1-\frac{1}{\binom{n}{\mu}}\sum_{\begin{subarray}{c}\lambda\mathbin{\vdash}_{d}n\end{subarray}}K_{\lambda,\mu}r^{G}_{\lambda},$
(45)

where $r^{G}_{\lambda}$ is the multiplicity of the trivial irrep of the
subgroup $G\subseteq\operatorname{S}_{n}$ inside the irrep $\lambda$ of the
symmetric group $\operatorname{S}_{n}$.

###  4.1. The Circle test

In this section, we consider the circle test, i.e. the case when $G$ is the
cyclic group $\textup{C}_{n}\vcentcolon=\langle(12\cdots
n)\rangle\subset\operatorname{S}_{n}$. Then the numbers
$r^{\textup{C}_{n}}_{\lambda}$ can be understood combinatorially [KW01]:

$r^{\textup{C}_{n}}_{\lambda}=\absolutevalue{\\{T\in\mathrm{SYT}(\lambda)\,|\,\mathrm{maj}_{n}(T)=0\\}},$
(46)

where $\mathrm{maj}_{n}(T)$ is the _major index modulo $n$_ of the _standard
Young tableaux_ $T$. Moreover, one can obtain the following identity [Swa18,
Theorem 4] for $\lambda\mathbin{\vdash}n$:

$\frac{r^{\textup{C}_{n}}_{\lambda}}{d_{\lambda}}=\frac{1}{n}+\frac{1}{n}\sum_{\begin{subarray}{c}\ell|n\\\
\ell\neq
1\end{subarray}}\frac{\chi_{\lambda}(\ell^{n/\ell})}{d_{\lambda}}\phi(\ell),$
(47)

where $\phi(\ell)$ is the Euler’s totient function and
$\chi_{\lambda}(\ell^{n/\ell})$ is the symmetric group $\operatorname{S}_{n}$
character for the conjugacy class of type $(\ell,\dotsc,\ell)$. Now since
$\sum_{\begin{subarray}{c}\lambda\mathbin{\vdash}_{d}n\end{subarray}}K_{\lambda,\mu}d_{\lambda}=\binom{n}{\mu}$
we get the general soundness error probability

$1-\mathbb{P}^{G}_{s}(\mu)=\frac{1}{n}+\frac{1}{n}\sum_{\begin{subarray}{c}\lambda\mathbin{\vdash}_{d}n\end{subarray}}\frac{K_{\lambda,\mu}d_{\lambda}}{\binom{n}{\mu}}\sum_{\begin{subarray}{c}\ell|n\\\
\ell\neq
1\end{subarray}}\frac{\chi_{\lambda}(\ell^{n/\ell})}{d_{\lambda}}\phi(\ell).$
(48)

It is easy to see that $r^{\textup{C}_{n}}_{(n)}=1$ and
$r^{\textup{C}_{n}}_{(n-1,1)}=0$. Therefore, for
$\mathbb{P}^{G}_{s}(n,h)\vcentcolon=\mathbb{P}^{G}_{s}((n-h,h))$ we have from
eq. 45:

$\displaystyle\mathbb{P}^{G}_{s}(n,1)=1-\frac{1}{n}.$ (49)

The worst case analysis of the circle test for prime $n$ and for asymptotic
$n$ was performed in [KNY08]. Equation 48 suggests that more fine-grained
analysis is possible via Roichmann’s bound [Roi96] and other results of
[Swa18].

###  4.2. The Iterated Cyclic Wreath test

Next, we initiate the study of the $G$-test when $G$ is an iterated wreath
product of the cyclic groups. More precisely, given a prime factorization
$n=\prod_{i=1}^{r}p_{i}^{m_{i}}$ we define

$G\vcentcolon=\underbrace{\textup{C}_{p_{1}}\wr\dotsc\wr\textup{C}_{p_{1}}}_{m_{1}}\wr\underbrace{\textup{C}_{p_{2}}\wr\dotsc\wr\textup{C}_{p_{2}}}_{m_{2}}\wr\dotsc\wr\underbrace{\textup{C}_{p_{r}}\wr\dotsc\wr\textup{C}_{p_{r}}}_{m_{r}}.$
(50)

The motivation for considering this group comes from the next section where we
study the special case corresponding to $n=2^{m}$ which we call _the Iterated
Swap Tree_. In general, it is very difficult to obtain formulas for
$r^{G}_{\lambda}$ for arbitrary $n$, so considering the case $n=2^{m}$ is the
first step towards understanding the general $n$ case.

##  5\. Approximation of the permutation test by the Iterated Swap Tree

###  5.1. The Iterated Swap Tree protocol

We propose a new simple protocol to compute the ~QSIμp problem based only on
applying the Swap test in a tree-like way on all the inputs. One motivation is
that this protocol will always be correct on equal inputs and hence has
perfect completeness. Another motivation is practical, applying a single Swap
test requires only controlling a single gate while the circle test requires
you to control over all $n$ shifts. The permutation test even requires
controlling over $n!$ permutations. Not only is the controlled operation
easier, but also the Fourier transform one has to apply afterwards to read out
the correct measurement is only on a single qubit, instead of $\log_{2}(n)$
qubits for the circle test or $\log_{2}(n!)$ qubits for the permutation test.
Unfortunately, we do not know of any way to compute the quantities in the
aforementioned $G$-test to get the exact performance of the protocol. However,
we give an alternative way to still bound its performance and show that it is
similar to that of the circle test. Note that this operation uses $n-1$ Swap
tests, answering an open question in [KNY08] that asks for an efficient
approximation of the permutation test using only $O(n)$ Swap tests.

Algorithm 2: The Iterated Swap Tree (IST) Input: $n=2^{m}$ quantum states
$\ket{\psi_{1}}\otimes\ket{\psi_{2}}\otimes\dots\otimes\ket{\psi_{n}}$, (1)
Randomly permute the index labels of all $n$ input registers with a
permutation $P$ to obtain the ordered set $I=\\{i_{1},i_{2},\dots,i_{n}\\}$
with $i_{k}\in[n]$. (2) For $l\in\\{0,\dots,m-1\\}$: (a) Let $S_{j}$, where
$\bigcup_{j=1}^{n/2^{l}}S_{j}=I$ be the sets of $2^{l}$ adjacent indices in
$I$. (b) For $b\in[n/2^{l+1}]$ (i) Perform the Swap test with as inputs
registers $S_{2b-1}$ and $S_{2b}$. (ii) If the measurement outcome is $1$,
return ‘not equal’, else continue. (3) Return ‘equal’.

$=$$\mathsf{ST}$$|\psi_{2}\rangle$$|\psi_{1}\rangle$$\mathrm{SWAP}$$|0\rangle$$|\psi_{2}\rangle$$|\psi_{1}\rangle$$P$$|\psi_{8}\rangle$$|\psi_{7}\rangle$$|\psi_{6}\rangle$$\mathsf{ST}$$\mathsf{ST}$$|\psi_{5}\rangle$$\mathsf{ST}$$\mathsf{ST}$$\mathsf{ST}$$\mathsf{ST}$$|\psi_{4}\rangle$$|\psi_{3}\rangle$$|\psi_{2}\rangle$$|\psi_{1}\rangle$$\mathsf{ST}$$H$$H$
Figure 1. Visualisation of the Iterated Swap Tree (IST) protocol for $n=8$.

Note that Algorithm 5.1 is always correct on the equal input case. To analyze
the performance of Algorithm 5.1 we want to estimate the probability that the
algorithm accepts the input state as being the all equal state while the input
was actually a state on which a subset was orthogonal to the other states. To
do so, consider what the Swap test tells us on two input states. If the states
are equal the measurement outcome will always be ‘0’, if the states are
orthogonal the measurement outcome will be either ‘0’ or ‘1’ with probability
$1/2$ [BCWd01]. We call the cases in which the Swap test may detect that the
inputs are orthogonal a possible click. If the input states are all equal, all
the Swap tests in the tree will get measurement outcome ‘0’. If a subset of
the input states is orthogonal to the others, we are interested in the number
of possible clicks, i.e. the number of times the Swap test could tell us two
states are orthogonal. Suppose we apply the Swap test to two orthogonal states
$\ket{\psi},\ket{\phi}$, then the post-measurement states will be:

$\displaystyle\frac{1}{\sqrt{2}}\ket{\psi}\ket{\phi}$
$\displaystyle+\ket{\phi}\ket{\psi},$ or
$\displaystyle\frac{1}{\sqrt{2}}\ket{\psi}\ket{\phi}$
$\displaystyle-\ket{\phi}\ket{\psi},$ (51)

corresponding to measurement outcomes ‘0’ and ‘1’ respectively.

For example, if a single state is orthogonal to the other states, then, it is
clear that in every layer of the IST in Figure 1 there is a single possible
click, no matter where the state is placed. The IST protocol will only not
detect this single input being orthogonal if all the measurement outcomes were
‘0’, which happens with probability $\left(\frac{1}{2}\right)^{\log
n}=\frac{1}{n}$. If the inputs were all equal, the IST protocol will always be
correct. Therefore if again half the time the input is all equal and the other
half there is a single orthogonal state the probability of correctly
identifying the state with the IST is:

$\displaystyle\frac{1}{2}\cdot
1+\frac{1}{2}\cdot\left(1-\frac{1}{n}\right)=1-\frac{1}{2n}.$ (52)

Which is equal to the $h=1$ case of Theorem 4, thus we see that for the $h=1$
case the IST is in fact optimal. Interestingly, the position of the orthogonal
state is not used by the IST, as is also the case for the permutation test,
but both protocols are nonetheless optimal.

Of interest is now how well the IST protocol performs for different input
partitions. The performance depends purely on the number of possible clicks
for the partition. For a specific input one can compute the number of possible
clicks by checking if the input ports in every Swap test are orthogonal or
not. However, it is more difficult to say something about the number of
possible clicks if the inputs are randomly permuted. We want to get the
soundness probability as an averaged quantity only depending on $n$ and $h$.
To say something quantitatively we consider the case where there is a
partition into two parts ($\mu=(n-h,h)$), and we propose a lower bound to the
performance of the IST protocol by bounding the number of possible clicks.

The idea is as follows, in the two input ports of a Swap test consider the
number of orthogonal states in each port. If this number of states is
different between the two ports, we know for sure that the input states are
orthogonal to each other and we get a possible click. If the number of
orthogonal states are equal it is possible to have a possible click, but as a
simplification we disregard this possibility. Then, we get a lower bound on
the number of possible clicks.

One can compute this lower bound on the number of possible clicks iterative
for every layer:

  * •

Check for every input pair if the number of orthogonal states in each input
port is different. If yes, add one to a possible click counter.

  * •

Add the number of orthogonal states in each port and send this through to the
next port.

As a simple example consider the input with $h=3,n=8$:

$\displaystyle\ket{\phi}\ket{\psi}\ket{\psi}\ket{\psi}\ket{\phi}\ket{\psi}\ket{\psi}\ket{\phi},$
(53)

where $\bra{\phi}\ket{\psi}=0$. Then we can write this input as
‘1,0,0,0,1,0,1,1’, where ‘1’ denotes the state $\ket{\phi}$ and ‘0’
$\ket{\psi}$. Then there are $2$ cases where the number of orthogonal states
in the ports are different. For the second layer, we add all the pairs of
inputs to get ‘1,0,1,2’, which has $2$ of these cases. Finally, for the last
layer, we get ‘1,3’, which has $1$ possible click. Thus the total number of
possible clicks for this input was at least $5$. So the probability to detect
that this input was the $\neq$ input is at least
$1-\left(\frac{1}{2}\right)^{5}$. Counting this way gives us a recursive way
to lower the possible clicks and the performance of the IST protocol by a
specific quantity. To see why this counting strategy does not count every
case, we give an example of a state initialization where the two input ports
of the Swap test have the same number of orthogonal states, but nonetheless,
the input states are orthogonal. Consider the input:

$\displaystyle\ket{\phi}\ket{\phi}\ket{\psi}\ket{\psi}\ket{\phi}\ket{\psi}\ket{\phi}\ket{\psi},$
(54)

and suppose we arrive at the final Swap test where both ports have 4 states as
input. We can assume we have not had a measurement outcome ‘1’ yet on any of
the Swap tests, since we stop when we detect this. Note that both ports will
have 2 orthogonal states in them, so our counting procedure would not count
this case as a measurement where a possible click can occur. Then the input
state in the first port is

$\displaystyle\frac{1}{\sqrt{2}}\left(\ket{\phi\phi\psi\psi}+\ket{\psi\psi\phi\phi}\right),$
(55)

and of the second state

$\displaystyle\frac{1}{2}\left(\ket{\phi\psi\phi\psi}+\ket{\phi\psi\psi\phi}+\ket{\psi\phi\psi\phi}+\ket{\psi\phi\phi\psi}\right).$
(56)

Note that both states are orthogonal to each other, so we have a possible
click. So we get a lower bound on the number of possible clicks. The recursive
structure of counting this way allows us to derive a general upper bound for
the soundness error of the Iterated Swap Tree.

###  5.2. A recursive upper bound

######  Theorem 6.

The soundness probability of the IST for $n=2^{m}$ and $h\in[n]$, with the
promise that $\mu=(n-h,h)$ is

$\mathbb{P}^{\mathrm{IST}}_{s}(n,h)\geq
1-\frac{\gamma(h,\log_{2}(n))}{\binom{n}{h}},$ (57)

where $\gamma(h,m)$ satisfies the recurrence relation for every integer $h\geq
2$ and integer $m\geq 0$

$\gamma(h,m)=\sum_{k=0}^{\lfloor\frac{h}{2}\rfloor}\gamma(k,m-1)\gamma(h-k,m-1)$
(58)

with the boundary conditions $\gamma(0,m)=\gamma(1,m)=1$ for every integer
$m\geq 0$ and $\gamma(h,0)=0$ for every integer $h\geq 2$.

###### Proof.

Note that $n/2\geq h$ by definition, otherwise we could say the other set of
states is the orthogonal part. For $n=2^{m}$ and a fixed $h$, we know that the
probability to not detect will be
$\mathbb{E}[\left(\frac{1}{2}\right)^{\\#\text{poss. clicks}(h,m)}]$, where
the expected value is taken over all possible input permutations. For
$n=2^{m}$ and the number of orthogonal states $h$, we define $\alpha(h,m)$ as
$\frac{1}{2}$ to the power of our value of the counting process described
above averaged over all permutations. Since our counting process undercounts
the number of clicks, we have
$\alpha(h,m)\geq\mathbb{E}[\left(\frac{1}{2}\right)^{\\#\text{poss.
clicks}(h,m)}]$. For a specific input we can compute the final value of our
counting process recursively as follows:

  * •

Divide the input into two equally sized halves and count the number of
orthogonal states in each of the halves. If the inputs are of size 1 stop.

  * •

These two numbers will be exactly the number of orthogonal states in each port
in the last layer of the protocol.

  * •

If the numbers are different add 1 to the counter, else do nothing.

  * •

Now do this process again to both of the halves of the original input.

The insight to why this recursion works is that if the final layer is removed
we have two IST independent from each other on the first and second half of
the inputs (see Figure 1). With this process, we can write down a formula for
$\alpha(n,h)$:

$\displaystyle\alpha(h,m)=\sum_{k=0}^{h}\mathbb{P}[k,h-k]\left(\frac{1}{2}\right)^{1-\delta_{k,h-k}}\alpha(k,m-1)\alpha(h-k,m-1),$
(59)

where $\delta_{x,h-x}$ is the Kronecker delta which tracks if the amount of
orthogonal states in the first and second half are equal. And
$\mathbb{P}[k,h-k]$ is the probability that the state has $k$ orthogonal
states in the first part and $h-k$ in the second part. For the boundary
conditions of $\alpha$ we know that if $h$ = 0, we will count anything so
$\alpha(0,m)=\left(\frac{1}{2}\right)^{0}=1$, and if $h$ = 1, we get a count
in every layer so $\alpha(1,m)=\left(\frac{1}{2}\right)^{m}$. When there are
no more divisions we don’t count any possible clicks anymore so
$\alpha(h,0)=0$. Note that these boundary conditions define a unique
$\alpha(h,m)$.

When we randomly permute all the inputs we can compute this probability:

$\displaystyle\alpha(h,m)$
$\displaystyle=\sum_{k=0}^{h}\frac{\binom{2^{m-1}}{k}\binom{2^{m-1}}{h-k}}{\binom{2^{m}}{h}}\left(\frac{1}{2}\right)^{1-\delta_{k,h-k}}\alpha(k,m-1)\alpha(h-k,m-1)$
(60) $\displaystyle\binom{2^{m}}{h}\alpha(h,m)$
$\displaystyle=\sum_{k=0}^{h}\left(\frac{1}{2}\right)^{1-\delta_{k,h-k}}\binom{2^{m-1}}{k}\alpha(k,m-1)\binom{2^{m-1}}{h-k}\alpha(h-k,m-1)$
(61) $\displaystyle\gamma(h,m)$
$\displaystyle=\sum_{k=0}^{h}\left(\frac{1}{2}\right)^{1-\delta_{k,h-k}}\gamma(k,m-1)\gamma(h-k,m-1),$
(62)

where we have defined $\gamma(h,m)=\binom{2^{m}}{h}\alpha(h,m)$. Using that
the expressions in the sum are equal for $k=i$ and $k=h-i$ we can further
simplify the expression. Note if $h$ is odd we have that $k$ is never equal to
$h-k$, so we get:

$\displaystyle\gamma(h,m)$
$\displaystyle=\sum_{k=0}^{h}\left(\frac{1}{2}\right)\gamma(k,m-1)\gamma(h-k,m-1)=\sum_{k=0}^{\lfloor\frac{h}{2}\rfloor}\gamma(k,m-1)\gamma(h-k,m-1).$
(63)

If $h$ is even we have

$\displaystyle\gamma(h,m)$
$\displaystyle=\sum_{k=0}^{\lfloor\frac{h}{2}\rfloor-1}\gamma(k,m-1)\gamma(h-k,m-1)+\left(\frac{1}{2}\right)^{1-\delta_{h/2,h/2}}\gamma(h/2,m-1)\gamma(h/2,m-1)$
(64)
$\displaystyle=\sum_{k=0}^{\lfloor\frac{h}{2}\rfloor}\gamma(k,m-1)\gamma(h-k,m-1).$
(65)

We get the same expressions for $h$ odd and even so we can write in general:

$\displaystyle\gamma(h,m)$
$\displaystyle=\sum_{k=0}^{\lfloor\frac{h}{2}\rfloor}\gamma(k,m-1)\gamma(h-k,m-1).$
(66)

With boundary conditions defined by $\alpha(h,m)$, namely
$\gamma(0,m)=\binom{2^{m}}{0}\alpha(0,m)=1$,
$\gamma(1,m)=\binom{2^{m}}{1}\alpha(1,m)=2^{m}\left(\frac{1}{2}\right)^{m}=1$,
and $\gamma(h,0)=0$. Finally, we get the lower bound on the soundness
probability

$\displaystyle\mathbb{P}^{\mathrm{IST}}_{s}((n,h))=1-\mathbb{E}\left[\left(\frac{1}{2}\right)^{\\#\text{poss.
clicks}(h,m)}\right]\geq
1-\alpha(h,\log_{2}(n))=1-\frac{\gamma(h,\log_{2}(n))}{\binom{n}{h}},$ (67)

as desired. ∎

Note that $\gamma(h,\log_{2}(n))$ is increasing in $h$ up until $n/2$, as well
as increasing in $n$, so having more orthogonal states instead of the other
states will give us better bounds on the soundness, but also having more
states in general will always give better bounds.

The proof above assumes a partition into two parts $\mu=(n-h,h)$. For a
general partition $\mu$ a way to lower bound the number of possible clicks can
be done as follows. Join the partitions together such that we get two parts
both of maximal size, then we can apply the theorem again and since
$\gamma(h,\log_{2}(n))$ is increasing in $h$ we take it as close as possible
to $n/2$. Then regard all the states in one partition as the same (i.e. the
$0$ and $1$), and apply our counting strategy to get a lower bound on the
number of possible clicks. To see that this again undercounts, note that
seeing two states as the same states does not increase the number of possible
clicks, and only does not count possible clicks between partitions that get
combined. Then we get the following corollary:

######  Corollary 2.

The soundness probability of the IST for $n=2^{m}$ and some partition $\mu$ is
lower bounded by,

$\displaystyle\mathbb{P}^{\mathrm{IST}}_{s}(\mu)\geq
1-\frac{\gamma(h^{*},\log_{2}(n))}{\binom{n}{h^{*}}},$ (68)

where $h^{*}=\sum_{i=k}^{h}\mu_{i}$, where
$k=\min\\{l\,|\,\sum_{i=l}^{h}\mu_{i}\leq\frac{n}{2}\\}$.

######  Lemma 2.

Fix $n=2^{m}$ and an integer $h\geq 1$. Then:

  1. (1)

for every $h\geq 2$, $\gamma(h,m)=0$ for every integer $m<\log_{2}(h)$,

  2. (2)

for any integers $h,m$ we have a symmetry $\gamma(h,m)=\gamma(n-h,m)$,

  3. (3)

$\gamma(h,m)$ is a polynomial in $m$ of degree $h-1$.

###### Proof.

(1) and (2) are obvious from the definition of $\gamma(h,m)$. Let’s prove (3).
We proceed by induction in $h$. The base of induction $h=1$ is clear:
$\gamma(1,m)=1$ for every $m$ from definition. Now assume $h\geq 2$ and
$\gamma(h-1,m)=p_{h-2}(m)$, where $p_{h-2}(m)$ is a polynomial of degree
$h-2$. Then using the defining relation of $\gamma(h,m)$ we get

$\displaystyle\gamma(h,m)$
$\displaystyle=\gamma(h,m-1)+\sum_{k=1}^{\lfloor\frac{h}{2}\rfloor}\gamma(k,m-1)\gamma(h-k,m-1)=\gamma(h,m-2)+\sum_{k=1}^{\lfloor\frac{h}{2}\rfloor}\sum_{x=m-2}^{m-1}\gamma(k,x)\gamma(h-k,x)$
(69)
$\displaystyle=\sum_{k=1}^{\lfloor\frac{h}{2}\rfloor}\sum_{x=0}^{m-1}\gamma(k,x)\gamma(h-k,x)=\sum_{k=0}^{\lfloor\frac{h}{2}\rfloor}\sum_{x=0}^{m-1}p_{k-1}(x)p_{h-k-1}(x)=\sum_{k=0}^{\lfloor\frac{h}{2}\rfloor}\sum_{x=0}^{m-1}q_{h-2}(x),$
(70)

where $q_{h-2}(x)$ is some polynomial of degree $h-2$. But

$\sum_{x=0}^{m-1}q_{h-2}(x)=p_{h-1}(m-1),$ (71)

for some polynomial $p_{h-1}(m-1)$ of degree $h-1$ due to the well known
Bernoulli’s formula

$\sum_{x=0}^{m-1}x^{h-2}=\frac{(m-1)^{h-1}}{h-1}+g(m-1),$ (72)

where $g(m-1)$ is a polynomial of degree $h-2$. Therefore we have

$\gamma(h,m)=\sum_{k=0}^{\lfloor\frac{h}{2}\rfloor}p_{h-1}(m-1),$ (73)

so $\gamma(h,m)$ is a polynomial of degree $h-1$. ∎

We will now show that for any fixed $h$, for sufficiently large $m$ the IST
will achieve optimal soundness error.

######  Corollary 3.

Let $n=2^{m}$ for $m\in\mathbb{N}$ and fix any $1\leq h\leq n/2$ Then there
exists a $n^{*}_{0}\in\mathbb{N}$ such that the IST protocol achieves perfect
completeness and for all $n\geq n_{0}$ has soundness probability $\geq 1-1/n$.

###### Proof.

Perfect completeness follows from Theorem 6. Since we are interested in the
worst-case error in the soundness setting, we can assume $\mu=(n-h,h)$. From
Lemma 2, we know that $\gamma(h,m)$ is a polynomial in $m$ of degree $h-1$.
Using that $m=\log_{2}n$, we have by Theorem 6 that the soundness probability,
given a fixed $h$, can be lower bounded as

$\mathbb{P}^{\mathrm{IST}}_{s}(n,h)\geq\frac{\gamma(h,\log_{2}(n))}{\binom{n}{h}}\geq
1-\frac{c_{h}(\log_{2}n)^{h-1}}{\left(\frac{n}{h}\right)^{h}}=1-\frac{1}{n}\cdot
f(n,h),$ (74)

where $f(n,h)$ is given by

$\displaystyle f(n,h):=c_{h}h\left(\frac{h\log_{2}n}{n}\right)^{h-1},$

with $c_{h}$ is a constant that only depends on $h$. Note that we have
$c_{1}=1$ and $f(n,1)=1$. For any $2\leq h\leq n/2$, we have that there exists
a constant $n_{0}$ which only depends on $c_{h}$ and $h$ such that for all
$n\geq n_{0}$ $f(n,h)\leq 1$. Hence, taking $n^{*}_{0}$ to be the maximum over
all such $n_{0}$, the statement directly follows. ∎

##  6\. Discussion and open problems

In the definition of the Quantum State Identity problem we consider the case
in which the input states are exactly orthogonal to each other. One could
relax this condition to states that are approximately orthogonal, i.e. we get
the promise that for some $\varepsilon>0$ the inner product between two states
$\ket{\psi_{i}}$ and $\ket{\psi_{j}}$ is either
$|\\!\bra{\psi_{i}}\ket{\psi_{k}}\\!|\geq 1-\varepsilon$ or
$|\\!\bra{\psi_{i}}\ket{\psi_{k}}\\!|\leq\varepsilon$. One could still perform
the permutation test and analyze its performance. One question would be if the
permutation test is still optimal in this setting. Another question is whether
there are simple operations that have the same performance as the permutation
test. This could imply that in some practical settings one can get optimal
performance of the QSI problem with an easier experimentally implementable
measurement.

The $G$-test we propose gives an analytical description of the performance of
a protocol that applies the permutation test to an arbitrary subgroup $G$. To
better understand the performance one would need to compute or get bounds on
the Kostca numbers and the multiplicities of the trivial irrep of this
subgroup $G$ inside the irrep of the symmetric group $\operatorname{S}_{n}$.

We introduce the Iterated Swap Tree as a new simple protocol that answers the
QSIμp problem. We derive lower bounds for the number of possible clicks which
enables us to give bounds on its performance. The quantity $\gamma(h,m)$ that
gives this bound is defined by a recurrence relation. It would be of interest
to derive an exact formula for $\gamma(h,m)$ or get some exact formula
$f(h,m)$ that bounds this recurrence relation, to get a better understanding
of the performance of the Iterated Swap Tree in the case of non fixed $h$.

The proposed Iterated Swap Tree can also be seen as a $G$-test where $G$ is
the iterated wreath product of the cyclic group of size 2 [OOR04]. This notion
can also be generalized to cyclic groups of larger prime size $p$, such the
inputs of $p^{m}$ qudits can also be analyzed. We can also take the wreath
product between different-sized groups. This would give us the tools to apply
a similar strategy as this Iterated Swap Tree to any sized input. One can take
the prime factorization of the amount of qudits you get as an input, and then
take the iterated wreath product between the cyclic groups, whose sizes are
these prime factors.

Finally, one can generalize the QSI problem to a more fine-grained property
testing problem: given $\rho^{\mu}_{\neq}$ for some
$\mu\mathbin{\vdash}n$333$\mu_{2}$ could be zero here., what is the most
efficient protocol to reconstruct $\mu$? This problem for qubits was studied
in [Mon09]. It was shown that the measurement called _weak Schur sampling_
[CHW07] is optimal for the qubit case. We conjecture that the qudit
generalization of the weak Schur sampling would also solve the general qudit
problem optimally with the probability of measuring $\mu$ being equal to
$\frac{d_{\mu}}{\binom{n}{\mu}}$.

## Acknowledgements

DG was supported by an NWO Vidi grant (Project No VI.Vidi.192.109). PVL and HB
were supported by the Dutch Research Council (NWO/OCW), as part of the NWO
Gravitation Programme Networks (project number 024.002.003). JW was supported
by the Dutch Ministry of Economic Affairs and Climate Policy (EZK), as part of
the Quantum Delta NL Programme.

## References

  * [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.  doi:http://doi.org/10.1137/S0097539796302452.
  * [BCH06] Dave Bacon, Isaac L. Chuang, and Aram W. Harrow.  Efficient quantum circuits for Schur and Clebsch–Gordan transforms.  Physical Review Letters, 97(17), 10 2006.  arXiv:quant-ph/0407082, doi:10.1103/physrevlett.97.170502.
  * [BCWd01] Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf.  Quantum fingerprinting.  Physical Review Letters, 87(16), October 2001.  doi:http://doi.org/10.1103/PhysRevLett.87.167902.
  * [BLM+22] Harry Buhrman, Noah Linden, Laura Mančinska, Ashley Montanaro, and Maris Ozols.  Quantum majority vote.  arXiv preprint arXiv:2211.11729, 2022.  doi:10.4230/LIPIcs.ITCS.2023.29.
  * [BV04] Stephen P Boyd and Lieven Vandenberghe.  Convex optimization.  Cambridge university press, 2004.  doi:http://dx.doi.org/10.1017/CBO9780511804441.
  * [CDM+18] Ulysse Chabaud, Eleni Diamanti, Damian Markham, Elham Kashefi, and Antoine Joux.  Optimal quantum-programmable projective measurement with linear optics.  Phys. Rev. A, 98:062318, Dec 2018.  doi:10.1103/PhysRevA.98.062318.
  * [CHW07] Andrew M Childs, Aram W Harrow, and Paweł Wocjan.  Weak fourier-schur sampling, the hidden subgroup problem, and the quantum collision problem.  In STACS 2007: 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22-24, 2007. Proceedings 24, pages 598–609. Springer, 2007.  doi:http://doi.org/10.1007/978-3-540-70918-3_51.
  * [CMN22] Benoit Collins, Sho Matsumoto, and Jonathan Novak.  The weingarten calculus.  Notices of the American Mathematical Society, 69(05):1, May 2022\.  URL: http://dx.doi.org/10.1090/noti2474, doi:10.1090/noti2474.
  * [CŚ06] Benoît Collins and Piotr Śniady.  Integration with respect to the haar measure on unitary, orthogonal and symplectic group.  Communications in Mathematical Physics, 264(3):773–795, 2006.  doi:http://doi.org/10.1007/s00220-006-1554-3.
  * [dB04] J Niel de Beaudrap.  One-qubit fingerprinting schemes.  Physical Review A, 69(2):022307, 2004.  doi:http://doi.org/10.1103/PhysRevA.69.022307.
  * [GBO23] Dmitry Grinko, Adam Burchardt, and Maris Ozols.  Gelfand–tsetlin basis for partially transposed permutations and mixed quantum schur transform.  2023\.  arXiv:2310.02252.
  * [Har05] Aram W. Harrow.  Applications of coherent classical communication and the Schur transform to quantum information theory.  PhD thesis, MIT, 2005.  URL: http://hdl.handle.net/1721.1/34973, arXiv:quant-ph/0512255.
  * [Har13] Aram W Harrow.  The church of the symmetric subspace.  arXiv preprint arXiv:1308.6595, 2013.  doi:https://doi.org/10.48550/arXiv.1308.6595.
  * [IW18] Mee Seong Im and Angela Wu.  Generalized iterated wreath products of cyclic groups and rooted trees correspondence.  In Advances in the Mathematical Sciences: AWM Research Symposium, Los Angeles, CA, April 2017, pages 15–28. Springer, 2018.  doi:http://doi.org/10.1007/978-3-319-98684-5_2.
  * [KMY01] Hirotada Kobayashi, Keiji Matsumoto, and Tomoyuki Yamakami.  Quantum certificate verification: Single versus multiple quantum certificates.  arXiv preprint quant-ph/0110006, 2001.  doi:https://doi.org/10.48550/arXiv.quant-ph/0110006.
  * [KNY08] Masaru Kada, Harumichi Nishimura, and Tomoyuki Yamakami.  The efficiency of quantum identity testing of multiple states.  Journal of Physics A: Mathematical and Theoretical, 41(39):395309, 2008.  doi:http://doi.org/10.1088/1751-8113/41/39/395309.
  * [KS18] William M. Kirby and Frederick W. Strauch.  A practical quantum algorithm for the Schur transform.  Quantum Information & Computation, 18(9&10):721–742, 2018.  arXiv:1709.07119, doi:10.26421/QIC18.9-10-1.
  * [KW01] Witold Kraskiewicz and Jerzy Weyman.  Algebra of coinvariants and the action of a coxeter element.  Bayreuther Mathematische Schriften, 63:265–284, 2001.
  * [Mon09] Ashley Montanaro.  Symmetric functions of qubits in an unknown basis.  Physical Review A, 79(6):062316, 2009.  doi:http://doi.org/10.1103/PhysRevA.79.062316.
  * [Ngu23] Quynh T. Nguyen.  The mixed schur transform: efficient quantum circuit and applications.  2023\.  arXiv:2310.01613.
  * [OOR04] Rosa C Orellana, Michael E Orrison, and Daniel N Rockmore.  Rooted trees and iterated wreath products of cyclic groups.  Advances in Applied Mathematics, 33(3):531–547, 2004.  doi:http://doi.org/10.1016/j.aam.2003.12.001.
  * [Roi96] Yuval Roichman.  Upper bound on the characters of the symmetric groups.  Inventiones mathematicae, 125:451–485, 1996.  doi:http://doi.org/10.1007/s002220050083.
  * [Sag13] Bruce E. Sagan.  The symmetric group: representations, combinatorial algorithms, and symmetric functions.  Graduate Texts in Mathematics. Springer New York, 2013.  URL: https://books.google.com/books?id=Y6vTBwAAQBAJ&pg=PA180.
  * [ST21] Vikesh Siddhu and Sridhar Tayur.  Five starter pieces: quantum information science via semi-definite programs, chapter 3, pages 59–92.  2021\.  arXiv:2112.08276, doi:10.1287/educ.2022.0243.
  * [Swa18] Joshua P Swanson.  On the existence of tableaux with given modular major index.  Algebraic Combinatorics, 1(1):3–21, 2018.  doi:http://doi.org/10.5802/alco.4.
  * [Wat18] John Watrous.  The Theory of Quantum Information.  Cambridge University Press, 2018.  URL: https://cs.uwaterloo.ca/~watrous/TQI/.
  * [WS23] Adam Wills and Sergii Strelchuk.  Generalised coupling and an elementary algorithm for the quantum schur transform.  2023\.  arXiv:2305.04069.
  * [WSV12] Henry Wolkowicz, Romesh Saigal, and Lieven Vandenberghe.  Handbook of Semidefinite Programming: Theory, Algorithms, and Applications.  International Series in Operations Research & Management Science. Springer, 2012.  URL: https://books.google.com/books?id=ErLSBwAAQBAJ, doi:10.1007/978-1-4615-4381-7.