# Quantum Algorithms for Realizing Symmetric, Asymmetric, and Antisymmetric
Projectors

Margarite L. LaBorde  Advanced Acoustics & Seabed Warfare Branch, Naval
Surface Warfare Center, Panama City, Florida 32407, USA  Soorya Rethinasamy
School of Applied and Engineering Physics, Cornell University, Ithaca, New
York 14850, USA  Mark M. Wilde  School of Electrical and Computer Engineering,
Cornell University, Ithaca, New York 14850, USA

###### Abstract

In quantum computing, knowing the symmetries a given system or state obeys or
disobeys is often useful. For example, Hamiltonian symmetries may limit
allowed state transitions or simplify learning parameters in machine learning
applications, and certain asymmetric quantum states are known to be
resourceful in various applications. Symmetry testing algorithms provide a
means to identify and quantify these properties with respect to a
representation of a group. In this paper, we present a collection of quantum
algorithms that realize projections onto the symmetric subspace, as well as
the asymmetric subspace, of quantum systems. We describe how this can be
modified to realize an antisymmetric projection as well, and we show how
projectors can be combined in a systematic way to effectively measure various
projections in a single quantum circuit. Using these constructions, we
demonstrate applications such as testing for Werner-state symmetry and
estimating Schmidt ranks of bipartite states, supported by experimental data
from IBM Quantum systems. This work underscores the pivotal role of symmetry
in simplifying quantum calculations and advancing quantum information tasks.

###### Contents

  1. I Introduction
  2. II Symmetric and Antisymmetric Projections
    1. II.1 Review of Symmetric Projections
    2. II.2 Antisymmetric Projection
  3. III Concatenating Projectors
    1. III.1 Uncomputing to Expand upon a Symmetry Test
    2. III.2 Realizing the Antisymmetric Projection
    3. III.3 Generalizing the Construction
    4. III.4 Examples
      1. III.4.1 Concatenating Symmetric and Antisymmetric Projectors
      2. III.4.2 Three Irreps of $S_{3}$
      3. III.4.3 Difference of Two Projectors
      4. III.4.4 Resolution of Identity
  4. IV Applications
    1. IV.1 Estimating Schmidt Rank
    2. IV.2 Alternate Test for Werner States
    3. IV.3 Estimating Commutators
    4. IV.4 Brief Comments on Schur Sampling
  5. V Discussion
  6. A Proof of Equation (100)

##  I Introduction

Symmetry has been prevalent throughout the field of physics since the
introduction of Noether’s theorem [1], and perhaps even earlier through its
prominence in mathematics and observation in crystalline materials [2]. A
recent direction of scholarship focuses on combining symmetry with quantum
information theory, demonstrating how the mathematical beauty of symmetry can
give rise to physically interesting phenomena in this regime. For instance,
the concept of Noether’s theorem, an integral link between physical symmetries
and conserved quantities, was expanded upon in [3], which investigated the
resourcefulness of quantum states under free channels. Similarly, the resource
theory of asymmetry [4] illustrates a connection between quantum computational
resources and symmetric properties of said quantum resources. Finally,
Schur–Weyl duality and its links to permutation symmetry enable quantum de
Finetti theorems [5, 6, 7], which in turn provide the backbone for many tests
of entanglement, particularly in the case of $k$-extendibility [8, 9, 10].

In quantum computing, symmetry can in principle be used to simplify
calculations, speed up computational tasks, or tackle classically intractable
problems. For instance, fully permutationally invariant Hamiltonians have been
shown to be efficiently simulatable on classical hardware [11]. Quantum
algorithms for testing symmetry of states [12], Hamiltonians [13], and open
quantum systems [14] have been investigated in recent work, and some were
shown to delineate a hierarchy of quantum complexity classes [15].
Furthermore, incorporating symmetry into quantum machine learning can reduce
parameter search space and speed up calculations [16, 17, 18].

In physics, a natural complement to symmetry is antisymmetry. Antisymmetry is
of course one particular type of symmetry, observable in nature in fermionic
systems. Antisymmetric properties are pertinent for a variety of physical
phenomena. Time reversal and spatial inversion antisymmetries occur in
magnetic crystallography, where some can be used to classify physical
properties (see [19] and references therein). Additionally, the antisymmetry
inherent in the quantum marginal problem for fermionic systems [20] implies
generalized Pauli constraints for these systems. Particularly relevant to
quantum information tasks, antisymmetric projections have been employed in
relation to the Schmidt rank [21] of quantum states—indeed, we will use this
result later in this work.

In this paper, we propose various quantum algorithms for testing symmetry,
antisymmetry, and the asymmetry of states. In more detail, we delineate
algorithms for projecting quantum states onto the symmetric and antisymmetric
subspaces of the standard representation of a permutation group and then
generalize this procedure to implement projectors in sequence, a process we
term projector concatenation. In combining these mathematical projectors, we
demonstrate how our tests enable us to examine relevant quantum information
tasks, such as testing for Werner-state symmetry and estimating the Schmidt
rank of a pure bipartite state. For these applications, we include example
data from experiments run on the IBM Quantum ibm_kyoto and ibm_osaka
computers. We also show how our algorithms generalize to more generic
projectors. Finally, we examine how a similar framework can realize a quantum
switch that estimates commutators of observables.

The structure of our paper is as follows. In Section II, we review previously
established formalism for symmetry tests and introduce the symmetric and
antisymmetric projectors. In Section III, we show how additional uncomputing
steps allow for realizing both projectors in a single quantum circuit. We then
show how this method can be conducted in sequence to test a state’s projection
onto various subspaces by means of a single circuit. We give examples for
symmetric subspaces and realize the difference of two or more projectors. In
Section IV, we discuss applications of these techniques. In particular, we
show how an antisymmetry test can be used to estimate Schmidt rank and how the
difference of two projectors can be used as a test for Werner-state symmetry.
We also show how an antisymmetrized circuit can be used to estimate
commutators. Finally, we conclude in Section V with a summary of our results
and comments on remaining open problems.

##  II Symmetric and Antisymmetric Projections

###  II.1 Review of Symmetric Projections

This work naturally rests on a foundation of symmetry tests; we will begin
there and then build upon it recursively, generalizing more in each step. Let
us begin by defining precisely what we mean by symmetry and, in turn,
antisymmetry.

Consider a finite group $G$ with a unitary representation
$U:G\to\mathcal{U}(V)$ on a vector space $V$. For such a representation $U$ of
a group $G$, we define the $G$-symmetric subspace by

$\mathcal{S}^{G}\coloneqq\\{|\psi\rangle\in V\ |\
U(g)|\psi\rangle=|\psi\rangle,\ \forall g\in G\\}.$ (1)

Vectors that belong to $\mathcal{S}^{G}$ are called $G$-symmetric vectors. If
$V=\mathcal{H}$ for some Hilbert space $\mathcal{H}$, then the set of
$G$-symmetric density matrices is given by

$\mathcal{S}^{G}_{\rho}\coloneqq\left\\{\rho\in\mathcal{D}(\mathcal{H})\ |\
U(g)\rho U^{\dagger}(g),\ \forall g\in G\right\\},$ (2)

where $\mathcal{D}(\mathcal{H})$ denotes the set of density operators acting
on a Hilbert space $\mathcal{H}$.

A stronger notion of symmetry for density operators, called $G$-Bose symmetry,
is discussed at length in [12], wherein a mixed state $\rho$ is said to be
$G$-Bose symmetric if

$\rho=\Pi_{G}\rho\Pi_{G},$ (3)

with the projector onto the $G$-Bose symmetric subspace defined as

$\Pi_{G}\coloneqq\frac{1}{|G|}\sum_{g\in G}U(g)\,.$ (4)

The projection onto the symmetric subspace has been well studied and is of
interest for many applications (see, e.g., [22, 23, 24]). It should be noted
for clarity that in this work we use the term “projector” to refer to the
mathematical object above and “projection” to refer to the image of a quantum
state after being acted on by such a projector.

It was shown that a test for $G$-Bose symmetry could be achieved using a
generalized phase estimation algorithm, as proposed in [25, Chapter 8], and
Figure 1 depicts this algorithm. Since $G$-Bose symmetry is a strictly
stronger notion than $G$-symmetry, any state exhibiting the former symmetry
naturally demonstrates the latter symmetry as well.

Figure 1: Figure demonstrating the generalized phase estimation applied to
test for $G$-Bose-symmetry of a state, as in (3). The unitary $U^{\rho}$
prepares a purification $\psi_{S^{\prime}S}$ of the state $\rho_{S}$. The
final measurement box with the plus-sign to the right of it indicates to
accept only if the initial superposition state $|+_{G}\rangle$ is measured.
Its acceptance probability is equal to
$\operatorname{Tr}[\Pi_{G}\rho_{S}\Pi_{G}]=\operatorname{Tr}[\Pi_{G}\rho_{S}]$.

For the case where $G$ is the symmetric group $S_{k}$ on $k$ letters, there is
a natural representation $U(\sigma)$ whose action on the tensor-power Hilbert
space $\mathcal{H}^{\otimes k}$ is given by permuting the Hilbert spaces
according to the permutation elements $\sigma$ of $S_{k}$. The space of states
that is invariant under this action is known as the symmetric subspace:

$\mathcal{S}^{S_{k}}\coloneqq\\{|\psi\rangle\in\mathcal{H}^{\otimes k}\ |\
U(\sigma)|\psi\rangle=|\psi\rangle,\ \forall\sigma\in S_{k}\\}.$ (5)

The projection onto $\mathcal{S}^{S_{k}}$ is given by acting on a state with
the projector

$\Pi_{S_{k}}\coloneqq\frac{1}{k!}\sum_{\sigma\in S_{k}}U(\sigma)\,,$ (6)

where, unless stated otherwise, the representation $\\{U(\sigma)\\}_{\sigma\in
S_{k}}$ of the symmetric group is generally taken to be the standard
representation. Explicitly, we consider permutations $\sigma\in S_{k}$ of the
Hilbert space in such a manner that the action of $U(\sigma)$ on a state
$|\phi\rangle_{A_{1}A_{2}\cdots A_{k}}$ is realized as

$U(\sigma)|\phi\rangle_{A_{1}A_{2}\cdots
A_{k}}=|\phi\rangle_{A_{\sigma(1)}A_{\sigma(2)}\cdots A_{\sigma(k)}}\,,$ (7)

where $\\{U(\sigma)\\}_{\sigma\in S_{k}}$ is a unitary representation of
$S_{k}$ in the same manner as those given in [26]. Equivalently,

$U(\sigma)=\sum_{i_{1},\ldots,i_{k}\in[d]}|i_{\sigma^{-1}(1)},\ldots,i_{\sigma^{-1}(n)}\rangle\\!\langle
i_{1},\ldots,i_{k}|,$ (8)

as defined in [24, page 3].

Given the projector onto the symmetric subspace, Ref. [26] gave a construction
to test whether an input state $\rho$ obeys the $S_{k}$-Bose symmetry
condition

$\rho=\Pi_{S_{k}}\rho\Pi_{S_{k}}\,.$ (9)

Using the fact that the symmetric group $S_{k}$ can be generated by acting on
the group $S_{k-1}$ with all transpositions of the type $(i\ k)$, the entire
symmetry test can be achieved using only transpositions and particular choices
of ancilla qubits.

We will now briefly review the construction, but we urge readers to review the
more detailed explanations given in [26] and [27]. The circuit for $S_{k}$ is
generated recursively given a circuit for $S_{k-1}$, and $S_{2}$ can be
constructed explicitly. Define a control state

$|+_{S_{k}}\rangle_{C}\coloneqq\bigotimes_{j=1}^{k}A_{j}|0\rangle^{\otimes
j-1}\,,$ (10)

where $A_{j}$ is a unitary with the following action:

$\displaystyle A_{j}|0\rangle^{\otimes j-1}$
$\displaystyle=\frac{1}{\sqrt{j}}|0\rangle^{\otimes
j-1}+\sqrt{\frac{j-1}{j}}|W_{j-1}\rangle,$ (11)
$\displaystyle=\frac{1}{\sqrt{j}}\left(|0\rangle^{\otimes
j-1}+\sum_{i=1}^{j-1}|2^{i-1}\rangle\right),$ (12)

and $|2^{i-1}\rangle$ is the computational basis state with a one in the
$i$-th position and zeros everywhere else. The $j$-th iteration controls an
array of $j-1$ C-SWAP gates corresponding to transpositions of the form $(i\
j)$, where $i$ runs from $1$ to $j-1$.

To see this, consider generating the test for $S_{3}$. Begin with the circuit
for $S_{2}$, the base case, which is equivalent to the SWAP test between
Hilbert spaces $\mathcal{H}_{1}$ and $\mathcal{H}_{2}$. The control state is
then given by one qubit in the state

$|+_{S_{2}}\rangle=\frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right).$ (13)

To create the test for $S_{3}$, we append to this a layer where $j-1=2$. Thus
two ancilla qubits are necessary to control two new C-SWAP gates, and they are
initialized in the state

$\frac{1}{\sqrt{3}}\left(|00\rangle+|01\rangle+|10\rangle\right),$ (14)

for an overall control state of

$|+_{S_{3}}\rangle\coloneqq\frac{1}{\sqrt{3}}\left(|00\rangle+|01\rangle+|10\rangle\right)\otimes|+_{S_{2}}\rangle\,.$
(15)

Controlling from (15), if the additional two ancilla qubits are in the state
$|01\rangle$, the second and third Hilbert spaces are swapped, realizing the
transposition $(2\ 3)$. If two new ancilla qubits are in the state
$|10\rangle$, the first and third Hilbert spaces are swapped, realizing $(1\
3)$. As before, $|1\rangle$ on the original ancilla realizes a swap between
the first and second Hilbert spaces, or the transposition $(1\ 2)$. There is
some freedom in choosing which transposition corresponds to which control
states, but this general procedure reflects the construction given in Figure 2
and is discussed at length in [27]. With this recipe, the projector
$\Pi_{S_{k}}$ can be realized for every $k$ using circuit depth
$\mathcal{O}(k^{2})$.

Figure 2: Quantum circuit for systematically realizing a test for the
symmetric group, using the procedure described in [26]. The definition of the
unitary $A_{j}$ is given in (11). The symbol $\rho$ refers to a state of $k$
qubits or systems.

###  II.2 Antisymmetric Projection

