# New Approaches to Complexity via Quantum Graphs

Eric Culf  Faculty of Mathematics and Institute for Quantum Computing,
University of<EMAIL_ADDRESS>Arthur Mehta  Department of
Mathematics and Statistics, University of<EMAIL_ADDRESS>
###### Abstract

Problems based on the structure of graphs — for example finding cliques,
independent sets, or colourings — are of fundamental importance in classical
complexity. It is well motivated to consider similar problems about quantum
graphs, which are an operator system generalisation of graphs. Defining well-
formulated decision problems for quantum graphs faces several technical
challenges, and consequently the connections between quantum graphs and
complexity have been underexplored.

In this work, we introduce and study the clique problem for quantum graphs.
Our approach utilizes a well-known connection between quantum graphs and
quantum channels. The inputs for our problems are presented as quantum
channels induced by circuits, which implicitly determine a corresponding
quantum graph. We also use this approach to reimagine the clique and
independent set problems for classical graphs, by taking the inputs to be
circuits of deterministic or noisy channels which implicitly determine
confusability graphs. We show that, by varying the collection of channels in
the language, these give rise to complete problems for the classes NP, MA,
QMA, and $\textsf{QMA}(2)$. In this way, we exhibit a classical complexity
problem whose natural quantisation is $\textsf{QMA}(2)$, rather than QMA,
which is commonly assumed.

To prove the results in the quantum case, we make use of methods inspired by
self-testing. To illustrate the utility of our techniques, we include a new
proof of the reduction of $\textsf{QMA}(k)$ to $\textsf{QMA}(2)$ via cliques
for quantum graphs. We also study the complexity of a version of the
independent set problem for quantum graphs, and provide preliminary evidence
that it may be in general weaker in complexity, contrasting to the classical
case where the clique and independent set problems are equivalent.

###### Contents

  1. 1 Introduction
    1. 1.1 Background
      1. 1.1.1 Quantum graphs
      2. 1.1.2 The clique/independent set problems for quantum graphs
    2. 1.2 Main results
    3. 1.3 Proof techniques
    4. 1.4 Relation to other works
    5. 1.5 Open problems
    6. 1.6 Acknowledgements
    7. 1.7 Outline
  2. 2 Preliminaries
    1. 2.1 Notation
    2. 2.2 Complexity theory
    3. 2.3 Quantum and classical circuits
    4. 2.4 Distances between states
    5. 2.5 The swap test
  3. 3 Classical Collision and Clique Problems
    1. 3.1 The deterministic case
    2. 3.2 The probabilistic case
  4. 4 The Clique Problem for Quantum Channels
    1. 4.1 The quantum clique problem is QMA(2)-complete
    2. 4.2 Reducing QMA(k) to QMA(2) using quantum cliques
    3. 4.3 What about quantum independent sets?
  5. 5 Specifying to QMA
  6. A Reductions from k-cliques to 2-cliques
  7. B Alternate proof of QMA(2)-hardness

##  1 Introduction

Shannon’s foundational work on zero-error capacity established a deep
connection between noisy channels and graph theory [Sha56]. Shannon showed
that to each classical noisy channel $N$, one can associate a corresponding
graph $G_{N}$, called a _confusability graph_ , which encodes many important
properties of the channel. Notably, $G_{N}$ will have an independent set
(_cf._ a clique) of size $k$ if and only if there is a collection of distinct
inputs $x_{1},\dots x_{k}$ for $N$ which have a zero (_cf._ non-zero)
probability of being confused as outputs.

A _quantum graph_ is a generalization of a graph which allows to extend the
graph notion of confusability to quantum channels [DSW13]. In brief, given a
quantum channel $\Phi$ there exists a corresponding _operator system_
$\mathcal{S}_{\Phi}$.

A collection of states $\rho_{1},\dots\rho_{k}$ forms an _independent set
(_cf._ clique)_ for $\mathcal{S}_{\Phi}$ if the average overlap
$\operatorname{Tr}(\mathcal{N}(\rho_{i})\mathcal{N}(\rho_{j}))$ is
sufficiently small (_cf._ large). Quantum graphs have been studied from
various points of view including channel capacity, non-local games, and non-
commutative relations [Sta16, TT20, KKS20, CW22, Mat22, CvS22, Gan23, BEVW22].

Due to the ubiquity of graphs in classical complexity, one might ask if it is
also natural to study quantum graphs in the context of quantum complexity
theory. In the classical setting, deciding if a graph has a clique (or an
independent set) is NP-complete [Sip12]. The complexity class QMA is
recognized as a quantum analogue of NP, as the classical proof strings of NP
are replaced by general quantum states for this class. Kitaev emphasized this
view by demonstrating QMA-completeness of the local Hamiltonian problem, a
quantum analogue of the NP-complete problem $k$-SAT [KSV02]. Similarly, other
NP-complete problems have been shown to quantise to QMA-complete problems,
_e.g._ [Bra06, BG22]. It is therefore reasonable to expect the clique and
independent set problems for quantum graphs to be QMA-complete.

Surprisingly, the complexity of these problems has received relatively little
study. An initial treatment was given by Beigi and Shor [BS08]; however, as we
discuss in Section 1.4, their work would require the additional assumption
that the input states are product states in order to apply to our setting. An
alternative quantum analogue of NP is class QMA(2), which contains QMA and
differs in that it is assumed that the that proofs are given as product states
[KMY03, ABD+09]. There are relatively few known QMA(2)-complete problems
compared to the cornucopia of QMA-complete problems; moreover, known
QMA(2)-complete problems like the sparse separable Hamiltonian problem [CS12],
and the product isometry output problem [GHMW15], don’t appear to be
straightforward generalizations of NP-complete problems.

In this work, we study the decision problems of identifying cliques and
independent sets in quantum graphs. We present our problem instances as
circuit descriptions of quantum channels $\Phi$, which in turn determines a
quantum graphs (operator systems) $\mathcal{S}_{\Phi}$. We also consider
versions of the clique/independent set problems for graphs, where instead of
an explicit description of a graph, the verifier is given a circuit
description of a noisy channel which implicitly determines a graph, given as
its confusability graph.

##### Summary of Results

For deterministic and classical noisy channels, we show that our versions of
both the clique and independent set problems are complete for NP and MA,
respectively. Then, we examine these problems for quantum channels, where we
show they are in $\textsf{QMA}(2)$ and prove that the clique problem is
$\textsf{QMA}(2)$-complete. Additionally, we show that, by quantifying over a
restricted class of channels, we recover a complete problem for QMA. Our work
outlines a hierarchy of decision problems which captures completeness for all
four of these important complexity classes and provides evidence for viewing
QMA(2) as a natural quantum analogue of NP.

###  1.1 Background

In this section, we provide a brief overview of quantum graphs. For
completeness we highlight that there are several overlapping notions of
quantum graphs, which have been discovered in somewhat distinct settings, for
example in early works due to Erdős, Katavolos, Shulman [EKS98], and Weaver
[Wea10, Wea21]. More comprehensive introductions to the topics of operator
systems and quantum graphs can be found in [Pau02], [Pau16], and [Daw22].

We focus on the motivation of quantum graphs from the point of view of
confusability graphs and describe how to include ordinary graphs333It is
sometimes useful to emphasize the distinction between a graph (_i.e._ vertex
and edge set) and a quantum graph (_i.e._ operator system). In this work, we
highlight this by using the terms ordinary or classical graph. as quantum
graphs. We also discuss the technical challenges of giving a quantum graph as
an input for a decision problem. Next, we outline our approach of presenting
them as the description of a quantum circuit and then sketch the definitions
of the $2$-clique and $2$-independent set problems. The extension of these
definitions to larger sets of states is given in Section 4. Lastly, we discuss
how presenting problem instances as circuits descriptions of channels, which
implicitly determines a confusability graph, motivates new versions of the
clique and independent set problems for classical graphs as well.

####  1.1.1 Quantum graphs

##### Confusability Graphs.

A classical noisy channel $N:X\rightarrow Y$ may be parametrised by a
probability transition matrix $N=N(y|x)$, which gives the probability of
receiving output $y$ given input $y$. Given a channel $N$, the corresponding
_confusability graph_ $G_{N}$, is defined on vertex set $X$ with edges $x\sim
x^{\prime}$ whenever $N(y|x)N(y|x^{\prime})\neq 0$, for some $y\in Y$, that is
whenever there is non-zero probability that two inputs are mapped to the same
output [Sha56]. A set $X^{\prime}\subseteq X$ forms an independent set of
$G_{N}$ if $x\not\sim x^{\prime}$ for all distinct $x,x^{\prime}\in
X^{\prime}$, which is if and only if the probability of any pair of distinct
$x,x^{\prime}\in X^{\prime}$ being sent to the same output is $0$. Similarly,
$X^{\prime}$ forms a clique of $G_{N}$ if $x\sim x^{\prime}$ for all distinct
$x,x^{\prime}\in X^{\prime}$, which is if and only if any pair of distinct
elements $x,x^{\prime}\in X^{\prime}$ have a non-zero probability as being
received as the same output.

In the quantum setting, classical noisy channels are superseded by quantum
channels, represented by completely positive trace-preserving (CPTP) maps
$\Phi:\mathbb{M}_{n}(\mathbb{C})\rightarrow\mathbb{M}_{m}(\mathbb{C})$. To
each such quantum channel, one can associate an operator system
$\mathcal{S}_{\Phi}\subseteq\mathbb{M}_{n}$, which is constructed as the
linear span of all products $A^{*}_{i}A_{j}$ for some set of Kraus operators
$\\{A_{i}\\}_{i}$ of $\Phi$. The operator system $\mathcal{S}_{\Phi}$ is
independent of the choice of Kraus representation and can be used to
generalize the role of confusability graphs to study zero-error capacities of
quantum channels. In particular, a collection of orthonormal states $\lvert
v_{1}\rangle,\dots\lvert v_{k}\rangle$ can be distinguished from one another
with certainty after passing through the channel if and only if
$\vphantom{v_{i}v_{j}}\left\lvert\smash{v_{i}}\middle\rangle\\!\middle\langle\smash{v_{j}}\right\rvert$
is orthogonal to $\mathcal{S}_{\Phi}$, in which case we say $\lvert
v_{1}\rangle,\dots,\lvert v_{k}\rangle$ is an _(exact) independent set_ for
$\Phi$ or $\mathcal{S}_{\Phi}$ [DSW13]. More generally, one can extend other
notions from classical graph theory such as cliques and graph colourings to
the setting of operator systems [OP16, Sta16, KM19, BTW21]. In this context,
operator systems are often referred to as quantum graphs or non-commuative
graphs.

##### Classical Graphs as Quantum Graphs

It is possible to embed classical graphs into the set of quantum graphs in the
following way. Starting with an undirected graph $G$, define an operator
system $\mathcal{S}_{G}$ by taking the span of
$\vphantom{ij}\left\lvert\smash{i}\middle\rangle\\!\middle\langle\smash{j}\right\rvert$
over vertices $i$ and $j$ in $G$ satisfying $i=j$ or $i\sim_{G}j$. Graphs $G$
and $H$ are isomorphic if and only if $\mathcal{S}_{G}$ and $\mathcal{S}_{H}$
are unitarily equivalent [OP16]. Similarly, given a noisy channel $N=N(y|x)$,
there are several ways to construct a corresponding quantum channel $\Phi_{N}$
which satisfies $\mathcal{S}_{\Phi_{N}}=\mathcal{S}_{G_{N}}$. Generalizations
of cliques, independent sets, and colourings to quantum graphs respect this
construction, _i.e._ there is a correspondence between $k$-cliques,
$k$-independent sets, and $k$-colourings for $G$ and those for the quantum
graph $\mathcal{S}_{G}$ [Pau16].

##### The Complement of a Quantum Graph.

Recall that, given a graph $G$, the complement $\overline{G}$ is a graph on
the same vertex set where the adjacency relation is defined as
$i\sim_{\overline{G}}j$ if and only if $i\not\sim_{G}j$. However, there is no
generally agreed-upon approach to extending the notion of the graph complement
to quantum graphs. One straightforward approach would be to take the
orthogonal complement of $\mathcal{S}$ inside $\mathbb{M}_{n}$ with respect to
the Hilbert-Schmidt inner product, but this will not be an operator system as
it fails to contain the identity element, and hence fail to correspond to any
channel. One can remedy this by making a correction such as
$\overline{\mathcal{S}}=\mathcal{S}+\mathbb{C}\mathbb{I}$ to account for the
identity [Sta16]. Unfortunately this does not extend the graph complement as
$\mathcal{S}_{\overline{G}}\neq\overline{\mathcal{S}}_{G}$. Another approach
allows both operator systems as well as their orthogonal complements to be
considered as quantum graphs [KM19].

Relevant for this work is the fact there that there is no straightforward and
unique notion of a graph complement for quantum graphs, and consequently the
complexity of decision problems based on cliques and independent sets for
quantum graphs cannot be reduced to one another by taking a complement.
Indeed, as we discuss in Section 1.5, it is even possible that they have
different complexity.

##### Quantum Independent Sets and Quantum Cliques.

Motivated by the study of non-local games, quantum generalizations of many
graph parameters have been found. The existence of $k$-cliques,
$k$-independent sets, and $k$-colourings for a classical graph $G$ can be
determined by the existence of a perfect classical strategy for a
corresponding non-local game. In some cases, _quantum strategies_ for these
games can outperform classical strategies, and perfect quantum strategies give
rise to _quantum cliques_ and _quantum independent sets_ for classical graphs
[MR16, HMPS19]. By considering non-local games where the questions are quantum
states, one can also define quantum cliques and quantum independent sets for
quantum graphs [BGH22].

It is known that determining the quantum value — or commuting operator value —
of a non-local game is an undecidable problem [CS19, JNV+21, MNY22]. These
results can be captured using the non-local games associated to the graph
parameters mentioned above, and thus it undecidable to determine the existence
of quantum cliques/quantum independent sets in either classical and quantum
graphs [Har23]. In this work, we take a different perspective and do not
consider quantum cliques or quantum independence sets. Instead, we exclusively
study the complexity of determining the existence of cliques and independent
sets in graphs and quantum graphs.

####  1.1.2 The clique/independent set problems for quantum graphs

Problems based on finding cliques, independent sets, or graph colourings are
well-studied in classical complexity; they all give rise to NP-complete
problems [Sip12]. In these cases, the input to the problem includes an
explicit description of the vertices and edges of a graph. Providing an
explicit description of a quantum graph raises some challenges: notably
quantum graphs are linear subspaces $\mathcal{S}\subseteq\mathbb{M}_{n}$ and
are thus determined by a basis of operators. As such, given a quantum channel
$\Phi$ on an $n$-qubit system, the corresponding quantum graph $S_{\Phi}$ is a
subspace with up to $2^{2n}$ dimensions, so specifying it in this way requires
a description of an exponentially sized basis. Note that this problem also
arises in the classical case, if the graphs in question are seen as arising
from an noisy channel on an $n$-bit input space. For our work, we will instead
consider quantum graphs as being determined by an underlying quantum channel
$\Phi$, and give a problem instance as a quantum circuit $C$ describing the
action of the channel $\Phi=\Phi_{C}$.

##### Presenting Quantum Graphs as Quantum Circuits.

Different noisy channels can give rise to the same confusability graph, _i.e._
the construction $N\mapsto G_{N}$ is not injective. Similarly, in the quantum
setting, the construction $\Phi\mapsto\mathcal{S}_{\Phi}$ is not injective. On
the other hand, given any graph $G$ one can construct $N$ satisfying $G=G_{N}$
with an appropriate choice of transition probabilities $N=N(y|x)$; likewise
given any operator system $\mathcal{S}\subseteq\mathbb{M}_{n}$, it is possible
to define $\Phi$ such that $\mathcal{S}_{\Phi}=\mathcal{S}$ [Pau16].
Consequently, quantifying over all quantum channels is sufficient to quantify
over all quantum graphs, and it is hence well-motivated to consider parameters
for quantum graphs at the level of channels.

In Section 4, we define approximate $k$-cliques and approximate
$k$-independent sets at the level of quantum channels. For convenience we
restate these definitions here. To keep the presentation concise, we only
include the case $k=2$. In fact, restricting $k=2$ is sufficient for all of
our complexity results in this paper, and in Appendix A we describe an
explicit reduction of the corresponding decision problems from $k>2$ to $k=2$.

######  Definition 1.1.

Let $\alpha\in[0,1]$. We say a pair of orthogonal states $\rho_{1},\rho_{2}$
are an _$(\alpha,2)$ -clique_ for $\Phi$ if
$\operatorname{Tr}\left[\Phi(\rho_{1})\Phi(\rho_{2})\right]\geq\alpha$, and an
_$(\alpha,2)$ -independent set_ if,
$\operatorname{Tr}\left[\Phi(\rho_{1})\Phi(\rho_{2})\right]\leq 1-\alpha$.

We remark on a few details motivating Definition 1.1. Firstly, we require the
inputs state to be exactly orthogonal. This agrees well with the classical
noisy channel setting, which considers sets of distinct inputs $x_{1}\neq
x_{2}$. Second, we express the probability that the outputs of the channel are
confused by means of the overlap under the Hilbert-Schmidt inner product
$\operatorname{Tr}\left[\Phi(\rho_{1})\Phi(\rho_{2})\right]$. This also agrees
well with classical notions of confusability since, if the output states are
classical, _i.e._
$\Phi(\rho_{1})=\sum_{x}\lambda_{x}\vphantom{x}\left\lvert\smash{x}\middle\rangle\\!\middle\langle\smash{x}\right\rvert$
and
$\Phi(\rho_{2})=\sum_{x}\mu_{x}\vphantom{x}\left\lvert\smash{x}\middle\rangle\\!\middle\langle\smash{x}\right\rvert$,
then the overlap $\sum_{x}\lambda_{x}\mu_{x}$ becomes simply the probability
of the channels providing the same input on independent evaluations. Further,
using the overlap as a measure of confusability is also natural in the
computational setting, as the overlap can be efficiently sampled from the
output states by means of the swap test, unlike other measures of closeness
such as the trace distance. We note that we do not require the input states to
be pure, though we can always assume the states in a clique or independent set
are pure by convexity. Neither do we assume the output states are pure, as we
quantify over general, not necessarily unitary, channels. Lastly, the
definition reduces to the exact case for particular values of the parameters:
$(1,k)$-independent sets of $\Phi$ are $k$-independent sets of
$\mathcal{S}_{\Phi}$, and $(1,k)$-cliques are $k$-independent sets of
$\mathcal{S}_{\Phi}^{\perp}$.

What may be seen as a flaw of our definition is that it is possible for a
mixed state $\rho$ to have small overlap with itself. This observation may
seem somewhat contradictory to our measure of confusability, as this means
that two inputs that have the same output state may nevertheless be close to
independent, or _pseudo-independent_. However, by seeing mixed states as
samples from an ensemble of pure states, what this really means is that, upon
taking two independent samples from the ensemble, they are unlikely to be
equal. As we discuss in Section 1.3, this property actually plays an important
role in our proof approach establishing $\textsf{QMA}(2)$-completeness of the
clique problem.

