# Testing symmetry on quantum computers

Margarite L. LaBorde  Hearne Institute for Theoretical Physics, Department of
Physics and Astronomy, and Center for Computation and Technology, Louisiana
State University, Baton Rouge, Louisiana 70803, USA  Soorya Rethinasamy
School of Applied and Engineering Physics, Cornell University, Ithaca, New
York 14850, USA  Hearne Institute for Theoretical Physics, Department of
Physics and Astronomy, and Center for Computation and Technology, Louisiana
State University, Baton Rouge, Louisiana 70803, USA  Mark M. Wilde  School of
Electrical and Computer Engineering, Cornell University, Ithaca, New York
14850, USA  Hearne Institute for Theoretical Physics, Department of Physics
and Astronomy, and Center for Computation and Technology, Louisiana State
University, Baton Rouge, Louisiana 70803, USA

###### Abstract

Symmetry is a unifying concept in physics. In quantum information and beyond,
it is known that quantum states possessing symmetry are not useful for certain
information-processing tasks. For example, states that commute with a
Hamiltonian realizing a time evolution are not useful for timekeeping during
that evolution, and bipartite states that are highly extendible are not
strongly entangled and thus not useful for basic tasks like teleportation.
Motivated by this perspective, this paper details several quantum algorithms
that test the symmetry of quantum states and channels. For the case of testing
Bose symmetry of a state, we show that there is a simple and efficient quantum
algorithm, while the tests for other kinds of symmetry rely on the aid of a
quantum prover. We prove that the acceptance probability of each algorithm is
equal to the maximum symmetric fidelity of the state being tested, thus giving
a firm operational meaning to these latter resource quantifiers. Special cases
of the algorithms test for incoherence or separability of quantum states. We
evaluate the performance of these algorithms on choice examples by using the
variational approach to quantum algorithms, replacing the quantum prover with
a parameterized circuit. We demonstrate this approach for numerous examples
using the IBM quantum noiseless and noisy simulators, and we observe that the
algorithms perform well in the noiseless case and exhibit noise resilience in
the noisy case. We also show that the maximum symmetric fidelities can be
calculated by semi-definite programs, which is useful for benchmarking the
performance of these algorithms for sufficiently small examples. Finally, we
establish various generalizations of the resource theory of asymmetry, with
the upshot being that the acceptance probabilities of the algorithms are
resource monotones and thus well motivated from the resource-theoretic
perspective.

LABEL:FirstPage1 LABEL:LastPage#110

###### Contents

  1. I Introduction
  2. II Notions of symmetry
  3. III Testing symmetry and extendibility on quantum computers
    1. III.1 Testing $G$-Bose symmetry
    2. III.2 Testing $G$-symmetry
    3. III.3 Testing $G$-Bose symmetric extendibility
    4. III.4 Testing $G$-symmetric extendibility
  4. IV Tests of $k$-extendibility of states and covariance symmetry of channels
    1. IV.1 Separability test for pure bipartite states
    2. IV.2 Separability test for pure multipartite states
    3. IV.3 $k$-Bose extendibility test for bipartite states
    4. IV.4 $k$-Extendibility test for bipartite states
    5. IV.5 Extendibility tests for multipartite states
    6. IV.6 Testing covariance symmetry of a quantum channel
    7. IV.7 Testing covariance symmetry of a quantum measurement
  5. V Semi-definite programs for maximum symmetric fidelities
  6. VI Variational algorithms for testing symmetry
    1. VI.1 $\mathbb{Z}_{2}$ Group
      1. VI.1.1 $G$-Bose symmetry
      2. VI.1.2 $G$-symmetry
    2. VI.2 Triangular dihedral group $D_{3}$
      1. VI.2.1 $G$-Bose symmetry
      2. VI.2.2 $G$-symmetry
      3. VI.2.3 $G$-Bose symmetric extendibility
      4. VI.2.4 $G$-symmetric extendibility
    3. VI.3 Collective $U$ group
      1. VI.3.1 $G$-Bose symmetry
      2. VI.3.2 $G$-symmetry
      3. VI.3.3 $G$-Bose symmetric extendibility
      4. VI.3.4 $G$-symmetric extendibility
    4. VI.4 Collective phase group
      1. VI.4.1 $G$-Bose symmetry
      2. VI.4.2 $G$-symmetry
      3. VI.4.3 $G$-Bose symmetric extendibility
      4. VI.4.4 $G$-symmetric extendibility
    5. VI.5 $k$-Extendibility and $k$-Bose extendibility
      1. VI.5.1 Two-Bose extendibility
      2. VI.5.2 Two-Extendibility
      3. VI.5.3 Three-Bose Extendibility
      4. VI.5.4 Three-Extendibility
  7. VII Resource theories
    1. VII.1 Resource theory of asymmetry
    2. VII.2 Resource theory of Bose asymmetry
    3. VII.3 Resource theory of asymmetric unextendibility
    4. VII.4 Resource theory of Bose asymmetric unextendibility
  8. VIII Conclusion
  9. A Proof of Theorem II.1
  10. B Acceptance probabilities of Algorithms 1–4 as maximum symmetric fidelities
    1. B.1 Proof of Theorem III.1
    2. B.2 Proof of Theorem III.2
    3. B.3 Proof of Theorem III.3
    4. B.4 Proof of Theorem III.4
  11. C Proof of Proposition VII.5
  12. D Cyclic group $C_{3}$
    1. D.1 $G$-Bose symmetry
    2. D.2 $G$-symmetry
    3. D.3 $G$-Bose symmetric extendibility
    4. D.4 $G$-symmetric extendibility
  13. E Cyclic group $C_{4}$
    1. E.1 $G$-Bose symmetry
    2. E.2 $G$-symmetry
    3. E.3 $G$-Bose symmetric extendibility
    4. E.4 $G$-symmetric extendibility
  14. F Quaternion group $Q_{8}$
    1. F.1 $G$-Bose symmetry
    2. F.2 $G$-symmetry
    3. F.3 $G$-Bose symmetric extendibility
    4. F.4 $G$-symmetric extendibility

##  I Introduction

Symmetry plays a fundamental role in physics [36, 39]. The evolution of a
closed physical system is dictated by a Hamiltonian, which often possesses
symmetry that limits transitions from one state to another in the form of
superselection rules [82, 3]. Permutation symmetry in the extension of a
bipartite quantum state indicates a lack of entanglement in that state [78,
30, 31]. This permutation symmetry limits entanglement, which relates to
fundamental principles of quantum information like no-cloning conditions [63,
28, 83] and monogamy [70]. Additionally, the lack of a shared reference frame
between two parties implies that a quantum state prepared relative to another
party’s reference frame respects a certain symmetry and is less useful than
one breaking that symmetry [15]. In all of these cases, a state respecting a
symmetry is less resourceful than one breaking it. In more recent years,
quantum resource theories have been proposed for each of the above scenarios
(asymmetry [59, 60], unextendibility [49, 50], and frameness [41]) in order to
quantify the resourcefulness of quantum states (see [21] for a review). As
such, it is useful to be able to test whether a quantum state possesses
symmetry and to quantify how much symmetry it possesses.

In this paper, we show how a quantum computer can test for symmetries of
quantum states and channels generated by quantum circuits. In fact, our
quantum-computational tests actually quantify how symmetric a state or channel
is. Given that asymmetry (i.e., breaking of symmetry) is a useful resource in
a wide variety of contexts while being potentially difficult for a classical
computer to verify, our tests are helpful in determining how useful a state
will be for certain quantum information processing tasks. Additionally, our
tests are in the spirit of the larger research program of using quantum
computers to understand fundamental quantum-mechanical properties of high-
dimensional quantum states, such as symmetry and entanglement, that are out of
reach for classical computers.

We begin our development in Section II by introducing a general form of
symmetry of quantum states that captures both the extendibility of bipartite
states [78, 30, 31], as well as symmetries of a single quantum system with
respect to a group of unitary transformations [59, 60]. This generalization
allows for incorporating several kinds of symmetry tests into a single
framework. We call this notion $G$-symmetric extendibility, and we discuss two
different forms of it.

In Section III we move on to an important contribution of our paper—namely,
how a quantum computer can test for and estimate quantifiers of symmetry.
These quantifiers are collectively called maximum symmetric fidelities, with
more particular names given in what follows. We prove that our quantum
computational tests of symmetry have acceptance probabilities precisely equal
to the various quantifiers. These results endow these resource-theoretic
measures with operational meanings and allows us to estimate them to arbitrary
precision. Using complexity-theoretic language, we demonstrate that these
quantum-computational tests of symmetry can be conducted in the form of a
quantum interactive proof (QIP) system consisting of two quantum messages
exchanged between a verifier and a prover [75, 73]. Our results thus
generalize previous results in the context of unextendibility and entanglement
of bipartite quantum states [45, 46]; additionally, we go on to clarify the
relation between our results and previous ones (Section IV). Simpler forms of
the tests can be conducted without the aid of a prover and are thus
efficiently computable on a quantum computer.

In Section IV, we show how the established concepts of $k$-extendibility or
$k$-Bose extendibility [78, 30, 31] can be recovered as special cases of our
symmetry tests for both bipartite and multipartite states. These examples are
particularly interesting as they serve as tests of separability. We also show
there how to test for the covariance symmetry of quantum channels and
measurements, where the former includes testing the symmetries of Hamiltonian
evolution as a special case [56].

Section V shows that the maximum symmetric fidelities can be calculated by
means of semi-definite programs, which is helpful for benchmarking the outputs
of the quantum algorithms for sufficiently small circuits. This follows from
combining the known semi-definite program for fidelity [76] with the semi-
definite constraints corresponding to the symmetry tests. Furthermore, we
employ representation theory [69] to simplify some of the semi-definite
programs even further, by making use of the block-diagonal form that results
from performing a group twirl on a state.

We follow this in Section VI by demonstrating the use of variational quantum
algorithms for estimating the maximum symmetric fidelities for various example
groups. (See [17, 5] for reviews of variational quantum algorithms and [40]
for a review of the variational principle). In general, this approach is not
guaranteed to estimate the maximum symmetric fidelities precisely, as the
parameterized circuit used is not able to realize an arbitrarily powerful
quantum computation. This approach thus leads only to lower bounds on the
maximum symmetric fidelities. However, we find that this heuristic approach
performs well for a variety of example groups, including symmetry tests with
respect to $\mathbb{Z}_{2}$, the triangular dihedral group, a collective
unitary action, and a collective phase action. In Appendices D–F, we go on to
provide further examples for cyclic groups and the quaternion group. We note
that a recent work adopted a similar variational approach for estimating the
fidelity of quantum states generated by quantum circuits [25]. It is well
known that this latter problem is QSZK-complete [74] and thus likely difficult
for quantum computers to solve in general. It remains an open question to
determine how well this variational approach performs generally, beyond the
examples considered in this paper. We note that the algorithms defined in this
work rely on local measurements alone and, as a consequence of the results of
[24], should not suffer from the barren plateau problem in which global cost
functions become untrainable. Since we have only conducted simulations of our
algorithms for small quantum systems, it remains open to provide evidence that
our algorithms will avoid the barren plateau problem for larger systems.

Finally, we review the resource theory of asymmetry [59, 60]. After doing so,
we define several generalized resource theories of asymmetry (Section VII),
including both the resource theory of asymmetry and the resource theory of
$k$-unextendibility [49, 50] as special cases. As part of this contribution,
we also define resource theories of Bose asymmetry, which to our knowledge
have not been considered yet. This development shows that the acceptance
probabilities of the aforementioned algorithms, i.e., maximum symmetric
fidelities, are resource monotones and thus well-motivated from the resource-
theoretic perspective.

In what follows, we proceed in the aforementioned order, and we finally
conclude in Section VIII with a brief summary and a discussion of future
questions.

##  II Notions of symmetry

We introduce the notions of $G$-symmetric extendibility and $G$-Bose symmetric
extendibility, as generalizations of the notions of $G$-symmetry [59, Section
2] and extendibility [78, 30, 31]. Later on in Section III, we devise quantum
algorithms to test for these symmetries.

Let $\rho_{S}$ be a quantum state of system $S$ with corresponding Hilbert
space $\mathcal{H}_{S}$. Let $G$ be a finite group, and let $U_{RS}(g)$ be a
unitary representation [59, Section 2] of the group element $g\in G$, where
$R$ indicates another Hilbert space such that $U_{RS}(g)$ acts on the tensor-
product Hilbert space $\mathcal{H}_{R}\otimes\mathcal{H}_{S}$. Let
$\Pi_{RS}^{G}$ denote the following projection operator:

$\Pi_{RS}^{G}\coloneqq\frac{1}{\left|G\right|}\sum_{g\in G}U_{RS}(g).$ (1)

Observe that

$\Pi_{RS}^{G}=U_{RS}(g)\Pi_{RS}^{G}=\Pi_{RS}^{G}U_{RS}(g),$ (2)

for all $g\in G$, which follows from what is called the rearrangement theorem
in group theory.

We now define $G$-symmetric extendible and $G$-Bose-symmetric extendible
states.

######  Definition II.1 ($G$-symmetric extendible)

A state $\rho_{S}$ is $G$-symmetric extendible if there exists a state
$\omega_{RS}$ such that

  1. 1.

the state $\omega_{RS}$ is an extension of $\rho_{S}$, i.e.,

$\operatorname{Tr}_{R}[\omega_{RS}]=\rho_{S},$ (3)

  2. 2.

the state $\omega_{RS}$ is $G$-invariant, in the sense that

$\omega_{RS}=U_{RS}(g)\omega_{RS}U_{RS}(g)^{{\dagger}}\qquad\forall g\in G.$
(4)

######  Definition II.2 ($G$-Bose symmetric extendible)

A state $\rho_{S}$ is $G$-Bose symmetric extendible (G-BSE) if there exists a
state $\omega_{RS}$ such that

  1. 1.

the state $\omega_{RS}$ is an extension of $\rho_{S}$, i.e.,

$\operatorname{Tr}_{R}[\omega_{RS}]=\rho_{S},$ (5)

  2. 2.

the state $\omega_{RS}$ satisfies

$\omega_{RS}=\Pi_{RS}^{G}\omega_{RS}\Pi_{RS}^{G}.$ (6)

Note that the condition in (6) is equivalent to
$\omega_{RS}=\Pi_{RS}^{G}\omega_{RS}$ or $\omega_{RS}=U_{RS}(g)\omega_{RS}$
for all $g\in G$. Also, observe that $\rho_{S}$ is $G$-symmetric extendible if
it is $G$-Bose symmetric extendible, but the opposite implication does not
necessarily hold.

We have made no assumptions about the unitary representation used thus far. It
is important to mention the case of projective unitary representations, due to
their physical relevance in the case of symmetries of density operators. See,
e.g., Eqs. (1.2) and (1.3) of [57] for a definition of a projective unitary
representation. Restricting to projective unitary representations helps in
avoiding trivial representations, and when considering symmetries of density
operators, they necessarily arise. Furthermore, when considering example
algorithms in later sections, we limit ourselves to faithful representations
of the groups involved. In principle, neither faithfulness nor a projective
representation are required unless stated otherwise. The choice of
representation does matter when considering the symmetry of a state; however,
following conventions in existing literature, we describe all symmetries with
respect to the group and omit the reliance on the representation in notation.

The notions of symmetry from Definitions II.1 and II.2 generalize both
$k$-extendibility of bipartite states and $G$-symmetry of unipartite states,
as we discuss below.

######  Example II.1 ($k$-extendible)

Recall that a bipartite state $\rho_{AB}$ is $k$-extendible [78, 30, 31] if
there exists an extension state $\omega_{AB_{1}\cdots B_{k}}$ such that

$\operatorname{Tr}_{B_{2}\cdots B_{k}}[\omega_{AB_{1}\cdots B_{k}}]=\rho_{AB}$
(7)

and

$\omega_{AB_{1}\cdots B_{k}}=W_{B_{1}\cdots B_{k}}(\pi)\omega_{AB_{1}\cdots
B_{k}}W_{B_{1}\cdots B_{k}}(\pi)^{{\dagger}},$ (8)

for all $\pi\in S_{k}$, where each system $B_{1}$, …, $B_{k}$ is isomorphic to
the system $B$ and $W_{B_{1}\cdots B_{k}}(\pi)$ is a unitary representation of
the permutation $\pi\in S_{k}$, with $S_{k}$ the symmetric group. Then the
established notion of $k$-extendibility is a special case of $G$-symmetric
extendibility, in which we set

$\displaystyle S$ $\displaystyle=AB_{1},$ (9) $\displaystyle R$
$\displaystyle=B_{2}\cdots B_{k},$ (10) $\displaystyle G$
$\displaystyle=S_{k},$ (11) $\displaystyle U_{RS}(g)$
$\displaystyle=I_{A}\otimes W_{B_{1}\cdots B_{k}}(\pi).$ (12)

######  Example II.2 ($k$-Bose-extendible)

A bipartite state $\rho_{AB}$ is $k$-Bose-extendible if there exists an
extension state $\omega_{AB_{1}\cdots B_{k}}$ such that

$\operatorname{Tr}_{B_{2}\cdots B_{k}}[\omega_{AB_{1}\cdots B_{k}}]=\rho_{AB}$
(13)

and

$\omega_{AB_{1}\cdots B_{k}}=\Pi_{B_{1}\cdots
B_{k}}^{\operatorname{Sym}}\omega_{AB_{1}\cdots B_{k}}\Pi_{B_{1}\cdots
B_{k}}^{\operatorname{Sym}},$ (14)

where

$\Pi_{B_{1}\cdots B_{k}}^{\operatorname{Sym}}\coloneqq\frac{1}{k!}\sum_{\pi\in
S_{k}}W_{B_{1}\cdots B_{k}}(\pi)$ (15)

is the projection onto the symmetric subspace. Thus, $k$-Bose-extendibility is
a special case of $G$-Bose-symmetric extendibility under the identifications
in (9)–(12).

######  Example II.3 ($G$-symmetric)

Let $G$ be a group with projective unitary representation
$\\{U_{S}(g)\\}_{g\in G}$, and let $\rho_{S}$ be a quantum state of system
$S$. A state $\rho_{S}$ is symmetric with respect to $G$ [59, 60] if

$\rho_{S}=U_{S}(g)\rho_{S}U_{S}(g)^{{\dagger}}\quad\forall g\in G.$ (16)

Thus, the established notion of symmetry of a state $\rho_{S}$ with respect to
a group $G$ is a special case of $G$-symmetric extendibility in which the
system $R$ is trivial.

######  Example II.4 ($G$-Bose-symmetric)

A state $\rho_{S}$ is Bose-symmetric with respect to $G$ if

$\rho_{S}=U_{S}(g)\rho_{S}\quad\forall g\in G.$ (17)

The condition in (17) is equivalent to the condition

$\rho_{S}=\Pi_{S}^{G}\rho_{S}\Pi_{S}^{G},$ (18)

where the projector $\Pi_{S}^{G}$ is defined as

$\Pi_{S}^{G}\coloneqq\frac{1}{\left|G\right|}\sum_{g\in G}U_{S}(g).$ (19)