Let us now consider antisymmetry in terms of the standard representation of a
group—or rather, in terms of permutations. Cayley’s theorem [28] states that
any finite group $G$ is isomorphic to a subgroup of a permutation group, and
so we can safely restrict ourselves to considering group elements as being
isomorphic to permutations without loss of generality. An element
$|\psi\rangle$ in the appropriate vector space $V$ is antisymmetric with
respect to a representation $U$ of a group $G$ if, for every transposition
$\sigma^{\prime}\in G$, we have that

$U(\sigma^{\prime})|\psi\rangle=(-1)|\psi\rangle\,.$ (16)

Equivalently, an antisymmetric vector $|\psi\rangle$ is defined by

$U(\sigma)|\psi\rangle=\text{sgn}(\sigma)|\psi\rangle\,,$ (17)

where $\text{sgn}(\sigma)$ denotes the sign of the permutation $\sigma$.

To model this action on quantum states, let us consider permutations of
systems acting as in (7), and define single transpositions $\sigma_{ij}$ that
swap the $i$-th and $j$-th systems, and some multipartite state
$\rho_{A_{1}\cdots A_{k}}$, which is defined on a tensor-product Hilbert space
$\mathcal{H}^{\otimes k}$. Then we propose a test analogous to (9), wherein we
define the antisymmetric projector

$\Pi_{\textrm{anti}_{k}}\coloneqq\frac{1}{k!}\sum_{\sigma\in
S_{k}}\operatorname{sgn}(\sigma)U(\sigma)\,,$ (18)

where $\\{U(\sigma)\\}_{\sigma\in S_{k}}$ is a unitary representation of
$S_{k}$ in the same manner as that given in [26]; specifically, we choose a
unitary representation such that it obeys the desired group action described
in (7).

Given this definition of antisymmetry, a corresponding algorithmic test can be
distilled from that in [26, 27]. The circuit construction is depicted in
Figure 3.

Figure 3: Figure demonstrating how to systematically generate a test for
antisymmetry. The definition of the unitaries $A_{j}$ is given in (11), and
$\overline{Z}_{n}$ is defined in (20). The symbol $\rho$ refers to a state on
$k$ qubits or systems.

As a reminder, the control state for that algorithm is

$|+_{S_{k}}\rangle_{C}\coloneqq\bigotimes_{j=1}^{k}A_{j}|0\rangle^{\otimes
j-1}\,,$ (19)

where the action of the unitary $A_{j}$ is given in (11). Here we take the
same approach shown in Figure 2, but additionally perform the operation
$\overline{Z}_{k-1}\otimes\cdots\otimes\overline{Z}_{1}$ after the C-SWAP
gates. The operation $\overline{Z}_{n}$ is defined as follows:

$\overline{Z}_{n}\coloneqq Z^{\otimes n},$ (20)

where $n$ is the number of qubits in the register. After this change, the
effective controlled unitary in each instance is given by

$\operatorname*{C-antiSWAP}({i,j})\coloneqq|0\rangle\\!\langle
0|_{C}\otimes\mathbb{I}_{i,j}\\\ +|1\rangle\\!\langle
1|_{C}\otimes(-1)U(\sigma_{i,j}),$ (21)

where $C$ is the specific qubit controlling the swap and $i,j$ are the spaces
to be swapped. Additionally, $U(\sigma_{i,j})$ is a SWAP gate acting on the
$i$th and $j$th registers. Replacing all of the controlled-SWAPs in the
algorithm with $\operatorname*{C-antiSWAP}_{i,j}$ gives an overall
implementation of the antisymmetric projector in (18):

$\langle+_{S_{k}}|_{C}\
\prod_{j=2}^{k}\prod_{i=1}^{j-1}\operatorname*{C-antiSWAP}(i,j)|+_{S_{k}}\rangle_{C}=\Pi_{\textrm{anti}_{k}}\,.$
(22)

Therefore, a test of antisymmetry can be easily generated from a corresponding
test of symmetry.

##  III Concatenating Projectors

###  III.1 Uncomputing to Expand upon a Symmetry Test

The approach in Figure 1 can be expanded upon by means of uncomputation.
Uncomputation refers to a technique commonly employed in quantum algorithms
wherein a computation is performed in reverse after the desired output has
been coherently stored [29, 30]. Of course, as with many quantum algorithms,
the control state is already undergoing some uncomputation. However, by
reversing the action on the remaining systems, the outcome can be used to
measure not only the projection onto the symmetric subspace but also the
projection onto the asymmetric space as well.

The rough sketch of the algorithm goes as thus: perform a symmetry testing
circuit on the state in question. Then, instead of performing the usual
measurement, store the acceptance outcome in an additional ancilla by
performing a CNOT controlled off of the all-zeros outcome. After this,
uncompute the symmetry test by reversing the order of the gates in the
original test and taking their conjugate transposes. If the new ancilla qubit
is measured, the probability that we measure one is
$\left\|\Pi_{G}|\psi\rangle\right\|_{2}^{2}$ and the probability to measure
zero is $\left\|\left(\mathbb{I}-\Pi_{G}\right)|\psi\rangle\right\|_{2}^{2}$.
Furthermore, the post-measurement state will be proportional to
$\Pi_{G}|\psi\rangle$ in the first case and to
$\left(\mathbb{I}-\Pi_{G}\right)|\psi\rangle$ in the second case. Therefore,
this algorithm can measure the symmetric and asymmetric projections of a state
using a single circuit and in a coherent manner.

We will now give a more thorough, mathematical description of the algorithm.

###### Algorithm 1

Given a unitary representation $\left\\{U(g)\right\\}_{g\in G}$ of a group
$G$, we can implement the group projection from (4) with the correct output
probability distribution and post-measurement states, by performing the
following steps:

  1. 1.

Prepare the state
$|+_{G}\rangle_{C}\coloneqq\frac{1}{\sqrt{\left|G\right|}}\sum_{g\in
G}|g\rangle_{C}$.

  2. 2.

Perform the controlled unitary $\sum_{g\in G}|g\rangle\\!\langle g|_{C}\otimes
U(g)$ from the control register to the data register.

  3. 3.

Prepare a control qubit in the state $|0\rangle_{C^{\prime}}$ and perform the
controlled unitary

$X_{C^{\prime}}\otimes|+_{G}\rangle\\!\langle+_{G}|_{C}+\mathbb{I}_{C^{\prime}}\otimes\left(\mathbb{I}-|+_{G}\rangle\\!\langle+_{G}|\right)_{C}.$
(23)

  4. 4.

Perform the controlled unitary $\sum_{g\in G}|g\rangle\\!\langle g|_{C}\otimes
U^{{\dagger}}(g)$ from the first control register $C$ to the data register.

  5. 5.

Optional: discard the control register $C$.

  6. 6.

Measure the register $C^{\prime}$ in the computational basis.

Figure 4: Figure demonstrating the use of uncomputation to generalize the
previous symmetry test. The gate $P$ acts on the all-zeros state to create a
superposition $|+_{G}\rangle$, and $\\{U(g)\\}_{g\in G}$ denotes the unitary
representation of $G$. The target qubit is measured to be in the $|0\rangle$
state with probability $\operatorname{Tr}[\Pi_{G}\rho]$ or in the $|1\rangle$
state with probability $\operatorname{Tr}[(\mathbb{I}-\Pi_{G})\rho]$.
Furthemore, the post-measurement state is proportional to $\Pi_{G}\rho\Pi_{G}$
or $(\mathbb{I}-\Pi_{G})\rho(\mathbb{I}-\Pi_{G})$, depending on the
measurement outcome.

Figure 4 depicts the approach. Following the procedure above, the initial
state of the algorithm after step one is
$|0\rangle_{C^{\prime}}|+_{G}\rangle_{C}|\psi\rangle$ where

$|+_{G}\rangle_{C}\coloneqq\frac{1}{\sqrt{|G|}}\sum_{g\in G}|g\rangle_{C}\,,$
(24)

a choice of control state we will employ often. After step two, the overall
state of the system is

$\frac{1}{\sqrt{|G|}}\sum_{g\in
G}|0\rangle_{C^{\prime}}|g\rangle_{C}U(g)|\psi\rangle\,.$ (25)

Figure 5: For convenience, we define a plus or minus controlled gate. The gate
$P$ prepares the state $|+_{G}\rangle$ on $n$ qubits; by convention, we say
that applying a $Z$ gate to each qubit of the $|+_{G}\rangle$ state generates
the $|-_{G}\rangle$ state. The controlled gate flips the target qubit if a)
the control is in the $|+_{G}\rangle$ state or b) the control is in the
$|-_{G}\rangle$ state, respectively. The operation $\overline{Z}_{n}$ is
defined in (20).

Here, we depart from the procedure followed in [12]. Instead of measuring the
control qubit after uncomputing, perform a controlled operation using the
$|+_{G}\rangle$ as a control state instead of a $|0\rangle$ or $|1\rangle$
instance. This change of control is shown in Figure 5a), where we define a
circuit diagram for use in future algorithms. After the controlled unitary in
step three, the state of the system is

$\left[X_{C^{\prime}}\otimes|+_{G}\rangle\\!\langle+_{G}|_{C}+\mathbb{I}_{C^{\prime}}\otimes\left(\mathbb{I}-|+_{G}\rangle\\!\langle+_{G}|\right)_{C}\right]\
\times\\\ \frac{1}{\sqrt{|G|}}\sum_{g\in
G}|0\rangle_{C^{\prime}}|g\rangle_{C}U(g)|\psi\rangle\,.$ (26)

Before continuing, let us observe a few facts. First, building from the logic
of the symmetry test depicted in Figure 1, we know that

$(\langle+_{G}|_{C}\otimes\mathbb{I})\frac{1}{\sqrt{|G|}}\sum_{g\in
G}|g\rangle_{C}\otimes U(g)=\Pi_{G}\,.$ (27)

Indeed, the algorithm presented in [12] depends on this fact. Furthermore,
since $\Pi_{G}$ is a projector formed from the sum over the unitary
representation, observe that

$U(g)\Pi_{G}=U^{\dagger}(g)\Pi_{G}=\Pi_{G}\,.$ (28)

Equipped with these facts, we can rewrite (26) as

$|1\rangle_{C^{\prime}}|+_{G}\rangle_{C}\Pi_{G}|\psi\rangle-|0\rangle_{C^{\prime}}|+_{G}\rangle_{C}\Pi_{G}|\psi\rangle\\\
+\frac{1}{\sqrt{|G|}}\sum_{g\in
G}|0\rangle_{C^{\prime}}|g\rangle_{C}U(g)|\psi\rangle\,.$ (29)

From here, we progress to step four. Using the property in (28), the state of
the system after step four is

$\displaystyle|1\rangle_{C^{\prime}}|+_{G}\rangle_{C}\Pi_{G}|\psi\rangle-|0\rangle_{C^{\prime}}|+_{G}\rangle_{C}\Pi_{G}|\psi\rangle+|0\rangle_{C^{\prime}}|+_{G}\rangle_{C}|\psi\rangle$
$\displaystyle=|1\rangle_{C^{\prime}}|+_{G}\rangle_{C}(\Pi_{G}|\psi\rangle)+|0\rangle_{C^{\prime}}|+_{G}\rangle_{C}(\mathbb{I}-\Pi_{G})|\psi\rangle$
(30)
$\displaystyle=|+_{G}\rangle_{C}\otimes\big{[}|1\rangle_{C^{\prime}}(\Pi_{G}|\psi\rangle)+|0\rangle_{C^{\prime}}(\mathbb{I}-\Pi_{G})|\psi\rangle\big{]}\,.$
(31)

Since the $C$ register is in tensor product with the other registers, it can
be discarded. We will elect to do so, in order to clean up notation. This
gives the final state of the system:

$|1\rangle_{C^{\prime}}\Pi_{G}|\psi\rangle+|0\rangle_{C^{\prime}}\left(\mathbb{I}-\Pi_{G}\right)|\psi\rangle\,.$
(32)

From (32), we can clearly see that, if we measure register $C^{\prime}$ in the
standard basis, then we will detect $C^{\prime}$ to be in the state
$|1\rangle$ with probability

$\Pr(|1\rangle_{C^{\prime}})=\left\|\Pi_{G}|\psi\rangle\right\|_{2}^{2}\,,$
(33)

with post-measurement state

$\frac{\Pi_{G}|\psi\rangle}{\left\|\Pi_{G}|\psi\rangle\right\|_{2}^{2}}\,.$
(34)

Furthermore, we will detect the state $|0\rangle$ with probability

$\Pr(|0\rangle_{C^{\prime}})=\left\|\left(\mathbb{I}-\Pi_{G}\right)|\psi\rangle\right\|_{2}^{2}\,,$
(35)

with post-measurement state

$\frac{\left(\mathbb{I}-\Pi_{G}\right)|\psi\rangle}{\left\|\left(\mathbb{I}-\Pi_{G}\right)|\psi\rangle\right\|_{2}^{2}}\,.$
(36)

The result in (35)–(36) can be understood as realizing the projection onto the
asymmetric subspace. Thus, we have accomplished our task of generalizing the
symmetric test to realize both projections simply by performing additional
uncomputation. Previous implementations [12] of this type of symmetry test
gave an estimate of the projection onto the symmetric subspace by measuring
the ancilla qubit. By adding additional ancilla qubits to the control register
and then acting on the data register with the Hermitian conjugate of the
symmetry testing algorithms, we have created a way to realize either the
symmetric and asymmetric projections probabilistically. Furthermore, we know
that the post-measurement state will either be symmetric or asymmetric
according to the outcome of the measurement.

###  III.2 Realizing the Antisymmetric Projection

A similar method can be employed for the antisymmetric test given in Section
II.2, which gives analogous results. Define the antisymmetric projector for a
group $G$ as

$\Pi_{\mathcal{A}}\coloneqq\frac{1}{|G|}\sum_{g\in
G}\operatorname{sgn}(g)U(g).$ (37)

This can be understood as a specific symmetry where the representation is
defined as $\\{\operatorname{sgn}(g)U(g)\\}_{g\in G}$, that is, a
representation identical to that of the symmetric group up to the sign of the
group element. While the sign of the group element may seem nebulously
defined, for finite groups there is a clear meaning, as previously stated.
Cayley’s theorem states that all groups are isomorphic to a subgroup of the
full permutation group. The elements of a permutation group have a well-
defined sign, as even permutations have sign $+1$ and odd-order permutations
have sign $-1$. Thus, to determine the sign of a group element, it suffices to
determine the sign of its corresponding permutation under Cayley’s theorem.

For completeness, we now detail the procedure.

