# Quantum majority vote

Harry Buhrman QuSoft, CWI, and University of Amsterdam<EMAIL_ADDRESS>Noah Linden University of Bristol<EMAIL_ADDRESS>Laura Mančinska
University of Copenhagen<EMAIL_ADDRESS>Ashley Montanaro Phasecraft
Ltd and University of Bristol<EMAIL_ADDRESS>Maris Ozols
QuSoft and University of Amsterdam<EMAIL_ADDRESS>
###### Abstract

Majority vote is a basic method for amplifying correct outcomes that is widely
used in computer science and beyond. While it can amplify the correctness of a
quantum device with classical output, the analogous procedure for quantum
output is not known. We introduce _quantum majority vote_ as the following
task: given a product state
$|\psi_{1}\rangle\otimes\dots\otimes|\psi_{n}\rangle$ where each qubit is in
one of two orthogonal states $|\psi\rangle$ or $|\psi^{\perp}\rangle$, output
the majority state. We show that an optimal algorithm for this problem
achieves worst-case fidelity of $1/2+\Theta(1/\sqrt{n})$. Under the promise
that at least $2/3$ of the input qubits are in the majority state, the
fidelity increases to $1-\Theta(1/n)$ and approaches $1$ as $n$ increases.

We also consider the more general problem of computing any symmetric and
equivariant Boolean function $f:\\{0,1\\}^{n}\to\\{0,1\\}$ in an unknown
quantum basis, and show that a generalization of our quantum majority vote
algorithm is optimal for this task. The optimal parameters for the generalized
algorithm and its worst-case fidelity can be determined by a simple linear
program of size $O(n)$. The time complexity of the algorithm is $O(n^{4}\log
n)$ where $n$ is the number of input qubits.

###### Contents

  1. 1 Introduction
    1. 1.1 Problem
    2. 1.2 Our results
    3. 1.3 Related work
    4. 1.4 Open problems
    5. 1.5 Outline
  2. 2 Preliminaries
    1. 2.1 Mathematical preliminaries
    2. 2.2 Computing functions in a basis-independent way
    3. 2.3 Symmetric and equivariant Boolean functions
    4. 2.4 Impossibility of perfect quantum majority
    5. 2.5 Symmetries of optimal algorithms
  3. 3 Generic pre-processing
    1. 3.1 Schur–Weyl duality
    2. 3.2 Schur transform
    3. 3.3 Nice Schur basis of the $n$-qubit space
    4. 3.4 Generic pre-processing
    5. 3.5 Example: $3$-qubit quantum majority
  4. 4 Completing the algorithm
    1. 4.1 Representation theory refresher
    2. 4.2 Two extremal channels
    3. 4.3 Understanding the extremal channels
    4. 4.4 The optimal algorithm and its fidelity
  5. 5 Applications of the general framework
    1. 5.1 Exact numerical results
    2. 5.2 Asymptotic fidelity of quantum majority
    3. 5.3 Unitary-equivariant Boolean functions
  6. A Graphical notation
    1. A.1 Vectorization
    2. A.2 Singlet chains
  7. B Properties of the vectors $|{(\lambda,w,i)}\rangle$
    1. B.1 Block-diagonalization of permutations
    2. B.2 Orthonormality
    3. B.3 Unitary action
  8. C Representations of $2\times 2$ matrices
    1. C.1 Construction
    2. C.2 Properties
    3. C.3 Irreducibility
    4. C.4 Completeness
    5. C.5 Representations of $\mathrm{U}(2)$
    6. C.6 Clebsch–Gordan transform
    7. C.7 Dual Clebsch–Gordan transform
  9. D Symmetric subspace
    1. D.1 Projector onto the symmetric subspace
    2. D.2 Symmetric subspace and irreducible representations of $\mathrm{SU}(2)$
    3. D.3 Symmetric subspace and tensor power states
    4. D.4 Invariant subspaces of $\mathbb{C}^{2}\otimes\mathrm{Sym}(\ell)$
    5. D.5 Symmetric subspace and (dual) Clebsch–Gordan transform
  10. E Implementation of the extremal covariant channels $\Phi^{\ell}_{\operatorname{Tr}}$ and $\Phi^{\ell}_{\mathrm{UNOT}}$
    1. E.1 Representations of quantum channels
    2. E.2 Kraus operators of $\Phi^{\ell}_{1}$ and $\Phi^{\ell}_{2}$
    3. E.3 The action of $\Phi^{\ell}_{1}$ and $\Phi^{\ell}_{2}$
    4. E.4 Proof that $\Phi^{\ell}_{1}=\Phi^{\ell}_{\operatorname{Tr}}$ and $\Phi^{\ell}_{2}=\Phi^{\ell}_{\mathrm{UNOT}}$
    5. E.5 Isometries and quantum circuits for $\Phi^{\ell}_{\operatorname{Tr}}$ and $\Phi^{\ell}_{\mathrm{UNOT}}$
  11. F Monotonicity of fidelity in the Hamming weight
  12. G Numerical Choi matrices
    1. G.1 Choi matrices for optimal quantum channels
    2. G.2 Choi matrices for unitary-equivariant Boolean functions

> Majority rule is a precious, sacred thing worth dying for. But—like other
> precious, sacred things—it’s not only worth dying for; it can make you wish
> you were dead. Imagine if all of life were determined by majority rule.
> Every meal would be a pizza.
>
> P. J. O’Rourke

##  1 Introduction

For most practical matters, it is safe to assume that the material world
around us obeys the laws of classical physics. However, explaining certain
phenomena, particularly at small scales, requires a more fundamental theory –
quantum mechanics. Similarly, our digital world at present is fully classical,
i.e., it consists of zeroes and ones, while the ultimate description of
information is quantum mechanical [Wat18]. Quantum information, at least from
a mathematical perspective, is not only more fundamental but also more
abundant – classical states form a measure zero subset of quantum states. From
this perspective, a (reversible) classical algorithm is nothing but a quantum
algorithm whose state remains in the standard basis throughout computation. In
particular, classical algorithms constitute only a measure zero subset of
quantum algorithms.111If we think of an algorithm as a CPTP map (see Section
2.1), probabilistic algorithms are described by diagonal Choi matrices that
constitute a measure zero subset of ones describing general quantum
algorithms.

While typically quantum algorithms are designed for solving classical
problems, i.e., their input and output consists of standard basis states, a
quantum algorithm should generally be thought of as a quantum channel that
processes quantum information – it has quantum input and quantum output. Far
from being just a philosophical stance, this is also a pragmatic view
motivated by quantum programming.

New quantum (and classical) algorithms are often obtained by combining
existing building blocks, i.e., subroutines that solve smaller sub-problems.
Even if the algorithm itself solves a classical problem, its constituent
subroutines are often fully quantum. For example, quantum Fourier transform
[Cop94], amplitude amplification [BH97, Gro98], and SWAP test [BBD+97] are
subroutines for intrinsically quantum tasks. This motivates the development of
new fully quantum subroutines that can be used as building blocks of new
quantum algorithms.

_Majority vote_ is a simple but ubiquitous method that ensures robustness to
errors in various contexts, ranging from elections to error-correction. For
example, majority vote is used in essentially all randomized (and in
particular also quantum) algorithms to amplify their success probability by
repeating the computation several times and selecting the most common outcome.
Since majority vote only deals with classical data, this begs the question of
whether there exists a natural analogue to majority vote that is fully
quantum. In fact, one can ask the same question for any Boolean function.

###  1.1 Problem

To state the problem more formally, consider two parties: Alice and Bob. Alice
has an $n$-bit string $x\in\\{0,1\\}^{n}$ represented by the $n$-qubit
standard basis state $|{x}\rangle\in\mathbb{C}^{2^{n}}$. She would like Bob to
evaluate some particular Boolean function $f:\\{0,1\\}^{n}\to\\{0,1\\}$ (e.g.,
the majority function) on her state and return the answer as a single-qubit
state $|{f(x)}\rangle\in\mathbb{C}^{2}$. However, assume that instead of
$|{x}\rangle$, Bob receives $U^{\otimes n}|{x}\rangle$ for some unknown
single-qubit unitary $U\in\mathrm{U}(2)$, and his goal is to produce
$U|{f(x)}\rangle$ for the same unknown $U$ (see Fig. 1).

AliceBob$|{x}\rangle$$|{f(x)}\rangle$$U^{\otimes
n}|{x}\rangle$$U|{f(x)}\rangle$$U^{\otimes n}$$U^{\dagger}$? Figure 1: The
ideal functionality of a unitary-equivariant Boolean function. For a given
function $f:\\{0,1\\}^{n}\to\\{0,1\\}$, Bob would like to implement the ideal
$n$-to-$1$ qubit map $U^{\otimes n}|{x}\rangle\mapsto U|{f(x)}\rangle$ for all
$U\in\mathrm{U}(2)$ and $x\in\\{0,1\\}^{n}$. Since in general the ideal map
cannot be implemented by a completely positive operation (see Section 2.4),
the problem is to find the best quantum channel that approximates it.

This problem appears naturally in several scenarios. For instance, if the
communication channel between Alice and Bob is imperfect, it may cause an
unknown unitary drift $U$ to each qubit transmitted in one direction, and
$U^{\dagger}$ when transmitted in the reverse direction (this is a simple way
to model an idealized lossless optical fiber). Alternatively, the laboratories
of Alice and Bob might not share a common reference frame, such as in the case
of satellite-based communication [DNW+12]. Finally, another,
cryptographically-motivated setting is when Alice scrambles (and later
unscrambles) the data on purpose to hide it from Bob who has been delegated
with computing $f$.

In either case, Bob is faced with the task of computing a Boolean function in
an unknown quantum basis determined by a unitary $U$ (both his input and
output qubits are in the same unknown basis). We call such basis-independent
computation _unitary-equivariant_ (see Section 2.2 for more details). Note
that in each of the above scenarios, despite Bob being unaware of the basis,
Alice can still correctly interpret his output because it either matches with
her basis or she can undo the scrambling unitary $U$ if she did it herself.

This problem is particularly well-motivated when $f$ is the $n$-bit _majority_
function. In this case, Bob receives an $n$-qubit product state
$|{\psi_{1}}\rangle\otimes\dotsb\otimes|{\psi_{n}}\rangle$ where each qubit
$|{\psi_{i}}\rangle\in\mathbb{C}^{2}$ is one of two orthogonal states
$|{\psi}\rangle$ or $|{\psi^{\perp}}\rangle$. He is asked to return either
$|{\psi}\rangle$ or $|{\psi^{\perp}}\rangle$, depending on which state occurs
more often. The difficulty lies in the fact that the basis
$\\{|{\psi}\rangle,|{\psi^{\perp}}\rangle\\}$ is unknown to Bob, so the
procedure has to work in any basis. We refer to this problem as _quantum
majority vote_ since Bob’s task is to compute the majority function in an
unknown quantum basis.

Just like the classical majority vote, quantum majority vote can also be seen
as a technique for mitigating errors. Assume that a given quantum device is
supposed to produce some unknown state $|{\psi}\rangle$, but it occasionally
fails and instead produces $|{\psi^{\perp}}\rangle$. Quantum majority vote can
then be used to distill the correct state from several samples (see Fig. 2).
In particular, this method can be used to amplify the output fidelity of any
quantum-output black-box subroutine within a quantum algorithm.

$|{\psi}\rangle|{\psi}\rangle|{\psi^{\perp}}\rangle|{\psi}\rangle|{\psi}\rangle|{\psi^{\perp}}\rangle|{\psi}\rangle|{\psi}\rangle|{\psi}\rangle$$|{\psi}\rangle$?
Figure 2: Quantum majority vote: given a sequence of $n$ quantum states from
an unknown basis $\\{|{\psi}\rangle,|{\psi^{\perp}}\rangle\\}$, output the
majority state.

For a general function $f$ it is not possible to perfectly implement the map
$U^{\otimes n}|{x}\rangle\mapsto U|{f(x)}\rangle$ for all input strings
$x\in\\{0,1\\}^{n}$ and unitaries $U\in\mathrm{U}(2)$ since it is not
completely positive (see Section 2.4 for a simple example). Hence, we will
instead look for a quantum channel that optimally approximates this map, in
the sense that it maximizes the fidelity with the ideal output state for the
worst-case input.

The simplest non-trivial instance of this problem is when $n=1$ and
$f=\mathrm{NOT}$ is the Boolean negation. The corresponding ideal map
$U|{x}\rangle\mapsto U|{\mathrm{NOT}(x)}\rangle$ is known as the _universal
$\mathrm{NOT}$_ since it is a unitary-equivariant extension of the
$\mathrm{NOT}$ function. This anti-unitary map sends an arbitrary qubit state
$|{\psi}\rangle=\begin{pmatrix}\alpha\\\ \beta\end{pmatrix}$ to its unique
perpendicular state $|{\psi^{\perp}}\rangle=\begin{pmatrix}\overline{\beta}\\\
-\overline{\alpha}\end{pmatrix}$. The best quantum channel that approximates
this map achieves the worst-case output fidelity of $2/3$ [BHW99] and has been
implemented experimentally [DMBSS02, PSS+03, DMPS04, RSSDM04].

###  1.2 Our results

Our main result is a generic algorithmic template $\mathcal{A}_{\mathbf{t}}$
for computing any unitary-equivariant Boolean function. This template has a
tuneable set of interpolation parameters $\mathbf{t}\in[0,1]^{\lfloor
n/2\rfloor+1}$, for which we derive an efficient linear program that finds the
optimal setting of $\mathbf{t}$, and we show that the algorithm
$\mathcal{A}_{\mathbf{t}}$ can be implemented efficiently. Below is an
informal statement of our main result (see Theorems 4.6, 4.7 and 4.8 in
Section 4.4 for more details).

######  Theorem 1.1 (informal).

Let $f:\\{0,1\\}^{n}\to\\{0,1\\}$ be a symmetric and equivariant Boolean
function. For appropriately chosen interpolation parameters $\mathbf{t}$, the
algorithm $\mathcal{A}_{\mathbf{t}}$ is optimal for computing the unitary-
equivariant extension of $f$. The optimal choice of $\mathbf{t}$ and the
corresponding worst-case fidelity for computing $f$ can be determined by a
simple linear program of size $O(n)$. The resulting algorithm
$\mathcal{A}_{\mathbf{t}}$ can be implemented using $O(n^{4}\log n)$ quantum
gates.

We apply our linear programming characterization to determine the optimal
fidelity $F_{\mathrm{MAJ}}(n)$ that can be achieved for the unitary-
equivariant $n$-bit majority function $\mathrm{MAJ}$. We distinguish two cases
depending on whether the input string $x\in\\{0,1\\}^{n}$ is arbitrary or its
Hamming weight $|x|$ is at least a constant fraction of $n$ away from $n/2$
(see Section 5.2 for more details).

No
promisePromise$\displaystyle\frac{1}{2}+\frac{1}{2n}$$\displaystyle\frac{5}{6}$Trivial$\displaystyle\frac{1}{2}+\Theta\left\lparen\frac{1}{\sqrt{n}}\right\rparen$$\displaystyle
1-\Theta\left\lparen\frac{1}{n}\right\rparen$Optimal$0$$n$$n\over
2$$0$$n$$n\over 2$$n/3$$n/3$ Figure 3: Optimal fidelities for the trivial
strategy that picks one of the $n$ input qubits at random, and the optimal
strategy. The first column corresponds to the case when there is no promise on
the input string $x\in\\{0,1\\}^{n}$, and the second when the Hamming weight
$|x|$ is at least $n/3$ away from the central value of $n/2$.

theoremmajority Let $n\geq 1$ be odd. If $|x|$ is arbitrary, then
$F_{\mathrm{MAJ}}(n)=1/2+\Theta(1/\sqrt{n})$. If we are promised that
$\big{\lvert}|x|-\frac{n}{2}\big{\rvert}\geq\frac{n}{3}$, then
$F_{\mathrm{MAJ}}(n)=1-\Theta(1/n)$.

For comparison, the trivial strategy that returns one of the input qubits at
random achieves worst-case fidelities
$(\frac{n}{2}+\frac{1}{2})/n=\frac{1}{2}+\frac{1}{2n}$ and $\frac{5}{6}$,
respectively (see Fig. 3). Note that in our setting the input state is of the
form
$|{\psi}\rangle\otimes|{\psi^{\perp}}\rangle\otimes\dotsb\otimes|{\psi}\rangle$
and in particular is pure. Hence we cannot directly compare our results to the
classical majority vote on the $n$-bit probability distribution
$(p,1-p)^{\otimes n}$ where $p\in[0,1]$, since this would require considering
mixed input states of the form $\rho^{\otimes n}$ where $\rho$ is an arbitrary
single-qubit density matrix. This version of the problem is known as _quantum
purification_ [CEM99, KW01].

###  1.3 Related work

While the idea of processing information encoded by parallel and antiparallel
spins has been suggested as an interesting direction already in [GP99], we are
not aware of any work that explores this problem in the setting of computing
Boolean functions in an unknown basis. Thus, here we survey work on problems
of similar flavor.

Montanaro has considered a problem that is closely related to ours, namely
computing a symmetric Boolean function on a quantum input but producing a
_classical_ output [Mon09]. Since the value of a symmetric function depends
only on the input’s Hamming weight, this problem effectively reduces to
determining the ratio of $|{\psi}\rangle$ versus $|{\psi^{\perp}}\rangle$ in
the tensor product input state. Similar to Montanaro’s approach, our algorithm
is also based on weak Schur sampling. However, producing a quantum output is
more challenging and requires further processing of the state that remains
after weak Schur sampling. This involves applying certain extremal unitary-
covariant channels with single-qubit output, which we characterize by
employing tools from representation theory of $\mathrm{U}(2)$ such as the dual
Clebsch–Gordan transform.

Another closely related problem is _quantum purification_ : given $n$ copies
of a mixed state

$\rho=(1-\epsilon)|{\psi}\rangle\langle{\psi}|+\epsilon|{\psi^{\perp}}\rangle\langle{\psi^{\perp}}|$
(1.1)

for some $\epsilon\in[0,1/2]$, output the state
$|{\psi}\rangle\langle{\psi}|$. This problem is closely related to quantum
majority vote since the binomial expansion of $\rho^{\otimes n}$ as a linear
combination of rank-$1$ product states
$|{\psi}\rangle\langle{\psi}|\otimes|{\psi^{\perp}}\rangle\langle{\psi^{\perp}}|\otimes\dotsb\otimes|{\psi}\rangle\langle{\psi}|$
is concentrated on states where the fraction of $|{\psi}\rangle\langle{\psi}|$
is roughly $1-\epsilon$. Since on such states quantum majority vote would
output a good approximation of $|{\psi}\rangle\langle{\psi}|$, we highly
suspect that our algorithm is also optimal for purification. Note that
previous work on purification has focused only on the information-theoretical
aspects of the problem, namely, at what rate and with what fidelity the task
can be achieved [CEM99, KW01]. However, as far as we are aware, algorithmic
implementation of purification has not been studied before. Therefore, if our
algorithm coincides with an optimal purifier, we are first to provide an
efficient implementation of purification – our algorithm uses $O(n^{4}\log n)$
gates. Other related quantum error suppression techniques have recently been
studied in [Koc21a, Koc21b, HMO+21].

Quantum cloning [SIGA05, GM97] can be considered as a reverse of purification
since it dilutes information by mapping a smaller number of perfect states to
a larger number of imperfect ones. Purification and cloning are examples of
so-called _quantum machines_ [HB09, Key02], i.e., algorithms with quantum
input or quantum output. Recent examples of these include quantum subtracting
machine [KFG19], unsupervised classification of quantum data [SMMT+19],
overlap estimation [FRS+20], and others [Wri16]. Quantum majority vote and its
generalization to equivariant Boolean functions also fit into this framework.
In fact, our template algorithm $\mathcal{A}_{\mathbf{t}}$ (Section 4.4) is an
example of a _programmable quantum processor_ [BHZR06, IH08]. Its
interpolation parameters $\mathbf{t}$ can be considered as a program that is
supplied either as a probability distribution or a quantum state. For
appropriately chosen $\mathbf{t}$ the algorithm can optimally evaluate any
symmetric equivariant Boolean function.