Thus, the established notion of Bose symmetry of a state $\rho_{S}$ with
respect to a group $G$ is a special case of $G$-Bose symmetric extendibility
in which the system $R$ is trivial.

Although the concepts of $G$-symmetric extendibility and $G$-Bose-symmetric
extendibility, in Definitions II.1 and II.2, respectively, are generally
different, we can relate them by purifying a $G$-symmetric extendible state to
a larger Hilbert space, as stated in Theorem II.1 below. The ability to do so
plays a critical role in the algorithms proposed in Section III. We give a
proof of Theorem II.1 in Appendix A.

###### Theorem II.1

A state $\rho_{S}$ is $G$-symmetric extendible if and only if there exists a
purification $\psi_{RS\hat{R}\hat{S}}^{\rho}$ of $\rho_{S}$ satisfying the
following:

$|\psi^{\rho}\rangle_{RS\hat{R}\hat{S}}=\left(U_{RS}(g)\otimes\overline{U}_{\hat{R}\hat{S}}(g)\right)|\psi^{\rho}\rangle_{RS\hat{R}\hat{S}}\quad\forall
g\in G,$ (20)

where the overbar denotes the entrywise complex conjugate. The condition in
(20) is equivalent to

$|\psi^{\rho}\rangle_{RS\hat{R}\hat{S}}=\Pi_{RS\hat{R}\hat{S}}^{G}|\psi^{\rho}\rangle_{RS\hat{R}\hat{S}},$
(21)

where

$\Pi_{RS\hat{R}\hat{S}}^{G}\coloneqq\frac{1}{\left|G\right|}\sum_{g\in
G}U_{RS}(g)\otimes\overline{U}_{\hat{R}\hat{S}}(g).$ (22)

##  III Testing symmetry and extendibility on quantum computers

Test | Algorithm | Acceptance Probability
---|---|---
$G$-Bose symmetry | 1 | $\max_{\sigma\in\text{B-Sym}_{G}}F(\rho,\sigma)$
$G$-symmetry | 2 | $\max_{\sigma\in\text{Sym}_{G}}F(\rho,\sigma)$
$G$-Bose symmetric extendibility | 3 | $\max_{\sigma\in\text{BSE}_{G}}F(\rho,\sigma)$
$G$-symmetric extendibility | 4 | $\max_{\sigma\in\text{SymExt}_{G}}F(\rho,\sigma)$
Table 1: Summary of the various symmetry tests proposed in Section III and
their acceptance probabilities. For more details, see Theorems III.1, III.2,
III.3, and III.4.

We can use a quantum computer to test for $G$-symmetric extendibility of a
quantum state, as well as for other forms of symmetry discussed in the
previous section. We assume the following in doing so:

  1. 1.

there is a quantum circuit available that prepares a purification
$\psi_{S^{\prime}S}^{\rho}$ of the state $\rho_{S}$,

  2. 2.

there is an efficient implementation of each of the unitary operators in the
set $\\{U_{RS}(g)\\}_{g\in G}$,

  3. 3.

and there is an efficient implementation of each of the unitary operators in
the set $\\{\overline{U}_{RS}(g)\\}_{g\in G}$.

The first assumption can be made less restrictive by employing the
variational, purification-learning procedure from [25]. That is, given a
circuit that prepares the state $\rho_{S}$, the variational algorithm from
[25] outputs a circuit that approximately prepares a purification of
$\rho_{S}$. We should note that the convergence of the algorithm from [25] has
not been established, and so the first assumption might be necessary for some
applications. See also [33].

The last assumption can be relaxed by the following reasoning: a standard gate
set for approximating arbitrary unitaries in quantum computing consists of the
controlled-NOT gate, the Hadamard gate, and the $T$ gate [61]. The first two
gates have only real entries while the $T$ gate is a diagonal $2\times 2$
unitary gate with the entries $1$ and $e^{i\pi/4}$. The complex conjugate of
this gate is equal to $T^{{\dagger}}$. Thus, if a circuit for $U_{RS}(g)$ is
constructed from this standard gate set, then we can generate a circuit for
$\overline{U}_{RS}(g)$ by replacing every $T$ gate in the original circuit
with $T^{{\dagger}}$.

We now consider various quantum computational tests of symmetry that have
increasing complexity. Table 1 summarizes the main theoretical insight of this
section, which is that the acceptance probability of each symmetry test can be
expressed in terms of the fidelity of the state being tested to a set of
symmetric states.

To give insight along the way, we provide an example along with the tests
below. In particular, we consider the dihedral group of the triangle, $D_{3}$,
which has order six and is isomorphic to the symmetric group on three
elements, the smallest non-abelian group. Recall that dihedral groups are the
symmetry groups of regular polygons.

Our example $D_{3}$ is generated via a flip $f$ and a rotation $r$: $\langle
e,f,r\ |\ r^{3}=e,f^{2}=e,frf=r^{-1}\rangle$. The group thus has six elements
$\\{e,f,r,r^{2},fr,fr^{2}\\}$, where $e$ is the identity element. We will
specify elements $r^{2},fr,fr^{2}$ in order to enforce the rules of the group.

The group table for this dihedral group is given by

Group element |  $e$ |  $f$ |  $r$ |  $r^{2}$ |  $fr$ |  $fr^{2}$
---|---|---|---|---|---|---
$e$ |  $e$ |  $f$ |  $r$ |  $r^{2}$ |  $fr$ |  $fr^{2}$
$f$ |  $f$ |  $e$ |  $fr$ |  $fr^{2}$ |  $r$ |  $r^{2}$
$r$ |  $r$ |  $fr^{2}$ |  $r^{2}$ |  $e$ |  $f$ |  $fr$
$r^{2}$ |  $r^{2}$ |  $fr$ |  $e$ |  $r$ |  $fr^{2}$ |  $f$
$fr$ |  $fr$ |  $r^{2}$ |  $fr^{2}$ |  $f$ |  $e$ |  $r$
$fr^{2}$ |  $fr^{2}$ |  $r$ |  $f$ |  $fr$ |  $r^{2}$ |  $e$

To fully realize $D_{3}$, we use a two-qubit unitary representation and
specify the generators as such:
$\\{e\rightarrow\mathbb{I},f\rightarrow\textrm{CNOT},r\rightarrow\textrm{CNOT}\circ\textrm{SWAP}\\}$.
A quick check confirms that these generators obey the commutation rules of the
group and generate the table above. Throughout the next four sections, we
substitute this group into the presented algorithms to demonstrate their
construction.

###  III.1 Testing $G$-Bose symmetry

Let us begin by discussing the simplest version of the problem. Suppose that
the state under consideration is pure, so that we can write it as
$\psi_{S}\equiv|\psi\rangle\\!\langle\psi|_{S}$, and that the $R$ system is
trivial. We recover the traditional case of $G$-Bose symmetry mentioned in
Example II.4. Thus, our goal is to decide if

$|\psi\rangle_{S}=U_{S}(g)|\psi\rangle_{S}\quad\forall g\in G.$ (23)

This latter condition is equivalent to

$|\psi\rangle_{S}=\Pi_{S}^{G}|\psi\rangle_{S},$ (24)

where

$\Pi_{S}^{G}\coloneqq\frac{1}{\left|G\right|}\sum_{g\in G}U_{S}(g),$ (25)

which is in turn equivalent to

$\left\|\Pi_{S}^{G}|\psi\rangle_{S}\right\|_{2}=1.$ (26)

The equivalence

$|\psi\rangle_{S}=\Pi_{S}^{G}|\psi\rangle_{S}\quad\Leftrightarrow\quad\left\|\Pi_{S}^{G}|\psi\rangle_{S}\right\|_{2}=1$
(27)

holds from the Pythagorean theorem and the positive definiteness of the norm.
Indeed,

$\left\|\Pi_{S}^{G}|\psi\rangle_{S}\right\|_{2}=1\quad\Rightarrow\quad\left\|\Pi_{S}^{G}|\psi\rangle_{S}\right\|_{2}^{2}=1=\left\||\psi\rangle_{S}\right\|_{2}^{2}$
(28)

and since the Pythagorean theorem states that

$\left\|\Pi_{S}^{G}|\psi\rangle_{S}\right\|_{2}^{2}+\left\|(I_{S}-\Pi_{S}^{G})|\psi\rangle_{S}\right\|_{2}^{2}=\left\||\psi\rangle_{S}\right\|_{2}^{2},$
(29)

we conclude that $\left\|(I_{S}-\Pi_{S}^{G})|\psi\rangle_{S}\right\|_{2}=0$,
which implies that $(I_{S}-\Pi_{S}^{G})|\psi\rangle_{S}=0$ from the positive
definiteness of the norm. This in turn is equivalent to the left-hand side of
(27). Thus, if we have a method to perform the projection onto $\Pi_{S}^{G}$,
then we can decide whether (26) holds.

There is a simple quantum algorithm to do so. This algorithm was originally
proposed in [42, Chapter 8] under the name of “generalized phase estimation.”
It proceeds as follows and can be summarized as “performing the quantum phase
estimation algorithm with respect to the unitary representation
$\\{U_{S}(g)\\}_{g\in G}$”:

######  Algorithm 1 ($G$-Bose symmetry test)

The algorithm consists of the following steps:

  1. 1.

Prepare an ancillary register $C$ in the state $|0\rangle_{C}$.

  2. 2.

Act on register $C$ with a quantum Fourier transform.

  3. 3.

Append the state $|\psi\rangle_{S}$ and perform the following controlled
unitary:

$\sum_{g\in G}|g\rangle\\!\langle g|_{C}\otimes U_{S}(g),$ (30)

  4. 4.

Perform an inverse quantum Fourier transform on register $C$, measure in the
basis $\\{|g\rangle\\!\langle g|_{C}\\}_{g\in G}$, and accept if the zero
outcome $|0\rangle\\!\langle 0|_{C}$ occurs.

Figure 1: Quantum circuit to implement Algorithm 1. 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 that the
measurement $\\{|+\rangle\\!\langle+|_{C},I_{C}-|+\rangle\\!\langle+|_{C}\\}$
is performed. (We use this same notation in several forthcoming figures.)
Algorithm 1 tests whether the state $\rho_{S}$ is $G$-Bose symmetric, as
defined in Example II.4. Its acceptance probability is equal to
$\operatorname{Tr}[\Pi_{S}^{G}\rho_{S}]$, where $\Pi_{S}^{G}$ is defined in
(25).

Note that the register $C$ has dimension $\left|G\right|$. Also, we can write
the state $|0\rangle_{C}$ as $|e\rangle_{C}$, where $e$ is the identity
element of the group. The result of Step 2 of Algorithm 1 is to prepare the
following uniform superposition state:

$|+\rangle_{C}\coloneqq\frac{1}{\sqrt{\left|G\right|}}\sum_{g\in
G}|g\rangle_{C}.$ (31)

Although the quantum Fourier transform is specified in Algorithm 1, in fact,
any unitary that generates the desired superposition state $|+\rangle_{C}$ can
serve as a replacement in Steps 2 and 4 above and oftentimes leads to an
improvement in circuit depth. The same is true for all algorithms that follow.

Moving on, the overall state after Step 3 is as follows:

$\frac{1}{\sqrt{\left|G\right|}}\sum_{g\in
G}|g\rangle_{C}U_{S}(g)|\psi\rangle_{S}.$ (32)

The final step of Algorithm 1 projects the register $C$ onto the state
$|+\rangle_{C}$. According to the aforementioned convention, Algorithm 1
accepts if the identity element outcome $|e\rangle\\!\langle e|_{C}$ occurs.
The probability that Algorithm 1 accepts is equal to

$\displaystyle\left\|\left(\langle+|_{C}\otimes
I_{S}\right)\left(\frac{1}{\sqrt{\left|G\right|}}\sum_{g\in
G}|g\rangle_{C}U_{S}(g)|\psi\rangle_{S}\right)\right\|_{2}^{2}$
$\displaystyle=\left\|\frac{1}{\left|G\right|}\sum_{g\in
G}U_{S}(g)|\psi\rangle_{S}\right\|_{2}^{2}$ (33)
$\displaystyle=\left\|\Pi_{S}^{G}|\psi\rangle_{S}\right\|_{2}^{2}.$ (34)

Figure 1 depicts this quantum algorithm. Not only does it decide whether the
state $|\psi\rangle_{S}$ is symmetric, but it also quantifies how symmetric
the state is. Since the acceptance probability is equal to
$\left\|\Pi_{S}^{G}|\psi\rangle_{S}\right\|_{2}^{2}$, and this quantity is a
measure of symmetry (see Theorem VII.2), we can repeat the algorithm a large
number of times to estimate the acceptance probability to arbitrary precision.

The same quantum algorithm can decide whether a given mixed state $\rho_{S}$
is $G$-Bose symmetric (see Example II.4). Similar to the above, it also can
estimate how $G$-Bose symmetric the state $\rho_{S}$ is. To see this, consider
that the acceptance probability for a pure state can be rewritten as follows:

$\left\|\Pi_{S}^{G}|\psi\rangle_{S}\right\|_{2}^{2}=\operatorname{Tr}[\Pi_{S}^{G}|\psi\rangle\\!\langle\psi|_{S}].$
(35)

Then since every mixed state can be written as a probabilistic mixture of pure
states, it follows that the acceptance probability of Algorithm 1, when acting
on the mixed state $\rho_{S}$, is equal to

$\operatorname{Tr}[\Pi_{S}^{G}\rho_{S}].$ (36)

This acceptance probability is equal to one if and only if
$\rho_{S}=\Pi_{S}^{G}\rho_{S}\Pi_{S}^{G}$, and so this test is a faithful test
of $G$-Bose symmetry. The equivalence

$\operatorname{Tr}[\Pi_{S}^{G}\rho_{S}]=1\quad\Leftrightarrow\quad\rho_{S}=\Pi_{S}^{G}\rho_{S}\Pi_{S}^{G}$
(37)

follows as a limiting case of the gentle measurement lemma [81, 62] (see also
[80, Lemma 9.4.1]):

$\frac{1}{2}\left\|\rho_{S}-\frac{\Pi_{S}^{G}\rho_{S}\Pi_{S}^{G}}{\operatorname{Tr}[\Pi_{S}^{G}\rho_{S}]}\right\|_{1}\leq\sqrt{1-\operatorname{Tr}[\Pi_{S}^{G}\rho_{S}]}$
(38)

and the positive definiteness of the trace norm. Again, through repetition, we
can estimate the acceptance probability
$\operatorname{Tr}[\Pi_{S}^{G}\rho_{S}]$ and then employ it as a measure of
$G$-Bose symmetry (see Theorem VII.2).

Interestingly, the acceptance probability of Algorithm 1 can be expressed as
the maximum $G$-Bose-symmetric fidelity, defined for a state $\rho_{S}$ as

$\max_{\sigma_{S}\in\operatorname{B-Sym}_{G}}F(\rho_{S},\sigma_{S}),$ (39)

where

$\operatorname{B-Sym}_{G}\coloneqq\left\\{\sigma_{S}\in\mathcal{D}(\mathcal{H}_{S}):\sigma_{S}=\Pi_{S}^{G}\sigma_{S}\Pi_{S}^{G}\right\\},$
(40)

and the fidelity of quantum states $\omega$ and $\tau$ is defined as [72]

$F(\omega,\tau)\coloneqq\left\|\sqrt{\omega}\sqrt{\tau}\right\|_{1}^{2}.$ (41)

We state this claim in Theorem III.1 below and provide a proof of Theorem
III.1 in Appendix B.1. Thus, Algorithm 1 gives an operational meaning to the
maximum $G$-Bose-symmetric fidelity in terms of its acceptance probability,
and it can be used to estimate this fundamental measure of symmetry.

###### Theorem III.1

For a state $\rho_{S}$, the acceptance probability of Algorithm 1 is equal to
the maximum $G$-Bose symmetric fidelity. That is,

$\operatorname{Tr}[\Pi_{S}^{G}\rho_{S}]=\max_{\sigma_{S}\in\operatorname{B-Sym}_{G}}F(\rho_{S},\sigma_{S}).$
(42)

###### Example III.1

In the example of the dihedral group $D_{3}$, the $|+\rangle_{C}$ state is a
uniform superposition of six elements. We use three qubits and the unitary
$U_{d}$ shown in Figure 2 to generate an equal superposition of six elements:

$U_{d}|000\rangle=\frac{1}{\sqrt{6}}(|000\rangle+|001\rangle+|010\rangle+\\\
|011\rangle+|100\rangle+|101\rangle).$ (43)

These control register states need to be mapped to group elements to be
meaningful; thus, we employ the mapping $\\{|000\rangle\rightarrow
e,|001\rangle\rightarrow fr^{2},|010\rangle\rightarrow
fr,|011\rangle\rightarrow r,|100\rangle\rightarrow f,|101\rangle\rightarrow
r^{2}\\}$ for our circuit constructions. The circuit to test for
$D_{3}$-symmetry is shown in Figure 3.

Figure 2: Unitary $U_{d}$, with
$\theta=2\arctan\\!\left(\frac{1}{\sqrt{2}}\right)$, generates the equal
superposition of six elements from (43).

.

Figure 3: Quantum circuit implementing Algorithm 1 to test $G$-Bose symmetry
for $D_{3}$. Compared to Figure 1, the systems $S$ and $S^{\prime}$ are two
qubits each, $C$ consists of three qubits, and $|+\rangle_{C}$ is defined as
$U_{d}|000\rangle$.

###  III.2 Testing $G$-symmetry

We now discuss how to modify Algorithm 1 to one that decides whether a state
$\rho_{S}$ is $G$-symmetric (see Example II.3), i.e., if

$\rho_{S}=U_{S}(g)\rho_{S}U_{S}(g)^{{\dagger}}\quad\forall g\in G\,.$ (44)

We also prove that the acceptance probability of the modified algorithm
(Algorithm 2 below) is equal to the maximum $G$-symmetric fidelity, defined as

$\max_{\sigma\in\text{Sym}_{G}}F(\rho_{S},\sigma_{S}),$ (45)

where

$\operatorname{Sym}_{G}\coloneqq\left\\{\sigma_{S}\in\mathcal{D}(\mathcal{H}_{S}):\sigma_{S}=U_{S}(g)\sigma_{S}U_{S}(g)^{{\dagger}}\
\forall g\in G\right\\},$ (46)

and $\mathcal{D}(\mathcal{H}_{S})$ denotes the set of density operators acting
on the Hilbert space $\mathcal{H}_{S}$. Thus, Algorithm 2 gives an operational
meaning to the maximum $G$-symmetric fidelity in terms of its acceptance
probability, and it can be used to estimate this fundamental measure of
symmetry.

In the modified approach, we suppose that the quantum computer (now called the
verifier) is equipped with access to a “quantum prover”—an agent who can
perform arbitrarily powerful quantum computations. We suppose that the quantum
computer is allowed to exchange two quantum messages with the prover. The
resulting class of problems that can be solved using this approach is
abbreviated QIP(2), for quantum interactive proofs with two quantum messages
exchanged [75, 73], and we note here that computational problems related to
entanglement of bipartite states [45, 46] and recoverability of tripartite
states [22] were previously shown to be decidable in QIP(2). These latter
problems were proven to be QSZK-hard, and it remains an open question to
determine their precise computational complexity.