###### Algorithm 2

The algorithm consists of the following steps:

  1. 1.

Prepare the state
$|+_{G}\rangle_{C}\coloneqq\frac{1}{\sqrt{\left|G\right|}}\sum_{g\in
G}|g\rangle_{C}$.

  2. 2.

Perform the controlled unitary $\sum_{g\in G}|g\rangle\\!\langle g|_{C}\otimes
U(g)$ from the control register to the data register.

  3. 3.

Act on every control qubit, changing the sign of all odd-parity basis states
to $-1$. This is equivalent to applying the unitary $\sum_{g\in
G}\operatorname{sgn}(g)|g\rangle\\!\langle g|_{C}$.

  4. 4.

Prepare another control qubit in the state $|0\rangle_{C^{\prime}}$ and
perform the controlled unitary

$X_{C^{\prime}}\otimes|+_{G}\rangle\\!\langle+_{G}|_{C}+\mathbb{I}_{C^{\prime}}\otimes\left(\mathbb{I}-|+_{G}\rangle\\!\langle+_{G}|\right)_{C}.$
(38)

  5. 5.

Act on the control qubits once more to change the sign of all odd-parity basis
states (equivalent to applying the unitary $\sum_{g\in
G}\operatorname{sgn}(g)|g\rangle\\!\langle g|_{C}$).

  6. 6.

Perform the controlled unitary $\sum_{g\in G}|g\rangle\\!\langle g|_{C}\otimes
U^{{\dagger}}(g)$ from the control register to the data register.

  7. 7.

Optional: discard the control register $C$.

  8. 8.

Measure the register $C^{\prime}$ in the computational basis.

The first two steps are identical to those used for the symmetric projection,
and the state of the system afterward is given by

$\frac{1}{\sqrt{|G|}}\sum_{g\in
G}|0\rangle_{C^{\prime}}|g\rangle_{C}U(g)|\psi\rangle\,,$ (39)

as before. Now, before moving on to the third step, define the state

$|-_{G}\rangle\coloneqq\frac{1}{\sqrt{|G|}}\sum_{g\in
G}\operatorname{sgn}(g)|g\rangle\,.$ (40)

It is easily checked that, for permutation groups,
$\overline{Z}_{n}|+_{G}\rangle=|-_{G}\rangle$ when the control state on $n$
qubits is constructed in such a way that odd-parity basis states in the
control are used to represent odd-parity permutations. As alluded to in
Section II.2, any finite group can be thought of as a subgroup of a
permutation group, and so this manner of creating $|-_{G}\rangle$ from
$|+_{G}\rangle$ generalizes in principle. Indeed, this is a natural way of
constructing the control register. If the identity group element $g=e$ is
associated to $|0\rangle^{\otimes n}$ for $n$ ancilla qubits, then the first
transposition $g=(1\ 2)$ in $S_{2}$ can be associated to $|0\rangle^{\otimes
n-1}\otimes|1\rangle$, and so on for each additional transposition. This
exactly follows the construction in Figure 2. Thus we can combine steps 3-5
into a single step where the effective controlled unitary is instead

$X_{C^{\prime}}\otimes|-_{G}\rangle\\!\langle-_{G}|_{C}+\mathbb{I}_{C^{\prime}}\otimes\left(\mathbb{I}-|-_{G}\rangle\\!\langle-_{G}|\right)_{C}.$
(41)

Note that this is completely equivalent to the $\operatorname*{C-antiSWAP}$
construction used previously in Section II.2 for the antisymmetry test; the
Pauli-$Z$ gates have merely been absorbed into the control state instead of
the controlled unitary. Similar to how the $|+_{G}\rangle$ state was used to
alter a controlled-NOT gate, this state will also be used in that manner. This
is depicted in Figure 5b).

After applying the new controlled unitary as described above, the state of the
system is given by

$\left[X_{C^{\prime}}\otimes|-_{G}\rangle\\!\langle-_{G}|_{C}+\mathbb{I}_{C^{\prime}}\otimes\left(\mathbb{I}-|-_{G}\rangle\\!\langle-_{G}|\right)_{C}\right]\
\times\\\ \frac{1}{\sqrt{|G|}}\sum_{g\in
G}|0\rangle_{C^{\prime}}|g\rangle_{C}U(g)|\psi\rangle,$ (42)

which in turn simplifies to

$|1\rangle_{C^{\prime}}|-_{G}\rangle_{C}\Pi_{\mathcal{A}}|\psi\rangle-|0\rangle_{C^{\prime}}|-_{G}\rangle_{C}\Pi_{\mathcal{A}}|\psi\rangle+\\\
|0\rangle_{C^{\prime}}\frac{1}{\sqrt{|G|}}\sum_{g\in
G}|g\rangle_{C}U(g)|\psi\rangle\,.$ (43)

This simplification can be computed directly from the definition of the
antisymmetric projector given in (18) and an analogous version of (27) with
respect to the antisymmetric projector:

$(\langle-_{G}|_{C}\otimes\mathbb{I})\frac{1}{\sqrt{|G|}}\sum_{g\in
G}|g\rangle_{C}\otimes U(g)=\Pi_{\mathcal{A}}\,.$ (44)

Next, we uncompute the data register via the controlled unitary $\sum_{g\in
G}|g\rangle\\!\langle g|_{C}\otimes U^{{\dagger}}(g)$. The state is then given
by

$|1\rangle_{C^{\prime}}\frac{1}{\sqrt{|G|}}\sum_{g\in
G}\operatorname{sgn}(g)|g\rangle
U^{\dagger}(g)\Pi_{\mathcal{A}}|\psi\rangle\\\
-|0\rangle_{C^{\prime}}\frac{1}{\sqrt{|G|}}\sum_{g\in
G}\operatorname{sgn}(g)|g\rangle
U^{\dagger}(g)\Pi_{\mathcal{A}}|\psi\rangle\\\
+|0\rangle_{C^{\prime}}\frac{1}{\sqrt{|G|}}\sum_{g\in
G}|g\rangle_{C}|\psi\rangle.$ (45)

Now, using the fact that

$\operatorname{sgn}(g)U(g)\Pi_{\mathcal{A}}=\operatorname{sgn}(g)U^{\dagger}(g)\Pi_{\mathcal{A}}=\Pi_{\mathcal{A}},$
(46)

the state simplifies to

$|1\rangle_{C^{\prime}}|+_{G}\rangle_{C}\Pi_{\mathcal{A}}|\psi\rangle+|0\rangle_{C^{\prime}}|+_{G}\rangle_{C}(\mathbb{I}-\Pi_{\mathcal{A}})|\psi\rangle.$
(47)

After this, we discard the control register $C$. Then the state of the system
is

$|1\rangle_{C^{\prime}}\Pi_{\mathcal{A}}|\psi\rangle+|0\rangle_{C^{\prime}}(\mathbb{I}-\Pi_{\mathcal{A}})|\psi\rangle\,.$
(48)

We can now see that, if we measure register $C^{\prime}$ in the standard
basis, then we will detect $C^{\prime}$ to be in the state $|1\rangle$ with
probability

$\Pr(|1\rangle_{C^{\prime}})=\left\|\Pi_{\mathcal{A}}|\psi\rangle\right\|_{2}^{2}\,,$
(49)

and with post-measurement state

$\frac{\Pi_{\mathcal{A}}|\psi\rangle}{\left\|\Pi_{\mathcal{A}}|\psi\rangle\right\|_{2}^{2}}.$
(50)

Furthermore, we detect the state $|0\rangle$ with probability

$\Pr(|0\rangle_{C^{\prime}})=\left\|\left(\mathbb{I}-\Pi_{\mathcal{A}}\right)|\psi\rangle\right\|_{2}^{2}\,,$
(51)

and with post-measurement state

$\frac{\left(\mathbb{I}-\Pi_{\mathcal{A}}\right)|\psi\rangle}{\left\|\left(\mathbb{I}-\Pi_{\mathcal{A}}\right)|\psi\rangle\right\|_{2}^{2}}.$
(52)

###  III.3 Generalizing the Construction

Let us now attempt to further generalize our previous constructions. In the
prior sections, we were able to realize projections of a state onto a
symmetric subspace by uncomputing the circuit used to realize the projector;
however, we can imagine using the same procedure to combine the action of two
different group projectors. We will refer to this procedure throughout as
concatenating the projectors, in reference to how the projectors are
essentially performed in series within a single algorithm. The projectors
should act on the same number of qubits, but a projector that acts on a
smaller system can essentially be padded to a larger one via tensoring with
the identity.

Suppose that we have a unitary representation $\\{V(h)\\}_{h\in H}$ of another
group $H$. We can then follow the exact procedure from Section III.1 only
replacing the superposition state with

$|+_{H}\rangle_{C}\coloneqq\frac{1}{\sqrt{|H|}}\sum_{h\in H}|h\rangle_{C}\,.$
(53)

Then the first controlled unitary, used in step two, becomes

$\sum_{h\in H}|h\rangle\\!\langle h|_{C}\otimes V(h)\,,$ (54)

and the final controlled unitary, used in step four, becomes

$\sum_{h\in H}|h\rangle\\!\langle h|_{C}\otimes V^{\dagger}(h)\,.$ (55)

Implementing these substitutions, the resultant state before measurement is

$|1\rangle_{C^{\prime}}\Pi_{H}|\psi\rangle+|0\rangle_{C^{\prime}}\left(\mathbb{I}-\Pi_{H}\right)|\psi\rangle\,,$
(56)

where the projection $\Pi_{H}$ is defined as

$\Pi_{H}\coloneqq\frac{1}{|H|}\sum_{h\in H}V(h)\,.$ (57)

Let us now consider cascading the two procedures. In this construction,
depicted in Figure 6, we first perform the approach for the group $G$ and then
follow it with the circuit corresponding to $H$. To achieve this, two ancilla
qubits are necessary, which we denote $C^{\prime}_{1}$ and $C^{\prime}_{2}$,
respectively. (A note of caution: the group representations should act on
Hilbert spaces of the same size, and if $|G|\neq|H|$, the control state on $C$
will have to be discarded after the first algorithm and cannot be reused.) The
transformation realized by this concatenation is

$|\psi\rangle\to|1\rangle_{C^{\prime}_{1}}|1\rangle_{C^{\prime}_{2}}\Pi_{H}\Pi_{G}|\psi\rangle+|1\rangle_{C^{\prime}_{1}}|0\rangle_{C^{\prime}_{2}}\Pi_{H}\left(\mathbb{I}-\Pi_{G}\right)|\psi\rangle\\\
+|0\rangle_{C^{\prime}_{1}}|1\rangle_{C^{\prime}_{2}}\left(\mathbb{I}-\Pi_{H}\right)\Pi_{G}|\psi\rangle\\\
+|0\rangle_{C^{\prime}_{1}}|0\rangle_{C^{\prime}_{2}}\left(\mathbb{I}-\Pi_{H}\right)\left(\mathbb{I}-\Pi_{G}\right)|\psi\rangle\,.$
(58)

Figure 6: Quantum circuit demonstrating the concatenation of two projectors in
sequence. $\\{U(g)\\}$ is a unitary representation of one group and
$\\{V(h)\\}$ is a unitary representation of another. Both unitary
representations should act on spaces of the same dimension.

###  III.4 Examples

####  III.4.1 Concatenating Symmetric and Antisymmetric Projectors

For a pertinent example, consider concatenating the approach from Section
III.3 for the symmetric and antisymmetric projectors of a group $G$. Then
$H=G$, and the two unitary representations can both be taken to be
$\\{U(\sigma)\\}_{\sigma\in G}$. This allows us to use the same control
register $C$ for both projectors. Then we can construct a simplified circuit
as in Figure 7, because the two controlled unitaries in the middle of Figure 6
are inverses of each other and therefore cancel out (keeping in mind that
there is a single control register $C$ in this special case). To illustrate
this, we begin with an initial state given by

$|00\rangle_{C^{\prime}C^{\prime\prime}}|+_{G}\rangle_{C}|\psi\rangle=\frac{1}{\sqrt{|G|}}\sum_{g\in
G}|00\rangle_{C^{\prime}C^{\prime\prime}}|g\rangle_{C}|\psi\rangle\,.$ (59)

In the second step we implement the controlled unitary $\sum_{g\in
G}|g\rangle\\!\langle g|_{C}\otimes U(g)$ and the $|+_{G}\rangle_{C}$
controlled gate successively. This step realizes the state

$\displaystyle\frac{1}{\sqrt{|G|}}$ $\displaystyle\sum_{g\in
G}|00\rangle_{C^{\prime}C^{\prime\prime}}|g\rangle_{C}U(g)|\psi\rangle$
$\displaystyle\to\Bigg{[}\big{(}X_{C^{\prime}}\otimes|+_{G}\rangle\\!\langle+_{G}|_{C}\big{)}+\big{(}\mathbb{I}_{C^{\prime}}\otimes(\mathbb{I}_{C}-|+_{G}\rangle\\!\langle+_{G}|_{C})\big{)}\Bigg{]}$
$\displaystyle\qquad\qquad\frac{1}{\sqrt{|G|}}\sum_{g\in
G}|00\rangle_{C^{\prime}C^{\prime\prime}}|g\rangle_{C}U(g)|\psi\rangle$ (60)
$\displaystyle=|0\rangle_{C^{\prime\prime}}\Bigg{[}|0\rangle_{C^{\prime}}\left(\frac{1}{\sqrt{|G|}}\sum_{g\in
G}|g\rangle
U(g)|\psi\rangle-|+_{G}\rangle\Pi_{\mathcal{S}}|\psi\rangle\right)$
$\displaystyle\qquad\qquad\qquad\qquad+|1\rangle_{C^{\prime}}|+_{G}\rangle\Pi_{\mathcal{S}}|\psi\rangle\Bigg{]}.$
(61)

Note that the controlled-NOT gate acting on registers $C$ and $C^{\prime}$
essentially coherently couples the projection onto the symmetric subspace with
the ancilla in register $C^{\prime}$. The next step will act similarly with
regard to the antisymmetric projection. By performing the $|-_{G}\rangle$
controlled gate from register $C$ to register $C^{\prime\prime}$, the state is
now

