# Quantum advantage and CSP complexity††thanks: This work will appear in the
Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science
(LICS’24). The research leading to these results was supported by UKRI
EP/X024431/1.

Lorenzo Ciardo
University of Oxford
<EMAIL_ADDRESS>
###### Abstract

Information-processing tasks modelled by homomorphisms between relational
structures can witness quantum advantage when entanglement is used as a
computational resource. We prove that the occurrence of quantum advantage is
determined by the same type of algebraic structure (known as a minion) that
captures the polymorphism identities of CSPs and, thus, CSP complexity. We
investigate the connection between the minion of quantum advantage and other
known minions controlling CSP tractability and width. In this way, we make use
of complexity results from the algebraic theory of CSPs to characterise the
occurrence of quantum advantage in the case of graphs, and to obtain new
necessary and sufficient conditions in the case of arbitrary relational
structures.

##  1 Introduction

The _constraint satisfaction problem_ (CSP) is a computational paradigm that
provides a common framework for studying the complexity of a variety of
combinatorial problems. The input consists in a set of variables, a set of
possible values for the variables, and a set of constraints between the
variables; the goal is to determine whether there exists an assignment of
values to the variables that satisfies the constraints. In its full
generality, the CSP is NP-complete. Nevertheless, restricting the admissible
constraints to a selected class can make the problem solvable in polynomial
time. This is the case of linear equations, which can be formulated as a CSP
where all constraints are linear relations between the variables. The theory
of CSP complexity aims at explaining the complexity of a CSP over some
specific type of constraints in terms of the structure of the constraints.

An elegant way of formalising the CSP is through the notion of homomorphisms
between relational structures. A relational structure consists of a set of
vertices and a set of relations on the vertices; for example, a graph is a
relational structure having a single binary symmetric irreflexive relation. A
homomorphism $\mathbf{X}\to\mathbf{Y}$ between two relational structures
$\mathbf{X}$ and $\mathbf{Y}$ is a map between the vertex sets of $\mathbf{X}$
and $\mathbf{Y}$ that preserves all relations, in the sense that the image of
a tuple in a relation of $\mathbf{X}$ must belong to the corresponding
relation of $\mathbf{Y}$. We can then formulate the CSP _parameterised_ by
$\mathbf{Y}$ as the problem of deciding if an arbitrary structure $\mathbf{X}$
admits a homomorphism to $\mathbf{Y}$. In this setting, the relations of
$\mathbf{X}$ encode the tuples of variables that appear in some constraint of
the CSP, while the relations of $\mathbf{Y}$ encode the types of admissible
constraints.

For example, linear equations over a finite field $\mathbb{F}$ of $n$ elements
correspond to $\operatorname{CSP}(\mathbf{Y})$, where the domain of
$\mathbf{Y}$ is $\\{1,\dots,n\\}$, and the relations of $\mathbf{Y}$ are
affine hyperplanes in vector spaces over $\mathbb{F}$. If $\mathbf{Y}$ is the
$n$-clique $\mathbf{K}_{n}$, $\operatorname{CSP}(\mathbf{Y})$ corresponds to
another primary example of a CSP — namely, the _graph $n$-colouring_ problem,
which consists in testing whether the chromatic number of a graph $\mathbf{X}$
is at most $n$. A natural generalisation is the _graph $\mathbf{Y}$-colouring_
problem, which corresponds to $\operatorname{CSP}(\mathbf{Y})$ for some fixed
graph $\mathbf{Y}$. The complexity of graph $n$-colouring was characterised by
Karp [48]: If $n=2$, the problem is in $\operatorname{P}$; otherwise, it is
${\operatorname{NP}}$-complete. Hell and Nešetřil [41] extended the dichotomy
by proving that graph $\mathbf{Y}$-colouring is in $\operatorname{P}$ if
$\mathbf{Y}$ is bipartite, and it is ${\operatorname{NP}}$-complete otherwise.
In [34], Feder and Vardi proposed the conjecture that Karp’s and
Hell–Nešetřil’s dichotomies could in fact extend to all CSPs. Feder–Vardi’s
Dichotomy Conjecture inspired a major research programme in the theory of
CSPs, that culminated twenty years later with its positive resolution obtained
by Bulatov [21] and, independently, by Zhuk [60].

The advent of quantum computation led to the natural programme of
understanding the type of advantage derived by having access to quantum
resources — as opposed to classical resources — in computational tasks. In
order to formalise this notion of _quantum advantage_ for computational tasks
consisting in constraint satisfaction problems, it shall be convenient to
adopt an alternative description of homomorphisms between relational
structures, in terms of winning strategies for non-local games.

For the sake of simplicity, suppose that $\mathbf{X}$ and $\mathbf{Y}$ are two
graphs. The _$\mathbf{X}\mathbf{Y}$ -homomorphism game_, introduced in [53],
involves two players (Alice and Bob) and a Verifier. The Verifier sends Alice
and Bob vertices $x_{A}$ and $x_{B}$ of $\mathbf{X}$, respectively. Alice and
Bob (who cannot communicate during the game, but can agree on a strategy
before the game starts) respond by sending the Verifier vertices $y_{A}$ and
$y_{B}$ of $\mathbf{Y}$, respectively. They win the
$\mathbf{X}\mathbf{Y}$-homomorphism game if $y_{A}$ and $y_{B}$ are adjacent
(resp. equal) vertices of $\mathbf{Y}$ whenever $x_{A}$ and $x_{B}$ are
adjacent (resp. equal) vertices of $\mathbf{X}$. If only resources of
classical type are allowed, the existence of a perfect strategy for this game
— i.e., a strategy that makes Alice and Bob win with probability $1$ — is
equivalent to the existence of a homomorphism $\mathbf{X}\to\mathbf{Y}$. In
fact, a classical perfect strategy simply consists in Alice and Bob sharing a
protocol for selecting some homomorphism $f:\mathbf{X}\to\mathbf{Y}$, and
responding with the vertex $f(x)$ whenever they are sent a vertex $x$ by the
Verifier.

Suppose now that Alice and Bob have access to quantum resources, modelled by
an entangled state in the space $\mathbb{H}_{A}\otimes\mathbb{H}_{B}$, where
$\mathbb{H}_{A}\simeq\mathbb{H}_{B}$ are finite-dimensional (real or complex)
Hilbert spaces. This state is shared by Alice and Bob; the separation between
the two players corresponds to the fact that Alice (resp. Bob) can only
perform measurements on $\mathbb{H}_{A}$ (resp. $\mathbb{H}_{B}$). This extra
resource allows the players to devise quantum-assisted strategies: Each player
performs a positive operator-valued measure of their part of the state, which
results in a vertex of $\mathbf{Y}$ that is then sent to the Verifier. A
_quantum perfect strategy_ over the space
$\mathbb{H}=\mathbb{H}_{A}\simeq\mathbb{H}_{B}$ for the
$\mathbf{X}\mathbf{Y}$-homomorphism game is a quantum-assisted strategy that
makes Alice and Bob win with probability $1$. In this case, $\mathbf{X}$ and
$\mathbf{Y}$ are said to be _quantum homomorphic_ over $\mathbb{H}$. The extra
correlation between the answers of Alice and Bob produced by the entanglement
of the quantum state can result in strategies that are strictly stronger than
classical strategies. In other words, it is possible for two graphs
$\mathbf{X}$ and $\mathbf{Y}$ to be quantum homomorphic even when they are not
homomorphic in the classical sense. In [53], the question of understanding for
which graphs $\mathbf{Y}$ the notions of quantum and classical homomorphisms
differ was posed. More precisely, we say that $\mathbf{Y}$ _has quantum
advantage_ if there exists some graph $\mathbf{X}$ such that $\mathbf{X}$ and
$\mathbf{Y}$ are quantum homomorphic but not classically homomorphic.

######  Question 1 ([53]).

Characterise the class of graphs $\mathbf{Y}$ having quantum advantage.

The notions of quantum perfect strategy, quantum homomorphism, and quantum
advantage that we consider in this work extend those described above, in that
they apply to arbitrary relational structures as opposed to only graphs. This
extension was recently introduced in [2], and it involves a modified version
of the $\mathbf{X}\mathbf{Y}$-homomorphism game discussed above, where the
roles of Alice and Bob are asymmetric: Alice receives a tuple $\mathbf{x}_{A}$
in some relation of $\mathbf{X}$, and returns a tuple $\mathbf{y}_{A}$ in the
corresponding relation of $\mathbf{Y}$; Bob receives a vertex $x_{B}$ of
$\mathbf{X}$ and returns a vertex $y_{B}$ of $\mathbf{Y}$. They win the game
if, whenever $x_{B}$ appears in the tuple $\mathbf{x}_{A}$, $y_{B}$ appears in
the corresponding position of the tuple $\mathbf{y}_{B}$.111If $\mathbf{X}$
and $\mathbf{Y}$ are graphs, it was noted in [2] that this definition results
in a stronger notion of quantum homomorphism than the one from [53]. As we
shall see in Section 6, the results of this paper apply to both definitions.

The main conceptual contribution of this work is to establish that _the
occurrence of quantum advantage is governed by the same type of algebraic
structure that determines the complexity of constraint satisfaction problems_
— namely, the algebraic structure known as a _minion_. We start by discussing
the role of minions in CSP complexity.

The mathematical framework that allowed attacking and, eventually, proving
Feder-Vardi’s Dichotomy Conjecture was the so-called _algebraic approach to
CSPs_ , whose origins can be traced back to [46, 45, 56]. The gist of this
approach is that the complexity of a CSP is entirely determined by a type of
identities satisfied by its higher-order symmetries, known as _polymorphisms_.
A polymorphism of a relational structure $\mathbf{Y}$ is a homomorphism
$\mathbf{Y}^{\ell}\to\mathbf{Y}$, where $\mathbf{Y}^{\ell}$ is the $\ell$-fold
direct power of $\mathbf{Y}$. If $\mathbf{Y}$ and $\mathbf{Y}^{\prime}$ are
two structures such that the set $\operatorname{Pol}(\mathbf{Y})$ of the
polymorphisms of $\mathbf{Y}$ is included in
$\operatorname{Pol}(\mathbf{Y}^{\prime})$ — thus meaning that
$\mathbf{Y}^{\prime}$ has “more symmetries” than $\mathbf{Y}$ — there exists a
specific kind of polynomial-time reduction (known as a _gadget reduction_)
from $\operatorname{CSP}(\mathbf{Y}^{\prime})$ to
$\operatorname{CSP}(\mathbf{Y})$ (in symbols,
$\operatorname{CSP}(\mathbf{Y}^{\prime})\leq_{\operatorname{g}}\operatorname{CSP}(\mathbf{Y})$).
This gives a powerful way of comparing the complexity of different CSPs, by
looking at the properties of their polymorphisms. The implication

$\displaystyle\operatorname{Pol}(\mathbf{Y})\subseteq\operatorname{Pol}(\mathbf{Y}^{\prime})\;\;\;\;\Rightarrow\;\;\;\;\operatorname{CSP}(\mathbf{Y}^{\prime})\leq_{\operatorname{g}}\operatorname{CSP}(\mathbf{Y})$

can in fact be strengthened: As established in [11], in order for a gadget
reduction to exist, it is enough for $\operatorname{Pol}(\mathbf{Y}^{\prime})$
to satisfy all identities of a certain type (known as _height-1_ or _minor_
identities) that are satisfied in $\operatorname{Pol}(\mathbf{Y})$. One can
then endow $\operatorname{Pol}(\mathbf{Y})$ with a particular algebraic
structure (known as _minion_ or _minor-closed class_ [56]) that encodes minor
identities. This results in the stronger implication

$\displaystyle\operatorname{Pol}(\mathbf{Y})\to\operatorname{Pol}(\mathbf{Y}^{\prime})\;\;\;\;\Rightarrow\;\;\;\;\operatorname{CSP}(\mathbf{Y}^{\prime})\leq_{\operatorname{g}}\operatorname{CSP}(\mathbf{Y}),$

where “$\to$” denotes a minor-preserving map (or _minion homomorphism_)
between the minions $\operatorname{Pol}(\mathbf{Y})$ and
$\operatorname{Pol}(\mathbf{Y}^{\prime})$. Furthermore, it was shown in [11]
that the converse of the implication above also holds. In this sense, the
polymorphism minion precisely captures CSP complexity.

#### Contributions

Our first contribution is to show that quantum advantage is a property of the
polymorphism minion, just like CSP complexity. To that end, we construct a
minion ${\mathscr{Q}}_{\mathbb{H}}$ having the property that a structure
$\mathbf{Y}$ has quantum advantage over $\mathbb{H}$ if and only if
${\mathscr{Q}}_{\mathbb{H}}\not\to\operatorname{Pol}(\mathbf{Y})$. This
_quantum minion_ belongs to a particular class of minions identified in [28],
known as _linear minions_. Its objects are tuples of orthogonal subspaces of
the Hilbert space $\mathbb{H}$, while the minors are defined in terms of sums
of linear spaces.