Let $|\psi\rangle_{S^{\prime}S}$ be a purification of the state $\rho_{S}$,
and suppose that the verifier has access to a circuit $U^{\rho}$ that prepares
this purification of $\rho_{S}$.

######  Algorithm 2 ($G$-symmetry test)

The algorithm consists of the following steps:

  1. 1.

The verifier uses the circuit $U^{\rho}$ to prepare the state
$|\psi\rangle_{S^{\prime}S}$.

  2. 2.

The verifier transmits the purifying system $S^{\prime}$ to the prover.

  3. 3.

The prover appends an ancillary register $E$ in the state $|0\rangle_{E}$ and
performs a unitary $V_{S^{\prime}E\rightarrow\hat{S}E^{\prime}}$.

  4. 4.

The prover sends the system $\hat{S}$ back to the verifier.

  5. 5.

The verifier prepares a register $C$ in the state $|0\rangle_{C}$.

  6. 6.

The verifier acts on register $C$ with a quantum Fourier transform.

  7. 7.

The verifier performs the following controlled unitary:

$\sum_{g\in G}|g\rangle\\!\langle g|_{C}\otimes
U_{S}(g)\otimes\overline{U}_{\hat{S}}(g).$ (47)

  8. 8.

The verifier performs an inverse quantum Fourier transform on register $C$,
measures in the basis $\\{|g\rangle\\!\langle g|_{C}\\}_{g\in G}$, and accepts
if and only if the zero outcome $|0\rangle\\!\langle 0|_{C}$ occurs.

Figure 4 depicts this quantum algorithm. The overall state after Step 3 of
Algorithm 2 is

$V_{S^{\prime}E\rightarrow\hat{S}E^{\prime}}|\psi\rangle_{S^{\prime}S}|0\rangle_{E}.$
(48)

The result of Step 6 is to prepare the uniform superposition state
$|+\rangle_{C}$, which is defined in (31). After Step 7, the overall state is

$\frac{1}{\sqrt{\left|G\right|}}\sum_{g\in
G}|g\rangle_{C}\left(U_{S}(g)\otimes\overline{U}_{\hat{S}}(g)\right)V_{S^{\prime}E\rightarrow\hat{S}E^{\prime}}|\psi\rangle_{S^{\prime}S}|0\rangle_{E}.$
(49)

For a fixed unitary $V_{S^{\prime}E\rightarrow\hat{S}E^{\prime}}$, the
probability of accepting, by following the same reasoning in (33)–(34), is
equal to

$\left\|\Pi_{S\hat{S}}^{G}V_{S^{\prime}E\rightarrow\hat{S}E^{\prime}}|\psi\rangle_{S^{\prime}S}|0\rangle_{E}\right\|_{2}^{2},$
(50)

where

$\Pi_{S\hat{S}}^{G}\coloneqq\frac{1}{\left|G\right|}\sum_{g\in
G}U_{S}(g)\otimes\overline{U}_{\hat{S}}(g).$ (51)

Since the goal of the prover in a quantum interactive proof is to convince the
verifier to accept [75, 73], the prover optimizes over every unitary
$V_{S^{\prime}E\rightarrow\hat{S}E^{\prime}}$ and the acceptance probability
of Algorithm 2 is given by

$\max_{V_{S^{\prime}E\rightarrow\hat{S}E^{\prime}}}\left\|\Pi_{S\hat{S}}^{G}V_{S^{\prime}E\rightarrow\hat{S}E^{\prime}}|\psi\rangle_{S^{\prime}S}|0\rangle_{E}\right\|_{2}^{2}.$
(52)

Figure 4: Quantum circuit to implement Algorithm 2. The unitary $U^{\rho}$
prepares a purification $\psi_{S^{\prime}S}$ of the state $\rho_{S}$.
Algorithm 2 tests whether the state $\rho_{S}$ is $G$-symmetric, as defined in
Example II.3. Its acceptance probability is equal to the maximum $G$-symmetric
fidelity, as defined in (45).

The main idea behind Algorithm 2 is that if the state $\rho_{S}$ possesses the
symmetry in (44), then Theorem II.1 (with trivial reference system $R$)
guarantees the existence of a purification $\phi_{S\hat{S}}$ of $\rho_{S}$
such that

$|\phi\rangle_{S\hat{S}}=\Pi_{S\hat{S}}^{G}|\phi\rangle_{S\hat{S}}.$ (53)

Since all purifications of a quantum state are related by a unitary acting on
the purifying system (see, e.g., [80]), the prover is able to apply a unitary
taking the purification $|\psi\rangle_{S^{\prime}S}$ to the purification
$|\phi\rangle_{S\hat{S}}$. After the prover sends back the system $\hat{S}$,
the verifier then performs a quantum-computational test to determine if the
condition in (53) holds.

We now formally state the claim made just after (44). See Appendix B.2 for a
proof of Theorem III.2.

###### Theorem III.2

The acceptance probability of Algorithm 2 is equal to the maximum
$G$-symmetric fidelity in (45), i.e.,

$\max_{V_{S^{\prime}E\rightarrow\hat{S}E^{\prime}}}\left\|\Pi_{S\hat{S}}^{G}V_{S^{\prime}E\rightarrow\hat{S}E^{\prime}}|\psi\rangle_{S^{\prime}S}|0\rangle_{E}\right\|_{2}^{2}\\\
=\max_{\sigma_{S}\in\operatorname{Sym}_{G}}F(\rho_{S},\sigma_{S}).$ (54)

###### Example III.2

For the triangular dihedral group example (see Example III.1), we use the same
unitary $U_{d}$ as in (43) to prepare the superposition $|+\rangle_{C}$ and
the same mapping of control states to group elements. The circuit to test for
$G$-symmetry is shown in Figure 5.

Figure 5: Quantum circuit implementing Algorithm 2 to test $G$-symmetry in the
case that the group $G$ is the triangular dihedral group. Compared to Figure
4, the systems $S$ and $S^{\prime}$ are two qubits each, $C$ consists of three
qubits, and $|+\rangle_{C}$ is defined as $U_{d}|000\rangle$. Both the SWAP
and CNOT gates have no imaginary entries, and thus they are equal to their own
complex conjugates.

######  Remark 1 (Testing incoherence)

We note here that testing the incoherence of a quantum state, in the sense of
[6, 67], is a special case of testing $G$-symmetry. To see this, we can pick
$G$ to be the cyclic group over $d$ elements with unitary representation
$\\{Z(z)\\}_{z}$, where $Z(z)$ is the generalized Pauli phase-shift unitary,
defined as

$Z(z)\coloneqq\sum_{j=0}^{d-1}e^{2\pi ijz/d}|j\rangle\\!\langle j|.$ (55)

A state is symmetric with respect to this group if the condition in (44)
holds. This condition is equivalent to the following one:

$\rho_{S}=\frac{1}{|G|}\sum_{g\in G}U_{S}(g)\rho_{S}U_{S}(g)^{\dagger}.$ (56)

For the choice mentioned above, the condition in (56) holds if and only if the
state $\rho_{S}$ is diagonal in the incoherent basis, i.e., if it can be
written as $\rho_{S}=\sum_{j}p(j)|j\rangle\\!\langle j|$, where $p(j)$ is a
probability distribution. Thus, Algorithm 2 can be used to test the
incoherence of quantum states.

###  III.3 Testing $G$-Bose symmetric extendibility

We now describe an algorithm for testing $G$-Bose symmetric extendibility of a
quantum state $\rho_{S}$, as defined in Definition II.2. The algorithm bears
some similarities with Algorithms 1 and 2. Like Algorithm 2, it involves an
interaction between a verifier and a prover. We prove that its acceptance
probability is equal to the maximum $G$-BSE fidelity:

$\max_{\sigma_{S}\in\operatorname*{BSE}_{G}}F(\rho_{S},\sigma_{S}),$ (57)

where BSEG is the set of $G$-Bose symmetric extendible states:

$\text{BSE}_{G}\coloneqq\\\ \left\\{\begin{array}[c]{c}\sigma_{S}:\exists\
\omega_{RS}\in\mathcal{D}(\mathcal{H}_{RS}),\operatorname{Tr}_{R}[\omega_{RS}]=\sigma_{S},\\\
\omega_{RS}=U_{RS}(g)\omega_{RS},\ \forall g\in G\end{array}\right\\}.$ (58)

Thus, the algorithm endows the maximum $G$-BSE fidelity with an operational
meaning. Note that the condition $\omega_{RS}=U_{RS}(g)\omega_{RS}$ for all
$g\in G$ is equivalent to

$\omega_{RS}=\Pi_{RS}^{G}\omega_{RS}\Pi_{RS}^{G},$ (59)

where

$\Pi_{RS}^{G}\coloneqq\frac{1}{\left|G\right|}\sum_{g\in G}U_{RS}(g).$ (60)

The algorithm is similar to Algorithm 2, but we list it here for completeness.
Let $|\psi\rangle_{S^{\prime}S}$ be a purification of the state $\rho_{S}$,
and suppose that the circuit $U^{\rho}$ prepares this purification of
$\rho_{S}$.

######  Algorithm 3 ($G$-BSE test)

The algorithm proceeds as follows:

  1. 1.

The verifier uses the circuit provided to prepare the state
$|\psi\rangle_{S^{\prime}S}$.

  2. 2.

The verifier transmits the purifying system $S^{\prime}$ to the prover.

  3. 3.

The prover appends an ancillary register $E$ in the state $|0\rangle_{E}$ and
performs a unitary $V_{S^{\prime}E\rightarrow RE^{\prime}}$.

  4. 4.

The prover sends the system $R$ back to the verifier.

  5. 5.

The verifier prepares a register $C$ in the state $|0\rangle_{C}$.

  6. 6.

The verifier acts on register $C$ with a quantum Fourier transform.

  7. 7.

The verifier performs the following controlled unitary:

$\sum_{g\in G}|g\rangle\\!\langle g|_{C}\otimes U_{RS}(g),$ (61)

  8. 8.

The verifier performs an inverse quantum Fourier transform on register $C$,
measures in the basis $\\{|g\rangle\\!\langle g|_{C}\\}_{g\in G}$, and accepts
if and only if the zero outcome $|0\rangle\\!\langle 0|_{C}$ occurs.

Figure 6: Quantum circuit to implement Algorithm 3. The unitary $U^{\rho}$
prepares a purification $\psi_{S^{\prime}S}$ of the state $\rho_{S}$.
Algorithm 3 tests whether the state $\rho_{S}$ is $G$-Bose symmetric
extendible, as defined in Definition II.2. Its acceptance probability is equal
to the maximum $G$-BSE fidelity, as defined in (57).

Figure 6 depicts this quantum algorithm. The overall state after Step 3 is

$V_{S^{\prime}E\rightarrow
RE^{\prime}}|\psi\rangle_{S^{\prime}S}|0\rangle_{E}.$ (62)

Step 6 prepares the uniform superposition state $|+\rangle_{C}$, which is
defined in (31). After Step 7, the overall state is

$\frac{1}{\sqrt{\left|G\right|}}\sum_{g\in
G}|g\rangle_{C}U_{RS}(g)V_{S^{\prime}E\rightarrow
RE^{\prime}}|\psi\rangle_{S^{\prime}S}|0\rangle_{E}.$ (63)

The last step can be understood as the verifier projecting the register $C$
onto the state $|+\rangle_{C}$.

The probability of accepting, following the same reasoning as before, is equal
to

$\left\|\Pi_{RS}^{G}V_{S^{\prime}E\rightarrow
RE^{\prime}}|\psi\rangle_{S^{\prime}S}|0\rangle_{E}\right\|_{2}^{2},$ (64)

where $\Pi_{RS}^{G}$ is defined in (60). As before, the goal of the prover in
a quantum interactive proof is to convince the verifier to accept [75, 73],
and so the prover optimizes over every unitary
$V_{S^{\prime}E\rightarrow\hat{S}E^{\prime}}$. The acceptance probability of
Algorithm 3 is then given by

$\max_{V_{S^{\prime}E\rightarrow
RE^{\prime}}}\left\|\Pi_{RS}^{G}V_{S^{\prime}E\rightarrow
RE^{\prime}}|\psi\rangle_{S^{\prime}S}|0\rangle_{E}\right\|_{2}^{2}.$ (65)

Our proof of the following theorem is similar to the proof given for Theorem
III.2; for completeness, we provide a proof in Appendix B.3.

###### Theorem III.3

The maximum acceptance probability of Algorithm 3 is equal to the maximum
$G$-BSE fidelity in (57), i.e.,

$\max_{V_{S^{\prime}E\rightarrow
RE^{\prime}}}\left\|\Pi_{RS}^{G}V_{S^{\prime}E\rightarrow
RE^{\prime}}|\psi\rangle_{S^{\prime}S}|0\rangle_{E}\right\|_{2}^{2}\\\
=\max_{\sigma_{S}\in\operatorname*{BSE}_{G}}F(\rho_{S},\sigma_{S}),$ (66)

where the set $\operatorname*{BSE}_{G}$ is defined in (58).

###### Example III.3

For the triangular dihedral group example (see Example III.1), we use the same
unitary $U_{d}$ to prepare the superposition $|+\rangle_{C}$ and the same
mapping of control states to group elements. The circuit to test for $G$-Bose
symmetric extendibility is shown in Figure 7.

Figure 7: Quantum circuit implementing Algorithm 3 to test $G$-Bose symmetric
extendibility for the triangular dihedral group. Compared to Figure 6, the
systems $S$ and $S^{\prime}$ are one qubit each, $C$ consists of three qubits,
and $|+\rangle_{C}$ is defined as $U_{d}|000\rangle$.

###  III.4 Testing $G$-symmetric extendibility

The final algorithm that we introduce tests whether a state $\rho_{S}$ is
$G$-symmetric extendible (recall Definition II.1). Similar to the algorithms
in the previous sections, not only does it decide whether $\rho_{S}$ is
$G$-symmetric extendible, but it also quantifies how similar it is to a state
in the set of $G$-symmetric extendible states. The acceptance probability is
equal to the maximum $G$-symmetric extendible fidelity:

$\max_{\sigma_{S}\in\operatorname{SymExt}_{G}}F(\rho_{S},\sigma_{S}),$ (67)

where

$\operatorname{SymExt}_{G}\coloneqq\left\\{\begin{array}[c]{c}\sigma_{S}:\exists\
\omega_{RS}\in\mathcal{D}(\mathcal{H}_{RS}),\operatorname{Tr}_{R}[\omega_{RS}]=\sigma_{S}\\\
\omega_{RS}=U_{RS}(g)\omega_{RS}U_{RS}(g)^{{\dagger}}\ \forall g\in
G\end{array}\right\\}.$ (68)

We again operate in the model of quantum interactive proofs, in which a
verifier interacts with a prover.

We list the algorithm below for completeness, noting its similarity to the
previous algorithms. Let $|\psi\rangle_{S^{\prime}S}$ be a purification of the
state $\rho_{S}$, and suppose that the circuit $U^{\rho}$ prepares this
purification of $\rho_{S}$.

######  Algorithm 4 ($G$-SE test)

The algorithm proceeds as follows:

  1. 1.

The verifier uses the circuit $U^{\rho}$ to prepare the state
$|\psi\rangle_{S^{\prime}S}$, which is a purification of the state $\rho_{S}$.

  2. 2.

The verifier transmits the purifying system $S^{\prime}$ to the prover.

  3. 3.

The prover appends an ancillary register $E$ in the state $|0\rangle_{E}$ and
performs a unitary $V_{S^{\prime}E\rightarrow R\hat{R}\hat{S}E^{\prime}}$.

  4. 4.

The prover sends the systems $R\hat{R}\hat{S}$ back to the verifier.

  5. 5.

The verifier prepares a register $C$ in the state $|0\rangle_{C}$.

  6. 6.

The verifier acts on register $C$ with a quantum Fourier transform.

  7. 7.

The verifier performs the following controlled unitary:

$\sum_{g\in G}|g\rangle\\!\langle g|_{C}\otimes
U_{RS}(g)\otimes\overline{U}_{\hat{R}\hat{S}}(g),$ (69)

  8. 8.

The verifier performs an inverse quantum Fourier transform on register $C$,
measures in the basis $\\{|g\rangle\\!\langle g|_{C}\\}_{g\in G}$, and accepts
if and only if the zero outcome $|0\rangle\\!\langle 0|_{C}$ occurs.

Figure 8 depicts this quantum algorithm. After Step 3, the overall state is

$V_{S^{\prime}E\rightarrow
R\hat{R}\hat{S}E^{\prime}}|\psi\rangle_{S^{\prime}S}|0\rangle_{E}.$ (70)

Step 5 prepares the uniform superposition state $|+\rangle_{C}$, which is
defined in (31). After Step 7, the overall state is

$\frac{1}{\sqrt{\left|G\right|}}\sum_{g\in
G}|g\rangle_{C}\left(U_{RS}(g)\otimes\overline{U}_{\hat{R}\hat{S}}(g)\right)V|\psi\rangle_{S^{\prime}S}|0\rangle_{E},$
(71)

where $V\equiv V_{S^{\prime}E\rightarrow R\hat{R}\hat{S}E^{\prime}}$. The last
step can be understood as the verifier projecting the register $C$ onto the
state $|+\rangle_{C}$.

The probability of accepting is equal to

$\left\|\Pi_{RS\hat{R}\hat{S}}^{G}V_{S^{\prime}E\rightarrow
R\hat{R}\hat{S}E^{\prime}}|\psi\rangle_{S^{\prime}S}|0\rangle_{E}\right\|_{2}^{2},$
(72)

where $\Pi_{RS\hat{R}\hat{S}}^{G}$ is defined in (22). As before, the prover
optimizes over every unitary $V_{S^{\prime}E\rightarrow
R\hat{R}\hat{S}E^{\prime}}$. The acceptance probability of Algorithm 4 is then
given by

$\left\|\Pi_{RS\hat{R}\hat{S}}^{G}V_{S^{\prime}E\rightarrow
R\hat{R}\hat{S}E^{\prime}}|\psi\rangle_{S^{\prime}S}|0\rangle_{E}\right\|_{2}^{2}.$
(73)

Figure 8: Quantum circuit to implement Algorithm 4. The unitary $U^{\rho}$
prepares a purification $\psi_{S^{\prime}S}$ of the state $\rho_{S}$.
Algorithm 4 tests whether the state $\rho_{S}$ is $G$-symmetric extendible, as
defined in Definition II.1. Its acceptance probability is equal to the maximum
$G$-symmetric extendible fidelity, as defined in (67).

Our proof of the following theorem is similar to the proof given for Theorem
III.2. For completeness, we provide our proof in Appendix B.4.

###### Theorem III.4

The maximum acceptance probability of Algorithm 4 is equal to the maximum
$G$-symmetric extendible fidelity in (67), i.e.,

$\max_{V_{S^{\prime}E\rightarrow
R\hat{R}\hat{S}E^{\prime}}}\left\|\Pi_{RS\hat{R}\hat{S}}^{G}V_{S^{\prime}E\rightarrow
R\hat{R}\hat{S}E^{\prime}}|\psi\rangle_{S^{\prime}S}|0\rangle_{E}\right\|_{2}^{2}\\\
=\max_{\sigma_{S}\in\operatorname*{SymExt}_{G}}F(\rho_{S},\sigma_{S}),$ (74)