In the special case when $n=1$, there are only two relevant Boolean functions
– the identity function and NOT. While computing the identity function in a
basis-independent way is trivial, computing the NOT function corresponds to
applying the universal $\mathrm{NOT}$ operation mentioned earlier, which can
only be done with fidelity $2/3$ [BHW00, BHW99, GP99]. The post-processing
step after weak Schur sampling in our algorithm can be viewed as a convex
combination of quantum channels for computing the identity function and the
universal $\mathrm{NOT}$. In particular, we provide a novel and efficient
implementation of a variant of the universal $\mathrm{NOT}$, where the input
state has been isometrically scaled down from the symmetric subspace to a
single system of the corresponding dimension.

The recent optimization framework [GO22] for problems with permutational and
unitary symmetries is highly relevant to our problem, however it does not
easily apply in our setting due to a certain technical limitation. Our problem
corresponds to the parameter choice $(p,q,d)=(n,1,2)$ in [GO22].
Unfortunately, the partial trace constraint in their semidefinite program
requires that $d\geq p+q-1=n$ (see eq. (117) in [GO22]), which is not
satisfied when $d=2$ and $n\geq 3$. We expect a future refinement of [GO22] to
overcome this technical limitation.

One of our technical results is Lemma 4.1 which characterizes a certain set of
unitary-covariant quantum channels. Upon completing the manuscript we realized
that a similar characterization was already obtained by Al Nuwairan [Nuw14];
she derives extremal points of the set of $\mathrm{SU}(2)$-covariant quantum
channels and determines their Stinespring, Kraus, and Choi representations.
Various further properties of these channels have been investigated also in
[CKK+22], which has some overlap222Despite this, we decided to keep our
writing as it is for the sake of completeness and coherence. with our results
in Sections E.2 and E.3. Note that the same class of channels is also
discussed in Section V of [CKJ20], where they play a central role in spin
amplification and inversion. The optimal channels for these two tasks are
reminiscent of our extremal channels
$\Phi^{\ell}_{1}=\Phi^{\ell}_{\operatorname{Tr}}$ and
$\Phi^{\ell}_{2}=\Phi^{\ell}_{\mathrm{UNOT}}$, respectively, see Sections 4.2
and 4.3. More generally, tensors and tensor networks with $\mathrm{SU}(2)$
symmetry have been considered in [SV12] and are known as _spin networks_
[Bae96] in the context of loop quantum gravity.

Our results originally appeared as a talk in QIP 2021 [BLM+21].

###  1.4 Open problems

While our work settles the problem of computing all symmetric equivariant
Boolean functions in a basis-independent way, it also opens up many
interesting new directions.

  1. 1.

The patterns exhibited by the exact numerical values of the optimal fidelity
in Section 5.1.2 resemble the behavior of quantum query complexity
$\mathsf{Q}(f)$ for symmetric Boolean functions $f$ [BBC+01]. Is there a
closer relationship between the optimal fidelity $F_{f}$ and the quantum query
complexity $\mathsf{Q}(f)$ of equivariant Boolean functions $f$?

  2. 2.

It should be possible to find a closed-form solution for the linear program
(LP) in Theorem 4.7 that characterizes the optimal fidelity.

  3. 3.

Although we focus on Boolean functions, the problem can be considered for any
alphabet with $d\geq 2$ symbols (see Section 2.2). For example, a _universal
inverter_ that generalizes the qubit universal $\mathrm{NOT}$ operation can be
considered in arbitrary dimension [RBC+01]. It is also interesting to consider
generalizations to functions with several outputs For example, quantum cloning
[BBH01, SIGA05] and other unitary-equivariant primitives [Key02] naturally fit
into this framework. We expect that the recent optimization framework of
[GO22] could be very useful for these types of problems.

  4. 4.

Investigate in more depth the notion of unitary-equivariant Boolean functions
introduced in Section 5.3. Does this concept also extend to non-symmetric
Boolean functions? How about functions over the alphabet $[d]$, for any $d\geq
2$? Does it also extend to relations?

  5. 5.

On a high level, our algorithm applies Schur transform and measures the
partition label $\lambda$ (i.e., performs _weak Schur sampling_), and then
post-processes the leftover state on the unitary register. However, the post-
processing assumes that the unitary register is in the so-called
_Gelfand–Tsetlin basis_ [GT88], see Section C.1. While most implementations of
Schur transform (in particular, [KS18]) guarantee this, some do not [Kro19].
Can our algorithm be adapted so that the type of Schur transform used does not
matter?

One possible route towards this could be to explicitly apply the inverse Schur
transform at the end of the algorithm. Currently, we discard the maximally
mixed state from the permutation register and obtain the output by processing
the unitary register. Could one instead replace the permutation register by
some pure state and apply the universal NOT directly onto the unitary
register? Then one could hope to obtain the desired output by performing the
inverse Schur transform and discarding all qubits but one.

Alternatively, could Schur transform be eliminated altogether? For example,
weak Schur sampling can instead be implemented via generalized phase
estimation [Har05, Section 8.1]. Unfortunately, without going to Schur basis
it is not clear how to discard or replace the permutation register. Moreover,
the post-processing step also needs to be modified. While implementing the
partial trace channel in the standard basis is trivial, one also needs to
implement the universal $\mathrm{NOT}$ operation with a multi-qubit input. Can
this be done without Schur transform?

  6. 6.

Our algorithm appears to extract some classical side-information about the
input state while still achieving optimal output fidelity. What does this
information contain and could it be used for anything? For example, the side-
information produced by an optimal algorithm for the universal $\mathrm{NOT}$
operation contains a full classical description of the output state, implying
that any number of copies of the output state can be produced with the same
fidelity. Understanding, for other Boolean functions, the trade-off between
the optimal fidelity and how much classical side-information or how many
additional copies of the output state can be produced could have cryptographic
applications. Indeed, our setup in Fig. 1 suggests a cryptographic
interpretation: Alice is delegating the computation of $f$ to Bob while trying
to hide her input $x$ and the output $f(x)$ from him.

  7. 7.

While our quantum majority vote problem can be interpreted as amplifying the
correct output of a quantum device, this device has a somewhat contrived
failure mode: whenever it fails to produce the ideal state $|{\psi}\rangle$,
it outputs a perfectly orthogonal state $|{\psi^{\perp}}\rangle$ (see Fig. 2).
A more natural setting instead would be to have the input states randomly
distributed around some unknown ideal state $|{\psi}\rangle$. _Quantum
averaging_ is then the problem of producing an approximate copy of the ideal
state $|{\psi}\rangle$. Presumably our quantum majority vote algorithm is
optimal also for quantum averaging. However, we do not know how its output
fidelity scales with the number of input states and their variance around the
ideal state $|{\psi}\rangle$.

  8. 8.

Various unitary-equivariant operations, such as approximations of universal
$\mathrm{NOT}$ and quantum cloning, have been implemented experimentally
[DMS12]. Quantum majority vote could be a useful primitive for reducing
experimental errors and cleaning up noisy quantum data. More generally, an
experimental implementation of our template algorithm
$\mathcal{A}_{\mathbf{t}}$ (see Section 4.4) would allow to optimally evaluate
any symmetric and equivariant Boolean function on quantum data.

###  1.5 Outline

This paper is structured as follows. Section 1 motivates the problem and
summarizes our main results. Section 2 formally states the problem and
analyzes its symmetries. Section 3 discusses Schur–Weyl duality and constructs
a particularly nice orthonormal Schur basis for the $n$-qubit space. These
ingredients are then used to derive a generic pre-processing procedure that
can be used without loss of generality as the first step for computing any
symmetric and equivariant Boolean function. Section 4 describes the second
step of the algorithm and derives our main results, Theorems 4.6, 4.7 and 4.8,
which describe the optimal algorithm, its fidelity, and implementation.
Section 5 considers various applications of our general framework, such as
exactly computing the optimal fidelities for all Boolean functions with $n\leq
7$ arguments and analyzing the asymptotic fidelity of the quantum majority
vote.

This paper also contains a number of appendices with detailed calculations and
extended background material. Appendix A introduces graphical notation and
Appendix B analyzes our preferred Schur basis $|{(\lambda,w,i)}\rangle$.
Appendix C is a pedagogical introduction to the representation theory of
$2\times 2$ matrices, with an emphasis on explicit constructions. Appendix D
discusses the symmetric subspace and its representation-theoretic properties,
and Appendix E derives quantum circuits for implementing certain extremal
unitary-covariant quantum channels needed in our algorithm. Finally, Appendix
F proves that the optimal fidelity is monotonic in the Hamming weight, and
Appendix G explicitly lists optimal Choi matrices for computing all symmetric
equivariant Boolean functions with $n\leq 3$ arguments.

##  2 Preliminaries

This section covers some preliminary material and sets up the problem. First,
in Section 2.1 we introduce notation, basic concepts, and terminology. Next,
in Section 2.2, we formally state the problem in a general setting and then,
in Section 2.3, specialize to Boolean functions. In Section 2.4, we
demonstrate the impossibility of perfectly computing quantum majority on three
inputs. Finally, we describe symmetries of optimal quantum algorithms in
Section 2.5.

###  2.1 Mathematical preliminaries

##### Linear algebra.

Fix an integer $d\geq 2$ and let $[d]:=\\{0,\dotsc,d-1\\}$. We denote the
_standard basis_ of $\mathbb{C}^{d}$ by $|{i}\rangle$ where $i\in[d]$. Then
$\mathbb{C}^{d}=\operatorname{span}\\{|{i}\rangle:i\in[d]\\}$ where
“$\operatorname{span}$” denotes the _complex linear span_. We write
$\mathrm{L}(\mathbb{C}^{d})$ to denote the set of all _linear operators_ on
$\mathbb{C}^{d}$, i.e., the set of all $d\times d$ matrices over $\mathbb{C}$,
and we let $I_{d}:=\sum_{i\in[d]}|{i}\rangle\langle{i}|$ denote the $d\times
d$ _identity matrix_. We denote the _commutator_ of
$A,B\in\mathrm{L}(\mathbb{C}^{d})$ by $[A,B]:=AB-BA$. The _partial trace_ over
the first register, denoted
$\operatorname{Tr}_{1}:\mathrm{L}(\mathbb{C}^{d_{1}}\otimes\mathbb{C}^{d_{2}})\to\mathrm{L}(\mathbb{C}^{d_{2}})$,
is defined as $\operatorname{Tr}_{1}(A\otimes B):=\operatorname{Tr}(A)B$, for
any $A\in\mathrm{L}(\mathbb{C}^{d_{1}})$ and
$B\in\mathrm{L}(\mathbb{C}^{d_{2}})$, and extended by linearity to non-product
operators. The partial trace over the second register,
$\operatorname{Tr}_{2}$, is defined similarly. The _unitary group_
$\mathrm{U}(d):=\\{U\in\mathrm{L}(\mathbb{C}^{d}):UU^{\dagger}=I_{d}\\}$
consists of all $d\times d$ _unitary matrices_ , where
$U^{\dagger}:=\overline{U}^{\mathsf{T}}$ denotes the _conjugate transpose_ of
$U$. The _special unitary group_
$\mathrm{SU}(d):=\\{U\in\mathrm{U}(d):\det(U)=1\\}$ consists of all unitary
matrices with determinant one. We write
$\mathrm{L}(\mathbb{C}^{d_{\mathrm{in}}},\mathbb{C}^{d_{\mathrm{out}}})$ to
denote all _linear operators_ from $\mathbb{C}^{d_{\mathrm{in}}}$ to
$\mathbb{C}^{d_{\mathrm{out}}}$. When
${d_{\mathrm{in}}}\leq{d_{\mathrm{out}}}$, the set of all _isometries_ is
$\mathrm{U}(\mathbb{C}^{d_{\mathrm{in}}},\mathbb{C}^{d_{\mathrm{out}}}):=\\{U\in\mathrm{L}(\mathbb{C}^{d_{\mathrm{in}}},\mathbb{C}^{d_{\mathrm{out}}}):U^{\dagger}U=I_{d_{\mathrm{in}}}\\}$.

##### Representation theory.

A $d$-dimensional _representation_ of a group $G$ is a map
$R:G\to\mathrm{U}(d)$ such that $R(gh)=R(g)R(h)$ for all $g,h\in G$ (i.e., $R$
is a _homomorphism_ from $G$ to $\mathrm{U}(d)$). It is _reducible_ if
$UR(g)U^{\dagger}=R_{1}(g)\oplus R_{2}(g)$ for some $U\in\mathrm{U}(d)$ and
representations $R_{1}$ and $R_{2}$, and _irreducible_ otherwise. The _dual
representation_ of $R$ is defined as $R^{*}(g):=R(g^{-1})^{\mathsf{T}}$, for
all $g\in G$. Since $R$ is a homomorphism, $R(g^{-1})=R(g)^{-1}$ for any $g\in
G$. Since $R$ is unitary, i.e., $R(g)\in\mathrm{U}(d)$, we have
$R^{*}(g)=R(g^{-1})^{\mathsf{T}}=\big{\lparen}R(g)^{-1}\big{\rparen}^{\mathsf{T}}=\big{\lparen}R(g)^{\dagger}\big{\rparen}^{\mathsf{T}}=\overline{R(g)}$.333While
$R^{*}(g)=\overline{R(g)}$ for all $g\in G$, we make a distinction between
$R^{*}(g)$ and $\overline{R(g)}$ since they might differ when $R$ is extended
beyond $G$. For example, if $G=\mathrm{U}(1)\subset\mathbb{C}$ and $R(z):=z$
for all $z\in\mathrm{U}(1)$, we have $R^{*}(z)=1/z$ while
$\overline{R(z)}=\overline{z}$ for $z\in\mathbb{C}$, so the two maps differ
when $R$ is extended from the unit circle to the whole complex plane. The
following lemma by Schur is an important tool in representation theory.

######  Lemma 2.1 (Schur’s Lemma).

Let $R_{1}$ and $R_{2}$ be irreducible representations of dimension $d_{1}$
and $d_{2}$ of some group $G$. Assume that $M$ is a $d_{1}\times d_{2}$
complex matrix such that $R_{1}(g)M=MR_{2}(g)$, for all $g\in G$. Then

  * •

if $R_{1}$ and $R_{2}$ are isomorphic then $d_{1}=d_{2}=:d$ and $M=cI_{d}$ for
some $c\in\mathbb{C}$ where $I_{d}$ is the $d\times d$ identity matrix;

  * •

if $R_{1}$ and $R_{2}$ are not isomorphic then $M=0$.

Since the representation theory of $\mathrm{SU}(2)$ and $\mathrm{U}(2)$ is
particularly important to us, we provide a self-contained introduction in
Appendix C and a brief refresher in Section 4.1.

##### Action of the symmetric group.

The _symmetric group_ $\mathrm{S}_{n}$ on $n\geq 1$ elements consists of all
$n$-element permutations. For any permutation $\pi\in\mathrm{S}_{n}$, let
$P(\pi)\in\mathrm{U}(d^{n})$ denote the permutation matrix whose action on the
standard basis of $(\mathbb{C}^{d})^{\otimes n}$ is given by

$P(\pi)\;|{x_{1}}\rangle\otimes\dotsb\otimes|{x_{n}}\rangle:=|{x_{\pi^{-1}(1)}}\rangle\otimes\dotsb\otimes|{x_{\pi^{-1}(n)}}\rangle,\qquad\forall
x\in[d]^{n},$ (2.1)

meaning that $P(\pi)$ permutes the $n$ qudits (or terms in the tensor product)
according to the permutation $\pi$. The map
$P:\mathrm{S}_{n}\to\mathrm{U}(d^{n})$ is a representation of the symmetric
group $\mathrm{S}_{n}$.

##### Bloch sphere representation of qubit states.

Any _pure_ single-qubit state $|{\psi}\rangle\in\mathbb{C}^{2}$ can be written
(up to a global phase) as

$|{\psi}\rangle=\begin{pmatrix}\cos\frac{\theta}{2}\\\
e^{i\varphi}\sin\frac{\theta}{2}\end{pmatrix},$ (2.2)

for some $\theta\in[0,\pi]$ and $\varphi\in[0,2\pi)$. To also capture _mixed_
states, we instead use a _density matrix_ $\rho\in\mathrm{L}(\mathbb{C}^{2})$
such that $\rho\geq 0$ (i.e., $\rho$ is positive semidefinite) and
$\operatorname{Tr}\rho=1$. Any such $\rho$ is of the form

$\rho(\vec{r}):=\frac{1}{2}\begin{pmatrix}1+z&x-iy\\\ x+iy&1-z\end{pmatrix},$
(2.3)

for some _Bloch vector_ $\vec{r}:=(x,y,z)\in\mathbb{R}^{3}$ with
$x^{2}+y^{2}+z^{2}\leq 1$. By solving $\rho=|{\psi}\rangle\langle{\psi}|$, we
see that the angles $\theta,\varphi$ of a pure state $|{\psi}\rangle$ are
related to the spherical coordinates $x=\sin\theta\cos\varphi$,
$y=\sin\theta\sin\varphi$, $z=\cos\theta$ of the point $(x,y,z)$. Hence, pure
states $\rho(\vec{r})$ correspond to unit vectors $\vec{r}\in\mathbb{R}^{3}$
and form the so-called _Bloch sphere_. The _uniform measure_ on the Bloch
sphere is given by

$d\psi:=\frac{1}{4\pi}\sin\theta\,d\theta\,d\varphi,$ (2.4)

which induces via eq. 2.2 a uniform measure on pure single-qubit states
$|{\psi}\rangle\in\mathbb{C}^{2}$. Note that $d\psi$ is normalized so that
$\int d\psi=1$. If $\rho(\vec{r})$ is pure, its unique orthogonal state is
$\rho(-\vec{r})$ since
$\operatorname{Tr}[\rho(\vec{r}_{1})\rho(\vec{r}_{2})]=(1+x_{1}x_{2}+y_{1}y_{2}+z_{1}z_{2})/2=0$
precisely when $\vec{r}_{1}=-\vec{r}_{2}$.

##### Choi matrix and CPTP maps.

Recall the following standard terminology and basic facts from quantum
information theory [Wat18]. We refer to linear maps of the form
$\Phi:\mathrm{L}(\mathbb{C}^{d_{\mathrm{in}}})\to\mathrm{L}(\mathbb{C}^{d_{\mathrm{out}}})$
as _superoperators_. The _Choi matrix_
$J(\Phi)\in\mathrm{L}(\mathbb{C}^{d_{\mathrm{out}}}\otimes\mathbb{C}^{d_{\mathrm{in}}})$
of a superoperator $\Phi$ is defined as

$J(\Phi):=\sum_{i,j\in[{d_{\mathrm{in}}}]}\Phi\big{\lparen}|{i}\rangle\langle{j}|\big{\rparen}\otimes|{i}\rangle\langle{j}|.$
(2.5)

The action of $\Phi$ on any $\rho\in\mathrm{L}(\mathbb{C}^{d_{\mathrm{in}}})$
can be recovered from its Choi matrix $J(\Phi)$ as follows:

$\Phi(\rho)=\operatorname{Tr}_{2}\big{[}J(\Phi)\cdot\lparen
I_{d_{\mathrm{out}}}\otimes\rho^{\mathsf{T}}\rparen\big{]},$ (2.6)

where we discard the second register that corresponds to the input system. If
a Choi matrix $J(\Phi)$ is subject to

$\displaystyle J(\Phi)$ $\displaystyle\geq 0,$
$\displaystyle\operatorname{Tr}_{1}J(\Phi)=I_{d_{\mathrm{in}}},$ (2.7)

the corresponding map $\Phi$ is called _completely positive_ (CP) and _trace-
preserving_ (TP), respectively. If both properties are satisfied
simultaneously, the map is called CPTP or a _quantum channel_. Such maps are
precisely the operations that can in principle be implemented on a quantum
computer. We denote the set of all CPTP maps with given input and output
dimensions by
$\mathrm{C}(\mathbb{C}^{d_{\mathrm{in}}},\mathbb{C}^{d_{\mathrm{out}}})$. In
addition to the Choi matrix, quantum channels admit other representations,
such as _Kraus_ and _Stinespring_ , which are described in Section E.1.

##### Quantum circuits and algorithms.

A _quantum circuit_ is a sequence of elementary quantum operations, where each
operation either applies a unitary gate on at most two quantum systems,
introduces an additional ancillary system initialized in $|{0}\rangle$, or
discards a system that is no longer needed. Any such circuit implements a CPTP
map. A _quantum algorithm_ is a uniform sequence of quantum circuits, meaning
that a single Turing machine can produce any of the circuits upon receiving
the corresponding problem size $n$ as its input. A quantum algorithm is
_efficient_ if the corresponding Turing machine runs in $\mathrm{poly}(n)$
time. While every quantum algorithm corresponds to a family of CPTP maps, not
every such family can be implemented by an efficient quantum algorithm. We
will use the term “quantum algorithm” as opposed to “quantum channel” whenever
we want to stress that our goal is to explicitly implement the underlying
family of CPTP maps as a sequence of elementary quantum operations.