##### Clique and Independent Set Problems

The _quantum channel $2$-clique problem_ with completeness $c$ and soundness
$s$ is the promise problem with yes instances consisting of circuits $C$ such
that $\Phi_{C}$ has a $(c,2)$-clique, and no instances consisting of circuits
for which $\Phi_{C}$ has no $(s,2)$-clique. We always assume $c\geq s$, and in
the cases we consider that there is some probability gap between them. We
define the _quantum channel $2$-independent set problem_ in a parallel way. In
Definition 4.2, we express these problems more formally and extend them to
larger $k$. These promise problems are written $\texttt{qClique}(k)_{c,s}$ and
$\texttt{qIS}(k)_{c,s}$. In this approach, a verifier given a problem instance
$C$ may perform computations by running the circuit $C$ in order to implement
channel $\Phi_{C}$, which determines properties of an underlying quantum graph
$\mathcal{S}_{\Phi_{C}}$. The size of a problem instance is then the size of
the quantum circuit which is used to run this computation, rather than the
size of an explicit description for the operator system
$\mathcal{S}_{\Phi_{C}}$.

We also consider the restricted problems where the circuits $C$ are only taken
from a specific family of quantum circuits $\mathcal{C}$, which we write as
$\texttt{qClique}(k,\mathcal{C})_{c,s}$ and
$\texttt{qIS}(k,\mathcal{C})_{c,s}$. This allows us to determine hardness
results with respect to particular families of channels/quantum circuits such
as entanglement breaking channels and channels which implement partial traces.
Importantly, in Section 5 we specify a family of circuits for which these
problems are QMA-complete.

##### Revisiting the Classical Case.

In light of the above discussion, we can revisit problems related to cliques
and independent sets of classical graphs. More concretely, we consider the
input given as a description of a classical circuit which implements a
deterministic or probabilistic (noisy) function $f$ on input set $X$. Note
that if $X=\\{0,1\\}^{n}$, then the confusability graph $G_{f}$ will be an
exponentially sized graph. We then define our decision problems as deciding if
the corresponding confusability graph $G_{f}$ has a clique or independent set
of size $k$. In this approach, the size of the problem instance is related to
the runtime needed to compute the adjacency relations in $G_{f}$, rather than
the size of an explicit description of $G_{f}$ itself. We also note that our
approach also differs from graph problems for succinctly presented graphs
[GW83], and to the best of our knowledge has not been studied before from this
point of view.

In the case that $f$ is deterministic the confusability graph consists of a
disjoint union of complete subgraphs. In this case, deciding if $G_{f}$ has a
clique of size $k=2$ is equivalent to the well studied collision problem for
functions. It asks whether, given some function $f:X\rightarrow Y$, is there a
pair of elements in the domain $x,y\in X$ with the same image $f(x)=f(y)$ — a
collision. The presumed computational difficulty of this problem on certain
classes of functions underlies the security of hash functions, which serve as
a primary building block of much of modern cryptography.

More formally, we say a deterministic function $f$ has a _$k$ -clique_, or a
_$k$ -independent set_, if there exists distinct inputs $x_{1},\dots,x_{k}$
such that $f(x_{1})=\dots=f(x_{k})$ or $f(x_{1})\neq\dots\neq f(x_{k})$
respectively. The corresponding decision problems, whose instances are
classical circuits describing functions, are denoted $\texttt{Clique}(k)$ and
$\texttt{IS}(k)$. We study this case in Section 3.1.

In the case that the underlying function $f$ is probabilistic, _i.e._ $f$ is a
noisy classical channel, the corresponding confusability graph $G_{f}$ can be
more interesting. Indeed, by suitably picking the transition probabilities it
can be observed that any graph on a vertex set $V$ can arise as the
consufsability graph of some noisy channel $f$ with input set $V$. In Section
3.2, we study the complexity of deciding the existence of approximate
$k$-cliques and approximate $k$-independent sets for probabilistic functions.
We restate the relevant definitions for the case $k=2$ here.

######  Definition 1.2.

Let $\alpha\in[0,1]$. A probabilistic function $f:X\rightarrow Y$ has an
_$(\alpha,2)$ -clique_ if there exist distinct $x,x^{\prime}\in X$ such that
$\Pr\left[f(x)=f(x^{\prime})\right]\geq\alpha,$ and an _$(\alpha,2)$
-independent set_ if there exist distinct $x,x^{\prime}\in X$ such that
$\Pr\left[f(x_{i})=f(x_{j})\right]\leq 1-\alpha.$

The _probabilistic $2$-clique problem_ and the _probabilistic $2$-independent
set problem_ are the promise problems that consist of deciding the existence
of approximate $2$-cliques or $2$-independent sets, up to some specified
promise gap $c-s$. In Section 3.2 we extend these definitions to larger $k$
and we write $\texttt{pClique}(k)_{c,s}$ and $\texttt{pIS}(k)_{c,s}$ for the
corresponding promise problems.

###  1.2 Main results

Our contributions focus on the complexity of the $k$-clique and
$k$-independent set problems across four different settings: the deterministic
case, the probabilistic case, the quantum case, and a restricted quantum case
where the only channels we consider are subset of entanglement breaking
channels. We show that deciding $2$-cliques across these settings is complete
for the classes NP, MA, QMA(2), and QMA, respectively. Further, we show that
the $k$-independent set problems in the deterministic, probabilistic, and
restricted quantum cases are complete for the same classes.

In Section 3, we review the complexity of deciding $k$-cliques and
$k$-independent sets for deterministic functions — the problems
$\texttt{Clique}(k)$ and $\texttt{IS}(k)$. These problems can be viewed as a
rephrasing of the well-studied collision problem for functions. Our
contribution here is to provide new proofs for NP-completeness of these
problems and to state them in a way which generalizes to the problems
considered in Sections 3.2, 4 and 5.

######  Theorem 1.3 (Deterministic case).

$\texttt{Clique}(2)$ and $\texttt{IS}(2)$ are NP-complete.

In Section 3.2, we consider the problems of deciding approximate $k$-cliques
($\texttt{pClique}(k)_{c,s}$) and approximate $k$-independent sets
($\texttt{pIS}(k)_{c,s}$) for probabilistic functions.

######  Theorem 1.4 (Probabilistic case).

There exist $c,s:\mathbb{N}\rightarrow(0,1)$ with constant gap such that
$\texttt{pClique}(2)_{c,s}$ and $\texttt{pIS}(2)_{c,s}$ are MA-complete.

Finding natural MA-complete problems is in itself a active area of research,
and few examples are known [BT10, AG19].

In the quantum setting we study the complexity of deciding approximate
$k$-cliques ($\texttt{qClique}(k)_{c,s}$) and approximate $k$-independent sets
($\texttt{qIS}(k)_{c,s}$) for a quantum channel $\Phi$. The inputs for these
problems are given as the description of a quantum circuit which implements
$\Phi$. In Section 4, we show that for $k=2$ both problems are in
$\textsf{QMA}(2)$, and establish the completeness of
$\texttt{qClique}(2)_{c,s}$. Our hardness result is obtained when quantifying
over a specific subset of quantum circuits,
$\mathcal{C}_{\operatorname{Tr}}\oplus\mathcal{C}_{\operatorname{Tr}}\oplus\mathcal{C}_{\mathrm{EB}}$,
as defined in Definitions 4.7, 4.6 and 4.5. Informally, this corresponds to
the set of circuits which implement channels that are probabilistic mixtures
of entanglement breaking channels and partial trace maps. This is stronger
than hardness of the problem quantified over all channels and implies it.

######  Theorem 1.5 (Quantum Case).

There exist $c,s:\mathbb{N}\rightarrow(0,1)_{\exp}$ with constant gap such
that the clique problem
$\texttt{qClique}(2,\mathcal{C}_{\operatorname{Tr}}\oplus\mathcal{C}_{\operatorname{Tr}}\oplus\mathcal{C}_{\mathrm{EB}})_{c,s}$
is $\textsf{QMA}(2)$-complete.

In Section 5, we show that by further restricting the set of channels to a
particular subset $\mathcal{C}_{\mathrm{EB}^{\prime}}$ of the entanglement
breaking channels, we can obtain QMA-completeness for
$\texttt{qClique}(2,\mathcal{C}_{\mathrm{EB}^{\prime}})_{c,s}$. This suggests
any potential distinction between QMA and $\textsf{QMA}(2)$ may be reflected
in the difference between the properties of these channels and those
considered above.

######  Theorem 1.6 (Restricted Quantum Case).

There exist $c,s:\mathbb{N}\rightarrow(0,1)_{\exp}$ with polynomial gap such
that $\texttt{qClique}(2,\mathcal{C}_{\mathrm{EB}^{\prime}})_{c,s}$ is QMA-
complete.

If one begins with a deterministic or classical noisy channel $f$, and
considers its inclusion as a quantum channel $\Phi_{f}$, as described in
[Pau16], then $f$ will have an $(\alpha,k)$-clique if and only if $\Phi_{f}$
does. Hence, the classical decision problems analysed in Section 3 can
naturally be viewed as a restriction of the problems in Section 5, which in
turn are a restriction of the problems considered and Section 4. Our results
can thus be viewed as a natural hierarchy of problems which are complete for
all four of the proof classes NP, MA, QMA, and $\textsf{QMA}(2)$, and whose
complexity may be tuned by varying the collection of channels.

In Section 4.2, we show that, by slightly extending our proof of hardness of
the quantum clique problem for $\textsf{QMA}(2)$, we can show that it is also
hard for $\textsf{QMA}(k)$. Hence, we provide an alternate proof that
$\textsf{QMA}(k)=\textsf{QMA}(2)$ than the original proof of Harrow and
Montanaro [HM13].

In Appendix A we provide a direct reductions from clique and independent set
problems in the deterministic, probabilistic, and quantum settings from larger
$k$ to $k=2$. In Appendix B, we provide a more straightforward proof
establishing $\textsf{QMA}(2)$-hardness for $\texttt{qClique}(2)_{c,s}$ when
quantifying over all quantum circuits than the stronger one given in Theorem
1.5.

Finally, as touched upon in Section 1.1.2, the problems of deciding
approximate $k$-cliques ($\texttt{pClique}(k)_{c,s}$) and approximate
$k$-independent sets ($\texttt{pIS}(k)_{c,s}$) for probabilistic functions can
be viewed as a new approach to define decision problems for graphs. Instead of
an explicit description of a graph, the instances of our problems consist of a
circuit description for a probabilistic function $f$ which implicitly
determines a graph $G_{f}$ as its confusability graph. Such an approach is
well suited to connect modern ideas in complexity to the pioneering work of
Shannon. To the best of our knowledge these types of decision problems on
graphs have not been studied before and we hope it can motivate future work
within the intersections of complexity theory and graph theory.

###  1.3 Proof techniques

Our proof techniques were inspired by techniques in self-testing and protocols
for delegating quantum computation, such as in [Gri19, BMZ23]. Other recent
work of Bassirian, Fefferman, and Marwaha considers different connections
between self-testing and $\textsf{QMA}(2)$ [BFM23]. In short, if we know a
channel has or does not have cliques over a particular set of states — for
example, the separable states — then we can combine it with another channel to
guarantee that possible cliques among the remaining states are not important.
The proofs use two important constructions, which we will comment on here. We
also discuss different techniques we use in the proof of QMA-completeness of a
restricted version of the problem.

##### Non-unitary circuits and direct sums

First, we devise a new technique to take direct sums of quantum circuits
(Definition 4.6). In order to be able to parametrise arbitrary non-unitary
channels by means of circuit diagrams, we work with an extended circuit model
that appends partial trace and state preparation maps to a basic set of
unitary gates. In this way, we extend the universality of a gate set to CPTP
maps by means of the Stinespring dilation theorem. At the level of channels,
there are a variety of ways to compose the maps to get new ones, but it is not
always immediate how that translates to composition at the level of circuits —
importantly, whether it is computationally efficient. In our constructions,
the way we will combine channels is by means of the direct sum: given two
channels $\Phi_{1}$ and $\Phi_{2}$ and a probability $p$, the direct sum is
$p\Phi_{1}\oplus(1-p)\Phi_{2}$, the convex combination of the channels
$\Phi_{1}$ and $\Phi_{2}$ with orthogonal output spaces. Of course, the
circuit model is well-adapted for composition and direct products of maps, but
not for sums. To get the wanted superposition of circuits, we might add a
qubit in state $\sqrt{p}\lvert 0\rangle+\sqrt{1-p}\lvert 1\rangle$,
conditionally act by either $\Phi_{1}$ or $\Phi_{2}$ based on this qubit, and
then measure the added qubit. This, however, has a technical obstruction:
conditioning a non-unitary channel can put the number of output qubits in
superposition or probabilistic mixture, which is untenable. Instead, we use
the fact that the circuits decompose into the basic gates to separate the
unitary from the non-unitary gates. Then, the unitary gates act conditionally
on the additional modulating qubit as wanted and the non-unitary gates can be
aligned to act the same way for both $\Phi_{1}$ and $\Phi_{2}$. In this way,
we get a circuit that implements a direct sum of channels of size polynomial
(in fact linear) in the size of the circuits describing the original channels.
See also Fig. 2 for an illustration of this construction. We are optimistic
that this direct sum construction might be able to find various other
applications in quantum information.

##### Self-testing for cliques

Next, the direct sum construction allows us to port ideas from self-testing
over to questions about quantum cliques. The main technical tool we prove to
use this technique is Lemma 4.9. As noted above, the technique takes the
direct sum of two channels in order to expand the set of pairs of states on
which some property of one of the channels. To illustrate how this works, we
outline the proof of $\textsf{QMA}(2)$-hardness of the quantum $2$-clique
problem (Theorem 4.8), which is based on this technique. Given some instance
$x$ of a $\textsf{QMA}(2)$ promise problem $(Y,N)$, we know that there is some
efficiently constructable circuit $\Phi_{x}$ that accepts with high
probability on some separable state if $x$ is a yes instance, and with low
probability on every separable state if $x$ is a no instance. In the first
step, we construct an entanglement-breaking channel $\Psi_{x}$ that runs this
verification, measures, and outputs a pure state if it accepts and a highly
mixed state if it rejects (Lemma 4.12). Note that this channel acts on one
more qubit than $\Phi_{x}$, which it immediately traces out, in order to have
that qubit guarantee orthogonality of any clique. If $\Phi_{x}$ accepts with
high probability, then $\Psi_{x}$ outputs a state close to pure, and thus, the
overlap of two input states differing only in the orthogonality qubit will be
high. As such, if $x$ is a yes instance, $\Psi_{x}$ has a clique in the
separable states. On the other hand, if $\Phi_{x}$ accepts with low
probability, then the output state will be far from pure, resulting in low
overlap — as such, a no instance leads to a channel $\Psi_{x}$ with no cliques
among the separable states. The trick however is to lift this property to all
the states. To do so, we use the channel $\Phi_{1}$ constructed in Lemmas 4.10
and 4.11, consisting of a direct sum of partial traces on the subregisters we
wish to be unentangled. For this channel, we uncover a property reminiscent of
self-testing: if states form a near optimal clique, then they must be
separable, since partial traces of entangled states are mixed and hence have
low overlap. Finally, in the convex combination of $\Phi_{1}$ and $\Psi_{x}$,
we find via Lemma 4.9 that if we weight $\Phi_{1}$ sufficiently, then the
testing for separability overcomes the any potential non-separable cliques of
$\Psi_{x}$, and thus that for a no instance the channel has no cliques. Since
the weighting can be chosen to preserve polynomial or constant gaps, this
proves the hardness of the $2$-clique problem for $\textsf{QMA}(2)$. We
believe that this technique is readily extendable to prove other properties of
channels; in fact, in Appendix A, we use $\Phi_{1}$ as well as a channel that
guarantees orthogonality among the tensor terms of a separable state to reduce
the quantum $k$-clique problem directly to the $2$-clique problem.

##### Independent sets

It is interesting to note that, though this proof technique is very useful in
determining properties of cliques, it seems not to be well-adapted to the
study of independent sets. First, Lemma 4.9 is used to expand collections of
states where there is no clique, whereas this would require us to be able to
expand collections of states where there is no independent set. A more serious
technical obstruction, however, is that where cliques may arise from
essentially one source, independent sets arise from two. The overlap of two
states is high if they are approximately equal _and_ pure. However, the
overlap of two states is low if they are approximately orthogonal _or_ highly
mixed. The first corresponds to an approximate version of the independent sets
for an operator system, but the second does not. This case of low overlap,
which we refer to as a _pseudo-independent_ set underpins the proofs of
hardness of the clique problem, but seems to be an obstruction for the
independent set problem. In particular, if we want to guarantee small overlap,
it is not required to output orthogonal states — it suffices to output a
highly mixed state. Also, high overlap is critical in guaranteeing
separability of states by means of Lemma 4.11. This raises an interesting
question: does there exist a channel where the independent sets are separable
states? Resolving this would serve to illuminate the complexity of the clique
problem greatly.

##### Entanglement-breaking channels and QMA

Finally, our proof of the QMA-completeness of the clique problem for a
subclass of the entanglement-breaking channels uses significantly different
techniques. The main difficulty lies in showing that this problem actually
lies in QMA. This relies on an interesting result of Brandão [Bra08], which
shows that the subclass of $\textsf{QMA}(2)$ where the verifier may measure
with a Bell measurement — measure each of the factors in the separable state
separately, and then classically compute whether or not to accept — lies in
QMA. We find that computing the clique value by running the channel and then
doing the swap test is in fact a Bell measurement when the channel is
entanglement-breaking. Nevertheless we must still further restrict, because
there is another check needed to verify a clique: checking orthogonality of
the states. In our proof that the clique problem is in $\textsf{QMA}(2)$, we
also do this via the swap test. However, since this swap test is not prefixed
by an entanglement-breaking channel, it cannot be evaluated by a Bell
measurement. In fact, Harrow and Montanaro [HM13] show that the swap test
cannot even be run by an LOCC measurement, which is a larger class the the
Bell measurements. As such, we need a different method to guarantee
orthogonality; we work over channels where the output is independent of one of
the qubits, _i.e._ that qubit is immediately traced out. This the same method
as we have used to guarantee existence of an orthogonal clique in the
$\textsf{QMA}(2)$-hard clique problem. As such, the prover need not even send
as a proof a clique where the states are orthogonal — the verifier may
nevertheless be certain that there exists one. Finally, we note that, unlike
the $\textsf{QMA}(2)$-completeness result, the QMA-completeness result
generalises immediately to the independent set problem as well.

###  1.4 Relation to other works

Closely related to our work is that given in the unpublished work of Beigi and
Shor [BS08]. In their work, a promise problem referred to as the _quantum
clique problem_ is proven to be complete for QMA. This problem is similar to
but distinct from $\texttt{qIS}(k,\mathcal{C})_{c,s}=(Y,N)$ as we define it in
Definition 4.1. Firstly, in terms of terminology, what Beigi and Shor refer to
as a _quantum clique_ for a channel is more closely related to what is
commonly called an independent set in the quantum graph literature. The
standardization of this terminology was established after the release their
work and we chose to model our terminology following more current conventions.