$\displaystyle|00\rangle_{C^{\prime}C^{\prime\prime}}\Bigg{(}\langle-_{G}|+_{G}\rangle|-_{G}\rangle_{C}\Pi_{\mathcal{S}}-|+_{G}\rangle_{C}\Pi_{\mathcal{S}}$
$\displaystyle\qquad\qquad+\frac{1}{\sqrt{G}}\sum_{g\in
G}|g\rangle_{C}U(g)-|-_{G}\rangle_{C}\Pi_{\mathcal{A}}\Bigg{)}|\psi\rangle$
$\displaystyle+|01\rangle_{C^{\prime}C^{\prime\prime}}|-_{G}\rangle_{C}\left(\Pi_{\mathcal{A}}-\langle-_{G}|+_{G}\rangle\Pi_{\mathcal{S}}\right)|\psi\rangle$
$\displaystyle+|10\rangle_{C^{\prime}C^{\prime\prime}}\left(|+_{G}\rangle_{C}\Pi_{\mathcal{S}}-\langle-_{G}|+_{G}\rangle|-_{G}\rangle_{C}\Pi_{\mathcal{S}}\right)|\psi\rangle$
$\displaystyle+|11\rangle_{C^{\prime}C^{\prime\prime}}|-_{G}\rangle_{C}\langle-_{G}|+_{G}\rangle\Pi_{\mathcal{A}}\Pi_{\mathcal{S}}|\psi\rangle.$
(62)

Next define the following quantity

$G_{p}\coloneqq\langle-_{G}|+_{G}\rangle=\frac{1}{|G|}\sum_{g\in
G}\operatorname{sgn}(g)\,.$ (63)

Note that this quantity is equal to zero for the symmetric group $S_{k}$, but
it is non-zero in some cases, e.g., for the cyclic group $Z_{3}$, for which
every group element corresponds to an even permutation.

Finally, applying the last controlled unitary $\sum_{g\in
G}|g\rangle\\!\langle g|_{C}\otimes U^{\dagger}(g)$, we get the following
state:

$|00\rangle_{C^{\prime}C^{\prime\prime}}\left[|+_{G}\rangle\mathbb{I}-|+_{G}\rangle\Pi_{\mathcal{A}}-|+_{G}\rangle\Pi_{\mathcal{S}}+G_{p}|-_{G}\rangle\Pi_{\mathcal{S}}\right]|\psi\rangle\\\
+|01\rangle_{C^{\prime}C^{\prime\prime}}\left[|+_{G}\rangle\Pi_{\mathcal{S}}-G_{p}|-_{G}\rangle\Pi_{\mathcal{S}}\right]|\psi\rangle\\\
\qquad+|10\rangle_{C^{\prime}C^{\prime\prime}}\left[|+_{G}\rangle\Pi_{\mathcal{A}}-G_{p}|-_{G}\rangle\Pi_{\mathcal{S}}\right]|\psi\rangle\\\
+|11\rangle_{C^{\prime}C^{\prime\prime}}\left[G_{p}|-_{G}\rangle\Pi_{\mathcal{S}}\right]|\psi\rangle.$
(64)

In the case that $G$ is the symmetric group $S_{k}$, it follows that
$G_{p}=\langle-_{G}|+_{G}\rangle=0$. Substituting for $G_{p}$, we find that
the final state is then given by

$|00\rangle_{C^{\prime}C^{\prime\prime}}|+_{G}\rangle\left[\mathbb{I}-\Pi_{\mathcal{A}}-\Pi_{\mathcal{S}}\right]|\psi\rangle\\\
+|01\rangle_{C^{\prime}C^{\prime\prime}}|+_{G}\rangle\Pi_{\mathcal{S}}|\psi\rangle\\\
\qquad+|10\rangle_{C^{\prime}C^{\prime\prime}}|+_{G}\rangle\Pi_{\mathcal{A}}|\psi\rangle.$
(65)

Lastly, also in the case that $G=S_{k}$, we find the following probabilities
upon measuring the state of the $C^{\prime}$ and $C^{\prime\prime}$ qubits:

$\displaystyle P(|00\rangle_{C^{\prime}C^{\prime\prime}})$
$\displaystyle=\left\|(\mathbb{I}-\Pi_{\mathcal{S}}-\Pi_{\mathcal{A}})|\psi\rangle\right\|_{2}^{2}\,,$
(66) $\displaystyle P(|01\rangle_{C^{\prime}C^{\prime\prime}})$
$\displaystyle=\left\|\Pi_{\mathcal{A}}|\psi\rangle\right\|_{2}^{2}\,,$ (67)
$\displaystyle P(|10\rangle_{C^{\prime}C^{\prime\prime}})$
$\displaystyle=\left\|\Pi_{\mathcal{S}}|\psi\rangle\right\|_{2}^{2}\,,$ (68)
$\displaystyle P(|11\rangle_{C^{\prime}C^{\prime\prime}})$
$\displaystyle=0\,.$ (69)

Note that the probability of measuring the state $|11\rangle$ corresponds to
measuring $\Pi_{\mathcal{S}}\Pi_{\mathcal{A}}|\psi\rangle$, which is always
equal to zero in the case that $G=S_{k}$.

The specific example of $S_{3}$, the symmetric group on three letters, is
described at length in Section III.4.2, the next section.

Figure 7: The above circuit first performs the symmetric projection, followed
by the antisymmetric projection.

####  III.4.2 Three Irreps of $S_{3}$

In this example, we recover the projections onto each of the three irreps of
the group $S_{3}$ by concatenating the symmetric and antisymmetric projection
circuits. As discussed in the previous section, both projectors utilize the
same representations, $\\{U(g)\\}_{g\in G}=\\{V(h)\\}_{h\in H}$. This allows
for a simplification of the middle portion of the algorithm, where

$U^{\dagger}(g)V(h)=U^{\dagger}(g)U(g)=\mathbb{I}\,,$ (70)

as $h=g$ for this specific combination of projectors as long as the same
initial control state $|+_{G}\rangle$ is used. This simplifies the resultant
circuit, as the intermediary unitaries cancel. Indeed, such a simplification
can be employed anytime the two projectors utilize the same unitaries in their
representation. Since $S_{3}$ is a particular symmetric group, it follows that
the final state before measurement is given by (65) and the final measurement
probabilities are given by (66)–(69).

It is worth remembering, at this juncture, that all of these algorithms are
necessarily dependent on the representation that is employed, even though this
is often suppressed in the literature. For example, if we take the
representation of $S_{3}$ that maps each transposition to a SWAP gate between
two-dimensional Hilbert spaces (i.e., $(1\
2)\to\operatorname{SWAP}_{A_{1}A_{2}}$), then the antisymmetric projector here
is exactly zero. Indeed, there are no three-qubit states that demonstrate such
antisymmetry. To guarantee a nontrivial antisymmetric subspace under these
types of representations, we require that the dimension $d$ of the individual
systems is greater than or equal to the number of systems to be permuted, $n$,
because the size of the antisymmetric subspace is then given by
$\binom{d}{n}$. Thus, using qudits, or systems of more than one qubit with
controlled-SWAPs replaced by a concatenation of several controlled-SWAPs with
the same control qubit, would give a nontrivial antisymmetric projector.

However, other choices of representations can also yield nontrivial results.
We choose a two-qubit unitary representation to demonstrate this in the
example below. In principle, any group representation that respects the group
action and the sign representation should be adaptable to these algorithms.
Consider the representation of $S_{3}$ on two qubits that maps the
transposition $(1\ 2)$ to the Hadamard gate on both qubits and $(2\ 3)$ to
applying a SWAP gate, CNOT gate, and then the Hadamard gate on both qubits.
This is equivalent to mapping $(1\ 2\ 3)$ to the operation
$\operatorname{CNOT}\cdot\operatorname{SWAP}$, as shown in Table 1. A quick
check can verify that this obeys the group action of $S_{3}$. Then the
symmetric projector is

$\Pi_{\mathcal{S}}=\frac{1}{4}\begin{pmatrix}3&1&1&1\\\
1&\nicefrac{{1}}{{3}}&\nicefrac{{1}}{{3}}&\nicefrac{{1}}{{3}}\\\
1&\nicefrac{{1}}{{3}}&\nicefrac{{1}}{{3}}&\nicefrac{{1}}{{3}}\\\
1&\nicefrac{{1}}{{3}}&\nicefrac{{1}}{{3}}&\nicefrac{{1}}{{3}}\\\
\end{pmatrix}\,,$ (71)

and the antisymmetric projector is

$\Pi_{\mathcal{A}}=\frac{1}{4}\begin{pmatrix}1&-1&-1&-1\\\ -1&1&1&1\\\
-1&1&1&1\\\ -1&1&1&1\\\ \end{pmatrix}\,.$ (72)

$\sigma\in S_{3}$ |  $U(\sigma)$
---|---
e |  $\mathbb{I}$
$(1\ 2)$ |  $H\otimes H$
$(2\ 3)$ |  $(H\otimes H)\operatorname{CNOT}\cdot\operatorname{SWAP}$
$(1\ 3)$ |  $(H\otimes H)\operatorname{SWAP}\cdot\operatorname{CNOT}$
$(1\ 2\ 3)$ |  $\operatorname{CNOT}\cdot\operatorname{SWAP}$
$(1\ 3\ 2)$ |  $\operatorname{SWAP}\cdot\operatorname{CNOT}$
Table 1: An example representation of $S_{3}$ on two qubits.

Thus, in this example, we can estimate the projection of the state
$|\psi\rangle$ onto any of the three irreps of $S_{3}$. For larger symmetric
groups, additional projectors could be added to sequentially project onto
different subspaces.

####  III.4.3 Difference of Two Projectors

Consider a unitary that can be written as the difference of two projectors,
$U=P-Q$, where $P$ and $Q$ are projectors. A specific example of this is the
SWAP gate, which can be written as SWAP $=\Pi_{\mathcal{S}}-\Pi_{\mathcal{A}}$
and which we will discuss at more length in Section IV.2 in the context of
determining Werner-state asymmetry of a bipartite state. Here, we will argue
that such a unitary can be used to estimate the quantity
$\left\|\operatorname{Re}(P\rho Q)\right\|_{2}^{2}$ for some state of interest
$\rho$ and that the circuit used to do so can be constructed using our
antisymmetry test perspective.

Suppose we have a completeness relation $\mathbb{I}=P+Q$; then, by simple
substitution, we can see that $P=\frac{1}{2}(\mathbb{I}+U)$. We can then
realize this projector by performing a controlled unitary. We use this fact to
construct the circuit given in Figure 8, which we claim can estimate the
quantity of interest, $\left\|\operatorname{Re}(P\rho Q)\right\|_{2}^{2}$.

Figure 8: Construction to estimate $\left\|\operatorname{Re}(P\rho
Q)\right\|_{2}^{2}$, where $U=P-Q$.

This circuit uses an antisymmetry test as a subroutine. Consider the set
$\\{V(h)\\}_{h\in H}=\\{\mathbb{I}\otimes\mathbb{I},\mathbb{I}\otimes
U,U\otimes\mathbb{I},U\otimes U\\}$ where $H=\\{00,01,10,11\\}$ corresponds to
the necessary control-register states. Although we have not made the
assumptions necessary to ensure that $\\{V(h)\\}_{h\in H}$ is a group
representation, we can construct the circuit using the same principles
regardless. For the construction, we assume that the state of interest
$\rho_{S}$ is provided in the form of a purification
$|\psi\rangle\\!\langle\psi|_{SR}$, i.e., so that
$\rho_{S}=\operatorname{Tr}_{R}[|\psi\rangle\\!\langle\psi|_{SR}]$.

The initial state of the system is given by

$\displaystyle|+,+,+\rangle_{C_{1}C_{2}C_{3}}|\psi\rangle_{S_{1}R_{1}}|\psi\rangle_{S_{2}R_{2}}\,,$
(73)

with $|+\rangle=\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$. However, we would
like to frame this algorithm as an antisymmetry test, and so we instead write
the initial state as

$\displaystyle|+\rangle_{C_{3}}|+_{H}\rangle|\Psi\rangle\,,$ (74)

where
$|\Psi\rangle\coloneqq|\psi\rangle_{S_{1}R_{1}}\otimes|\psi\rangle_{S_{2}R_{2}}$
and

$|+_{H}\rangle=\frac{1}{\sqrt{|H|}}\sum_{h\in H}|h\rangle\,.$ (75)

The action of the antisymmetric subroutine is thus as follows:

$\displaystyle|+\rangle_{C_{3}}|+_{H}\rangle|\Psi\rangle$
$\displaystyle\to\frac{|+\rangle_{C_{3}}}{2}\sum_{h\in
H}\operatorname{sgn}(h)|h\rangle V(h)|\Psi\rangle\,,$ (76)

noting that $|H|=4$ by construction. Substituting the definitions above into
(76) gives us

$=\frac{|+\rangle_{C_{3}}}{2}\Big{(}|00\rangle(|\psi\rangle_{S_{1}R_{1}}\otimes|\psi\rangle_{S_{2}R_{2}})\\\
-|01\rangle(|\psi\rangle_{S_{1}R_{1}}\otimes U|\psi\rangle_{S_{2}R_{2}})\\\
-|10\rangle(U|\psi\rangle_{S_{1}R_{1}}\otimes|\psi\rangle_{S_{2}R_{2}})\\\
+|11\rangle(U|\psi\rangle_{S_{1}R_{1}}\otimes
U|\psi\rangle_{S_{2}R_{2}})\Big{)}\,.$ (77)

Next, we act on qubits $C_{1}$ and $C_{2}$ with Hadamard gates, seen in Figure
8, leading to the state:

$\frac{|+\rangle_{C_{3}}}{4}\Bigg{(}\Big{(}|0\rangle_{C_{1}}(\mathbb{I}-U)|\psi\rangle_{S_{1}R_{1}}+|1\rangle_{C_{1}}(\mathbb{I}+U)|\psi\rangle_{S_{1}R_{1}})\Big{)}\\\
\otimes\Big{(}|0\rangle_{C_{2}}(\mathbb{I}-U)|\psi\rangle_{S_{2}R_{2}}+|1\rangle_{C_{2}}(\mathbb{I}+U)|\psi\rangle_{S_{2}R_{2}}\Big{)}\Bigg{)}\,.$
(78)

Recall that $P=\frac{1}{2}\left(\mathbb{I}+U\right)$ and thus by the
completeness relation, $Q=\frac{1}{2}\left(\mathbb{I}-U\right)$. This allows
us to rewrite (78) as

$|+\rangle_{C_{3}}\otimes\left(|0\rangle_{C_{1}}Q|\psi\rangle+|1\rangle_{C_{1}}P|\psi\rangle\right)\\\
\otimes\left(|0\rangle_{C_{2}}Q|\psi\rangle+|1\rangle_{C_{2}}P|\psi\rangle\right).$
(79)