###  2.2 Computing functions in a basis-independent way

In this section, we formalize the problem of computing a function whose input
is provided in an unknown quantum basis. We also specify the figure of merit
used to measure the performance of a quantum algorithm for this task.

Fix a unitary $U\in\mathrm{U}(d)$ of dimension $d\geq 2$ and a string
$x\in[d]^{n}$ of length $n\geq 1$ over the alphabet $[d]=\\{0,\dotsc,d-1\\}$.
One can think of the state $U^{\otimes n}|{x}\rangle$ or its density matrix

$\rho^{U}_{x}:=U^{\otimes n}|{x}\rangle\langle{x}|U^{\dagger\otimes n}$ (2.8)

as a quantum encoding of the string $x$ in the basis given by $U$. Given this
state and a function $f:[d]^{n}\to[d]$, we would like to find a quantum
algorithm that computes $f$ and outputs the answer $f(x)$ in the same basis as
the input. In other words, we want a quantum algorithm that approximates the
map

$U^{\otimes n}|{x}\rangle\mapsto U|{f(x)}\rangle,$ (2.9)

for any unknown unitary $U\in\mathrm{U}(d)$ and string $x\in[d]^{n}$. For each
$n$, such algorithm is described by a CPTP map $\Phi$ from $n$ qudits to $1$
qudit.

Let $F(|{\psi}\rangle,\rho):=\langle{\psi}|\rho|{\psi}\rangle$ denote the
_fidelity_ between a mixed state $\rho$ and a pure state $|{\psi}\rangle$ of
the same dimension. The following definition formalizes the worst-case
fidelity for computing a function in a basis-independent way on a quantum
computer. Determining this fidelity and deriving the corresponding optimal
quantum algorithm is the main goal of this paper.

######  Definition 2.2 (Fidelity for computing $f$).

Let $f:[d]^{n}\to[d]$ be a function and
$\Phi\in\mathrm{C}(\mathbb{C}^{d^{n}},\mathbb{C}^{d})$ a CPTP map for
computing $f$. For a particular input string $x\in[d]^{n}$ and a single-qudit
unitary $U\in\mathrm{U}(d)$, the _fidelity of $\Phi$ for computing $f$ on
input $x$ in basis $U$_ is

$F\big{\lparen}U|{f(x)}\rangle,\Phi(\rho^{U}_{x})\big{\rparen}:=\langle{f(x)}|U^{\dagger}\Phi(\rho^{U}_{x})U|{f(x)}\rangle.$
(2.10)

The _(worst-case) fidelity of $\Phi$ for computing $f$_ is

$F_{f}(\Phi):=\min_{\begin{subarray}{c}x\in[d]^{n}\\\
U\in\mathrm{U}(d)\end{subarray}}F\big{\lparen}U|{f(x)}\rangle,\Phi(\rho^{U}_{x})\big{\rparen},$
(2.11)

and the _optimal fidelity for computing $f$ in a basis-independent way_ is

$F_{f}:=\max_{\Phi\in\mathrm{C}(\mathbb{C}^{d^{n}},\mathbb{C}^{d})}F_{f}(\Phi).$
(2.12)

A CPTP map $\Phi$ is _optimal for computing $f$_ if $F_{f}(\Phi)=F_{f}$.

Note that the ideal functionality in eq. 2.9 is not well-defined for all
functions $f:[d]^{n}\to[d]$. To see this, consider any non-trivial permutation
matrix $M\in\mathrm{U}(d)$ that relabels the symbols in $[d]$. Then
$M^{\otimes n}|{x}\rangle=|{x^{\prime}}\rangle$ for some other string
$x^{\prime}\in[d]^{n}$. Since the unitary basis change $M$ is not explicitly
included as part of the input, it is not possible to tell whether the actual
argument of $f$ should be $x$ or $x^{\prime}$, so on one hand the correct
output should be $M|{f(x)}\rangle$ while on the other hand it should be
$|{f(x^{\prime})}\rangle$. Hence, the ideal functionality of the algorithm for
a given function $f$ is well-defined only when these two states agree for any
permutation $M$ of $[d]$ (this is equivalent to the function $f$ being
_equivariant_ , see Definition 2.3 below).

Although formally Definition 2.2 makes sense for any function
$f:[d]^{n}\to[d]$, we focus specifically on equivariant functions, since for
this class of functions the ideal functionality in eq. 2.9 is well-defined.
Moreover, we further restrict our attention to _symmetric_ functions (see
Definition 2.3 below). While this restriction is not necessary and the problem
can also be studied for non-symmetric functions, assuming symmetry
significantly simplifies the analysis by enabling the use of the so-called
_Schur–Weyl duality_ (see Section 3.1).

######  Definition 2.3 (Symmetric and equivariant functions).

A function $f:[d]^{n}\to[d]$ is _symmetric_ if

$f\big{\lparen}x_{\pi^{-1}(1)},\dotsc,x_{\pi^{-1}(n)}\big{\rparen}=f(x),\qquad\forall
x\in[d]^{n},\quad\forall\pi\in\mathrm{S}_{n},$ (2.13)

where $\pi$ permutes the characters in the string $x$, and _equivariant_ if

$f\big{\lparen}\sigma(x_{1}),\dotsc,\sigma(x_{n})\big{\rparen}=\sigma\big{\lparen}f(x)\big{\rparen},\qquad\forall
x\in[d]^{n},\quad\forall\sigma\in\mathrm{S}_{d},$ (2.14)

where $\sigma$ relabels the symbols in the alphabet $[d]$.

###  2.3 Symmetric and equivariant Boolean functions

The main focus of this paper is the $d=2$ case of Boolean functions. Since the
only non-trivial permutation of $\\{0,1\\}$ is the negation
$\mathrm{NOT}(a):=a\oplus 1$, where $a\in\\{0,1\\}$ and “$\oplus$” denotes the
bit-wise addition modulo $2$, equivariant Boolean functions have a
particularly simple characterization – they are invariant under simultaneously
negating all input and output bits. Alluding to the duality between
$\mathrm{AND}$ and $\mathrm{OR}$ established by De Morgan’s laws, such
functions are also known as _self-dual_.

######  Definition 2.4 (Equivariant or self-dual Boolean functions).

A Boolean function $f:\\{0,1\\}^{n}\to\\{0,1\\}$ is _equivariant_ or _self-
dual_ if

$f(x\oplus 1^{n})=f(x)\oplus 1,\qquad\forall x\in\\{0,1\\}^{n},$ (2.15)

where $1^{n}$ denotes the string of $n$ ones and “$\oplus$” denotes the bit-
wise addition modulo $2$.

To fully determine a symmetric Boolean function, it is enough to specify its
value only on one input string for each possible Hamming weight. Thus one can
replace a symmetric $n$-argument Boolean function
$f:\\{0,1\\}^{n}\to\\{0,1\\}$ by a function
$\bar{f}:\\{0,\dotsc,n\\}\to\\{0,1\\}$ whose argument is the Hamming weight of
the original input string: $\bar{f}(|x|):=f(x)$, for all $x\in\\{0,1\\}$.

If a symmetric function $f$ is also equivariant, the following constraint is
imposed on $\bar{f}$:

$\bar{f}(h)=\bar{f}(n-h)\oplus 1,\qquad\forall h\in\\{0,\dotsc,n\\}.$ (2.16)

This constraint cannot be satisfied when $n$ is even since
$\bar{f}(n/2)=\bar{f}(n/2)\oplus 1$ is not possible. Hence, it is only
meaningful to consider the case of _odd_ $n$.

While we will not do this here, an alternative option is to consider relations
instead of functions when $n$ is even. For example, the majority relation can
output either $0$ or $1$ when the Hamming weight of the input is exactly
$n/2$. We expect that our results can be easily extended to this variation of
the problem.

######  Example 2.5 (Majority and parity).

We are particularly interested in the $n$-bit _majority_ function
$\mathrm{MAJ}_{n}$ that returns the value that appears the most often in the
input string. Another interesting function is the $n$-bit _parity_ :

$\displaystyle\mathrm{PAR}_{n}(x_{1},\dotsc,x_{n}):=x_{1}\oplus\dotsb\oplus
x_{n},\qquad\forall x\in\\{0,1\\}^{n}.$ (2.17)

It is evident that $\mathrm{MAJ}_{n}$ and $\mathrm{PAR}_{n}$ are symmetric and
(when $n$ is odd) equivariant. All symmetric and equivariant Boolean functions
on $n=1$ and $n=3$ bits are summarized in Table 1.

$x$ | $\mathrm{ID}$ | $\mathrm{NOT}$
---|---|---
0 | 0 | 1

$x$ | $\mathrm{MAJ}_{3}$ | $\mathrm{PAR}_{3}$ | $\mathrm{NPAR}_{3}$ | $\mathrm{NMAJ}_{3}$
---|---|---|---|---
000 | 0 | 0 | 1 | 1
001 | 0 | 1 | 0 | 1

Table 1: All $1$-bit and $3$-bit symmetric equivariant Boolean functions. For
$1$-bit functions, it is sufficient to list their values only on the input
$0$, while for $3$-bit functions only the strings $000$ and $001$ are
sufficient (on all other strings the value can be inferred from symmetry and
equivariance). Here we use the notation
$\mathrm{NMAJ}_{n}(x):=\mathrm{NOT}\lparen\mathrm{MAJ}_{n}(x)\rparen$ and
$\mathrm{NPAR}_{n}(x):=\mathrm{NOT}\lparen\mathrm{PAR}_{n}(x)\rparen$.

###  2.4 Impossibility of perfect quantum majority

Let us consider an example of computing quantum majority on three qubits, and
show that no quantum algorithm can achieve this task perfectly.

A perfect algorithm would have to work correctly on all inputs. In particular,
for the standard basis states we should have

$W|{x}\rangle|{\Omega}\rangle=|{\mathrm{MAJ}_{3}(x)}\rangle|{\mathrm{j}_{x}}\rangle,\qquad\forall
x\in\\{0,1\\}^{3},$ (2.18)

where $W$ is an isometry (Stinespring dilation) that fully describes the
algorithm. The algorithm may use an additional ancillary system, which is
initialized in some fixed state $|{\Omega}\rangle$, and produce some junk
states $|{\mathrm{j}_{x}}\rangle$ that are discarded once the computation is
finished. More explicitly:

$\displaystyle\begin{aligned}
W|{000}\rangle|{\Omega}\rangle&=|{0}\rangle|{\mathrm{j}_{000}}\rangle,\\\
W|{001}\rangle|{\Omega}\rangle&=|{0}\rangle|{\mathrm{j}_{001}}\rangle,\\\
W|{010}\rangle|{\Omega}\rangle&=|{0}\rangle|{\mathrm{j}_{010}}\rangle,\\\
W|{100}\rangle|{\Omega}\rangle&=|{0}\rangle|{\mathrm{j}_{100}}\rangle,\end{aligned}$
$\displaystyle\begin{aligned}
W|{111}\rangle|{\Omega}\rangle&=|{1}\rangle|{\mathrm{j}_{111}}\rangle,\\\
W|{110}\rangle|{\Omega}\rangle&=|{1}\rangle|{\mathrm{j}_{110}}\rangle,\\\
W|{101}\rangle|{\Omega}\rangle&=|{1}\rangle|{\mathrm{j}_{101}}\rangle,\\\
W|{011}\rangle|{\Omega}\rangle&=|{1}\rangle|{\mathrm{j}_{011}}\rangle.\end{aligned}$
(2.19)

Since $W$ is an isometry, all the $|{\mathrm{j}_{x}}\rangle$ are normalized.
Moreover, the $|{\mathrm{j}_{x}}\rangle$ with a majority of $0$’s amongst
$x_{1},x_{2},x_{3}\in\\{0,1\\}$ are all orthogonal to each other, as are the
$|{\mathrm{j}_{x}}\rangle$ with a majority of $1$’s.

Now consider the “all qubits equal” state in an arbitrary basis:

$|{\Psi}\rangle:=\big{\lparen}\alpha|{0}\rangle+\beta|{1}\rangle\big{\rparen}\otimes\big{\lparen}\alpha|{0}\rangle+\beta|{1}\rangle\big{\rparen}\otimes\big{\lparen}\alpha|{0}\rangle+\beta|{1}\rangle\big{\rparen}$
(2.20)

where $\alpha|{0}\rangle+\beta|{1}\rangle\in\mathbb{C}^{2}$ is an arbitrary
single-qubit state. Then by linearity and eq. 2.19,

$\displaystyle
W|{\Psi}\rangle|{\Omega}\rangle=\alpha|{0}\rangle\big{\lparen}\alpha^{2}|{\mathrm{j}_{000}}\rangle$
$\displaystyle+\alpha\beta|{\mathrm{j}_{001}}\rangle+\alpha\beta|{\mathrm{j}_{010}}\rangle+\alpha\beta|{\mathrm{j}_{100}}\rangle\big{\rparen}$
(2.21)
$\displaystyle{}+\beta|{1}\rangle\big{\lparen}\beta^{2}|{\mathrm{j}_{111}}\rangle$
$\displaystyle+\alpha\beta|{\mathrm{j}_{110}}\rangle+\alpha\beta|{\mathrm{j}_{101}}\rangle+\alpha\beta|{\mathrm{j}_{011}}\rangle\big{\rparen}.$

For this to be the correct outcome of the majority, we need the two junk
states

$\displaystyle\begin{aligned}
|{\mathrm{J}_{0}}\rangle&:=\big{\lparen}\alpha^{2}|{\mathrm{j}_{000}}\rangle+\alpha\beta|{\mathrm{j}_{001}}\rangle+\alpha\beta|{\mathrm{j}_{010}}\rangle+\alpha\beta|{\mathrm{j}_{100}}\rangle\big{\rparen},\\\
|{\mathrm{J}_{1}}\rangle&:=\big{\lparen}\beta^{2}|{\mathrm{j}_{111}}\rangle+\alpha\beta|{\mathrm{j}_{110}}\rangle+\alpha\beta|{\mathrm{j}_{101}}\rangle+\alpha\beta|{\mathrm{j}_{011}}\rangle\big{\rparen}\end{aligned}$
(2.22)

to be equal. But for general $\alpha$ and $\beta$ they are not since their
norms are different. Thus there is no perfect algorithm for quantum majority
of $n=3$ states. A similar argument can show that there is also no perfect
algorithm for quantum majority for any $n\geq 3$ states.

According to the above argument, a linear map that implements the ideal
operation

$U^{\otimes n}|{x}\rangle\langle{x}|U^{\dagger\otimes n}\mapsto
U|{\mathrm{MAJ}_{n}(x)}\rangle\langle{\mathrm{MAJ}_{n}(x)}|U^{\dagger}$ (2.23)

for any $n\geq 3$ cannot be completely positive since it has no Stinespring
dilation $W$. The same conclusion can be easily reached also for the ideal
universal $\mathrm{NOT}$ operation. Let $\vec{r}\in\mathbb{R}^{3}$ be an
arbitrary unit vector on the Bloch sphere and $\rho(\vec{r})$ the
corresponding density matrix given in eq. 2.3. Since the unique pure state
orthogonal to $\rho(\vec{r})$ has density matrix $\rho(-\vec{r})$, the Choi
matrix $J(\mathrm{UNOT})\in\mathrm{L}(\mathbb{C}^{4})$ for the ideal universal
$\mathrm{NOT}$ operation must satisfy

$\operatorname{Tr}_{2}\big{[}J\cdot(I_{2}\otimes\rho(\vec{r})^{\mathsf{T}})\big{]}=\rho(-\vec{r})$
(2.24)

for all $\vec{r}=(x,y,z)$. Comparing the coefficients at $x,y,z$, we find the
unique solution to be

$J(\mathrm{UNOT})=\begin{pmatrix}0&0&0&-1\\\ 0&1&0&0\\\ 0&0&1&0\\\
-1&0&0&0\end{pmatrix}.$ (2.25)

Since its eigenvalues are $(-1,1,1,1)$, the ideal universal $\mathrm{NOT}$
operation is not completely positive and hence cannot be implemented on a
quantum computer. Nevertheless, as an abstract superoperator it is still
meaningful.

We discuss this perspective more in Section 5.3, where we also point out that
the ideal superoperator appears to be unique for any symmetric and equivariant
Boolean function. Moreover, in Section G.2 we provide explicit Choi matrices
for the ideal superoperators of all symmetric and equivariant Boolean
functions with $n=1$ and $n=3$ arguments.

###  2.5 Symmetries of optimal algorithms

Let us show that an optimal quantum algorithm for computing any symmetric
function $f:[d]^{n}\to[d]$ in a basis-independent way can always be chosen so
that it is equivariant with respect to the unitary group $\mathrm{U}(d)$ and
symmetric with respect to the permutation group $\mathrm{S}_{n}$.

To formalize this, let $\Phi\in\mathrm{C}(\mathbb{C}^{d^{n}},\mathbb{C}^{d})$
be a quantum channel and consider two different symmetrized versions of
$\Phi$, one over the symmetric group and the other over the unitary group:

$\displaystyle\Phi_{P}(\rho)$
$\displaystyle:=\sum_{\pi\in\mathrm{S}_{n}}\frac{1}{n!}\Phi\big{\lparen}P(\pi)\rho
P(\pi)^{\dagger}\big{\rparen},$ $\displaystyle\Phi_{Q}(\rho)$
$\displaystyle:=\int_{V\in\mathrm{U}(d)}V^{\dagger}\Phi\big{\lparen}V^{\otimes
n}\rho V^{\dagger\otimes n}\big{\rparen}VdV,$ (2.26)

where $P(\pi)$ permutes the $n$ tensor factors in
$\mathbb{C}^{d}\otimes\dotsb\otimes\mathbb{C}^{d}$ according to the
permutation $\pi$, see eq. 2.1, and $dV$ denotes the Haar measure on
$\mathrm{U}(d)$ normalized so that $\int_{V\in\mathrm{U}(d)}dV=1$. Notice that
$\Phi_{P}$ and $\Phi_{Q}$ are quantum channels since
$\mathrm{C}(\mathbb{C}^{d^{n}},\mathbb{C}^{d})$ is a convex set.

######  Lemma 2.6.

For any symmetric function $f:[d]^{n}\to[d]$ and any
$\Phi\in\mathrm{C}(\mathbb{C}^{d^{n}},\mathbb{C}^{d})$, the symmetrized
channels $\Phi_{P}$ and $\Phi_{Q}$ compute $f$ with fidelity no worse than the
original channel $\Phi$:

$\displaystyle F_{f}(\Phi_{P})$ $\displaystyle\geq F_{f}(\Phi),$
$\displaystyle F_{f}(\Phi_{Q})$ $\displaystyle\geq F_{f}(\Phi).$ (2.27)

###### Proof.

Recall from Definition 2.2 that $\Phi_{Q}$ computes $f$ with worst-case
fidelity

$F_{f}(\Phi_{Q})=\min_{\begin{subarray}{c}x\in[d]^{n}\\\
U\in\mathrm{U}(d)\end{subarray}}F\big{\lparen}U|{f(x)}\rangle,\Phi_{Q}(\rho^{U}_{x})\big{\rparen}.$
(2.28)

We can bound the fidelity function within the minimization as follows:

$\displaystyle\langle{f(x)}|U^{\dagger}\Phi_{Q}(\rho^{U}_{x})U|{f(x)}\rangle$
$\displaystyle=\int_{V\in\mathrm{U}(d)}\langle{f(x)}|U^{\dagger}\cdot
V^{\dagger}\Phi\big{\lparen}V^{\otimes n}\rho^{U}_{x}V^{\dagger\otimes
n}\big{\rparen}V\cdot U|{f(x)}\rangle\,dV$ (2.29)
$\displaystyle=\int_{V\in\mathrm{U}(d)}\langle{f(x)}|(VU)^{\dagger}\Phi\big{\lparen}(VU)^{\otimes
n}|{x}\rangle\langle{x}|(VU)^{\dagger\otimes
n}\big{\rparen}(VU)|{f(x)}\rangle\,dV$
$\displaystyle=\int_{V\in\mathrm{U}(d)}F\big{\lparen}VU|{f(x)}\rangle,\Phi(\rho^{VU}_{x})\big{\rparen}\,dV$
$\displaystyle\geq\int_{V\in\mathrm{U}(d)}F_{f}(\Phi)\,dV$
$\displaystyle=F_{f}(\Phi),$