There are also a few more substantial differences which make our results and
theirs incomparable in a direct sense. In order to highlight some of these
differences we restate their definition below.

######  Definition 1.7.

[Definition 2.9 from [BS08]] Quantum clique problem $(\Phi,k,a,b)$

  * •

Input Integer numbers $n$ and $k$, non-negative real numbers $a,b$ with an
inverse polynomial gap $b-a>n^{-c}$, and an entanglement breaking channel
$\Phi$ that acts on $n$-qubit states.

  * •

Promise Either there exists $\rho^{1}\otimes\dots\otimes\rho^{k}$ such that
$\sum_{i,j}tr(S\,\Phi(\rho^{i})\otimes\Phi(\rho^{j}))\leq a$ or for any state
$\rho^{1,2\dots k}$ we have $\sum_{i,j}tr(S\,\Phi^{\otimes 2}(\rho^{i,j}))\geq
b$.

  * •

Output Decide which one is the case.

One key difference between Definition 4.1 and Definition 1.7 is that their
promise problem makes explicit reference to the SWAP operator $S$ — see
Section 2.5 for more details on this and the well-known swap test. Even when
quantifying over only entanglement-breaking maps, it is not clear that the two
problems are the same, since the swap test can fail if the input state is not
given as a product state. That is, the promise made in the work of Beigi and
Shor is more significant than we use: no instances are those where the swap
test rejects with high probability on all, potentially entangled, states and
not just on separable states, as we require.

Another difference is with regard to how the classical description for a
quantum channel $\Phi$ is given as input to the problems. Beigi and Shor
establish QMA-completeness for Definition 1.7 when considering entanglement-
breaking quantum channels given in terms of an operator sum, or Kraus,
representation

$\Phi(\rho)=\sum_{i=1}^{r}E_{i}\rho E_{i}^{\dagger},$ (1)

whereas in our case we consider inputs given as a description of a quantum
circuit $C$.

Despite some differences in our approaches we took much inspiration from the
ideas present in [BS08]. Separate from our work here, another active project
is investigating the complexity of quantum graph problems using an approach
more closely following that given in [BS08].

###  1.5 Open problems

In this section, we outline a selection of open problems motivated by our
work.

##### Deciding Independent Sets in Quantum Graphs

The existence of graph complementation provides a straightforward way to
reduce the problems of deciding cliques and independent sets for graphs. This
also extends to the versions of these problems introduced in Section 3.

In the quantum setting, our proof technique establishing
$\textsf{QMA}(2)$-hardness for the clique problem $\texttt{qClique}(k)_{c,s}$
could not readily be extended to the problem $\texttt{qIS}(k)_{c,s}$. As
discussed in Section 1.1.1, there is no canonical way to take the complement
of a quantum graph as there is classically. Instead, several differing
approaches have been considered in the literature. Even when one considers the
different approaches available, it is not clear how to use these maps on the
level of operator systems to obtain an efficient reduction between
$\texttt{qClique}(k)_{c,s}$ and $\texttt{qIS}(k)_{c,s}$. Indeed, in an
informal sense, it would appear that under any appropriate notion of
complementation the complement of a quantum graph can be a significantly more
complicated object than the original quantum graph. On the one hand, we know
that the quantum independent set problem is contained in $\textsf{QMA}(2)$. On
the other hand, it is hard for QMA. However, we feel it is unlikely that there
exists a QMA verification circuit for $\texttt{qIS}(k)_{c,s}$. This is a
similar situation to the pure state version of the QMA-complete consistency of
local density matrices problem, which has long been conjectured to be complete
for $\textsf{QMA}(2)$ [BG22]. It is possible that neither of these problems is
QMA or $\textsf{QMA}(2)$-complete, and a reduction from one of the two
problems to the other would be enlightening.

##### Deciding Colourings

Famously, Lovász showed a reduction between the $k$-colouring problem and the
$3$-colouring problem in ordinary graphs [Lov73]. In this case, the instances
are given using an explicit description of the graph. In Section 3, we
introduce new variants of the $k$-clique and $k$-independent set problems
motivated from the study of noisy channels and confusability graphs. It is
straightforward to similarly define a new version of the $k$-colouring
problem. We did not investigate the complexity of this problem but suggest it
as worthy area of exploration. Since a colouring on exponentially many
vertices cannot be described in polynomial time, it is altogether possible
that the class where this colouring problem lives is significantly larger than
NP.

In the quantum setting, various approaches to define a $k$-colouring for a
quantum graph have been considered [KM19, Sta16]. Informally, a $k$-colouring
of a quantum graph $\mathcal{S}\subseteq\mathbb{M}_{k}$ consists of a
partition of an orthogonal basis for $\mathbb{C}^{k}$ into independent sets.
As in the classical case, for an $n$-qubit quantum channel, this would require
specifying a basis for a $2^{n}$ dimensional space. It seems unlikely that the
corresponding problem could decided in $\textsf{QMA}(2)$.

##### Other Graph Problems:

There are a variety of decision problems for graphs which can possibly
extended to the quantum setting via a similar approach to the one we use for
the clique and independent set problems. We suggest two more here. Firstly, in
our problems, the size $k$ of a clique or independent set is a parameter which
defines the problem. One can instead consider the value $k$ to be specified
along with the circuit description as an input. In the classical case of
graphs described by their adjacency matrices, this takes the complexity of
finding a clique or independent set from P to NP-hard [Sip12]. One might
imagine a similar jump happens in the cases we have considered, from NP, MA,
QMA, or $\textsf{QMA}(2)$ to larger classes.

Secondly, one can consider versions of the well-studied graph isomorphism and
non-isomorphism problems. In particular, consider a quantum verifier who
receives as input a pair of circuits $C_{1}$ and $C_{2}$ which implement
classical or quantum channels $\Phi_{1}$ and $\Phi_{2}$. The corresponding
promise problems would then be to decide if the quantum graphs
$\mathcal{S}_{\Phi_{1}}$ and $\mathcal{S}_{\Phi_{1}}$ are approximately
isomorphic or far from isomorphic. The quantum analogues of these problems may
also provide new approaches to zero-knowledge proof protocols in the quantum
setting, since graph isomorphism/non-isomorphism played an important role in
early work on zero-knowledge proof systems [GMW91, BOGG+88]. The area of zero-
knowledge proof systems in the quantum setting has seen a flurry of recent
advances [GSY19, VZ20, BG22, CFGS18, BMZ23], and it would be interesting if
the study of quantum graph isomorphisms can provide new approaches to zero-
knowledge in some of these settings.

Another possible area of exploration is Ramsey theory for quantum graphs.
Ramsey theory is a branch of mathematics initiated by F. Ramsey which examines
the existence of ordered substructures arising in graphs of a sufficient size
[Ram30]. Ramsey theory has some interesting connections with computational
complexity, such as studying the computational complexity of computing the
Ramsey numbers [Bur90]. Several of the motivating themes of Ramsey theory have
been explored for quantum graphs [Wea17, KKS20], and it may be worthwhile to
explore connections to complexity inspired by these works that incorporates
our approaches for presenting quantum graphs as circuits.

###  1.6 Acknowledgements

We thank David Cui, Joshua Nevin, Seyed Sajjad Nezhadi, Laura Mančinska, Se-
Jin Kim, and Adrian She for lengthy discussions during the early stages of
this project. We also thank Adrian She and David Cui for detailed discussions
and for sharing extensive notes on [BS08].

###  1.7 Outline

In Section 2 we outline the important notation we use, and give some brief
background information on complexity theory and aspects of quantum information
we require. In Section 3, we consider the classical deterministic (Section
3.1) and probabilistic (Section 3.2) versions of the clique and independent
set problems. We show their completeness for the complexity classes NP and MA,
respectively. Next, in Section 4, we study the clique and independent set
problems for quantum channels. We show in Section 4.1 that the quantum
$2$-clique problem is $\textsf{QMA}(2)$-complete, and in Section 4.2 that this
completeness implies a new proof that $\textsf{QMA}(k)=\textsf{QMA}(2)$. In
Section 4.3, we discuss the quantum independent set problem for quantum
channels. Finally, in Section 5, we present a restriction of the quantum
clique and independent set problems that is QMA-complete. We also collect some
additional results in appendices: first, in Appendix A, we give reductions
from $k$-clique and independent set problems to the correpsonding problem with
$k=2$; also, in Appendix B, we give a simpler but weaker proof of the
$\textsf{QMA}(2)$-completeness of the quantum $2$-clique problem.

##  2 Preliminaries

###  2.1 Notation

We use italic capitals $H,K,L$ to represent Hilbert spaces, which we always
assume to be finite-dimensional. Given a finite set $S$, write
$\mathbb{C}^{S}$ for the $|S|$-dimensional Hilbert space with canonical
(computational) basis $\vphantom{\lvert s\rangle s\in S}\left\\{{\lvert
s\rangle}\mid{s\in S}\right\\}$. As a special case, we denote the space of one
qubit $Q=\mathbb{C}^{\\{0,1\\}}$. Fix some Hilbert space $H$. Write
$H_{\perp}$ for the superspace $H+\mathbb{C}\lvert\perp\rangle$ where
$\|\lvert\perp\rangle\|=1$ and
$\vphantom{\perp\psi}\left\langle\smash{\perp}\middle|\smash{\psi}\right\rangle=0$
for all $\lvert\psi\rangle\in H$. For any subspace $K\subseteq H$, write
$\mu_{K}$ for the maximally-mixed state on $K$. Write $\mathcal{L}(H)$ for the
space of linear operators on $H$, write $\mathcal{P}(H)$ for the space of
positive operators, and $\mathcal{D}(H)$ to be the set of density operators
(trace $1$ positive operators). We use quantum state interchangeably with
density operator, specifying to pure quantum states when necessary; and we use
quantum channel interchangeably with completely positive trace-preserving
(CPTP) map.

We denote the set of all bitstrings
$\\{0,1\\}^{\ast}:=\bigcup_{n=0}^{\infty}\\{0,1\\}^{n}$. Given some
$x\in\\{0,1\\}^{\ast}$, write $|x|\in\mathbb{N}$ for its length. For a
function $f:\mathbb{N}\rightarrow[0,1]$, write
$f:\mathbb{N}\rightarrow(0,1)_{\exp}$ to mean that there exist $N,k>0$ such
that $2^{-n^{k}}<f(n)<1-2^{-n^{k}}$ for all $n\geq N$. Write the set of
polynomially-bounded functions
$\texttt{poly}=\vphantom{f:\mathbb{N}\rightarrow\mathbb{R}\exists\,k,N\geq
0.\;f(n)\leq n^{k}\,\forall\,n\geq
N}\left\\{{f:\mathbb{N}\rightarrow\mathbb{R}}\mid{\exists\,k,N\geq
0.\;f(n)\leq n^{k}\,\forall\,n\geq N}\right\\}$. For a natural number
$n\in\mathbb{N}$, write $[n]:=\\{1,2,\ldots,n\\}$.

###  2.2 Complexity theory

A _language_ is a subset $L\subseteq\\{0,1\\}^{\ast}$. An element $x\in L$ is
called a yes instance, and an element $x\notin L$ is called a no instance. A
_promise problem_ is a pair $(Y,N)$ of disjoint subsets
$Y,N\subseteq\\{0,1\\}^{\ast}$. Here, $x\in Y$ is called a yes instance and
$x\in N$ is called a no instance, while $x\notin Y\cup N$ is indeterminate.
Promise problems generalise languages in the sense that every language $L$
corresponds to the promise problem $(L,L^{c})$. A _complexity class_ is a
collection of languages or promise problems.

A function $f:\\{0,1\\}^{\ast}\rightarrow\\{0,1\\}^{\ast}$ is computable in
time $T(n)$ if there exists a Turing machine $M$ that, on input $x$, outputs
$M(x)=f(x)$ in $T(|x|)$ steps. We say $f$ is polynomial-time computable if
there exists a polynomial $p:\mathbb{N}\rightarrow\mathbb{N}$ such that $f$ is
computable in time $p(n)$.

A language $L_{1}$ is _polynomial-time Karp-reducible_ to another language
$L_{2}$ if there exists a polynomial-time computable function $f$ such that
$x\in L_{1}$ iff $f(x)\in L_{2}$. For promise problems, a similar definition
holds, the only difference being that the function must map no instances to no
instances as well. Given a complexity class C, $L$ is _C -hard_ (under
polynomial-time Karp reductions) if every element of C is polynomial-time Karp
reducible to $L$. $L$ is _C -complete_ if additionally $L\in\textsf{C}$.

###  2.3 Quantum and classical circuits

In its usual usage, the circuit model of quantum computation is used to
describe unitary channels. To describe unitaries, we fix a (finite) universal
gate set $S\in\mathcal{U}_{n_{0}}(\mathbb{C})$ — in this work, we do not need
to specify the choice of gate set set, but one can, for example, always assume
that it is the Clifford$+T$ gate set $\\{\mathrm{CNOT},H,T\\}$. We can
approximate any unitary to arbitrary precision by a composition of finitely
many tensors of the basic gates.

In order to describe all quantum channels, we need to add two non-unitary
operations, that change the number of qubits, to the basic gate set:

  * •

The _partial trace_ on one qubit
$\operatorname{Tr}:\mathcal{L}(\mathbb{C}^{2})\rightarrow\mathbb{C}$;

  * •

_State preparation_ of one qubit in the computational basis
$\mathbb{C}\rightarrow\mathcal{L}(\mathbb{C}^{2})$,
$\lambda\mapsto\lambda\vphantom{0}\left\lvert\smash{0}\middle\rangle\\!\middle\langle\smash{0}\right\rvert$.

Due to the Stinespring dilation theorem, the augmented gate set
$S\cup\\{\operatorname{Tr},\vphantom{0}\left\lvert\smash{0}\middle\rangle\\!\middle\langle\smash{0}\right\rvert\\}$
can approximate any quantum channel to arbitrary precision. Stinespring
dilation also guarantees that the circuit can be expressed in a canonical form
where qubit preparation happens first, followed by unitary gates, followed by
partial traces. In fact, given a circuit description, it can be taken to this
canonical form efficiently simply by sliding the state preparations backwards
and the partial traces forwards. As such, we will assume that the circuits are
always in this form.

Note that POVM measurements can in particular be realised in this model. For
example, measurement of a qubit in the computational basis can be realised by
the following circuit:

$\lvert 0\rangle$${\operatorname{Tr}}$

Other measurements can be realised similarly — diagonalising for PVMs or using
Naimark’s theorem for general POVMs — although the circuit representations may
consist of many gates.

For the computational problems we consider, the instances take the form of
circuit diagrams describing some quantum channel. It is perhaps simplest from
the theory standpoint to present the diagrams as pictures, but it is wholly
equivalent to represent the circuits as an encoding of the diagram as a
bitstring, which is more natural from a computational standpoint. For a
circuit diagram $C$, write $\Phi_{C}$ for its implementation as a quantum
channel. We take the length of the circuit
$|C|=\texttt{in}(C)+\texttt{out}(C)+\texttt{gates}(C)$, the sum of the number
of input qubits, the number of output qubits, and the number of gates. Note
that it is possible to choose an encoding as a bitstring whose length is
polynomial in the circuit length described above, and vice versa.

We can also treat classical circuits in a similar way. Here, circuits describe
not channels but functions $f:\\{0,1\\}^{m}\rightarrow\\{0,1\\}^{n}$. But, as
in the quantum case, we can choose a finite universal gate set, for example
$\\{\mathrm{NAND}\\}$. Given a classical circuit diagram $C$, write $f_{C}$
for the function it represents and
$|C|=\texttt{in}(C)+\texttt{out}(C)+\texttt{gates}(C)$ for the circuit size.

###  2.4 Distances between states

There are a variety of natural distance measures between quantum states; we
use three: the Euclidean norm, the trace norm, and the Frobenius (or Hilbert-
Schmidt) norm. The Euclidean distance is only defined on pure states and is
simply the natural norm induced by the inner product on the Hilbert space
$\|\lvert\psi\rangle\|=\sqrt{\vphantom{\psi}\left\langle\smash{\psi}\middle|\smash{\psi}\right\rangle}$.
The trace norm is defined for all $A\in\mathcal{L}(H)$ as
$\|A\|_{\operatorname{Tr}}=\frac{1}{2}\operatorname{Tr}[\sqrt{A^{\dagger}A}]$;
and the Frobenius norm is defined similarly as
$\|A\|_{2}=\sqrt{\operatorname{Tr}[A^{\dagger}A]}$. The following simple lemma
relates the metrics that these norms induce on the pure states. We use this
extensively and without mention.

######  Lemma 2.1.

Let $\lvert\psi\rangle,\lvert\phi\rangle$ be pure states. Then,

$\displaystyle\|\vphantom{\psi}\left\lvert\smash{\psi}\middle\rangle\\!\middle\langle\smash{\psi}\right\rvert-\vphantom{\phi}\left\lvert\smash{\phi}\middle\rangle\\!\middle\langle\smash{\phi}\right\rvert\|_{2}=\sqrt{2}\|\vphantom{\psi}\left\lvert\smash{\psi}\middle\rangle\\!\middle\langle\smash{\psi}\right\rvert-\vphantom{\phi}\left\lvert\smash{\phi}\middle\rangle\\!\middle\langle\smash{\phi}\right\rvert\|_{\operatorname{Tr}},$
(2)
$\displaystyle\|\vphantom{\psi}\left\lvert\smash{\psi}\middle\rangle\\!\middle\langle\smash{\psi}\right\rvert-\vphantom{\phi}\left\lvert\smash{\phi}\middle\rangle\\!\middle\langle\smash{\phi}\right\rvert\|_{2}\leq\sqrt{2}\|\lvert\psi\rangle-\lvert\phi\rangle\|.$
(3)

###### Proof.

For the first relation, let
$X=\vphantom{\psi}\left\lvert\smash{\psi}\middle\rangle\\!\middle\langle\smash{\psi}\right\rvert-\vphantom{\phi}\left\lvert\smash{\phi}\middle\rangle\\!\middle\langle\smash{\phi}\right\rvert$.
If $X=0$, then this holds trivially. Else, there exists an eigenvalue
$\lambda\neq 0$ of $X$. Since $\mathrm{rank}(X)=2$ and
$\operatorname{Tr}(X)=0$, the only nonzero eigenvalues of $X$ are $\lambda$
and $-\lambda$. This gives that
$\|X\|_{2}=\sqrt{\lambda^{2}+(-\lambda)^{2}}=\sqrt{2}|\lambda|$; and
$\|X\|_{\operatorname{Tr}}=\tfrac{1}{2}\left\lparen|\lambda|+|-\lambda|\right\rparen=|\lambda|$.

For the second relation, note that