Now we move on to the second half of the circuit, which realizes a SWAP test
between the systems $S_{1}$ and $S_{2}$ using $C_{3}$ as the control. The
effect of these controlled-SWAPs on the state of (79) is given by

$\displaystyle\frac{1}{\sqrt{2}}\Big{[}|000\rangle[Q|\psi\rangle\otimes
Q|\psi\rangle]+|001\rangle[Q|\psi\rangle\otimes P|\psi\rangle]$
$\displaystyle\quad+|010\rangle[P|\psi\rangle\otimes
Q|\psi\rangle]+|011\rangle[P|\psi\rangle\otimes P|\psi\rangle]$
$\displaystyle\quad+|100\rangle F[Q|\psi\rangle\otimes
Q|\psi\rangle]+|101\rangle F[Q|\psi\rangle\otimes P|\psi\rangle]$
$\displaystyle\quad+|110\rangle F[P|\psi\rangle\otimes
Q|\psi\rangle]+|111\rangle F[P|\psi\rangle\otimes P|\psi\rangle]\,,$ (80)

with $F\coloneqq F_{S_{1}S_{2}}$ the unitary swap operator. Next, we apply the
final controlled-SWAP gate from $C_{3}$ to $C_{1}$ and $C_{2}$ and the
Hadamard gate on $C_{3}$. The state just before the final measurements is then

$\displaystyle|\Phi\rangle$
$\displaystyle\coloneqq\frac{1}{2}\Big{[}|000\rangle[Q|\psi\rangle\otimes
Q|\psi\rangle+F[Q|\psi\rangle\otimes Q|\psi\rangle]]$
$\displaystyle\qquad+|001\rangle[Q|\psi\rangle\otimes
P|\psi\rangle+F[P|\psi\rangle\otimes Q|\psi\rangle]]$
$\displaystyle\qquad+|010\rangle[P|\psi\rangle\otimes
Q|\psi\rangle+F[Q|\psi\rangle\otimes P|\psi\rangle]]$
$\displaystyle\qquad+|011\rangle[P|\psi\rangle\otimes
P|\psi\rangle+F[P|\psi\rangle\otimes P|\psi\rangle]]$
$\displaystyle\qquad+|100\rangle[Q|\psi\rangle\otimes
Q|\psi\rangle-F[Q|\psi\rangle\otimes Q|\psi\rangle]]$
$\displaystyle\qquad+|101\rangle[Q|\psi\rangle\otimes
P|\psi\rangle-F[P|\psi\rangle\otimes Q|\psi\rangle]]$
$\displaystyle\qquad+|110\rangle[P|\psi\rangle\otimes
Q|\psi\rangle-F[Q|\psi\rangle\otimes P|\psi\rangle]]$
$\displaystyle\qquad+|111\rangle[P|\psi\rangle\otimes
P|\psi\rangle-F[P|\psi\rangle\otimes P|\psi\rangle]]\Big{]}.$ (81)

This state can be written more compactly as

$|\Phi\rangle=\frac{1}{2}\sum_{a,b,c\in\\{0,1\\}}|abc\rangle\left[P_{b}|\psi\rangle\otimes
P_{c}|\psi\rangle\right.\\\ \left.+(-1)^{a}F[P_{c}|\psi\rangle\otimes
P_{b}|\psi\rangle]\right],$ (82)

where we define $P_{0}\coloneqq Q$ and $P_{1}\coloneqq P$. Measuring the first
three qubits $C_{3}C_{2}C_{1}$, the probability $p(abc)$ of measuring the
bitstring $abc$ is given by

$\displaystyle p(abc)$ $\displaystyle=\left\|(\langle
abc|_{C_{3}C_{2}C_{1}}\otimes\mathbb{I}_{S_{1}R_{1}S_{2}R_{2}})|\Phi\rangle\right\|^{2}_{2}$
(83)
$\displaystyle=\frac{1}{2}[\operatorname{Tr}[P_{b}\rho]\operatorname{Tr}[P_{c}\rho]+(-1)^{a}\operatorname{Tr}[P_{b}\rho
P_{c}\rho]].$ (84)

Thus, we can take the difference between some of the probabilities to find
that

$\displaystyle p(000)-p(100)$ $\displaystyle=\operatorname{Tr}[Q\rho Q\rho],$
(85) $\displaystyle p(001)-p(101)$ $\displaystyle=\operatorname{Tr}[Q\rho
P\rho],$ (86) $\displaystyle p(010)-p(110)$
$\displaystyle=\operatorname{Tr}[P\rho Q\rho]=\operatorname{Tr}[Q\rho P\rho],$
(87) $\displaystyle p(011)-p(111)$ $\displaystyle=\operatorname{Tr}[P\rho
P\rho].$ (88)

Next, we show that this is simply related to the quantity of interest:
$\left\|\operatorname{Re}(P\rho Q)\right\|_{2}^{2}$. Consider that

$\left\|\operatorname{Re}(X)\right\|^{2}_{2}=\frac{1}{4}\operatorname{Tr}[X^{2}+XX^{\dagger}+X^{\dagger}X+(X^{\dagger})^{2}].$
(89)

Substituting for $X$ with $P\rho Q$, we find that

$\displaystyle\left\|\operatorname{Re}(P\rho Q)\right\|_{2}^{2}$
$\displaystyle=\frac{1}{4}\Big{[}\operatorname{Tr}[QP\rho
QP\rho]+\operatorname{Tr}[PQ\rho PQ\rho]+2\operatorname{Tr}[P\rho
Q\rho]\Big{]}$ $\displaystyle=\frac{1}{2}\operatorname{Tr}[P\rho Q\rho],$ (90)

where the second equality results from the fact that $PQ=QP=0$. Combining both
results, we see that

$\displaystyle\left\|\operatorname{Re}(P\rho Q)\right\|_{2}^{2}$
$\displaystyle=\frac{1}{2}(p(001)-p(101))$ (91)
$\displaystyle=\frac{1}{2}(p(010)-p(110)).$ (92)

Thus, by repeating the circuit multiple times and building measurement
statistics, we can estimate $\left\|\operatorname{Re}(P\rho
Q)\right\|_{2}^{2}$. Additionally, by collecting both the measurement results
from (86) and (87), we can converge to the desired quantity of
$\left\|\operatorname{Re}(P\rho Q)\right\|_{2}^{2}$ faster than if we were
sampling only a single measurement outcome. In more detail, for all
$t\in\\{1,\ldots,T\\}$, let $Y_{t}$ be a random variable that is set to $0$
after obtaining the results 000, 100, 011, or 111, $+1$ after obtaining the
results 001 or 010, and $-1$ after obtaining the results 101 or 110. Then, it
follows from (85)–(88) and (90) that

$\mu\equiv\mathbb{E}[Y_{t}]=2\operatorname{Tr}[P\rho
Q\rho]=4\left\|\operatorname{Re}(P\rho Q)\right\|_{2}^{2},$ (93)

so that $\overline{Y_{T}}\coloneqq\frac{1}{T}\sum_{t=1}^{T}Y_{t}$ is an
unbiased estimator of $4\left\|\operatorname{Re}(P\rho Q)\right\|_{2}^{2}$.
Set $\varepsilon>0$ and $\delta\in(0,1)$. The Hoeffding bound (see, e.g., [15,
Lemma 1]) implies that, if
$T\geq\frac{2}{\varepsilon^{2}}\ln\\!\left(\frac{2}{\delta}\right)$, then
$\Pr[|\overline{Y_{T}}-\mu|\leq\varepsilon]\geq 1-\delta$.

####  III.4.4 Resolution of Identity

Consider the $r$-term resolution of identity, given by

$\mathbb{I}=P_{0}+\cdots+P_{r-1},$ (94)

where each $P_{i}$ is a projector. In this example, we provide an algorithm,
and an antisymmetry perspective, to estimate terms of the form

$\left\|\operatorname{Re}(P_{i}\rho P_{j})\right\|^{2}_{2}.$ (95)

For $i\neq j$, this quantity measures the component of the state $\rho$ in the
off-block-diagonal subspaces. For example, using projectors onto subspaces of
fixed Hamming weight, it was shown that quantitites of this form can be used
to test if a state is invariant under collective phase rotations [12]. More
generally, estimating terms of this form can measure coherences, or lack
thereof, which is relevant in a range of settings, particularly in
thermodynamics [31, 32] and coherence distillation [33, 34].

Using a similar argument as in the previous section, it follows that, when
$i\neq j$,

$\left\|\operatorname{Re}(P_{i}\rho
P_{j})\right\|^{2}_{2}=\frac{1}{2}\operatorname{Tr}[P_{i}\rho P_{j}\rho].$
(96)

Define the following unitary $U$:

$U\coloneqq\sum_{j=0}^{r-1}\exp{\left(\frac{2\pi\mathrm{i}j}{r}\right)}P_{j}.$
(97)

We also define the following operation $\tilde{Z}$ as follows:

$\tilde{Z}\coloneqq\sum_{c=0}^{r-1}\exp{\left(\frac{2\pi\mathrm{i}c}{r}\right)}|c\rangle\\!\langle
c|.$ (98)

Figure 9: Construction to estimate $\left\|\operatorname{Re}(P_{i}\rho
P_{j})\right\|_{2}^{2}$, where $U$ is defined in (97) and the unitary
$\tilde{Z}$ is defined in (98).

The circuit uses an antisymmetry test as a subroutine. Consider the set

$\\{V(h)\\}_{h\in H}=\\{U^{a}\otimes U^{b}\ |\ a,b\in\\{0,\ldots,r-1\\}\\},$
(99)

where $H=\\{a,b\ |\ a,b\in\\{0,\ldots,r-1\\}\\}$, corresponding to the
necessary control register states. Although we have not made the assumptions
necessary to ensure $\\{V(h)\\}_{h\in H}$ is a group representation, we can
construct the circuit using the same principles regardless. For the
construction, we assume that the state of interest $\rho_{S}$ is provided in
the form of a purification $|\psi\rangle\\!\langle\psi|_{SR}$, i.e., such that
$\rho_{S}=\operatorname{Tr}_{R}[|\psi\rangle\\!\langle\psi|_{SR}]$.

For the circuit, we append three ancilla registers — $C_{3}$, which is a
qubit, and $C_{2}$ and $C_{1}$, which are $r$-level systems. As seen in Figure
9, we measure Pauli-$Z$ on the first qubit and assign the value of $+1$ if the
outcome zero occurs, and $-1$ if the outcome one occurs, and we measure the
other two $r$-level systems in the computational basis. The different expected
values are given by

$p(0ab)-p(1ab)=\operatorname{Tr}[P_{a-1}\rho P_{b-1}\rho],$ (100)

where the subtraction in $a-1$ and $b-1$ is modulo $r$. We provide the state
simulation and the proof of this result in Appendix A. Thus, when $a\neq b$,
this circuit measures the cross terms as desired. Furthermore, we see that
this is a generalization of Example III.4.3, where we set $r=2$, $P_{0}=P$ and
$P_{1}=Q$. Using (96), we can estimate all the cross terms from the statistics
of the different measurement outcomes.

##  IV Applications

###  IV.1 Estimating Schmidt Rank

The Schmidt rank of a pure state can be estimated by utilizing a projection
onto the antisymmetric subspace [21]. In this section, we will briefly review
Schmidt rank and the aforementioned result before giving example computations
of this application.

The Schmidt decomposition of a bipartite pure state is a superposition of
coordinated orthonormal states. We state the theorem more formally as follows.

######  Theorem IV.1 (Schmidt Decomposition)

Suppose that we have a bipartite pure state,

$|\psi\rangle_{RS}\in\mathcal{H}_{R}\otimes\mathcal{H}_{S},$ (101)

where $\mathcal{H}_{R}$ and $\mathcal{H}_{S}$ are finite-dimensional Hilbert
spaces, not necessarily of the same dimension, and
$\left\||\psi\rangle_{RS}\right\|_{2}=1$. Then it is possible to express this
state as follows:

$|\psi\rangle_{RS}=\sum_{i=0}^{r-1}\lambda_{i}|v_{i}\rangle_{R}|w_{i}\rangle_{S},$
(102)

where the amplitudes $\lambda_{i}$ are real, strictly positive, and normalized
so that $\sum_{i}\lambda_{i}^{2}=1$, the states
$\\{|v_{i}\rangle_{R}\\}_{i=0}^{r-1}$ form an orthonormal basis in system $R$,
and the states $\\{|w_{i}\rangle_{S}\\}_{i=0}^{r-1}$ form an orthonormal basis
in system $S$. The Schmidt rank $r$ of a bipartite state is equal to the
number of Schmidt coefficients in its Schmidt decomposition; i.e.,
$r=|\\{\lambda_{i}\\}_{i=0}^{r-1}|$.

The Schmidt decomposition theorem applies to any bipartite cut of a pure
quantum state, and the Schmidt rank $r$ obeys the following inequality

$r\leq\min\\{\operatorname{dim}(\mathcal{H}_{R}),\operatorname{dim}(\mathcal{H}_{S})\\}.$
(103)

It is well known that the Schmidt rank can be used to decide if a state is
entangled. The Schmidt rank $r>1$ if and only if the state is entangled.
Another application of estimating the Schmidt rank, in the context of quantum
machine learning, can found in [35].

The result from [21] is as follows:

######  Theorem IV.2 ([21])

Suppose $|\psi\rangle_{RS}\in\mathcal{H}_{R}\otimes\mathcal{H}_{S}$ is a
bipartite state vector. Then $\operatorname{SR}(|\psi\rangle)\leq r$ if and
only if

$\left(\Pi^{\mathcal{A}}_{R,r+1}\otimes\Pi^{\mathcal{A}}_{S,r+1}\right)(|\psi\rangle_{RS}^{\otimes
r+1})=0,$ (104)

where $\Pi^{\mathcal{A}}_{R,r+1}$ is the projection onto the antisymmetric
subspace of $\mathcal{H}^{\otimes(r+1)}_{R}$ (and similarly for the $S$
system).

Using the antisymmetry test from Section II.2, we can construct a test for
estimating the Schmidt rank by performing two antisymmetry tests in tandem.
This process is shown in the schematic in Figure 10, and we give a concrete
construction for $r=2$ in Figure 11. For these algorithms, a non-zero
probability of measuring the all-zeros ($|\vec{0}\rangle_{C}$) outcome
indicates that the Schmidt rank of the state is strictly greater than $r$,
i.e., $\operatorname{SR}(|\psi\rangle)>r$. Note that in both figures, the
registers $R$ and $S$ can be multi-qubit registers. In that case, each qubit
of the multi-qubit registers is individually swapped. The count of the number
of qubits, two-qubit gates, and CSWAPs to compare the Schmidt rank of a
bipartite $n$-qubit state, and a constant $r$ is given in Table 2.

Figure 10: Construction to test if the Schmidt rank of the input state is less than or equal to $r$. The circuit realizes two antisymmetric projections on the $R$ and $S$ subsystems independently. The unitary $P$ creates the appropriate superposition for the given $r$, and $U(g)$ is one of the corresponding group elements. Figure 11: Concrete example of Schmidt rank test for $r=2$.  Property |  Count
---|---
Qubits |  $(r+1)(n+r)$
Two-qubit gates |  $4r(r-1)$
CSWAPs |  $nr(r+1)$
Table 2: Number of elements for the Schmidt rank estimation algorithm. Here
$n$ denotes the total number of qubits of the state being tested, and $r$
denotes the Schmidt rank test value.

We demonstrate this algorithm in Figures 12, 13, and 14 for a Bell state, W
state, and double Bell state respectively. For each of these states, we plot
the probability of obtaining the all-zeros outcome as a function of the
Schmidt cutoff rank $r$. These states are all known to be entangled, and that
is reflected in the results given. Each of the plots have the probability
$p(0)\neq 0$ for $r=1$, implying that their Schmidt rank $r>1$, the signature
of an entangled state.

Figure 12:  Measurement statistics for the Bell state $|\Phi^{+}\rangle_{RS}$.
We see that the probability of obtaining outcome $0$ is non-zero for $r=1$ and
is zero for $r=2$. This implies that the Schmidt rank of the state across the
$R:S$ bipartition is two. Figure 13: Measurement statistics for the W state
$|W\rangle_{RS}$, where $|R|=2$. We see that the probability of obtaining
outcome $0$ is non-zero for $r=1$, and is zero for $r=2$. This implies that
the Schmidt rank of the state across the $R:S$ bipartition is two. Figure 14:
Measurement statistics for the double Bell state
$|\Phi^{+}\rangle_{RS_{1}}\otimes|\Phi^{+}\rangle_{S_{2}S_{3}}$, where
$|R|=1$. The bipartition here is between the first qubit and the last three.
Since the second Bell state lies completely in the $S$ partition, it should
have no effect on the algorithm, and the data indicates this fact. We see that
the probability of obtaining outcome $0$ is non-zero for $r=1$ and is zero for
$r=2$. This implies that the Schmidt rank of the state across the $R:S$
bipartition is two.

###  IV.2 Alternate Test for Werner States

A Werner state [36] exhibits a particular kind of symmetry called Werner
invariance. Consider a state $\rho$ on $N$ qudits, and then define
$\overline{\rho}$ by

$\overline{\rho}=\int(U)^{\otimes N}\rho(U^{\dagger})^{\otimes N}dU\,.$ (105)

If a state $\rho$ exhibits symmetry under a collective unitary action, then
$\rho=\overline{\rho}$ is called a Werner state. For instance, this is the
case for a two-party state that satisfies the following:

$\overline{\rho}=\int(U\otimes U)\rho_{AB}(U\otimes U)^{{\dagger}}dU\,.$ (106)

As a special case of Schur–Weyl duality, we know that
$\rho_{AB}=\overline{\rho}$ in (106) if and only if

$\rho_{AB}=p\frac{\Pi_{S}}{d(d+1)/2}+(1-p)\frac{\Pi_{\mathcal{A}}}{d(d-1)/2}\,,$
(107)

where $p\in[0,1]$, $\Pi_{S}$ is the projection onto the symmetric subspace,
and $\Pi_{\mathcal{A}}$ is the projection onto the antisymmetric subspace.
Specifically, we define $\Pi_{S}$ and $\Pi_{\mathcal{A}}$ to be

$\displaystyle\Pi_{S}$
$\displaystyle\coloneqq\frac{\mathbb{I}_{AB}+F_{AB}}{2}\,,$ (108)
$\displaystyle\Pi_{\mathcal{A}}$
$\displaystyle\coloneqq\frac{\mathbb{I}_{AB}-F_{AB}}{2}\,,$ (109)

where $F_{AB}$ is the unitary swap operator for systems $A$ and $B$.

Since $\Pi_{S}+\Pi_{\mathcal{A}}=\mathbb{I}_{AB}$, it follows that a general
state can be decomposed as

$\displaystyle\sigma_{AB}$
$\displaystyle=(\Pi_{S}+\Pi_{\mathcal{A}})\sigma_{AB}(\Pi_{S}+\Pi_{\mathcal{A}})$
(110)
$\displaystyle=\Pi_{S}\sigma_{AB}\Pi_{S}+\Pi_{\mathcal{A}}\sigma_{AB}\Pi_{\mathcal{A}}$
$\displaystyle\qquad+\Pi_{\mathcal{A}}\sigma_{AB}\Pi_{S}+\Pi_{S}\sigma_{AB}\Pi_{\mathcal{A}}\,.$
(111)

By comparison with (107), we see that a state $\sigma_{AB}$ is a Werner state
if and only if both of the cross terms $\Pi_{\mathcal{A}}\sigma_{AB}\Pi_{S}$
and $\Pi_{S}\sigma_{AB}\Pi_{\mathcal{A}}$ are zero. Thus, it suffices to
develop a quantum algorithm for estimating the norm of these matrix elements
in order to perform Werner-state symmetry tests.

We can perform such a test by using the general approach developed in Example
III.4.3. First, notice that
$\operatorname{SWAP}=(\Pi_{\mathcal{S}}-\Pi_{\mathcal{A}})$. Then let
$U=\operatorname{SWAP}$. By measuring the control state as described therein,
we obtain an estimate of
$\left\|\operatorname{Re}(\Pi_{\mathcal{S}}\rho\Pi_{\mathcal{A}})\right\|_{2}^{2}$.
This is depicted in Figure 15.

A simple example of a Werner state is the singlet state

$|\psi^{-}\rangle=\frac{1}{\sqrt{2}}\left(|01\rangle-|10\rangle\right)\,.$
(112)

Indeed, every pure Werner state is equal to a linear combination of singlets
[37, Theorem 1]. For example, consider the “pizza” state for six qubits given
in [38, Figure 1]:

$|P\rangle\coloneqq\frac{1}{\sqrt{8}}\Big{(}|000111\rangle-|111000\rangle-|001110\rangle\\\
+|110001\rangle-|010101\rangle+|101010\rangle\\\
+|011100\rangle-|100011\rangle\Big{)}\,.$ (113)

Another example of a two-qubit Werner state is achieved via a convex
combination of the maximally-mixed state and a Bell state,

$W(p)=\frac{p}{6}\begin{pmatrix}\frac{p}{3}&0&0&0\\\
0&\frac{3-2p}{6}&\frac{-3+4p}{6}&0\\\ 0&\frac{-3+4p}{6}&\frac{3-2p}{6}&0\\\
0&0&0&\frac{p}{3}\\\ \end{pmatrix}\,.$ (114)

We include computational results from applying our algorithm to the states in
(112), (113), and (114) in Table 3. For comparison, we also include the
results of using a random two-qubit state and the states $|00\rangle$ and
$|11\rangle$, none of which demonstrate Werner invariance.

State $\rho_{AB}$ | True Value | Noiseless | Shot Noise | Noisy | Quantum Device
---|---|---|---|---|---
$|\psi^{-}\rangle$ | $0.0$ | $0.0$ | $0.0$ | $-0.0003$ | $-0.007$
$|P\rangle$ | $0.0$ | $0.0$ | $0.0$ | $-0.001$ | $0.0008$
$W(0.3)$ | $0.0$ | $0.0$ | $-0.002$ | $-5.6\times 10^{-5}$ | $-2.1\times 10^{-5}$
Random $2$-qubit | $0.195$ | $0.195$ | $0.196$ | $0.071$ | $0.004$
$|00\rangle$ | $0.0$ | $0.0$ | $0.0$ | $0.001$ | $-0.0002$
$|11\rangle$ | $0.0$ | $0.0$ | $0.0$ | $0.0002$ | $0.01$
Table 3: Results of test for Werner States, which estimates
$\left\|\operatorname{Re}(\Pi_{\mathcal{S}}\rho\Pi_{\mathcal{A}})\right\|^{2}_{2}$
for different states of interest. We provide the true value (calculated by
classical means), noiseless, shot noise with $10^{5}$ shots, noisy
simulations, and quantum device ibm_osaka. Figure 15: Quantum circuit to test
whether is a quantum state is a Werner state.

###  IV.3 Estimating Commutators

Commutators play an important role in quantum mechanics, especially in
quantifying uncertainty when measuring two observables. We present here two
different methods for estimating a commutator and a nested commutator. We show
how the antisymmetric circuit structure can be easily adapted to realize a
quantum switch between operators, as described in [39, 40, 41].

We begin by considering the commutator between two unitaries $A$ and $B$,
which for now we suppose have the same dimensions. Figure 16 depicts a quantum
circuit to obtain this quantity. First, consider an input state
$|0\rangle_{C}|\psi\rangle$. After acting on the control qubit with a Hadamard
and then a Pauli-$Z$ gate, the state of the system is

$|-\rangle_{C}|\psi\rangle=\frac{1}{\sqrt{2}}(|0\rangle_{C}|\psi\rangle-|1\rangle_{C}|\psi\rangle)\,.$
(115)

Next, conditioned on the control qubit, act on the system with the operators
$AB$ if in the state $|0\rangle_{C}$ or with operators $BA$ is the control is
in the state $|1\rangle$. Performing this sequence of controls leads to the
overall state

$\frac{1}{\sqrt{2}}(|0\rangle_{C}AB|\psi\rangle-|1\rangle_{C}BA|\psi\rangle)\,.$
(116)

After a second Hadamard on the control register, this becomes

$\displaystyle\frac{1}{2}(|0\rangle_{C}AB|\psi\rangle+|1\rangle_{C}AB|\psi\rangle-|0\rangle_{C}BA|\psi\rangle)+|1\rangle_{C}BA|\psi\rangle)$
$\displaystyle=\frac{1}{2}[|0\rangle_{C}\otimes(AB-
BA)|\psi\rangle+|1\rangle_{C}\otimes(AB+BA)|\psi\rangle)]$ (117)
$\displaystyle=\frac{1}{2}[|0\rangle_{C}[A,B]|\psi\rangle+|1\rangle_{C}\\{A,B\\}|\psi\rangle]\,,$
(118)