where the inequality holds because of the minimization over $x\in[d]^{n}$ and
$U\in\mathrm{U}(d)$ within the definition of $F_{f}(\Phi)$. Since the above
calculation works for any $x$ and $U$, we get $F_{f}(\Phi_{Q})\geq
F_{f}(\Phi)$. The calculation for $\Phi_{P}$ is similar, except we symmetrize
over $\mathrm{S}_{n}$:

$\displaystyle\langle{f(x)}|U^{\dagger}\Phi_{P}(\rho^{U}_{x})U|{f(x)}\rangle$
$\displaystyle=\sum_{\pi\in\mathrm{S}_{n}}\frac{1}{n!}\langle{f(x)}|U^{\dagger}\Phi\big{\lparen}P(\pi)\rho^{U}_{x}P(\pi)^{\dagger}\big{\rparen}U|{f(x)}\rangle$
(2.30)
$\displaystyle=\sum_{\pi\in\mathrm{S}_{n}}\frac{1}{n!}\langle{f(x_{\pi})}|U^{\dagger}\Phi\lparen\rho^{U}_{x_{\pi}}\rparen
U|{f(x_{\pi})}\rangle$
$\displaystyle\geq\sum_{\pi\in\mathrm{S}_{n}}\frac{1}{n!}F_{f}(\Phi)$
$\displaystyle=F_{f}(\Phi),$

where $x_{\pi}$ is the string obtained by permuting the characters of $x$
according to $\pi$, and we used $f(x)=f(x_{\pi})$ in the second equality since
$f$ is symmetric. ∎

Due to Lemma 2.6, we are particularly interested in maps $\Phi$ that are
invariant under the symmetric group $\mathrm{S}_{n}$ and equivariant with
respect to the unitary group $\mathrm{U}(d)$. The following definition
generalizes $\mathrm{S}_{n}$-invariance from $n$-argument functions (see
Definition 2.3) to superoperators with $n$ input qudits.

######  Definition 2.7 (Permutation invariance).

Let $\mathcal{X}:=(\mathbb{C}^{d})^{\otimes n}$ be a tensor product input
space and $\mathcal{Y}$ an arbitrary output space. A linear map
$\Phi:\mathrm{L}(\mathcal{X})\to\mathrm{L}(\mathcal{Y})$ is _permutation-
invariant_ if

$\Phi(P(\pi)\rho
P(\pi)^{\dagger})=\Phi(\rho),\qquad\forall\rho\in\mathrm{L}(\mathcal{X}),\quad\forall\pi\in\mathrm{S}_{n},$
(2.31)

where $P(\pi)$ permutes $n$ qudits according to $\pi$, see eq. 2.1.

Similarly, we can also extend the notion of equivariance from functions (see
Definition 2.3) to superoperators by replacing functions $f:[d]^{n}\to[d]$
with superoperators from $n$ qudits to one qudit. Moreover, we extend the
discrete $\mathrm{S}_{d}$-equivariance to the continuous
$\mathrm{U}(d)$-equivariance.

######  Definition 2.8 (Unitary equivariance).

A linear map
$\Phi:\mathrm{L}(\mathbb{C}^{d^{n}})\to\mathrm{L}(\mathbb{C}^{d})$ is
_unitary-equivariant_ if

$\Phi(U^{\otimes n}\rho U^{\dagger\otimes
n})=U\Phi(\rho)U^{\dagger},\qquad\forall\rho\in\mathrm{L}(\mathbb{C}^{d^{n}}),\quad\forall
U\in\mathrm{U}(d).$ (2.32)

We will also need a slightly more general notion than the invariance under
applying $U$ to all input qudits and $U^{\dagger}$ to all output qudits. The
following definition accounts for arbitrary $\mathrm{U}(d)$-representations on
the input and output spaces.

######  Definition 2.9 (Unitary covariance).

Let $\mathcal{X}$ and $\mathcal{Y}$ be arbitrary linear spaces admitting some
$\mathrm{U}(d)$-representations
$R_{\mathrm{in}}:\mathrm{U}(d)\to\mathrm{U}(\mathcal{X})$ and
$R_{\mathrm{out}}:\mathrm{U}(d)\to\mathrm{U}(\mathcal{Y})$, respectively. A
linear map $\Phi:\mathrm{L}(\mathcal{X})\to\mathrm{L}(\mathcal{Y})$ is
_unitary-covariant_ if

$\Phi\big{\lparen}R_{\mathrm{in}}(U)\rho
R_{\mathrm{in}}(U)^{\dagger}\big{\rparen}=R_{\mathrm{out}}(U)\Phi(\rho)R_{\mathrm{out}}(U)^{\dagger},\qquad\forall\rho\in\mathrm{L}(\mathcal{X}),\quad\forall
U\in\mathrm{U}(d).$ (2.33)

We denote the set of all _unitary-covariant channels_ by
$\mathrm{UC}(\mathcal{X},\mathcal{Y})$.

Unitary equivariance corresponds to the special case when
$R_{\mathrm{in}}(U)=U^{\otimes n}$ and $R_{\mathrm{out}}(U)=U$. In all other
cases the $\mathrm{U}(d)$-representations $R_{\mathrm{in}}$ and
$R_{\mathrm{out}}$ will be clear from the context.

It can be easily verified that the CPTP maps $\Phi_{P}$ and $\Phi_{Q}$ in eq.
2.26 are permutation-invariant and unitary-equivariant, respectively. The
following corollary is a direct consequence of Lemma 2.6.

######  Corollary 2.10.

For any symmetric function $f:[d]^{n}\to[d]$, with $d\geq 2$ and $n\geq 1$,
there exists an optimal quantum algorithm
$\Phi\in\mathrm{C}(\mathbb{C}^{d^{n}},\mathbb{C}^{d})$ for computing $f$ in a
basis-independent way, such that $\Phi$ is permutation-invariant and unitary-
equivariant.

Our next goal is to characterize Choi matrices of unitary-equivariant maps.
The following lemma describes how the Choi matrix transforms under an
arbitrary input and output basis change of $\Phi$.

######  Lemma 2.11.

Let $\mathcal{X}$ and $\mathcal{Y}$ be linear spaces,
$\Phi:\mathrm{L}(\mathcal{X})\to\mathrm{L}(\mathcal{Y})$ a linear map, and let
$V\in\mathrm{L}(\mathcal{X})$ and $W\in\mathrm{L}(\mathcal{Y})$ be arbitrary
matrices. Then the Choi matrix for the map
$\Phi^{\prime}(\rho):=W^{\dagger}\Phi(V\rho V^{\dagger})W$ is

$J(\Phi^{\prime})=(W\otimes\overline{V})^{\dagger}J(\Phi)(W\otimes\overline{V}).$
(2.34)

###### Proof.

Recall from eq. 2.6 that the action of $\Phi$ on any
$\rho\in\mathrm{L}(\mathcal{X})$ can be expressed via its Choi matrix:
$\Phi(\rho)=\operatorname{Tr}_{2}\big{[}J(\Phi)\cdot\lparen
I_{d_{\mathrm{out}}}\otimes\rho^{\mathsf{T}}\rparen\big{]}$ where
${d_{\mathrm{out}}}:=\dim\mathcal{Y}$. If we modify the input of $\Phi$ by
conjugating it with $V$, the new output looks as follows:

$\displaystyle\Phi\lparen V\rho V^{\dagger}\rparen$
$\displaystyle=\operatorname{Tr}_{2}\Big{[}J(\Phi)\cdot\big{\lparen}I_{d_{\mathrm{out}}}\otimes\lparen
V\rho V^{\dagger}\rparen^{\mathsf{T}}\big{\rparen}\Big{]}$ (2.35)
$\displaystyle=\operatorname{Tr}_{2}\Big{[}J(\Phi)\cdot\big{\lparen}I_{d_{\mathrm{out}}}\otimes\lparen\overline{V}\rho^{\mathsf{T}}\overline{V}^{\dagger}\rparen\big{\rparen}\Big{]}$
(2.36)
$\displaystyle=\operatorname{Tr}_{2}\Big{[}J(\Phi)\cdot(I_{d_{\mathrm{out}}}\otimes\overline{V})\cdot(I_{d_{\mathrm{out}}}\otimes\rho^{\mathsf{T}})\cdot(I_{d_{\mathrm{out}}}\otimes\overline{V}^{\dagger})\Big{]}$
(2.37)
$\displaystyle=\operatorname{Tr}_{2}\Big{[}(I_{d_{\mathrm{out}}}\otimes\overline{V}^{\dagger})\cdot
J(\Phi)\cdot(I_{d_{\mathrm{out}}}\otimes\overline{V})\cdot(I_{d_{\mathrm{out}}}\otimes\rho^{\mathsf{T}})\Big{]},$
(2.38)

where the last equality follows from the cyclic property of the partial trace
(it is crucial here that the matrix
$I_{d_{\mathrm{out}}}\otimes\overline{V}^{\dagger}$ acts trivially on the
first register which is not traced out). If we also modify the output of
$\Phi$ by conjugating it with $W^{\dagger}$, we get

$\Phi^{\prime}(\rho)=W^{\dagger}\Phi\big{\lparen}V\rho
V^{\dagger}\big{\rparen}W=\operatorname{Tr}_{2}\Big{[}(W^{\dagger}\otimes\overline{V}^{\dagger})\cdot
J(\Phi)\cdot(W\otimes\overline{V})\cdot(I_{d_{\mathrm{out}}}\otimes\rho^{\mathsf{T}})\Big{]}$
(2.39)

after moving the basis change inside the partial trace. Since
$\Phi^{\prime}(\rho)=\operatorname{Tr}_{2}\big{[}J(\Phi^{\prime})\cdot\lparen
I_{d_{\mathrm{out}}}\otimes\rho^{\mathsf{T}}\rparen\big{]}$ and both formulas
hold for all $\rho\in\mathrm{L}(\mathcal{X})$, we conclude that
$J(\Phi^{\prime})=(W\otimes\overline{V})^{\dagger}J(\Phi)(W\otimes\overline{V})$.
∎

######  Corollary 2.12.

A linear map $\Phi:\mathrm{L}(\mathcal{X})\to\mathrm{L}(\mathcal{Y})$ is
unitary-covariant with respect to representations
$R_{\mathrm{in}}:\mathrm{U}(d)\to\mathrm{U}(\mathcal{X})$ and
$R_{\mathrm{out}}:\mathrm{U}(d)\to\mathrm{U}(\mathcal{Y})$ if and only if

$\big{[}J(\Phi),R_{\mathrm{out}}(\overline{U})\otimes
R_{\mathrm{in}}(U)\big{]}=0,\qquad\forall U\in\mathrm{U}(d).$ (2.40)

###### Proof.

According to Lemma 2.11, the unitary covariance condition from Definition 2.9
translates into

$J(\Phi)=\big{\lparen}R_{\mathrm{out}}(U)\otimes
R_{\mathrm{in}}(\overline{U})\big{\rparen}^{\dagger}J(\Phi)\big{\lparen}R_{\mathrm{out}}(U)\otimes
R_{\mathrm{in}}(\overline{U})\big{\rparen},\qquad\forall U\in\mathrm{U}(d),$
(2.41)

since $\overline{R(U)}=R(\overline{U})$ for any (polynomial) representation
$R$ of $\mathrm{U}(d)$. The result follows by substituting $U$ with
$\overline{U}$. ∎

It seems from eq. 2.11 that infinitely many different input states need to be
considered to determine the fidelity $F_{f}(\Phi)$ with which a given quantum
algorithm $\Phi$ computes a function $f$ in a basis-independent manner. It
turns out that in the cases relevant to us it suffices to consider a finite
list of inputs to determine this fidelity. Since our primary interest is in
Boolean functions, we restrict to $d=2$.

######  Lemma 2.13.

Let $f:\\{0,1\\}^{n}\to\\{0,1\\}$ be a symmetric and equivariant Boolean
function. A permutation-invariant and unitary-equivariant channel
$\Phi\in\mathrm{C}(\mathbb{C}^{2^{n}},\mathbb{C}^{2})$ computes $f$ with
fidelity

$F_{f}(\Phi)=\min_{0\leq h\leq\lfloor
n/2\rfloor}F\big{\lparen}|{f(0^{n-h}1^{h})}\rangle,\Phi(|{0^{n-h}1^{h}}\rangle\langle{0^{n-h}1^{h}}|)\big{\rparen},$
(2.42)

where $0^{n-h}1^{h}:=\underbrace{0\dots 0}_{n-h}\underbrace{1\dots 1}_{h}$.

###### Proof.

Let $\rho_{x}^{U}:=U^{\otimes n}|{x}\rangle\langle{x}|U^{\dagger\otimes n}$
denote the input state corresponding to an arbitrary $x\in\\{0,1\\}^{n}$ and
$U\in\mathrm{U}(2)$. Recall from eq. 2.11 that $\Phi$ computes $f$ with
fidelity

$F_{f}(\Phi)=\min_{\begin{subarray}{c}x\in\\{0,1\\}^{n}\\\
U\in\mathrm{U}(d)\end{subarray}}F\big{\lparen}U|{f(x)}\rangle,\Phi(\rho^{U}_{x})\big{\rparen}.$
(2.43)

Since $\Phi$ is permutation-invariant and unitary-equivariant,

$\displaystyle F\big{\lparen}U|{f(x)}\rangle,\Phi(\rho_{x}^{U})\big{\rparen}$
$\displaystyle=\langle{f(x)}|U^{\dagger}\Phi(\rho_{x}^{U})U|{f(x)}\rangle$
(2.44)
$\displaystyle=\langle{f(x)}|U^{\dagger}U\Phi(|{x}\rangle\langle{x}|)U^{\dagger}U|{f(x)}\rangle$
(2.45)
$\displaystyle=F\big{\lparen}|{f(x)}\rangle,\Phi(|{x}\rangle\langle{x}|)\big{\rparen}.$
(2.46)

Therefore, when $\Phi$ is unitary-equivariant, the minimization over unitaries
$U$ in eq. 2.43 can be omitted. Moreover, we can also simplify the
minimization over $x$.

Let $X:=\begin{pmatrix}0&1\\\ 1&0\end{pmatrix}$ and note that $X^{\otimes
n}|{x}\rangle=|{x\oplus 1^{n}}\rangle$ and $X|{f(x)}\rangle=|{f(x\oplus
1^{n})}\rangle$ since $f$ is equivariant, see eq. 2.15. Setting $U:=X$ in the
above calculation results in

$F\big{\lparen}|{f(x\oplus 1^{n})}\rangle,\Phi(|{x\oplus
1^{n}}\rangle\langle{x\oplus
1^{n}}|)\big{\rparen}=F\big{\lparen}|{f(x)}\rangle,\Phi(|{x}\rangle\langle{x}|)\big{\rparen},$
(2.47)

so it suffices to minimize only over strings $x\in\\{0,1\\}^{n}$ with $\lvert
x\rvert\leq\frac{n}{2}$. Finally, if $\lvert x\rvert=h$ then
$f(x)=f(0^{n-h}1^{h})$ and
$\Phi(|{x}\rangle\langle{x}|)=\Phi(|{0^{n-h}1^{h}}\rangle\langle{0^{n-h}1^{h}}|)$
since $f$ is symmetric and $\Phi$ is permutation-invariant. Therefore

$F\big{\lparen}|{f(x)}\rangle,\Phi(|{x}\rangle\langle{x}|)\big{\rparen}=F\big{\lparen}|{f(0^{n-h}1^{h})}\rangle,\Phi(|{0^{n-h}1^{h}}\rangle\langle{0^{n-h}1^{h}}|)\big{\rparen}$
(2.48)

and it suffices to optimize only over Hamming weights $h\in\\{0,\dotsc,\lfloor
n/2\rfloor\\}$. ∎

##  3 Generic pre-processing

While the problem of computing $f:[d]^{n}\to[d]$ in a basis-independent way
can be studied for any $d\geq 2$, for the rest of this paper we focus
specifically on the $d=2$ or Boolean case. In this case we can take advantage
of the relatively simple structure of the qubit Schur basis discussed in
Section 3.3. While some of our discussion applies also to any $d\geq 2$, we
expect the general case to be much more complicated and leave it for future
work.

As an additional simplifying assumption, we consider only symmetric functions
$f$. This helps us to narrow down the structure of possible quantum channels
for computing $f$, and reduces the problem of finding an optimal channel from
a semidefinite optimization problem to a linear one (see [GO22] for an in-
depth study of this phenomenon).

In this section, we outline a generic procedure for pre-processing the quantum
input $\rho_{x}^{U}$, which can be used to simplify the task of computing any
symmetric equivariant $n$-bit Boolean function $f:\\{0,1\\}^{n}\to\\{0,1\\}$
in a basis-independent manner. This pre-processing does not lose any relevant
information about the input, so it is always possible to afterwards complete
the algorithm and still compute $f$ optimally. The pre-processing is based on
Schur–Weyl duality and uses a particularly nice basis of the $n$-qubit space
which we explain in the following subsections.

###  3.1 Schur–Weyl duality

This section provides a brief summary of Schur–Weyl duality, which is one of
our main tools. While it holds for any $d\geq 2$, here we focus specifically
on $d=2$. We list some standard material and recommend [Har05, Section 5.3]
and [GW09, Section 9.1] for more background.

Let $U\in\mathrm{U}(2)$ be a single-qubit unitary and $\pi\in\mathrm{S}_{n}$ a
permutation of $n$ elements. We can extend both operations to unitaries that
act on the $n$-qubit space $(\mathbb{C}^{2})^{\otimes n}$ by considering
$Q(U):=U^{\otimes n}$, which simultaneously applies $U$ to each qubit, and
$P(\pi)$, see eq. 2.1, which permutes the qubits according to $\pi$. Note that
$Q(U)$ and $P(\pi)$ are unitary representations of the groups $\mathrm{U}(2)$
and $\mathrm{S}_{n}$, respectively. Moreover, their actions commute:
$[Q(U),P(\pi)]=0$.

The representations $Q$ and $P$ not only commute with each other but in fact
generate algebras that are mutual commutants of one another. Recall that an
_algebra_ $\mathscr{A}\subseteq\mathrm{L}(\mathbb{C}^{2^{n}})$ is a linear
subspace that is closed under matrix multiplication, and the _commutant_ of
$\mathscr{A}$ is defined as

$\operatorname{Comm}(\mathscr{A}):=\\{M\in\mathrm{L}(\mathbb{C}^{2^{n}}):MA=AM,\forall
A\in\mathscr{A}\\}.$ (3.1)

If we denote the algebras generated by the representations $Q$ and $P$ as
follows

$\displaystyle\mathscr{Q}$
$\displaystyle:=\operatorname{span}\\{Q(U):U\in\mathrm{U}(2)\\},$
$\displaystyle\mathscr{P}$
$\displaystyle:=\operatorname{span}\\{P(\pi):\pi\in\mathrm{S}_{n}\\},$ (3.2)

then _Schur–Weyl duality_ says that
$\operatorname{Comm}(\mathscr{Q})=\mathscr{P}$ and
$\operatorname{Comm}(\mathscr{P})=\mathscr{Q}$.

The above statement of Schur–Weyl duality is very concise but not necessarily
very insightful. We can make it much more concrete as follows. First, we
decompose the $n$-qubit state space $\mathbb{C}^{2^{n}}$ as follows:

$\underbrace{\mathbb{C}^{2}\otimes\dotsb\otimes\mathbb{C}^{2}}_{n}\cong\bigoplus_{\lambda\mathbin{\vdash}n}\mathcal{Q}_{\lambda}\otimes\mathcal{P}_{\lambda},$
(3.3)

where $\lambda\mathbin{\vdash}n$ means that $\lambda$ runs over all
_partitions_ of $n$ with _exactly two parts_ 444This somewhat differs from the
conventional meaning of $\lambda\mathbin{\vdash}n$, which is that $\lambda$
can have any number of integer parts and each part has strictly positive
size.:

$\displaystyle\lambda\mathbin{\vdash}n\quad\Longleftrightarrow\quad\lambda\in\\{(\lambda_{1},\lambda_{2})\in\mathbb{Z}^{2}:\lambda_{1}+\lambda_{2}=n,\lambda_{1}\geq\lambda_{2}\geq
0\\}.$ (3.4)

Equivalently, $\lambda=(n-k,k)$ for some $k\in\\{0,\dotsc,\lfloor
n/2\rfloor\\}$. The subspace
$\mathcal{Q}_{\lambda}\otimes\mathcal{P}_{\lambda}$ corresponding to a
particular $\lambda$ in eq. 3.3 is called the _$\lambda$ -isotypic subspace_.
The dimensions of the _unitary register_ $\mathcal{Q}_{\lambda}$ and the
_permutation register_ $\mathcal{P}_{\lambda}$ within this subspace are

$\displaystyle\dim\mathcal{Q}_{\lambda}$
$\displaystyle=\lambda_{1}-\lambda_{2}+1=:m_{\lambda},$
$\displaystyle\dim\mathcal{P}_{\lambda}$
$\displaystyle=\binom{\lambda_{1}+\lambda_{2}}{\lambda_{1}}\frac{\lambda_{1}-\lambda_{2}+1}{\lambda_{1}+1}=:d_{\lambda},$
(3.5)

which obey the non-trivial combinatorial identity
$2^{n}=\sum_{\lambda\mathbin{\vdash}n}m_{\lambda}d_{\lambda}$.

The defining property of the decomposition (3.3) is that the operators $Q(U)$
and $P(\pi)$ take a particularly simple form in the right-hand side basis.
Namely, if we write $\hat{M}$ to denote a matrix
$M\in\mathrm{L}(\mathbb{C}^{2^{n}})$ expressed in this basis then

$\displaystyle\hat{Q}(U)$
$\displaystyle=\bigoplus_{\lambda\mathbin{\vdash}n}Q_{\lambda}(U)\otimes
I_{d_{\lambda}},$ $\displaystyle\hat{P}(\pi)$
$\displaystyle=\bigoplus_{\lambda\mathbin{\vdash}n}I_{m_{\lambda}}\otimes
P_{\lambda}(\pi),$ (3.6)

where $Q_{\lambda}$ and $P_{\lambda}$, acting on registers
$\mathcal{Q}_{\lambda}$ and $\mathcal{P}_{\lambda}$, are irreducible
representations of the unitary group $\mathrm{U}(2)$ and the permutation group
$\mathrm{S}_{n}$, respectively, and $I_{d}$ denotes the identity matrix of
dimension $d$. The dual nature of $\hat{Q}(U)$ and $\hat{P}(\pi)$ in eq. 3.6
constitute a concrete embodiment of the _Schur–Weyl duality_. It is evident
from eq. 3.6 that $[\hat{Q}(U),\hat{P}(\pi)]=0$.

###  3.2 Schur transform

Any orthonormal basis of $(\mathbb{C}^{2})^{\otimes n}$ that decomposes the
space as in eq. 3.3 and that block-diagonalizes the action of $\mathrm{U}(2)$
and $\mathrm{S}_{n}$ as in eq. 3.6 is called a _Schur basis_ , and the
corresponding unitary basis change

$U_{\mathrm{Sch}}:(\mathbb{C}^{2})^{\otimes
n}\to\bigoplus_{\lambda\mathbin{\vdash}n}\big{\lparen}\mathbb{C}^{m_{\lambda}}\otimes\mathbb{C}^{d_{\lambda}}\big{\rparen}$
(3.7)

is called a _Schur transform_.

If $R:G\to\mathrm{U}(d)$ is a representation of a group $G$ then so is
$R^{\prime}(g)=VR(g)V^{\dagger}$ for any $V\in\mathrm{U}(d)$. Since each of
the $\mathcal{Q}_{\lambda}$ and $\mathcal{P}_{\lambda}$ registers in eq. 3.3
has a similar unitary degree of freedom, Schur basis is not unique and thus
neither is Schur transform. Any two Schur transforms
$U_{\mathrm{Sch}},U_{\mathrm{Sch}}^{\prime}\in\mathrm{U}(\mathbb{C}^{2^{n}})$
are related as

$U_{\mathrm{Sch}}=\left\lparen\bigoplus_{\lambda\mathbin{\vdash}n}\big{\lparen}V_{\lambda}\otimes
W_{\lambda}\big{\rparen}\right\rparen U_{\mathrm{Sch}}^{\prime},$ (3.8)

for some $V_{\lambda}\in\mathrm{U}(m_{\lambda})$ and
$W_{\lambda}\in\mathrm{U}(d_{\lambda})$.

Quantum circuits for implementing Schur transform, efficient in the local
dimension $d\geq 2$ and the number of systems $n\geq 1$, are known [Har05,
BCH06, BCH07, KS18, Kro19]. However, as far as we can tell, our algorithm
requires not just any old Schur transform but one that produces a particular
basis on the unitary registers $\mathcal{Q}_{\lambda}$. Namely, the action of
$U^{\otimes n}$ in Schur basis should be given by

$\bigoplus_{\lambda\mathbin{\vdash}n}Q_{\lambda}(U)\otimes I_{d_{\lambda}},$
(3.9)

where the irreducible $\mathrm{U}(2)$-representations $Q_{\lambda}(U)$ are in
the so-called _Gelfand–Tsetlin basis_. We describe in detail the construction
and properties of such representations in Appendix C, and in Section 3.3 we
provide a family of Schur bases that produce them (see Lemma B.9 for proof).

Generally, a Schur basis that is suitable for us can be produced by employing
the representation theory of the unitary group and the associated
Clebsch–Gordan transform.555This is in contrast to the approach of [Kro19]
which exploits the representation theory of the symmetric group. For example,
the $n$-qubit Schur transform implemented by [KS18] is suitable for use in our
algorithm.

Analogous to the Gelfand–Tsetlin basis for the unitary registers
$\mathcal{Q}_{\lambda}$, a similarly elegant choice, the so-called
_Young–Yamanouchi basis_ , exists also for the permutation registers
$\mathcal{P}_{\lambda}$, i.e., the second register in eq. 3.9. However, for us
the actual basis used for the permutation registers will not matter since our
algorithm will discard them. Indeed, as we consider only symmetric functions,
this register will be in the maximally mixed state that looks the same in any
basis.

###  3.3 Nice Schur basis of the $n$-qubit space

Since Schur basis is not unique, we would like to choose one with a
particularly nice structure. In this section, we describe a construction
borrowed from [CEM99] (see Appendix B for a comprehensive treatment). While
this construction does not determine a unique basis, any member of the
resulting family has enough structure for our purposes.

From now on we focus exclusively on the $d=2$ case because of the following
particularly nice Schur basis for $(\mathbb{C}^{2})^{\otimes n}$. It consists
of vectors

$|{(\lambda,w,i)}\rangle,\qquad\text{where}\qquad\lambda\mathbin{\vdash}n,\;w\in[m_{\lambda}],\;i\in[d_{\lambda}].$
(3.10)

Here $\lambda$ labels the blocks in eq. 3.3 while $w$ and $i$ label bases for
the unitary register $\mathcal{Q}_{\lambda}$ and the permutation register
$\mathcal{P}_{\lambda}$, respectively. Note that the range of $w$ and $i$
depends on $\lambda$.

To construct this basis, we first define the $i=0$ vectors as

$|{(\lambda,w,0)}\rangle:=|{s_{\lambda_{1}-\lambda_{2}}(w)}\rangle\otimes|{\Psi^{-}}\rangle^{\otimes\lambda_{2}},$
(3.11)

where $|{\Psi^{-}}\rangle:=(|{01}\rangle-|{10}\rangle)/\sqrt{2}$ is the
_singlet state_ and $|{s_{\ell}(w)}\rangle\in(\mathbb{C}^{2})^{\otimes\ell}$
is the $\ell$-qubit _symmetric_ or _Dicke state_ [Dic54] of Hamming weight
$w$:

$|{s_{\ell}(w)}\rangle:=\binom{\ell}{w}^{-1/2}\sum_{\begin{subarray}{c}x\in\\{0,1\\}^{\ell}\\\
\lvert x\rvert=w\end{subarray}}|{x}\rangle.$ (3.12)

Note that
$\langle{s_{\ell}(w)}|{s_{\ell}(w^{\prime})}\rangle=\delta_{ww^{\prime}}$, so
these states form an orthonormal basis of the $\ell$-qubit symmetric subspace.

Next, we (semi-explicitly) describe the states $|{(\lambda,w,i)}\rangle$ with
$i\in\\{1,\dotsc,d_{\lambda}-1\\}$. Let

$|{(\lambda,w,i)}\rangle:=\sum_{\pi\in\mathrm{S}_{n}}\alpha_{\pi}^{\lambda,i}P(\pi)|{(\lambda,w,0)}\rangle,$
(3.13)

where the coefficients $\alpha_{\pi}^{\lambda,i}\in\mathbb{R}$ do not depend
on $w$ and are chosen so that for $w=0$ the states
$\\{|{(\lambda,0,i)}\rangle:i\in[d_{\lambda}]\\}$ form an orthonormal basis of
$\mathcal{P}_{\lambda,0}$ where

$\mathcal{P}_{\lambda,w}:=\operatorname{span}\big{\\{}P(\pi)|{(\lambda,w,0)}\rangle:\pi\in\mathrm{S}_{n}\big{\\}}.$
(3.14)

In other words, we fix $\lambda$ and choose $\alpha_{\pi}^{\lambda,i}$ so that

$\langle{(\lambda,0,i)}|{(\lambda,0,j)}\rangle=\delta_{ij},$ (3.15)

and then reuse them for all other values of $w$ and the same $\lambda$.
Surprisingly, this ensures that the states
$\\{|{(\lambda,w,i)}\rangle:i\in[d_{\lambda}]\\}$ with $w\neq 0$ also form an
orthonormal basis of $\mathcal{P}_{\lambda,w}$ (see Proposition B.6 in
Appendix B). Although the above construction does not fully determine the
vectors $|{(\lambda,w,i)}\rangle$, this ambiguity will not make any difference
in the arguments that follow. In particular, the full set of vectors
$|{(\lambda,w,i)}\rangle$ is always orthonormal (see Lemma B.7 in Appendix B)
and hence forms a basis for $(\mathbb{C}^{2})^{\otimes n}$.

Let us now argue that these vectors are indeed compatible with the action of
$\mathrm{S}_{n}$ and $\mathrm{U}(d)$ in eq. 3.6. First, note from eq. 3.14
that each subspace $\mathcal{P}_{\lambda,w}$ is invariant under qubit
permutations $P(\pi)$. Moreover, Lemma B.8 in Appendix B shows that the
subspaces

$\mathcal{Q}_{\lambda,i}:=\operatorname{span}\big{\\{}|{(\lambda,w,i)}\rangle:w\in[m_{\lambda}]\big{\\}}$
(3.16)

are invariant under $U^{\otimes n}$, for any $U\in\mathrm{U}(2)$. The actions
of $\pi\in\mathrm{S}_{n}$ and $U\in\mathrm{U}(2)$ on subspaces
$\mathcal{P}_{\lambda,w}$ and $\mathcal{Q}_{\lambda,i}$ are given by the
corresponding $\lambda$-irreps $P_{\lambda}(\pi)$ and $Q_{\lambda}(U)$,
respectively, see Lemmas B.1 and B.9 in Appendix B. This establishes the
explicit Schur–Weyl duality in eq. 3.6 and implies that the vectors
$|{(\lambda,w,i)}\rangle$ indeed form a Schur basis. While the exact form of
$P_{\lambda}(\pi)$ will not be important to us, we will need more information
about the $\mathrm{U}(2)$-irreps $Q_{\lambda}(U)$, so we provide an extensive
discussion on their construction and properties in Appendix C.

With a basis at hand we can express the projection onto the $\lambda$-isotypic
subspace as

$\Pi_{\lambda}:=\sum_{w\in[m_{\lambda}]}\sum_{i\in[d_{\lambda}]}|{(\lambda,w,i)}\rangle\langle{(\lambda,w,i)}|,$
(3.17)

which takes the following very simple form in the Schur basis:

$\hat{\Pi}_{\lambda}=\bigoplus_{\kappa\mathbin{\vdash}n}\delta_{\lambda\kappa}I_{m_{\kappa}d_{\kappa}}.$
(3.18)

Moreover, we can write the associated Schur transform as follows:

$U_{\mathrm{Sch}}:=\bigoplus_{\lambda\mathbin{\vdash}n}\left\lparen\sum_{w\in[m_{\lambda}]}\sum_{i\in[d_{\lambda}]}|{w}\rangle\otimes|{i}\rangle\langle{(\lambda,w,i)}|\right\rparen.$
(3.19)

A key property of the above construction is that $|{(\lambda,w,0)}\rangle$ and
$|{(\lambda,w,i)}\rangle$ satisfy eqs. 3.11 and 3.13, respectively, and the
actual values of the coefficients $\alpha_{\pi}^{\lambda,i}$ in eq. 3.13 do
not matter to us. Any basis of this form can be used in our analysis, and the
associated Schur transform (3.19) can be used as the first step of our
algorithm to compute any symmetric equivariant Boolean function
$f:\\{0,1\\}^{n}\to\\{0,1\\}$ in a basis-independent manner.

From now on by _Schur basis_ we will mean any basis of the above form, and by
_Schur transform_ we will mean the corresponding transform (3.19).

###  3.4 Generic pre-processing

We now describe a generic pre-processing procedure $\Gamma$ that can be used
as the first step when computing any symmetric and equivariant Boolean
function $f:\\{0,1\\}^{n}\to\\{0,1\\}$. We will conclude in Corollary 3.6 that
applying $\Gamma$ does not incur any loss in fidelity.

Algorithm 1: Generic pre-processing $\Gamma$ Input: Quantum state $U^{\otimes
n}|{x}\rangle$ with an unknown $x\in\\{0,1\\}^{n}$ and $U\in\mathrm{U}(2)$.
Output: Partition $\lambda=(\lambda_{1},\lambda_{2})\mathbin{\vdash}n$ and
quantum state $Q_{\lambda}(U)|{w_{\lambda,x}}\rangle$ of dimension
$m_{\lambda}:=\lambda_{1}-\lambda_{2}+1$ where $w_{\lambda,x}:=\lvert
x\rvert-\lambda_{2}$ (see Lemma 3.2). Step 1: Apply Schur transform
$U_{\mathrm{Sch}}$. Step 2: Measure $\lambda\mathbin{\vdash}n$ (_weak Schur
sampling_). Step 3: Discard the permutation register $\mathcal{P}_{\lambda}$.

Since the output dimension $m_{\lambda}$ of this procedure is a random
variable, we can either think of $\Gamma$ as a collection of CP maps
$(\Gamma_{\lambda}:\lambda\mathbin{\vdash}n)$ where
$\Gamma_{\lambda}:\mathrm{L}(\mathbb{C}^{2^{n}})\to\mathrm{L}(\mathbb{C}^{m_{\lambda}})$,
or we can identify the output space of $\Gamma$ with the direct sum
$\bigoplus_{\lambda\mathbin{\vdash}n}\mathbb{C}^{m_{\lambda}}$. The following
lemma shows that $\Gamma$ is permutation-invariant, i.e., invariant under
applying $P(\pi)$ for any $\pi\in\mathrm{S}_{n}$ on the input. In addition,
$\Gamma$ is also unitary-covariant, meaning that each $\Gamma_{\lambda}$ is
unitary-covariant, i.e., instead of applying $U^{\otimes n}$ on the input we
can apply $\bigoplus_{\lambda\mathbin{\vdash}n}Q_{\lambda}(U)$ on the output
of $\Gamma$.

######  Lemma 3.1.

The generic pre-processing
$\Gamma\in\mathrm{C}(\mathbb{C}^{2^{n}},\bigoplus_{\lambda\mathbin{\vdash}n}\mathbb{C}^{m_{\lambda}})$
implemented by Section 3.4 is permutation-invariant and unitary-covariant. In
other words, for any $\rho\in\mathrm{L}(\mathbb{C}^{2^{n}})$,

$\displaystyle\Gamma\big{\lparen}P(\pi)\,\rho\,P(\pi)^{\dagger}\big{\rparen}$
$\displaystyle=\Gamma\big{\lparen}\rho\big{\rparen},$
$\displaystyle\forall\pi$ $\displaystyle\in\mathrm{S}_{n},$ (3.20)
$\displaystyle\Gamma\big{\lparen}U^{\otimes n}\,\rho\,U^{\dagger\otimes
n}\big{\rparen}$
$\displaystyle=\bigoplus_{\lambda\mathbin{\vdash}n}Q_{\lambda}(U)\,\Gamma_{\lambda}\lparen\rho\rparen\,Q_{\lambda}(U)^{\dagger},$
$\displaystyle\forall U$ $\displaystyle\in\mathrm{U}(2).$ (3.21)

###### Proof.

To see that $\Gamma$ is permutation-invariant, recall from eq. 3.6 that the
$n$-qubit permutation $P(\pi)$ acts as
$\hat{P}(\pi)=\bigoplus_{\lambda\mathbin{\vdash}n}I_{m_{\lambda}}\otimes
P_{\lambda}(\pi)$ in Schur basis. Hence, it does not interfere with the
measurement performed in Step 2 since the measurement operators
$\hat{\Pi}_{\lambda}=\bigoplus_{\kappa\mathbin{\vdash}n}\delta_{\lambda\kappa}I_{m_{\kappa}}\otimes
I_{d_{\kappa}}$ from eq. 3.18 are diagonal in Schur basis. The effect of the
permutation is negated when the permutation register is discarded in Step 3,
thus $\Gamma$ is permutation-invariant.

To argue unitary covariance, recall from eq. 3.6 that $U^{\otimes n}$ acts as
$\hat{Q}(U)=\bigoplus_{\lambda\mathbin{\vdash}n}Q_{\lambda}(U)\otimes
I_{d_{\lambda}}$ in Schur basis, which also does not interfere with the
measurement performed in Step 2. Since $\hat{Q}(U)$ acts trivially on the
permutation register, we can instead apply $Q_{\lambda}(U)$ on the output once
the permutation register has been discarded in Step 3. This shows that
$\Gamma$ is unitary-covariant. ∎

######  Lemma 3.2.

When the generic pre-processing $\Gamma$ given by Section 3.4 is applied to
$U^{\otimes n}|{x}\rangle$ for some $U\in\mathrm{U}(2)$ and
$x\in\\{0,1\\}^{n}$, the probability of measurement outcome
$\lambda=(\lambda_{1},\lambda_{2})$ in Step 2 is

$p_{\lambda}(x):=\begin{cases}\frac{\tbinom{n}{\lambda_{2}}-\tbinom{n}{\lambda_{2}-1}}{\tbinom{n}{\lvert
x\rvert}}&\text{if $\lambda_{2}\leq\lvert x\rvert$},\\\
0&\text{otherwise},\end{cases}$ (3.22)

where $\lvert x\rvert$ denotes the number of ones in the string $x$. The
corresponding output state after Step 3 is

$Q_{\lambda}(U)|{w_{\lambda,x}}\rangle\in\mathbb{C}^{m_{\lambda}},$ (3.23)

where $Q_{\lambda}(U)$ is a representation of $U$ of dimension
$m_{\lambda}:=\lambda_{1}-\lambda_{2}+1$, see eq. C.39 in Section C.5, and
$w_{\lambda,x}:=\lvert x\rvert-\lambda_{2}$. The full output of $\Gamma$ is

$\Gamma\big{\lparen}U^{\otimes n}|{x}\rangle\langle{x}|U^{\dagger\otimes
n}\big{\rparen}=\bigoplus_{\lambda\mathbin{\vdash}n}p_{\lambda}(x)\,Q_{\lambda}(U)|{w_{\lambda,x}}\rangle\langle{w_{\lambda,x}}|Q_{\lambda}(U)^{\dagger}.$
(3.24)

###### Proof.

Recall from eq. 3.21 in Lemma 3.1 that $\Gamma$ is unitary-covariant:

$\Gamma\big{\lparen}U^{\otimes n}|{x}\rangle\langle{x}|U^{\dagger\otimes
n}\big{\rparen}=\bigoplus_{\lambda\mathbin{\vdash}n}Q_{\lambda}(U)\Gamma_{\lambda}\big{\lparen}|{x}\rangle\langle{x}|\big{\rparen}Q_{\lambda}(U)^{\dagger}.$
(3.25)