$\displaystyle\begin{split}\|\vphantom{\psi}\left\lvert\smash{\psi}\middle\rangle\\!\middle\langle\smash{\psi}\right\rvert-\vphantom{\phi}\left\lvert\smash{\phi}\middle\rangle\\!\middle\langle\smash{\phi}\right\rvert\|_{2}^{2}&=2-2\left\lvert\vphantom{\psi\phi}\left\langle\smash{\psi}\middle|\smash{\phi}\right\rangle\right\rvert^{2}\leq
2(2-2\lvert\vphantom{\psi\phi}\left\langle\smash{\psi}\middle|\smash{\phi}\right\rangle\rvert)\\\
&\leq
2(2-2\operatorname{Re}\vphantom{\psi\phi}\left\langle\smash{\psi}\middle|\smash{\phi}\right\rangle)=2\|\lvert\psi\rangle-\lvert\phi\rangle\|^{2}.\end{split}$
(4)

∎

###  2.5 The swap test

The swap test, first introduced in [BCWdW01], provides a computationally
efficient way to project on the symmetric subspace of a tensor product Hilbert
space — the $+1$ eigenspace of the swap operator that exchanges the two tensor
terms. The swap test proceeds on a state $\rho\in\mathcal{D}(H\otimes H)$ as
follows:

  1. 1.

Prepare an auxiliary qubit in the state $\lvert+\rangle$.

  2. 2.

Act with the swap operator on $\rho$ conditionally on the auxiliary qubit.

  3. 3.

Measure the auxiliary qubit the Hadamard basis. Accept if the measurement
result is $0$ and reject if not.

The swap test is illustrated as a quantum circuit Fig. 1.