where the set $\operatorname*{SymExt}_{G}$ is defined in (68).

###### Example III.4

For the triangular dihedral group example (see Example III.1), we use the same
unitary $U_{d}$ to prepare the superposition $|+\rangle_{C}$ and the same
mapping of control states to group elements. The circuit to test for
$G$-symmetric extendibility is shown in Figure 9.

Figure 9: Quantum circuit implementing Algorithm 4 to test $G$-symmetric
extendibility in the case that the group $G$ is the triangular dihedral group.
Compared to Figure 8, the systems $S$ and $S^{\prime}$ are one qubit each, $C$
consists of three qubits, and $|+\rangle_{C}$ is defined as
$U_{d}|000\rangle$. Both the SWAP and CNOT gates have no imaginary entries and
thus are equal to their own complex conjugates.

##  IV Tests of $k$-extendibility of states and covariance symmetry of
channels

The theory developed in Section III is rather general. In the forthcoming
subsections, we apply it to test for extendibility of bipartite and
multipartite quantum states and to test for covariance symmetry of quantum
channels and measurements. Later on in Section VI, we consider many other
example of groups and symmetry tests and simulate the performance of
Algorithms 1–4.

###  IV.1 Separability test for pure bipartite states

We illustrate the $G$-Bose symmetry test from Section III.1 on a case of
interest: deciding whether a pure bipartite state is entangled. This problem
is known to be BQP-complete [38], and one can decide it by means of the SWAP
test as considered in [44]. The SWAP test as a quantum computational method of
quantifying entanglement has been further studied in recent work [35, 10].

Let $\psi_{AB}$ be a pure bipartite state, and let $\psi_{AB}^{\otimes k}$
denote $k$ copies of it. Then we can consider the permutation unitaries
$W_{B_{1}\cdots B_{k}}(\pi)$ from Example II.1. This example is a special case
of $G$-Bose symmetry with the identifications

$\displaystyle S$ $\displaystyle\leftrightarrow A_{1}B_{1}\cdots A_{k}B_{k},$
(75) $\displaystyle U_{S}(g)$ $\displaystyle\leftrightarrow I_{A_{1}\cdots
A_{k}}\otimes W_{B_{1}\cdots B_{k}}(\pi).$ (76)

The acceptance probability of Algorithm 1 is equal to

$\operatorname{Tr}[\Pi_{B_{1}\cdots B_{k}}^{\text{Sym}}\rho_{B}^{\otimes k}],$
(77)

where the projection $\Pi_{B_{1}\cdots B_{k}}^{\text{Sym}}$ onto the symmetric
subspace is defined in (15) and
$\rho_{B}\coloneqq\operatorname{Tr}_{A}[\psi_{AB}]$. We note that there is an
efficient quantum algorithm to implement this test [4, Section 4], which
amounts to an instance of the abstract formulation in Algorithm 1. For $k=2$,
this reduces to the well-known SWAP test with acceptance probability

$p_{\text{acc}}^{(2)}\coloneqq\frac{1}{2}\left(1+\operatorname{Tr}[\rho_{B}^{2}]\right).$
(78)

For $k=3$, the acceptance probability is

$p_{\text{acc}}^{(3)}\coloneqq\frac{1}{6}\left(1+3\operatorname{Tr}[\rho_{B}^{2}]+2\operatorname{Tr}[\rho_{B}^{3}]\right).$
(79)

For $k=4$, the acceptance probability is

$p_{\text{acc}}^{(4)}\coloneqq\\\
\frac{1}{24}\left(1+6\operatorname{Tr}[\rho_{B}^{2}]+3\left(\operatorname{Tr}[\rho_{B}^{2}]\right)^{2}+8\operatorname{Tr}[\rho_{B}^{3}]+6\operatorname{Tr}[\rho_{B}^{4}]\right).$
(80)

We conclude that

$p_{\text{acc}}^{(2)}\geq p_{\text{acc}}^{(3)}\geq p_{\text{acc}}^{(4)},$ (81)

because $\operatorname{Tr}[\rho^{k}]=\sum_{j}\lambda_{j}^{k}$, where the
eigenvalues of $\rho$ are $\\{\lambda_{j}\\}_{j}$, and for all
$x,y\in\left[0,1\right]$,

$\displaystyle\frac{1}{2}\left(x+x^{2}\right)$
$\displaystyle\geq\frac{1}{6}\left(x+3x^{2}+2x^{3}\right)$ (82)
$\displaystyle\geq\frac{1}{24}\left(x+6x^{2}+3x^{2}y+8x^{3}+6x^{4}\right).$
(83)

The inequalities in (81) imply that the tests become more difficult to pass as
$k$ increases. In a previous version of our paper [55], we speculated that
this trend of decreasing acceptance probability continues as $k$ increases.
Indeed, this was subsequently shown to be true in [14].

We can interpret these findings in two different ways. For each $k$, the
rejection probability $1-p_{\text{acc}}^{(k)}$ can be understood as an
entanglement measure for pure states, similar to how the linear entropy
$1-\operatorname{Tr}[\rho_{B}^{2}]$ is interpreted as an entanglement measure.
Indeed, these quantities are non-increasing under local operations and
classical communication that take pure states to pure states, as every Rényi
entropy (defined as
$\frac{1}{1-\alpha}\log\operatorname{Tr}[\rho_{B}^{\alpha}]$ for
$\alpha\in(0,1)\cup(1,\infty)$) is an entanglement measure for pure states
[43]. Another interpretation is that, if using these tests to decide if a
given pure state is product or entangled, a decision can be determined with
fewer repetitions of the basic test by using tests with higher values of $k$.

###  IV.2 Separability test for pure multipartite states

We can generalize the test from the previous section to one for pure
multipartite entanglement. Let $\psi_{A_{1}\cdots A_{m}}$ be a multipartite
pure state, and let $\psi_{A_{1}\cdots A_{m}}^{\otimes k}$ denote $k$ copies
of it. For $i\in\left\\{1,\ldots,m\right\\}$ and $\pi_{i}\in S_{k}$, let
$W_{A_{i,1}\cdots A_{i,k}}(\pi_{i})$ denote a permutation unitary, where $i$
is an index for the $i$th party, and the notation $A_{i,j}$ for
$j\in\left\\{1,\ldots,k\right\\}$ indicates the $j$th system of the $i$th
party. This example is a special case of $G$-Bose symmetry with the
identifications:

$\displaystyle S$ $\displaystyle\leftrightarrow A_{1,1}\cdots A_{1,k}\cdots
A_{m,1}\cdots A_{m,k},$ (84) $\displaystyle U_{S}(g)$
$\displaystyle\leftrightarrow\bigotimes\limits_{i=1}^{m}W_{A_{i,1}\cdots
A_{i,k}}(\pi_{i})$ (85) $\displaystyle G$
$\displaystyle\leftrightarrow\overset{m\text{
times}}{\overbrace{S_{k}\times\cdots\times S_{k}}},$ (86) $\displaystyle g$
$\displaystyle\leftrightarrow(\pi_{1},\ldots,\pi_{m}),$ (87)

where $\times$ denotes the direct product of groups. The $G$-Bose symmetry
test from Section III.1 has the following acceptance probability in this case:

$\operatorname{Tr}\\!\left[\bigotimes\limits_{i=1}^{m}\Pi_{A_{i,1}\cdots
A_{i,k}}^{\operatorname{Sym}}\psi_{A_{1}\cdots A_{m}}^{\otimes k}\right].$
(88)

Note that one can again use the circuit from [4, Section 4] to implement this
test. For $k=2$, this test is known to be a test of multipartite pure-state
entanglement [44], which has been considered in more recent works [35, 10]. As
far as we aware, the test proposed above, for larger values of $k$, has not
been considered previously. Presumably, as was the case for the bipartite
entanglement test mentioned above, the multipartite test is such that it
becomes easier to detect an entangled state as $k$ increases. We leave its
detailed analysis for future work.

###  IV.3 $k$-Bose extendibility test for bipartite states

We now demonstrate how the test for $G$-Bose symmetric extendibility from
Section III.3 can realize a test for $k$-Bose extendibility of a bipartite
state. Since every separable state is $k$-Bose extendible, this test is then
indirectly a test for separability. To see this in detail, recall that a
bipartite state $\sigma_{AB}$ is separable if it can be written as a convex
combination of pure product states [43, 54]:

$\sigma_{AB}=\sum_{x}p_{X}(x)\psi_{A}^{x}\otimes\phi_{B}^{x},$ (89)

where $p_{X}$ is a probability distribution and $\\{\psi_{A}^{x}\\}_{x}$ and
$\\{\phi_{B}^{x}\\}_{x}$ are sets of pure states. A $k$-Bose extension for
this state is as follows:

$\omega_{AB_{1}\cdots
B_{k}}=\sum_{x}p_{X}(x)\psi_{A}^{x}\otimes\phi_{B_{1}}^{x}\otimes\cdots\otimes\phi_{B_{k}}^{x}.$
(90)

By making the identifications discussed in Example II.2, it follows from
Theorem III.3 that the test from Section III.3 is a test for $k$-Bose
extendibility. For an input state $\rho_{AB}$, the acceptance probability of
Algorithm 3 is equal to the maximum $k$-Bose extendible fidelity

$\max_{\omega_{AB}\in k\text{-BE}}F(\rho_{AB},\omega_{AB}),$ (91)

where $k$-BE denotes the set of $k$-Bose extendible states, as defined in
Example II.2.

This test for $k$-Bose extendibility was proposed in [45, 46] for
understanding the computational complexity of the circuit separability
problem. In that work, it was not mentioned that the test employed is a test
for $k$-Bose extendibility; instead, it was suggested to be a test for
$k$-extendibility. Thus, our observation here (also made earlier by [58]) is
that the test proposed in [45, 46] is actually a test for $k$-Bose
extendibility, and we consider in the next section a true test for
$k$-extendibility. The main results of [45, 46] were the computational
complexity of the circuit version of the separability problem, and so the
precise kind of test used was not particularly important there.

###  IV.4 $k$-Extendibility test for bipartite states

In this section, we discuss how the test for $G$-symmetric extendibility from
Section III.4 can realize a test for $k$-extendibility of a bipartite state.
Due to the known connections between $k$-extendibility and separability [23,
7, 8, 12], this test is an indirect test for separability of a bipartite
state. Since every separable state is $k$-Bose extendible, as discussed in
Section IV.3, and every $k$-Bose extendible state is $k$-extendible, it
follows that every separable state is $k$-extendible.

By making the identifications discussed in Example II.1, it follows from
Theorem III.4 that the test from Section III.4 is a test for
$k$-extendibility. For an input state $\rho_{AB}$, the acceptance probability
of Algorithm 4 is equal to the maximum $k$-extendible fidelity

$\max_{\omega_{AB}\in k\text{-E}}F(\rho_{AB},\omega_{AB}),$ (92)

where $k$-E denotes the set of $k$-extendible states, as defined in Example
II.1.

As far as we are aware, this quantum computational test for $k$-extendibility
is original to this paper, however inspired by the approach from [45, 46]. It
was argued in [45, 46] that the acceptance probability of the test there is
bounded from above by the maximum $k$-extendible fidelity, which is consistent
with the fact that the set of $k$-Bose extendible states is contained in the
set of $k$-extendible states and our observation here that the acceptance
probability of the test in [45, 46] is equal to the maximum $k$-Bose
extendible fidelity.

###  IV.5 Extendibility tests for multipartite states

We discuss briefly how the tests from Sections III.3 and III.4 apply to the
multipartite case, using identifications similar to those in (84)–(87).

First, let us recall the definition of multipartite extendibility [32]. Let
$\sigma_{A_{1}\cdots A_{m}}$ be a multipartite state. Such a state is
$(k_{1},\ldots,k_{m})$-extendible if there exists a state
$\omega_{A_{1,1}\cdots A_{1,k_{1}}\cdots A_{m,1}\cdots A_{m,k_{m}}}$ such that

$\sigma_{A_{1}\cdots A_{m}}=\\\ \operatorname{Tr}_{A_{1,2}\cdots
A_{1,k_{1}}\cdots A_{m,2}\cdots A_{m,k_{m}}}[\omega_{A_{1,1}\cdots
A_{1,k_{1}}\cdots A_{m,1}\cdots A_{m,k_{m}}}]$ (93)

and

$\omega_{A_{1,1}\cdots A_{1,k_{1}}\cdots A_{m,1}\cdots A_{m,k_{m}}}\\\
=W_{{}_{A_{1,1}\cdots A_{1,k_{1}}\cdots A_{m,1}\cdots
A_{m,k_{m}}}}^{\mathbf{\pi}}\omega_{A_{1,1}\cdots A_{1,k_{1}}\cdots
A_{m,1}\cdots A_{m,k_{m}}}\times\\\ (W_{{}_{A_{1,1}\cdots A_{1,k_{1}}\cdots
A_{m,1}\cdots A_{m,k_{m}}}}^{\mathbf{\pi}})^{{\dagger}},$ (94)

for all $\mathbf{\pi}$, where $\mathbf{\pi}=(\pi_{1},\ldots,\pi_{m})\in
S_{k_{1}}\times\cdots\times S_{k_{m}}$ and

$W_{{}_{A_{1,1}\cdots A_{1,k_{1}}\cdots A_{m,1}\cdots
A_{m,k_{m}}}}^{\mathbf{\pi}}\coloneqq\bigotimes\limits_{i=1}^{m}W_{A_{i,1}\cdots
A_{i,k_{i}}}^{\pi_{i}}.$ (95)

A multipartite state is $(k_{1},\ldots,k_{m})$-Bose extendible if there exists
a state $\omega_{A_{1,1}\cdots A_{1,k_{1}}\cdots A_{m,1}\cdots A_{m,k_{m}}}$
such that (93) holds and

$\omega_{A_{1,1}\cdots A_{1,k_{1}}\cdots A_{m,1}\cdots A_{m,k_{m}}}=\\\
\Pi_{A_{1,1}\cdots A_{1,k_{1}}\cdots A_{m,1}\cdots
A_{m,k_{m}}}\omega_{A_{1,1}\cdots A_{1,k_{1}}\cdots A_{m,1}\cdots
A_{m,k_{m}}}\\\ \times\Pi_{A_{1,1}\cdots A_{1,k_{1}}\cdots A_{m,1}\cdots
A_{m,k_{m}}},$ (96)

where

$\displaystyle\Pi_{A_{1,1}\cdots A_{1,k_{1}}\cdots A_{m,1}\cdots A_{m,k_{m}}}$
$\displaystyle\coloneqq\bigotimes\limits_{i=1}^{m}\Pi_{A_{i,1}\cdots
A_{i,k_{i}}}^{\operatorname{Sym}},$ (97) $\displaystyle\Pi_{A_{i,1}\cdots
A_{i,k_{i}}}^{\operatorname{Sym}}$
$\displaystyle\coloneqq\frac{1}{k_{i}!}\sum_{\pi_{i}\in
S_{k_{i}}}W_{A_{i,1}\cdots A_{i,k_{i}}}^{\pi_{i}}.$ (98)

By making the identifications

$\displaystyle S$ $\displaystyle\leftrightarrow A_{1,1}\cdots A_{m,1},$ (99)
$\displaystyle R$ $\displaystyle\leftrightarrow A_{1,2}\cdots
A_{1,k_{1}}\cdots A_{m,2}\cdots A_{m,k_{m}}$ (100) $\displaystyle U_{S}(g)$
$\displaystyle\leftrightarrow\bigotimes\limits_{i=1}^{m}W_{A_{i,1}\cdots
A_{i,k_{i}}}(\pi_{i})$ (101) $\displaystyle G$ $\displaystyle\leftrightarrow
S_{k_{1}}\times\cdots\times S_{k_{m}},$ (102) $\displaystyle g$
$\displaystyle\leftrightarrow(\pi_{1},\ldots,\pi_{m}),$ (103)

it follows that Algorithm 3 is a test for multipartite
$(k_{1},\ldots,k_{m})$-Bose extendibility of a state $\rho_{A_{1}\cdots
A_{m}}$, with acceptance probability equal to

$\max_{\omega_{A_{1}\cdots
A_{m}}\in(k_{1},\ldots,k_{m})\text{-BE}}F(\rho_{A_{1}\cdots
A_{m}},\omega_{A_{1}\cdots A_{m}}),$ (104)

and Algorithm 4 is a test for multipartite
$(k_{1},\ldots,k_{m})$-extendibility of a state $\rho_{A_{1}\cdots A_{m}}$,
with acceptance probability equal to

$\max_{\omega_{A_{1}\cdots
A_{m}}\in(k_{1},\ldots,k_{m})\text{-E}}F(\rho_{A_{1}\cdots
A_{m}},\omega_{A_{1}\cdots A_{m}}),$ (105)

where $(k_{1},\ldots,k_{m})$-BE and $(k_{1},\ldots,k_{m})$-E denote the sets
of $(k_{1},\ldots,k_{m})$-Bose extendible and
$(k_{1},\ldots,k_{m})$-extendible states, respectively.

###  IV.6 Testing covariance symmetry of a quantum channel

We can also use the test from Algorithm 2 to test for covariance symmetry of a
quantum channel. Before stating it, let us recall the notion of a covariant
channel [47]. Let $G$ be a group and let $\\{U_{A}(g)\\}_{g\in G}$ and
$\\{V_{B}(g)\\}_{g\in G}$ denote projective unitary representations of $G$. A
channel $\mathcal{N}_{A\rightarrow B}$ is covariant if the following
$G$-covariance symmetry condition holds

$\mathcal{N}_{A\rightarrow
B}\circ\mathcal{U}_{A}(g)=\mathcal{V}_{B}(g)\circ\mathcal{N}_{A\rightarrow
B}\qquad\forall g\in G,$ (106)

where the unitary channels $\mathcal{U}_{A}(g)$ and $\mathcal{V}_{B}(g)$ are
respectively defined from $U_{A}(g)$ and $V_{B}(g)$ as

$\displaystyle\mathcal{U}_{A}(g)(\omega_{A})$ $\displaystyle\coloneqq
U_{A}(g)\omega_{A}U_{A}(g)^{{\dagger}},$ (107)
$\displaystyle\mathcal{V}_{B}(g)(\tau_{B})$ $\displaystyle\coloneqq
V_{B}(g)\tau_{B}V_{B}(g)^{{\dagger}}.$ (108)

It is well known that a channel is covariant in the sense above if and only if
its Choi state is invariant in the following sense [19, Eq. (59)]:

$\Phi_{RB}^{\mathcal{N}}=(\overline{\mathcal{U}}_{R}(g)\otimes\mathcal{V}_{B}(g))(\Phi_{RB}^{\mathcal{N}})\quad\forall
g\in G,$ (109)

where

$\overline{\mathcal{U}}_{R}(g)(\omega_{R})\coloneqq\overline{U}_{R}(g)\omega_{R}U_{R}(g)^{T},$
(110)

and the superscript $T$ indicates the transpose. Also, the Choi state
$\Phi_{RB}^{\mathcal{N}}$ is defined as