Hence, it suffices to argue that
$\Gamma_{\lambda}\big{\lparen}|{x}\rangle\langle{x}|\big{\rparen}=p_{\lambda}(x)\,|{w_{\lambda,x}}\rangle\langle{w_{\lambda,x}}|$,
i.e., applying $\Gamma$ to $|{x}\rangle$ produces $|{w_{\lambda,x}}\rangle$
with probability $p_{\lambda}(x)$ (note that $\Gamma$ is trace-preserving
while $\Gamma_{\lambda}$ are not).

Let us analyze the effect of Steps 1–3 on $|{x}\rangle$. Since Step 1
corresponds to applying the Schur transform $U_{\mathrm{Sch}}$ defined in eq.
3.19, let us first express $|{x}\rangle$ in the Schur basis
$|{(\lambda,w,i)}\rangle$. Note from eqs. 3.11 and 3.13 that the standard
basis expansion of $|{(\lambda,w,i)}\rangle$ involves only states of Hamming
weight $w+\lambda_{2}$, therefore $|{x}\rangle$ can be expressed as a linear
combination of $|{(\lambda,w_{\lambda,x},i)}\rangle$ where
$w_{\lambda,x}=\lvert x\rvert-\lambda_{2}$:

$|{x}\rangle=\sum_{\lambda\mathbin{\vdash}n}\sum_{i\in[d_{\lambda}]}c_{\lambda,i}(x)|{(\lambda,w_{\lambda,x},i)}\rangle,$
(3.26)

for some coefficients $c_{\lambda,i}(x)\in\mathbb{R}$. Using eq. 3.19, we find
that $|{x}\rangle$ in the Schur basis looks as follows:

$U_{\mathrm{Sch}}|{x}\rangle=\bigoplus_{\lambda\mathbin{\vdash}n}\left[\sum_{i\in[d_{\lambda}]}c_{\lambda,i}(x)\big{\lparen}|{w_{\lambda,x}}\rangle\otimes|{i}\rangle\big{\rparen}\right]=\bigoplus_{\lambda\mathbin{\vdash}n}\Bigg{[}|{w_{\lambda,x}}\rangle\otimes\underbrace{\sum_{i\in[d_{\lambda}]}c_{\lambda,i}(x)|{i}\rangle}_{|{\psi_{\lambda}(x)}\rangle}\Bigg{]}.$
(3.27)

The probability of obtaining measurement outcome $\lambda$ in Step 2 is

$p_{\lambda}(x)=\lVert|{\psi_{\lambda}(x)}\rangle\rVert^{2}=\sum_{i\in[d_{\lambda}]}\lvert
c_{\lambda,i}(x)\rvert^{2},$ (3.28)

and the corresponding post-measurement state is

$|{w_{\lambda,x}}\rangle\otimes\frac{|{\psi_{\lambda}(x)}\rangle}{\sqrt{p_{\lambda}(x)}}.$
(3.29)

Discarding the second register results in the desired state
$|{w_{\lambda,x}}\rangle\in\mathbb{C}^{m_{\lambda}}$. The formula for
$p_{\lambda}(x)$ stated in eq. 3.22 has been derived in [Mon09, Lemma 4]. This
is a special case of a more general formula derived in [HHY21], i.e.,
$p_{\lambda}(x)=p(\lambda_{2}|n,h,n,h)$ where $h=|x|$. ∎

The following lemma shows that the generic pre-processing channel $\Gamma$
implemented by Section 3.4 is reversible. More specifically, we can find a
channel $\Gamma^{\prime}$ that undoes the action of $\Gamma$ on all input
states that are symmetric over $\mathrm{S}_{n}$.

######  Lemma 3.3.

There exists a unitary-covariant quantum channel
$\Gamma^{\prime}\in\mathrm{C}(\bigoplus_{\lambda\mathbin{\vdash}n}\mathbb{C}^{m_{\lambda}},\mathbb{C}^{2^{n}})$
such that

$(\Gamma^{\prime}\circ\Gamma\circ\Theta)\big{\lparen}U^{\otimes
n}|{x}\rangle\langle{x}|U^{\dagger\otimes
n}\big{\rparen}=\Theta\big{\lparen}U^{\otimes
n}|{x}\rangle\langle{x}|U^{\dagger\otimes n}\big{\rparen},$ (3.30)

for all $x\in\\{0,1\\}^{n}$ and $U\in\mathrm{U}(2)$, where $\Gamma$ is the
generic pre-processing implemented by Section 3.4 and
$\Theta:\mathrm{L}(\mathbb{C}^{2^{n}})\to\mathrm{L}(\mathbb{C}^{2^{n}})$
denotes symmetrization over $\mathrm{S}_{n}$:

$\Theta(\rho):=\frac{1}{n!}\sum_{\pi\in\mathrm{S}_{n}}P(\pi)\rho
P(\pi)^{\dagger},\qquad\forall\rho\in\mathrm{L}(\mathbb{C}^{2^{n}}).$ (3.31)

###### Proof.

Recall from Lemma 3.1 that $\Gamma$ is unitary-covariant and note from eq.
3.31 that so is $\Theta$. In addition, once we define the map
$\Gamma^{\prime}$, we will see that it is also unitary-covariant. Therefore,
we can assume without loss of generality that $U=I_{2}$ in eq. 3.30, so it
suffices to show that, for all $x\in\\{0,1\\}^{n}$,

$(\Gamma^{\prime}\circ\Gamma\circ\Theta)\big{\lparen}|{x}\rangle\langle{x}|\big{\rparen}=\Theta\big{\lparen}|{x}\rangle\langle{x}|\big{\rparen}.$
(3.32)

It will be easier to argue this in the Schur basis, so let us show that, for
all $x\in\\{0,1\\}^{n}$,

$U_{\mathrm{Sch}}(\Gamma^{\prime}\circ\Gamma\circ\Theta)\big{\lparen}|{x}\rangle\langle{x}|\big{\rparen}U_{\mathrm{Sch}}^{\dagger}=U_{\mathrm{Sch}}\Theta\big{\lparen}|{x}\rangle\langle{x}|\big{\rparen}U_{\mathrm{Sch}}^{\dagger}.$
(3.33)

Recall from eq. 3.27 that

$U_{\mathrm{Sch}}|{x}\rangle=\bigoplus_{\lambda\mathbin{\vdash}n}\Big{[}|{w_{\lambda,x}}\rangle\otimes|{\psi_{\lambda}(x)}\rangle\Big{]}.$
(3.34)

Using eq. 3.6 we can extend this to any input of the form $P(\pi)|{x}\rangle$
where $\pi\in\mathrm{S}_{n}$:

$U_{\mathrm{Sch}}P(\pi)|{x}\rangle=\left\lparen\bigoplus_{\lambda\mathbin{\vdash}n}I_{m_{\lambda}}\otimes
P_{\lambda}(\pi)\right\rparen
U_{\mathrm{Sch}}|{x}\rangle=\bigoplus_{\lambda\mathbin{\vdash}n}\Big{[}|{w_{\lambda,x}}\rangle\otimes
P_{\lambda}(\pi)|{\psi_{\lambda}(x)}\rangle\Big{]}.$ (3.35)

Substituting $\Theta$ from eq. 3.31, the right-hand side of eq. 3.33 becomes

$\displaystyle
U_{\mathrm{Sch}}\Theta\big{\lparen}|{x}\rangle\langle{x}|\big{\rparen}U_{\mathrm{Sch}}^{\dagger}$
$\displaystyle=U_{\mathrm{Sch}}\left\lparen\frac{1}{n!}\sum_{\pi\in\mathrm{S}_{n}}P(\pi)|{x}\rangle\langle{x}|P(\pi)^{\dagger}\right\rparen
U_{\mathrm{Sch}}^{\dagger}$ (3.36)
$\displaystyle=\bigoplus_{\lambda\mathbin{\vdash}n}\left[|{w_{\lambda,x}}\rangle\langle{w_{\lambda,x}}|\otimes\frac{1}{n!}\sum_{\pi\in\mathrm{S}_{n}}P_{\lambda}(\pi)|{\psi_{\lambda}(x)}\rangle\langle{\psi_{\lambda}(x)}|P_{\lambda}(\pi)^{\dagger}\right].$
(3.37)

Since the matrix on the second register commutes with $P_{\lambda}(\sigma)$,
for any $\sigma\in\mathrm{S}_{n}$, by Schur’s lemma (Lemma 2.1) we get

$\frac{1}{n!}\sum_{\pi\in\mathrm{S}_{n}}P_{\lambda}(\pi)|{\psi_{\lambda}(x)}\rangle\langle{\psi_{\lambda}(x)}|P_{\lambda}(\pi)^{\dagger}=c_{\lambda}(x)\frac{I_{d_{\lambda}}}{d_{\lambda}}.$
(3.38)

By comparing the trace of both sides, we find from eq. 3.28 that
$c_{\lambda}(x)=\lVert|{\psi_{\lambda}(x)}\rangle\rVert^{2}=p_{\lambda}(x)$.
In summary, the right-hand side of eq. 3.33 can be written as

$U_{\mathrm{Sch}}\Theta\big{\lparen}|{x}\rangle\langle{x}|\big{\rparen}U_{\mathrm{Sch}}^{\dagger}=\bigoplus_{\lambda\mathbin{\vdash}n}\left[p_{\lambda}(x)|{w_{\lambda,x}}\rangle\langle{w_{\lambda,x}}|\otimes\frac{I_{d_{\lambda}}}{d_{\lambda}}\right].$
(3.39)

To analyze the left-hand side of eq. 3.33, recall that Step 1 of $\Gamma$
corresponds to applying the Schur transform $U_{\mathrm{Sch}}$. Since $\Gamma$
is acting on $\Theta\big{\lparen}|{x}\rangle\langle{x}|\big{\rparen}$, the
result of Step 1 coincides with eq. 3.39. Hence, we only need to analyze Steps
2 and 3 that correspond to measuring $\lambda$ and discarding the permutation
register. It is immediate from eq. 3.39 that these steps produce

$(\Gamma\circ\Theta)\big{\lparen}|{x}\rangle\langle{x}|\big{\rparen}=\bigoplus_{\lambda\mathbin{\vdash}n}p_{\lambda}(x)|{w_{\lambda,x}}\rangle\langle{w_{\lambda,x}}|.$
(3.40)

It is now easy to see that the following steps implement a map
$\Gamma^{\prime}$ that undoes the action of $\Gamma$:

  1. Step 1’:

Measure $\lambda$.

  2. Step 2’:

Attach a new (permutation) register containing the maximally mixed state
$I_{d_{\lambda}}/d_{\lambda}$.

  3. Step 3’:

Apply the inverse Schur transform $U_{\mathrm{Sch}}^{\dagger}$.

Note that Steps 1’ and 2’ recover the state in eq. 3.39 and Step 3’ recovers
the original symmetrized state
$\Theta\big{\lparen}|{x}\rangle\langle{x}|\big{\rparen}$. This establishes eq.
3.32.

It remains to show that $\Gamma^{\prime}$ is unitary-covariant. Similar to the
argument in Lemma 3.1, we recall from eq. 3.6 that $U^{\otimes n}$ acts as
$\hat{Q}(U)=\bigoplus_{\lambda\mathbin{\vdash}n}Q_{\lambda}(U)\otimes
I_{d_{\lambda}}$ in the Schur basis. Since this does not interfere with the
measurement in Step 1’ and acts trivially on the permutation register that is
attached in Step 2’, we conclude that $\Gamma^{\prime}$ is unitary-covariant.
∎

While the above proof is useful for understanding the evolution of any input
state $\rho_{x}^{U}$ during the generic pre-processing $\Gamma$, Lemma 3.3 can
actually be generalized to all inputs. The following result shows that
$\Gamma^{\prime}$ is the inverse of $\Gamma$ on symmetric inputs.666On general
inputs $\Gamma$ is not invertible.

######  Lemma 3.4.

Let
$\Gamma\in\mathrm{C}(\mathbb{C}^{2^{n}},\bigoplus_{\lambda\mathbin{\vdash}n}\mathbb{C}^{m_{\lambda}})$
be the generic pre-processing implemented by Section 3.4 and
$\Gamma^{\prime}\in\mathrm{C}(\bigoplus_{\lambda\mathbin{\vdash}n}\mathbb{C}^{m_{\lambda}},\mathbb{C}^{2^{n}})$
be the unitary-covariant quantum channel introduced above. Then

$\Gamma^{\prime}\circ\Gamma\circ\Theta=\Theta$ (3.41)

where $\Theta$ is the quantum channel that symmetrizes over $\mathrm{S}_{n}$,
see eq. 3.31.

###### Proof.

Fix an arbitrary input $M\in\mathrm{L}(\mathbb{C}^{2^{n}})$. Since
$[\Theta(M),P(\pi)]=0$ for all $\pi\in\mathrm{S}_{n}$, the output $\Theta(M)$
is in the commutant of the algebra generated by
$\\{P(\pi):\pi\in\mathrm{S}_{n}\\}$. Hence,
$\Theta(M)\in\operatorname{span}\\{U^{\otimes n}:U\in\mathrm{U}(2)\\}$ by
Schur–Weyl duality (see Section 3.1). Since $U_{\mathrm{Sch}}U^{\otimes
n}U_{\mathrm{Sch}}^{\dagger}=\bigoplus_{\lambda\mathbin{\vdash}n}Q_{\lambda}(U)\otimes
I_{d_{\lambda}}$ by eq. 3.6, expressing $\Theta(M)$ in the Schur basis gives
us

$U_{\mathrm{Sch}}\Theta(M)U_{\mathrm{Sch}}^{\dagger}=\bigoplus_{\lambda\mathbin{\vdash}n}M_{\lambda}\otimes\frac{I_{d_{\lambda}}}{d_{\lambda}},$
(3.42)

for some $M_{\lambda}\in\mathrm{L}(\mathbb{C}^{m_{\lambda}})$. Note that Steps
2 and 3 of Section 3.4 (namely, measuring $\lambda$ and then discarding the
permutation register) are reversible operations when applied on this input.
Since $\Gamma^{\prime}$ undoes these steps, we recover back the original input
$\Theta(M)$. ∎

The following lemma shows that the implementation of any permutation-invariant
quantum channel can start off by first applying $\Gamma$, which justifies the
name “generic pre-processing” for Section 3.4. Moreover, this decomposition is
compatible with unitary-covariance.

######  Lemma 3.5.

For any permutation-invariant quantum channel
$\Phi\in\mathrm{C}(\mathbb{C}^{2^{n}},\mathbb{C}^{2})$ there exists a quantum
channel
$\Phi^{\prime}\in\mathrm{C}(\bigoplus_{\lambda\mathbin{\vdash}n}\mathbb{C}^{m_{\lambda}},\mathbb{C}^{2})$
such that

$\Phi=\Phi^{\prime}\circ\Gamma,$ (3.43)

where
$\Gamma\in\mathrm{C}(\mathbb{C}^{2^{n}},\bigoplus_{\lambda\mathbin{\vdash}n}\mathbb{C}^{m_{\lambda}})$
is the generic pre-processing implemented by Section 3.4. If $\Phi$ is
unitary-covariant then so is $\Phi^{\prime}$.

###### Proof.

By combining permutation-invariance of $\Phi$ with Lemma 3.4, we get

$\displaystyle\Phi=\Phi\circ\Theta=\Phi\circ\Gamma^{\prime}\circ\Gamma\circ\Theta=(\Phi\circ\Gamma^{\prime})\circ(\Gamma\circ\Theta)=\Phi^{\prime}\circ\Gamma$
(3.44)

where the last equality follows by defining
$\Phi^{\prime}:=\Phi\circ\Gamma^{\prime}$ and noting that
$\Gamma\circ\Theta=\Gamma$ thanks to the permutation-invariance of $\Gamma$
from Lemma 3.1. If $\Phi$ is unitary-covariant then so is $\Phi^{\prime}$
since it is a composition of two unitary-covariant channels ($\Gamma^{\prime}$
is unitary-covariant by Lemma 3.3). ∎

We can now conclude that, without loss of generality, an optimal quantum
algorithm for computing a symmetric and equivariant Boolean function in a
basis-independent way starts off by applying the generic pre-processing
$\Gamma$.

######  Corollary 3.6.

Every symmetric and equivariant Boolean function $f:\\{0,1\\}^{n}\to\\{0,1\\}$
has an optimal quantum algorithm
$\Phi\in\mathrm{UC}(\mathbb{C}^{2^{n}},\mathbb{C}^{2})$ such that
$\Phi=\Phi^{\prime}\circ\Gamma$ where $\Phi^{\prime}$ is unitary-covariant and
$\Gamma$ is the generic pre-processing implemented by Section 3.4.

###### Proof.

Thanks to Corollary 2.10, we can assume that $\Phi$ is permutation-invariant
and unitary-equivariant. The claim then follows from Lemma 3.5. ∎

###  3.5 Example: $3$-qubit quantum majority

Suppose we are interested in computing the 3-bit majority function in a basis-
independent way. As input we receive a state $U^{\otimes 3}|{x}\rangle$ for
some unknown unitary $U\in\mathrm{U}(2)$ and a 3-bit string $x$. Without loss
of generality we first apply the generic pre-processing $\Gamma$. Recall from
Lemma 3.2 that the output of $\Gamma$ is a partition
$\lambda=(\lambda_{1},\lambda_{2})\mathbin{\vdash}3$, occurring with
probability $p_{\lambda}(x)$ defined in eq. 3.22, and a state
$Q_{\lambda}(U)|{w_{\lambda,x}}\rangle$ where $w_{\lambda,x}=\lvert
x\rvert-\lambda_{2}$ and $Q_{\lambda}(U)$ is a representation of $U$ of
dimension $m_{\lambda}=\lambda_{1}-\lambda_{2}+1$. For the sake of this
example, we will apply an additional isometry
$|{w}\rangle\mapsto|{s_{\ell}(w)}\rangle$ that maps the output state into the
symmetric subspace of $\ell=\lambda_{1}-\lambda_{2}$ qubits. Then the output
state is

$U^{\otimes\ell}|{s_{\ell}(w_{\lambda,x})}\rangle,$ (3.45)

where $|{s_{\ell}(w_{\lambda,x})}\rangle$ is the $\ell$-qubit symmetric state
of Hamming weight $w_{\lambda,x}$, see eq. 3.12.

There are only two three-element partitions relevant to us: $\lambda=(2,1)$
and $\lambda=(3,0)$. Moreover, since the generic pre-processing is
permutation-invariant and unitary-covariant (see Lemma 3.1), Lemma 2.13 tells
us that it is enough to consider only two inputs: $x=000$ and $x=001$. For
example, we can think of the input $x=101$ as $X^{\otimes
3}P(\pi)|{001}\rangle$ where $\pi$ is the permutation $(132)$. For each input
$x$ and measurement outcome $\lambda$, the table below describes the
corresponding Hamming weight $w_{\lambda,x}$, the number of output qubits
$\ell$, the probability $p_{\lambda}(x)$, and the corresponding output state.

| $x=000$ | $x=001$
---|---|---
| $w_{\lambda,x}=-1,\ell=1$ | $w_{\lambda,x}=0,\ell=1$
$\lambda=(2,1)$ | $p_{\lambda}(x)=0$ | $p_{\lambda}(x)=\frac{2}{3}$
| —– | $U|{0}\rangle$
| $w_{\lambda,x}=0,\ell=3$ | $w_{\lambda,x}=1,\ell=3$
$\lambda=(3,0)$ | $p_{\lambda}(x)=1$ | $p_{\lambda}(x)=\frac{1}{3}$
| $U^{\otimes 3}|{000}\rangle$ | $U^{\otimes 3}\frac{|{001}\rangle+|{010}\rangle+|{100}\rangle}{\sqrt{3}}$

Let us now go a step further and think about the actions we could take after
the generic pre-processing to finish computing the three-qubit majority
function. Note that for both $x=000$ and $x=001$, the correct output is
$U|{0}\rangle$.

  * •

If the measurement outcome is $\lambda=(2,1)$, we can simply return the
remaining 1-qubit state $U|{0}\rangle$ since it is the desired output. Since
the outcome $\lambda=(2,1)$ cannot occur on inputs $x\in\\{000,111\\}$, we
also have additional classical side-information about the Hamming weight of
$x$.

  * •