Using this connection, the question “ _Which structures have quantum
advantage?_ ” can be reformulated as “ _Which minions admit a homomorphism
from the quantum minion?_ ”. In other words, the problem of classifying the
occurrence of quantum advantage is translated into the problem of locating
${\mathscr{Q}}_{\mathbb{H}}$ within the preorder on the class of minions
induced by the minion homomorphism relation. We prove the following three
results:

$(i)$ If $\mathbb{H}$ has dimension $1$ or $2$, ${\mathscr{Q}}_{\mathbb{H}}$
is equivalent to the so-called _dictator minion_ ${\mathscr{D}}$ (also known
as projection minion). To show this, we make use of the Hopf fibration of the
complex projective line $\mathbb{C}\textbf{P}^{1}$ into the $2$-sphere
$S^{2}$, which has the property of mapping pairs of orthogonal vectors into
antipodal points. Then, we consider an antipodal partition of $S^{2}$. In this
way, we can select in any element of ${\mathscr{Q}}_{\mathbb{H}}$ a
distinguished coordinate — namely, the coordinate whose corresponding subspace
is mapped by the Hopf fibration to, say, the first part of the partition. The
map assigning to each element of ${\mathscr{Q}}_{\mathbb{H}}$ its
distinguished coordinate is then shown to be a minion homomorphism from
${\mathscr{Q}}_{\mathbb{H}}$ to ${\mathscr{D}}$.
$(ii)$ If $\mathbb{H}$ has dimension at least $3$,
${\mathscr{Q}}_{\mathbb{H}}$ is not equivalent to the dictator minion. Our
proof of this fact works by showing that a homomorphism
${\mathscr{Q}}_{\mathbb{H}}\to{\mathscr{D}}$ would induce a Boolean measure on
the subspaces of $\mathbb{H}$. By virtue of Gleason’s Theorem [39], any
measure $\mu$ on the subspaces of $\mathbb{H}$ must be of the form
$\mu(v)=\operatorname{tr}(m\cdot\operatorname{pr}_{v})$ for some positive
semidefinite linear operator $m$ (where $\operatorname{pr}_{v}$ denotes the
orthogonal projector onto the space $v$). Thus, in particular, $\mu$ must have
a continuous dependence on its inputs, which contradicts the fact that $\mu$
is Boolean.
$(iii)$ For any $\mathbb{H}$, ${\mathscr{Q}}_{\mathbb{H}}$ admits a
homomorphism to a linear minion ${\mathscr{S}}$ introduced in [28] and,
independently, in [15], which captures the power of the _standard semidefinite
programming_ relaxation for CSPs. The result is obtained by projecting a fixed
vector of $\mathbb{H}$ onto the spaces consitituing the elements of
${\mathscr{Q}}_{\mathbb{H}}$. This yields a minion homomorphism from
${\mathscr{Q}}_{\mathbb{H}}$ to a complex version ${\mathscr{S}}_{\mathbb{C}}$
of ${\mathscr{S}}$; then, we show that ${\mathscr{S}}_{\mathbb{C}}$ and
${\mathscr{S}}$ are in fact equivalent.

The minion-theoretic results on ${\mathscr{Q}}_{\mathbb{H}}$ listed above
directly translate into results on the occurrence of quantum advantage. In
particular, $(i)$ implies that quantum advantage can only happen over Hilbert
spaces of dimension $3$ or higher — an instance of the known phenomenon that
strong non-locality cannot be realised by two-qubit systems, see [18, 1]. For
such spaces, $(ii)$ and $(iii)$ yield new sufficient and necessary conditions
for the occurrence of quantum advantage in terms of the complexity of the
corresponding CSP: $(ii)$ implies that, if $\operatorname{CSP}(\mathbf{Y})$ is
not decided by a polynomial-time algorithm, $\mathbf{Y}$ has quantum
advantage; $(iii)$ implies that, if $\mathbf{Y}$ has quantum advantage,
$\operatorname{CSP}(\mathbf{Y})$ has _unbounded width_ 222We also describe an
alternative derivation of this result, by showing that
${\mathscr{Q}}_{\mathbb{H}}$ admits a homomorphism to the _skeletal minion_
introduced in [27], see Remark 26. This minion corresponds to a stronger
version of the _singleton arc consistency_ algorithm for CSPs [33, 12, 24] and
thus, similarly to the minion ${\mathscr{S}}$ of semidefinite programming, it
captures bounded-width CSPs [50]. — where the width of a CSP is a central
notion in the theory of CSP complexity, expressing the power of local-
consistency techniques for its solution [34, 9].

In the case of graphs, the combination of these results completely
characterises the occurrence of quantum advantage: Using Hell–Nešetřil’s
dichotomy for the complexity of graph CSPs (in Bulatov’s reformulation [20] in
terms of polymorphisms), we show that, if $\dim(\mathbb{H})\geq 3$, a graph
has quantum advantage if and only if it is non-bipartite (while, if
$\dim(\mathbb{H})\leq 2$, no graph has quantum advantage as stated above).
This provides a complete answer to Question 1.

Finally, we introduce a natural generalisation of quantum advantage. A
structure $\mathbf{Y}$ having quantum advantage means that the presence of a
quantum homomorphism from $\mathbf{X}$ to $\mathbf{Y}$ is not sufficient to
guarantee the complete classical information $\mathbf{X}\to\mathbf{Y}$. Can it
still provide some _partial_ classical information, in the form of a classical
homomorphism $\mathbf{X}\to\mathbf{Y}^{\prime}$ to a different structure
$\mathbf{Y}^{\prime}$? If the answer is negative, we say that the pair
$(\mathbf{Y},\mathbf{Y}^{\prime})$ has quantum advantage. We show that our
minion framework is also able to capture this more general notion of quantum
advantage. As a consequence, we connect quantum advantage for pairs of
structures to the complexity of a _promise_ variant of CSPs formalised in [6,
14, 8]. In this way, we show that the two notions of quantum advantage do not
collapse, in the sense that there exist two structures $\mathbf{Y}$ and
$\mathbf{Y}^{\prime}$ such that both $\mathbf{Y}$ and $\mathbf{Y}^{\prime}$
have quantum advantage, but the pair $(\mathbf{Y},\mathbf{Y}^{\prime})$ does
not.

#### Related work

Understanding the power of entanglement as a resource in non-local games (like
the homomorphism game described above) is a well-established research
programme in quantum information and theoretical computer science. A prominent
example of this line of work is the
“$\operatorname{MIP}^{*}=\operatorname{RE}$” Theorem, recently proved in [47],
that characterises the class $\operatorname{MIP}^{*}$ of languages decided by
a classical polynomial-time verifier interacting with multiple non-
communicating computationally unbounded players sharing a finite-dimensional
entangled state, as the class $\operatorname{RE}$ of recursively enumerable
languages. In the same line of works, we mention [44, 49, 43, 55].

Quantum perfect strategies in the special case of the graph $n$-colouring
problem (i.e., when $\mathbf{Y}$ is the $n$-clique) and the corresponding
notion of _quantum chromatic number_ were considered in [7, 23, 35, 54, 59,
52, 36, 29]. Boolean CSPs (i.e., $\operatorname{CSP}(\mathbf{Y})$ with
$\mathbf{Y}$ being a Boolean relational structure) that are unsatisfiable but
admit compatible assignments of self-adjoint unitary operators were
characterised in [4]. The relation between this notion of CSP satisfiability
and quantum perfect strategies for non-local games was described in [30], in
the Boolean setting.

Unlike their non-promise variant, the complexity of promise CSPs remains
largely undiscovered: Even the complexity of the promise version of graph
$n$-colouring — known as _approximate graph colouring_ [37] — is unknown in
general. Since the introduction of a minion-based algebraic approach to
promise CSPs in [8], the theory of minions has proved important in the
investigation of this type of problems. For example, minions were used in [27,
28, 15, 16, 32] to describe the power of relaxation techniques for promise
CSPs, and in [51, 26, 25] to investigate the complexity and tractability under
certain relaxation models of approximate graph colouring. Transferring the
geometric techniques we develop in this work for describing the structure of
the quantum minion to other types of minions used in the theory of promise CSP
complexity appears to be an interesting direction for future investigation.

Finally, we note that the dual version of Question 1 — characterise the
structures $\mathbf{X}$ for which there exists some $\mathbf{Y}$ such that
$\mathbf{X}$ and $\mathbf{Y}$ are quantum but not classically homomorphic —
corresponds to the so-called _left-hand side_ CSP (LCSP), where $\mathbf{X}$
is a fixed parameter and $\mathbf{Y}$ is the input. For a single $\mathbf{X}$,
LCSP is always trivially decidable in polynomial time. Hence, LCSP complexity
questions are only studied in the setting where the left-hand side is an
infinite class of structures, and their analysis is not captured by the
algebraic approach [31, 40]. Therefore, our methods are inapplicable for
characterising this dual type of quantum advantage.

##  2 Preliminaries

By $\mathbb{N}$, $\mathbb{R}$, and $\mathbb{C}$ we denote the sets of positive
integer numbers, real numbers, and complex numbers, respectively. For
$\ell\in\mathbb{N}$, $[\ell]$ is the set $\\{1,2,\dots,\ell\\}$. For
$i\leq\ell\in\mathbb{N}$, $\mathbf{e}_{i;\ell}$ is the $i$-th standard unit
vector of length $\ell$ (i.e., the $i$-th entry of $\mathbf{e}_{i;\ell}$ is
$1$ and all other entries are $0$). Given $\ell\in\mathbb{N}$ and a set $S$,
$S^{\ell}$ denotes the set of tuples of elements of $S$ of length $\ell$. For
a complex matrix $M$, we denote the transpose and the conjugate transpose of
$M$ by the symbols $M^{\top}$ and $M^{*}$, respectively.

###  2.1 Finite-dimensional Hilbert spaces

Throughout this work, we let $\mathbb{H}$ denote a finite-dimensional Hilbert
space (i.e., a finite-dimensional complex or real vector space equipped with
an inner product ${\langle\cdot,\cdot\rangle}$). By $\dim(\mathbb{H})$ we
denote the dimension of $\mathbb{H}$, while $\mathbf{0}_{\mathbb{H}}$
indicates the zero vector in $\mathbb{H}$. To avoid trivial cases, we require
$\mathbb{H}\neq\\{\mathbf{0}_{\mathbb{H}}\\}$. Two subsets $v,w$ of
$\mathbb{H}$ are _orthogonal_ (in symbols, $v\perp w$) if
${\langle\mathbf{v},\mathbf{w}\rangle}=0$ for each $\mathbf{v}\in v$,
$\mathbf{w}\in w$. By $v^{\perp}$ we denote the _orthogonal complement_ of
$v$; i.e., the set of all vectors $\mathbf{w}\in\mathbb{H}$ such that
${\langle\mathbf{v},\mathbf{w}\rangle}=0$ for each $\mathbf{v}\in v$. The set
of all linear maps from $\mathbb{H}$ to itself shall be denoted by
$\operatorname{End}_{\mathbb{H}}$. Given
$p,p^{\prime}\in\operatorname{End}_{\mathbb{H}}$, $p+p^{\prime}$ denotes their
_sum_ , $pp^{\prime}$ (or sometimes, for typographical convenience, $p\cdot
p^{\prime}$) denotes their _product_ or _composition_ , while
$[p,p^{\prime}]=pp^{\prime}-p^{\prime}p$ is their _commutator_. The _adjoint_
of $p\in\operatorname{End}_{\mathbb{H}}$ is the unique map
$p^{*}\in\operatorname{End}_{\mathbb{H}}$ satisfying
${\langle\mathbf{h},p^{*}(\mathbf{h}^{\prime})\rangle}={\langle
p(\mathbf{h}),\mathbf{h}^{\prime}\rangle}$ for each
$\mathbf{h},\mathbf{h}^{\prime}\in\mathbb{H}$. $p$ is _self-adjoint_ if
$p^{*}=p$, and it is an _orthogonal projector_ if it is self-adjoint and
idempotent (i.e., if $p^{2}=p=p^{*}$). $\operatorname{Proj}_{\mathbb{H}}$
denotes the set of all orthogonal projectors in
$\operatorname{End}_{\mathbb{H}}$, while $L_{\mathbb{H}}$ denotes the set of
all linear subspaces of $\mathbb{H}$. The function
$\operatorname{rg}_{\bullet}$ sending a linear map
$p\in\operatorname{End}_{\mathbb{H}}$ to its range
$\operatorname{rg}_{p}\subseteq\mathbb{H}$ establishes a bijection between
$\operatorname{Proj}_{\mathbb{H}}$ and $L_{\mathbb{H}}$. We denote the inverse
of this bijection by $\operatorname{pr}_{\bullet}$ (i.e., for any $v\in
L_{\mathbb{H}}$, $\operatorname{pr}_{v}\in\operatorname{Proj}_{\mathbb{H}}$ is
the orthogonal projector onto $v$). By $\operatorname{id}_{\mathbb{H}}$ and
$\mathbx{0}_{\mathbb{H}}$ we denote the identity and zero maps on
$\mathbb{H}$, respectively.