$\displaystyle\Phi_{RB}^{\mathcal{N}}$
$\displaystyle\coloneqq\mathcal{N}_{A\rightarrow B}(\Phi_{RA}),$ (111)
$\displaystyle\Phi_{RA}$
$\displaystyle\coloneqq\frac{1}{\left|A\right|}\sum_{i,j}|i\rangle\\!\langle
j|_{R}\otimes|i\rangle\\!\langle j|_{A}.$ (112)

Suppose then that a circuit is available that generates the channel
$\mathcal{N}_{A\rightarrow B}$. Similar to the first assumption in Section
III, we suppose that the circuit realizes a unitary channel
$\mathcal{W}_{AE^{\prime}\rightarrow BE}$ that extends the original channel,
in the sense that

$\mathcal{N}_{A\rightarrow
B}(\omega_{A})=(\operatorname{Tr}_{E}\circ\mathcal{W}_{AE^{\prime}\rightarrow
BE})(\omega_{A}\otimes|0\rangle\\!\langle 0|_{E^{\prime}}).$ (113)

Then to decide whether the channel is covariant, we send in one share of a
maximally entangled state to the unitary extension channel, such that the
overall state is

$\mathcal{W}_{AE^{\prime}\rightarrow BE}(\Phi_{RA}\otimes|0\rangle\\!\langle
0|_{E^{\prime}}).$ (114)

Now making the identifications

$\displaystyle E$ $\displaystyle\leftrightarrow S^{\prime},$ (115)
$\displaystyle RB$ $\displaystyle\leftrightarrow S,$ (116)
$\displaystyle\overline{U}_{R}(g)\otimes V_{B}(g)$
$\displaystyle\leftrightarrow U_{S}(g),$ (117)

we apply Algorithm 2, and as a consequence of Theorem III.2, the acceptance
probability is equal to

$\max_{\sigma_{RB}\in\operatorname{Sym}_{G}}F(\Phi_{RB}^{\mathcal{N}},\sigma_{RB}),$
(118)

where

$\operatorname{Sym}_{G}\coloneqq\left\\{\begin{array}[c]{c}\sigma_{RB}\in\mathcal{D}(\mathcal{H}_{RB}):\\\
\sigma_{RB}=(\overline{\mathcal{U}}_{R}(g)\otimes\mathcal{V}_{B}(g))(\sigma_{RB})\
\forall g\in G\end{array}\right\\}.$ (119)

Thus, the test accepts with probability equal to one if and only if the
channel is covariant in the sense of (106).

We note here that a special kind of channel is a unitary channel induced by
Hamiltonian evolution (i.e., $\mathcal{N}(\cdot)=e^{-iHt}(\cdot)e^{iHt}$,
where $H$ is the Hamiltonian and $t$ is the evolution time). This special case
was considered in [56], in which channel symmetry tests were employed as
Hamiltonian symmetry tests.

###  IV.7 Testing covariance symmetry of a quantum measurement

Recall that a quantum measurement is described by a positive operator-valued
measure (POVM), which is a set
$\Lambda\coloneqq\\{\Lambda^{x}\\}_{x\in\mathcal{X}}$ of positive semi-
definite operators such that $\sum_{x\in\mathcal{X}}\Lambda^{x}=I$. From this
set, we can define a quantum measurement channel as follows:

$\mathcal{M}_{S\rightarrow
X}(\rho_{S})\coloneqq\sum_{x\in\mathcal{X}}\operatorname{Tr}[\Lambda_{S}^{x}\rho_{S}]|x\rangle\\!\langle
x|_{X},$ (120)

where $\\{|x\rangle_{X}\\}_{x\in\mathcal{X}}$ is an orthonormal basis.

A POVM is $G$-symmetric (also called group covariant) if there exists a
projective unitary representation $\left\\{U(g)\right\\}_{g\in G}$ of a group
$G$ such that

$U(g)^{{\dagger}}\Lambda^{x}U(g)\in\Lambda\quad\forall g\in
G,\,x\in\mathcal{X}.$ (121)

$G$-symmetric POVMs have been studied extensively in the literature [27, 48,
20, 29], and they arise in many applications, having to do with state
discrimination [51] and estimation [18]. It is thus of interest to determine
whether a given POVM is $G$-symmetric.

Connecting to the previous section, a measurement channel
$\mathcal{M}_{S\rightarrow X}$ is $G$-symmetric if there exists projective
unitary representations $\left\\{U(g)\right\\}_{g\in G}$ and
$\left\\{W(g)\right\\}_{g\in G}$ such that

$\mathcal{M}_{S\rightarrow
X}\circ\mathcal{U}(g)=\mathcal{W}(g)\circ\mathcal{M}_{S\rightarrow
X}\quad\forall g\in G.$ (122)

Plugging into (120), the condition in (122) becomes

$\sum_{x\in\mathcal{X}}\operatorname{Tr}[U(g)^{{\dagger}}\Lambda^{x}U(g)\rho_{S}]|x\rangle\\!\langle
x|_{X}\\\
=\sum_{x\in\mathcal{X}}\operatorname{Tr}[\Lambda_{S}^{x}\rho_{S}]W(g)|x\rangle\\!\langle
x|_{X}W(g)^{{\dagger}}\quad\forall g\in G.$ (123)

Since the output system $X$ is classical, it is sensible to restrict the
unitary $W(g)$ to be a shift operator that realizes a permutation $\pi_{g}$ of
the classical letter $x$, so that we can write

$\displaystyle\sum_{x\in\mathcal{X}}\operatorname{Tr}[U(g)^{{\dagger}}\Lambda^{x}U(g)\rho_{S}]|x\rangle\\!\langle
x|_{X}$
$\displaystyle=\sum_{x\in\mathcal{X}}\operatorname{Tr}[\Lambda_{S}^{x}\rho_{S}]|\pi_{g}(x)\rangle\\!\langle\pi_{g}(x)|_{X}$
(124)
$\displaystyle=\sum_{x\in\mathcal{X}}\operatorname{Tr}[\Lambda_{S}^{\pi_{g}^{-1}(x)}\rho_{S}]|x\rangle\\!\langle
x|_{X}.$ (125)

Since this equation holds for every input state $\rho$, we conclude that the
following condition holds for a $G$-symmetric measurement channel:

$U(g)^{{\dagger}}\Lambda^{x}U(g)=\Lambda_{S}^{\pi_{g}^{-1}(x)}\quad\forall
g\in G,\ x\in\mathcal{X},$ (126)

coinciding with the definition given in (121).

As a consequence of the connection between (122) and the definition in (121),
we can use the methods from the previous section to test whether a POVM is
$G$-symmetric. Recall that the Choi state of a measurement channel has the
following form (see, e.g., [54, Eq. (3.2.162)]):

$\Phi_{RX}^{\mathcal{M}}\coloneqq\mathcal{M}_{S\rightarrow
X}(\Phi_{RS})=\frac{1}{\left|\mathcal{X}\right|}\sum_{x\in\mathcal{X}}\left(\Lambda_{R}^{x}\right)^{T}\otimes|x\rangle\\!\langle
x|_{X}.$ (127)

By appealing to (109), (122), and (126), it follows that a POVM is
$G$-symmetric if and only if its Choi state is $G$-symmetric in the following
sense:

$(\overline{\mathcal{U}}_{R}(g)\otimes\mathcal{W}_{X}(g))(\Phi_{RX}^{\mathcal{M}})=\Phi_{RX}^{\mathcal{M}}\quad\forall
g\in G,$ (128)

or equivalently, if

$\frac{1}{\left|\mathcal{X}\right|}\sum_{x\in\mathcal{X}}\left[\mathcal{U}_{R}(g)(\Lambda_{R}^{x})\right]^{T}\otimes|\pi_{g}(x)\rangle\\!\langle\pi_{g}(x)|_{X}\\\
=\frac{1}{\left|\mathcal{X}\right|}\sum_{x\in\mathcal{X}}\left(\Lambda_{R}^{x}\right)^{T}\otimes|x\rangle\\!\langle
x|_{X}\qquad\forall g\in G.$ (129)

One method for performing a measurement on a quantum system $S$ is to employ a
unitary circuit $U_{SX}$ acting on the system $S$ and a probe system $X$
prepared in the state $|0\rangle\\!\langle 0|_{X}$ (see, e.g., [54, Figure
3.1]). This is then followed by a projective measurement
$\\{|x\rangle\\!\langle x|_{X}\\}_{x\in\mathcal{X}}$ in the standard basis of
the probe system $X$. To realize this process in a fully unitary manner, we
can attach two probe systems $X$ and $X^{\prime}$ to the system $S$, prepared
in the state $|0\rangle\\!\langle 0|_{X}\otimes|0\rangle\\!\langle
0|_{X^{\prime}}$, perform the unitary $U_{SX}$, followed by generalized
controlled-NOT gates from $X$ to $X^{\prime}$. If we send in one share $S$ of
a maximally entangled state $\Phi_{RS}$, the resulting state is

$C_{XX^{\prime}}U_{SX}\left(\Phi_{RS}\otimes|0\rangle\\!\langle
0|_{X}\otimes|0\rangle\\!\langle
0|_{X^{\prime}}\right)U_{SX}^{{\dagger}}C_{XX^{\prime}}^{{\dagger}},$ (130)

where $C_{XX^{\prime}}$ denotes the generalized CNOT gate, defined through
$C_{XX^{\prime}}|x\rangle_{X}|0\rangle_{X^{\prime}}=|x\rangle_{X}|x\rangle_{X^{\prime}}$.
Tracing over systems $S$ and $X^{\prime}$, the resulting state is the Choi
state of the measurement channel, as given in (127). Thus, by making the
identifications

$\displaystyle SX^{\prime}$ $\displaystyle\leftrightarrow S^{\prime},$ (131)
$\displaystyle RX$ $\displaystyle\leftrightarrow S,$ (132)
$\displaystyle\overline{\mathcal{U}}_{R}(g)\otimes\mathcal{W}_{X}(g)$
$\displaystyle\leftrightarrow U_{S}(g),$ (133)

we apply Algorithm 2, and as a consequence of Theorem III.2, the acceptance
probability is equal to

$\max_{\sigma_{RX}\in\text{Sym}_{G}}F(\Phi_{RX}^{\mathcal{M}},\sigma_{RX}),$
(134)

where

$\text{Sym}_{G}\coloneqq\left\\{\begin{array}[c]{c}\sigma_{RX}\in\mathcal{D}(\mathcal{H}_{RX}):\\\
\sigma_{RX}=(\overline{\mathcal{U}}_{R}(g)\otimes\mathcal{W}_{X}(g))(\sigma_{RX})\
\forall g\in G\end{array}\right\\}.$ (135)

Thus, the test accepts with probability equal to one if and only if the POVM
is $G$-symmetric, as defined in (121). Finally, we remark that it suffices to
restrict the optimization over $\sigma_{RX}$ to be over quantum-classical
states of the form
$\sigma_{RX}=\sum_{x\in\mathcal{X}}\tilde{\sigma}_{R}^{x}\otimes|x\rangle\\!\langle
x|_{X}$, where each $\tilde{\sigma}_{R}^{x}$ is positive semi-definite and
$\sum_{x\in\mathcal{X}}\operatorname{Tr}[\tilde{\sigma}_{R}^{x}]=1$. This
follows because the Choi state $\Phi_{RX}^{\mathcal{M}}$ is quantum-classical
(and thus invariant under such a dephasing), and the fidelity does not
decrease under the action of a completely-dephasing channel on the classical
system $X$. It thus suffices to optimize over quantum-classical $\sigma_{RX}$
satisfying

$\sum_{x\in\mathcal{X}}\tilde{\sigma}_{R}^{x}\otimes|x\rangle\\!\langle
x|_{X}=\sum_{x\in\mathcal{X}}\overline{\mathcal{U}}_{R}(g)(\tilde{\sigma}_{R}^{x})\otimes|\pi_{g}(x)\rangle\\!\langle\pi_{g}(x)|_{X}\,,$
(136)

for all $g\in G$, or equivalently,
$\tilde{\sigma}_{R}^{\pi_{g}(x)}=\overline{\mathcal{U}}_{R}(g)(\tilde{\sigma}_{R}^{x})$
for all $x\in\mathcal{X}$ and $g\in G$.

##  V Semi-definite programs for maximum symmetric fidelities

In this section, we note that the acceptance probabilities of Algorithms 1–4
can be computed by means of semi-definite programming (see [16, 77, 54] for
reviews). This is useful for comparing the true values of the acceptance
probabilities of Algorithms 1–4 to estimates formed from executing them on
near-term quantum computers; however, this semi-definite programming approach
only works well in practice if the circuit $U^{\rho}$ acts on a small number
of qubits. This limitation holds because the semi-definite programs (SDPs) run
in a time polynomial in the dimension of the states involved, but the
dimension of a state grows exponentially with the number of qubits involved.

We note that the fact that the acceptance probabilities of Algorithms 1–4 can
be computed by semi-definite programming follows from a more general fact that
the acceptance probability of a QIP(2) algorithm can be computed in this
manner [75, 73]; however, it is helpful to have the explicit form of the SDPs
available.

We now list the SDPs for the acceptance probabilities of Algorithms 1–4. To
begin with, let us note that the acceptance probability of Algorithm 1 is
equal to $\operatorname{Tr}[\Pi_{S}^{G}\rho_{S}]$, and so there is no need for
an optimization. This quantity can be calculated directly if the projection
matrix $\Pi_{S}^{G}$ and the density matrix $\rho_{S}$ are available.
Alternatively, one could employ an optimization as given below. Let us first
note that the root fidelity of states $\omega$ and $\tau$ can be calculated by
the following SDP [76]:

$\sqrt{F}(\omega,\tau)=\max_{X\in\mathcal{L}(\mathcal{H})}\left\\{\operatorname{Tr}[\operatorname{Re}[X]]:\begin{bmatrix}\omega&X^{{\dagger}}\\\
X&\tau\end{bmatrix}\geq 0\right\\},$ (137)

where $\mathcal{L}(\mathcal{H})$ is the space of linear operators acting on
the Hilbert space $\mathcal{H}$. Each of the sets $\text{B-Sym}_{G}$,
$\operatorname*{Sym}_{G}$, $\operatorname*{BSE}_{G}$, and
$\operatorname*{SymExt}_{G}$ are specified by semi-definite constraints. Thus,
combining the optimization in (137) with various constraints, we find that the
acceptance probabilities of Algorithms 1–4 can be calculated by using the
following SDPs, respectively:

$\max_{\sigma_{S}\in\text{B-Sym}_{G}}\sqrt{F}(\rho_{S},\sigma_{S})\\\
=\max_{\begin{subarray}{c}X\in\mathcal{L}(\mathcal{H}_{S}),\\\ \sigma_{S}\geq
0\end{subarray}}\left\\{\begin{array}[c]{c}\operatorname{Tr}[\operatorname{Re}[X]]:\\\
\begin{bmatrix}\rho_{S}&X^{{\dagger}}\\\ X&\sigma_{S}\end{bmatrix}\geq 0,\\\
\operatorname{Tr}[\sigma_{S}]=1,\\\
\sigma_{S}=\Pi^{G}_{S}\sigma_{S}\Pi^{G}_{S}\end{array}\right\\},$ (138)
$\max_{\sigma_{S}\in\operatorname*{Sym}_{G}}\sqrt{F}(\rho_{S},\sigma_{S})\\\
=\max_{\begin{subarray}{c}X\in\mathcal{L}(\mathcal{H}_{S}),\\\ \sigma_{S}\geq
0\end{subarray}}\left\\{\begin{array}[c]{c}\operatorname{Tr}[\operatorname{Re}[X]]:\\\
\begin{bmatrix}\rho_{S}&X^{{\dagger}}\\\ X&\sigma_{S}\end{bmatrix}\geq 0,\\\
\operatorname{Tr}[\sigma_{S}]=1,\\\
\sigma_{S}=U_{S}(g)\sigma_{S}U_{S}(g)^{{\dagger}}\ \forall g\in
G\end{array}\right\\},$ (139)
$\max_{\sigma_{S}\in\operatorname*{BSE}_{G}}\sqrt{F}(\rho_{S},\sigma_{S})\\\
=\max_{\begin{subarray}{c}X\in\mathcal{L}(\mathcal{H}_{S}),\\\ \omega_{RS}\geq
0\end{subarray}}\left\\{\begin{array}[c]{c}\operatorname{Tr}[\operatorname{Re}[X]]:\\\
\begin{bmatrix}\rho_{S}&X^{{\dagger}}\\\
X&\operatorname{Tr}_{R}[\omega_{RS}]\end{bmatrix}\geq 0,\\\
\operatorname{Tr}[\omega_{RS}]=1,\\\
\omega_{RS}=\Pi_{RS}^{G}\omega_{RS}\Pi_{RS}^{G}\end{array}\right\\},$ (140)
$\max_{\sigma_{S}\in\operatorname*{SymExt}_{G}}\sqrt{F}(\rho_{S},\sigma_{S})\\\
=\max_{\begin{subarray}{c}X\in\mathcal{L}(\mathcal{H}_{S}),\\\ \omega_{RS}\geq
0\end{subarray}}\left\\{\begin{array}[c]{c}\operatorname{Tr}[\operatorname{Re}[X]]:\\\
\begin{bmatrix}\rho_{S}&X^{{\dagger}}\\\
X&\operatorname{Tr}_{R}[\omega_{RS}]\end{bmatrix}\geq 0,\\\
\operatorname{Tr}[\omega_{RS}]=1,\\\
\omega_{RS}=U_{RS}(g)\omega_{RS}U_{RS}(g)^{{\dagger}}\ \forall g\in
G\end{array}\right\\}.$ (141)

We note here that the complexity of the SDPs in (139) and (141) can be greatly
simplified by employing basic concepts from representation theory (i.e.,
Schur’s lemma). See [69] for background on representation theory and
Propositions 4.2.2 and 4.2.3 therein for Schur’s lemma. Focusing on the SDP in
(139), it is well known that there exists a unitary $W$ that block
diagonalizes every unitary in the set $\\{U(g)\\}_{g\in G}$, as follows:

$U(g)=W\left(\bigoplus_{\lambda}I_{m_{\lambda}}\otimes
U_{\lambda}(g)\right)W^{\dagger},$ (142)

where the variable $\lambda$ labels an irreducible representation (irrep) of
$U(g)$, the matrix $I_{m_{\lambda}}$ is an identity matrix of dimension
$m_{\lambda}$, and the unitary $U_{\lambda}(g)$ is an irrep of $U(g)$ with
multiplicity $m_{\lambda}$. This same unitary $W$ induces a direct-sum
decomposition (called isotypic decomposition) of the Hilbert space
$\mathcal{H}$ for $\rho_{S}$ and $\sigma_{S}$ as follows:

$\displaystyle W^{\dagger}\mathcal{H}$
$\displaystyle=\bigoplus_{\lambda}\mathcal{H}_{\lambda},$ (143)
$\displaystyle\mathcal{H}_{\lambda}$
$\displaystyle\coloneqq\mathbb{C}^{m_{\lambda}}\otimes\mathcal{K}_{\lambda},$
(144)