$H$$H$$\rho\;{\Bigg{\\{}}$$\lvert 0\rangle$ Figure 1: Quantum circuit
representation of the swap test.

Let $\Pi_{H}:H\otimes H\rightarrow H\otimes H$ be the projector onto the
symmetric subspace. Then, the swap test implements the channel
$\rho\mapsto\Pi_{H}\rho\Pi_{H}\otimes\vphantom{0}\left\lvert\smash{0}\middle\rangle\\!\middle\langle\smash{0}\right\rvert+(\mathbb{I}-\Pi_{H})\rho(\mathbb{I}-\Pi_{H})\otimes\vphantom{1}\left\lvert\smash{1}\middle\rangle\\!\middle\langle\smash{1}\right\rvert$.
It’s also useful to note that, if $\rho$ is a separable state
$\rho=\rho_{1}\otimes\rho_{2}$, then the probability of the swap test
accepting is
$\frac{1}{2}+\frac{1}{2}\operatorname{Tr}\left[\rho_{1}\rho_{2}\right]$.

##  3 Classical Collision and Clique Problems

In this section, we formally introduce the classical versions of the clique
and collisions problems and study their computational complexity.

###  3.1 The deterministic case

The _collision problem_ for functions is of fundamental interest to complexity
theory and cryptography. It asks whether, given some function $f:X\rightarrow
Y$, is there a pair of elements in the domain $x,y\in X$ with the same image
$f(x)=f(y)$ — a collision.

Collisions also have a natural interpretation in the language of channel
capacity. The function $f$ can be seen as a deterministic (_i.e._ not noisy)
channel from the input set $X$ to the output set $Y$. As in the case for a
noisy channel, this induces a _confusability graph_ on the set $X$: $x$ and
$y$ are connected by an edge if and only if $f(x)=f(y)$. That is, the
confusability graph indicates the collisions of the function. The graphs that
this procedure induce are, in themselves, not particularly interesting — they
are simply disjoint unions of complete graphs on the subsets of the input set
that collide — but they allow to interpret collisions in a graph-theoretic
way, as cliques. With this in mind, we define the following graph-theoretic
notions for functions.

######  Definition 3.1.

Let $X,Y$ be sets and $k\in\mathbb{N}$.

  * •

A function $f:X\rightarrow Y$ has a _$k$ -clique_ (or $k$-collision) if there
exist distinct $x_{1},\ldots,x_{k}\in X$ such that $f(x_{1})=\ldots=f(x_{k})$.

  * •

A function $f:X\rightarrow Y$ has a $k$-independent set if there exist
distinct $x_{1},\ldots,x_{k}\in X$ such that $f(x_{i})\neq f(x_{j})$ for all
$i\neq j$.

To study the complexity of finding cliques and independent sets, we fix a
presentation for the functions we consider. The most basic way to present a
function is as a table of values. Though this is the most general, it is
highly inefficient: a function that may be easy to compute is described with
the same complexity as function that is more difficult, and the length of the
function description is exponential in the size of the input set. Two natural
and equivalent options from the point of view of computational complexity are
to present a function as a Turing machine or as a circuit diagram. We will use
the circuit description, as this will generalise more naturally to quantum
channels, represented as quantum circuits. With this choice of convention, we
can formally present the clique and independent set problems in the
deterministic case.

######  Definition 3.2.

Let $k\in\mathbb{N}$. The language for the _$k$ -clique problem_ is

$\displaystyle\texttt{Clique}(k)=\vphantom{\text{circuits
}Cf_{C}:\\{0,1\\}^{\texttt{in}(C)}\rightarrow\\{0,1\\}^{\texttt{out}(C)}\text{
has a $k$-clique}}\left\\{{\text{circuits
}C}\mid{f_{C}:\\{0,1\\}^{\texttt{in}(C)}\rightarrow\\{0,1\\}^{\texttt{out}(C)}\text{
has a $k$-clique}}\right\\}.$ (5)

The language for the _$k$ -independent set problem_ is

$\displaystyle\texttt{IS}(k)=\vphantom{\text{circuits
}Cf_{C}:\\{0,1\\}^{\texttt{in}(C)}\rightarrow\\{0,1\\}^{\texttt{out}(C)}\text{
has a $k$-independent set}}\left\\{{\text{circuits
}C}\mid{f_{C}:\\{0,1\\}^{\texttt{in}(C)}\rightarrow\\{0,1\\}^{\texttt{out}(C)}\text{
has a $k$-independent set}}\right\\}.$ (6)

It is well known that the collision problem for general functions is NP-
complete; we will give simple constructions that provide this completeness in
the context of our graph-theoretic language. First, we recall the definition
of NP.

######  Definition 3.3.

A language $L\subseteq\\{0,1\\}^{\ast}$ is in NP if there exist polynomials
$p,q:\mathbb{N}\rightarrow\mathbb{N}$ and a Turing machine $V$ with two input
tapes and one output tape such that

  * •

For all $x,y\in\\{0,1\\}^{\ast}$, $V$ halts on input $(x,y)$ in $q(|x|)$
steps.

  * •

For all $x\in L$, there exists $y\in\\{0,1\\}^{p(|x|)}$ such that $V(x,y)=1$.

  * •

For all $x\notin L$ and for all $y\in\\{0,1\\}^{\ast}$, $V(x,y)=0$.

To finish this section, we give proofs of the NP-completeness of both the
$2$-clique and the $2$-independent set problems. Note that the proofs of
inclusion of the $2$-clique and $2$-independent set problems in NP generalise
directly to the case of $k$-cliques and $k$-independent sets (for $k$
polynomial in the instance size), showing that these _a priori_ harder
problems are also NP-complete. In Appendix A, we also provide a direct
reductions to the $2$-clique and independent set problems.

######  Proposition 3.4.

$\texttt{Clique}(2)$ is NP-complete.

###### Proof.

First, it is direct to see that the problem
$\texttt{Clique}(2)\in\textsf{NP}$. In fact, given a circuit $C$, the verifier
expects to receive a proof of the form $(x,y)$ for
$x,y\in\\{0,1\\}^{\texttt{in}(C)}$, computes $f_{C}(x)$ and $f_{C}(y)$, and
accepts if and only if they are equal. If $C$ is a yes instance, then the
prover can simply provide a collision, causing the verifer to accept; and
else, there is no clique for the prover to provide, so the verifier never
accepts.

Next, we need to see that $\texttt{Clique}(2)$ is NP-hard. Let
$L\in\textsf{NP}$, let
$V:\\{0,1\\}^{\ast}\times\\{0,1\\}^{\ast}\rightarrow\\{0,1\\}$ be its verifier
Turing machine, $q$ be the halting time, and $p$ be the proof length. Then,
for each $x\in\\{0,1\\}^{\ast}$, let
$f_{x}:\\{0,1\\}^{p(|x|)}\times\\{0,1\\}\rightarrow\\{0,1\\}^{p(|x|)}\times\\{0,1\\}$
be the function $f_{x}(y,b)=(y,b\lor V(x,y))$. Since $V(x,y)$ halts in
$q(|x|)$ steps, $f_{x}$ is computable in time polynomial in $|x|$, and hence
has a circuit description $C_{x}$ that is polynomial size in $|x|$. This
provides an instance of the collision problem. Now, if $x\in L$, there exists
$y$ such that $V(x,y)=1$, so $f_{x}(y,0)=(y,1)=f_{x}(y,1)$, so
$C_{x}\in\texttt{Clique}(2)$; on the other hand, if $x\notin L$, then for all
$y$, $V(x,y)=0$, giving $f_{x}(y,b)=(y,b)$ is injective, so
$C_{x}\notin\texttt{Clique}(2)$. As such, we have the wanted Karp reduction. ∎

######  Proposition 3.5.

$\texttt{IS}(2)$ is NP-complete.

###### Proof.

First, we need that $\texttt{IS}(2)\in\textsf{NP}$. As for the clique problem,
the proof for a circuit $C$ can be taken to be the description of the
independent set $(x,y)$. In that case, the verifier simply needs to compute
$f_{C}(x)$ and $f_{C}(y)$ and check that they are different, something that it
can do efficiently in the length of the circuit.

Conversely, let $L\in\textsf{NP}$ be some language and let $V$ be a verifier
for $L$. Now for $x\in\\{0,1\\}^{\ast}$, consider the function
$f_{x}:\\{0,1\\}^{p(|x|)}\rightarrow\\{0,1\\}^{2}$ defined as
$f_{x}(y)=(y_{1}\land V(x,y),\lnot y_{1}\land V(x,y))$, where $y_{1}$ is the
first bit of $y$. If $x\notin L$, then $V(x,y)=0$ for all
$y\in\\{0,1\\}^{p(|x|)}$, so $f_{x}(y)=(0,0)$ giving that there is no
independent set. On the other hand, if there is $y$ such that $V(x,y)=1$,
$f_{x}(y)=(y_{1},\lnot y_{1})\neq(0,0)$. Then, for any
$z\in\\{0,1\\}^{p(|x|)}$ such that $z_{1}\neq y_{1}$, $f_{x}(y)\neq f_{x}(z)$.
So, $f_{x}$ has a $2$-independent set if and only if $x\in L$. Finally, it is
direct to see that, since the circuit of $y\mapsto V(x,y)$ is efficiently
describable in $|x|$, the circuit of $f_{x}$ is also. ∎

###  3.2 The probabilistic case

The results of the previous section generalise easily to probabilistic
functions. This is the setting where cliques and independent sets of functions
were originally considered, since probabilistic functions model noisy channels
[Sha56]. First, we formally introduce probabilistic functions.

######  Definition 3.6.

A _probabilistic function_ $f:X\rightarrow Y$ is a function that to each $x\in
X$ associates a random variable $f(x)$ on $Y$.

Intuitively, cliques of a noisy channel describe inputs that are likely to
become confused, and independent sets describe inputs that are unlikely to. We
can think of this in the context of zero-error capacity, wherein cliques are
those inputs that are always confused, and independent sets those that are
never confused. However, from a complexity-theoretic point of view, this is
too restrictive, since we are looking to extract a property of a probabilistic
object that should hold exactly. To remedy this, we define cliques/independent
sets with respect to an additional parameter that describes the probability of
confusion.

######  Definition 3.7.

Let $X,Y$ be sets, $k\in\mathbb{N}$, and $\alpha\in[0,1]$.

  * •

A probabilistic function $f:X\rightarrow Y$ has an _$(\alpha,k)$ -clique_ if
there exist distinct $x_{1},\ldots,x_{k}\in X$ such that for all $i\neq j$,

$\displaystyle\frac{2}{k(k-1)}\sum_{1\leq i<j\leq
k}\Pr\left[f(x_{i})=f(x_{j})\right]\geq\alpha,$ (7)

where the probability is with respect to independent evaluations of the
function, that is $\Pr\left[f(x_{i})=f(x_{j})\right]=\sum_{y\in
Y}\Pr\left[y=f(x_{i})\right]\Pr\left[y=f(x_{j})\right]$.

  * •

A probabilistic function $f:X\rightarrow Y$ has an _$(\alpha,k)$ -independent
set_ if there exist distinct $x_{1},\ldots,x_{k}\in X$ such that for all
$i\neq j$,

$\displaystyle\frac{2}{k(k-1)}\sum_{1\leq i<j\leq
k}\Pr\left[f(x_{i})=f(x_{j})\right]\leq 1-\alpha.$ (8)

Similarly to the deterministic case, we describe functions by circuits. Here,
however, to allow probabilistic functions, we will consider probabilistic
circuits, where there are some bits of random input.

######  Definition 3.8.

  * •

A _probabilistic circuit_ $C^{m}$ with $n$ inputs is a circuit $C$ on $n+m$
inputs such that on each evaluation of the circuit, the final $m$ wires are
given uniformly random bits as input.

  * •

A _probabilistic Turing machine_ $M^{p}$ with $k$ input tapes is a Turing
machine $M$ with $k+1$ input tapes along with a function
$p:\mathbb{N}\rightarrow\mathbb{N}$. On input $x$, $M^{p}(x)=M(x,r)$ where
$r\in\\{0,1\\}^{p(|x|)}$ is sampled uniformly at random.

Next, we can introduce the complexity problem for probabilistic cliques and
independent sets. Rather than a language, we present it as a promise problem,
which provides a probability gap between the yes and no instances.

######  Definition 3.9.

Let $k\in\mathbb{N}$ and let $c,s:\mathbb{N}\rightarrow(0,1)$. The
_probabilistic $k$-clique problem_ with completeness $c$ and soundness $s$ is
the promise problem $\texttt{pClique}(k)_{c,s}=(Y,N)$ with

$\displaystyle\begin{split}&Y=\vphantom{\text{probabilistic circuits
}C^{m}f_{C^{m}}\text{ has a
$(c(|C^{m}|),k)$-clique}}\left\\{{\text{probabilistic circuits
}C^{m}}\mid{f_{C^{m}}\text{ has a $(c(|C^{m}|),k)$-clique}}\right\\},\\\
&N=\vphantom{\text{probabilistic circuits }C^{m}f_{C^{m}}\text{ has no
$(s(|C^{m}|),k)$-clique}}\left\\{{\text{probabilistic circuits
}C^{m}}\mid{f_{C^{m}}\text{ has no
$(s(|C^{m}|),k)$-clique}}\right\\}.\end{split}$ (9)

The _probabilistic $k$-independent set problem_ with completeness $c$ and
soundness $s$ is the promise problem $\texttt{pIS}(k)_{c,s}=(Y,N)$ with

$\displaystyle\begin{split}&Y=\vphantom{\text{probabilistic circuits
}C^{m}f_{C^{m}}\text{ has a $(c(|C^{m}|),k)$-independent
set}}\left\\{{\text{probabilistic circuits }C^{m}}\mid{f_{C^{m}}\text{ has a
$(c(|C^{m}|),k)$-independent set}}\right\\},\\\
&N=\vphantom{\text{probabilistic circuits }C^{m}f_{C^{m}}\text{ has no
$(s(|C^{m}|),k)$-independent set}}\left\\{{\text{probabilistic circuits
}C^{m}}\mid{f_{C^{m}}\text{ has no $(s(|C^{m}|),k)$-independent
set}}\right\\}.\end{split}$ (10)

Analogously to the deterministic case, the probabilistic clique and
independent set problems are complete for the probabilistic analogue of NP,
which is MA. First, we provide a definition of this class.

######  Definition 3.10.

Let $c,s:\mathbb{N}\rightarrow(0,1)$. A promise problem
$Y,N\subseteq\\{0,1\\}^{\ast}$ is in $\textsf{MA}_{c,s}$ if there exist
polynomials $p,q,l:\mathbb{N}\rightarrow\mathbb{N}$ and a probabilistic Turing
machine $V^{l}$ with two input tapes and one output tape such that

  * •

For all $x,y\in\\{0,1\\}^{\ast}$, $V^{l}$ halts on input $(x,y)$ in $q(|x|)$
steps.

  * •

For all $x\in Y$, there exists $y\in\\{0,1\\}^{p(|x|)}$ such that
$\Pr\left[V^{l}(x,y)=1\right]\geq c(|x|)$.

  * •

For all $x\notin N$ and for all $y\in\\{0,1\\}^{\ast}$,
$\Pr\left[V^{l}(x,y)=1\right]\leq s(|x|)$.

Note that, as long as there exists $N\in\mathbb{N}$, a polynomial
$P:\mathbb{N}\rightarrow\mathbb{N}$, and a function
$E:\mathbb{N}\rightarrow\mathbb{N}$ no larger than exponential such that
$c(n)-s(n)\geq\frac{1}{P(n)}$ and $s(n),1-c(n)\geq\frac{1}{E(n)}$ for all
$n\geq N$, $\textsf{MA}_{c,s}=\textsf{MA}_{\frac{2}{3},\frac{1}{3}}$, so we
write this class simply MA.

Next, we show completeness of the $2$-clique and independent set problems. As
in the deterministic case, we refer to Appendix A for the reduction from
$k$-cliques and independent sets to this case.

######  Proposition 3.11.

There exist $c,s:\mathbb{N}\rightarrow(0,1)$ with constant gap such that
$\texttt{pClique}(2)_{c,s}$ is MA-complete.

###### Proof.

First, we see that $\texttt{pClique}(2)_{c,s}\in\textsf{MA}_{c,s}$ for all
$c,s$. An instance is simply a probabilistic circuit $C^{m}$, and the verifier
expects a proof that is a $(c,2)$-clique $(x,y)$. Then, the verifier computes
samples of $f_{C^{m}}(x)$ and $f_{C^{m}}(y)$, and accepts if and only if they
are equal. Then, if $C^{m}\in Y$,
$\Pr\left[f_{C^{m}}(x)=f_{C^{m}}(y)\right]\geq c(|C^{m}|)$, so
$\Pr\left[V_{l}(C^{m},(x,y))=1\right]\geq c(|C^{m}|)$. Conversely, if
$C^{m}\in N$, $\Pr\left[f_{C^{m}}(x)=f_{C^{m}}(y)\right]\leq s(|C^{m}|)$, so
$\Pr\left[V_{l}(C^{m},(x,y))=1\right]\leq s(|C^{m}|)$, completing the proof of
inclusion.

Let $L=(Y,N)\in\textsf{MA}_{\frac{2}{3},\frac{1}{3}}$. Then, there exists a
probabilistic polynomial time Turing machine $V^{l}$ such that for all $x\in
Y$, there exists $y$ such that $\Pr\left[V^{l}(x,y)=1\right]\geq\frac{2}{3}$;
and if $x\in N$, then for all $y$,
$\Pr\left[V^{l}(x,y)=1\right]\leq\frac{1}{3}$. For each $x$, Let $C_{x}^{l}$
be a probabilistic circuit describing the probabilistic function
$f_{C_{x}^{l}}(y,b)=(y,V^{l}(x,y)\lor b)$. If $x\in Y$, then $(y,0),(y,1)$
forms a $(2/3,2)$-clique, as

$\displaystyle\Pr\left[f_{C_{x}^{l}}(y,0)=f_{C_{x}^{l}}(y,1)\right]=\Pr\left[V^{l}(x,y)=1\right]=\frac{2}{3}.$
(11)

Conversely, if $x\in N$, then suppose there exists a $(s,2)$-clique
$(y,b),(y^{\prime},b^{\prime})$ for $s\geq 1/3$. First, since the probability
of acceptance is greater than $0$, we must have $y=y^{\prime}$. Also, since
$(y,b)\neq(y,b^{\prime})$, we can take without loss of generality $b=0$ and
$b^{\prime}=1$. Therefore,

$\displaystyle\frac{1}{3}<s\leq\Pr\left[f_{C_{x}^{l}}(y,0)=f_{C_{x}^{l}}(y,1)\right]=\Pr\left[V^{l}(x,y)=1\right],$
(12)

which is a contradiction. This provides that
$\texttt{qClique}_{\frac{2}{3},\frac{1}{3}}(2)$ is MA-hard. ∎

######  Proposition 3.12.

There exist $c,s:\mathbb{N}\rightarrow(0,1)$ with constant gap such that
$\texttt{pIS}_{c,s}(2)$ is a MA-complete.

###### Proof.

It is, as before, direct to see that
$\texttt{pIS}_{c,s}(2)\in\textsf{MA}_{c,s}$ for all $c,s$ with polynomial gap.
Given a circuit $C^{m}$ as instance and a proof $(x,y)$, the verifier simply
computes samples of $f_{C^{m}}(x)$ and $f_{C^{m}}(y)$ and accepts iff they are
not equal. If $(x,y)$ is a $(c,2)$-independent set of $f_{C^{m}}$, then
$\Pr\left[V^{l}(C^{m},(x,y))=1\right]=\Pr\left[f_{C^{m}}(x)\neq
f_{C^{m}}(y)\right]\geq c$; and conversely, if $f_{C^{m}}$ has no
$(s,2)$-independent set, $\Pr\left[V^{l}(C^{m},(x,y))=1\right]\leq s$.

Now, let $L=(Y,N)\in\textsf{MA}_{\frac{2}{3},\frac{1}{3}}$ with verification
circuit $V_{l}$, and define the probabilistic circuit $C_{x}^{l}$ with
function $f_{C_{x}^{l}}(y)=(y_{1}\land V^{l}(x,y),\lnot y_{1}\land
V^{l}(x,y))$. If $x\in Y$, then there exists $y$ such that
$\Pr\left[V^{l}(x,y)=1\right]\geq\frac{2}{3}$, giving that
$\Pr\left[f_{C_{x}^{l}}(y)=(y_{1},\lnot y_{1})\right]\geq\frac{2}{3}$. Taking
any $z$ such that $z_{1}\neq y_{1}$, the possible values of $f_{C_{x}^{l}}(z)$
are $(0,0)$ and $(z_{1},\lnot z_{1})$, so $f_{C_{x}^{l}}(z)\neq(y_{1},\lnot
y_{1})$. As such, $\Pr\left[f_{C_{x}^{l}}(y)\neq
f_{C_{x}^{l}}(z)\right]\geq\Pr\left[f_{C_{x}^{l}}(y)=(y_{1},\lnot
y_{1})\right]\Pr\left[f_{C_{x}^{l}}(z)\neq(y_{1},\lnot
y_{1})\right]\geq\frac{2}{3}$. On the other hand, if $x\in N$, for all $y$,
$\Pr\left[V^{l}(x,y)=1\right]\leq\frac{1}{3}$, so
$\Pr\left[f_{C_{x}^{l}}(y)=(0,0)\right]\geq\frac{2}{3}$. Thus, for all
$y,y^{\prime}$,
$\Pr\left[f_{C_{x}^{l}}(y)=f_{C_{x}^{l}}(y^{\prime})\right]\geq\Pr\left[f_{C_{x}^{l}}(y)=(0,0)\right]\Pr\left[f_{C_{x}^{l}}(y^{\prime})=(0,0)\right]\geq\frac{4}{9}$.
Thus, $\texttt{pIS}_{\tfrac{2}{3},\tfrac{5}{9}}$ is MA-hard. ∎

##  4 The Clique Problem for Quantum Channels

###  4.1 The quantum clique problem is QMA(2)-complete

Generalising cliques and independent sets to quantum channels poses two
definitional problems: what sets of states are taken form cliques/independent
sets, and when should states be considered to be confused? We discuss the case
of cliques, but independent sets follow the same logic. First, a clique of a
channel $\Phi$ should be a set of states $(\rho_{1},\ldots,\rho_{k})$ that are
orthogonal, since a classical clique is a set of distinct inputs
$(x_{1},\ldots,x_{k})$, corresponding to orthogonal classical states
$(\vphantom{x_{1}}\left\lvert\smash{x_{1}}\middle\rangle\\!\middle\langle\smash{x_{1}}\right\rvert,\ldots,\vphantom{x_{k}}\left\lvert\smash{x_{k}}\middle\rangle\\!\middle\langle\smash{x_{k}}\right\rvert)$.
Second, we express the probability that the outputs of the channel are
confused by means of the overlap
$\operatorname{Tr}\left[\Phi(\rho_{i})\Phi(\rho_{j})\right]$. In fact, if the
output states are classical
$\Phi(\rho_{i})=\sum_{x}\lambda_{x}\vphantom{x}\left\lvert\smash{x}\middle\rangle\\!\middle\langle\smash{x}\right\rvert$
and
$\Phi(\rho_{j})=\sum_{x}\mu_{x}\vphantom{x}\left\lvert\smash{x}\middle\rangle\\!\middle\langle\smash{x}\right\rvert$,
then

$\displaystyle\Pr\left[\Phi(\rho_{i})=\Phi(\rho_{j})\right]=\sum_{x}\Pr\left[\Phi(\rho_{i})=x\right]\Pr\left[\Phi(\rho_{j})=x\right]=\sum_{x}\lambda_{x}\mu_{x}=\operatorname{Tr}\left[\Phi(\rho_{i})\Phi(\rho_{j})\right].$
(13)

Also, the overlap can be efficiently sampled from the output states by means
of the swap test, unlike other measures of confusability such as the trace
distance. Formally, this leads to the following definition.

######  Definition 4.1.

Let $H,K$ be Hilbert spaces and let $k\in\mathbb{N}$.

  * •

A quantum channel $\Phi:\mathcal{L}(H)\rightarrow\mathcal{L}(K)$ has an
_$(\alpha,k)$ -clique_ if there exist orthogonal states
$\rho_{1},\ldots,\rho_{k}\in\mathcal{D}(H)$ such that

$\displaystyle\frac{2}{k(k-1)}\sum_{1\leq i<j\leq
k}\operatorname{Tr}\left[\Phi(\rho_{i})\Phi(\rho_{j})\right]\geq\alpha.$ (14)

  * •

A quantum channel $\Phi:\mathcal{L}(H)\rightarrow\mathcal{L}(K)$ has an
_$(\alpha,k)$ -independent set_ if there exist orthogonal states
$\rho_{1},\ldots,\rho_{k}\in\mathcal{D}(H)$ such that

$\displaystyle\frac{2}{k(k-1)}\sum_{1\leq i<j\leq
k}\operatorname{Tr}\left[\Phi(\rho_{i})\Phi(\rho_{j})\right]\leq 1-\alpha.$
(15)

As in the classical case, this gives rise to clique and independent set
promise problems, whose instances are circuit diagrams, this time for quantum
circuits.

######  Definition 4.2.

Let $\mathcal{C}$ be some collection of quantum circuits,
$c,s:\mathbb{N}\rightarrow[0,1]$, and $k\in\mathbb{N}$. The _quantum channel
$k$-clique problem_ on $\mathcal{C}$ with completeness $c$ and soundness $s$
is the promise problem $\texttt{qClique}(k,\mathcal{C})_{c,s}=(Y,N)$ with

$\displaystyle\begin{split}&Y=\vphantom{\text{quantum circuits
}CC\in\mathcal{C},\,\Phi_{C}\text{ has a
$(c(|C|),k)$-clique}}\left\\{{\text{quantum circuits
}C}\mid{C\in\mathcal{C},\,\Phi_{C}\text{ has a
$(c(|C|),k)$-clique}}\right\\},\\\ &N=\vphantom{\text{quantum circuits
}CC\in\mathcal{C},\,\Phi_{C}\text{ has no
$(s(|C|),k)$-clique}}\left\\{{\text{quantum circuits
}C}\mid{C\in\mathcal{C},\,\Phi_{C}\text{ has no
$(s(|C|),k)$-clique}}\right\\},\end{split}$ (16)

The _quantum channel $k$-independent set problem_ on $\mathcal{C}$ with
completeness $c$ and soundness $s$ is the promise problem
$\texttt{qIS}(k,\mathcal{C})_{c,s}=(Y,N)$ with

$\displaystyle\begin{split}&Y=\vphantom{\text{quantum circuits
}C\Phi_{C}\in\mathcal{C},\,\Phi_{C}\text{ has a $(c(|C|),k)$-independent
set}}\left\\{{\text{quantum circuits
}C}\mid{\Phi_{C}\in\mathcal{C},\,\Phi_{C}\text{ has a $(c(|C|),k)$-independent
set}}\right\\},\\\ &N=\vphantom{\text{quantum circuits
}C\Phi_{C}\in\mathcal{C},\,\Phi_{C}\text{ has no $(s(|C|),k)$-independent
set}}\left\\{{\text{quantum circuits
}C}\mid{\Phi_{C}\in\mathcal{C},\,\Phi_{C}\text{ has no
$(s(|C|),k)$-independent set}}\right\\},\end{split}$ (17)

Write $\texttt{qClique}(k)_{c,s}$ and $\texttt{qIS}(k)_{c,s}$ for the promise
problems with respect to all circuits.

The main results of this section are to show that all of the above problems
are in $\textsf{QMA}(2)$ for $c,s:\mathbb{N}\rightarrow(0,1)_{\exp}$ with
polynomial gap, and to show that the quantum $2$-clique problem for some class
of channels is in fact $\textsf{QMA}(2)$-hard. First, we recall the formal
definition of $\textsf{QMA}(2)$.

######  Definition 4.3.

Let $c,s:\mathbb{N}\rightarrow[0,1]$. A promise problem
$Y,N\subseteq\\{0,1\\}^{\ast}$ is in $\textsf{QMA}(2)_{c,s}$ if there exist
polynomials $p,q:\mathbb{N}\rightarrow\mathbb{N}$ and a Turing machine $V$
with one input tape and one output tape such that

  * •

For all $x\in\\{0,1\\}^{\ast}$, $V$ halts on input $x$ in $q(|x|)$ steps and
outputs the description of a quantum circuit from $2p(|x|)$ qubits to one
qubit.

  * •

For all $x\in Y$, there exist states $\rho,\sigma\in\mathcal{D}(Q^{\otimes
p(|x|)})$ such that
$\vphantom{1\Phi_{V(x)}(\rho\otimes\sigma)1}\left\langle\smash{1}\middle\rvert\smash{\Phi_{V(x)}(\rho\otimes\sigma)}\middle\rvert\smash{1}\right\rangle\geq
c(|x|)$.

  * •

For all $x\in N$ and $\rho,\sigma\in\mathcal{D}(Q^{\otimes p(|x|)})$,
$\vphantom{1\Phi_{V(x)}(\rho\otimes\sigma)1}\left\langle\smash{1}\middle\rvert\smash{\Phi_{V(x)}(\rho\otimes\sigma)}\middle\rvert\smash{1}\right\rangle\leq
s(|x|)$.

As for MA and QMA, we know that whenever
$c,s:\mathbb{N}\rightarrow(0,1)_{\exp}$ and have polynomial gap, then
$\textsf{QMA}(2)_{c,s}=\textsf{QMA}(2)_{\frac{2}{3},\frac{1}{3}}=:\textsf{QMA}(2)$.
Due to [HM13], we also know that $\textsf{QMA}(P)=\textsf{QMA}(2)$ for
$P:\mathbb{N}\rightarrow\mathbb{N}$ any polynomial number of provers.

######  Lemma 4.4.

Let $\mathcal{C}$ be any set of quantum circuits and let
$c,s:\mathbb{N}\rightarrow[0,1]$. Then, the problem
$\texttt{qClique}(2,\mathcal{C})_{c,s}\in\textsf{QMA}(2)_{c^{\prime},s^{\prime}}$,
where $c^{\prime}=\frac{1}{2}+(c-s)\frac{c}{8}$ and
$s^{\prime}=\frac{1}{2}+(c-s)\frac{c+s}{16}$

Thus, if $c,s:\mathbb{N}\rightarrow(0,1)_{\exp}$ have polynomial gap, then
$c^{\prime}-s^{\prime}=\frac{(c-s)^{2}}{16}\in\frac{1}{\mathrm{poly}}$, giving
that $\texttt{qClique}(2,\mathcal{C})_{c,s}\in\textsf{QMA}(2)$.

###### Proof.

Suppose the verifier receives a quantum circuit $C$. Let $\Phi=\Phi_{C}$. The
verifier expects to receive a proof
$\rho\otimes\sigma\in\mathcal{D}(Q^{\otimes 2\texttt{in}(C)})$, and then
effects the following procedure.

  1. 1.

The verifier samples a random bit $b$, which is $0$ with probability $p$ (to
be specified later).

  2. 2.

If $b=0$, the verifier runs the swap test on $\rho\otimes\sigma$. If it fails,
she accepts and outputs $1$, and if it passes she rejects and outputs $0$.

  3. 3.

If $b=1$, the verifier acts with $\Phi$ to get
$\Phi(\rho)\otimes\Phi(\sigma)$. Then, she runs the swap test on this state,
and outputs $1$ if it passes and $0$ if it fails.

Now, suppose $C\in Y$. Then, there exists a $(c(|C|),2)$-clique
$\rho,\sigma\in\mathcal{D}(Q^{\texttt{in}(C)})$, so the prover provides
$\rho\otimes\sigma$ to the verifier. If $b=0$, the probability of accepting is
$\frac{1}{2}-\frac{1}{2}\operatorname{Tr}(\rho\sigma)=\frac{1}{2}$, as $\rho$
and $\sigma$ are orthogonal; if $b=1$, since $\rho$ and $\sigma$ form a
clique, the probability of accepting is
$\frac{1}{2}+\frac{1}{2}\operatorname{Tr}\left[\Phi(\rho)\Phi(\sigma)\right]\geq\frac{1}{2}+\frac{c(|C|)}{2}$.
All together, the acceptance probability is at least
$c^{\prime}(|C|)=p\frac{1}{2}+(1-p)\left\lparen\frac{1}{2}+\frac{c(|C|)}{2}\right\rparen=\frac{1}{2}+(1-p)\frac{c(|C|)}{4}$.
On the other hand, suppose that $C\in N$. Then, for all orthogonal
$\rho,\sigma\in\mathcal{D}(Q^{\texttt{in}(C)})$,
$\operatorname{Tr}\left[\Phi(\rho)\Phi(\sigma)\right]\leq s(|C|)$. Without
loss of generality, we may assume that the verifier receives a pure state
proof
$\rho\otimes\sigma=\vphantom{\psi}\left\lvert\smash{\psi}\middle\rangle\\!\middle\langle\smash{\psi}\right\rvert\otimes\vphantom{\phi}\left\lvert\smash{\phi}\middle\rangle\\!\middle\langle\smash{\phi}\right\rvert$.
Then, if $b=0$, the probability of accepting is
$\frac{1}{2}-\frac{1}{2}|\vphantom{\psi\phi}\left\langle\smash{\psi}\middle|\smash{\phi}\right\rangle|^{2}$.
There exists a state $\lvert\phi^{\prime}\rangle$ orthogonal to
$\lvert\psi\rangle$ such that
$\lvert\phi\rangle=\alpha\lvert\psi\rangle+\beta\lvert\phi^{\prime}\rangle$
with
$|\alpha|^{2}=|\vphantom{\psi\phi}\left\langle\smash{\psi}\middle|\smash{\phi}\right\rangle|^{2}$.
Now, note that

$\displaystyle\|\vphantom{\phi}\left\lvert\smash{\phi}\middle\rangle\\!\middle\langle\smash{\phi}\right\rvert-\vphantom{\phi^{\prime}}\left\lvert\smash{\phi^{\prime}}\middle\rangle\\!\middle\langle\smash{\phi^{\prime}}\right\rvert\|_{\operatorname{Tr}}=\frac{1}{\sqrt{2}}\|\vphantom{\phi}\left\lvert\smash{\phi}\middle\rangle\\!\middle\langle\smash{\phi}\right\rvert-\vphantom{\phi^{\prime}}\left\lvert\smash{\phi^{\prime}}\middle\rangle\\!\middle\langle\smash{\phi^{\prime}}\right\rvert\|_{2}=\sqrt{\frac{1}{2}\left\lparen
2-2|\beta|^{2}\right\rparen}=|\vphantom{\phi\psi}\left\langle\smash{\phi}\middle|\smash{\psi}\right\rangle|.$
(18)

So, if $b=1$, the probability of accepting is

$\displaystyle\begin{split}\frac{1}{2}+\frac{1}{2}\operatorname{Tr}\left[\Phi(\vphantom{\psi}\left\lvert\smash{\psi}\middle\rangle\\!\middle\langle\smash{\psi}\right\rvert)\Phi(\vphantom{\phi}\left\lvert\smash{\phi}\middle\rangle\\!\middle\langle\smash{\phi}\right\rvert)\right]&\leq\frac{1}{2}+\frac{1}{2}\operatorname{Tr}\left[\Phi(\vphantom{\psi}\left\lvert\smash{\psi}\middle\rangle\\!\middle\langle\smash{\psi}\right\rvert)\Phi(\vphantom{\phi^{\prime}}\left\lvert\smash{\phi^{\prime}}\middle\rangle\\!\middle\langle\smash{\phi^{\prime}}\right\rvert)\right]+\frac{1}{2}\|\vphantom{\phi}\left\lvert\smash{\phi}\middle\rangle\\!\middle\langle\smash{\phi}\right\rvert-\vphantom{\phi^{\prime}}\left\lvert\smash{\phi^{\prime}}\middle\rangle\\!\middle\langle\smash{\phi^{\prime}}\right\rvert\|_{\operatorname{Tr}}\\\
&\leq\frac{1}{2}+\frac{s(|C|)}{2}+\frac{|\vphantom{\psi\phi}\left\langle\smash{\psi}\middle|\smash{\phi}\right\rangle|}{2}.\end{split}$
(19)

Thus, the total probability of accepting is at most

$\displaystyle\begin{split}s^{\prime}(|C|)&=\frac{1}{2}+(1-p)\frac{s(|C|)}{4}+\frac{1}{2}\left\lparen(1-p)|\vphantom{\psi\phi}\left\langle\smash{\psi}\middle|\smash{\phi}\right\rangle|-p|\vphantom{\psi\phi}\left\langle\smash{\psi}\middle|\smash{\phi}\right\rangle|^{2}\right\rparen\\\
&\leq\frac{1}{2}+(1-p)\frac{s(|C|)}{4}+\frac{(1-p)^{2}}{8p},\end{split}$ (20)

by maximising over
$|\vphantom{\phi\psi}\left\langle\smash{\phi}\middle|\smash{\psi}\right\rangle|\in\mathbb{R}$.
Now taking $p=1-\frac{c(|C|)-s(|C|)}{2}$, we get
$c^{\prime}=\frac{1}{2}+(c-s)\frac{c}{8}$ and
$s^{\prime}=\frac{1}{2}+(c-s)\frac{s}{8}+\frac{(c-s)^{2}}{16(2-(c-s))}\leq\frac{1}{2}+(c-s)\frac{s}{8}+\frac{(c-s)^{2}}{16}=\frac{1}{2}+(c-s)\frac{c+s}{16}$
∎

Next, we want to show that the quantum clique problem is in fact
$\textsf{QMA}(2)$-hard as well. In fact, we show the stronger property that a
subclass of all channels achieves this hardness. First, we introduce this
subclass.

######  Definition 4.5.

A quantum channel $\Phi:\mathcal{L}(H)\rightarrow\mathcal{L}(K)$ is
_entanglement-breaking_ if there exists a POVM
$\\{M_{i}\\}_{i}\subseteq\mathcal{P}(H)$ and a set of states
$\\{\sigma_{i}\\}_{i}\subseteq\mathcal{P}(K)$ such that
$\Phi(\rho)=\sum_{i}\operatorname{Tr}\left[M_{i}\rho\right]\sigma_{i}$.

Write $\mathcal{C}_{\mathrm{EB}}$ for the set of quantum circuits representing
entanglement-breaking channels. Write $\mathcal{C}_{\operatorname{Tr}}$ for
the collection of circuits that are partial traces on some of the qubits.

The name _entanglement-breaking_ for these maps arises since, if $\Phi$ is
entanglement-breaking, then the output state of $\mathbb{I}\otimes\Phi$ is
always separable. These are the only maps with the property. For more on
entanglement-breaking channels, see for example [HSR03, Wat18].

The circuits we we are interested in combine the above two restricted classes
of channels by means of a direct sum. At the level of channels, we mean to use
channels of the form $p\Phi_{\operatorname{Tr}}\oplus(1-p)\Phi_{\mathrm{EB}}$.
To do so, we need a way to form the direct sum of two quantum circuits.

######  Definition 4.6.

Let $C_{1}$ and $C_{2}$ be circuits with
$\texttt{in}(C_{1})=\texttt{in}(C_{2})$ and $p\in[0,1]$. Let $P_{i}$ be the
number of qubits prepared by $C_{i}$, and let
$T_{i}=\texttt{in}(C_{i})+P_{i}-\texttt{out}(C_{i})$ be the number of qubits
traced out by $C_{i}$. We define the _direct sum circuit_
$C_{1}\oplus_{p}C_{2}$ as the circuit constructed as follows

  1. (i)

The circuit prepares a qubit $R$ in the state $\sqrt{p}\lvert
0\rangle+\sqrt{1-p}\lvert 1\rangle$.

  2. (ii)

The circuit prepares
$\max\\{P_{1},P_{2}\\}+|\texttt{out}(C_{1})-\texttt{out}(C_{2})|$ qubits in
state $\lvert 0\rangle$.

  3. (iii)

The circuit acts with all the unitary gates of $C_{1}$ conditioned on $R$.
Then, it swaps, conditionally on $R$ as well, the qubits of $C_{1}$ that would
be traced out to the last positions.

  4. (iv)

The circuit flips $R$ with $X$ and acts in the same way as above for $C_{2}$
conditioned on $R$, before flipping back with $X$.

  5. (v)

The circuit traces out the last $\max\\{T_{1},T_{2}\\}$ qubits.

  6. (vi)

The circuit measures $R$ in the computational basis.

Note that the state $\sqrt{p}\lvert 0\rangle+\sqrt{1-p}\lvert 1\rangle$ cannot
be generated exactly by finitely many gates from the gate set for all but
countably many values of $p$. However, for any $p$, polynomially-many gates
(in the circuit sizes) can be used to construct an exponentially-good
approximation to the state, which we use to keep the circuits of reasonable
length. See also Fig. 2 for an example of the implementation of the above
definition.

$C_{1}=$$\vdots$$\vdots$$\vdots$$\vdots$$\cdots$$\texttt{in}(C_{1})\,{\Big{\\{}}$$P_{1}\,{\Big{\\{}}$${\Big{\\}}}\texttt{out}(C_{1})$${\Big{\\}}}T_{1}$$\lvert
0\rangle$$\lvert
0\rangle$$U_{1}$$U_{k}$${\operatorname{Tr}}$${\operatorname{Tr}}$

$C_{2}=$$\vdots$$\vdots$$\vdots$$\vdots$$\cdots$$\texttt{in}(C_{2})\,{\Big{\\{}}$$P_{2}\,{\Big{\\{}}$${\Big{\\}}}\texttt{out}(C_{2})$${\Big{\\}}}T_{2}$$\lvert
0\rangle$$\lvert
0\rangle$$V_{1}$$V_{l}$${\operatorname{Tr}}$${\operatorname{Tr}}$

$C_{1}\oplus_{p}C_{2}=$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$\cdots$$\cdots$$\lvert
0\rangle$$\lvert 0\rangle$$\lvert 0\rangle$$\lvert
0\rangle$$U_{p}$$U_{1}$$U_{k}$$X$$V_{1}$$V_{l}$$X$${\operatorname{Tr}}$${\operatorname{Tr}}$${\operatorname{Tr}}$

Figure 2: Representation of the construction of the circuit
$C_{1}\oplus_{p}C_{2}$ from the circuits $C_{1}$ and $C_{2}$ in canonical
form, with $\texttt{out}(C_{2})<\texttt{out}(C_{1})$. $U_{p}$ is a unitary
that implements the map $\lvert 0\rangle\mapsto\sqrt{p}\lvert
0\rangle+\sqrt{1-p}\lvert 1\rangle$ to good approximation.

Using the natural identification, for $m>n$, of $Q^{\otimes m}\oplus
Q^{\otimes n}$ with the subspace $\lvert 0\rangle\otimes Q^{\otimes m}+\lvert
1\rangle\otimes Q^{\otimes n}\otimes\lvert 0^{m-n}\rangle\subseteq
Q^{\otimes(m+1)}$, we see that
$\Phi_{C_{1}\oplus_{p}C_{2}}=p\Phi_{C_{1}}\oplus(1-p)\Phi_{C_{2}}$. Note also
that, by the above definition $|C_{1}\oplus_{p}C_{2}|=O(|C_{1}|+|C_{2}|)$.

######  Definition 4.7.

Let $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$ be collections of quantum
circuits. Write

$\displaystyle\mathcal{C}_{1}\oplus\mathcal{C}_{2}=\vphantom{C_{1}\oplus_{p}C_{2}C_{1}\in\mathcal{C}_{1},\,C_{2}\in\mathcal{C}_{2},\,p\in[0,1]}\left\\{{C_{1}\oplus_{p}C_{2}}\mid{C_{1}\in\mathcal{C}_{1},\,C_{2}\in\mathcal{C}_{2},\,p\in[0,1]}\right\\}.$
(21)

######  Theorem 4.8.

There exist $c,s:\mathbb{N}\rightarrow(0,1)_{\exp}$ with constant gap such
that the clique problem
$\texttt{qClique}(2)_{c,s}(2,\mathcal{C}_{\operatorname{Tr}}\oplus\mathcal{C}_{\operatorname{Tr}}\oplus\mathcal{C}_{\mathrm{EB}})$
is $\textsf{QMA}(2)$-hard.

To prove this theorem, we develop a technique to take a channel whose cliques
have certain properties with respect to a set of states, and combine it with
another channel in order to enlarge the set of states on which those
properties hold. This is inspired by self-testing techniques, such as Lemma
5.5 of [BMZ23].

######  Lemma 4.9.

Let $H$, $K$, and $K^{\prime}$ be Hilbert spaces, and
$A,B\subseteq\mathcal{D}(H)^{2}$ be sets of pairs of states. Suppose there
exist channels $\Phi:\mathcal{L}(H)\rightarrow\mathcal{L}(K)$ and
$\Psi:\mathcal{L}(H)\rightarrow\mathcal{L}(K^{\prime})$ with the properties
that

  * •

For $(\rho,\sigma)\in A$,
$\operatorname{Tr}\left[\Phi(\rho)\Phi(\sigma)\right]\leq p_{0}$, and if
$\operatorname{Tr}\left[\Phi(\rho)\Phi(\sigma)\right]\geq p_{0}-\varepsilon$
then there exist $(\rho_{0},\sigma_{0})\in B$ such that
$\|\rho-\rho_{0}\|_{\operatorname{Tr}}+\|\sigma-\sigma_{0}\|_{\operatorname{Tr}}\leq
C\varepsilon^{\alpha}$ for some constants $C,\alpha>0$ independent of
$(\rho,\sigma)$.

  * •

For all $(\rho,\sigma)\in B$,
$\operatorname{Tr}\left[\Psi(\rho)\Psi(\sigma)\right]\leq q_{0}$.

Then, for all $\eta>0$, there exists $p\in(0,1)$ such that the channel
$\Phi_{p}:\mathcal{L}(H)\rightarrow\mathcal{L}(K\oplus K^{\prime})$ defined
$\Phi_{p}=p\Phi\oplus(1-p)\Psi$ satisfies the property that, for all
$(\rho,\sigma)\in A$,

$\displaystyle\operatorname{Tr}\left[\Phi_{p}(\rho)\Phi_{p}(\sigma)\right]\leq
p^{2}p_{0}+(1-p)^{2}q_{0}+\eta.$ (22)

From the proof below, it may be verified that if $\eta=1/\mathrm{poly}$,
$C=\mathrm{poly}$, and $\alpha<1$ is constant, we get a probability
$p,1-p=1/\mathrm{poly}$. Further, the construction preserves polynomial gaps.
In fact, if we have the promise that
$\operatorname{Tr}\left[\Psi(\rho)\Psi(\sigma)\right]\leq s$ for all
$(\rho,\sigma)\in B$ or
$\operatorname{Tr}\left[\Psi(\rho)\Psi(\sigma)\right]\geq c$ for some
$(\rho,\sigma)\in A\cap B$ with $c-s=1/\mathrm{poly}$, then, we have that
either $\operatorname{Tr}\left[\Phi_{p}(\rho)\Phi_{p}(\sigma)\right]\leq
s^{\prime}$ for all $(\rho,\sigma)\in A$ or
$\operatorname{Tr}\left[\Phi_{p}(\rho)\Phi_{p}(\sigma)\right]\geq c^{\prime}$
for some $(\rho,\sigma)\in A\cap B$, where $c^{\prime}=p^{2}p_{0}+(1-p)^{2}c$
and $s^{\prime}=p^{2}p_{0}+(1-p)^{2}s+\eta$. So the gap becomes
$c^{\prime}-s^{\prime}=(1-p)^{2}(c-s)-\eta$. Since
$(1-p)^{2}=\frac{\eta^{1-\alpha}}{\mathrm{poly}}$, we may choose
$\eta=1/\mathrm{poly}$ small enough to preserve the polynomial gap.

###### Proof.

Let $(\rho,\sigma)\in A$. Then, there exists some $\varepsilon\geq 0$ such
that $\operatorname{Tr}\left[\Phi(\rho)\Phi(\sigma)\right]=p_{0}-\varepsilon$.
By hypothesis, there exist $(\rho_{0},\sigma_{0})\in B$ such that
$\|\rho-\rho_{0}\|_{\operatorname{Tr}}+\|\sigma-\sigma_{0}\|_{\operatorname{Tr}}\leq
C\varepsilon^{\alpha}$. Also, we have by hypothesis that
$\operatorname{Tr}\left[\Psi(\rho_{0})\Psi(\sigma_{0})\right]\leq q_{0}$.
Therefore,

$\displaystyle\begin{split}\operatorname{Tr}\left[\Psi(\rho)\Psi(\sigma)\right]&=\operatorname{Tr}\left[\Psi(\rho_{0})\Psi(\sigma_{0})\right]+\operatorname{Tr}\left[\Psi^{\dagger}(\Psi(\rho_{0}))(\sigma-\sigma_{0})\right]+\operatorname{Tr}\left[(\rho-\rho_{0})\Psi^{\dagger}(\Psi(\sigma))\right]\\\
&\leq\operatorname{Tr}\left[\Psi(\rho_{0})\Psi(\sigma_{0})\right]+\|\sigma-\sigma_{0}\|_{\operatorname{Tr}}+\|\rho-\rho_{0}\|_{\operatorname{Tr}}\\\
&\leq q_{0}+C\varepsilon^{\alpha}.\end{split}$ (23)

Using this bound,

$\displaystyle\begin{split}\operatorname{Tr}\left[\Phi_{p}(\rho)\Phi_{p}(\sigma)\right]&=p^{2}\operatorname{Tr}\left[\Phi(\rho)\Phi(\sigma)\right]+(1-p)^{2}\operatorname{Tr}\left[\Psi(\rho)\Psi(\sigma)\right]\\\
&\leq p^{2}(p_{0}-\varepsilon)+(1-p)^{2}(q_{0}+C\varepsilon^{\alpha})\\\
&=p^{2}p_{0}+(1-p)^{2}q_{0}+(1-p)^{2}C\varepsilon^{\alpha}-p^{2}\varepsilon\end{split}$
(24)

To finish the proof, it remains to show that $p$ may be chosen so that
$(1-p)^{2}C\varepsilon^{\alpha}-p^{2}\varepsilon\leq\eta$ for all
$\varepsilon\geq 0$. Without loss of generality, we may assume $\alpha<1$.
Then, by extremising the expression with respect to $\varepsilon$, we see that
it is maximised at $\varepsilon=\left\lparen
C\alpha\left\lparen\tfrac{1}{p}-1\right\rparen^{2}\right\rparen^{1/(1-\alpha)}$,
giving $(1-p)^{2}C\varepsilon^{\alpha}-p^{2}\varepsilon\leq
C^{1/(1-\alpha)}\left\lparen\alpha^{\alpha/(1-\alpha)}-\alpha^{1/(1-\alpha)}\right\rparen
p^{2}\left\lparen\tfrac{1}{p}-1\right\rparen^{2/(1-\alpha)}$. Thus,
rearranging the wanted expression
$C^{1/(1-\alpha)}\left\lparen\alpha^{\alpha/(1-\alpha)}-\alpha^{1/(1-\alpha)}\right\rparen
p^{2}\left\lparen\tfrac{1}{p}-1\right\rparen^{2/(1-\alpha)}\leq\eta$ gives

$\displaystyle\frac{1-p}{p^{\alpha}}\leq\left\lparen\frac{\eta}{C^{1/(1-\alpha)}\left\lparen\alpha^{\alpha/(1-\alpha)}-\alpha^{1/(1-\alpha)}\right\rparen}\right\rparen^{(1-\alpha)/2}.$
(25)

Since $\frac{1-p}{p}\geq\frac{1-p}{p^{\alpha}}$, we may take
$\frac{1-p}{p}=\left\lparen\frac{\eta}{C^{1/(1-\alpha)}\left\lparen\alpha^{\alpha/(1-\alpha)}-\alpha^{1/(1-\alpha)}\right\rparen}\right\rparen^{(1-\alpha)/2}$,
or

$\displaystyle
p=\frac{1}{1+\left\lparen\frac{\eta}{C^{1/(1-\alpha)}\left\lparen\alpha^{\alpha/(1-\alpha)}-\alpha^{1/(1-\alpha)}\right\rparen}\right\rparen^{(1-\alpha)/2}}$
(26)

to get the result. ∎

######  Lemma 4.10.

Let $H$ and $K$ be Hilbert spaces and pure states
$\rho=\vphantom{\psi}\left\lvert\smash{\psi}\middle\rangle\\!\middle\langle\smash{\psi}\right\rvert,\sigma=\vphantom{\phi}\left\lvert\smash{\phi}\middle\rangle\\!\middle\langle\smash{\phi}\right\rvert\in\mathcal{D}(H^{\otimes
k}\otimes K)$. Suppose that there exist $\varepsilon_{i}>0$ such that
$\operatorname{Tr}(\rho_{i}\sigma_{i})\geq 1-\varepsilon_{i}$ for all $i$,
where $\rho_{i}$ and $\sigma_{i}$ are the marginals on the $i$-th copy of $H$.
Write $\varepsilon=\frac{1}{k}\sum_{i}\varepsilon_{i}$. Then, there exist
separable states
$\tilde{\rho}=\vphantom{\psi_{1}}\left\lvert\smash{\psi_{1}}\middle\rangle\\!\middle\langle\smash{\psi_{1}}\right\rvert\otimes\cdots\otimes\vphantom{\psi_{k}}\left\lvert\smash{\psi_{k}}\middle\rangle\\!\middle\langle\smash{\psi_{k}}\right\rvert\otimes\vphantom{\psi^{\prime}}\left\lvert\smash{\psi^{\prime}}\middle\rangle\\!\middle\langle\smash{\psi^{\prime}}\right\rvert,\tilde{\sigma}=\vphantom{\phi_{1}}\left\lvert\smash{\phi_{1}}\middle\rangle\\!\middle\langle\smash{\phi_{1}}\right\rvert\otimes\cdots\otimes\vphantom{\phi_{k}}\left\lvert\smash{\phi_{k}}\middle\rangle\\!\middle\langle\smash{\phi_{k}}\right\rvert\otimes\vphantom{\phi^{\prime}}\left\lvert\smash{\phi^{\prime}}\middle\rangle\\!\middle\langle\smash{\phi^{\prime}}\right\rvert\in\mathcal{D}(H^{\otimes
k}\otimes K)$ such that $\|\rho-\tilde{\rho}\|_{2}\leq 2\sqrt{k\varepsilon}$,
$\|\sigma-\tilde{\sigma}\|_{2}\leq 2\sqrt{k\varepsilon}$, and
$\|\operatorname{Tr}_{K}\tilde{\rho}-\operatorname{Tr}_{K}\tilde{\sigma}\|_{2}\leq
6\sqrt{k\varepsilon}$.

###### Proof.

Fix some $i=1,\ldots,k$. Then, $\operatorname{Tr}(\rho_{i}\sigma_{i})\geq
1-\varepsilon_{i}$ implies that
$\sqrt{\operatorname{Tr}\rho_{i}^{2}}\sqrt{\operatorname{Tr}\sigma_{i}^{2}}\geq
1-\varepsilon_{i}$. In particular, since $\operatorname{Tr}\sigma_{i}^{2}\leq
1$, $\operatorname{Tr}\rho_{i}^{2}\geq(1-\varepsilon_{i})^{2}$. Now, Let
$\rho_{i}=\sum_{j}\lambda_{i,j}\vphantom{\psi_{j}^{(i)}}\left\lvert\smash{\psi_{j}^{(i)}}\middle\rangle\\!\middle\langle\smash{\psi_{j}^{(i)}}\right\rvert$
be s spectral decomposition of $\rho_{i}$, with
$\lambda_{i,1}\geq\lambda_{i,2}\geq\ldots$. First, the above implies that
$\sum_{j}\lambda_{i,j}^{2}\geq(1-\varepsilon_{i})^{2}$ and the fact that
$\rho_{i}$ is a state means that $\sum_{j}\lambda_{i,j}=1$. As such,

$\displaystyle\lambda_{i,1}=\sum_{j}\lambda_{i,1}\lambda_{i,j}\geq\sum_{j}\lambda_{i,j}^{2}\geq(1-\varepsilon_{i})^{2}.$
(27)

Thus,
$\vphantom{\psi_{1}^{(i)}\rho_{i}\psi_{1}^{(i)}}\left\langle\smash{\psi_{1}^{(i)}}\middle\rvert\smash{\rho_{i}}\middle\rvert\smash{\psi_{1}^{(i)}}\right\rangle=\lambda_{i,1}\geq(1-\varepsilon_{i})^{2}$,
or equivalently,
$\|(\mathbb{I}\otimes\langle\psi^{(i)}_{1}\rvert\otimes\mathbb{I})\lvert\psi\rangle\|\geq
1-\varepsilon_{i}$. Now, we can expand $\lvert\psi\rangle$ in the basis
$\lvert\psi^{(1)}_{j_{1}}\rangle\otimes\cdots\otimes\lvert\psi^{(k)}_{j_{k}}\rangle$
of $H^{\otimes k}$ as
$\lvert\psi\rangle=\sum_{j_{1},\ldots,j_{k}}\lvert\psi_{j_{1}}\rangle\otimes\cdots\otimes\lvert\psi_{j_{k}}\rangle\otimes\lvert\psi_{j_{1}\ldots
j_{k}}\rangle$, where the $\lvert\psi_{j_{1}\ldots j_{k}}\rangle\in K$ are
subnormalised states such that
$\sum_{j_{1},\ldots,j_{k}}\vphantom{\psi_{j_{1}\ldots
j_{k}}}\left\langle\smash{\psi_{j_{1}\ldots
j_{k}}}\middle|\smash{\psi_{j_{1}\ldots j_{k}}}\right\rangle=1$. For all $i$,
we have that

$\displaystyle\sum_{j_{i}\neq 1}\vphantom{\psi_{j_{1}\ldots
j_{k}}}\left\langle\smash{\psi_{j_{1}\ldots
j_{k}}}\middle|\smash{\psi_{j_{1}\ldots
j_{k}}}\right\rangle=1-\|(\mathbb{I}\otimes\langle\psi^{(i)}_{1}\rvert\otimes\mathbb{I})\lvert\psi\rangle\|^{2}\leq
1-(1-\varepsilon_{i})^{2}\geq 2\varepsilon_{i}.$ (28)

Therefore, by a union bound,

$\displaystyle\begin{split}\vphantom{\psi_{1\ldots
1}}\left\langle\smash{\psi_{1\ldots 1}}\middle|\smash{\psi_{1\ldots
1}}\right\rangle&=1-\sum_{j_{1}\neq 1\lor\ldots\lor j_{k}\neq
1}\vphantom{\psi_{j_{1}\ldots j_{k}}}\left\langle\smash{\psi_{j_{1}\ldots
j_{k}}}\middle|\smash{\psi_{j_{1}\ldots j_{k}}}\right\rangle\geq
1-\sum_{i}\sum_{j_{i}\neq 1}\vphantom{\psi_{j_{1}\ldots
j_{k}}}\left\langle\smash{\psi_{j_{1}\ldots
j_{k}}}\middle|\smash{\psi_{j_{1}\ldots j_{k}}}\right\rangle\\\ &\geq
1-2k\varepsilon.\end{split}$ (29)

Let $\lvert\psi_{i}\rangle=\lvert\psi^{(i)}_{1}\rangle$ and
$\lvert\psi^{\prime}\rangle=\frac{\lvert\psi_{1\ldots
1}\rangle}{\|\lvert\psi_{1\ldots 1}\rangle\|}$. Then,

$\displaystyle\begin{split}\|\rho-\tilde{\rho}\|_{2}^{2}&=2-2\|(\langle\psi_{1}\rvert\otimes\cdots\otimes\langle\psi_{k}\rvert\otimes\langle\psi^{\prime}\rvert)\lvert\psi\rangle\|^{2}=2-2|\vphantom{\psi^{\prime}\psi_{1\ldots
1}}\left\langle\smash{\psi^{\prime}}\middle|\smash{\psi_{1\ldots
1}}\right\rangle|^{2}\\\ &=2-2\vphantom{\psi_{1\ldots
1}}\left\langle\smash{\psi_{1\ldots 1}}\middle|\smash{\psi_{1\ldots
1}}\right\rangle\leq 4k\varepsilon.\end{split}$ (30)

By symmetry, we also get separable $\tilde{\sigma}$ such that
$\|\sigma-\tilde{\sigma}\|_{2}\leq 2\sqrt{k\varepsilon}$.

For the last part of the proof, note that

$\displaystyle\begin{split}\|\operatorname{Tr}_{K}\tilde{\rho}-\operatorname{Tr}_{K}\tilde{\sigma}\|_{2}^{2}&=\|\vphantom{\psi_{1}}\left\lvert\smash{\psi_{1}}\middle\rangle\\!\middle\langle\smash{\psi_{1}}\right\rvert\otimes\cdots\otimes\vphantom{\psi_{k}}\left\lvert\smash{\psi_{k}}\middle\rangle\\!\middle\langle\smash{\psi_{k}}\right\rvert-\vphantom{\phi_{1}}\left\lvert\smash{\phi_{1}}\middle\rangle\\!\middle\langle\smash{\phi_{1}}\right\rvert\otimes\cdots\otimes\vphantom{\phi_{k}}\left\lvert\smash{\phi_{k}}\middle\rangle\\!\middle\langle\smash{\phi_{k}}\right\rvert\|_{2}^{2}\\\
&=2-2\lvert\vphantom{\psi_{1}\phi_{1}}\left\langle\smash{\psi_{1}}\middle|\smash{\phi_{1}}\right\rangle\rvert^{2}\cdots\lvert\vphantom{\psi_{k}\phi_{k}}\left\langle\smash{\psi_{k}}\middle|\smash{\phi_{k}}\right\rangle\rvert^{2}\\\
&=2-2(1-\tfrac{1}{2}\|\vphantom{\psi_{1}}\left\lvert\smash{\psi_{1}}\middle\rangle\\!\middle\langle\smash{\psi_{1}}\right\rvert-\vphantom{\phi_{1}}\left\lvert\smash{\phi_{1}}\middle\rangle\\!\middle\langle\smash{\phi_{1}}\right\rvert\|_{2}^{2})\cdots(1-\tfrac{1}{2}\|\vphantom{\psi_{k}}\left\lvert\smash{\psi_{k}}\middle\rangle\\!\middle\langle\smash{\psi_{k}}\right\rvert-\vphantom{\phi_{k}}\left\lvert\smash{\phi_{k}}\middle\rangle\\!\middle\langle\smash{\phi_{k}}\right\rvert\|_{2}^{2})\\\
&\leq\sum_{i}\|\vphantom{\psi_{i}}\left\lvert\smash{\psi_{i}}\middle\rangle\\!\middle\langle\smash{\psi_{i}}\right\rvert-\vphantom{\phi_{i}}\left\lvert\smash{\phi_{i}}\middle\rangle\\!\middle\langle\smash{\phi_{i}}\right\rvert\|_{2}^{2}.\end{split}$
(31)

Next,
$\|\rho_{i}-\vphantom{\psi_{i}}\left\lvert\smash{\psi_{i}}\middle\rangle\\!\middle\langle\smash{\psi_{i}}\right\rvert\|_{2}^{2}=\operatorname{Tr}(\rho_{i}^{2})+1-2\vphantom{\psi_{i}\rho_{i}\psi_{i}}\left\langle\smash{\psi_{i}}\middle\rvert\smash{\rho_{i}}\middle\rvert\smash{\psi_{i}}\right\rangle\leq
2-2(1-\varepsilon_{i})^{2}\leq 4\varepsilon_{i}$ and similarly for $\sigma$,
so

$\displaystyle\begin{split}\|\vphantom{\psi_{i}}\left\lvert\smash{\psi_{i}}\middle\rangle\\!\middle\langle\smash{\psi_{i}}\right\rvert-\vphantom{\phi_{i}}\left\lvert\smash{\phi_{i}}\middle\rangle\\!\middle\langle\smash{\phi_{i}}\right\rvert\|_{2}&\leq\|\vphantom{\psi_{i}}\left\lvert\smash{\psi_{i}}\middle\rangle\\!\middle\langle\smash{\psi_{i}}\right\rvert-\rho_{i}\|_{2}+\|\rho_{i}-\sigma_{i}\|_{2}+\|\sigma_{i}-\vphantom{\phi_{i}}\left\lvert\smash{\phi_{i}}\middle\rangle\\!\middle\langle\smash{\phi_{i}}\right\rvert\|_{2}\\\
&\leq
2\sqrt{\varepsilon_{i}}+\sqrt{2\varepsilon_{i}}+2\sqrt{\varepsilon_{i}}=(4+\sqrt{2})\sqrt{\varepsilon_{i}}.\end{split}$
(32)

Together, this gives
$\|\operatorname{Tr}_{K}\tilde{\rho}-\operatorname{Tr}_{K}\tilde{\sigma}\|_{2}^{2}\leq
k(4+\sqrt{2})^{2}\varepsilon$, as wanted ∎

######  Lemma 4.11.

Let $H$ and $K$ be Hilbert spaces and $k\in\mathbb{N}$, and define the channel
$\Phi_{1}:\mathcal{L}(H^{\otimes k}\otimes
K)\rightarrow\mathcal{L}(H\otimes\mathbb{C}^{[k]})$ as

$\displaystyle\Phi_{1}(\rho)=\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{i=1}^{k}\rho_{i}\otimes\vphantom{i}\left\lvert\smash{i}\middle\rangle\\!\middle\langle\smash{i}\right\rvert,$
(33)

where $\rho_{i}$ is the marginal of $\rho$ on the $i$-th copy of $H$. Let
$\rho=\vphantom{\psi}\left\lvert\smash{\psi}\middle\rangle\\!\middle\langle\smash{\psi}\right\rvert,\sigma=\vphantom{\phi}\left\lvert\smash{\phi}\middle\rangle\\!\middle\langle\smash{\phi}\right\rvert\in\mathcal{D}(H^{\otimes
k}\otimes H^{\prime})$ be orthogonal pure states. Then,
$\operatorname{Tr}\left[\Phi_{1}(\rho)\Phi_{1}(\sigma)\right]\leq\frac{1}{k}$
and if
$\operatorname{Tr}\left[\Phi_{1}(\rho)\Phi_{1}(\sigma)\right]\geq\frac{1}{k}-\varepsilon$,
then there exist states $\lvert\psi_{1}\rangle,\ldots,\lvert\psi_{k}\rangle\in
H$ and orthogonal states $\lvert\alpha\rangle,\lvert\beta\rangle\in K$ such
that

$\displaystyle\|\rho-\tilde{\rho}\|_{\operatorname{Tr}}+\|\sigma-\tilde{\sigma}\|_{\operatorname{Tr}}\leq
10k\varepsilon^{1/4},$ (34)

where
$\tilde{\rho}=\vphantom{\psi_{1}}\left\lvert\smash{\psi_{1}}\middle\rangle\\!\middle\langle\smash{\psi_{1}}\right\rvert\otimes\cdots\otimes\vphantom{\psi_{k}}\left\lvert\smash{\psi_{k}}\middle\rangle\\!\middle\langle\smash{\psi_{k}}\right\rvert\otimes\vphantom{\alpha}\left\lvert\smash{\alpha}\middle\rangle\\!\middle\langle\smash{\alpha}\right\rvert$
and
$\tilde{\sigma}=\vphantom{\psi_{1}}\left\lvert\smash{\psi_{1}}\middle\rangle\\!\middle\langle\smash{\psi_{1}}\right\rvert\otimes\cdots\otimes\vphantom{\psi_{k}}\left\lvert\smash{\psi_{k}}\middle\rangle\\!\middle\langle\smash{\psi_{k}}\right\rvert\otimes\vphantom{\beta}\left\lvert\smash{\beta}\middle\rangle\\!\middle\langle\smash{\beta}\right\rvert$.

###### Proof.

First,
$\operatorname{Tr}\left[\Phi_{1}(\rho)\Phi_{1}(\sigma)\right]=\frac{1}{k}\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{i}\operatorname{Tr}(\rho_{i}\sigma_{i})\leq\frac{1}{k}\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{i}1=\frac{1}{k}$.
Now, suppose that
$\operatorname{Tr}\left[\Phi_{1}(\rho)\Phi_{1}(\sigma)\right]\geq\frac{1}{k}-\varepsilon$.
Let $\varepsilon_{i}\in[0,1]$ such that
$\operatorname{Tr}(\rho_{i}\sigma_{i})=1-\varepsilon_{i}$; we know that
$k\varepsilon\geq\operatorname*{\mathchoice{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\displaystyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-10.00012pt}{\leavevmode\resizebox{18.9231pt}{10.00012pt}{\hbox{\raisebox{0.0pt}{$\textstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-7.00009pt}{\leavevmode\resizebox{13.24615pt}{7.00009pt}{\hbox{\raisebox{0.0pt}{$\scriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}{\raisebox{-5.00006pt}{\leavevmode\resizebox{9.46153pt}{5.00006pt}{\hbox{\raisebox{0.0pt}{$\scriptscriptstyle\vphantom{\mathbb{E}}\text{\raisebox{0.3pt}{\scalebox{0.9}{$\mathbb{E}$}}}$}}}}}}_{i}\varepsilon_{i}$.
Then, due to Lemma 4.10, there exist separable states
$\rho^{\prime}=\vphantom{\psi_{1}}\left\lvert\smash{\psi_{1}}\middle\rangle\\!\middle\langle\smash{\psi_{1}}\right\rvert\otimes\cdots\otimes\vphantom{\psi_{k}}\left\lvert\smash{\psi_{k}}\middle\rangle\\!\middle\langle\smash{\psi_{k}}\right\rvert\otimes\vphantom{\alpha}\left\lvert\smash{\alpha}\middle\rangle\\!\middle\langle\smash{\alpha}\right\rvert,\sigma^{\prime}=\vphantom{\phi_{1}}\left\lvert\smash{\phi_{1}}\middle\rangle\\!\middle\langle\smash{\phi_{1}}\right\rvert\otimes\cdots\otimes\vphantom{\phi_{k}}\left\lvert\smash{\phi_{k}}\middle\rangle\\!\middle\langle\smash{\phi_{k}}\right\rvert\otimes\vphantom{\phi^{\prime}}\left\lvert\smash{\phi^{\prime}}\middle\rangle\\!\middle\langle\smash{\phi^{\prime}}\right\rvert\in\mathcal{D}(H^{\otimes
k}\otimes H^{\prime})$ such that $\|\rho-\rho^{\prime}\|_{2}\leq
2k\sqrt{\varepsilon}$, $\|\sigma-\sigma^{\prime}\|_{2}\leq
2k\sqrt{\varepsilon}$, and
$\|\operatorname{Tr}_{H^{\prime}}\rho^{\prime}-\operatorname{Tr}_{H^{\prime}}\sigma^{\prime}\|_{2}\leq
6k\sqrt{\varepsilon}$. Since all these are pure states, this implies that
$\|\rho-\rho^{\prime}\|_{\operatorname{Tr}}\leq\sqrt{2}k\sqrt{\varepsilon}$,
$\|\sigma-\sigma^{\prime}\|_{\operatorname{Tr}}\leq\sqrt{2}k\sqrt{\varepsilon}$,
and
$\|\operatorname{Tr}_{H^{\prime}}\rho^{\prime}-\operatorname{Tr}_{H^{\prime}}\sigma^{\prime}\|_{\operatorname{Tr}}\leq
3\sqrt{2}k\sqrt{\varepsilon}$. Let
$\sigma^{\prime\prime}=\operatorname{Tr}_{H^{\prime}}(\rho^{\prime})\otimes\vphantom{\phi^{\prime}}\left\lvert\smash{\phi^{\prime}}\middle\rangle\\!\middle\langle\smash{\phi^{\prime}}\right\rvert$;
then

$\displaystyle\|\sigma-\sigma^{\prime\prime}\|_{\operatorname{Tr}}\leq\|\sigma-\sigma^{\prime}\|_{\operatorname{Tr}}+\|\operatorname{Tr}_{H^{\prime}}\sigma^{\prime}-\operatorname{Tr}_{H^{\prime}}\rho^{\prime}\|_{\operatorname{Tr}}\leq
4\sqrt{2}k\sqrt{\varepsilon}.$ (35)

Now, the inner product

$\displaystyle\begin{split}\left\lvert\vphantom{\alpha\phi^{\prime}}\left\langle\smash{\alpha}\middle|\smash{\phi^{\prime}}\right\rangle\right\rvert^{2}=\operatorname{Tr}\left[\rho^{\prime}\sigma^{\prime\prime}\right]\leq\operatorname{Tr}\left[\rho\sigma\right]+\|\rho-\rho^{\prime}\|_{\operatorname{Tr}}+\|\sigma-\sigma^{\prime\prime}\|_{\operatorname{Tr}}\leq
5\sqrt{2}k\sqrt{\varepsilon}.\end{split}$ (36)

There exists a state $\lvert\beta\rangle\in H^{\prime}$ orthogonal to
$\lvert\alpha\rangle$ such that
$\lvert\phi^{\prime}\rangle=a\lvert\alpha\rangle+b\lvert\beta\rangle$ for some
$|\alpha|^{2}\leq 5\sqrt{2}k\sqrt{\varepsilon}$. Due to this

$\displaystyle\|\vphantom{\phi^{\prime}}\left\lvert\smash{\phi^{\prime}}\middle\rangle\\!\middle\langle\smash{\phi^{\prime}}\right\rvert-\vphantom{\beta}\left\lvert\smash{\beta}\middle\rangle\\!\middle\langle\smash{\beta}\right\rvert\|_{\operatorname{Tr}}=\frac{1}{\sqrt{2}}\|\vphantom{\phi^{\prime}}\left\lvert\smash{\phi^{\prime}}\middle\rangle\\!\middle\langle\smash{\phi^{\prime}}\right\rvert-\vphantom{\beta}\left\lvert\smash{\beta}\middle\rangle\\!\middle\langle\smash{\beta}\right\rvert\|_{2}=\sqrt{\frac{1}{2}\left\lparen
2-2|b|^{2}\right\rparen}=|a|\leq\sqrt{5\sqrt{2}k\sqrt{\varepsilon}}.$ (37)

Let $\tilde{\rho}=\rho^{\prime}$ and
$\tilde{\sigma}=\operatorname{Tr}_{H^{\prime}}\sigma^{\prime\prime}\otimes\vphantom{\beta}\left\lvert\smash{\beta}\middle\rangle\\!\middle\langle\smash{\beta}\right\rvert$.
Then we get the wanted result

$\displaystyle\begin{split}\|\rho-\tilde{\rho}\|_{\operatorname{Tr}}+\|\sigma-\tilde{\sigma}\|_{\operatorname{Tr}}&\leq\|\rho-\rho^{\prime}\|_{\operatorname{Tr}}+\|\sigma-\sigma^{\prime\prime}\|_{\operatorname{Tr}}+\|\vphantom{\alpha}\left\lvert\smash{\alpha}\middle\rangle\\!\middle\langle\smash{\alpha}\right\rvert+\vphantom{\beta}\left\lvert\smash{\beta}\middle\rangle\\!\middle\langle\smash{\beta}\right\rvert\|_{\operatorname{Tr}}\\\
&\leq 5\sqrt{2}k\sqrt{\varepsilon}+\sqrt{5\sqrt{2}k\sqrt{\varepsilon}}\leq
10k\varepsilon^{1/4}.\end{split}$ (38)

∎

######  Lemma 4.12.

Let $H$ be a Hilbert space. For any channel
$\Phi:\mathcal{L}(H)\rightarrow\mathcal{L}(Q)$ define
$\Psi:\mathcal{L}(H\otimes Q)\rightarrow\mathcal{L}(Q_{\perp})$ as

$\displaystyle\Psi(\rho)=\vphantom{0(\Phi\otimes\operatorname{Tr})(\rho)0}\left\langle\smash{0}\middle\rvert\smash{(\Phi\otimes\operatorname{Tr})(\rho)}\middle\rvert\smash{0}\right\rangle\mu_{Q}+\vphantom{1(\Phi\otimes\operatorname{Tr})(\rho)1}\left\langle\smash{1}\middle\rvert\smash{(\Phi\otimes\operatorname{Tr})(\rho)}\middle\rvert\smash{1}\right\rangle\vphantom{\perp}\left\lvert\smash{\perp}\middle\rangle\\!\middle\langle\smash{\perp}\right\rvert$
(39)

Then, for any $\rho\in\mathcal{D}(H)$ and
$\sigma,\sigma^{\prime}\in\mathcal{D}(Q)$, if
$\vphantom{1\Phi(\rho)1}\left\langle\smash{1}\middle\rvert\smash{\Phi(\rho)}\middle\rvert\smash{1}\right\rangle\geq\frac{3}{4}$,
then
$\operatorname{Tr}\left[\Psi(\rho\otimes\sigma)\Psi(\rho\otimes\sigma^{\prime})\right]\geq\frac{19}{32}$;
and if
$\vphantom{1\Phi(\rho)1}\left\langle\smash{1}\middle\rvert\smash{\Phi(\rho)}\middle\rvert\smash{1}\right\rangle\leq\frac{2}{3}$,
then
$\operatorname{Tr}\left[\Psi(\rho\otimes\sigma)\Psi(\rho\otimes\sigma^{\prime})\right]\leq\frac{1}{2}$

###### Proof.

We can directly compute this. First,
$\Psi(\rho\otimes\sigma)=\vphantom{0\Phi(\rho)0}\left\langle\smash{0}\middle\rvert\smash{\Phi(\rho)}\middle\rvert\smash{0}\right\rangle\mu_{Q}+\vphantom{1\Phi(\rho)1}\left\langle\smash{1}\middle\rvert\smash{\Phi(\rho)}\middle\rvert\smash{1}\right\rangle\vphantom{\perp}\left\lvert\smash{\perp}\middle\rangle\\!\middle\langle\smash{\perp}\right\rvert$.
Therefore,

$\displaystyle\begin{split}\operatorname{Tr}\left[\Psi(\rho\otimes\sigma)\Psi(\rho\otimes\sigma^{\prime})\right]&=\vphantom{0\Phi(\rho)0}\left\langle\smash{0}\middle\rvert\smash{\Phi(\rho)}\middle\rvert\smash{0}\right\rangle^{2}\operatorname{Tr}(\mu_{Q}^{2})+\vphantom{1\Phi(\rho)1}\left\langle\smash{1}\middle\rvert\smash{\Phi(\rho)}\middle\rvert\smash{1}\right\rangle^{2}|\vphantom{\perp}\left\langle\smash{\perp}\middle|\smash{\perp}\right\rangle|^{2}\\\
&=\frac{1}{2}\left\lparen
1-\vphantom{1\Phi(\rho)1}\left\langle\smash{1}\middle\rvert\smash{\Phi(\rho)}\middle\rvert\smash{1}\right\rangle\right\rparen^{2}+\vphantom{1\Phi(\rho)1}\left\langle\smash{1}\middle\rvert\smash{\Phi(\rho)}\middle\rvert\smash{1}\right\rangle^{2}.\end{split}$
(40)

The inequalities follow from this expression. ∎

###### Proof of Theorem 4.8.

Let $L=(Y,N)\in\textsf{QMA}(2)_{\frac{3}{4},\frac{1}{4}}$, and let $x\in Y\cup
N$. Then, there exists a polynomial-time computable channel
$\Phi_{x}:\mathcal{L}(Q^{\otimes 2p(|x|)})\rightarrow\mathcal{L}(Q)$ such
that, if $x\in Y$, there exist $\rho,\sigma\in\mathcal{D}(Q^{\otimes p(|x|)})$
such that
$\vphantom{1\Phi_{x}(\rho\otimes\sigma)1}\left\langle\smash{1}\middle\rvert\smash{\Phi_{x}(\rho\otimes\sigma)}\middle\rvert\smash{1}\right\rangle\geq\frac{3}{4}$;
and if $x\in N$, for all $\rho,\sigma\in\mathcal{D}(Q^{\otimes p(|x|)})$,
$\vphantom{1\Phi_{x}(\rho\otimes\sigma)1}\left\langle\smash{1}\middle\rvert\smash{\Phi_{x}(\rho\otimes\sigma)}\middle\rvert\smash{1}\right\rangle\leq\frac{1}{4}$.
Construct the channel
$\Psi_{x}:\mathcal{L}(Q^{\otimes(2p(|x|)+1)})\rightarrow\mathcal{L}(Q_{\perp})$
from $\Phi_{x}$ as in Lemma 4.12. Also, write $H=Q^{\otimes p(|x|)}$ and
$K=Q$, and let $\Phi_{1}:\mathcal{L}(H\otimes H\otimes
K)\rightarrow\mathcal{L}(H\otimes\mathbb{C}^{[2]})$ as in Lemma 4.11. For
$p\in(0,1)$, consider the channel $\Phi_{p}=p\Phi_{1}\oplus(1-p)\Psi_{x}$.
Using the construction of Definition 4.6 and the fact that $\Phi_{x}$ admits a
circuit polynomial in the size of the instance $x$, we see that this channel
admits a circuit representation polynomial in $|x|$.

First, suppose that $x\in Y$. Then, I claim that there exist
$\rho,\sigma\in\mathcal{D}(Q^{\otimes(2p(|x|)+1)})$ such that
$\operatorname{Tr}\left[\Phi_{p}(\rho)\Phi_{p}(\sigma)\right]\geq\frac{p^{2}}{2}+\frac{19(1-p)^{2}}{32}$.
Since $x\in Y$, there exists a separable state on which $\Phi_{x}$ accepts
with high probability; we may, without loss of generality, assume that this
state is pure so of the form $\lvert\psi\rangle\otimes\lvert\phi\rangle$. Let
$\rho=\vphantom{\psi}\left\lvert\smash{\psi}\middle\rangle\\!\middle\langle\smash{\psi}\right\rvert\otimes\vphantom{\phi}\left\lvert\smash{\phi}\middle\rangle\\!\middle\langle\smash{\phi}\right\rvert\otimes\vphantom{0}\left\lvert\smash{0}\middle\rangle\\!\middle\langle\smash{0}\right\rvert$
and
$\sigma=\vphantom{\psi}\left\lvert\smash{\psi}\middle\rangle\\!\middle\langle\smash{\psi}\right\rvert\otimes\vphantom{\phi}\left\lvert\smash{\phi}\middle\rangle\\!\middle\langle\smash{\phi}\right\rvert\otimes\vphantom{1}\left\lvert\smash{1}\middle\rangle\\!\middle\langle\smash{1}\right\rvert$.
Then,
$\Phi_{p}(\rho)=\frac{p}{2}\left\lparen\vphantom{\psi}\left\lvert\smash{\psi}\middle\rangle\\!\middle\langle\smash{\psi}\right\rvert\otimes\vphantom{1}\left\lvert\smash{1}\middle\rangle\\!\middle\langle\smash{1}\right\rvert+\vphantom{\phi}\left\lvert\smash{\phi}\middle\rangle\\!\middle\langle\smash{\phi}\right\rvert\otimes\vphantom{2}\left\lvert\smash{2}\middle\rangle\\!\middle\langle\smash{2}\right\rvert\right\rparen\oplus(1-p)\Psi_{x}(\rho)$,
and similarly for $\sigma$, giving that

$\displaystyle\begin{split}\operatorname{Tr}\left[\Phi_{p}(\rho)\Phi_{p}(\sigma)\right]&=\frac{p^{2}}{4}\left\lparen|\vphantom{\psi}\left\langle\smash{\psi}\middle|\smash{\psi}\right\rangle|^{2}+|\vphantom{\phi}\left\langle\smash{\phi}\middle|\smash{\phi}\right\rangle|^{2}\right\rparen+(1-p)^{2}\operatorname{Tr}\left[\Psi_{x}(\rho)\Psi_{x}(\sigma)\right]\\\
&\geq\frac{p^{2}}{2}+(1-p)^{2}\frac{19}{32}.\end{split}$ (41)

Now, suppose that $x\in N$. We use Lemma 4.9 to show that for all $\eta>0$,
there exists $p\in(0,1)$ such that
$\operatorname{Tr}\left[\Phi_{p}(\rho)\Phi_{p}(\sigma)\right]\leq\frac{p^{2}}{2}+\frac{(1-p)^{2}}{2}+\eta$.
We need that $\Phi_{1}$ and $\Psi_{x}$ satisfy the conditions of lemma. Let

$\displaystyle
A=\vphantom{(\vphantom{\psi}\left\lvert\smash{\psi}\middle\rangle\\!\middle\langle\smash{\psi}\right\rvert,\vphantom{\phi}\left\lvert\smash{\phi}\middle\rangle\\!\middle\langle\smash{\phi}\right\rvert)\vphantom{\psi}\left\lvert\smash{\psi}\middle\rangle\\!\middle\langle\smash{\psi}\right\rvert,\vphantom{\phi}\left\lvert\smash{\phi}\middle\rangle\\!\middle\langle\smash{\phi}\right\rvert\in\mathcal{D}(Q^{\otimes(2p(|x|)+1)}),\;\vphantom{\psi\phi}\left\langle\smash{\psi}\middle|\smash{\phi}\right\rangle=0}\left\\{{(\vphantom{\psi}\left\lvert\smash{\psi}\middle\rangle\\!\middle\langle\smash{\psi}\right\rvert,\vphantom{\phi}\left\lvert\smash{\phi}\middle\rangle\\!\middle\langle\smash{\phi}\right\rvert)}\mid{\vphantom{\psi}\left\lvert\smash{\psi}\middle\rangle\\!\middle\langle\smash{\psi}\right\rvert,\vphantom{\phi}\left\lvert\smash{\phi}\middle\rangle\\!\middle\langle\smash{\phi}\right\rvert\in\mathcal{D}(Q^{\otimes(2p(|x|)+1)}),\;\vphantom{\psi\phi}\left\langle\smash{\psi}\middle|\smash{\phi}\right\rangle=0}\right\\},$
(42)
$\displaystyle\begin{split}&B=\big{\\{}(\vphantom{\psi_{1}}\left\lvert\smash{\psi_{1}}\middle\rangle\\!\middle\langle\smash{\psi_{1}}\right\rvert\otimes\vphantom{\psi_{2}}\left\lvert\smash{\psi_{2}}\middle\rangle\\!\middle\langle\smash{\psi_{2}}\right\rvert\otimes\vphantom{\alpha}\left\lvert\smash{\alpha}\middle\rangle\\!\middle\langle\smash{\alpha}\right\rvert,\vphantom{\psi_{1}}\left\lvert\smash{\psi_{1}}\middle\rangle\\!\middle\langle\smash{\psi_{1}}\right\rvert\otimes\vphantom{\psi_{2}}\left\lvert\smash{\psi_{2}}\middle\rangle\\!\middle\langle\smash{\psi_{2}}\right\rvert\otimes\vphantom{\beta}\left\lvert\smash{\beta}\middle\rangle\\!\middle\langle\smash{\beta}\right\rvert)\\\
&\qquad\qquad\big{|}\vphantom{\psi_{1}}\left\lvert\smash{\psi_{1}}\middle\rangle\\!\middle\langle\smash{\psi_{1}}\right\rvert,\vphantom{\psi_{2}}\left\lvert\smash{\psi_{2}}\middle\rangle\\!\middle\langle\smash{\psi_{2}}\right\rvert\in\mathcal{D}(Q^{\otimes
p(|x|)}),\;\vphantom{\alpha}\left\lvert\smash{\alpha}\middle\rangle\\!\middle\langle\smash{\alpha}\right\rvert,\vphantom{\beta}\left\lvert\smash{\beta}\middle\rangle\\!\middle\langle\smash{\beta}\right\rvert\in\mathcal{D}(Q),\;\vphantom{\alpha\beta}\left\langle\smash{\alpha}\middle|\smash{\beta}\right\rangle=0\big{\\}}.\end{split}$
(43)

First, due to Lemma 4.11, for all $(\rho,\sigma)\in A$,
$\operatorname{Tr}\left[\Phi_{1}(\rho)\Phi_{1}(\sigma)\right]\leq\frac{1}{2}$,
and if
$\operatorname{Tr}\left[\Phi_{1}(\rho)\Phi_{1}(\sigma)\right]\geq\frac{1}{2}-\varepsilon$,
then there exists $(\tilde{\rho},\tilde{\sigma})\in B$ such that
$\|\rho-\tilde{\rho}\|_{\operatorname{Tr}}+\|\sigma-\tilde{\sigma}\|_{\operatorname{Tr}}\leq
20\varepsilon^{1/4}$. Also, due to Lemma 4.12, we know that for all
$(\tilde{\rho},\tilde{\sigma})\in B$,
$\operatorname{Tr}\left[\Psi_{x}(\tilde{\rho})\Psi_{x}(\tilde{\sigma})\right]\leq\frac{1}{2}$.
As such, Lemma 4.9 gives that for all $\eta>0$, there exists $p\in(0,1)$ such
that
$\operatorname{Tr}\left[\Phi_{p}(\rho)\Phi_{p}(\sigma)\right]\leq\frac{p^{2}}{2}+\frac{(1-p)^{2}}{2}+\eta$
for all $(\rho,\sigma)\in A$. As this bound holds for all pure states, it
holds for all states. This gives that
$\texttt{qClique}(2)_{p^{2}/2+19(1-p)^{2}/32,p^{2}/2+(1-p)^{2}/2+\eta}$ is
$\textsf{QMA}(2)_{c,s}$-hard. Finally, as remarked near Lemma 4.9, $\eta$ may
be chosen so that $p^{2}/2+19(1-p)^{2}/32$ and $p^{2}/2+(1-p)^{2}/2+\eta$ have
constant gap $3(1-p)^{2}/32-\eta$, as the coefficient from Lemma 4.11 is
constant in the case $k=2$. ∎

###  4.2 Reducing QMA(k) to QMA(2) using quantum cliques

In this section, we give an alternate proof of
$\textsf{QMA}(k)=\textsf{QMA}(2)$ (for $k$ polynomial) than the original proof
of Harrow and Montanaro [HM13]. To do this, we show that
$\texttt{qClique}(2)_{c,s}$ with some polynomial gap is hard for
$\textsf{QMA}(k)$, independently of the result of [HM13]. The proof is similar
to the case $k=2$ that we showed in Theorem 4.8. This implies the wanted
equality via Lemma 4.4, which showed that
$\texttt{qClique}(2)_{c,s}\in\textsf{QMA}(2)$ for all $c,s$ with polynomial
gap.

######  Theorem 4.13.

For all $c,s:\mathbb{N}\rightarrow(0,1)_{\exp}$ with polynomial gap and
$k:\mathbb{N}\rightarrow\mathbb{N}$ polynomial, there exist
$c^{\prime},s^{\prime}:\mathbb{N}\rightarrow(0,1)_{\exp}$ with polynomial gap
such that $\texttt{qClique}(2)_{c^{\prime},s^{\prime}}$ is
$\textsf{QMA}(k)_{c,s}$-hard.

###### Proof.

The proof proceeds analogously to Theorem 4.8. Let
$L=(Y,N)\in\textsf{QMA}(k)_{c,s}$. By increasing the number of proofs, it is
possible to amplify the probability gap. In particular, there exists a
polynomial $k^{\prime}:\mathbb{N}\rightarrow\mathbb{N}$ such that
$L\in\textsf{QMA}(k^{\prime})_{\frac{3}{4},\frac{1}{4}}$. Let $x\in Y\cup N$
be an instance of $L$. Now, let $\Phi_{x}:\mathcal{L}(Q^{\otimes
k^{\prime}p(|x|)})\rightarrow\mathcal{L}(Q)$ be the channel of the
$\textsf{QMA}(k^{\prime})_{\frac{3}{4},\frac{1}{4}}$ verifier for $L$, from
which we can follow the construction of Lemma 4.12 to get
$\Psi_{x}:\mathcal{L}(Q^{\otimes
k^{\prime}p(|x|)+1})\rightarrow\mathcal{L}(Q_{\perp})$. Also, let
$H=Q^{\otimes p(|x|)}$, $K=Q$, and $\Phi_{1}:\mathcal{L}(H^{\otimes
k^{\prime}}\otimes
K)\rightarrow\mathcal{L}(H\otimes\mathbb{C}^{[k^{\prime}]})$ be the channel
from Lemma 4.11 with $k=k^{\prime}$. Let
$\Phi_{p}=p\Phi_{1}\oplus(1-p)\Psi_{x}$; we consider the cliques of this