###  2.2 Relational structures

A _signature_ $\sigma$ is a finite set of relation symbols $R$, each with its
_arity_ $\operatorname{ar}(R)\in\mathbb{N}$. A _relational structure_
$\mathbf{X}$ with signature $\sigma$ (in short, a $\sigma$-structure) consists
of a set $X$ (the _domain_ 333Unless otherwise stated, the domains of all
relational structures appearing in this work shall be assumed to be finite. of
$\mathbf{X}$) and a relation $R^{\mathbf{X}}\subseteq
X^{\operatorname{ar}(R)}$ for each symbol $R\in\sigma$. If $\sigma$ contains a
unique symbol $R$ of arity $2$, and the relation $R^{\mathbf{X}}$ is symmetric
and irreflexive (i.e., $(x,x^{\prime})\in R^{\mathbf{X}}$ implies that
$(x^{\prime},x)\in R^{\mathbf{X}}$ and $x\neq x^{\prime}$), $\mathbf{X}$ is
called a (simple) _graph_. Two relational structures $\mathbf{X},\mathbf{Y}$
are _similar_ if they have the same signature. In this case, a _homomorphism_
from $\mathbf{X}$ to $\mathbf{Y}$ is a map $f:X\to Y$ that preserves all
relations; i.e., $f(\mathbf{x})\in R^{\mathbf{Y}}$ for each $\mathbf{x}\in
R^{\mathbf{X}}$, where $f$ is applied entrywise to the entries of
$\mathbf{x}$. We denote the existence of a homomorphism from $\mathbf{X}$ to
$\mathbf{Y}$ by the expression $\mathbf{X}\to\mathbf{Y}$.

Given a $\sigma$-structure $\mathbf{Y}$, the _constraint satisfaction problem_
parameterised by $\mathbf{Y}$ (in short, $\operatorname{CSP}(\mathbf{Y})$) is
the following computational problem: Given as input a $\sigma$-structure
$\mathbf{X}$, output Yes if $\mathbf{X}\to\mathbf{Y}$, and No if
$\mathbf{X}\not\to\mathbf{Y}$.444This is the _decision_ version of
$\operatorname{CSP}(\mathbf{Y})$. In the _search_ version, the problem is to
find an explicit homomorphism $f:\mathbf{X}\to\mathbf{Y}$ for any input
$\mathbf{X}$ such that $\mathbf{X}\to\mathbf{Y}$. The two versions of
$\operatorname{CSP}$ are equivalent up to polynomial-time reductions [22]. For
$\ell\in\mathbb{N}$, we denote by $\mathbf{Y}^{\ell}$ the $\ell$-th _direct
power_ of $\mathbf{Y}$; i.e., $\mathbf{Y}^{\ell}$ is the $\sigma$-structure
whose domain is $Y^{\ell}$ and whose relations are defined as follows: Given
$R\in\sigma$ and any $\ell\times\operatorname{ar}(R)$ matrix $M$ whose rows
are tuples in $R^{\mathbf{Y}}$, the columns of $M$ form a tuple in
$R^{\mathbf{Y}^{\ell}}$. A _polymorphism_ of $\mathbf{Y}$ (of arity $\ell$) is
a homomorphism from $\mathbf{Y}^{\ell}$ to $\mathbf{Y}$. By
$\operatorname{Pol}(\mathbf{Y})$ (resp.
$\operatorname{Pol}^{(\ell)}(\mathbf{Y})$) we denote the set of all
polymorphisms (resp. all polymorphisms of arity $\ell$) of $\mathbf{Y}$.

###  2.3 Quantum advantage

Given two $\sigma$-structures $\mathbf{X}$ and $\mathbf{Y}$, consider a family
$\\{p_{x,y}\\}_{x\in X,\,y\in Y}$ of orthogonal projectors in
$\operatorname{Proj}_{\mathbb{H}}$. For each $R\in\sigma$, $\mathbf{x}\in
X^{\operatorname{ar}(R)}$, and $\mathbf{y}\in Y^{\operatorname{ar}(R)}$,
define $p_{\mathbf{x},\mathbf{y}}=p_{x_{1},y_{1}}\cdot
p_{x_{2},y_{2}}\cdot\ldots\cdot
p_{x_{\operatorname{ar}(R)},y_{\operatorname{ar}(R)}}$. Consider the following
three conditions:

  1. (Q1)

$\sum_{y\in Y}p_{x,y}=\operatorname{id}_{\mathbb{H}}$ for each $x\in X$;

  2. (Q2)

$[p_{x_{i},y},p_{x_{j},y^{\prime}}]=\mathbx{0}_{\mathbb{H}}$ for each
$R\in\sigma$, $\mathbf{x}\in R^{\mathbf{X}}$, $i,j\in[\operatorname{ar}(R)]$,
and $y,y^{\prime}\in Y$;

  3. (Q3)

$p_{\mathbf{x},\mathbf{y}}=\mathbx{0}_{\mathbb{H}}$ for each $R\in\sigma$,
$\mathbf{x}\in R^{\mathbf{X}}$, and $\mathbf{y}\in
Y^{\operatorname{ar}(R)}\setminus R^{\mathbf{Y}}$.

Following [2], we say that $\mathbf{X}$ and $\mathbf{Y}$ are _quantum
homomorphic_ over $\mathbb{H}$ (and write
$\mathbf{X}\to_{\mathbb{H}}\mathbf{Y}$) if there exists a family
$\\{p_{x,y}\\}_{x\in X,\,y\in Y}$ having the three properties listed above. It
was shown in [2] that $\mathbf{X}\to_{\mathbb{H}}\mathbf{Y}$ if and only if
there exists a _quantum perfect strategy_ for the
$\mathbf{X}\mathbf{Y}$-homomorphism game mentioned in the Introduction.
Observe that $\mathbf{X}\to\mathbf{Y}$ always implies
$\mathbf{X}\to_{\mathbb{H}}\mathbf{Y}$. Indeed, if $f:\mathbf{X}\to\mathbf{Y}$
is a homomorphism, letting $p_{x,y}=\operatorname{id}_{\mathbb{H}}$ if
$y=f(x)$ and $p_{x,y}=\mathbx{0}_{\mathbb{H}}$ otherwise yields a proper
quantum homomorphism. We say that $\mathbf{Y}$ _has quantum advantage over
$\mathbb{H}$_ if the converse is not true; i.e., if there exists a
$\sigma$-structure $\mathbf{X}$ such that
$\mathbf{X}\to_{\mathbb{H}}\mathbf{Y}$ but $\mathbf{X}\not\to\mathbf{Y}$. In
terms of the $\mathbf{X}\mathbf{Y}$-homomorphism game, this means that Alice
and Bob can win the game using a quantum-assisted strategy, but they cannot
using a classical strategy.555We point out that, if $\mathbf{X}$ and
$\mathbf{Y}$ are graphs, the definition of quantum homomorphism from [2] is
more restrictive than the one given in [53], in that the latter does not
enforce the commutativity condition (Q2) among the projectors. Nevertheless,
in the case of graphs, our results hold for both notions of quantum
homomorphisms, see Remark 30.

###  2.4 Minions

A minion ${\mathscr{M}}$ is the disjoint union of non-empty sets
${\mathscr{M}}^{(\ell)}$ for $\ell\in\mathbb{N}$, equipped with operations
$(\cdot)_{/\pi}:{\mathscr{M}}^{(\ell)}\to{\mathscr{M}}^{(\ell^{\prime})}$
(known as _minor operations_) for each pair of integers
$\ell,\ell^{\prime}\in\mathbb{N}$ and each map $\pi:[\ell]\to[\ell^{\prime}]$,
which must satisfy the following two conditions:

  * •

$M_{/\operatorname{id}}=M$ for each $\ell\in\mathbb{N}$ and
$M\in{\mathscr{M}}^{(\ell)}$, where $\operatorname{id}$ is the identity map on
the set $[\ell]$;

  * •

$(M_{/\pi})_{/\tilde{\pi}}=M_{/\tilde{\pi}\circ\pi}$ for each
$\ell,\ell^{\prime},\ell^{\prime\prime}\in\mathbb{N}$,
$M\in{\mathscr{M}}^{(\ell)}$, $\pi:[\ell]\to[\ell^{\prime}]$, and
$\tilde{\pi}:[\ell^{\prime}]\to[\ell^{\prime\prime}]$.666Equivalently, we may
define a minion as a functor from the skeleton category of non-empty finite
sets to the category of non-empty sets. The definition of minion as we present
it here was introduced in [16], and it is an abstraction of the _minor-closed
classes of functions_ considered in [56] to study a Galois connection between
functions and relations. In fact, the latter objects are precisely the
function minions of Example 2.

Given $M\in{\mathscr{M}}$, the index $\ell$ for which
$M\in{\mathscr{M}}^{(\ell)}$ is referred to as the _arity_ of $M$. A
_subminion_ of a minion ${\mathscr{M}}$ is a non-empty subset of
${\mathscr{M}}$ that is closed under the minor operations of ${\mathscr{M}}$.
In this work, we shall consider two concrete types of minions, described in
the two examples below.

######  Example 2 (Function minions).

Take two sets $S$ and $T$. For any integer $\ell\in\mathbb{N}$, consider the
set $\mathscr{F}^{(\ell)}_{S,T}$ of all functions from $S^{\ell}$ to $T$.
Given $f\in\mathscr{F}^{(\ell)}_{S,T}$ and $\pi:[\ell]\to[\ell^{\prime}]$, we
let $f_{/\pi}\in\mathscr{F}^{(\ell^{\prime})}_{S,T}$ be the function defined
as follows:

$\displaystyle f_{/\pi}:S^{\ell^{\prime}}$ $\displaystyle\to T$
$\displaystyle(s_{1},\dots,s_{\ell^{\prime}})$ $\displaystyle\mapsto
f(s_{\pi(1)},\dots,s_{\pi(\ell)}).$

The set $\mathscr{F}_{S,T}$ consisting in the disjoint union of all sets
$\mathscr{F}^{(\ell)}_{S,T}$ for $\ell\in\mathbb{N}$ is easily seen to be a
minion. A _function minion_ (over the sets $S$ and $T$) is any subminion of
$\mathscr{F}_{S,T}$.

######  Example 3 (Linear minions).

Let $\mathcal{A}$ be an abelian monoid — i.e., a set equipped with a binary
operation “$+_{\mathcal{A}}$” that is associative and commutative, and admits
an identity element “$0_{\mathcal{A}}$”. Following [28], we let a _linear
minion_ over $\mathcal{A}$ be a non-empty set ${\mathscr{M}}$ of matrices
having entries in $\mathcal{A}$ that is closed under the following elementary
row operations:

  * •

swapping two rows;

  * •

replacing two rows with their sum;

  * •

inserting an extra zero row.

(Here, the sum is the entrywise application of the “$+_{\mathcal{A}}$”
operation, while the zero row is a tuple of copies of “$0_{\mathcal{A}}$”.) We
let ${\mathscr{M}}^{(\ell)}$ be the set of all matrices in ${\mathscr{M}}$
having exactly $\ell$-many rows. Moreover, given a matrix
$M\in{\mathscr{M}}^{(\ell)}$ and a map $\pi:[\ell]\to[\ell^{\prime}]$, we
define $M_{/\pi}$ as the matrix whose $i$-th row, for $i\in[\ell^{\prime}]$,
is the sum of all rows of $M$ having index in $\pi^{-1}(i)$; i.e.,

$\displaystyle\mathbf{e}_{i;\ell^{\prime}}^{\top}M_{/\pi}=\sum_{j\in\pi^{-1}(i)}\mathbf{e}_{j;\ell}^{\top}M.$

Starting from $M$, one can realise $M_{/\pi}$ through a sequence of the
elementary row operations listed above. Therefore,
$M_{/\pi}\in{\mathscr{M}}^{(\ell^{\prime})}$. Furthermore, this choice for the
minor operations guarantees that ${\mathscr{M}}$ is a minion.