where $\\{A,B\\}$ denotes the anticommutator of $A$ and $B$. Given this final
state, we measure the control qubit to be in the state $|0\rangle_{C}$ with
probability

$P(|0\rangle\\!\langle
0|_{C})=\frac{1}{4}\left\|[A,B]|\psi\rangle\right\|_{2}^{2}\,.$ (119)

In this manner, we have effectively reproduced Equations (5)–(8) of [41].

Figure 16: Figure demonstrating how to measure the commutator of two unitary
operators $A$ and $B$. The probability to measure $|0\rangle$ on the control
state is $\frac{1}{4}\left\|[A,B]|\psi\rangle\right\|_{2}^{2}$

However, in principle there could be higher order, or nested, commutators to
consider. We can determine the sum of the nested commutators between two
operators $A$ and $B$ via the Baker–Campbell–Hausdorff (BCH) formula. For some
elements $X$ and $Y$ in the Lie algebra of a Lie group, BCH (specifically, an
1897 lemma of the famous theorem) tells us that

$e^{X}Ye^{-X}=e^{\operatorname{ad}_{X}}Y=Y+[X,Y]+\frac{1}{2!}[X,[X,Y]]+\cdots\,,$
(120)

where $\operatorname{ad}_{X}$ is the adjoint endomorphism defined to act as
$\operatorname{ad}_{X}Y=[X,Y]$.

Figure 17: Figure demonstrating how to measure the commutator of two operators
$A$ and $B$. This circuit uses the BCH formula to calculate the full sum of
nested commutations.

Suppose now that we have an exponentiated unitary $U=e^{iA}$. In this context,
$A$ is essentially a Hamiltonian, and the unitary $U$ can be realized via
Hamiltonian simulation methods [42]. For particular choices of the Hamiltonian
$A$, the unitary $U$ can be efficiently realized on a quantum computer. While
every unitary can be written in this form via Stone’s theorem [43], for
practical purposes, it is best to choose $A$ such that $U$ can be implemented
efficiently on a quantum computer. We can use (120) to calculate the sum of
the nested commutators. Observe that

$\displaystyle e^{iA}Be^{-iA}-B$
$\displaystyle=i[A,B]+\frac{-1}{2!}[A,[A,B]]+\cdots$ (121)
$\displaystyle=\sum_{n=1}^{\infty}(\operatorname{ad}_{iA})^{n}B.$

Realizing this quantity merely employs a rewriting of the previous algorithm
used for the commutator. Replace the operator $AB$ with $e^{iA}Be^{-iA}$ and
$BA$ with $B$, as shown in Figure 17. Then, follow the same procedure as
below; only now, the final state of the system before the measurement is

$\frac{1}{2}(|0\rangle_{C}(e^{iA}Be^{-iA}-B)|\psi\rangle+|1\rangle_{C}(e^{iA}Be^{-iA}+B)|\psi\rangle)\\\
=\frac{1}{2}\left(\sum_{n=1}^{\infty}|0\rangle_{C}(\operatorname{ad}_{iA})^{n}B|\psi\rangle+|1\rangle_{C}(e^{iA}Be^{-iA}+B)|\psi\rangle\right)\,.$
(122)

From this final state, we measure the control qubit to be in the state
$|0\rangle_{C}$ with probability

$P(|0\rangle\\!\langle
0|_{C})=\frac{1}{4}\left\|\sum_{n=1}^{\infty}(\operatorname{ad}_{iA})^{n}B|\psi\rangle\right\|_{2}^{2}\,.$
(123)

Both the probabilities in (119) and (123) above depend on the input state
$|\psi\rangle$. By choosing to replace $|\psi\rangle$ with the maximally-mixed
state, we can obtain an estimation of both the commutator and the sum of
nested commutators respectively as

$\displaystyle P=\frac{1}{4d}\left\|[A,B]\right\|_{2}^{2}\,$ (124)

and