where $\mathcal{H}_{\lambda}$ is the space on which $I_{m_{\lambda}}\otimes
U_{\lambda}(g)$ acts and $\mathcal{K}_{\lambda}$ is the factor on which
$U_{\lambda}(g)$ acts. Noting that the condition

$\sigma_{S}=U_{S}(g)\sigma_{S}U_{S}(g)^{{\dagger}}\qquad\forall g\in G$ (145)

is equivalent to

$\sigma_{S}=\mathcal{T}_{G}(\sigma_{S}),$ (146)

where the group twirl channel is defined as

$\mathcal{T}_{G}(\cdot)\coloneqq\frac{1}{|G|}\sum_{g\in
G}U_{S}(g)(\cdot)U_{S}(g)^{\dagger},$ (147)

it then follows from (142) and Schur’s lemma that the twirl channel
$\mathcal{T}_{G}$ has the following form (see page 8 of [15]):

$\mathcal{T}_{G}(\cdot)=\mathcal{W}\circ\left(\sum_{\lambda}(\operatorname{id}_{m_{\lambda}}\otimes\mathcal{D}_{\lambda})\circ\mathcal{P}_{\lambda}\right)\circ\mathcal{W}^{\dagger},$
(148)

where $\mathcal{W}(\cdot)\coloneqq W(\cdot)W^{\dagger}$, the map
$\mathcal{P}_{\lambda}$ projects onto $\mathcal{H}_{\lambda}$ (i.e.,
$\mathcal{P}_{\lambda}(\cdot)\coloneqq\Pi_{\lambda}(\cdot)\Pi_{\lambda}$, with
$\Pi_{\lambda}$ the projection onto $\mathcal{H}_{\lambda}$), the map
$\operatorname{id}_{m_{\lambda}}$ denotes the identity channel acting on the
multiplicity space, and $\mathcal{D}_{\lambda}$ denotes a completely
depolarizing channel with the action
$\mathcal{D}_{\lambda}(\cdot)\coloneqq\operatorname{Tr}[\cdot]\pi_{\lambda}$,
with $\pi_{\lambda}\coloneqq I_{d_{\lambda}}/d_{\lambda}$ and $d_{\lambda}$
the dimension of $\mathcal{K}_{\lambda}$. The effect of the twirl
$\mathcal{T}_{G}$ on a general input $\sigma$ is then

$\mathcal{T}_{G}(\sigma)=W\left(\bigoplus_{\lambda}\operatorname{Tr}_{2}[\Pi_{\lambda}W^{\dagger}\sigma
W\Pi_{\lambda}]\otimes\pi_{\lambda}\right)W^{\dagger}.$ (149)

It then follows that every state satisfying (146) has the following form:

$\sigma_{S}=W\left(\bigoplus_{\lambda}\tilde{\sigma}_{\lambda}\otimes\pi_{\lambda}\right)W^{\dagger},$
(150)

where $\\{\tilde{\sigma}_{\lambda}\\}_{\lambda}$ is a set of positive semi-
definite operators such that
$\sum_{\lambda}\operatorname{Tr}[\tilde{\sigma}_{\lambda}]=1$. Thus, when
performing the optimization in (139), it suffices to find the diagonalizing
unitary $W$ for the representation $\\{U(g)\\}_{g\in G}$ (for which an
algorithm is known [1, Section 9.2.5]) and then optimize over the set
$\\{\tilde{\sigma}_{\lambda}\\}_{\lambda}$, thus greatly reducing the space
over which the optimization needs to be conducted. This kind of reduction was
recently exploited in [37], and a Matlab toolbox was provided in [65]. We note
that we can employ similar reasoning to simplify the optimization in (141).

It also follows from Schur’s lemma that the group projection $\Pi^{G}_{S}$ has
the following form [26, Eqs. (1)–(2)]:

$\displaystyle\Pi^{G}_{S}$
$\displaystyle=W\left(\bigoplus_{\lambda}\delta_{\lambda,\lambda_{t}}I_{m_{\lambda}}\otimes
I_{d_{\lambda}}\right)W^{\dagger},$ (151)
$\displaystyle=W\Pi_{\lambda_{t}}W^{{\dagger}},$ (152)

where $\lambda_{t}$ is the irrep for the trivial representation of
$\\{U_{S}(g)\\}_{g\in G}$. Noting that $d_{\lambda_{t}}=1$ for this irrep, it
follows that $\Pi_{\lambda_{t}}$ acts as $I_{m_{\lambda}}$ on this subspace.
Thus, in the optimization in (138), it follows that every state $\sigma_{S}$
satisfying $\sigma_{S}=\Pi^{G}_{S}\sigma_{S}\Pi^{G}_{S}$ has the following
form:

$W\sigma_{\lambda_{t}}W^{\dagger},$ (153)

where $\sigma_{\lambda_{t}}$ is a state with support only in the space
$\mathcal{H}_{\lambda_{t}}$, i.e., satisfying
$\sigma_{\lambda_{t}}=\Pi_{\lambda_{t}}\sigma_{\lambda_{t}}\Pi_{\lambda_{t}}$.
In this way, we can simplify the optimization task in (138). We finally note
that we can employ similar reasoning to simplify the optimization in (141).

##  VI Variational algorithms for testing symmetry

Having established that the acceptance probabilities can be computed by SDPs
for circuits on a sufficiently small number of qubits, we now propose
variational quantum algorithms (VQA) for use on quantum computers (see [17, 5]
for reviews of variational quantum algorithms). These algorithms make use of
variational machine learning techniques to mimic the action of the prover in
Algorithms 2–4; however, these techniques are in general limited in terms of
their capabilities and thus do not fully satisfy the all-powerful nature of
the prover called for in quantum interactive proofs. Note also that training a
VQA has been shown to be NP-hard [13]; nonetheless, implementing such methods
on near-term quantum devices gives a rough lower bound on the quantities of
interest. We present here a series of examples and show the circuit diagrams
and VQA performance for these tests. To demonstrate the wide-ranging
applicability of these algorithms, we have performed symmetry tests for a
variety of groups. We present a subset of them now and defer the rest of them
to Appendices D through F in the interest of space.

For the algorithms discussed in this section, all code was implemented in
Python using Qiskit (a Python package used for quantum computing with IBM
Quantum). For each algorithm, the noiseless variant was implemented using the
IBM Quantum noiseless simulator. For the noisy versions, we use the noise
model from the IBM-Jakarta quantum computer and conduct a noisy simulation. We
find that the algorithms behave well in both scenarios. In the noisy
simulations, the algorithms converge well, and the parameters obtained exhibit
a noise resilience as put forward in [68]; that is, the relevant quantity can
be accurately estimated by inputting the parameters learned from the noisy
simulator into the noiseless simulator. Note that some sections show only a
noiseless simulation; for these cases, the noisy simulation requires a noise
model of a larger quantum system than is currently available to us.

As with many VQAs, it is necessary in these simulations to endeavor to avoid
the barren plateau problem, in which global cost functions become untrainable.
The algorithms specified in Section III rely solely on local measurements
alone in the regime in which the number of data qubits is much larger than the
number of control qubits and thus should not suffer from this issue in this
regime [24]. However, we have only considered simulations of small quantum
systems; it remains open to provide evidence that our algorithms will avoid
the barren plateau problem for larger systems.

In what follows, we consider several groups and their unitary representations
and test states for $G$-Bose symmetry, $G$-symmetry, $G$-Bose symmetric
extendibility, and $G$-symmetric extendibility. We also test for two- and
three-extendibility.

###  VI.1 $\mathbb{Z}_{2}$ Group

Figure 10: Symmetry tests for the $\mathbb{Z}_{2}$ group: a) $G$-Bose symmetry
and b) $G$-symmetry.

In order to test membership in $\operatorname{Sym}_{G}$, a group with an
established unitary representation is needed. One somewhat trivial, albeit
easily testable, example is the group generated by the identity and the Pauli
$Z$ gate. The group table for the $\mathbb{Z}_{2}$ group is given by

Group element |  $e$ |  $g$
---|---|---
$e$ |  $e$ |  $g$
$g$ |  $g$ |  $e$

where $e$ denotes the identity element. The $\mathbb{Z}_{2}$ group has a
simple one-qubit unitary representation $\\{e\rightarrow I,g\rightarrow Z\\}$.
Since $\mathbb{Z}_{2}$ has two elements, the $|+\rangle_{C}$ state is a
uniform superposition of two elements. Thus, we use one qubit and the Hadamard
gate to generate the necessary state:

$H|0\rangle=\frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right).$ (154)

The control register states need to be mapped to group elements. We employ the
mapping $\\{|0\rangle\rightarrow e,|1\rangle\rightarrow g\\}$ for our circuit
constructions.

####  VI.1.1 $G$-Bose symmetry

We begin with a test for Bose symmetry, which in this case is a test whether
the state is equal to $|0\rangle\\!\langle 0|$, because the group projector
$\Pi^{\mathbb{Z}_{2}}_{S}=(I+Z)/2=|0\rangle\\!\langle 0|$. Calculation by hand
or classical computation can easily verify whether a state is Bose symmetric
with respect to $I$ and $Z$. Additionally, this simple gate set can be easily
implemented on noisy intermediate-scale quantum computers.

Figure 10a) shows the circuit that tests for this $G$-Bose symmetry. Table 2
shows the results for various input states. The true fidelity value is
calculated using (36), where $\Pi^{G}_{S}$ is defined in (19).

State |  True Fidelity |  Noiseless |  Noisy
---|---|---|---
$|0\rangle\\!\langle 0|$ |  1 |  1.0 |  0.9998
$|1\rangle\\!\langle 1|$ |  0 |  0.0 |  0.0013
$|+\rangle\\!\langle+|$ |  0.5 |  0.5 |  0.5002
$\mathbb{I}/2$ |  0.5 |  0.5 |  0.5092
Table 2: Results of $Z_{2}$-Bose symmetry tests.

####  VI.1.2 $G$-symmetry

We now consider a simple test for $G$-symmetry. As mentioned in Remark 1, this
is also a test for incoherence of the input state, i.e., to determine if it is
diagonal in the computational basis. In the circuit depicted in Figure 10b), a
parameterized circuit substitutes the role of an all-powerful prover.

A circuit that tests for $G$-symmetry is shown in Figure 10b). As this circuit
involves variational parameters, an example of the training process is shown
in Figure 11. Table 3 shows the final results after training for various input
states. The true fidelity is calculated using the semi-definite program given
in (139) and is used as a comparison point.

Figure 11: Example of the training process for testing $\mathbb{Z}_{2}$-symmetry of $\rho=\mathbb{I}/2$. We see that the training exhibits a noise resilience. State |  True Fidelity |  Noiseless |  Noisy |  Noise Resilient
---|---|---|---|---
$|0\rangle\\!\langle 0|$ |  1 |  0.9999 |  0.9987 |  0.9999
$|1\rangle\\!\langle 1|$ |  1 |  1.0 |  1.0 |  0.9999
$|+\rangle\\!\langle+|$ |  0.5 |  0.5 |  0.5087 |  0.5
$\mathbb{I}/2$ |  1 |  0.9999 |  0.9932 |  0.9999
Table 3: Results of $Z_{2}$-symmetry tests.

###  VI.2 Triangular dihedral group $D_{3}$

####  VI.2.1 $G$-Bose symmetry

Throughout Section III, we have used the dihedral group of the equilateral
triangle, abbreviated as $D_{3}$, as an example, and we continue to do so now.
As a reminder, this group is generated by a flip of order two and a rotation
of order three (denoted respectively by $f$ and $r$). Then the group is
specified as $D_{3}=\\{e,f,r,r^{2},fr,fr^{2}\\}$ where $e$ is the identity
element. General dihedral groups have previously been studied as non-abelian
groups for which a quantum algorithm to find a hidden subgroup is available
[53].

In the introduction of Section III, we provided a faithful, projective unitary
representation of this group given by letting $U(f)=\textrm{CNOT}$,
$U(r)=\textrm{CNOT}\cdot\textrm{SWAP}$, and $U(e)=\mathbb{I}_{4}$. Figure 3
shows the circuit needed to test for $G$-Bose symmetry. Note that we do not
generate the control register using a quantum Fourier transform; as the
resultant control state is still equivalent to
$|+\rangle_{C}=\frac{1}{\sqrt{6}}\sum_{g\in D_{3}}|g\rangle$, this
simplification suffices for our calculations. Table 4 shows the results for
various input states. The true fidelity value is calculated using (36), where
$\Pi^{G}_{S}$ is defined in (19).

State |  True Fidelity |  Noiseless |  Noisy
---|---|---|---
$|00\rangle\\!\langle 00|$ |  1 |  1.0000 |  0.9998
$\rho$ |  1 |  0.9999 |  0.8756
$\Phi^{+}$ |  0.6666 |  0.6666 |  0.5864
$\pi^{\otimes 2}$ |  0.5 |  0.5000 |  0.4716
Table 4: Results of $D_{3}$-Bose symmetry tests. The state $\rho$ is defined
as $|\psi\rangle\\!\langle\psi|$ where
$|\psi\rangle=\frac{1}{\sqrt{3}}(|01\rangle+|10\rangle+|11\rangle)$.

####  VI.2.2 $G$-symmetry

As with $\mathbb{Z}_{2}$, moving to $G$-symmetry requires the addition of a
prover. This alteration was already depicted in Figure 5. The prover is
replaced for practical purposes with a parameterized circuit involving
variational parameters, and the training process is shown in Figure 12. Table
5 shows the final results after training for various input states. The true
fidelity is calculated using the semi-definite program given in (139).

Figure 12: Example of the training process for testing $D_{3}$-symmetry of $\Phi^{+}$. We see that the training exhibits a noise resilience. State |  True Fidelity |  Noiseless |  Noisy |  Noise Resilient
---|---|---|---|---
$|00\rangle\\!\langle 00|$ |  1.0000 |  0.9999 |  0.9987 |  0.9999
$\rho$ |  1.0000 |  0.9999 |  0.6564 |  0.9425
$\Phi^{+}$ |  0.6666 |  0.6666 |  0.5330 |  0.6415
$\pi^{\otimes 2}$ |  1.0000 |  0.9989 |  0.5189 |  0.8712
Table 5: Results of $D_{3}$-symmetry tests. The state $\rho$ is defined as
$|\psi\rangle\\!\langle\psi|$ where
$|\psi\rangle=\frac{1}{\sqrt{3}}(|01\rangle+|10\rangle+|11\rangle)$.

####  VI.2.3 $G$-Bose symmetric extendibility

A circuit that tests for $G$-Bose symmetric extendibility was originally shown
in Figure 7 as the example circuit construction. Now, we show how that
construction behaves under a parameterized circuit substitution of the prover.
Again, we give an example of the training behavior of the algorithm in Figure
13. We also provide Table 6, which shows the final results after training for
various input states. The true fidelity is calculated using the semi-definite
program given in (140).

Figure 13: Example of the training process for testing $D_{3}$-Bose symmetric extendibility of $|1\rangle\\!\langle 1|$. We see that the training exhibits a noise resilience. State |  True Fidelity |  Noiseless |  Noisy |  Noise Resilient
---|---|---|---|---
$|0\rangle\\!\langle 0|$ |  1.0000 |  1.0000 |  0.8758 |  0.9988
$|1\rangle\\!\langle 1|$ |  0.6670 |  0.6667 |  0.5834 |  0.6663
$\pi$ |  1.0000 |  1.0000 |  0.8255 |  0.9995
$\begin{bmatrix}1/3&1/3\\\ 1/3&2/3\end{bmatrix}$ |  1.0000 |  0.9999 |  0.6564 |  0.9425
Table 6: Results of $D_{3}$-Bose symmetric extendibility tests.

####  VI.2.4 $G$-symmetric extendibility

Finally, we address the circuit in Figure 9, which gives a test for
$G$-symmetric extendibility. This final circuit has the prover performing two
actions at once—both finding the correct purification as in the case of
$G$-symmetry and creating the correct extension as in $G$-Bose symmetric
extendibility tests. Once again, the prover is replaced with a parameterized
circuit, and an example of the training process is shown in Figure 14. Table 7
shows the final results after training for various input states. The true
fidelity is calculated using the semi-definite program given in (141).

Figure 14: Example of the training process for testing $D_{3}$-symmetric extendibility of $|0\rangle\\!\langle 0|$. We see that the training exhibits a noise resilience. State |  True Fidelity |  Noiseless |  Noisy |  Noise Resilient
---|---|---|---|---
$|0\rangle\\!\langle 0|$ |  1.0000 |  0.9998 |  0.6725 |  0.9835
$|1\rangle\\!\langle 1|$ |  0.6666 |  0.6641 |  0.4476 |  0.6497
$\pi$ |  1.0000 |  0.9988 |  0.6901 |  0.9764
$\rho$ |  0.9714 |  0.9662 |  0.5593 |  0.8789
Table 7: Results of $D_{3}$-symmetric extendibility tests. The state $\rho$ is
defined as $\begin{bmatrix}0.5&-0.354i\\\ 0.354i&0.5\end{bmatrix}$.

###  VI.3 Collective $U$ group

Given an $n$-qudit state $\rho$, we wish to test if it is symmetric with
respect to the following group:

$G_{U}\coloneqq\\{U^{\otimes n}\\}_{U\in\operatorname{SU}(d)}.$ (155)

####  VI.3.1 $G$-Bose symmetry

A state that is $G_{U}$-Bose symmetric satisfies the condition given in (37),
where

$\Pi_{U}^{(n)}\coloneqq\int dU\ U^{\otimes n},$ (156)

with $dU$ being the Haar measure for the group $\operatorname{SU}(d)$.

In what follows, we focus on two-qubit states. A simple calculation shows that
for $n=2$ and $d=2$, the singlet state
$|\Psi^{-}\rangle\coloneqq\frac{1}{\sqrt{2}}\left(|01\rangle-|01\rangle\right)$,
is the only $G_{U}$-Bose symmetric state. In other words,

$\Pi^{(2)}_{U}=|\Psi^{-}\rangle\\!\langle\Psi^{-}|.$ (157)

Thus, testing for $G_{U}$-Bose symmetry is equivalent to testing if the state
is the singlet state.

To test a symmetry of this form, we rewrite the projector in terms of a set
$\\{U_{i}\\}_{i=1}^{N}$ of unitaries satisfying

$\Pi^{(2)}_{U}=\frac{1}{N}\sum\limits_{i=1}^{N}U_{i}.$ (158)

While there exist multiple choices for the set $\\{U_{i}\\}_{i=1}^{N}$, we
pick a set that is compatible with all of the symmetry tests that we perform
in the forthcoming subsections. Our choice $\\{U_{i}\\}_{i=1}^{N}$ is given in
[9, Appendix A] and is composed of products of bilateral rotations $B_{x}$,
$B_{y}$, and $B_{z}$, where

$B_{a}\coloneqq R_{a}(-\pi/2)\otimes R_{a}(-\pi/2)\,,$ (159)

and $R_{a}$ is the following rotation gate about the $a$ axis:

$\displaystyle R_{a}(\theta)$ $\displaystyle\coloneqq
e^{-i\theta\sigma_{a}/2}$ (160)
$\displaystyle=\cos(\theta/2)\mathbb{I}-i\sin(\theta/2)\sigma_{a}.$ (161)