Let ${\mathscr{M}}$ and ${\mathscr{N}}$ be two minions. A _minion
homomorphism_ $\xi:{\mathscr{M}}\to{\mathscr{N}}$ is a map from the underlying
set of ${\mathscr{M}}$ to the underlying set of ${\mathscr{N}}$ that

  * •

preserves the arity — i.e., $\xi(M)\in{\mathscr{N}}^{(\ell)}$ if
$M\in{\mathscr{M}}^{(\ell)}$;

  * •

preserves the minors — i.e., $\xi(M_{/\pi})=\xi(M)_{/\pi}$ if
$M\in{\mathscr{M}}^{(\ell)}$ and
$\pi:[\ell]\to[\ell^{\prime}]$.777Equivalently, a minion homomorphism
$\xi:{\mathscr{M}}\to{\mathscr{N}}$ is a natural transformation from
${\mathscr{M}}$ to ${\mathscr{N}}$.

Given a relational structure $\mathbf{Y}$, the set
$\operatorname{Pol}(\mathbf{Y})$ of all polymorphisms of $\mathbf{Y}$ is a
subset of $\mathscr{F}_{Y,Y}$ (as defined in Example 2), it is non-empty
(since it contains the identity homomorphism), and it is closed under the
minor operations of $\mathscr{F}_{Y,Y}$; hence, it is a (function) minion.
Polymorphism minions capture the complexity of CSPs, in the sense of the
following result.

######  Theorem 4 ([11]).

Let $\mathbf{Y}$ and $\mathbf{Y}^{\prime}$ be two relational structures. If
there exists a minion homomorphism
$\operatorname{Pol}(\mathbf{Y})\to\operatorname{Pol}(\mathbf{Y}^{\prime})$,
then $\operatorname{CSP}(\mathbf{Y}^{\prime})$ reduces in polynomial time to
$\operatorname{CSP}(\mathbf{Y})$.888In fact, a log-space reduction from
$\operatorname{CSP}(\mathbf{Y}^{\prime})$ to $\operatorname{CSP}(\mathbf{Y})$
exists.

##  3 The quantum minion

In this section, we describe a new minion that captures quantum advantage. The
geometric properties of this minion shall be used in the later sections to
obtain information on the occurrence of quantum advantage.