$P=\frac{1}{4d}\left\|\sum_{n=1}^{\infty}(\operatorname{ad}_{iA})^{n}B\right\|_{2}^{2}\,,$
(125)

where $d$ is the dimension of the input state. However, by instead maximizing
all possible input states $|\psi\rangle$, we instead obtain

$P=\frac{1}{4}\left\|[A,B]\right\|_{\infty}^{2}\,$ (126)

for the single commutator estimation and

$P=\frac{1}{4}\left\|\sum_{n=1}^{\infty}(\operatorname{ad}_{iA})^{n}B\right\|_{\infty}^{2}\,,$
(127)

for the algorithm in which we consider the sum of the nested commutators of
$iA$ and $B$.

Thus, via this simple application of an asymmetric circuit we have
demonstrated methods by which the commutator of two operators can be computed.

###  IV.4 Brief Comments on Schur Sampling

A pointed observation of our procedure for concatenating projectors,
particularly projectors onto irreps of the symmetric group as in Section
III.4.2, might naturally lead to the question of how this procedure compares
to Schur sampling. Schur sampling refers to the task of measuring the Schur
basis labels of a $n$-qubit (or, in principle, qudit) system [44, 45, 46].
This task is often accomplished by first implementing the quantum Schur
transform [47, 25]. The Schur basis labels are typically given in a triple
$(\lambda,p_{\lambda},q_{\lambda})$, which denote the Young label and bases of
the irreducible representations given by Schur–Weyl duality. Determining the
values of each of these labels is called strong Schur sampling, while the task
of only determining the Young label is called weak Schur sampling [46]. For
more information on the quantum Schur transform and the related tasks of Schur
sampling, see Refs. [47, 25].