Specifically, the set $\\{U_{i}\\}_{i}$ is given by

$\\{U_{i}\\}_{i}=\\{\mathbb{I},\ B_{x}B_{x},\ B_{y}B_{y},\ B_{z}B_{z},\
B_{x}B_{y},\ B_{y}B_{z},\\\ B_{z}B_{x},\ B_{y}B_{x},\ B_{x}B_{y}B_{x}B_{y},\
\\\ B_{y}B_{z}B_{y}B_{z},\ B_{z}B_{x}B_{z}B_{x},\ B_{y}B_{x}B_{y}B_{x}\\}.$
(162)

The set $\\{U_{i}\\}_{i}$ forms a group isomorphic to the alternating group
$A_{4}$, which is defined as the set of even permutations on four objects.
Furthermore, $A_{4}$ can be written as a product of a Klein group on four
objects $K_{4}=\\{e,a=(12)(34),b=(13)(24),c=(14)(23)\\}$ and the cyclic group
$C_{3}=\\{e,g=(123),h=(132)\\}$. In other words,

$A_{4}=K_{4}\times C_{3}.$ (163)

The Klein group $K_{4}$ can be mapped as $\\{e\rightarrow I,a\rightarrow
B_{x}B_{x},b\rightarrow B_{y}B_{y},c\rightarrow B_{z}B_{z}\\}$. Similarly, the
cyclic group can be mapped as $\\{e\rightarrow I,g\rightarrow
B_{x}B_{y},h\rightarrow B_{y}B_{x}\\}$. We use this to design our control
register and corresponding mapping there. Since we have 12 elements, the
$|+\rangle_{C}$ state is a uniform superposition of 12 elements. However, the
aforementioned decomposition allows us to split the control register into two
sets, one controlling the $K_{4}$ group and another controlling the $C_{3}$
group. We use a unary encoding for both subgroups, leading to a five-qubit
control register. The specific mapping and group assignment are as follows:

Control State |  Group Element |  Unitary Representation
---|---|---
00 000 |  $e$ |  $I$
00 100 |  $c$ |  $B_{z}B_{z}$
00 010 |  $b$ |  $B_{y}B_{y}$
00 001 |  $a$ |  $B_{x}B_{x}$
01 000 |  $g$ |  $B_{x}B_{y}$
01 100 |  $gc$ |  $B_{y}B_{z}$
01 010 |  $gb$ |  $B_{z}B_{x}$
01 001 |  $ga$ |  $B_{y}B_{x}B_{y}B_{x}$
10 000 |  $h$ |  $B_{y}B_{x}$
10 100 |  $hc$ |  $B_{y}B_{z}B_{y}B_{z}$
10 010 |  $hb$ |  $B_{x}B_{y}B_{x}B_{y}$
10 001 |  $ha$ |  $B_{z}B_{x}B_{z}B_{x}$

To generate an equal superposition of the 12 basis elements, we use the
unitary $U_{W}$ depicted in Figure 15. With this construction settled, we can
now test for symmetry with respect to this collective $U$ group.

Figure 15: Unitary $U_{W}$, with
$\theta_{1}=\theta_{3}=2\arctan\left(\frac{1}{\sqrt{2}}\right)$ and
$\theta_{2}=\pi/3$, generates the equal superposition of 12 elements given.
The circuit acting on the top two qubits generates the state
$(|00\rangle+|01\rangle+|10\rangle)/\sqrt{3}$, and the circuit acting on the
bottom three qubits generates the state
$(|000\rangle+|001\rangle+|010\rangle+|100\rangle)/\sqrt{4}$. Figure 16:
Symmetry tests for the collective-$U$ group: a) $G$-Bose symmetry, b)
$G$-symmetry, c) $G$-Bose symmetric extendible, and d) $G$-symmetric
extendible.

Figure 16a) depicts the circuit that tests for $G$-Bose symmetry. Table 8
shows the results for various input states. The true fidelity value is
calculated using (36), where $\Pi^{G}_{S}$ is defined in (19).

State |  True Fidelity |  Noiseless |  Noisy
---|---|---|---
$|00\rangle\\!\langle 00|$ |  0 |  0.0000 |  0.0459
$\rho$ |  0.6667 |  0.6667 |  0.2661
$\Psi^{+}$ |  0 |  0.0000 |  0.0389
$\Psi^{-}$ |  1.0 |  1.0000 |  0.3517
Table 8: Results of collective $U$-Bose symmetry tests. The state $\rho$ is
defined as $|\psi\rangle\\!\langle\psi|$ where
$|\psi\rangle=\frac{1}{\sqrt{3}}\left(|00\rangle-|01\rangle+|10\rangle\right)$.

####  VI.3.2 $G$-symmetry

An $n$-qudit state $\rho$ that is $G_{U}$-symmetric satisfies the following
condition:

$\rho=\int dU\ U^{\otimes n}\rho(U^{\dagger})^{\otimes n},$ (164)

where $dU$ is the Haar measure for the group $\operatorname{SU}(d)$. States
that satisfy this condition for $n=2$ are called Werner states [79], i.e.,

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

As shown in [9], for $n=2$ and $d=2$, the continuum of rotations in the
symmetry test can be replaced by a discrete sum (a two-design), as follows:

$\bar{\rho}=\frac{1}{N}\sum\limits_{i=1}^{N}U_{i}\rho U^{\dagger}_{i},$ (166)

where $\\{U_{i}\\}_{i=1}^{N}$ is the set defined in (162). A circuit that
tests for $G$-symmetry is shown in Figure 16b). It involves variational
parameters, and an example of the training process is shown in Figure 17. Note
that, as this construction requires many qubits, only noiseless simulations
results could be obtained. These results may be easily extended as access to
higher-qubit machines becomes more readily available, allowing for noisy
simulations of more complex systems. Table 9 shows the final results after
training for various input states. The true fidelity is calculated using the
semi-definite program given in (139).

Figure 17: Example of the training process for testing collective $U$-symmetry of $\rho=|\psi\rangle\\!\langle\psi|$ where $|\psi\rangle=\frac{1}{\sqrt{3}}(|00\rangle-|01\rangle+|10\rangle)$. State |  True Fidelity |  Noiseless
---|---|---
$|10\rangle\\!\langle 10|$ |  0.5000 |  0.4997
$\rho$ |  0.6667 |  0.6666
$\Psi^{+}$ |  0.3333 |  0.3332
$\pi^{\otimes 2}$ |  1.0000 |  0.9988
Table 9: Results of collective $U$-symmetry tests. The state $\rho$ is defined
as $|\psi\rangle\\!\langle\psi|$ where
$|\psi\rangle=\frac{1}{\sqrt{3}}(|00\rangle-|01\rangle+|10\rangle)$.

We note here that the $G_{U}$-symmetry test would be unaffected by redefining
the integral over all unitaries $U\in\operatorname{U}(2)$ without the
restriction to $\operatorname{SU}(2)$. However, the projector for the
$G_{U}$-Bose symmetry test would be as follows in that case:

$\Pi_{U}=\int_{U\in\operatorname{U}(2)}dU\ U\otimes U=0,$ (167)

making the test trivial. Thus, in the previous section, we chose to restrict
the group to $\operatorname{SU}(2)$ unitaries.

####  VI.3.3 $G$-Bose symmetric extendibility

A circuit that tests for $G$-Bose symmetric extendibility is shown in Figure
16c). It involves variational parameters, and an example of the training
process is shown in Figure 18. Table 10 shows the final results after training
for various input states. The true fidelity is calculated using the semi-
definite program given in (140).

Figure 18: Example of the training process for testing collective $U$-Bose symmetric extendibility of the state $\begin{bmatrix}0.93&0\\\ 0&0.07\end{bmatrix}$. State |  True Fidelity |  Noiseless
---|---|---
$|1\rangle\\!\langle 1|$ |  0.5000 |  0.5000
$\pi$ |  1.0000 |  0.9998
$\begin{bmatrix}0.93&0\\\ 0&0.07\end{bmatrix}$ |  0.7500 |  0.7499
Table 10: Results of collective $U$-Bose symmetric extendibility tests.

####  VI.3.4 $G$-symmetric extendibility

A circuit that tests for $G$-symmetric extendibility is shown in Figure 16d).
It involves variational parameters, and an example of the training process is
shown in Figure 19. Table 11 shows the final results after training for
various input states. The true fidelity is calculated using the semi-definite
program given in (141).

Figure 19: Example of the training process for testing collective $U$-symmetric extendibility of the state $\begin{bmatrix}0.95&0\\\ 0&0.05\end{bmatrix}$. State |  True Fidelity |  Noiseless
---|---|---
$|0\rangle\\!\langle 0|$ |  0.5000 |  0.4995
$\pi$ |  1.0000 |  0.9996
$\begin{bmatrix}0.95&0\\\ 0&0.05\end{bmatrix}$ |  0.7169 |  0.7095
Table 11: Results of collective $U$-symmetric extendibility tests.

These group symmetry tests have applications in the identification and
verification of Werner states, as discussed above. Current limitations include
access to higher qubit machines, but also the noisiness of these machines. Our
VQA results converge well in the noiseless case, but it is likely that noise
will only become a bigger problem as the circuit size scales up, unless
adequately addressed.

###  VI.4 Collective phase group

Figure 20: Symmetry tests for the collective phase group: a) $G$-Bose
symmetry, b) $G$-symmetry, c) $G$-Bose symmetric extendibility, and d)
G-symmetric extendibility. The unitary $U_{0}$ is defined in (188). Note that
$U_{2}=U_{0}^{\dagger}$.

Given an $n$-qubit state $\rho$, we wish to test if the state is symmetric
with respect to the following collective phase group:

$G_{z}\coloneqq\\{R_{z}(\phi)^{\otimes n}\\}_{\phi\in[0,4\pi)},$ (168)

where we recall that $R_{z}(\phi)\coloneqq\exp(-i\phi\sigma_{z}/2)$. The
interval for $\phi$ is $[0,4\pi)$ to ensure that $G_{z}$ is a group. This is a
consequence of $\operatorname{SU}(2)$ double covering $\operatorname{SO}(3)$,
implying that $R_{z}(4\pi)=\mathbb{I}$. Additionally, the Haar measure for the
group of unitaries $\\{R_{z}(\phi)\\}_{\phi\in[0,4\pi)}$ is given by

$dU=\frac{d\phi}{4\pi}.$ (169)

####  VI.4.1 $G$-Bose symmetry

A state that is $G_{z}$-Bose symmetric satisfies the condition given in (37),
where

$\Pi_{z}^{(n)}\coloneqq\frac{1}{4\pi}\int_{0}^{4\pi}R_{z}(\phi)^{\otimes
n}\,d\phi.$ (170)

Expressing $R_{z}(\phi)$ in the computational basis,

$R_{z}(\phi)=\operatorname{Diag}\left\\{\exp\\!\left(-\frac{i\phi}{2}\right),\exp\\!\left(\frac{i\phi}{2}\right)\right\\}.$
(171)

Similarly, expressing $R_{z}(\phi)^{\otimes 2}$ in the computational basis,

$R_{z}(\phi)^{\otimes
2}=\operatorname{Diag}\left\\{\exp\left(-i\phi\right),1,1,\exp\left(i\phi\right)\right\\}.$
(172)

Generalizing to the case of $n$ qubits, observe that the number of zeros in a
bit-string $x$ is $n-H(x)$ and the number of ones is $H(x)$, where $H(x)$ is
the Hamming weight of $x$. For example, $H(6)=2$ since $6_{10}\equiv 110_{2}$.
Each zero contributes a phase of $-\phi/2$ for a total of $-(n-H(x))\phi/2$,
and each one contributes a phase of $\phi/2$, for a total of $H(x)\phi/2$.
Then the overall total for the bit-string $x$ is

$-(n-H(x))\phi/2+H(x)\phi/2=(2H(x)-n)\phi/2.$ (173)

This implies that

$R_{z}(\phi)^{\otimes
n}=\operatorname{Diag}\left\\{\exp\left[\left(\frac{2H(x)-n}{2}\right)i\phi\right]_{x=0}^{2^{n}-1}\right\\},$
(174)

where $H(x)$ is the Hamming weight of $x$ written in binary. For example,

Performing the integral, we note that for $a\in\mathbb{Z}\setminus\\{0\\}$,

$\int_{0}^{4\pi}\exp\\!\left(\frac{a}{2}i\phi\right)\,d\phi=0.$ (175)

Thus, only terms satisfying $H(x)=n/2$ survive the integral. Observe then that
$\Pi_{z}^{(n)}=0$ for all odd $n$. Thus, it follows that

$\Pi_{z}^{(n)}=\begin{cases}P_{k}&\text{if }n=2k\\\
0&\text{otherwise},\end{cases}$ (176)

where $P_{k}$ is defined as the projector onto the subspace of computational
basis elements with Hamming weight $k$. As an example, for $n=2$,

$\Pi_{z}^{(2)}=P_{1}=|01\rangle\\!\langle 01|+|10\rangle\\!\langle 10|.$ (177)

To test a symmetry of this form, we rewrite the projector in terms of
unitaries. We construct a set of unitaries $U_{y}$ such that

$\Pi_{z}^{(n)}=\frac{1}{n+1}\sum_{y=0}^{n}U_{y}.$ (178)

We use a construction similar to the form given in the section on pinching
channels [71]. Define a unitary representation $\\{U_{y}\\}_{y=0}^{n}$ as

$U_{y}\coloneqq\sum\limits_{x=0}^{n}\exp\left[\frac{\pi
i}{n+1}\left(2y-n\right)\left(2x-n\right)\right]P_{x}.$ (179)

Observe that $U_{y}^{\dagger}U_{y}=\mathbb{I}$. Furthermore, we see that

$\sum\limits_{y=0}^{n}U_{y}=\sum\limits_{x=0}^{n}\sum\limits_{y=0}^{n}\exp\left[\frac{\pi
i}{n+1}\left(2y-n\right)\left(2x-n\right)\right]P_{x}.$ (180)

Consider that for integer $c\neq 0$,

$\displaystyle\sum\limits_{y=0}^{n}\exp\\!\left(\frac{\pi
i}{n+1}c\left(2y-n\right)\right)$ $\displaystyle=\exp\\!\left(\frac{-\pi
icn}{n+1}\right)\frac{1-\exp(2\pi ic)}{1-\exp\left(\frac{2\pi
ic}{n+1}\right)}$ $\displaystyle=0.$ (181)

Thus, only terms satisfying $2x=n$ survive the summation. Therefore,

$\displaystyle\frac{1}{n+1}\sum\limits_{y=0}^{n}U_{y}$
$\displaystyle=\sum\limits_{x=0}^{n}\delta(2x,n)P_{x}$ (182)
$\displaystyle=\begin{cases}P_{k}&\text{if }n=2k\\\
0&\text{otherwise}\end{cases}$ (183) $\displaystyle=\Pi_{z}^{(n)}.$ (184)

Thus, testing $G$-Bose symmetry with respect to $G_{z}=\\{R_{z}(\phi)^{\otimes
n}\\}_{\phi\in[0,4\pi)}$ is equivalent to testing $G$-Bose symmetry with
respect to $\\{U_{y}\\}_{y=0}^{n}$. To summarize, testing if a $n$-qubit state
is $G_{z}$-Bose symmetric is equivalent to testing if it belongs to the
subspace of Hamming weight $n=2k$. As an aside, we note that a generalization
of our method allows for performing a projection onto constant-Hamming-weight
subspaces, which is useful in tasks like entanglement concentration [80]. See
also [52] for alternative circuit constructions for performing measurements of
Hamming weight.

In what follows, we test the symmetry for an example, with $n=2$. From the
definition, we see that

$\displaystyle U_{0}$ $\displaystyle=\exp\\!\left(-\frac{2\pi
i}{3}\right)P_{0}+P_{1}+\exp\\!\left(\frac{2\pi i}{3}\right)P_{2},$ (185)
$\displaystyle U_{1}$ $\displaystyle=\mathbb{I},$ (186) $\displaystyle U_{2}$
$\displaystyle=\exp\\!\left(\frac{2\pi
i}{3}\right)P_{0}+P_{1}+\exp\\!\left(-\frac{2\pi i}{3}\right)P_{2}$
$\displaystyle=U_{0}^{2}.$ (187)

Thus, the set of unitaries forms a unitary representation of the cyclic group
$C_{3}$. The group table can be seen in Appendix D, where
$\\{|00\rangle\rightarrow U_{1},|01\rangle\rightarrow
U_{0},|11\rangle\rightarrow U_{2}\\}$. Expanding terms, we see that

$U_{0}=\left(R_{z}\\!\left(\frac{2\pi}{3}\right)\right)^{\otimes 2}.$ (188)

Furthermore, since $U_{2}=U^{2}_{0}$,

$U_{2}=\left(R_{z}\\!\left(-\frac{2\pi}{3}\right)\right)^{\otimes 2}.$ (189)

Since we have three elements, the $|+\rangle_{C}$ state is a uniform
superposition of three elements. We use two qubits and the same unitary
$U_{3}$ used to generate the superposition for the cyclic group $C_{3}$, as
shown in Figure 30,

$U_{3}|00\rangle=\frac{1}{\sqrt{3}}(|00\rangle+|01\rangle+|11\rangle).$ (190)

Figure 20a) depicts the circuit that tests for $G$-Bose symmetry. Table 12
shows the results for various input states. The true fidelity value is
calculated using (36), where $\Pi^{G}_{S}$ is defined in (19).

State |  True Fidelity |  Noiseless |  Noisy
---|---|---|---
$|00\rangle\\!\langle 00|$ |  0.0 |  0.0000 |  0.0220
$\rho$ |  1.0 |  1.0000 |  0.9170
$|0\rangle\\!\langle 0|\otimes|+\rangle\\!\langle+|$ |  0.5 |  0.5000 |  0.4877
$\pi^{\otimes 2}$ |  0.5 |  0.5000 |  0.4661
Table 12: Results of collective-phase-Bose symmetry tests. The state $\rho$ is
defined as $|\psi\rangle\\!\langle\psi|$ where
$|\psi\rangle=\frac{1}{\sqrt{2}}(|01\rangle+|10\rangle)$.

####  VI.4.2 $G$-symmetry

A state that is $G_{z}$-symmetric satisfies the following condition:

$\rho=\mathcal{C}_{z}^{(n)}(\rho),$ (191)

where the collective dephasing channel $\mathcal{C}_{z}^{(n)}$ is defined as

$\mathcal{C}_{z}^{(n)}(\omega)\coloneqq\frac{1}{4\pi}\int_{0}^{4\pi}d\phi\
R_{z}(\phi)^{\otimes n}\omega R^{\dagger}_{z}(\phi)^{\otimes n}.$ (192)

Using the fact that

$R_{z}(\phi)=\operatorname{exp}(-i\phi\sigma_{z}/2),$ (193)

we see that

$R_{z}(\phi)|a\rangle\\!\langle
b|R^{\dagger}_{z}(\phi)=e^{i\phi(a-b)}|a\rangle\\!\langle b|,$ (194)

for $a,b\in\\{0,1\\}$. Thus, for a general $n$-qubit state $\rho$, expanded in
the computational basis as