Recall that $L_{\mathbb{H}}$ denotes the set of all linear subspaces of
$\mathbb{H}$. Given $v,w\in L_{\mathbb{H}}$, we let
$v\mathbin{\mathchoice{\ooalign{$\displaystyle\boxempty$\cr$\displaystyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\textstyle\boxempty$\cr$\textstyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptstyle\boxempty$\cr$\scriptstyle\mathchoice{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.22362pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.17824pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptscriptstyle\boxempty$\cr$\scriptscriptstyle\mathchoice{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.15973pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.12732pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}}w$
denote their sum as linear spaces; i.e.,
$v\mathbin{\mathchoice{\ooalign{$\displaystyle\boxempty$\cr$\displaystyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\textstyle\boxempty$\cr$\textstyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptstyle\boxempty$\cr$\scriptstyle\mathchoice{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.22362pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.17824pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptscriptstyle\boxempty$\cr$\scriptscriptstyle\mathchoice{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.15973pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.12732pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}}w=\\{\mathbf{v}+\mathbf{w}\mid\mathbf{v}\in
v,\mathbf{w}\in w\\}$. Let $\mathcal{L}_{\mathbb{H}}$ denote the set
$L_{\mathbb{H}}$ equipped with the operation
“$\mathbin{\mathchoice{\ooalign{$\displaystyle\boxempty$\cr$\displaystyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\textstyle\boxempty$\cr$\textstyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptstyle\boxempty$\cr$\scriptstyle\mathchoice{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.22362pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.17824pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptscriptstyle\boxempty$\cr$\scriptscriptstyle\mathchoice{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.15973pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.12732pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}}$”,
and observe that $\mathcal{L}_{\mathbb{H}}$ is an abelian monoid, with the
subspace $\\{\mathbf{0}_{\mathbb{H}}\\}$ as the identity element. For
$\ell\in\mathbb{N}$, consider the set

$\displaystyle{\mathscr{Q}}_{\mathbb{H}}^{(\ell)}=\left\\{\begin{array}[]{llll}\mathbf{q}=\begin{bmatrix}q_{1}\\\
\vdots\\\ q_{\ell}\end{bmatrix}\;\;\;\mbox{such
that}\;\;\;\begin{array}[]{lll}q_{i}\in L_{\mathbb{H}}\mbox{ for each
}i,\\\\[5.0pt] q_{i}\perp q_{j}\mbox{ for each }i\neq j,\\\\[5.0pt]
\displaystyle\mathop{\vphantom{\bigoplus}\mathchoice{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\mathbin{\mathchoice{\ooalign{$\displaystyle\boxempty$\cr$\displaystyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\textstyle\boxempty$\cr$\textstyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptstyle\boxempty$\cr$\scriptstyle\mathchoice{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.22362pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.17824pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptscriptstyle\boxempty$\cr$\scriptscriptstyle\mathchoice{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.15973pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.12732pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}}$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\mathbin{\mathchoice{\ooalign{$\displaystyle\boxempty$\cr$\displaystyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\textstyle\boxempty$\cr$\textstyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptstyle\boxempty$\cr$\scriptstyle\mathchoice{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.22362pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.17824pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptscriptstyle\boxempty$\cr$\scriptscriptstyle\mathchoice{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.15973pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.12732pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}}$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\mathbin{\mathchoice{\ooalign{$\displaystyle\boxempty$\cr$\displaystyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\textstyle\boxempty$\cr$\textstyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptstyle\boxempty$\cr$\scriptstyle\mathchoice{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.22362pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.17824pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptscriptstyle\boxempty$\cr$\scriptscriptstyle\mathchoice{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.15973pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.12732pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}}$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\mathbin{\mathchoice{\ooalign{$\displaystyle\boxempty$\cr$\displaystyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\textstyle\boxempty$\cr$\textstyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptstyle\boxempty$\cr$\scriptstyle\mathchoice{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.22362pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.17824pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptscriptstyle\boxempty$\cr$\scriptscriptstyle\mathchoice{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.15973pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.12732pt}{\hbox{\set<EMAIL_ADDRESS>
We define the _quantum minion_ ${\mathscr{Q}}_{\mathbb{H}}$ as the disjoint
union of the sets ${\mathscr{Q}}_{\mathbb{H}}^{(\ell)}$ for
$\ell\in\mathbb{N}$.

######  Lemma 5.

${\mathscr{Q}}_{\mathbb{H}}$ is a linear minion over the abelian monoid
$\mathcal{L}_{\mathbb{H}}$.999In fact, ${\mathscr{Q}}_{\mathbb{H}}$ belongs to
a particular class of linear minions known as _conic minions_ , introduced in
[28] (see also [32]).

###### Proof.

All elements of ${\mathscr{Q}}_{\mathbb{H}}$ are vectors (i.e., matrices
having a single column) of spaces in $L_{\mathbb{H}}$. The statement
immediately follows by observing that ${\mathscr{Q}}_{\mathbb{H}}$ is closed
under the three elementary row operations of Example 3. ∎

Using the quantum minion, we will show that quantum advantage is a property of
the polymorphism minion of relational structures. Formally, we will prove the
next result.

######  Theorem 6.

A relational structure $\mathbf{Y}$ has quantum advantage over $\mathbb{H}$ if
and only if ${\mathscr{Q}}_{\mathbb{H}}\not\to\operatorname{Pol}(\mathbf{Y})$.

The proof of Theorem 6 makes use of two ingredients: the _free structures_
from [8] and the _minion tests_ from [28].

Let ${\mathscr{M}}$ be a minion and let $\mathbf{Y}$ be a $\sigma$-structure.
On a high level, the free structure $\mathbb{F}_{{\mathscr{M}}}(\mathbf{Y})$
of ${\mathscr{M}}$ generated by $\mathbf{Y}$ is obtained by simulating the
relations of $\mathbf{Y}$ on a domain consisting of elements of
${\mathscr{M}}$. Formally, following [8], we let
$\mathbb{F}_{{\mathscr{M}}}(\mathbf{Y})$ be the (potentially infinite)
$\sigma$-structure whose domain is the set ${\mathscr{M}}^{(n)}$ (where $n$ is
the domain size of $\mathbf{Y}$) and whose relations are described as follows.
For each symbol $R\in\sigma$, let $m$ be the cardinality of $R^{\mathbf{Y}}$.
A tuple $(M_{1},\dots,M_{\operatorname{ar}(R)})$ of elements of
${\mathscr{M}}^{(n)}$ belongs to $R^{\mathbb{F}_{{\mathscr{M}}}(\mathbf{Y})}$
if and only if there exists some $\tilde{M}\in{\mathscr{M}}^{(m)}$ such that
$M_{i}=\tilde{M}_{/\pi_{i}}$ for each $i\in[\operatorname{ar}(R)]$, where
$\pi_{i}:[m]\to[n]$ is the function mapping each tuple $\mathbf{y}\in
R^{\mathbf{Y}}$ to its $i$-th entry $y_{i}$.101010Here we are implicitly
identifying $Y$ with $[n]$ and $R^{\mathbf{Y}}$ with $[m]$, in order to avoid
introducing extra notation for the bijections between those sets. Notice that
the domain of $\mathbb{F}_{{\mathscr{M}}}(\mathbf{Y})$ can be infinite even
when the domain of $\mathbf{Y}$ is finite. In particular, this is the case for
${\mathscr{M}}={\mathscr{Q}}_{\mathbb{H}}$ (except in the cases where the
dimension of $\mathbb{H}$ or the domain size of $\mathbf{Y}$ equals $1$).

The next result, whose proof is deferred to Appendix A, shows that quantum
homomorphisms correspond to classical homomorphisms to the free structure of
the quantum minion.111111The idea of expressing quantum homomorphisms as
classical homomorphisms to a modified structure already appeared in [53, 2].
More precisely, in the case of graphs, the structure
$\mathbb{F}_{{\mathscr{Q}}_{\mathbb{H}}}(\mathbf{Y})$ of Proposition 7
corresponds to the graph $M(\mathbf{Y},d)$ from [53, Theorem 2.9], where
$d=\dim(\mathbb{H})$. Moreover, for arbitrary relational structures, it
corresponds to the structure $\mathcal{Q}_{d}\mathbf{Y}$, where
$\mathcal{Q}_{d}$ is the _quantum monad_ introduced in [2]. In our setting,
however, it is crucial to formulate Proposition 7 in terms of the free
structure of a minion. This allows us to use the notion of minion tests and,
through Theorem 8, to express quantum advantage as a property of the
polymorphism minion (Theorem 6), thus linking it to the complexity of the
corresponding CSP.

######  Proposition 7.

Let $\mathbf{X},\mathbf{Y}$ be similar relational structures. Then
$\mathbf{X}\to_{\mathbb{H}}\mathbf{Y}$ if and only if
$\mathbf{X}\to\mathbb{F}_{{\mathscr{Q}}_{\mathbb{H}}}(\mathbf{Y})$.

Next, we describe the notion of minion tests from [28]. Let ${\mathscr{M}}$ be
a minion, let $\sigma$ be a signature, and let $\Sigma$ be the class of all
(finite) $\sigma$-structures. Consider the function

$\displaystyle\operatorname{Test}_{{\mathscr{M}}}:\Sigma^{2}$
$\displaystyle\to\\{\textsc{Yes},\textsc{No}\\}$
$\displaystyle(\mathbf{X},\mathbf{Y})$
$\displaystyle\mapsto\left\\{\begin{array}[]{lll}\textsc{Yes}&\mbox{if
}\;\mathbf{X}\to\mathbb{F}_{{\mathscr{M}}}(\mathbf{Y})\\\
\textsc{No}&\mbox{otherwise.}\end{array}\right.$

Fix a $\sigma$-structure $\mathbf{Y}$. It is not hard to verify that
$\mathbf{Y}\to\mathbb{F}_{{\mathscr{M}}}(\mathbf{Y})$ for every
${\mathscr{M}}$. Hence, $\mathbf{X}\to\mathbf{Y}$ implies
$\operatorname{Test}_{{\mathscr{M}}}(\mathbf{X},\mathbf{Y})=\textsc{Yes}$. We
say that $\operatorname{Test}_{{\mathscr{M}}}$ _solves_
$\operatorname{CSP}(\mathbf{Y})$ if the converse implication also holds; i.e.,
if, for every $\sigma$-structure $\mathbf{X}$,
$\operatorname{Test}_{{\mathscr{M}}}(\mathbf{X},\mathbf{Y})=\textsc{Yes}$
implies $\mathbf{X}\to\mathbf{Y}$. As stated next, this can be reformulated in
terms of minion homomorphisms.

######  Theorem 8 ([28]).

Let ${\mathscr{M}}$ be a minion and let $\mathbf{Y}$ be a relational
structure. Then $\operatorname{Test}_{{\mathscr{M}}}$ solves
$\operatorname{CSP}(\mathbf{Y})$ if and only if
${\mathscr{M}}\to\operatorname{Pol}(\mathbf{Y})$.

We can now prove Theorem 6.

###### Proof of Theorem 6.

By virtue of Proposition 7, the existence of a quantum homomorphism over
$\mathbb{H}$ can be viewed as a minion test for the quantum minion
${\mathscr{Q}}_{\mathbb{H}}$. More precisely, given two $\sigma$-structures
$\mathbf{X}$ and $\mathbf{Y}$, $\mathbf{X}\to_{\mathbb{H}}\mathbf{Y}$ if and
only if
$\operatorname{Test}_{{\mathscr{Q}}_{\mathbb{H}}}(\mathbf{X},\mathbf{Y})=\textsc{Yes}$.
Therefore, $\mathbf{Y}$ has quantum advantage over $\mathbb{H}$ precisely when
$\operatorname{Test}_{{\mathscr{Q}}_{\mathbb{H}}}$ does not solve
$\operatorname{CSP}(\mathbf{Y})$. The result then follows from Theorem 8. ∎

##  4 ${\mathscr{Q}}_{\mathbb{H}}$ and the dictator minion

By virtue of Theorem 6, in order to investigate the occurrence of quantum
advantage, one needs to understand the structure of the quantum minion
${\mathscr{Q}}_{\mathbb{H}}$. “Minion homomorphism” is a binary, reflexive,
and transitive relation; thus, it induces a preorder on the class of all
minions. It shall be crucial to obtain information on where
${\mathscr{Q}}_{\mathbb{H}}$ is located within this preorder. We shall see
that, when $\dim(\mathbb{H})\leq 2$, ${\mathscr{Q}}_{\mathbb{H}}$ is a _least
element_ of the preorder, as it is equivalent to a specific minion — known as
the dictator minion — that admits a homomorphism to all minions. This implies
that no structure has quantum advantage over such Hilbert spaces. Things get
more interesting when $\dim(\mathbb{H})\geq 3$. In this case, we shall see
that ${\mathscr{Q}}_{\mathbb{H}}$ is essentially different from the dictator
minion. Through known results on the complexity of CSPs and the theory of
their polymorphism minions, this separation shall lead to a sufficient
condition for the occurrence of quantum advantage.

We start by defining the _dictator minion_ as the linear minion
${\mathscr{D}}$ over the abelian monoid $(\mathbb{R},+)$ consisting of all
standard unit vectors $\mathbf{e}_{i;\ell}$ for $1\leq
i\leq\ell\in\mathbb{N}$.121212Equivalently, we may define ${\mathscr{D}}$ as a
function minion over some finite set with at least two elements, consisting of
functions that project any input tuple onto one fixed coordinate — whence the
alternative name _projection minion_ , which is common in the CSP literature
(see [8]). Yet another description of ${\mathscr{D}}$ is the following: For
$\ell\in\mathbb{N}$, ${\mathscr{D}}^{(\ell)}=[\ell]$; for
$\pi:[\ell]\to[\ell^{\prime}]$ and $i\in{\mathscr{D}}^{(\ell)}$,
$i_{/\pi}=\pi(i)$. The next simple result shows that ${\mathscr{D}}$ is a
least element of the minion homomorphism preorder.131313The minion
homomorphism preorder also has a _greatest element_ : The linear minion (over
any abelian monoid) whose only $\ell$-ary element, for each
$\ell\in\mathbb{N}$, is the all-zero vector of length $\ell$.

######  Lemma 9.

${\mathscr{D}}\to{\mathscr{M}}$ for every minion ${\mathscr{M}}$.

###### Proof.

Fix an element $M\in{\mathscr{M}}^{(1)}$ (which must exist as minions are non-
empty by definition). For $i\leq\ell\in\mathbb{N}$, consider the map
$\pi_{i,\ell}:[1]\to[\ell]$ given by $1\mapsto i$. It is straightforward to
check that the function $\mathbf{e}_{i;\ell}\mapsto M_{/\pi_{i,\ell}}$ yields
a minion homomorphism from ${\mathscr{D}}$ to ${\mathscr{M}}$. ∎

We shall establish the following characterisation of when the quantum minion
admits a homomorphism (and, thus, is homomorphically equivalent) to the
dictator minion.

######  Theorem 10.

${\mathscr{Q}}_{\mathbb{H}}\to{\mathscr{D}}$ if and only if
$\dim(\mathbb{H})\leq 2$.

Our proofs of the two directions of Theorem 10 are both geometric. This is not
surprising, as the quantum minion ${\mathscr{Q}}_{\mathbb{H}}$ has a natural
geometric interpretation.

The “if” part (Proposition 12) is established as follows. First, we show that
every $2$-dimensional Hilbert space can be partitioned into two parts in a way
that any pair of nonzero orthogonal vectors in the space is separated by the
partition. In order to prove this fact, we consider the Hopf fibration of the
complex projective line $\mathbb{C}\textbf{P}^{1}$ into the
$2$-sphere141414This construction results in the object that is sometimes
called the _Riemann sphere_ or _Bloch sphere_. — which has the property of
mapping orthogonal vectors to antipodal points of the sphere. We can then
partition the Hilbert space by taking the preimage under the Hopf fibration of
an antipodal partition of the $2$-sphere.

######  Lemma 11.

If $\dim(\mathbb{H})=2$, there exists $C\subset\mathbb{H}$ such that, given
any two nonzero orthogonal vectors $\mathbf{v},\mathbf{w}\in\mathbb{H}$,
exactly one of $\mathbf{v}$ and $\mathbf{w}$ lies in $C$.

A self-contained proof of Lemma 11 is given in Appendix A. Once such a
partition $\\{C,\mathbb{H}\setminus C\\}$ is fixed, we can select in each pair
of $1$-dimensional orthogonal subspaces of $\mathbb{H}$ a distinguished
element — namely, the subspace generated by a vector in $C$. As we shall see
next, the property of the partition guarantees that the distinguished element
is preserved under taking minors, thus yielding a proper homomorphism from
${\mathscr{Q}}_{\mathbb{H}}$ to ${\mathscr{D}}$.

######  Proposition 12.

If $\dim(\mathbb{H})\leq 2$, ${\mathscr{Q}}_{\mathbb{H}}\to{\mathscr{D}}$.

###### Proof.

Given $\mathbf{q}\in{\mathscr{Q}}_{\mathbb{H}}$ of some arity $\ell$, an
_essential coordinate_ of $\mathbf{q}$ is an index $i\in[\ell]$ for which
$q_{i}\neq\\{\mathbf{0}_{\mathbb{H}}\\}$. We denote the set of essential
coordinates of $\mathbf{q}$ by $\operatorname{sec(\mathbf{q})}$. Note that the
cardinality of $\sec(\mathbf{q})$ is at most $\dim(\mathbb{H})\leq 2$. For any
$1$-dimensional subspace $v\in L_{\mathbb{H}}$, fix a nonzero vector $g(v)\in
v$. Let also $C\subset\mathbb{H}$ be the set constructed in Lemma 11.

We define $\xi:{\mathscr{Q}}_{\mathbb{H}}\to{\mathscr{D}}$ as follows. Given
$\mathbf{q}\in{\mathscr{Q}}_{\mathbb{H}}$ of arity $\ell$, if $\mathbf{q}$ has
a unique essential coordinate $i$, we let
$\xi(\mathbf{q})=\mathbf{e}_{i;\ell}$. Otherwise, $\mathbf{q}$ has two
essential coordinates $i\neq j$ — in which case, it must be that
$\dim(\mathbb{H})=2$ and $\dim(q_{i})=\dim(q_{j})=1$. If $g(q_{i})\in C$, we
let $\xi(\mathbf{q})=\mathbf{e}_{i;\ell}$; otherwise, we let
$\xi(\mathbf{q})=\mathbf{e}_{j;\ell}$. Since ${\langle
g(q_{i}),g(q_{j})\rangle}=0$, $\xi$ is well defined by virtue of the property
of $C$. We claim that $\xi$ yields a minion homomorphism from
${\mathscr{Q}}_{\mathbb{H}}$ to ${\mathscr{D}}$.

The facts that $\xi(\mathbf{q})\in{\mathscr{D}}$ for each
$\mathbf{q}\in{\mathscr{Q}}_{\mathbb{H}}$ and that $\xi$ preserves the arity
directly follow from the definition. To show that $\xi$ preserves the minors,
take $\pi:[\ell]\to[\ell^{\prime}]$ and
$\mathbf{q}\in{\mathscr{Q}}_{\mathbb{H}}^{(\ell)}$. Observe that

$\displaystyle\sec(\mathbf{q}_{/\pi})=\\{\pi(i):i\in\sec(\mathbf{q})\\}.$

If $\sec(\mathbf{q})=\\{i\\}$, it follows that

$\displaystyle\xi(\mathbf{q}_{/\pi})=\mathbf{e}_{\pi(i);\ell^{\prime}}=(\mathbf{e}_{i;\ell})_{/\pi}=\xi(\mathbf{q})_{/\pi}.$

If $\sec(\mathbf{q})=\\{i,j\\}$ with $i\neq j$, let $k\in\\{i,j\\}$ be such
that $\xi(\mathbf{q})=\mathbf{e}_{k;\ell}$. There are two cases. If
$\pi(i)=\pi(j)$, we have that $\sec(\mathbf{q}_{/\pi})=\\{\pi(k)\\}$, and it
follows that $\xi(\mathbf{q}_{/\pi})=\mathbf{e}_{\pi(k);\ell^{\prime}}$. If
$\pi(i)\neq\pi(j)$, $\mathbf{q}_{/\pi}$ is the vector in
${\mathscr{Q}}_{\mathbb{H}}^{(\ell^{\prime})}$ whose $\pi(i)$-th entry is
$q_{i}$, whose $\pi(j)$-th entry is $q_{j}$, and all of whose other entries
are $\\{\mathbf{0}_{\mathbb{H}}\\}$. Hence, also in this case it holds that
$\xi(\mathbf{q}_{/\pi})=\mathbf{e}_{\pi(k);\ell^{\prime}}$. This means that,
in either case, we have

$\displaystyle\xi(\mathbf{q}_{/\pi})=\mathbf{e}_{\pi(k);\ell^{\prime}}=(\mathbf{e}_{k;\ell})_{/\pi}=\xi(\mathbf{q})_{/\pi}.$

Therefore, the identity $\xi(\mathbf{q}_{/\pi})=\xi(\mathbf{q})_{/\pi}$ is
satisfied in all cases, and it follows that $\xi$ is a minion homomorphism. ∎

As a direct consequence, we obtain the following.

######  Corollary 13.

No relational structure has quantum advantage over $\mathbb{H}$ if
$\dim(\mathbb{H})\leq 2$.

###### Proof.

If $\dim(\mathbb{H})\leq 2$, Lemma 9 and Proposition 12 yield

$\displaystyle{\mathscr{Q}}_{\mathbb{H}}\to{\mathscr{D}}\to\operatorname{Pol}(\mathbf{Y})$

for any relational structure $\mathbf{Y}$, and the conclusion immediately
follows from Theorem 6. ∎

Corollary 13 is an instance of a more general phenomenon in quantum
information, observed in [18] in the context of pseudo-telepathy games (see
also [1]): In order for an $n$-qubit system to exhibit strong non-locality
with any finite number of local measurements, $n$ must be at least $3$. We now
turn to the “only if” part of Theorem 10 (Proposition 15). Our proof builds on
a deep result by Gleason on measures on the subspaces of Hilbert spaces —
which we state next, after introducing the necessary terminology.

The _trace_ $\operatorname{tr}(p)$ of a linear map
$p\in\operatorname{End}_{\mathbb{H}}$ is the trace of a matrix representation
of $p$ in any basis of $\mathbb{H}$. We say that $p$ is _positive
semidefinite_ (and write $p\succeq\mathbx{0}_{\mathbb{H}}$) if $p$ is self-
adjoint and ${\langle p(\mathbf{h}),\mathbf{h}\rangle}\geq 0$ for each
$\mathbf{h}\in\mathbb{H}$. A _measure on the subspaces of $\mathbb{H}$_ is a
function $\mu:L_{\mathbb{H}}\to\mathbb{R}_{\geq 0}$ such that, for each
collection $\\{v_{1},\dots,v_{\ell}\\}$ of mutually orthogonal subspaces of
$\mathbb{H}$, it holds that

$\displaystyle\mu\left(\mathop{\vphantom{\bigoplus}\mathchoice{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\mathbin{\mathchoice{\ooalign{$\displaystyle\boxempty$\cr$\displaystyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\textstyle\boxempty$\cr$\textstyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptstyle\boxempty$\cr$\scriptstyle\mathchoice{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.22362pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.17824pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptscriptstyle\boxempty$\cr$\scriptscriptstyle\mathchoice{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.15973pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.12732pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}}$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\mathbin{\mathchoice{\ooalign{$\displaystyle\boxempty$\cr$\displaystyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\textstyle\boxempty$\cr$\textstyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptstyle\boxempty$\cr$\scriptstyle\mathchoice{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.22362pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.17824pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptscriptstyle\boxempty$\cr$\scriptscriptstyle\mathchoice{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.15973pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.12732pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}}$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\mathbin{\mathchoice{\ooalign{$\displaystyle\boxempty$\cr$\displaystyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\textstyle\boxempty$\cr$\textstyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptstyle\boxempty$\cr$\scriptstyle\mathchoice{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.22362pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.17824pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptscriptstyle\boxempty$\cr$\scriptscriptstyle\mathchoice{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.15973pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.12732pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}}$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\mathbin{\mathchoice{\ooalign{$\displaystyle\boxempty$\cr$\displaystyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\textstyle\boxempty$\cr$\textstyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptstyle\boxempty$\cr$\scriptstyle\mathchoice{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.22362pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.17824pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptscriptstyle\boxempty$\cr$\scriptscriptstyle\mathchoice{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.15973pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.12732pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}}$}}}}}\displaylimits_{i\in[\ell]}v_{i}\right)=\sum_{i\in[\ell]}\mu(v_{i}).$
(33)

######  Theorem 14 ([39]).

Let $\mu$ be a measure on the subspaces of a finite-dimensional (real or
complex) Hilbert space $\mathbb{H}$ of dimension at least three. Then there
exists a positive semidefinite linear map
$m\in\operatorname{End}_{\mathbb{H}}$ such that

$\displaystyle\mu(v)=\operatorname{tr}(m\cdot\operatorname{pr}_{v})$ (34)

for each $v\in L_{\mathbb{H}}$.151515We point out that Gleason’s Theorem holds
in the more general setting of separable, not necessarily finite-dimensional
Hilbert spaces $\mathbb{H}$. In the general formulation, $\mu$ needs to be
defined on all closed subspaces of $\mathbb{H}$, and it needs to satisfy the
condition (33) for each countable collection of mutually orthogonal subspaces
whose linear span is closed.

Proposition 15 is established by showing that a homomorphism from the quantum
minion to the dictator minion would yield a well-defined, Boolean measure
$\mu$ on the subspaces of $\mathbb{H}$. However, if the dimension of
$\mathbb{H}$ is at least $3$, Theorem 14 implies that $\mu$ must have a
continuous dependence on its inputs and, in particular, it must assume
intermediate values between $0$ and $1$, thus yielding a contradiction.

######  Proposition 15.

If $\dim(\mathbb{H})\geq 3$, ${\mathscr{Q}}_{\mathbb{H}}\not\to{\mathscr{D}}$.

###### Proof.

Suppose, for the sake of contradiction, that there exists a homomorphism
$\xi:{\mathscr{Q}}_{\mathbb{H}}\to{\mathscr{D}}$. We associate with any linear
subspace $v\in L_{\mathbb{H}}$ the vector

$\displaystyle\widehat{v}=\begin{bmatrix}v\\\
v^{\perp}\end{bmatrix}\in{\mathscr{Q}}_{\mathbb{H}}^{(2)}.$

Recall that ${\mathscr{D}}^{(2)}=\\{\mathbf{e}_{1;2},\mathbf{e}_{2;2}\\}$, and
consider the function $\mu:L_{\mathbb{H}}\to\mathbb{R}_{\geq 0}$ defined by

$\displaystyle\mu(v)=\left\\{\begin{array}[]{llll}1&\mbox{if}&\xi(\widehat{v})=\mathbf{e}_{1;2}\\\
0&\mbox{if}&\xi(\widehat{v})=\mathbf{e}_{2;2}\end{array}\right.$

for each $v\in L_{\mathbb{H}}$. We claim that $\mu$ is a measure on the
subspaces of $\mathbb{H}$. Take a collection $\\{v_{1},\dots,v_{\ell}\\}$ of
mutually orthogonal subspaces of $\mathbb{H}$, and let
$w=\mathop{\vphantom{\bigoplus}\mathchoice{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\mathbin{\mathchoice{\ooalign{$\displaystyle\boxempty$\cr$\displaystyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\textstyle\boxempty$\cr$\textstyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptstyle\boxempty$\cr$\scriptstyle\mathchoice{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.22362pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.17824pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptscriptstyle\boxempty$\cr$\scriptscriptstyle\mathchoice{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.15973pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.12732pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}}$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\mathbin{\mathchoice{\ooalign{$\displaystyle\boxempty$\cr$\displaystyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\textstyle\boxempty$\cr$\textstyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptstyle\boxempty$\cr$\scriptstyle\mathchoice{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.22362pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.17824pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptscriptstyle\boxempty$\cr$\scriptscriptstyle\mathchoice{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.15973pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.12732pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}}$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\mathbin{\mathchoice{\ooalign{$\displaystyle\boxempty$\cr$\displaystyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\textstyle\boxempty$\cr$\textstyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptstyle\boxempty$\cr$\scriptstyle\mathchoice{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.22362pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.17824pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptscriptstyle\boxempty$\cr$\scriptscriptstyle\mathchoice{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.15973pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.12732pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}}$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\mathbin{\mathchoice{\ooalign{$\displaystyle\boxempty$\cr$\displaystyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\textstyle\boxempty$\cr$\textstyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptstyle\boxempty$\cr$\scriptstyle\mathchoice{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.22362pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.17824pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptscriptstyle\boxempty$\cr$\scriptscriptstyle\mathchoice{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.15973pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.12732pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}}$}}}}}\displaylimits_{i\in[\ell]}v_{i}$.

Suppose first that $\mu(w)=1$, which means that
$\xi(\widehat{w})=\mathbf{e}_{1;2}$. Take the vector

$\displaystyle\mathbf{q}=\begin{bmatrix}v_{1}&v_{2}&\dots&v_{\ell}&w^{\perp}\end{bmatrix}^{\top}\in{\mathscr{Q}}_{\mathbb{H}}^{(\ell+1)},$

and consider the map $\pi:[\ell+1]\to[2]$ such that $\pi(i)=1$ if
$i\in[\ell]$, and $\pi(\ell+1)=2$. Note that $\mathbf{q}_{/\pi}=\widehat{w}$;
using that $\xi$ is a homomorphism, we get

$\displaystyle\mathbf{e}_{1;2}=\xi(\widehat{w})=\xi(\mathbf{q}_{/\pi})=\xi(\mathbf{q})_{/\pi},$
(35)

whence it follows that $\xi(\mathbf{q})=\mathbf{e}_{j;\ell+1}$ for some
$j\in[\ell]$. Consider now, for $k\in[\ell]$, the map $\pi_{k}:[\ell+1]\to[2]$
such that $\pi_{k}(k)=1$ and $\pi_{k}(i)=2$ for each
$i\in[\ell+1]\setminus\\{k\\}$. Observe that
$\mathbf{q}_{/\pi_{k}}=\widehat{v_{k}}$. Therefore,

$\displaystyle\xi(\widehat{v_{k}})=\xi(\mathbf{q}_{/\pi_{k}})=\xi(\mathbf{q})_{/\pi_{k}}=(\mathbf{e}_{j;\ell+1})_{/\pi_{k}}=\mathbf{e}_{\pi_{k}(j);2}.$
(36)

It follows from the above that $\mu(v_{k})=1$ precisely when $\pi_{k}(j)=1$.
In other words, $\mu(v_{j})=1$ and $\mu(v_{k})=0$ for each $k\neq j$.
Therefore,

$\displaystyle\sum_{i\in[\ell]}\mu(v_{i})=1=\mu(w)=\mu\left(\mathop{\vphantom{\bigoplus}\mathchoice{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\mathbin{\mathchoice{\ooalign{$\displaystyle\boxempty$\cr$\displaystyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\textstyle\boxempty$\cr$\textstyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptstyle\boxempty$\cr$\scriptstyle\mathchoice{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.22362pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.17824pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptscriptstyle\boxempty$\cr$\scriptscriptstyle\mathchoice{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.15973pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.12732pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}}$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\mathbin{\mathchoice{\ooalign{$\displaystyle\boxempty$\cr$\displaystyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\textstyle\boxempty$\cr$\textstyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptstyle\boxempty$\cr$\scriptstyle\mathchoice{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.22362pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.17824pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptscriptstyle\boxempty$\cr$\scriptscriptstyle\mathchoice{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.15973pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.12732pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}}$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\mathbin{\mathchoice{\ooalign{$\displaystyle\boxempty$\cr$\displaystyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\textstyle\boxempty$\cr$\textstyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptstyle\boxempty$\cr$\scriptstyle\mathchoice{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.22362pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.17824pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptscriptstyle\boxempty$\cr$\scriptscriptstyle\mathchoice{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.15973pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.12732pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}}$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\mathbin{\mathchoice{\ooalign{$\displaystyle\boxempty$\cr$\displaystyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\textstyle\boxempty$\cr$\textstyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptstyle\boxempty$\cr$\scriptstyle\mathchoice{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.22362pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.17824pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptscriptstyle\boxempty$\cr$\scriptscriptstyle\mathchoice{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.15973pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.12732pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}}$}}}}}\displaylimits_{i\in[\ell]}v_{i}\right),$

as needed.

Suppose now that $\mu(w)=0$. In this case, the equation (35) turns into

$\displaystyle\mathbf{e}_{2;2}=\xi(\widehat{w})=\xi(\mathbf{q}_{/\pi})=\xi(\mathbf{q})_{/\pi},$

which means that $\xi(\mathbf{q})=\mathbf{e}_{\ell+1;\ell+1}$. Then, for each
$k\in[\ell]$, the equation (36) becomes

$\displaystyle\xi(\widehat{v_{k}})=\xi(\mathbf{q}_{/\pi_{k}})=\xi(\mathbf{q})_{/\pi_{k}}=(\mathbf{e}_{\ell+1;\ell+1})_{/\pi_{k}}=\mathbf{e}_{\pi_{k}(\ell+1);2}=\mathbf{e}_{2;2},$

thus showing that $\mu(v_{k})=0$ for each $k\in[\ell]$. It follows that

$\displaystyle\sum_{i\in[\ell]}\mu(v_{i})=0=\mu(w)=\mu\left(\mathop{\vphantom{\bigoplus}\mathchoice{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\mathbin{\mathchoice{\ooalign{$\displaystyle\boxempty$\cr$\displaystyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\textstyle\boxempty$\cr$\textstyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptstyle\boxempty$\cr$\scriptstyle\mathchoice{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.22362pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.17824pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptscriptstyle\boxempty$\cr$\scriptscriptstyle\mathchoice{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.15973pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.12732pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}}$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\mathbin{\mathchoice{\ooalign{$\displaystyle\boxempty$\cr$\displaystyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\textstyle\boxempty$\cr$\textstyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptstyle\boxempty$\cr$\scriptstyle\mathchoice{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.22362pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.17824pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptscriptstyle\boxempty$\cr$\scriptscriptstyle\mathchoice{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.15973pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.12732pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}}$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\mathbin{\mathchoice{\ooalign{$\displaystyle\boxempty$\cr$\displaystyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\textstyle\boxempty$\cr$\textstyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptstyle\boxempty$\cr$\scriptstyle\mathchoice{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.22362pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.17824pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptscriptstyle\boxempty$\cr$\scriptscriptstyle\mathchoice{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.15973pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.12732pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}}$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\mathbin{\mathchoice{\ooalign{$\displaystyle\boxempty$\cr$\displaystyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\textstyle\boxempty$\cr$\textstyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptstyle\boxempty$\cr$\scriptstyle\mathchoice{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.22362pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.17824pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptscriptstyle\boxempty$\cr$\scriptscriptstyle\mathchoice{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.15973pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.12732pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}}$}}}}}\displaylimits_{i\in[\ell]}v_{i}\right).$

Hence, $\mu$ is a measure on the subspaces of $\mathbb{H}$, as claimed. We can
then invoke Theorem 14 and find a linear map
$m\in\operatorname{End}_{\mathbb{H}}$ such that
$m\succeq\mathbx{0}_{\mathbb{H}}$ and
$\mu(v)=\operatorname{tr}(m\cdot\operatorname{pr}_{v})$ for each $v\in
L_{\mathbb{H}}$. In particular,

$\displaystyle\mu(\mathbb{H})=\operatorname{tr}(m\cdot\operatorname{pr}_{\mathbb{H}})=\operatorname{tr}(m\cdot\operatorname{id}_{\mathbb{H}})=\operatorname{tr}(m).$
(37)

We now claim that $\mu(\mathbb{H})=1$. Indeed, if $\mu(\mathbb{H})=0$, it
would follow from (37) that $\operatorname{tr}(m)=0$; since $m$ is positive
semidefinite, this would mean that $m=\mathbx{0}_{\mathbb{H}}$; then, (34)
would force $\mu(v)=0$ for each $v\in L_{\mathbb{H}}$. On the other hand,
letting $\tau:[2]\to[2]$ be the map $1\mapsto 2$, $2\mapsto 1$, we would find

$\displaystyle\xi(\widehat{\\{\mathbf{0}_{\mathbb{H}}\\}})=\xi(\widehat{\mathbb{H}}_{/\tau})=\xi(\widehat{\mathbb{H}})_{/\tau}=({\mathbf{e}_{2;2}})_{/\tau}=\mathbf{e}_{1;2}$

and, thus, $\mu(\\{\mathbf{0}_{\mathbb{H}}\\})=1$, a contradiction.

Next, let $d=\dim(\mathbb{H})$, let
$\\{\mathbf{v}_{1},\dots,\mathbf{v}_{d}\\}$ be an orthonormal basis of
eigenvectors for $m$, and let $\lambda_{1},\dots,\lambda_{d}$ be the
corresponding (real, nonnegative) eigenvalues of $m$. It follows from (37)
that

$\displaystyle
1=\mu(\mathbb{H})=\operatorname{tr}(m)=\sum_{i\in[d]}\lambda_{i}.$

Therefore, letting $v_{i}$ be the linear span of $\mathbf{v}_{i}$, we have

$\displaystyle\mu(v_{i})=\operatorname{tr}(m\cdot\operatorname{pr}_{v_{i}})=\lambda_{i}$

for each $i\in[d]$. On the other hand, the range of $\mu$ is included in
$\\{0,1\\}$ by construction. We deduce that the spectrum of $m$ consists of
the values $1$ (with multiplicity $1$) and $0$ (with multiplicity $d-1$). In
other words, $m=\operatorname{pr}_{v_{j}}$ for some $j\in[d]$. Choose an index
${k}\neq j$, and let $w$ be the linear span of the vector
$\mathbf{v}_{j}+\mathbf{v}_{k}$. Using that $m$ is self-adjoint, we obtain

$\displaystyle\mu(w)$
$\displaystyle=\operatorname{tr}(m\cdot\operatorname{pr}_{w})=\sum_{i\in[d]}{\langle
m\cdot\operatorname{pr}_{w}(\mathbf{v}_{i}),\mathbf{v}_{i}\rangle}$
$\displaystyle=\sum_{i\in[d]}{\langle\operatorname{pr}_{w}(\mathbf{v}_{i}),m(\mathbf{v}_{i})\rangle}=\sum_{i\in[d]}{\langle\operatorname{pr}_{w}(\mathbf{v}_{i}),\operatorname{pr}_{v_{j}}(\mathbf{v}_{i})\rangle}$
$\displaystyle={\langle\operatorname{pr}_{w}(\mathbf{v}_{j}),\mathbf{v}_{j}\rangle}.$

Since an orthonormal basis for $w$ is given by the single vector
$\mathbf{w}=\frac{1}{\sqrt{2}}(\mathbf{v}_{j}+\mathbf{v}_{k})$, we have that

$\displaystyle\operatorname{pr}_{w}(\mathbf{v})={\langle\mathbf{v},\mathbf{w}\rangle}\mathbf{w}$

for each $\mathbf{v}\in\mathbb{H}$. Observe that
${\langle\mathbf{w},\mathbf{v}_{j}\rangle}=\frac{1}{\sqrt{2}}$. As a
consequence,

$\displaystyle\mu(w)=\left\langle{\langle\mathbf{v}_{j},\mathbf{w}\rangle}\mathbf{w},\mathbf{v}_{j}\right\rangle=\frac{1}{2},$

a contradiction. ∎

Proposition 15 yields a separation of the quantum minion from the dictator
minion. Together with Theorem 6, it implies that $\mathbf{Y}$ has quantum
advantage over any Hilbert space of dimension at least $3$ whenever
$\operatorname{Pol}(\mathbf{Y})\to{\mathscr{D}}$. In turn, the algebraic
theory of CSPs allows formulating the latter condition in terms of the
complexity of $\operatorname{CSP}(\mathbf{Y})$.

Since homomorphisms between polymorphism minions provide polynomial-time
reductions between CSPs (Theorem 4) and since the dictator minion is
homomorphic to any minion (Lemma 9), if
$\operatorname{Pol}(\mathbf{Y})\to{\mathscr{D}}$ it must hold that
$\operatorname{CSP}(\mathbf{Y})$ is ${\operatorname{NP}}$-complete. It follows
from the CSP Dichotomy Theorem proved in [60, 21] (in its reformulation in
terms of polymorphism minions from [11]) that the converse implication is also
true.

######  Theorem 16 ([11, 60, 21]).

Let $\mathbf{Y}$ be a relational structure. Then
$\operatorname{CSP}(\mathbf{Y})$ is ${\operatorname{NP}}$-complete if
$\operatorname{Pol}(\mathbf{Y})\to{\mathscr{D}}$, and it is tractable in
polynomial time otherwise.

As a consequence, we obtain the following sufficient condition for the
occurrence of quantum advantage.

######  Corollary 17.

Let $\mathbf{Y}$ be a relational structure such that
$\operatorname{CSP}(\mathbf{Y})$ is not tractable in polynomial time. If
$\dim(\mathbb{H})\geq 3$, $\mathbf{Y}$ has quantum advantage over
$\mathbb{H}$.

###### Proof.

If $\operatorname{CSP}(\mathbf{Y})$ is not in $\operatorname{P}$, it follows
from Theorem 16 that $\operatorname{Pol}(\mathbf{Y})\to{\mathscr{D}}$. If
$\dim(\mathbb{H})\geq 3$, we must then have
${\mathscr{Q}}_{\mathbb{H}}\not\to\operatorname{Pol}(\mathbf{Y})$, as
otherwise composing the homomorphisms would yield
${\mathscr{Q}}_{\mathbb{H}}\to{\mathscr{D}}$, contradicting Proposition 15.
Hence, the conclusion follows from Theorem 6. ∎

Equivalently, Corollary 17 may be phrased as follows: If
$\operatorname{CSP}(\mathbf{Y})$ is not in $\operatorname{P}$ and
$\dim(\mathbb{H})\geq 3$, there must exist some $\mathbf{X}$ such that
$\mathbf{X}\to_{\mathbb{H}}\mathbf{Y}$ but $\mathbf{X}\not\to\mathbf{Y}$.

##  5 ${\mathscr{Q}}_{\mathbb{H}}$ and the bounded-width minion

As we have seen, no structure has quantum advantage over Hilbert spaces of
dimension $1$ or $2$. If the dimension is at least $3$, Corollary 17 provides
a sufficient condition for the occurrence of quantum advantage, in terms of
the complexity of $\operatorname{CSP}(\mathbf{Y})$. In this section, we
establish a necessary condition, also formulated in terms of a complexity
notion of $\operatorname{CSP}(\mathbf{Y})$ — namely, its _width_.

The concept of width is central in the theory of constraint satisfaction. On a
high level, the width of a CSP expresses the power of local-consistency
techniques for its solvability. More formally, given two similar relational
structures $\mathbf{X}$ and $\mathbf{Y}$ and some fixed $k\in\mathbb{N}$, the
$k$-consistency algorithm provides a heuristic to check if
$\mathbf{X}\to\mathbf{Y}$, by testing for the existence of a non-empty family
of partial homomorphisms from substructures of $\mathbf{X}$ of size at most
$k$ to $\mathbf{Y}$, that is closed under restriction and under extension up
to size $k$. If such a family exists, $\mathbf{X}$ and $\mathbf{Y}$ are said
to be $k$-consistent.161616We refer to [9] for the formal definition of the
$k$-consistency algorithm. As long as $k$ is a constant, there exists a
polynomial-time procedure (in the size of $\mathbf{X}$) to check whether
$\mathbf{X}$ and $\mathbf{Y}$ are $k$-consistent. If
$\mathbf{X}\to\mathbf{Y}$, a family of partial homomorphisms as described
above always exists. We say that $\operatorname{CSP}(\mathbf{Y})$ has width
$k$ if the $k$-consistency algorithm always detects unsatisfiable instances;
i.e., if $\mathbf{X}$ and $\mathbf{Y}$ are $k$-consistent precisely when
$\mathbf{X}\to\mathbf{Y}$. If that is the case, this method yields a
polynomial-time algorithm for the solution of
$\operatorname{CSP}(\mathbf{Y})$. CSPs that are solvable in some constant
width $k\in\mathbb{N}$ are known as _bounded-width_ CSPs, and constitute an
important fragment of all tractable CSPs.

The goal of this section is to prove that the width of a CSP parameterised by
a structure having quantum advantage over some finite-dimensional Hilbert
space must be unbounded (Corollary 25). Our proof is in some sense specular to
the argument in the previous section. Indeed, this time we need to show that
the quantum minion ${\mathscr{Q}}_{\mathbb{H}}$ is located “left enough” in
the minion homomorphism preorder, in that it always admits a homomorphism to
one specific minion — recently introduced in [28] and, independently, in [15]
— that is known to capture bounded width. Then, the result will follow from
Theorem 6. We shall conclude the section by outlining an alternative argument
to obtain the same result, that makes use of a different minion introduced in
[27].

We start by defining the minion for bounded width.

######  Definition 18 ([28, 15]).

${\mathscr{S}}$ is the linear minion over the abelian monoid $(\mathbb{R},+)$
whose elements are all real matrices $M$ of finite but arbitrary size, such
that $MM^{\top}$ is a diagonal matrix of trace $1$.

The fact that the linear minion ${\mathscr{S}}$ captures bounded width follows
from its connection to a CSP algorithm known as the _standard semidefinite
programming_ relaxation (SDP). Essentially, SDP relaxes a given CSP by
considering a semidefinite program whose variables are real vectors having
constrained inner products. We now present the formal description of
$\operatorname{SDP}$, following [58]. Let $\mathbf{X}$ and $\mathbf{Y}$ be two
$\sigma$-structures. We consider a real vector $\mathbf{u}_{x,y}$ for each
$x\in X$, $y\in Y$, and a real number $v_{R,\mathbf{x},\mathbf{y}}$ for each
$R\in\sigma$, $\mathbf{x}\in R^{\mathbf{X}}$, and $\mathbf{y}\in
R^{\mathbf{Y}}$. We also fix a real vector $\mathbf{u}_{0}$ of norm $1$.
Consider the system

$\displaystyle\begin{array}[]{lllll}\displaystyle\sum_{\mathbf{y}\in
R^{\mathbf{Y}}}v_{R,\mathbf{x},\mathbf{y}}=1&(R\in\sigma,\mathbf{x}\in
R^{\mathbf{X}})\\\\[5.0pt] \displaystyle v_{R,\mathbf{x},\mathbf{y}}\geq
0&(R\in\sigma,\mathbf{x}\in R^{\mathbf{X}},\mathbf{y}\in
R^{\mathbf{Y}})\\\\[5.0pt]
\displaystyle{\langle\mathbf{u}_{x_{i},y},\mathbf{u}_{0}\rangle}=\sum_{\begin{subarray}{c}\mathbf{y}\in
R^{\mathbf{Y}}\\\
y_{i}=y\end{subarray}}v_{R,\mathbf{x},\mathbf{y}}&\left(\begin{array}[]{llll}R\in\sigma,\mathbf{x}\in
R^{\mathbf{X}},\\\ i\in[\operatorname{ar}(R)],y\in
Y\end{array}\right)\\\\[5.0pt]
\displaystyle{\langle\mathbf{u}_{x_{i},y},\mathbf{u}_{x_{j},y^{\prime}}\rangle}=\sum_{\begin{subarray}{c}\mathbf{y}\in
R^{\mathbf{Y}}\\\
y_{i}=y,\,y_{j}=y^{\prime}\end{subarray}}v_{R,\mathbf{x},\mathbf{y}}&\left(\begin{array}[]{llll}R\in\sigma,\mathbf{x}\in
R^{\mathbf{X}},\\\ i,j\in[\operatorname{ar}(R)],y,y^{\prime}\in
Y\end{array}\right).\end{array}$

We say that SDP _solves_ $\operatorname{CSP}(\mathbf{Y})$ if
$\mathbf{X}\to\mathbf{Y}$ whenever the system above admits a feasible solution
such that all vectors $\mathbf{u}_{x,y}$ belong to a real vector space of some
finite, large-enough dimension.

######  Theorem 19 ([28, 15]).

Given a relational structure $\mathbf{Y}$, $\operatorname{SDP}$ solves
$\operatorname{CSP}(\mathbf{Y})$ if and only if
${\mathscr{S}}\to\operatorname{Pol}(\mathbf{Y})$.

In fact, the theorem above corresponds to the fact that $\operatorname{SDP}$
has precisely the same power as $\operatorname{Test}_{{\mathscr{S}}}$ (i.e.,
the minion test associated with the minion ${\mathscr{S}}$; cf. [15, §
6.3.2]). The following result characterises the class of CSPs solved by SDP in
terms of their width.

######  Theorem 20 ([10]).

Given a relational structure $\mathbf{Y}$, $\operatorname{SDP}$ solves
$\operatorname{CSP}(\mathbf{Y})$ if and only if
$\operatorname{CSP}(\mathbf{Y})$ has bounded width.

As a consequence of the two results stated above, Corollary 25 would follow if
we show that the quantum minion admits a homomorphism to ${\mathscr{S}}$. To
that end, it shall be useful to introduce a complex version of
${\mathscr{S}}$.

######  Definition 21.

${\mathscr{S}}_{\mathbb{C}}$ is the linear minion over the abelian monoid
$(\mathbb{C},+)$ whose elements are all complex matrices $M$ of finite but
arbitrary size, such that $MM^{*}$ is a diagonal matrix of trace $1$.

It turns out that ${\mathscr{S}}$ and ${\mathscr{S}}_{\mathbb{C}}$ are in fact
the same minion, up to homomorphic equivalence.

######  Proposition 22.

${\mathscr{S}}$ and ${\mathscr{S}}_{\mathbb{C}}$ are homomorphically
equivalent.

###### Proof.

The inclusion map yields a homomorphism
${\mathscr{S}}\to{\mathscr{S}}_{\mathbb{C}}$. To build a homomorphism in the
opposite direction, take a matrix $M\in{\mathscr{S}}_{\mathbb{C}}^{(\ell)}$
for some $\ell\in\mathbb{N}$, and let $M_{R}$ and $M_{I}$ denote the real and
imaginary parts of $M$, respectively; i.e., $M_{R}$ and $M_{I}$ are real
matrices of the same size as $M$, such that $M=M_{R}+\mathrm{i}M_{I}$. We
claim that the map $\vartheta:M\mapsto\begin{bmatrix}M_{R}&M_{I}\end{bmatrix}$
yields a minion homomorphism from ${\mathscr{S}}_{\mathbb{C}}$ to
${\mathscr{S}}$. Observe that

$\displaystyle\vartheta(M)\vartheta(M)^{\top}=M_{R}M_{R}^{\top}+M_{I}M_{I}^{\top}.$

Furthermore,

$\displaystyle MM^{*}$
$\displaystyle=(M_{R}+\mathrm{i}M_{I})(M_{R}+\mathrm{i}M_{I})^{*}=(M_{R}+\mathrm{i}M_{I})(M_{R}^{\top}-\mathrm{i}M_{I}^{\top})$
$\displaystyle=(M_{R}M_{R}^{\top}+M_{I}M_{I}^{\top})+\mathrm{i}(M_{I}M_{R}^{\top}-M_{R}{M_{I}}^{\top}).$

Since $MM^{*}$ is diagonal and has trace $1$, it follows that also its real
part $M_{R}M_{R}^{\top}+M_{I}M_{I}^{\top}$ is diagonal and has trace $1$.
Hence, we conclude that $\vartheta(M)\in{\mathscr{S}}^{(\ell)}$. The fact that
$\vartheta$ preserves the arity is clear. To show that it preserves the
minors, we simply observe that, for $\pi:[\ell]\to[\ell^{\prime}]$,

$\displaystyle\vartheta(M_{/\pi})$
$\displaystyle=\begin{bmatrix}(M_{/\pi})_{R}&(M_{/\pi})_{I}\end{bmatrix}=\begin{bmatrix}(M_{R})_{/\pi}&(M_{I})_{/\pi}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}M_{R}&M_{I}\end{bmatrix}_{/\pi}=\vartheta(M)_{/\pi},$

as required. ∎

We shall need the following basic properties of orthogonal projectors. Recall
that, for $p\in\operatorname{End}_{\mathbb{H}}$, $\operatorname{rg}_{p}$
denotes the range of $p$.

######  Lemma 23 ([42]).

Take $p,p^{\prime}\in\operatorname{Proj}_{\mathbb{H}}$.

  * •

$pp^{\prime}\in\operatorname{Proj}_{\mathbb{H}}$ if and only if
$[p,p^{\prime}]=\mathbx{0}_{\mathbb{H}}$.

  * •

$p+p^{\prime}\in\operatorname{Proj}_{\mathbb{H}}$ if and only if
$pp^{\prime}=p^{\prime}p=\mathbx{0}_{\mathbb{H}}$ if and only if
$\operatorname{rg}_{p}\perp\operatorname{rg}_{p^{\prime}}$. In this case,
$\operatorname{rg}_{p+p^{\prime}}=\operatorname{rg}_{p}\mathbin{\mathchoice{\ooalign{$\displaystyle\boxempty$\cr$\displaystyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\textstyle\boxempty$\cr$\textstyle\mathchoice{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.41667pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.31944pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.25462pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptstyle\boxempty$\cr$\scriptstyle\mathchoice{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.22362pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.17824pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptscriptstyle\boxempty$\cr$\scriptscriptstyle\mathchoice{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.20833pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.15973pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.12732pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}}\operatorname{rg}_{p^{\prime}}$.

We now show that the quantum minion (over any $\mathbb{H}$) homomorphically
maps to ${\mathscr{S}}$. Essentially, the proof works by fixing an arbitrary
vector in $\mathbb{H}$ and projecting it onto the spaces constituting the
entries of the elements of ${\mathscr{Q}}_{\mathbb{H}}$. This yields a
homomorphism ${\mathscr{Q}}_{\mathbb{H}}\to{\mathscr{S}}_{\mathbb{C}}$ which,
by Proposition 22, is enough to establish the result.

######  Theorem 24.

${\mathscr{Q}}_{\mathbb{H}}\to{\mathscr{S}}$.

###### Proof.

Fix an orthonormal basis $B$ of $\mathbb{H}$, and let $d=\dim(\mathbb{H})$.
Given any $\mathbf{v}\in\mathbb{H}$, we shall let $r(\mathbf{v})$ be the
column vector of length $d$ containing the coordinates of $\mathbf{v}$ in the
basis $B$. Fix also an arbitrary vector $\mathbf{w}\in\mathbb{H}$ of norm $1$.
For any $\mathbf{q}\in{\mathscr{Q}}_{\mathbb{H}}$ of some arity $\ell$,
consider the complex $\ell\times d$ matrix $M$ defined by

$\displaystyle
M^{*}\mathbf{e}_{i;\ell}=r(\operatorname{pr}_{q_{i}}(\mathbf{w}))$

for each $i\in[\ell]$. We claim that the assignment $\xi:\mathbf{q}\mapsto M$
yields a homomorphism from ${\mathscr{Q}}_{\mathbb{H}}$ to
${\mathscr{S}}_{\mathbb{C}}$.

First of all, we show that $M\in{\mathscr{S}}_{\mathbb{C}}$. For
$i,j\in[\ell]$, the $(i,j)$-th entry of $MM^{*}$ is

$\displaystyle\mathbf{e}_{i;\ell}^{*}MM^{*}\mathbf{e}_{j;\ell}=(r(\operatorname{pr}_{q_{i}}(\mathbf{w})))^{*}r(\operatorname{pr}_{q_{j}}(\mathbf{w}))={\langle\operatorname{pr}_{q_{j}}(\mathbf{w}),\operatorname{pr}_{q_{i}}(\mathbf{w})\rangle}.$

Since $q_{i}\perp q_{j}$ whenever $i\neq j$, we deduce that $MM^{*}$ is a
diagonal matrix. Therefore, we can write its trace as

$\displaystyle\operatorname{tr}(MM^{*})$
$\displaystyle=\sum_{i,j\in[\ell]}\mathbf{e}_{i;\ell}^{*}MM^{*}\mathbf{e}_{j;\ell}=\sum_{i,j\in[\ell]}{\langle\operatorname{pr}_{q_{j}}(\mathbf{w}),\operatorname{pr}_{q_{i}}(\mathbf{w})\rangle}$
$\displaystyle=\bigg{\|}\sum_{i\in[\ell]}\operatorname{pr}_{q_{i}}(\mathbf{w})\bigg{\|}^{2}.$

Furthermore, by Lemma 23,

$\displaystyle\sum_{i\in[\ell]}\operatorname{pr}_{q_{i}}(\mathbf{w})=\operatorname{pr}_{\mathop{\vphantom{\bigoplus}\mathchoice{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\mathbin{\mathchoice{\ooalign{$\displaystyle\boxempty$\cr$\displaystyle\mathchoice{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.22362pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.17824pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\textstyle\boxempty$\cr$\textstyle\mathchoice{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.22362pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.17824pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptstyle\boxempty$\cr$\scriptstyle\mathchoice{\raisebox{0.20416pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.20416pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.15652pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.12477pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptscriptstyle\boxempty$\cr$\scriptscriptstyle\mathchoice{\raisebox{0.14583pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.14583pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.1118pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.08913pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}}$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\mathbin{\mathchoice{\ooalign{$\displaystyle\boxempty$\cr$\displaystyle\mathchoice{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.22362pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.17824pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\textstyle\boxempty$\cr$\textstyle\mathchoice{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.22362pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.17824pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptstyle\boxempty$\cr$\scriptstyle\mathchoice{\raisebox{0.20416pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.20416pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.15652pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.12477pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptscriptstyle\boxempty$\cr$\scriptscriptstyle\mathchoice{\raisebox{0.14583pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.14583pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.1118pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.08913pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}}$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\mathbin{\mathchoice{\ooalign{$\displaystyle\boxempty$\cr$\displaystyle\mathchoice{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.22362pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.17824pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\textstyle\boxempty$\cr$\textstyle\mathchoice{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.22362pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.17824pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptstyle\boxempty$\cr$\scriptstyle\mathchoice{\raisebox{0.20416pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.20416pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.15652pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.12477pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptscriptstyle\boxempty$\cr$\scriptscriptstyle\mathchoice{\raisebox{0.14583pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.14583pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.1118pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.08913pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}}$}}}}{\vbox{\hbox{\leavevmode\resizebox{0.0pt}{}{$\mathbin{\mathchoice{\ooalign{$\displaystyle\boxempty$\cr$\displaystyle\mathchoice{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.22362pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.17824pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\textstyle\boxempty$\cr$\textstyle\mathchoice{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.29167pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.22362pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.17824pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptstyle\boxempty$\cr$\scriptstyle\mathchoice{\raisebox{0.20416pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.20416pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.15652pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.12477pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}{\ooalign{$\scriptscriptstyle\boxempty$\cr$\scriptscriptstyle\mathchoice{\raisebox{0.14583pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\displaystyle+$}}}}}{\raisebox{0.14583pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\textstyle+$}}}}}{\raisebox{0.1118pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptstyle+$}}}}}{\raisebox{0.08913pt}{\hbox{\set@color\scalebox{0.875}{\hbox{\set@color$\scriptscriptstyle+$}}}}}$\cr}}}$}}}}}\displaylimits_{i\in[\ell]}q_{i}}(\mathbf{w})=\operatorname{pr}_{\mathbb{H}}(\mathbf{w})=\mathbf{w}.$

It follows that $\operatorname{tr}(MM^{*})=\|\mathbf{w}\|^{2}=1$, as required
to conclude that $M\in{\mathscr{S}}_{\mathbb{C}}$.

We are left to show that $\xi$ is a minion homomorphism. The fact that it
preserves the arity directly follows from its definition. To prove that it
preserves the minors, take a map $\pi:[\ell]\to[\ell^{\prime}]$. We need to
show that $\xi(\mathbf{q}_{/\pi})=\xi(\mathbf{q})_{/\pi}$. Pick an index
$j\in[\ell^{\prime}]$, and observe that

$\displaystyle(\xi(\mathbf{q}_{/\pi}))^{*}\mathbf{e}_{j;\ell^{\prime}}$