Much previous literature has been devoted to implementing the quantum Schur
transform and measuring Young labels. The seminal work of [47] realized the
quantum Schur transform in $O(\operatorname{poly}(n,d,\log(1/\varepsilon)))$
operations, with $d$ being the dimension of a qudit, $\varepsilon$ the
allowable error, and $n$ is index of the symmetric group $S_{n}$. Similarly,
more recent scholarship affirms that high-dimensional quantum Schur transforms
can be implemented in $O(\operatorname{poly}(n,\log(1/\varepsilon))$
operations, and an explicit gate count of $O(n^{4}\log(n/\varepsilon))$ was
given in [44] for the inverse Schur transform. These approaches all use $O(n)$
qubits. A technique for weak Schur sampling can estimate Young labels using
logarithmically many qubits and $O(n^{3}\log(n/\varepsilon))$ gates [46]. So
how would an approach based on our concatenated circuits fair in comparison?

The natural procedure for Schur sampling based on the concatenated projector
procedure given in Section III would be to implement a projector onto each of
the $r$ irreps of $S_{n}$ in turn and measure the projection of a state on
that system. The number of qubits necessary for this task would require at
least $n$ from the data register and an additional $n^{2}+r$ ancillary qubits,
based on the circuit construction for the symmetric group given in [12], and
$r-1$ qubits to store each projection measurement outcome. The reliance on
ancillary qubits could in principle be reduced, as the optimal implementation
based on group size would be $\log_{d}(|S_{n}|)=\log_{d}(n!)$, where $d$ is
again the dimension of a qudit. For sufficiently large $n$, the Stirling
approximation gives that this scales asymptotically as $O(n\log(n))$ with the
size of the group. As such, the number of qubits required goes at best as
$O(n\log(n)+n+r)$. For the construction used in this work, each transposition
is realized by either a controlled-SWAP gate or such a gate with an additional
Pauli-$Z$ acting on the ancilla. Each of these gates requires five to seven
elementary gates from the Clifford+$T$ gate set to be realized [46] if not
native. The symmetric test for $S_{n}$ uses $O(n^{2})$ such gates. Assuming
each irrep projector scales similarly, a procedure for testing each of these
projections in sequence for $r$ projectors would scale as $O(5rn^{2})$
elementary gates. The number of irreps of $S^{n}$ corresponds directly to the
partitions of $n$, which itself grows exponentially with respect to $\sqrt{n}$
[48, 49]. As such, alternate approaches would likely be preferable to reduce
necessary resources. Indeed, the authors of [47] predicted just such an
inefficiency, and instead achieve better results by employing Clebsch–Gordon
transforms recursively.

However, our procedure does offer a benefit in an important regard. If only
the projections onto the symmetric and antisymmetric spaces are desired, all
other projections can be grouped together into a collective result. In this
case, the algorithm described in Example III.4.2 will suffice. That procedure
would scale primarily with the size of the symmetric and antisymmetric tests,
thus requiring around $O(2n^{2})$ operations to implement.

##  V Discussion

In this paper, we have provided a variety of procedures for realizing
projectors in a quantum circuit, with a view towards combining symmetry,
asymmetry, and antisymmetry. We have introduced an algorithm to realize the
antisymmetric projector and demonstrated how an antisymmetrized circuit can be
used to test for relevant physical phenomenon such as Schmidt rank, Werner
invariance, or to realize a quantum switch. For the Schmidt-rank and Werner-
state tests, we have given experimental results for various examples with
small-dimensional systems, using currently available quantum hardware.

Some open questions remain. First and foremost, it remains to be seen whether
this general procedure for concatenating projectors can be used to realize a
Schur transform or a Schur sampling algorithm in the manner of [47, 25, 46].
The naïve approach presented here would scale poorly with the size of the
symmetric group. Previous literature utilized a recursive structure to
simplify the implementation of this task to scale reasonably on a quantum
computer. A natural next step would be to combine the recursive structure used
in [47] with the concatenation procedure given here to see if a less resource-
intensive algorithm would result.

Another open question is whether these algorithms can be utilized to
efficiently prepare the antisymmetric state. The natural approach of utilizing
the maximally-mixed state as input to an antisymmetry test and then post-
selecting for successful states would result in an exponentially low
acceptance probability with respect to the number of qubits in said state. If
such an algorithm cannot be devised to run efficiently, the natural
alternative question is whether there exists an efficiently preparable state
such that the acceptance probability is appreciably large.

Both of these questions rely on reasonable scaling of resources in terms of
gates and qubits and are each worthy of further study.

###### Acknowledgements.

MLL acknowledges support from the OUSD(R&E) SMART SEED grant and NSF Grant No.
2315398. SR and MMW acknowledge support from the School of Electrical and
Computer Engineering at Cornell University, the National Science Foundation
under Grant No. 2315398, and AFRL under agreement no. FA8750-23-2-0031. This
material is based on research sponsored by Air Force Research Laboratory under
agreement number FA8750-23- 2-0031. The U.S. Government is authorized to
reproduce and distribute reprints for Governmental purposes notwithstanding
any copyright notation thereon. The views and conclusions contained herein are
those of the authors and should not be interpreted as necessarily representing
the official policies or endorsements, either expressed or implied, of Air
Force Research Laboratory or the U.S. Government. This document is
Distribution Statement A, Approved for Public Release; distribution is
unlimited. We acknowledge use of the IBM Q for this work. The views expressed
are those of the authors and do not reflect the official policy or position of
IBM or the IBM Q team.

## References

  * Noether [1918] E. Noether, Invariante variationsprobleme, Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen, Mathematisch-Physikalische Klasse 1918, 235 (1918).
  * Fedorov [1891] E. S. Fedorov, The symmetry of regular systems of figures, Proceedings of the Imperial St. Petersburg Mineralogical Society 28, 1 (1891).
  * Marvian and Spekkens [2014a] I. Marvian and R. W. Spekkens, Extending Noether’s theorem by quantifying the asymmetry of quantum states, Nature Communications 5, 3821 (2014a).
  * Marvian and Spekkens [2013] I. Marvian and R. W. Spekkens, The theory of manipulations of pure state asymmetry: I. Basic tools, equivalence classes and single copy transformations, New Journal of Physics 15, 033001 (2013).
  * Caves  _et al._ [2002] C. M. Caves, C. A. Fuchs, and R. Schack, Unknown quantum states: the quantum de Finetti representation, Journal of Mathematical Physics 43, 4537 (2002).
  * König and Renner [2005] R. König and R. Renner, A de Finetti representation for finite symmetric quantum states, Journal of Mathematical Physics 46, 122108 (2005).
  * Christandl  _et al._ [2007] M. Christandl, R. König, G. Mitchison, and R. Renner, One-and-a-half quantum de Finetti theorems, Communications in Mathematical Physics 273, 473 (2007).
  * Werner [1989a] R. F. Werner, An application of Bell’s inequalities to a quantum state extension problem, Letters in Mathematical Physics 17, 359 (1989a).
  * Doherty  _et al._ [2002] A. C. Doherty, P. A. Parrilo, and F. M. Spedalieri, Distinguishing separable and entangled states, Physical Review Letters 88, 187904 (2002).
  * Doherty  _et al._ [2004] A. C. Doherty, P. A. Parrilo, and F. M. Spedalieri, Complete family of separability criteria, Physical Review A 69, 022308 (2004).
  * Anschuetz  _et al._ [2023] E. R. Anschuetz, A. Bauer, B. T. Kiani, and S. Lloyd, Efficient classical algorithms for simulating symmetric quantum systems, Quantum 7, 1189 (2023).
  * LaBorde  _et al._ [2023] M. L. LaBorde, S. Rethinasamy, and M. M. Wilde, Testing symmetry on quantum computers, Quantum 7, 1120 (2023).
  * LaBorde and Wilde [2022] M. L. LaBorde and M. M. Wilde, Quantum algorithms for testing Hamiltonian symmetry, Physical Review Letters 129, 160503 (2022).
  * Bandyopadhyay  _et al._ [2023] R. Bandyopadhyay, A. H. Rubin, M. Radulaski, and M. M. Wilde, Efficient quantum algorithms for testing symmetries of open quantum systems, Open Systems & Information Dynamics 30, 2350017 (2023).
  * Rethinasamy  _et al._ [2023] S. Rethinasamy, M. L. LaBorde, and M. M. Wilde, Quantum computational complexity and symmetry (2023), arXiv:2309.10081 .
  * Ragone  _et al._ [2022] M. Ragone, P. Braccia, Q. T. Nguyen, L. Schatzki, P. J. Coles, F. Sauvage, M. Larocca, and M. Cerezo, Representation theory for geometric quantum machine learning (2022), arXiv:2210.07980.
  * Larocca  _et al._ [2022] M. Larocca, F. Sauvage, F. M. Sbahi, G. Verdon, P. J. Coles, and M. Cerezo, Group-invariant quantum machine learning, PRX Quantum 3, 030341 (2022).
  * Meyer  _et al._ [2023] J. J. Meyer, M. Mularski, E. Gil-Fuster, A. A. Mele, F. Arzani, A. Wilms, and J. Eisert, Exploiting symmetry in variational quantum machine learning, PRX Quantum 4, 010328 (2023).
  * Padmanabhan  _et al._ [2020] H. Padmanabhan, J. M. Munro, I. Dabo, and V. Gopalan, Antisymmetry: Fundamentals and applications, Annual Review of Materials Research 50, 255 (2020).
  * Schilling [2015] C. Schilling, The quantum marginal problem, in  _Mathematical Results in Quantum Mechanics: Proceedings of the QMath12 Conference_ (World Scientific, 2015) pp. 165–176.
  * Johnston  _et al._ [2022] N. Johnston, B. Lovitz, and A. Vijayaraghavan, Complete hierarchy of linear systems for certifying quantum entanglement of subspaces, Physical Review A 106, 062443 (2022).
  * Marvian [2012] I. Marvian,  _Symmetry, asymmetry and quantum information_ , Ph.D. thesis, University of Waterloo (2012), http://hdl.handle.net/10012/7088.
  * Marvian and Spekkens [2014b] I. Marvian and R. W. Spekkens, Modes of asymmetry: The application of harmonic analysis to symmetric quantum dynamics and quantum reference frames, Physical Review A 90, 062110 (2014b), arXiv:1312.0680.
  * Harrow [2013] A. W. Harrow, The church of the symmetric subspace (2013), arXiv:1308.6595 .
  * Harrow [2005] A. W. Harrow,  _Applications of coherent classical communication and the Schur transform to quantum information theory_ , Ph.D. thesis, Massachusetts Institute of Technology (2005), arXiv:quant-ph/0512255.
  * Barenco  _et al._ [1997] A. Barenco, A. Berthiaume, D. Deutsch, A. Ekert, R. Jozsa, and C. Macchiavello, Stabilization of quantum computations by symmetrization, SIAM Journal on Computing 26, 1541 (1997).
  * Bradshaw  _et al._ [2023] Z. P. Bradshaw, M. L. LaBorde, and M. M. Wilde, Cycle index polynomials and generalized quantum separability tests, Proceedings of the Royal Society A 479, 20220733 (2023), arXiv:2208.14596.
  * Dummit and Foote [2004] D. S. Dummit and R. M. Foote,  _Abstract Algebra_ , 3rd ed. (Wiley, 2004).
  * Bennett [1973] C. H. Bennett, Logical reversibility of computation, IBM Journal of Research and Development 17, 525 (1973).
  * Aaronson  _et al._ [2017] S. Aaronson, D. Grier, and L. Schaeffer, The classification of reversible bit operations, in  _8th Innovations in Theoretical Computer Science Conference (ITCS 2017)_, Leibniz International Proceedings in Informatics (LIPIcs), Vol. 67, edited by C. H. Papadimitriou (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2017) pp. 23:1–23:34.
  * Yuan  _et al._ [2020] Y. Yuan, Z. Hou, J.-F. Tang, A. Streltsov, G.-Y. Xiang, C.-F. Li, and G.-C. Guo, Direct estimation of quantum coherence by collective measurements, npj Quantum Information 6, 46 (2020).
  * Rodríguez-Rosario  _et al._ [2013] C. A. Rodríguez-Rosario, T. Frauenheim, and A. Aspuru-Guzik, Thermodynamics of quantum coherence (2013), arXiv:1308.1245 [quant-ph] .
  * Liu and Zhou [2019] C. L. Liu and D. L. Zhou, Deterministic coherence distillation, Physical Review Letters 123, 070402 (2019).
  * Regula  _et al._ [2018] B. Regula, K. Fang, X. Wang, and G. Adesso, One-shot coherence distillation, Physical Review Letters 121, 010401 (2018).
  * Jing  _et al._ [2023] M. Jing, G. Liu, H. Ren, and X. Wang, Quantum sequential scattering model for quantum state learning (2023), arXiv:2310.07797.
  * Werner [1989b] R. F. Werner, Quantum states with Einstein-Podolsky-Rosen correlations admitting a hidden-variable model, Physical Review A 40, 4277 (1989b).
  * Lyons and Walck [2008] D. W. Lyons and S. N. Walck, Multiparty quantum states stabilized by the diagonal subgroup of the local unitary group, Physical Review A 78, 042314 (2008).
  * Lyons  _et al._ [2023] D. W. Lyons, C. Mullican, A. Rilatt, and J. D. Putnam, Werner states from diagrams, Journal of Physics A: Mathematical and Theoretical 56, 225301 (2023).
  * Chiribella  _et al._ [2013] G. Chiribella, G. M. D’Ariano, P. Perinotti, and B. Valiron, Quantum computations without definite causal structure, Physical Review A 88, 022318 (2013).
  * van der Lugt  _et al._ [2023] T. van der Lugt, J. Barrett, and G. Chiribella, Device-independent certification of indefinite causal order in the quantum switch, Nature Communications 14, 5811 (2023).
  * Gao  _et al._ [2023] N. Gao, D. Li, A. Mishra, J. Yan, K. Simonov, and G. Chiribella, Measuring incompatibility and clustering quantum observables with a quantum switch, Physical Review Letters 130, 170201 (2023).
  * Childs  _et al._ [2018] A. M. Childs, D. Maslov, Y. Nam, N. J. Ross, and Y. Su, Toward the first quantum simulation with quantum speedup, Proceedings of the National Academy of Sciences 115, 9456 (2018).
  * Hall [2013] B. C. Hall,  _Quantum Theory for Mathematicians_ (Springer, 2013).
  * Kirby and Strauch [2018] W. M. Kirby and F. W. Strauch, A practical quantum algorithm for the Schur transform, Quantum Information and Computation 18, 0721 (2018), arXiv:1709.07119 [quant-ph] .
  * Krovi [2019] H. Krovi, An efficient high dimensional quantum Schur transform, Quantum 3, 122 (2019).
  * Cervero-Martín and Mančinska [2023] E. Cervero-Martín and L. Mančinska, Weak Schur sampling with logarithmic quantum memory (2023), arXiv:2309.11947.
  * Bacon  _et al._ [2007] D. Bacon, I. L. Chuang, and A. W. Harrow, The quantum Schur and Clebsch–Gordan transforms: I. efficient qudit circuits, in  _Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms_ , SODA ’07 (Society for Industrial and Applied Mathematics, USA, 2007) p. 1235–1244, arXiv:quant-ph/0601001.
  * Andrews and Eriksson [2004] G. E. Andrews and K. Eriksson,  _Integer Partitions_ (Cambridge University Press, 2004).
  * Fulton and Harris [2013] W. Fulton and J. Harris,  _Representation Theory: A First Course_ , Vol. 129 (Springer Science & Business Media, 2013).

##  Appendix A Proof of Equation (100)

In this appendix, we examine Example III.4.4 and give a derivation for the
acceptance probability given in (100). Before we begin with the proof, we show
some preliminary results.

###### Lemma A.1

Consider a resolution of the identity

$\mathbb{I}=\sum_{i=0}^{r-1}P_{i},$ (128)

where $P_{i}^{\dagger}=P_{i}$, and $P_{i}^{2}=P_{i}$. Then,

$P_{i}P_{j}=\delta_{i,j}P_{i}.$ (129)

Proof. Consider the following:

$\displaystyle P_{j}$ $\displaystyle=P_{j}\mathbb{I}P_{j}$ (130)
$\displaystyle=P_{j}\left(\sum_{i=0}^{r-1}P_{i}\right)P_{j}$ (131)
$\displaystyle=\sum_{i=0}^{r-1}P_{j}P_{i}P_{j}$ (132)
$\displaystyle=P_{j}+\sum_{i,i\neq j}P_{j}P_{i}P_{j}.$ (133)

Thus,

$\sum_{i,i\neq j}P_{j}P_{i}P_{j}=0.$ (134)

Next, consider that, for every $i$ and $j$ such that $i\neq j$, and after
defining $|\phi\rangle\coloneqq P_{i}P_{j}|\psi\rangle$,

$\displaystyle\langle\psi|P_{j}P_{i}P_{j}|\psi\rangle$
$\displaystyle=\langle\psi|P_{j}P_{i}P_{i}P_{j}|\psi\rangle$ (135)
$\displaystyle=\langle\phi|\phi\rangle$ (136) $\displaystyle\geq 0,$ (137)

for every vector $|\psi\rangle$. Thus, $P_{j}P_{i}P_{j}$ is a positive semi-
definite operator, for all $i\neq j$. Using (134), a sum of positive semi-
definite operators is equal to zero if and only if each terms is zero. Thus,

$P_{j}P_{i}P_{j}=0\quad\forall i\neq j.$ (138)

Lastly, consider that, for all $i\neq j$,

$\displaystyle\left\|P_{i}P_{j}\right\|^{2}_{2}$
$\displaystyle=\operatorname{Tr}[P_{j}P_{i}P_{i}P_{j}]$ (139)
$\displaystyle=\operatorname{Tr}[P_{j}P_{i}P_{j}]$ (140) $\displaystyle=0.$
(141)

Using the fact that the two-norm of an operator is zero if and only if the
operator itself is zero, we see that $P_{i}P_{j}=0$ for $i\neq j$, completing
the proof.

Next, we show that the operator $U$, defined in (97), is indeed unitary.
Consider that

$U=\sum_{j=0}^{r-1}\exp{\left(\frac{2\pi\mathrm{i}j}{r}\right)}P_{j}.$ (142)

Thus, we see that

$\displaystyle UU^{\dagger}$
$\displaystyle=\left(\sum_{j=0}^{r-1}\exp{\left(\frac{2\pi\mathrm{i}j}{r}\right)}P_{j}\right)\left(\sum_{k=0}^{r-1}\exp{\left(\frac{-2\pi\mathrm{i}k}{r}\right)}P_{k}\right)$
$\displaystyle=\sum_{j=0}^{r-1}\sum_{k=0}^{r-1}\exp{\left(\frac{2\pi\mathrm{i}(j-k)}{r}\right)}P_{j}P_{k}$
$\displaystyle=\sum_{j=0}^{r-1}\sum_{k=0}^{r-1}\exp{\left(\frac{2\pi\mathrm{i}(j-k)}{r}\right)}\delta_{j,k}P_{j}$
$\displaystyle=\sum_{j=0}^{r=1}P_{j}$ $\displaystyle=\mathbb{I}.$ (143)

Similarly, we can show that $U^{\dagger}U=\mathbb{I}$.

The initial state of the system, in the algorithm described just before (100),
is given by

$|000\rangle_{C_{3}C_{2}C_{1}}|\psi\rangle_{S_{1}R_{1}}|\psi\rangle_{S_{2}R_{2}}.$
(144)

Next, we act on system $C_{3}$ with the Hadamard operation, and on $C_{2}$ and
$C_{1}$ each with the quantum Fourier transform (QFT). The overall state is
now

$\frac{1}{r}|+\rangle_{C_{3}}\sum_{a,b=0}^{r-1}|ab\rangle_{C_{2}C_{1}}|\psi\rangle|\psi\rangle.$
(145)

Next, we perform the two controlled operations

$\displaystyle\sum_{a=0}^{r-1}|a\rangle\\!\langle a|_{C_{1}}\otimes
U^{a}_{A_{2}B_{2}},$ (146) $\displaystyle\sum_{d=0}^{r-1}|b\rangle\\!\langle
b|_{C_{2}}\otimes U^{b}_{A_{1}B_{1}}.$ (147)

The overall state is then

$\frac{1}{r}|+\rangle\sum_{a,b=0}^{r-1}|a\rangle|b\rangle
U^{a}|\psi\rangle\otimes U^{b}|\psi\rangle.$ (148)

Next, we perform the $\tilde{Z}$ operation on each of the systems $C_{2}$ and
$C_{1}$, where the operation is defined by

$\tilde{Z}\coloneqq\sum_{c=0}^{r-1}\exp{\left(\frac{2\pi\mathrm{i}j}{r}\right)}|c\rangle\\!\langle
c|.$ (149)

The state is then given by

$\frac{1}{r}|+\rangle\sum_{a,b=0}^{r-1}\exp{\left(\frac{2\pi\mathrm{i}(a+b)}{r}\right)}|a\rangle|b\rangle
U^{a}|\psi\rangle\otimes U^{b}|\psi\rangle.$ (150)

Performing the inverse QFT (IQFT) on each of the systems $C_{1}$ and $C_{2}$
next leads to the following state:

$\displaystyle\frac{1}{r^{2}}|+\rangle\sum_{a,b=0}^{r-1}\sum_{c,d=0}^{r-1}\exp{\left(\frac{2\pi\mathrm{i}(a+b)}{r}\right)}\exp{\left(\frac{-2\pi\mathrm{i}(ac+bd)}{r}\right)}|c\rangle|d\rangle
U^{a}|\psi\rangle\otimes U^{b}|\psi\rangle$
$\displaystyle=\frac{1}{r^{2}}|+\rangle\sum_{c,d=0}^{r-1}|c\rangle|d\rangle\Bigg{[}\sum_{a,b=0}^{r-1}\exp{\left(\frac{2\pi\mathrm{i}(a+b)}{r}\right)}\exp{\left(\frac{-2\pi\mathrm{i}(ac+bd)}{r}\right)}U^{a}\otimes
U^{b}\Bigg{]}|\psi\rangle|\psi\rangle$
$\displaystyle=\frac{1}{r^{2}}|+\rangle\sum_{c,d=0}^{r-1}|c\rangle|d\rangle\Bigg{[}\sum_{a=0}^{r-1}\exp{\left(\frac{2\pi\mathrm{i}a}{r}\right)}\exp{\left(\frac{-2\pi\mathrm{i}ac}{r}\right)}U^{a}\Bigg{]}|\psi\rangle\otimes\Bigg{[}\sum_{b=0}^{r-1}\exp{\left(\frac{2\pi\mathrm{i}b}{r}\right)}\exp{\left(\frac{-2\pi\mathrm{i}bd}{r}\right)}U^{b}\Bigg{]}|\psi\rangle.$
(151)

Consider the following:

$\displaystyle\sum_{a=0}^{r-1}\exp{\left(\frac{2\pi\mathrm{i}a}{r}\right)}\exp{\left(\frac{-2\pi\mathrm{i}ac}{r}\right)}U^{a}$
$\displaystyle=\sum_{a=0}^{r-1}\sum_{j=0}^{r-1}\exp{\left(\frac{2\pi\mathrm{i}a}{r}\right)}\exp{\left(\frac{-2\pi\mathrm{i}ac}{r}\right)}\exp{\left(\frac{2\pi\mathrm{i}ja}{r}\right)}P_{j}$
$\displaystyle=\sum_{j=0}^{r-1}r\delta_{j+1,c}P_{j}$ $\displaystyle=rP_{c-1},$
(152)

where the subscript $c-1$ is taken modulo $r$. Thus, the overall state after
the IQFT is given by

$|+\rangle\sum_{c,d=0}^{r-1}|c\rangle|d\rangle P_{c-1}|\psi\rangle\otimes
P_{d-1}|\psi\rangle.$ (153)

Next, we apply the three CSWAP operations and the Hadamard operation

$\frac{1}{\sqrt{2}}\Bigg{[}|+\rangle\sum_{c,d=0}^{r-1}|c\rangle|d\rangle
P_{c-1}|\psi\rangle\otimes
P_{d-1}|\psi\rangle+|-\rangle\sum_{c,d=0}^{r-1}|c\rangle|d\rangle
F(P_{d-1}|\psi\rangle\otimes P_{c-1}|\psi\rangle)\Bigg{]}.$ (154)

Expanding, we get

$|\Phi\rangle=\frac{1}{2}\sum_{y=0}^{1}\sum_{c,d=0}^{r-1}\left[|y\rangle|cd\rangle(P_{c-1}\otimes
P_{d-1}+(-1)^{y}F(P_{d-1}\otimes P_{c-1}))\right].$ (155)

Lastly, measuring registers $C_{3}C_{2}C_{1}$, we find that

$\displaystyle p(xab)$ (156) $\displaystyle=\left\|\langle
xab|_{C_{3}C_{2}C_{1}}\otimes
I_{S_{1}R_{1}S_{2}R_{2}}|\Phi\rangle\right\|^{2}_{2}.$
$\displaystyle=\frac{1}{2}[\operatorname{Tr}[P_{a-1}\rho]\operatorname{Tr}[P_{b-1}\rho]+(-1)^{x}\operatorname{Tr}[P_{a-1}\rho
P_{b-1}\rho]].$

Thus, it follows that

$p(0ab)-p(1ab)=\operatorname{Tr}[P_{a-1}\rho P_{b-1}\rho].$ (157)

Observe that

$\displaystyle p(0ba)-p(1ba)$ $\displaystyle=\operatorname{Tr}[P_{b-1}\rho
P_{a-1}\rho]$ (158) $\displaystyle=\operatorname{Tr}[P_{a-1}\rho
P_{b-1}\rho],$

As such, to estimate this quantity, we can perform a sampling procedure
similar to what is described around (93). For all $t\in\\{1,\ldots,T\\}$, let
$Y_{t}$ be a random variable that is set to $+1$ after obtaining the results
$0ab$ or $0ba$, $-1$ after obtaining the results $1ab$ or $1ba$, and 0
otherwise. Then, it follows from (157)–(158) and (96) that

$\displaystyle\mu$ $\displaystyle\equiv\mathbb{E}[Y_{t}]$ (159)
$\displaystyle=2\operatorname{Tr}[P_{a-1}\rho P_{b-1}\rho]$ (160)
$\displaystyle=4\left\|\operatorname{Re}(P_{a-1}\rho
P_{b-1})\right\|_{2}^{2},$ (161)

so that $\overline{Y_{T}}\coloneqq\frac{1}{T}\sum_{t=1}^{T}Y_{t}$ is an
unbiased estimator of $4\left\|\operatorname{Re}(P_{a-1}\rho
P_{b-1})\right\|_{2}^{2}$. Set $\varepsilon>0$ and $\delta\in(0,1)$. The
Hoeffding bound (see, e.g., [15, Lemma 1]) implies that, if
$T\geq\frac{2}{\varepsilon^{2}}\ln\\!\left(\frac{2}{\delta}\right)$, then
$\Pr[|\overline{Y_{T}}-\mu|\leq\varepsilon]\geq 1-\delta$.