$\rho=\sum_{x_{1},\ldots,x_{n},y_{1},\ldots,y_{n}}\rho_{x_{1},\ldots,x_{n},y_{1},\ldots,y_{n}}|x_{1}\cdots
x_{n}\rangle\\!\langle y_{1}\cdots y_{n}|,$ (195)

it follows that

$\mathcal{C}_{z}^{(n)}(\rho)=\sum_{x_{1},\ldots,x_{n},y_{1},\ldots,y_{n}}\delta\\!\left(\sum_{i}x_{i},\sum_{j}y_{j}\right)\times\\\
\rho_{x_{1},\ldots,x_{n},y_{1},\ldots,y_{n}}|x_{1}\cdots
x_{n}\rangle\\!\langle y_{1}\cdots y_{n}|.$ (196)

Since $\sum_{i}x_{i}=H(x)$, it follows that

$\mathcal{C}_{z}^{(n)}(\rho)=\sum\limits_{k=0}^{n}P_{k}\rho P_{k},$ (197)

where, as before, $P_{k}$ is the projector onto the subspace of Hamming weight
$k$. For the case of $n=2$, we get the following projectors

$\displaystyle P_{0}$ $\displaystyle=|00\rangle\\!\langle 00|,$ (198)
$\displaystyle P_{1}$ $\displaystyle=|01\rangle\\!\langle
01|+|10\rangle\\!\langle 10|,$ (199) $\displaystyle P_{2}$
$\displaystyle=|11\rangle\\!\langle 11|.$ (200)

To test a symmetry of this form, we can rewrite the channel in terms of a set
$\\{U_{y}\\}_{y}$ unitaries satisfying

$\mathcal{C}_{z}^{(n)}(\rho)=\frac{1}{n+1}\sum\limits_{y=0}^{n}U_{y}\rho
U^{\dagger}_{y}.$ (201)

We now prove that the unitaries $\\{U_{y}\\}_{y=0}^{n}$ from (179) satisfy
this condition:

$\displaystyle\frac{1}{n+1}\sum\limits_{y=0}^{n}U_{y}\rho U^{\dagger}_{y}$
$\displaystyle=\frac{1}{n+1}\sum\limits_{x,x^{\prime},y=0}^{n}\exp\left[\frac{\pi
i}{n+1}\left(2y-n\right)2\left(x-x^{\prime}\right)\right]P_{x}\rho
P_{x^{\prime}}$
$\displaystyle=\frac{1}{n+1}\sum\limits_{x,x^{\prime}=0}^{n}(n+1)\delta(x,x^{\prime})P_{x}\rho
P_{x^{\prime}}$ $\displaystyle=\sum\limits_{x=0}^{n}P_{x}\rho P_{x},$ (202)

where the third equality follows from the reasoning in (181).

Thus, similar to the $G$-Bose symmetry tests, testing $G$-symmetry with
respect to $G_{z}=\\{R_{z}(\phi)^{\otimes n}\\}_{\phi\in[0,4\pi)}$ is
equivalent to testing $G$-symmetry with respect to $\\{U_{y}\\}_{y=0}^{n}$. To
summarize, testing if an $n$-qubit state is $G_{z}$-symmetric is equivalent to
testing if it belongs to a subspace of fixed Hamming weight. In this work, we
test the symmetry for $n=2$.

A circuit that tests for $G$-symmetry is shown in Figure 20b). It involves
variational parameters, and an example of the training process is shown in
Figure 21. Table 13 shows the final results after training for various input
states. The true fidelity is calculated using the semi-definite program given
in (139).

Figure 21: Example of the training process for testing collective-phase-symmetry of $\rho=|\Psi^{+}\rangle\\!\langle\Psi^{+}|$, where $|\Psi^{+}\rangle=\frac{1}{\sqrt{2}}(|01\rangle+|10\rangle)$. State |  True Fidelity |  Noiseless |  Noisy |  Noise Resilient
---|---|---|---|---
$|00\rangle\\!\langle 00|$ |  1.0000 |  0.9999 |  0.8380 |  0.9928
$\rho$ |  1.0000 |  1.0000 |  0.8162 |  0.9906
$\tau$ |  0.5001 |  0.5000 |  0.4630 |  0.4990
$\pi^{\otimes 2}$ |  1.0000 |  0.9998 |  0.8417 |  0.9934
Table 13: Results of collective-phase-symmetry tests. The state $\rho$ is
defined as $|\Psi^{+}\rangle\\!\langle\Psi^{+}|$ where
$|\Psi^{+}\rangle=\frac{1}{\sqrt{2}}(|01\rangle+|10\rangle)$. The state $\tau$
is defined as $|\Phi^{+}\rangle\\!\langle\Phi^{+}|$ where
$|\Phi^{+}\rangle=\frac{1}{\sqrt{2}}(|00\rangle)+|11\rangle)$.

####  VI.4.3 $G$-Bose symmetric extendibility

A circuit that tests for $G$-Bose symmetric extendibility is shown in Figure
20c). It involves variational parameters, and an example of the training
process is shown in Figure 22. Table 14 shows the final results after training
for various input states. The true fidelity is calculated using the semi-
definite program given in (140).

Figure 22: Example of the training process for testing collective-phase-Bose symmetric extendibility of $\nicefrac{{3}}{{4}}|0\rangle\\!\langle 0|+\nicefrac{{1}}{{4}}|1\rangle\\!\langle 1|$. We see that the training exhibits a noise resilience. State |  True Fidelity |  Noiseless |  Noisy |  Noise Resilient
---|---|---|---|---
$|0\rangle\\!\langle 0|$ |  1.0000 |  1.0000 |  0.9783 |  0.9980
$\sigma$ |  1.0000 |  1.0000 |  0.9349 |  0.9993
$|-\rangle\\!\langle-|$ |  0.5002 |  0.5000 |  0.4464 |  0.5000
$\rho$ |  0.9330 |  0.9330 |  0.9208 |  0.9328
Table 14: Results of collective-phase-Bose symmetric extendibility tests. The state $\sigma$ is defined as $\nicefrac{{3}}{{4}}|0\rangle\\!\langle 0|+\nicefrac{{1}}{{4}}|1\rangle\\!\langle 1|$. The state $\rho$ is defined as $\begin{bmatrix}0.93&0.25\\\ 0.25&0.07\end{bmatrix}$. State |  True Fidelity |  Noiseless |  Noisy |  Noise Resilient
---|---|---|---|---
$|0\rangle\\!\langle 0|$ |  1.0000 |  0.9960 |  0.8632 |  0.9988
$|+\rangle\\!\langle+|$ |  0.5000 |  0.5000 |  0.4580 |  0.4997
$\rho$ |  0.7500 |  0.7494 |  0.6577 |  0.7484
Table 15: Results of collective-phase-symmetric extendibility tests. The state
$\rho$ is defined as $\begin{bmatrix}0.75&0.43\\\ 0.43&0.25\end{bmatrix}$.

####  VI.4.4 $G$-symmetric extendibility

A circuit that tests for $G$-symmetric extendibility is shown in Figure 20d).
It involves variational parameters, and an example of the training process is
shown in Figure 23. Table 15 shows the final results after training for
various input states. The true fidelity is calculated using the semi-definite
program given in (141).

Figure 23: Example of the training process for testing collective-phase-
symmetric extendibility of $|+\rangle\\!\langle+|$.

###  VI.5 $k$-Extendibility and $k$-Bose extendibility

As seen in Examples II.1 and II.2, $k$-extendibility and $k$-Bose
extendibility are special cases of $G$-symmetric extendibility and $G$-Bose
symmetric extendibility, respectively. In this section, we look at the cases
of two and three extending subsystems.

As seen in (9)–(12), $U_{RS}(g)=I_{A}\otimes W_{B_{1}\cdots B_{k}}(\pi)$,
where $W_{B_{1}\cdots B_{k}}(\pi)$ is a unitary representation of the
symmetric group $S_{k}$. Thus, given a unitary representation of $S_{k}$, we
can test for the required symmetries.

The $S_{2}$ group has two elements, and the group table is given by

Group element |  $e$ |  $a$
---|---|---
$e$ |  $e$ |  $a$
$a$ |  $a$ |  $e$

The standard representation of $S_{2}$ translates easily to a two-qubit
unitary representation with $\\{e\rightarrow I,a\rightarrow F\\}$, where $F$
is the SWAP gate. In fact, throughout this section, we will consider unitary
representations corresponding to system permutations in a direct
correspondence with the standard representations of $S_{k}$. Using this
definition, let $U_{RS}(e)=I_{A}\otimes I_{B_{1}B_{2}}$ and
$U_{RS}(a)=I_{A}\otimes F_{B_{1}B_{2}}$. Since we have two elements, the
$|+\rangle_{C}$ state is a uniform superposition of two elements. We thus use
one qubit and the Hadamard gate to generate the necessary state:

$H|0\rangle=\frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right).$ (203)

The control register states need to be mapped to group elements; for this, we
employ the mapping $\\{|0\rangle\rightarrow e,|1\rangle\rightarrow a\\}$ for
our circuit constructions.

Similarly, the $S_{3}$ group has six elements and the group table is given by

Group element |  $e$ |  $a$ |  $b$ |  $c$ |  $d$ |  $f$
---|---|---|---|---|---|---
$e$ |  $e$ |  $a$ |  $b$ |  $c$ |  $d$ |  $f$
$a$ |  $a$ |  $e$ |  $d$ |  $f$ |  $b$ |  $c$
$b$ |  $b$ |  $f$ |  $e$ |  $d$ |  $c$ |  $a$
$c$ |  $c$ |  $d$ |  $f$ |  $e$ |  $a$ |  $b$
$d$ |  $d$ |  $c$ |  $a$ |  $b$ |  $f$ |  $e$
$f$ |  $f$ |  $b$ |  $c$ |  $a$ |  $e$ |  $d$

The $S_{3}$ group has a three-qubit unitary representation $\\{e\rightarrow
I,a\rightarrow F_{23},b\rightarrow F_{13},c\rightarrow F_{12},d\rightarrow
F_{12}F_{23},f\rightarrow F_{13}F_{23}\\}$, where $F_{ij}$ is the SWAP gate
between qubits $i$ and $j$. Since we have six elements, the $|+\rangle_{C}$
state is a uniform superposition of six elements. We use three qubits and the
same unitary $U_{d}$ used to generate the superposition for the triangular
dihedral group, as shown in Figure 2, to generate an equal superposition of
six elements,

$U_{d}|000\rangle=\frac{1}{\sqrt{6}}(|000\rangle+|001\rangle+|010\rangle+\\\
|011\rangle+|100\rangle+|101\rangle).$ (204)

The control register states need to be mapped to group elements, and we do so
via the mapping $\\{|000\rangle\rightarrow e,|001\rangle\rightarrow
a,|010\rangle\rightarrow b,|011\rangle\rightarrow f,|100\rangle\rightarrow
c,|101\rangle\rightarrow d\\}$.

Figure 24: Tests for extendibility: a) two-Bose extendibility, b) two-
extendibility, c) three-Bose extendibility, and d) three-extendibility.

####  VI.5.1 Two-Bose extendibility

A circuit that tests for two-Bose extendibility is shown in Figure 24a). It
involves variational parameters, and an example of the training process is
shown in Figure 25. Table 16 shows the final results after training for
various input states. The true fidelity is calculated using the semi-definite
program given in (140).

Figure 25: Example of the training process for testing two-Bose extendibility of $\rho=\nicefrac{{3}}{{4}}|00\rangle\\!\langle 00|+\nicefrac{{1}}{{4}}|11\rangle\\!\langle 11|$. We see that the training exhibits a noise resilience. State |  True Fidelity |  Noiseless |  Noisy |  Noise Resilient
---|---|---|---|---
$|00\rangle\\!\langle 00|$ |  1.0000 |  1.0000 |  0.9544 |  0.9995
$\rho$ |  1.0000 |  1.0000 |  0.9584 |  0.9995
$\Psi^{+}$ |  0.7500 |  0.7500 |  0.7256 |  0.7500
Table 16: Results of $S_{2}$-Bose symmetric extendibility tests. The state
$\rho$ is defined as $\nicefrac{{3}}{{4}}|00\rangle\\!\langle
00|+\nicefrac{{1}}{{4}}|11\rangle\\!\langle 11|$.

####  VI.5.2 Two-Extendibility

Similar to the non-extended cases, it is simpler to test if a state exhibits
$G$-BSE—or, in this case, if the state is $k$-Bose-symmetric extendible—than
to test if it is merely symmetric. This is reflected in Figure 24b), which
shows a test for 2-BSE. The circuit involves variational parameters, and an
example of the training process is shown in Figure 26. Table 17 shows the
final results after training for various input states. The true fidelity is
calculated using the semi-definite program given in (141).

Figure 26: Example of the training process for testing two-extendibility of $\rho=|\psi\rangle\\!\langle\psi|$, where $|\psi\rangle=\frac{1}{\sqrt{2}}|11\rangle+\frac{1}{\sqrt{6}}(|00\rangle+|01\rangle+|10\rangle)$. We see that the training exhibits a noise resilience. State |  True Fidelity |  Noiseless |  Noisy |  Noise Resilient
---|---|---|---|---
$|00\rangle\\!\langle 00|$ |  1.0000 |  0.9991 |  0.9267 |  0.9960
$\rho$ |  0.9925 |  0.9901 |  0.9720 |  0.9913
$\Psi^{+}$ |  0.7506 |  0.7498 |  0.6959 |  0.7480
Table 17: Results of $S_{2}$-symmetric extendibility tests. The state $\rho$
is defined as $|\psi\rangle\\!\langle\psi|$ where
$|\psi\rangle=\frac{1}{\sqrt{2}}|11\rangle+\frac{1}{\sqrt{6}}(|00\rangle+|01\rangle+|10\rangle)$.
The reduced state of $\rho$ has eigenvalues
$\frac{1}{6}\left(3+\sqrt{5+2\sqrt{3}}\right)\approx 0.985$ and
$\frac{1}{6}\left(3-\sqrt{5+2\sqrt{3}}\right)\approx 0.015$. It is thus not so
entangled, and we expect its two-extendible fidelity to be close to one.

####  VI.5.3 Three-Bose Extendibility

A circuit that tests for three-Bose extendibility is shown in Figure 24c). It
involves variational parameters, and an example of the training process is
shown in Figure 27. Table 18 shows the final results after training for
various input states. The true fidelity is calculated using the semi-definite
program given in (140).

Figure 27: Example of the training process for testing three-Bose extendibility of $\rho=\nicefrac{{3}}{{4}}|00\rangle\\!\langle 00|+\nicefrac{{1}}{{4}}|11\rangle\\!\langle 11|$. We see that the training exhibits a noise resilience. State |  True Fidelity |  Noiseless |  Noisy |  Noise Resilient
---|---|---|---|---
$|00\rangle\\!\langle 00|$ |  1.0000 |  0.9999 |  0.8644 |  0.9982
$\rho$ |  1.0000 |  0.9994 |  0.8403 |  0.9851
$\Psi^{+}$ |  0.6675 |  0.6667 |  0.5666 |  0.6666
Table 18: Results of $S_{3}$-Bose symmetric extendibility tests. The state
$\rho$ is defined as $\nicefrac{{3}}{{4}}|00\rangle\\!\langle
00|+\nicefrac{{1}}{{4}}|11\rangle\\!\langle 11|$.

####  VI.5.4 Three-Extendibility

A circuit that tests for three-extendibility is shown in Figure 24d). It
involves variational parameters, and an example of the training process is
shown in Figure 28. Table 19 shows the final results after training for
various input states. The true fidelity is calculated using the semi-definite
program given in (141).

Figure 28: Example of the training process for testing three-extendibility of $|00\rangle\\!\langle 00|$. State |  True Fidelity |  Noiseless
---|---|---
$|00\rangle\\!\langle 00|$ |  1.0000 |  0.9970
$\rho$ |  1.0000 |  0.9988
$\Psi^{+}$ |  0.6670 |  0.6650
Table 19: Results of $S_{3}$-symmetric extendibility tests. Here,
$\rho=\nicefrac{{3}}{{4}}|00\rangle\\!\langle
00|+\nicefrac{{1}}{{4}}|11\rangle\\!\langle 11|$.

For all of the above cases, we see that results achieved via parameterized
circuit substitutions for the prover demonstrate noise resilience, and thus
give some confidence for practical applications. In this final case, we have
shown explicitly how our algorithm allows for tests of $k$-extendibility and
related quantities. While only small systems are considered here, this is a
limitation of current hardware more so than of the algorithm itself. Indeed,
it would be interesting to observe the performance of this algorithm on higher
fidelity machines with more qubits, which will hopefully be achievable in the
near future.

##  VII Resource theories

In this section, we prove that the various maximum symmetric fidelities
proposed in Section III are proper resource-theoretic monotones, in the sense
reviewed in [21]. Thus, they are indeed measures of symmetry as claimed.

To begin with, let us recall the basics of a resource theory (see [21,
Definition 1]). Intuitively, one can delineate a resource theory by first
specifying a restricted set of free channels, which are understood as allowed
operations. In a resource theory, one of the basic questions is to determine
whether it is possible to transition from a source state to a target state by
means of only these free channels. Furthermore, once the set of free channels
is fixed, the free states are also set, because a free state can be understood
as a particular kind of free channel in which the input system to the channel
is a trivial system.

More formally, let $\mathcal{F}$ be a mapping that assigns a unique set of
quantum channels to any arbitrary input and output systems $A$ and $B$,
respectively. We require that $\mathcal{F}$ include the identity channel
($\mathcal{F}(A\rightarrow A)=\operatorname{id}_{A}$) and that, for any three
physical systems $A$, $B$, and $C$, any two maps $\mathcal{N}_{A\rightarrow
B}\in\mathcal{F}(A\rightarrow B)$ and $\mathcal{M}_{B\rightarrow
C}\in\mathcal{F}(B\rightarrow C)$ have the transitive property

$\mathcal{M}_{B\rightarrow C}\circ\mathcal{N}_{A\rightarrow
B}\in\mathcal{F}(A\rightarrow C)\,.$ (205)

If $\mathcal{F}$ obeys above criteria, then the mapping $\mathcal{F}$ defines
the resource theory. The set $\mathcal{F}(\mathbb{C}\rightarrow A)$ defines
the set of free states—that is, channels from the trivial space ($\mathbb{C}$)
to system $A$ are quantum states. The set $\mathcal{F}(A\rightarrow B)$
defines the set of free channels from system $A$ to system $B$.

###  VII.1 Resource theory of asymmetry

The resource theory of asymmetry is well established by now [59], but to the
best of our knowledge, the resource theory of Bose asymmetry has not been
defined yet. Let us begin by recalling the resource theory of asymmetry.
Afterwards, we establish the resource theory of Bose asymmetry as well as two
other generalizations involving unextendibility, which are in turn
generalizations of the resource theory of unextendibility proposed in [49,
50].

Let $G$ be a group, and let $\\{U_{A}(g)\\}_{g\in G}$ and
$\\{V_{B}(g)\\}_{g\in G}$ denote projective unitary representations of $G$. A
channel $\mathcal{N}_{A\rightarrow B}$ is a free channel in the resource
theory of asymmetry if the following $G$-covariance symmetry condition holds