If the outcome is $\lambda=(3,0)$, we cannot eliminate any input $x$. However,
we can simply return any of the three qubits. If $x=000$ we end up returning
the desired target state $U|{0}\rangle$ while for $x=001$ we return a mixed
state
$U\big{\lparen}\frac{2}{3}|{0}\rangle\langle{0}|+\frac{1}{3}|{1}\rangle\langle{1}|\big{\rparen}U^{\dagger}$
that has fidelity $2/3$ with the desired target state.

Overall, this algorithm achieves worst-case fidelity

$\min\left\\{0+1\cdot 1,\frac{2}{3}\cdot
1+\frac{1}{3}\cdot\frac{2}{3}\right\\}=\frac{8}{9},$ (3.46)

which we later show is optimal (see Section 5.1). Note that $8/9\approx
0.888889$ is better than $2/3\approx 0.666667$ and $5/6\approx 0.833333$
obtained by the trivial strategy for $n=3$ in the no-promise and promise
cases, respectively (see Fig. 3).

##  4 Completing the algorithm

The goal of this section is to complete the algorithm by finding an optimal
way to proceed after the generic pre-processing $\Gamma$. We will show in
Lemma 4.1 that the second step of the algorithm can be described by a unitary-
covariant channel that has only one degree of freedom. A complete optimal
algorithm can therefore be found by choosing this parameter optimally for each
pre-processing measurement outcome $\lambda$. Our main result, Theorem 4.7, is
a simple linear program that describes the optimal choice.

###  4.1 Representation theory refresher

Let us briefly recall some basic facts about the representation theory of
$\mathrm{U}(2)$ and $\mathrm{SU}(2)$. For more details, see Appendix C.

Any (polynomial) irreducible representation of $\mathrm{U}(2)$ is given by a
map $Q_{\lambda}:\mathrm{U}(2)\to\mathrm{U}(m_{\lambda})$, where
$\lambda=(\lambda_{1},\lambda_{2})$ for some integers
$\lambda_{1}\geq\lambda_{2}\geq 0$, and
$m_{\lambda}:=\lambda_{1}-\lambda_{2}+1$. Alternatively, we can use parameters
$r:=\lambda_{2}\geq 0$ and $\ell:=\lambda_{1}-\lambda_{2}\geq 0$, see Fig. 4,
so that

$(\lambda_{1},\lambda_{2})=(r+\ell,r).$ (4.1)

Note that $\lambda$ is a partition of $n=\lambda_{1}+\lambda_{2}=2r+\ell$.
With these conventions,

$Q_{\lambda}(M):=(\det M)^{r}T^{\ell}(M),\qquad\forall
M\in\mathrm{L}(\mathbb{C}^{2}),$ (4.2)

where $\det M$ denotes the determinant of $M$ and the map
$T^{\ell}:\mathrm{L}(\mathbb{C}^{2})\to\mathrm{L}(\mathbb{C}^{\ell+1})$ is
explicitly described in Section C.1. The matrix entries of $T^{\ell}(M)$ are
degree-$\ell$ homogeneous polynomials in the entries of $M$ (e.g.,
$T^{0}(M)=1$ and $T^{1}(M)=M$). Since $n$ is required to be odd for an
$n$-variable Boolean function to be equivariant, see Section 2.3, we cannot
have $\ell=0$. From now on we assume that $\ell\geq 1$.

$\lambda_{1}$$\lambda_{2}=r$$\ell$ Figure 4: Correspondence between the
parameters $r,\ell$ and partitions $\lambda=(\lambda_{1},\lambda_{2})$ in eq.
4.1. The total number of boxes is $n=\lambda_{1}+\lambda_{2}=2r+\ell$.

If $M\in\mathrm{L}(\mathbb{C}^{2})$ is invertible, we denote its _dual_ 777Not
to be confused with $\overline{M}$, the entry-wise complex conjugate of $M$.
Note that $M^{*}=\overline{M}$ only when $M$ is unitary. by
$M^{*}:=(M^{-1})^{\mathsf{T}}$. Note that $M\mapsto M^{*}$ is a homomorphism,
also known as the _dual of the defining representation_. Its tensor product
$M^{*}\otimes T^{\ell}(M)$ with any of the representations $T^{\ell}$ is also
a representation, albeit not irreducible. It is decomposed into irreducibles
by the _dual Clebsch–Gordan transform_
$D_{\ell}\in\mathrm{U}(\mathbb{C}^{2(\ell+1)})$:

$D_{\ell}\big{\lparen}M^{*}\otimes
T^{\ell}(M)\big{\rparen}D^{\dagger}_{\ell}=T^{\ell-1}(M)\oplus\frac{1}{\det
M}T^{\ell+1}(M).$ (4.3)

Note that both sides have the same dimension since
$2\cdot(\ell+1)=\ell+(\ell+2)$. Moreover, when multiplied by $\det M$, the
matrix entries on both sides are polynomials of degree $\ell+1$ in the matrix
entries of $M$. While eq. 4.3 can be taken as an implicit
definition888Multiplying both sides of eq. 4.3 from the right by $D_{\ell}$
and comparing the coefficients at all monomials produces a linear system of
equations that determines $D_{\ell}$ almost uniquely (up to two signs). of
$D_{\ell}$, we also provide an explicit formula in eq. C.54. For more details
on $D_{\ell}$, see Section C.7.

###  4.2 Two extremal channels

Recall from Lemma 3.2 that the generic pre-processing $\Gamma$ given by
Section 3.4 produces a measurement outcome
$\lambda=(\lambda_{1},\lambda_{2})\mathbin{\vdash}n$ and a corresponding post-
measurement state of dimension $m_{\lambda}=\ell+1$ where
$\ell:=\lambda_{1}-\lambda_{2}\geq 1$. From Corollary 2.10 we know that an
optimal algorithm for computing a function in a basis-independent way can be
assumed to be unitary-equivariant. Therefore, to complete the algorithm it
suffices to consider only unitary-covariant channels from
$\mathbb{C}^{\ell+1}$ to a single qubit. Following Definition 2.9, we denote
the set of such channels by $\mathrm{UC}(\mathbb{C}^{\ell+1},\mathbb{C}^{2})$,
where the $\mathrm{U}(2)$-representations on the input and output spaces are
$T^{\ell}(U)$ and $T^{1}(U)=U$, respectively. It turns out that, irrespective
of the value of $\ell\geq 1$, any such channel can be described by a single
parameter. The following lemma proves this and derives the Choi matrices of
the two extremal channels.

######  Lemma 4.1.

For any integer $\ell\geq 1$, the set
$\mathrm{UC}(\mathbb{C}^{\ell+1},\mathbb{C}^{2})$ of unitary-covariant
channels is convex with two extremal points. The Choi matrices of the two
extremal channels are

$\displaystyle J(\Phi^{\ell}_{1})$
$\displaystyle=D^{\dagger}_{\ell}\left[\frac{\ell+1}{\ell}I_{\ell}\oplus
0_{\ell+2}\right]D_{\ell},$ $\displaystyle J(\Phi^{\ell}_{2})$
$\displaystyle=D^{\dagger}_{\ell}\left[0_{\ell}\oplus\frac{\ell+1}{\ell+2}I_{\ell+2}\right]D_{\ell},$
(4.4)

where $D_{\ell}\in\mathrm{U}(\mathbb{C}^{2(\ell+1)})$ denotes the dual
Clebsch–Gordan transform (see eq. 4.3 or Section C.7) and $0_{d}$ denotes the
$d\times d$ all-zeroes matrix. In particular, their Choi ranks are
$\operatorname{rank}J(\Phi^{\ell}_{1})=\ell$ and
$\operatorname{rank}J(\Phi^{\ell}_{2})=\ell+2$, and they satisfy

$\ell J(\Phi^{\ell}_{1})+(\ell+2)J(\Phi^{\ell}_{2})=(\ell+1)I_{2(\ell+1)}.$
(4.5)

###### Proof.

The set $\mathrm{UC}(\mathbb{C}^{\ell+1},\mathbb{C}^{2})$ is convex since it
is the intersection of two convex sets – the set of all channels and the set
of all unitary-covariant maps from $\mathrm{L}(\mathbb{C}^{\ell+1})$ to
$\mathrm{L}(\mathbb{C}^{2})$.

To argue that there are only two extremal points, consider an arbitrary
channel $\Phi\in\mathrm{UC}(\mathbb{C}^{\ell+1},\mathbb{C}^{2})$. From
Corollary 2.12 we know that its Choi matrix $J(\Phi)$ commutes with
$\overline{U}\otimes T^{\ell}(U)$, for all unitaries $U\in\mathrm{U}(2)$. Note
that $\overline{U}=(U^{\dagger})^{\mathsf{T}}=(U^{-1})^{\mathsf{T}}=U^{*}$, so
based on eq. 4.3 we can use the dual Clebsch–Gordan transform $D_{\ell}$ to
decompose $\overline{U}\otimes T^{\ell}(U)$ as a direct sum:

$D_{\ell}\big{\lparen}\overline{U}\otimes
T^{\ell}(U)\big{\rparen}D^{\dagger}_{\ell}=T^{\ell-1}(U)\oplus\tfrac{1}{\det
U}T^{\ell+1}(U),$ (4.6)

where the two blocks are of dimension $\ell$ and $\ell+2$, respectively. Since
the representations $T^{\ell\pm 1}$ are irreducible (see Lemma C.2), we can
use Schur’s lemma (Lemma 2.1) to conclude that in the dual Clebsch–Gordan
basis $J(\Phi)$ takes the form

$D_{\ell}J(\Phi)D^{\dagger}_{\ell}=c_{1}I_{\ell}\oplus c_{2}I_{\ell+2},$ (4.7)

for some $c_{1},c_{2}\in\mathbb{C}$.

Let us consider the CPTP constraints (2.7) for the quantum channel $\Phi$.
Since $\Phi$ is completely positive, $c_{1},c_{2}\geq 0$. Since $\Phi$ is
trace-preserving, on the one hand
$\operatorname{Tr}J(\Phi)=\operatorname{Tr}(I_{\ell+1})=\ell+1$, while on the
other we see from eq. 4.7 that $\operatorname{Tr}J(\Phi)=\ell
c_{1}+(\ell+2)c_{2}$, so

$\ell+1=\ell c_{1}+(\ell+2)c_{2}.$ (4.8)

Because of this constraint there is only one free parameter. Furthermore,
since $c_{1},c_{2}\geq 0$, there are two extremal points:

$\displaystyle(c_{1},c_{2})$ $\displaystyle=(\tfrac{\ell+1}{\ell},0),$
$\displaystyle(c_{1},c_{2})$ $\displaystyle=(0,\tfrac{\ell+1}{\ell+2}).$ (4.9)

Substituting them in eq. 4.7, the corresponding two extremal channels
$\Phi^{\ell}_{1}$ and $\Phi^{\ell}_{2}$ have Choi matrices

$\displaystyle D_{\ell}J(\Phi^{\ell}_{1})D^{\dagger}_{\ell}$
$\displaystyle=\frac{\ell+1}{\ell}I_{\ell}\oplus 0_{\ell+2},$ $\displaystyle
D_{\ell}J(\Phi^{\ell}_{2})D^{\dagger}_{\ell}$
$\displaystyle=0_{\ell}\oplus\frac{\ell+1}{\ell+2}I_{\ell+2}$ (4.10)

in the dual Clebsch–Gordan basis. Clearly,
$\operatorname{rank}J(\Phi^{\ell}_{1})=\ell$ and
$\operatorname{rank}J(\Phi^{\ell}_{2})=\ell+2$, and

$\ell J(\Phi^{\ell}_{1})+(\ell+2)J(\Phi^{\ell}_{2})=(\ell+1)I_{\ell+(\ell+2)}$
(4.11)

since $D_{\ell}$ is unitary. ∎

######  Example 4.2 (Extremal channels for $\ell=1$).

Choi matrices of the two $\ell=1$ extremal channels are:

$\displaystyle J(\Phi^{1}_{1})$ $\displaystyle=\begin{pmatrix}1&0&0&1\\\
0&0&0&0\\\ 0&0&0&0\\\ 1&0&0&1\end{pmatrix},$ $\displaystyle J(\Phi^{1}_{2})$
$\displaystyle=\frac{1}{3}\begin{pmatrix}1&0&0&-1\\\ 0&2&0&0\\\ 0&0&2&0\\\
-1&0&0&1\end{pmatrix}.$ (4.12)

Note that $J(\Phi^{1}_{1})+3J(\Phi^{1}_{2})=2I_{4}$, which agrees with eq.
4.11 when $\ell=1$. The corresponding dual Clebsch–Gordan transform (see
Section C.7) is given by999In the context of mixed Schur–Weyl duality, this
transform also appears in Example 3.9 of [GO22]. The matrix $U$ in eq. (58)
there slightly differs from our $D_{1}$ due to different conventions.

$D_{1}=\frac{1}{\sqrt{2}}\begin{pmatrix}1&0&0&1\\\ 0&0&\sqrt{2}&0\\\
-1&0&0&1\\\ 0&-\sqrt{2}&0&0\end{pmatrix}.$ (4.13)

In particular,
$D_{1}J(\Phi^{1}_{1})D^{\dagger}_{1}=\operatorname{diag}(2,0,0,0)$ and
$D_{1}J(\Phi^{1}_{2})D^{\dagger}_{1}=\operatorname{diag}(0,\frac{2}{3},\frac{2}{3},\frac{2}{3})$
as claimed. Since the Choi matrix (2.25) of the ideal universal $\mathrm{NOT}$
operation can be expressed as
$J(\mathrm{UNOT})=-\frac{1}{2}J(\Phi^{1}_{1})+\frac{3}{2}J(\Phi^{1}_{2})$, the
ideal operation is not completely positive.

###  4.3 Understanding the extremal channels

This section provides an intuitive way to think about the above two extremal
channels and shows that they are related to the partial trace and the
universal $\mathrm{NOT}$.

Let us denote the _symmetric subspace_ of $\ell\geq 1$ qubits by

$\mathrm{Sym}(\ell):=\operatorname{span}\big{\\{}|{s_{\ell}(w)}\rangle:w\in\\{0,\dotsc,\ell\\}\big{\\}}\subseteq\lparen\mathbb{C}^{2}\rparen^{\otimes\ell},$
(4.14)

where $|{s_{\ell}(w)}\rangle$ is the symmetric $\ell$-qubit state of Hamming
weight $w$, see eq. 3.12. Since
$\langle{s_{\ell}(w)}|{s_{\ell}(w^{\prime})}\rangle=\delta_{ww^{\prime}}$, the
projector onto the $\ell$-qubit symmetric subspace can be written as

$\displaystyle\Pi_{\mathrm{Sym}(\ell)}:=\sum_{w=0}^{\ell}|{s_{\ell}(w)}\rangle\langle{s_{\ell}(w)}|=\frac{1}{\ell!}\sum_{\pi\in\mathrm{S}_{\ell}}P(\pi)=(\ell+1)\int\big{\lparen}|{\psi}\rangle\langle{\psi}|\big{\rparen}^{\otimes\ell}\,d\psi,$
(4.15)

where $P(\pi)\in\mathrm{U}(2^{\ell})$ are the $\ell$-qubit permutations
defined in eq. 2.1 and $d\psi$ denotes the uniform measure on the Bloch
sphere, see eq. 2.4. The last two identities are proved in Lemma D.1. For more
details on the symmetric subspace, see Appendix D.

Let
$V^{\ell}\in\mathrm{U}(\mathbb{C}^{\ell+1},\lparen\mathbb{C}^{2}\rparen^{\otimes\ell})$
denote the isometry that maps the $k$-th standard basis state of
$\mathbb{C}^{\ell+1}$ to the symmetric state $|{s_{\ell}(k)}\rangle$ of
Hamming weight $k$ in the $\ell$-qubit symmetric subspace:

$\displaystyle V^{\ell}:=\sum_{k=0}^{\ell}|{s_{\ell}(k)}\rangle\langle{k}|,$
(4.16)

and let
$\Sigma^{\ell}\in\mathrm{C}(\mathbb{C}^{\ell+1},\lparen\mathbb{C}^{2}\rparen^{\otimes\ell})$
denote the quantum channel corresponding to the isometry $V^{\ell}$:

$\Sigma^{\ell}(\rho):=V^{\ell}\rho V^{\ell\dagger},$ (4.17)

for all $\rho\in\mathrm{L}(\mathbb{C}^{\ell+1})$.

The following two maps from $\mathrm{L}(\mathbb{C}^{\ell+1})$ to
$\mathrm{L}(\mathbb{C}^{2})$ will play an important role. They first embed the
input into the $\ell$-qubit symmetric subspace $\mathrm{Sym}(\ell)$. The first
map then traces out all qubits but the first, while the second performs the
uniform measurement on all tensor power states and outputs for each outcome
the corresponding orthogonal state. Because of this, we denote them by
$\Phi^{\ell}_{\operatorname{Tr}}$ and $\Phi^{\ell}_{\mathrm{UNOT}}$,
respectively.

######  Definition 4.3 ($\Phi^{\ell}_{\operatorname{Tr}}$ and
$\Phi^{\ell}_{\mathrm{UNOT}}$).

For any integer $\ell\geq 1$, let
$\Phi^{\ell}_{\operatorname{Tr}},\Phi^{\ell}_{\mathrm{UNOT}}:\mathrm{L}(\mathbb{C}^{\ell+1})\to\mathrm{L}(\mathbb{C}^{2})$
act on $\rho\in\mathrm{L}(\mathbb{C}^{\ell+1})$ as follows:

$\displaystyle\Phi^{\ell}_{\operatorname{Tr}}(\rho)$
$\displaystyle:=\operatorname{Tr}_{2,\dotsc,\ell}\left[\Sigma^{\ell}(\rho)\right],$
(4.18) $\displaystyle\Phi^{\ell}_{\mathrm{UNOT}}(\rho)$
$\displaystyle:=(\ell+1)\int\langle{\psi}|^{\otimes\ell}\left[\Sigma^{\ell}(\rho)\right]|{\psi}\rangle^{\otimes\ell}\big{\lparen}I_{2}-|{\psi}\rangle\langle{\psi}|\big{\rparen}\,d\psi,$
(4.19)

where $|{\psi}\rangle\in\mathbb{C}^{2}$ and $d\psi$ denotes the uniform
measure on the Bloch sphere, see eq. 2.4. Sometimes we will use the notation
$\Phi^{\lambda}_{\operatorname{Tr}}:=\Phi^{\ell}_{\operatorname{Tr}}$ and
$\Phi^{\lambda}_{\mathrm{UNOT}}:=\Phi^{\ell}_{\mathrm{UNOT}}$ where
$\lambda=(\lambda_{1},\lambda_{2})$ and $\ell:=\lambda_{1}-\lambda_{2}$.

Let us verify that both maps are in fact quantum channels.

######  Proposition 4.4.

For any integer $\ell\geq 1$, the maps $\Phi^{\ell}_{\operatorname{Tr}}$ and
$\Phi^{\ell}_{\mathrm{UNOT}}$ are quantum channels.

###### Proof.

Let us verify that $\Phi^{\ell}_{\operatorname{Tr}}$ and
$\Phi^{\ell}_{\mathrm{UNOT}}$ conform to Stinespring and Kraus
representations, respectively (see Section E.1 for more background on quantum
channel representations).

It is evident that $\Phi^{\ell}_{\operatorname{Tr}}$ is a quantum channel
since eq. 4.18 constitutes its Stinespring dilation. Similarly, eq. 4.19
constitutes a Kraus representation of $\Phi^{\ell}_{\mathrm{UNOT}}$:

$\Phi^{\ell}_{\mathrm{UNOT}}(\rho)=\int K^{\ell}_{\psi}\rho
K^{\ell\dagger}_{\psi}\,d\psi,$ (4.20)

with Kraus operators
$K^{\ell}_{\psi}:=\sqrt{\ell+1}|{\psi^{\perp}}\rangle\cdot\langle{\psi}|^{\otimes\ell}V^{\ell}\in\mathrm{L}(\mathbb{C}^{\ell+1},\mathbb{C}^{2})$
where $|{\psi^{\perp}}\rangle\in\mathbb{C}^{2}$ is such that
$|{\psi^{\perp}}\rangle\langle{\psi^{\perp}}|=I_{2}-|{\psi}\rangle\langle{\psi}|$.
In particular, $\Phi^{\ell}_{\mathrm{UNOT}}$ is completely positive. To verify
that $\Phi^{\ell}_{\mathrm{UNOT}}$ is trace-preserving, we compute

$\int K^{\ell\dagger}_{\psi}K^{\ell}_{\psi}\,d\psi=(\ell+1)\int
V^{\ell\dagger}\big{\lparen}|{\psi}\rangle\langle{\psi}|\big{\rparen}^{\otimes\ell}V^{\ell}\,d\psi=V^{\ell\dagger}\Pi_{\mathrm{Sym}(\ell)}V^{\ell}=I_{\ell+1},$
(4.21)

where the last two equalities follow from eq. 4.15 and the fact that
$V^{\ell}$ defined in eq. 4.16 is an isometry. ∎

Lemma E.4 in Section E.4 identifies the above two quantum channels with the
two extremal channels from Lemma 4.1:

$\displaystyle\Phi^{\ell}_{1}$
$\displaystyle=\Phi^{\ell}_{\operatorname{Tr}},$
$\displaystyle\Phi^{\ell}_{2}$ $\displaystyle=\Phi^{\ell}_{\mathrm{UNOT}}.$
(4.22)

Hence, we conclude from Lemma 4.1 that any unitary-covariant quantum channel
from $\mathbb{C}^{\ell+1}$ to $\mathbb{C}^{2}$ must be a convex combination of
$\Phi^{\ell}_{\operatorname{Tr}}$ and $\Phi^{\ell}_{\mathrm{UNOT}}$.

######  Corollary 4.5.

Any unitary-covariant quantum channel
$\Phi_{\ell}\in\mathrm{UC}(\mathbb{C}^{\ell+1},\mathbb{C}^{2})$ is of the form

$\Phi_{\ell}=t\Phi^{\ell}_{\operatorname{Tr}}+(1-t)\Phi^{\ell}_{\mathrm{UNOT}},$
(4.23)

for some $t\in[0,1]$, where
$\Phi^{\ell}_{\operatorname{Tr}},\Phi^{\ell}_{\mathrm{UNOT}}\in\mathrm{UC}(\mathbb{C}^{\ell+1},\mathbb{C}^{2})$
are defined in Definition 4.3.

###  4.4 The optimal algorithm and its fidelity

In this section, we describe a parametrized _template algorithm_
$\mathcal{A}_{\mathbf{t}}$ (see Section 4.4) that depends on a vector of
_interpolation parameters_ $\mathbf{t}=\lparen
t_{\lambda}\in[0,1]:\lambda\mathbin{\vdash}n\rparen$. First, it applies the
generic pre-processing $\Gamma$ (see Section 3.4) and then, depending on the
measurement outcome $\lambda$, a general unitary-covariant channel
$\Phi_{\lambda}$. According to Corollary 4.5, $\Phi_{\lambda}$ is a convex
combination
$t_{\lambda}\Phi^{\lambda}_{\operatorname{Tr}}+(1-t_{\lambda})\Phi^{\lambda}_{\mathrm{UNOT}}$
of the two extremal maps discussed in Section 4.3, with some interpolation
parameter $t_{\lambda}\in[0,1]$. The following theorem shows that, for any
symmetric and equivariant Boolean function $f$, the optimal fidelity for
computing $f$ in a basis-independent way can be achieved by the algorithm
$\mathcal{A}_{\mathbf{t}}$ with appropriately chosen interpolation parameters
$\mathbf{t}$.

######  Theorem 4.6.

Let $f:\\{0,1\\}^{n}\to\\{0,1\\}$ be a symmetric and equivariant Boolean
function. For some choice of interpolation parameters $\mathbf{t}$, the
quantum channel
$\mathcal{A}_{\mathbf{t}}\in\mathrm{C}(\mathbb{C}^{2^{n}},\mathbb{C}^{2})$
implemented by Section 4.4 is optimal for computing $f$ in a basis-independent
way. Moreover, $\mathcal{A}_{\mathbf{t}}$ is permutation-invariant and
unitary-equivariant.

Algorithm 2: Template algorithm $\mathcal{A}_{\mathbf{t}}$ Input: Quantum
state $U^{\otimes n}|{x}\rangle$ with an unknown $x\in\\{0,1\\}^{n}$ and
$U\in\mathrm{U}(2)$. Output: An approximation of $U|{f(x)}\rangle$.
Parameters: A vector of _interpolation parameters_ $\mathbf{t}=\lparen
t_{\lambda}\in[0,1]:\lambda\mathbin{\vdash}n\rparen$. Step 1: Perform the
generic pre-processing $\Gamma$ (see Section 3.4). Step 2: If the measurement
outcome was $\lambda$, apply the channel (see Definition 4.3)
$\Phi_{\lambda}:=t_{\lambda}\Phi^{\lambda}_{\operatorname{Tr}}+(1-t_{\lambda})\Phi^{\lambda}_{\mathrm{UNOT}}$

###### Proof.

Based on Corollary 3.6, an optimal quantum channel for computing $f$ is of the
form $\Phi^{\prime}\circ\Gamma$, where $\Gamma$ is the generic pre-processing
(see Section 3.4) and $\Phi^{\prime}$ is some unitary-covariant channel.
Depending on the measurement outcome $\lambda=(\lambda_{1},\lambda_{2})$
obtained by $\Gamma$, the second step $\Phi^{\prime}$ simply consists of
applying some unitary-covariant channel
$\Phi_{\lambda}\in\mathrm{UC}(\mathbb{C}^{\ell+1},\mathbb{C}^{2})$ on the
remaining $(\ell+1)$-dimensional state where $\ell:=\lambda_{1}-\lambda_{2}$.

According to Corollary 4.5, the unitary-covariant channel $\Phi_{\lambda}$ is
a convex combination of the two extremal channels
$\Phi^{\lambda}_{\operatorname{Tr}}$ and $\Phi^{\lambda}_{\mathrm{UNOT}}$
introduced in Definition 4.3:

$\Phi_{\lambda}:=t_{\lambda}\Phi^{\lambda}_{\operatorname{Tr}}+(1-t_{\lambda})\Phi^{\lambda}_{\mathrm{UNOT}},$
(4.24)

for some parameter $t_{\lambda}\in[0,1]$. Since Section 4.4 describes a
general quantum channel $\mathcal{A}_{\mathbf{t}}$ that consists of applying
$\Gamma$ followed by some unitary-covariant $\Phi_{\lambda}$, an optimal
channel for computing $f$ can be found by optimizing the parameters
$\mathbf{t}$ in $\mathcal{A}_{\mathbf{t}}$. The template algorithm
$\mathcal{A}_{\mathbf{t}}$ is permutation-invariant since so is $\Gamma$ (see
Lemma 3.1), and it is unitary-equivariant since it is a composition of two
unitary-covariant channels (see Lemmas 3.1 and 4.5). ∎

Based on Theorem 4.6, we can find an optimal quantum channel for any symmetric
and equivariant Boolean function $f$ simply by finding for each measurement
outcome $\lambda\mathbin{\vdash}n$ an optimal choice of the corresponding
parameter $t_{\lambda}\in[0,1]$ that determines the probability of applying
$\Phi^{\lambda}_{\operatorname{Tr}}$ versus $\Phi^{\lambda}_{\mathrm{UNOT}}$
in Step 2 of Section 4.4. Our main result, Theorem 4.7 below, shows that the
optimal fidelity $F_{f}$ and an optimal choice of the interpolation parameters
$\mathbf{t}$ in the template algorithm $\mathcal{A}_{\mathbf{t}}$ can be found
by solving a linear program of size $O(n)$. The resulting algorithm
$\mathcal{A}_{\mathbf{t}}$ computes $f$ with optimal fidelity.

######  Theorem 4.7.

Let $f:\\{0,1\\}^{n}\to\\{0,1\\}$ be a symmetric and equivariant Boolean
function. The optimal fidelity $F_{f}$ for computing $f$ in a basis-
independent way can be found by solving the following linear program with
$\lfloor n/2\rfloor+2$ variables and $3\lfloor n/2\rfloor+3$ constraints:

$\begin{array}[]{llll}&F_{f}=\displaystyle\max_{c,\mathbf{t}}c\\\ &\text{such
that}&\displaystyle\sum_{k=0}^{h}p_{k}(h)\Big{[}t_{k}a_{k}(h)+(1-t_{k})b_{k}(h)\Big{]}\geq
c,&\forall
h\in\left\\{0,\dotsc,\left\lfloor\frac{n}{2}\right\rfloor\right\\},\\\ &&0\leq
t_{k}\leq 1,&\forall
k\in\left\\{0,\dotsc,\left\lfloor\frac{n}{2}\right\rfloor\right\\}.\end{array}$
(LP)

Here we are using the following shorthands:

$\displaystyle p_{k}(h)$
$\displaystyle:=\frac{\binom{n}{k}-\binom{n}{k-1}}{\binom{n}{h}},$ (4.25)
$\displaystyle a_{k}(h)$
$\displaystyle:=\frac{n-h-k}{n-2k}-\bar{f}(h)\frac{n-2h}{n-2k},$ (4.26)
$\displaystyle b_{k}(h)$
$\displaystyle:=\frac{h-k+1}{n-2k+2}+\bar{f}(h)\frac{n-2h}{n-2k+2},$ (4.27)

where $\bar{f}(h):=f(0^{n-h}1^{h})$ denotes the value of $f$ on strings of
Hamming weight $h$. Given an optimal solution $\left\lparen
t^{*}_{k}:k=0,\dotsc,\lfloor n/2\rfloor\right\rparen$ of the above linear
program, the template algorithm $\mathcal{A}_{\mathbf{t}^{*}}$ (see Section
4.4) achieves the optimal fidelity $F_{f}$ if we set
$t^{*}_{\lambda}:=t^{*}_{k}$ where $\lambda=(n-k,k)$ and
$k\in\\{0,\dotsc,\lfloor n/2\rfloor\\}$.

###### Proof.

According to Theorem 4.6, an optimal quantum channel for computing $f$ can be
found by optimizing the interpolation parameters $\mathbf{t}$ in the template
algorithm $\mathcal{A}_{\mathbf{t}}$ (Section 4.4). Moreover, we also known
from Theorem 4.6 that $\mathcal{A}_{\mathbf{t}}$ is unitary-equivariant, so we
can omit the unitaries $U$ from the input state $U^{\otimes n}|{x}\rangle$ and
consider only standard basis inputs $|{x}\rangle$.

Let us first derive the output of $\mathcal{A}_{\mathbf{t}}$ on input
$x\in\\{0,1\\}^{n}$. The first step of $\mathcal{A}_{\mathbf{t}}$ is the
generic pre-processing $\Gamma$. According to Lemma 3.2,

$\Gamma\big{\lparen}|{x}\rangle\langle{x}|\big{\rparen}=\bigoplus_{\lambda\mathbin{\vdash}n}p_{\lambda}(x)|{w_{\lambda,x}}\rangle\langle{w_{\lambda,x}}|,$
(4.28)

where $w_{\lambda,x}:=\lvert x\rvert-\lambda_{2}$ and the probability
$p_{\lambda}(x)$ of measurement outcome $\lambda$ is given in eq. 3.22. For
each $\lambda$, the second step of $\mathcal{A}_{\mathbf{t}}$ applies the map
$\Phi_{\lambda}:=t_{\lambda}\Phi^{\lambda}_{\operatorname{Tr}}+(1-t_{\lambda})\Phi^{\lambda}_{\mathrm{UNOT}}$
for some $t_{\lambda}\in[0,1]$, so the final state of the overall procedure is

$\mathcal{A}_{\mathbf{t}}\big{\lparen}|{x}\rangle\langle{x}|\big{\rparen}=\sum_{\lambda\mathbin{\vdash}n}p_{\lambda}(x)\left[t_{\lambda}\Phi^{\lambda}_{\operatorname{Tr}}\big{\lparen}|{w_{\lambda,x}}\rangle\langle{w_{\lambda,x}}|\big{\rparen}+(1-t_{\lambda})\Phi^{\lambda}_{\mathrm{UNOT}}\big{\lparen}|{w_{\lambda,x}}\rangle\langle{w_{\lambda,x}}|\big{\rparen}\right],$
(4.29)

where the direct sum has been replaced by a regular sum since the measurement
outcome $\lambda$ is effectively discarded.

If we parameterize the partition as $\lambda=(n-k,k)$, we can sum over
$k\in\\{0,\dotsc,\lfloor n/2\rfloor\\}$ instead of $\lambda\mathbin{\vdash}n$.
Since $p_{\lambda}(x)$ and $w_{\lambda,x}$ depend only on the Hamming weight
$h:=\lvert x\rvert$, we can write them in terms of $k$ and $h$ as follows:
$w_{\lambda,x}=h-k$ and $p_{\lambda}(x)=p_{k}(h)$ where $p_{k}(h)$ is defined
in eq. 4.25. Since $\ell:=\lambda_{1}-\lambda_{2}=n-2\lambda_{2}=n-2k$, we get
from Lemma E.4 that
$\Phi^{\lambda}_{\operatorname{Tr}}=\Phi^{\ell}_{1}=\Phi^{n-2k}_{1}$ and
$\Phi^{\lambda}_{\mathrm{UNOT}}=\Phi^{\ell}_{2}=\Phi^{n-2k}_{2}$. Finally, we
replace $t_{\lambda}$ by the corresponding $t_{k}$. With this notation, eq.
4.29 becomes

$\mathcal{A}_{\mathbf{t}}\big{\lparen}|{x}\rangle\langle{x}|\big{\rparen}=\sum_{k=0}^{h}p_{k}(h)\left[t_{k}\Phi^{n-2k}_{1}\big{\lparen}|{h-k}\rangle\langle{h-k}|\big{\rparen}+(1-t_{k})\Phi^{n-2k}_{2}\big{\lparen}|{h-k}\rangle\langle{h-k}|\big{\rparen}\right],$
(4.30)

where we have truncated the sum at $k=h$ since $p_{\lambda}(x)=0$ when
$k>\lvert x\rvert=h$, see eq. 3.22.

To evaluate the fidelity
$F\big{\lparen}|{f(x)}\rangle,\mathcal{A}_{\mathbf{t}}\big{\lparen}|{x}\rangle\langle{x}|\big{\rparen}\big{\rparen}=\langle{f(x)}|\mathcal{A}_{\mathbf{t}}\big{\lparen}|{x}\rangle\langle{x}|\big{\rparen}|{f(x)}\rangle$
with the correct output state $|{f(x)}\rangle$, we can use linearity and deal
with each term separately. Since $f$ is symmetric, the ideal output state for
an input $x\in\\{0,1\\}^{n}$ of Hamming weight $h:=\lvert x\rvert$ is
$|{f(x)}\rangle=|{f(0^{n-h}1^{h})}\rangle=:|{\bar{f}(h)}\rangle$. If we let

$\displaystyle a_{k}(h)$
$\displaystyle:=\langle{\bar{f}(h)}|\Phi^{n-2k}_{1}\big{\lparen}|{h-k}\rangle\langle{h-k}|\big{\rparen}|{\bar{f}(h)}\rangle,$
(4.31) $\displaystyle b_{k}(h)$
$\displaystyle:=\langle{\bar{f}(h)}|\Phi^{n-2k}_{2}\big{\lparen}|{h-k}\rangle\langle{h-k}|\big{\rparen}|{\bar{f}(h)}\rangle,$
(4.32)

we can write the output fidelity on input $x$ as follows:

$\langle{\bar{f}(h)}|\mathcal{A}_{\mathbf{t}}\big{\lparen}|{x}\rangle\langle{x}|\big{\rparen}|{\bar{f}(h)}\rangle=\sum_{k=0}^{h}p_{k}(h)\Big{[}t_{k}a_{k}(h)+(1-t_{k})b_{k}(h)\Big{]}.$
(4.33)

Since $\mathcal{A}_{\mathbf{t}}$ is permutation-invariant and unitary-
equivariant, according to Lemma 2.13 its fidelity for computing $f$ in a
basis-independent way is

$F_{f}(\mathcal{A}_{\mathbf{t}})=\min_{0\leq h\leq\lfloor
n/2\rfloor}F\big{\lparen}|{f(0^{n-h}1^{h})}\rangle,\mathcal{A}_{\mathbf{t}}(|{0^{n-h}1^{h}}\rangle\langle{0^{n-h}1^{h}}|)\big{\rparen}.$
(4.34)

Hence, it suffices to determine the output fidelity of
$\mathcal{A}_{\mathbf{t}}$ only on input strings of the form $x=0^{n-h}1^{h}$,
for all Hamming weights $h\in\\{0,\dotsc,\lfloor n/2\rfloor\\}$. From eq. 4.33
we see that

$F_{f}(\mathcal{A}_{\mathbf{t}})=\min_{0\leq h\leq\lfloor
n/2\rfloor}\sum_{k=0}^{h}p_{k}(h)\Big{[}t_{k}a_{k}(h)+(1-t_{k})b_{k}(h)\Big{]}.$
(4.35)

The optimal worst-case fidelity $F_{f}$ for computing $f$ can be obtained by
maximizing the interpolation parameters $t_{k}$ and a constant
$c\in\mathbb{R}$, subject to $F_{f}(\mathcal{A}_{\mathbf{t}})\geq c$ and
$0\leq t_{k}\leq 1$ for all
$k\in\left\\{0,\dotsc,\left\lfloor\frac{n}{2}\right\rfloor\right\\}$. This
produces the desired linear program.

To complete the proof, it remains to show that eqs. 4.31 and 4.32 defining
$a_{k}(h)$ and $b_{k}(h)$ agree with eqs. 4.26 and 4.27 in the statement of
the theorem. From Lemma E.3 in Section E.3 we have that for any $\ell\geq 1$
and $w\in\\{0,\dotsc,\ell\\}$,

$\displaystyle\Phi^{\ell}_{1}\big{\lparen}|{w}\rangle\langle{w}|\big{\rparen}$
$\displaystyle=\frac{\ell-w}{\ell}|{0}\rangle\langle{0}|+\frac{w}{\ell}|{1}\rangle\langle{1}|,$
(4.36)
$\displaystyle\Phi^{\ell}_{2}\big{\lparen}|{w}\rangle\langle{w}|\big{\rparen}$
$\displaystyle=\frac{w+1}{\ell+2}|{0}\rangle\langle{0}|+\frac{\ell+1-w}{\ell+2}|{1}\rangle\langle{1}|.$
(4.37)

Substituting $\ell=n-2k$ and $w=h-k$ into these formulas, we find that

$\displaystyle\Phi^{n-2k}_{1}\big{\lparen}|{h-k}\rangle\langle{h-k}|\big{\rparen}$
$\displaystyle=\frac{n-h-k}{n-2k}|{0}\rangle\langle{0}|+\frac{h-k}{n-2k}|{1}\rangle\langle{1}|,$
(4.38)
$\displaystyle\Phi^{n-2k}_{2}\big{\lparen}|{h-k}\rangle\langle{h-k}|\big{\rparen}$
$\displaystyle=\frac{h-k+1}{n-2k+2}|{0}\rangle\langle{0}|+\frac{n-h-k+1}{n-2k+2}|{1}\rangle\langle{1}|.$
(4.39)

Plugging this back into eqs. 4.31 and 4.32 gives us the following explicit
formulas:

$\displaystyle a_{k}(h)$
$\displaystyle=\begin{cases}\frac{n-h-k}{n-2k}&\text{if $\bar{f}(h)=0$},\\\
\frac{h-k}{n-2k}&\text{if $\bar{f}(h)=1$},\end{cases}$ $\displaystyle
b_{k}(h)$ $\displaystyle=\begin{cases}\frac{h-k+1}{n-2k+2}&\text{if
$\bar{f}(h)=0$},\\\ \frac{n-h-k+1}{n-2k+2}&\text{if
$\bar{f}(h)=1$},\end{cases}$ (4.40)

which agree with eqs. 4.26 and 4.27. ∎

######  Theorem 4.8.

For any choice of the interpolation parameters $\mathbf{t}$, the $n$-qubit
template algorithm $\mathcal{A}_{\mathbf{t}}$ (Section 4.4) can be implemented
using $O(n^{4}\log n)$ elementary quantum gates.

###### Proof.

Step 1 of Section 4.4 consists of the generic pre-processing $\Gamma$
described in Section 3.4. The only non-trivial step of $\Gamma$ is the
$n$-qubit Schur transform $U_{\mathrm{Sch}}$, which can be implemented exactly
using $O(n^{4}\log n)$ quantum gates if CNOT and all single-qubit gates are
available [KS18].

Step 2 of Section 4.4 probabilistically applies either