# Quantum Merlin-Arthur and proofs without relative phase

Roozbeh Bassirian<EMAIL_ADDRESS>University of Chicago  Bill Fefferman
<EMAIL_ADDRESS>University of Chicago  Kunal Marwaha<EMAIL_ADDRESS>University of Chicago

###### Abstract

We study a variant of ${\mathsf{QMA}}$ where quantum proofs have no relative
phase (i.e. non-negative amplitudes, up to a global phase). If only
completeness is modified, this class is equal to ${\mathsf{QMA}}$ [GKS14]; but
if both completeness and soundness are modified, the class (named
${\mathsf{QMA}}^{+}$ by Jeronimo and Wu [JW23]) can be much more powerful. We
show that ${\mathsf{QMA}}^{+}$ with some constant gap is equal to
${\mathsf{NEXP}}$, yet ${\mathsf{QMA}}^{+}$ with some _other_ constant gap is
equal to ${\mathsf{QMA}}$. One interpretation is that Merlin’s ability to
“deceive” originates from _relative phase_ at least as much as from
_entanglement_ , since ${\mathsf{QMA}}(2)\subseteq{\mathsf{NEXP}}$.

##  1 Introduction

The strangeness of quantum states has at least two fundamental sources:
_entanglement_ , the source of “spooky action at a distance”; and _relative
phase_ , which allows for destructive interference. We use complexity theory
to probe these sources of strangeness. Extending the main result of [JW23], we
find that ${\mathsf{QMA}}^{+}$ (${\mathsf{QMA}}$ where quantum proofs have no
relative phase) is as powerful as ${\mathsf{NEXP}}$.

A ${\mathsf{QMA}}_{c,s}$ protocol is a verification task for a quantum
computer (termed “Arthur”) when interacting with a dishonest but all-powerful
machine (termed “Merlin”). If the statement is true (“completeness”), Merlin
sends a quantum state (“proof”) that truthfully convinces Arthur. If the
statement is false (“soundness”), Merlin will send any quantum state possible
to deceive Arthur. A valid protocol distinguishes these cases, succeeding with
probability at least $c$ in completeness and at most $s<c$ in soundness.
Canonically, ${\mathsf{QMA}}$ is the class of all valid
${\mathsf{QMA}}_{2/3,1/3}$ protocols.

One could potentially reduce the power of ${\mathsf{QMA}}$ by restricting
Merlin’s proof in completeness. Surprisingly, many restrictions of this type
_do not reduce the power of the class_. For example, this is true even if the
quantum state is a _subset state_ (with no relative phase nor relative non-
zero amplitude) [GKS14]. The reason behind this is _promise gap amplification_
: there exist techniques to increase the gap $c-s$ to $1-2^{-p(n)}$ for any
polynomial $p(n)$. As a result, a subset state with polynomially small overlap
with the best completeness proof succeeds. This argument generalizes to any
set of states that form an $\epsilon_{n}$-covering of all $n$-qubit quantum
states, where $\epsilon_{n}$ is at least inverse polynomial in $n$.

By contrast, restricting Merlin’s proof in soundness seems to increase the
power of this complexity class, since this reduces Merlin’s ability to
“deceive”. For example, if Merlin must send a quantum proof _without relative
phase_ , Arthur can ask about its _sparsity_ ($\ell_{1}$ norm). When a state
has no relative phase, a low overlap with $\ket{+}^{\otimes n}$ actually
implies it is sparse, as opposed to a state with destructively interfering
phases (i.e. any other Hadamard basis vector).

One popular variant of ${\mathsf{QMA}}$ restricts Merlin’s _entanglement_ over
a fixed barrier; it is named ${\mathsf{QMA}}(2)$ (as if there are two
unentangled Merlins each sending a quantum proof [KMY03]). This complexity
class may seem more powerful than ${\mathsf{QMA}}$, but despite much study
[BT10, ABD+08, CD10, Per12, HM13, GSS+18, SY22], little is known except the
trivial bounds
${\mathsf{QMA}}\subseteq{\mathsf{QMA}}(2)\subseteq{\mathsf{NEXP}}$.

What happens if one restricts both _entanglement_ and _relative phase_? [JW23]
define ${\mathsf{QMA}}^{+}_{c,s}$ and ${\mathsf{QMA}}^{+}(2)_{c,s}$, where
quantum proofs are required to have no relative phase (non-negative
amplitudes, up to a global phase) _in both cases_.111As noted before,
restricting the state in completeness may not change the complexity class, but
restricting the state in soundness can make the class more powerful, since the
latter limits Merlin’s adversarial strategies. Surprisingly, [JW23] show the
existence of constants $1>c>s>0$ such that
${\mathsf{QMA}}^{+}(2)_{c,s}={\mathsf{NEXP}}$, crucially including a protocol
to estimate the _sparsity_ of a quantum proof. This hints perhaps at a route
to prove ${\mathsf{QMA}}(2)={\mathsf{NEXP}}$, since there are other constants
$1>c^{\prime}>s^{\prime}>0$ where
${\mathsf{QMA}}^{+}(2)_{c^{\prime},s^{\prime}}={\mathsf{QMA}}(2)$.222This is
because every state has constant overlap with some state without relative
phase. See also Proposition 29.

In this work, we show that restricting _relative phase_ alone gives the power
of ${\mathsf{NEXP}}$; i.e., there exist constants $1>c>s>0$ where
${\mathsf{QMA}}^{+}_{c,s}={\mathsf{NEXP}}$. Note that assuming
${\mathsf{EXP}}\neq{\mathsf{NEXP}}$, this implies ${\mathsf{QMA}}^{+}$ cannot
be amplified, since as before, there are other constants
$1>c^{\prime}>s^{\prime}>0$ where
${\mathsf{QMA}}^{+}_{c^{\prime},s^{\prime}}={\mathsf{QMA}}\subseteq{\mathsf{EXP}}$.
As a result, techniques to prove
${\mathsf{QMA}}(2)={\mathsf{QMA}}^{+}(2)={\mathsf{NEXP}}$ must crucially use
the unentanglement promise inherent in ${\mathsf{QMA}}(2)$. See Figure 1 and
Figure 2 for a pictorial description.

Figure 1: Relationship between ${\mathsf{QMA}}^{+}$ and ${\mathsf{QMA}}(2)$.
[JW23] show that for some constants $1>c>s>0$,
${\mathsf{QMA}}^{+}(2)_{c,s}={\mathsf{NEXP}}$. We show that the same is true
for ${\mathsf{QMA}}^{+}$. Restricting relative phase does not restrict
entanglement across a fixed barrier: for example, consider the GHZ state
$\ket{0}^{\otimes n}+\ket{1}^{\otimes n}$, or more generally states where the
Schmidt vectors have no relative phase.

###  1.1 Techniques

Our primary technical contribution is to show a ${\mathsf{QMA}}^{+}$ protocol
for a ${\mathsf{NEXP}}$-complete problem. This directly extends the work of
Jeronimo and Wu [JW23], who show a ${\mathsf{QMA}}^{+}(2)$ protocol for a
${\mathsf{NEXP}}$-complete problem. As in [JW23], we study constraint
satisfaction problems (CSPs) with _constant_ gap. In $(1,\delta)$-GapCSP,
either _all_ constraints can be satisfied, or at most a $\delta$ fraction of
constraints can be satisfied. These problems are known to be
${\mathsf{NP}}$-hard or ${\mathsf{NEXP}}$-hard (depending on the problem size)
using the PCP theorem [AS92, ALM+98, Har04].

Before proving ${\mathsf{QMA}}^{+}$ with some constant gap equals
${\mathsf{NEXP}}$, we prove ${\mathsf{QMA}}^{+}_{\log}$ (with some other
constant gap) equals ${\mathsf{NP}}$. This choice (also taken by [JW23]) is
pedagogical: it allows us to explain the protocol without worrying about input
encoding size, since ${\mathsf{QMA}}^{+}$ has a polynomial amount of space and
verifier runtime. Here, we consider $(1,\delta)$-GapCSP with polynomially many
variables and clauses; the quantum proof must certify that there is a
satisfying assignment to all clauses.

The ${\mathsf{QMA}}^{+}_{\log}(2)$ protocol of [JW23] crucially relies on an
estimate of _sparsity_ ($\ell_{1}$ norm) of a quantum state without relative
phase. The overlap of a $m$-qubit quantum state without relative phase
$\ket{\psi}$ with $\ket{+}^{\otimes m}$ is exactly the value
$2^{-m/2}\cdot\|\ket{\psi}\|_{1}$. With multiple quantum proofs
$\ket{\psi_{1}}\otimes\dots\ket{\psi_{k}}$, one can _estimate_ the sparsity by
repeating this “sparsity test” on each $\ket{\psi_{i}}$, and using a swap test
to ensure that all $\ket{\psi_{i}}$ are approximately equal. Interestingly, no
other part of their protocol requires the _no relative phase_
assumption.333Formally, [JW23] studies states with non-negative amplitudes.
Recall that the set of these states, up to global phase, are equivalent to
states with _no relative phase_.

In ${\mathsf{QMA}}^{+}_{\log}$, we have a single quantum proof, so we cannot
use this test to estimate sparsity. Instead, we design a similar test that
directly enforces a _rigidity_ property of the proof.444Note that we use the
intuition of _rigidity_ in a more general context, where Arthur’s tests, not a
non-local game, enforce states of a certain form. The required form is
$\frac{1}{\sqrt{R}}\sum_{j\in[R]}\ket{j}\ket{\vec{v}_{j}}$, where the second
register is constant-sized. Using a “sparsity test” over the second register,
Arthur ensures that the second register has one $\vec{v}_{j}$ per $j$; but
using the _complement_ of a “sparsity test” over the whole proof, Arthur
ensures the overall state maximizes $\ell_{1}$ norm. States of the required
form are optimal for this combination of tests. We make use of the _no
relative phase_ property in Lemmas 6 and 8.

Now we can describe our protocol. For each constraint $j\in R$, Arthur asks
for the values $\vec{v}_{j}$ associated with the variables involved in
constraint $j$. The protocol either enforces _rigidity_ of the quantum proof,
or verifies the _constraints_ of the CSP. Note that we need two kinds of
constraint checks: the values $\vec{v}_{j}$ must _satisfy_ constraint $j$, and
the value of a variable must be _consistent_ across the constraints it
participates in. For states with the rigidity property, checking
_satisfiability_ is simple: measure in the computational basis and verify the
measured constraint $j,\vec{v}_{j}$. States with the rigidity property will
succeed with probability equal to the satisfying fraction of the CSP
assignment.

Checking _consistency_ is done using a technique called “regularization” from
the PCP literature [Din07]; for each constraint $j$, we verify that each
variable participating in $j$ has the same value in exactly $d$ other
constraints for some constant $d$, in a way that the edges form an _expander
graph_. The expansion property guarantees that cheating on this test is as
damaging as cheating on the satisfiability test. Jeronimo and Wu [JW23] use a
swap test to implement these new checks, but this requires multiple quantum
proofs. We show how to use a Hadamard test (which requires only one quantum
proof) to achieve the same result, building on ideas from previous work
[BFM22]. Since there exists a $\delta$ such that $(1,\delta)$-GapCSP is
${\mathsf{NP}}$-hard, this completes the proof of
${\mathsf{NP}}\subseteq{\mathsf{QMA}}^{+}_{\log}$ with some constant gap.

When scaling up to ${\mathsf{QMA}}^{+}$, one must be careful of how to
succinctly encode the input of a ${\mathsf{NEXP}}$-complete problem. The PCP
theorem allows us to choose $(1,\delta)$-GapCSP that is _succinct_ , but we
need stronger properties. Following the adjustments taken in [JW23], we choose
a PCP system for ${\mathsf{NEXP}}$ that is both _doubly explicit_ and
_strongly uniform_. _Doubly explicit_ means that one can efficiently compute
the variables participating in a given constraint _and_ the constraints a
given variable participates in; using this, we can implement the consistency
checks in polynomial time. _Strongly uniform_ means that the number of
constraints a variable participates in is efficiently computable, and one of a
fixed number of possibilities; using this, we only need to build a fixed
number of expander graphs during regularization. Recent work also shows how to
construct exponentially-sized expander graphs in polynomial time [Lub09,
Alo21]. Once we are through these input encoding difficulties, our protocol is
identical to that for ${\mathsf{NP}}$.

Fundamentally, the _no relative phase_ property allows Arthur to verify a
number of constraints exponential in the number of qubits. Attempts to do this
for ${\mathsf{QMA}}(2)$ gave too small a promise gap [BT10, Per12, GNN12], too
many provers [ABD+08, CD10, CF11], or too much space or time [HM13, NZ23].
Jeronimo and Wu [JW23] show that ${\mathsf{QMA}}^{+}(2)$ circumvents this
difficulty: using _no relative phase_ and _unentanglement_ , Arthur enforces
the _sparsity_ of a quantum proof to solve a ${\mathsf{NEXP}}$-complete
problem. At the center of our work is the insight that _no relative phase_ is
enough for Arthur to require constant-sized answers to exponentially many
questions, solving a ${\mathsf{NEXP}}$-complete problem with a single
polynomial-size quantum proof.

###  1.2 Related work

#### The complexity class ${\mathsf{QMA}}(2)$

The complexity class ${\mathsf{QMA}}(2)$ is known to have promise gap
amplification, and to be equal to ${\mathsf{QMA}}(k)$ for any $k$ at most
polynomial in $n$ [HM13]. It is not obvious how to test for entanglement; even
determining whether a polynomially-sized vector is entangled is
${\mathsf{NP}}$-hard [Gha09]. If there exist efficient approximate
“disentanglers” that can create any separable state, then
${\mathsf{QMA}}={\mathsf{QMA}}(2)$; see [ABD+08] for some progress. [GSS+18]
describe quantum variants of the polynomial hierarchy and connect their
properties to bounds on ${\mathsf{QMA}}(2)$. It is not even known whether
there is a _quantum_ oracle separating ${\mathsf{QMA}}$ and
${\mathsf{QMA}}(2)$ [Aar21].

Figure 2: Plot of ${\mathsf{QMA}}^{+}_{c,s}$ for increasing $\frac{c}{s}$. By
our main result, there exist constants $c,s$ where $1<\frac{c}{s}<4$ and
${\mathsf{QMA}}^{+}_{c,s}={\mathsf{NEXP}}$, but by Corollary 30,
${\mathsf{QMA}}^{+}_{c,s}={\mathsf{QMA}}$ when $\frac{c}{s}>4$. Gap
amplification of ${\mathsf{QMA}}^{+}$ would imply
${\mathsf{QMA}}={\mathsf{NEXP}}$.

#### PCPs and expander graphs

Probabilistically checkable proofs (PCPs) show hardness for CSPs with a
constant gap [AS92, ALM+98, Har04]. Dinur [Din07] proves the PCP theorem using
a _regularization_ step, which adds new constraints associated with the edges
of a _regular_ expander graph. _Polynomial-time_ regularization for
${\mathsf{NEXP}}$ requires an efficient description of exponentially-sized
expander graphs. Recent advances in expander graph constructions [Lub09,
Alo21] allow for this type of regularization, first used in [JW23].

#### Quantum states and relative phase

Up to a global phase, states with non-negative amplitudes are equivalent to
states with no relative phase. [JW23] propose the class ${\mathsf{QMA}}^{+}$
and ${\mathsf{QMA}}^{+}(2)$, and show ${\mathsf{QMA}}^{+}(2)={\mathsf{NEXP}}$.
Note that by contrast, ${\mathsf{QMA}}$ restricted to states with _real_
amplitudes is equal to ${\mathsf{QMA}}$ [McK13]. Relative phase was recently
proposed as a quantum resource [Xu23]. For both ${\mathsf{QMA}}$ and
${\mathsf{QMA}}(2)$, restricting Merlin in completeness to send a _subset
state_ does not change the power of the complexity class (i.e.,
${\mathsf{QMA}}={\mathsf{SQMA}}$ and ${\mathsf{QMA}}(2)={\mathsf{SQMA}}(2)$).
[GKS14] also shows why their proof strategy fails if Merlin is restricted in
both completeness and soundness.

#### Rigidity and games

Rigidity was first formally introduced in the context of non-local games
[MY04], and have been used to prove several complexity class equalities. For
example, the CHSH game [CHSH69] tests for a maximally entangled state on two
qubits [Tsi93], and was used to prove ${\mathsf{QMIP}}={\mathsf{MIP}}^{*}$
[RUV13]. The Mermin-Peres magic square game tests for two copies of a
maximally entangled quantum state, and was used to prove
${\mathsf{MIP}}^{*}={\mathsf{RE}}$ [JNV+21]. Rigidity is known to exist in
broader contexts, including some (but not all) linear constraint games
[CMMN20] and monogamy-of-entanglement games [BC23].

##  2 Our setup

We restate the definition of ${\mathsf{QMA}}^{+}(k)$ from [JW23]. When the
proof length is not specified, it is allowed to be at most any polynomial in
input size. We follow the conventions
${\mathsf{QMA}}^{+}:={\mathsf{QMA}}^{+}(1)$,
${\mathsf{QMA}}^{+}(k):=\bigcup_{c-s=\Omega(1)}{\mathsf{QMA}}^{+}(k)_{c,s}$,
and ${\mathsf{QMA}}^{+}_{\log}:={\mathsf{QMA}}^{+}$ with proof length at most
$O(\log n)$.

######  Definition 1 (${\mathsf{QMA}}^{+}_{\ell}(k)_{c,s}$).

Let $k:\mathbb{N}\rightarrow\mathbb{N}$ and
$s,c,\ell:\mathbb{N}\rightarrow\mathbb{R}^{+}$ be polynomial time computable
functions. A promise problem
$\mathcal{L}_{\text{yes}},\mathcal{L}_{\text{no}}\subseteq\\{0,1\\}^{*}$ is in
${\mathsf{QMA}}^{+}_{\ell}(k)_{c,s}$ if there exists a ${\mathsf{BQP}}$
verifier $V$ such that for every $n\in\mathbb{N}$ and every
$x\in\\{0,1\\}^{n}$:

  * •

Completeness: if $x\in\mathcal{L}_{\text{yes}}$, then there exist unentangled
states $\ket{\psi_{1}},\ldots,\ket{\psi_{k(n)}}$, each on at most $\ell(n)$
qubits and with real non-negative amplitudes, s.t.

$\displaystyle\mathop{\bf
Pr\/}[V(x,\ket{\psi_{1}}\otimes\ldots\otimes\ket{\psi_{k(n)}})\text{
accepts}]\geq c(n)\,.$

  * •

Soundness: If $x\in\mathcal{L}_{\text{no}}$, then for every set of unentangled
states $\ket{\psi_{1}},\ldots,\ket{\psi_{k(n)}}$, each on at most $\ell(n)$
qubits and with real non-negative amplitudes, we have

$\displaystyle\mathop{\bf
Pr\/}[V(x,\ket{\psi_{1}}\otimes\ldots\otimes\ket{\psi_{k(n)}})\text{
accepts}]\leq s(n)\,.$

We make a few remarks on this complexity class, with extended discussion in
Section 5. First, we stress that the restriction to quantum proofs with non-
negative amplitudes is _promise-symmetric_ , i.e. both in completeness and in
soundness. This is unlike, for example, the class ${\mathsf{SQMA}}$ [GKS14].
Although the restriction to _subset states_ is stronger than _non-negative
amplitudes_ ,555A _subset state_ is a uniform superposition over a subset of
all computational basis states. States with non-negative amplitudes are
conical combinations of subset states. its use _only_ in completeness allows
for ${\mathsf{SQMA}}={\mathsf{QMA}}$. In fact, our work implies that
${\mathsf{QMA}}$ with a promise-symmetric _subset state_ restriction also
interpolates from ${\mathsf{QMA}}$ to ${\mathsf{NEXP}}$, depending on the size
of the promise gap.

We also explain why the promise gap of ${\mathsf{QMA}}^{+}$ cannot obviously
be amplified. The first strategy one might try is _parallel repetition_ : an
honest Merlin sends multiple copies of the original proof and Arthur verifies
each copy of the original proof. For ${\mathsf{QMA}}$, entangling the copies
in soundness does not help Merlin, since Arthur’s protocol is sound for all
quantum states. But perhaps unintuitively, it _can_ help for
${\mathsf{QMA}}^{+}$. (See 28 for a simple example.) This is because partial
measurement can _destroy_ the restriction on the quantum proof! For example,
Arthur’s first measurement may introduce relative phase in the rest of the
proof. This fact also obstructs more clever amplification strategies for
${\mathsf{QMA}}$ such as the proof-length preserving variant [MW05].

Furthermore, it is not clear how to upper-bound ${\mathsf{QMA}}^{+}$ beyond
the trivial ${\mathsf{NEXP}}$.666${\mathsf{QMA}}^{+}\subseteq{\mathsf{NEXP}}$
by directly simulating the quantum proof and verifier. One technique to upper-
bound ${\mathsf{QMA}}$ is to find the optimal proof using a semidefinite
program (or a general convex program). This shows that
${\mathsf{QMA}}\subseteq{\mathsf{PSPACE}}$ (or
${\mathsf{QMA}}\subseteq{\mathsf{EXP}}$ with a convex program). But these
arguments do not immediately transfer to ${\mathsf{QMA}}^{+}$. Convex
optimization over states with non-negative amplitudes is equivalent to
optimizing over the _copositive cone_ [Bur11]. Even the _weak membership_
problem over the copositive cone (deciding if the optimal vector is close to a
non-negative vector) is ${\mathsf{NP}}$-hard in polynomially-sized vector
spaces; recall that quantum states are in _exponentially_ -sized vector
spaces. These are the same reasons that prevent straightforward upper bounds
for ${\mathsf{QMA}}(2)$ [Gha09].

##  3 ${\mathsf{QMA}}^{+}_{\log}$ Protocol for ${\mathsf{NP}}$

We first define the problem we consider:

######  Definition 2 (CSP system).

A _$(N,R,q,\Sigma)$ -CSP system_ $\mathcal{C}$ on $N$ variables with values in
$\Sigma$ consists of a set (possibly a multi-set) of $R$ constraints
$\\{\mathcal{C}_{1},\dots,\mathcal{C}_{R}\\}$ where the arity of each
constraint is exactly $q$.

######  Definition 3 (Value of CSP).

The _value_ of a $(N,R,q,\Sigma)$-CSP system $\mathcal{C}$ is the maximum
fraction of satisfiable constraints over all possible assignments
$\sigma:[N]\to\Sigma$. The value of $\mathcal{C}$ is denoted $\mathop{\bf
val\/}(\mathcal{C})$.

######  Definition 4 (GapCSP).

The _$(1,\delta)$ -GapCSP problem_ inputs a CSP system $\mathcal{C}$. The task
is to distinguish whether $\mathcal{C}$ is such that (in completeness)
$\mathop{\bf val\/}(\mathcal{C})=1$ or (in soundness) $\mathop{\bf
val\/}(\mathcal{C})\leq\delta$.

Fix the input size $n$, and consider $(N,R,q,\Sigma)$-CSP systems where $N$
and $R$ are polynomials in $n$. Deciding whether or not these systems are
satisfiable is ${\mathsf{NP}}$-hard. In fact, there exists $\delta<1$ such
that deciding $(1,\delta)$-GapCSP on these CSP systems is
${\mathsf{NP}}$-hard.

######  Theorem 5 ([Din07]).

There exist constants $q>1$ and $|\Sigma|$ such that $(1,1/2)$-GapCSP is
${\mathsf{NP}}$-hard.

Our goal in this section is to construct a protocol for $(1,\delta)$-GapCSP
given any $(N,R,q,\Sigma)$-CSP system $\mathcal{C}$ where
$N,R=\mathrm{poly}(n)$ and $q,|\Sigma|=O(1)$. Let $\kappa:=|\Sigma|^{q}$. We
first outline the protocol. Arthur asks for a quantum state from
$\mathbb{C}^{R}\otimes\mathbb{C}^{\kappa}$; we call the first register the
_constraint register_ and the second register the _color register_. A quantum
proof has the following form:

$\displaystyle\ket{\psi}:=\sum_{j\in[R],x\in\Sigma^{q}}a_{j,x}\ket{j}\ket{x}$

For completeness, consider the satisfying assignment of variables (in $[N]$)
to values (in $\Sigma$). Merlin sends the quantum proof
$\frac{1}{\sqrt{R}}\sum_{j\in[R]}\ket{j}\ket{\vec{v}_{j}}$, where each
$\vec{v}_{j}$ is the (ordered) list of values associated with the variables
participating in $\mathcal{C}_{j}$.

Arthur then applies one of two kinds of tests:

  1. 1.

_Rigidity tests_ : These ensure that the quantum proof is of the form
$\frac{1}{\sqrt{R}}\sum_{j\in[R]}\ket{j}\ket{\vec{v}_{j}}$.

  2. 2.

_Constraint tests_ : These verify that values in the quantum proof satisfy
constraints of the CSP system.

Below, we separately describe the rigidity tests and constraint tests. In
each, we analyze the success probability in completeness and prove lemmas to
study soundness. We then combine the technical statements to prove the result.

###  3.1 Rigidity tests

Arthur enforces _rigidity_ of a quantum proof using two tests. The first test
is the _Density test_ , which maximizes $\ell_{1}$ norm. Here, we measure the
state in the Hadamard basis and _accept_ if the outcome is $\ket{+}$.777For
simplicity, we denote the uniform superposition over all standard basis states
by $\ket{+}$. The dimension is clear from the context. Given $\ket{\psi}$, the
success probability of this test is

$\displaystyle
D(\ket{\psi})=\left|\bra{+}\ket{\psi}\right|^{2}=\frac{1}{\kappa
R}\left|\sum_{j\in[R],x\in\Sigma^{q}}a_{j,x}\right|^{2}=\frac{1}{\kappa
R}(\|\ket{\psi}\|_{1})^{2}\,.$

Recall that if $\ket{\psi}$ is a subset state according to subset $S$, its
sparsity $\|\ket{\psi}\|_{1}$ is exactly $\sqrt{|S|}$. In completeness, the
quantum proof is a subset state with $R$ elements, so this test passes with
probability $\frac{1}{\kappa}$.

The second test is the _Validity test_ , which minimizes $\ell_{1}$ norm
_only_ on the second register. Here, we measure the color register in the
Hadamard basis, and _reject_ if the outcome is $\ket{+}$. Given $\ket{\psi}$,
the success probability of this test is

$\displaystyle
V(\ket{\psi})=1-\bra{+}\Tr_{R}(\ket{\psi}\bra{\psi})\ket{+}=1-\frac{1}{\kappa}\sum_{j\in[R]}\left|\sum_{x\in\Sigma^{q}}a_{j,x}\right|^{2}\,,$

where $\Tr_{R}$ is partial trace over the constraint register. In
completeness, recall that the proof has the form
$\frac{1}{\sqrt{R}}\sum_{j\in[R]}\ket{j}\ket{\vec{v}_{j}}$, so the success
probability is

$\displaystyle
1-\bra{+}\left(\frac{1}{R}\sum_{j\in[R]}\outerproduct{\vec{v}_{j}}{\vec{v}_{j}}\right)\ket{+}=1-\frac{1}{\kappa}\,.$

In fact, no quantum state without relative phase can pass the _Validity test_
with a higher probability:

######  Lemma 6.

Suppose $\ket{\psi}$ has no relative phase. Then $V(\ket{\psi})\leq
1-\frac{1}{\kappa}$.

###### Proof.

The success probability $V(\ket{\psi})$ is

$\displaystyle
1-\frac{1}{\kappa}\sum_{j\in[R]}(\sum_{x\in\Sigma^{q}}a_{j,x})^{2}$
$\displaystyle=1-\frac{1}{\kappa}(\sum_{j\in[R]}\sum_{x,y\in\Sigma^{q}}a_{j,x}a_{j,y})$
$\displaystyle=1-\frac{1}{\kappa}(1+\sum_{j\in[R]}\sum_{x,y\in\Sigma^{q};x\neq
y}a_{j,x}a_{j,y})$ $\displaystyle\leq 1-\frac{1}{\kappa}\,,$

where the second equality follows from $\sum_{j,x}a_{j,x}^{2}=1$ and the
inequality holds since $a_{j,x}\geq 0$. ∎

It turns out that is impossible to score high on both the _Validity test_ and
the _Density test_. We use this to enforce the rigidity property of
$\ket{\psi}$.

######  Lemma 7.

$D(\ket{\psi})+V(\ket{\psi})\leq 1$.

###### Proof.

By Cauchy-Schwarz,

$\displaystyle D(\ket{\psi})=\frac{1}{\kappa
R}\left|\sum_{j\in[R]}\sum_{x\in\Sigma^{q}}a_{j,x}\right|^{2}\leq\frac{1}{\kappa}\sum_{j\in[R]}\left|\sum_{x\in\Sigma^{q}}a_{j,x}\right|^{2}=1-V(\ket{\psi})\,.$
∎

Why does this help with rigidity? Suppose Arthur inputs a quantum proof
(without relative phase) $\ket{\psi}$ and runs _Density test_ with probability
$p_{1}$ and _Validity test_ with probability $p_{2}$. Suppose also that
$p_{2}>p_{1}$. Then the expected success probability is
$p_{1}D(\ket{\psi})+p_{2}V(\ket{\psi})\leq
p_{1}+(p_{2}-p_{1})V(\ket{\psi})\leq p_{1}+(p_{2}-p_{1})(1-\frac{1}{\kappa})$.
Note that this upper bound is achieved in completeness, and for any state of
the form $\frac{1}{\sqrt{R}}\sum_{j\in R}\ket{j}\ket{\vec{v}_{j}}$. We show
that quantum proofs must have this form to reach the upper bound.

One requirement to get close to the upper bound is near-optimal success
probability on _Validity test_. We prove that any quantum proof that has this
property must be close to a state that assigns one color to each constraint.

######  Lemma 8.

Given $\ket{\psi}=\sum_{j,x}a_{j,x}\ket{j}\ket{x}$ with no relative phase
(i.e. $a_{j,x}\geq 0$), let

$\displaystyle\gamma:=\max_{\nu:[R]\to\Sigma^{q}}\sum_{j\in[R]}a_{j,\nu(j)}^{2}$

be associated with maximizing function $\sigma$, and let
$\ket{\phi}:=\frac{1}{\sqrt{\gamma}}\sum_{j}a_{j,\sigma(j)}\ket{j}\ket{\sigma(j)}$.
Fix any $d\geq 0$. If $V(\ket{\psi})=1-\frac{1+d}{\kappa}$, then
$\left|\bra{\psi}\ket{\phi}\right|^{2}\geq 1-d$.

###### Proof.

Note that for all $x\in\Sigma^{q}$, $a_{j,\sigma(j)}\geq a_{j,x}$; otherwise,
$\sigma$ is not maximizing. Using the proof of Lemma 6,

$\displaystyle d=\sum_{j\in[R]}\sum_{x,y\in\Sigma^{q};x\neq
y}a_{j,x}a_{j,y}\geq\sum_{j\in[R]}\sum_{y\in\Sigma^{q};y\neq\sigma(j)}a_{j,\sigma(j)}a_{j,y}\geq\sum_{j\in[R]}\sum_{y\in\Sigma^{q};y\neq\sigma(j)}a_{j,y}^{2}\,.$

So then,

$\displaystyle\gamma=\sum_{j\in[R]}a_{j,\sigma(j)}^{2}=(\sum_{j\in[R]}\sum_{x\in\Sigma^{q}}a_{j,x}^{2})-(\sum_{j\in[R]}\sum_{x\in\Sigma^{q};x\neq\sigma(j)}a_{j,x}^{2})\geq
1-d\,.$

So
$\left|\bra{\psi}\ket{\phi}\right|^{2}=(\frac{1}{\sqrt{\gamma}}\sum_{j}a_{j,\sigma(j)}^{2})^{2}=\gamma\geq
1-d$. ∎

Another requirement to get close to the upper bound is near-optimal success
probability on _Density test_ , up to Lemma 7. Consider any quantum proof that
passes _Validity test_ with probability close to $1-\frac{1}{\kappa}$ and
_Density test_ with probability close to $\frac{1}{\kappa}$; we show it must
be close to a state of the form $\frac{1}{\sqrt{R}}\sum_{j\in
R}\ket{j}\ket{\vec{v}_{j}}$. Now we can prove the soundness of the rigidity
test by relying on the following fact:

######  Fact 9.

Let $0\leq\Pi\leq\mathbb{I}$ be a positive semi-definite matrix, and let
$\ket{\psi_{1}}$ and $\ket{\psi_{2}}$ be quantum states such that
$\left|\innerproduct{\psi_{1}}{\psi_{2}}\right|^{2}\geq 1-d$. Then
$\left|\bra{\psi_{1}}\Pi\ket{\psi_{1}}-\bra{\psi_{2}}\Pi\ket{\psi_{2}}\right|\leq\sqrt{d}$.

###### Proof.

The quantity
$\left|\bra{\psi_{1}}\Pi\ket{\psi_{1}}-\bra{\psi_{2}}\Pi\ket{\psi_{2}}\right|=\left|\Tr(\Pi\left(\outerproduct{\psi_{1}}{\psi_{1}}-\outerproduct{\psi_{2}}{\psi_{2}}\right))\right|$
is upper-bounded by the trace distance of $\outerproduct{\psi_{1}}{\psi_{1}}$
and $\outerproduct{\psi_{2}}{\psi_{2}}$, which has value
$\sqrt{1-\left|\bra{\psi_{1}}\ket{\psi_{2}}\right|^{2}}\leq\sqrt{d}$. ∎

######  Lemma 10 (Rigidity lemma).

Let $d_{2}\geq d_{1}\geq 0$ be small constants. Suppose $\ket{\psi}$,
$\ket{\phi}$, and $\sigma$ are defined as in Lemma 8, and $\ket{\chi}$ is
defined as

$\displaystyle\ket{\chi}:=\frac{1}{\sqrt{R}}\sum_{j\in[R]}\ket{j}\ket{\sigma(j)}\,.$

If $D(\ket{\psi})=\frac{1}{\kappa}-d_{1}$ and
$V(\ket{\psi})=1-\frac{1}{\kappa}-d_{2}$, then
$\left|\innerproduct{\chi}{\psi}\right|^{2}\geq 1-\kappa
d_{1}-(\kappa+1)\sqrt{\kappa\cdot d_{2}}$.

###### Proof.

By Lemma 8, we know that $\left|\innerproduct{\psi}{\phi}\right|^{2}\geq
1-\kappa\cdot d_{2}$. So by 9, for any quantum state $\ket{\mu}$,
$\left|\left|\innerproduct{\mu}{\phi}\right|^{2}-\left|\innerproduct{\mu}{\psi}\right|^{2}\right|\leq\sqrt{\kappa\cdot
d_{2}}$. We use this in two places. First, when $\ket{\mu}=\ket{+}$. Since
$D(\ket{\psi})=\left|\innerproduct{+}{\psi}\right|^{2}=\frac{1}{\kappa}-d_{1}$,
we have
$\left|\innerproduct{+}{\phi}\right|^{2}\geq\frac{1}{\kappa}-d_{1}-\sqrt{\kappa\cdot
d_{2}}$ by triangle inequality. Second, when $\ket{\mu}=\ket{\chi}$. Notice
that

$\displaystyle\left|\innerproduct{\chi}{\phi}\right|^{2}=\kappa\left|\innerproduct{+}{\phi}\right|^{2}\geq
1-\kappa(d_{1}+\sqrt{\kappa\cdot d_{2}})\,.$

Again by triangle inequality,

$\displaystyle\left|\innerproduct{\chi}{\psi}\right|^{2}\geq
1-\kappa(d_{1}+\sqrt{\kappa\cdot d_{2}})-\sqrt{\kappa\cdot d_{2}}\,.$ ∎

Intuitively, Lemma 10 allows us to _tune_ the probability of each test in the
${\mathsf{NP}}$ protocol. As we explain in the analysis (Section 3.3), if the
probabilities of running _Validity test_ and _Density test_ are much higher
than that for constraint tests, then if $d_{1}$ or $d_{2}$ is large, these two
tests catch a “deceptive” quantum proof in soundness. This allows constraint
tests to focus on the case of small $d_{1}$ and $d_{2}$; i.e. nearly _rigid_
quantum proofs.

###  3.2 Constraint tests

We analyze the constraint tests on _rigid_ quantum proofs, i.e. states of the
form $\ket{\psi}=\frac{1}{\sqrt{R}}\sum_{j\in[R}\ket{j}\ket{\vec{v}_{j}}$. The
verifier needs to check two properties:

  1. (i)

(_satisfiability_) For all $j\in[R]$, the assignment $\vec{v}_{j}$ satisfies
$\mathcal{C}_{j}$.

  2. (ii)

(_consistency_) Each variable is assigned the same value when participating in
different constraints.

One may ask why we even need to check for _consistency_. Couldn’t we ask for
the assignment of each variable $a:[N]\to\Sigma$, for example as the quantum
proof $\frac{1}{\sqrt{N}}\sum_{i\in[N]}\ket{i}\ket{a(i)}$? The problem with
this is checking _satisfiability_ becomes difficult, since the assigned values
are given in superposition.888There is a way around this limitation for CSP
systems consisting of _unique game constraints_ , where each (binary)
constraint involving variables $i_{1},i_{2}$ accepts exactly one $a(i_{2})$
for each $a(i_{1})$. See [JW23, Section 6] for more discussion.

Instead, with a state
$\frac{1}{\sqrt{R}}\sum_{j\in[R}\ket{j}\ket{\vec{v}_{j}}$, _satisfiability_ is
easy to verify: measure the first register (observing some
$\ket{j}\ket{\vec{v}_{j}}$), and compute $\mathcal{C}_{j}(\vec{v}_{j})$. Let
$u_{s}$ be the number of unsatisfied constraints. The outcome is $1$ with
probability $1-\frac{u_{s}}{R}$.

But this form of quantum proof gives Merlin a new way to “deceive”: for a
given variable, send different values depending on the constraint! We prevent
this by checking for _consistency_ , similarly to the pre-processing step of
[Din07] sometimes called _regularization_. As in [JW23, Section 7], we add
“consistency constraints” to the CSP system $\mathcal{C}$ as follows:999Note
that since $N$ and $R$ are polynomially-sized, this process is efficient.

  * •

For each variable $i\in[N]$, let $V_{i}$ represent the constraints that $i$
participates in.

  * •

Fix a constant $d$. For each $i\in[N]$, draw a $d$-regular graph with vertices
$V_{i}$ that is _expanding_.101010For technical reasons of 11, we require that
the Cheeger constant is at least 2.

  * •

Each edge $(j_{1},j_{2})$ of each expander $V_{i}$ represents a “consistency
constraint”, where we assert that the value of variable $i$ sent with
constraint $j_{1}$ equals that sent with constraint $j_{2}$.

Using _expander_ graphs allows us to prevent this kind of “deceptive” Merlin:
either the proof fails many of the original constraints, or it fails many
“consistency constraints”. Let $u_{e}$ be the number of unsatisfied
“consistency constraints” out of $Rq\cdot\frac{d}{2}$:

######  Claim 11 ([Din07, Lemma 4.1]).

Consider a $(N,R,q,\Sigma)$-CSP system $\mathcal{C}$, and apply
_regularization_. If $\mathop{\bf val\/}(\mathcal{C})=1$, then all
“consistency constraints” can be simultaneously satisfied. If $\mathop{\bf
val\/}(\mathcal{C})\leq\delta$, then the total number of unsatisfied
constraints $(u_{s}+u_{e})$ is at least $(1-\delta)R$.

How do we check these “consistency constraints”? Over the next few paragraphs,
we construct a unitary related to permutations on the constraint graph. In
completeness, the quantum proof is an eigenvector of this unitary, but in
soundness, all _rigid_ quantum proofs are detectably far (i.e. using a
Hadamard test) from an eigenvector. We study the graph $\widetilde{G}$ with
$R\cdot q$ vertices, where each vertex $(j,i)$ corresponds to a clause $j$ and
a variable $i$ that participates in clause $j$. Let $\widetilde{G}$ be the
union of all consistency edges created during regularization, i.e.
$(j_{1},j_{2})$ for variable $i$ becomes the edge $((j_{1},i),(j_{2},i))$.
Note that $\widetilde{G}$ contains a copy of each expander graph, so it is
$d$-regular.

We now choose $d$ permutations. It is a classical fact that the adjacency
matrix of any $d$-regular graph can always be decomposed to $d$ permutations.
Let $\pi_{1},\ldots,\pi_{d}$ be the decomposition of $\widetilde{G}$; recall
that these are permutations on $V(\widetilde{G})$ where
$|V(\widetilde{G})|=R\cdot q$. For each $k\in[d]$, we identify $\pi_{k}$ with
a permutation on $[R]\times[N]$, where any $(j,i)\in[R]\times[N]$ that is not
a vertex of $\widetilde{G}$ (i.e. variable $i$ does not participate in
constraint $j$) is mapped to itself.111111These permutations (and their
inverses) are all efficient because $N$ and $R$ are polynomially-sized. Note
that this map always preserves the variable $i\in[N]$; without loss of
generality, we also identify $\pi_{k}$ with its restriction
$[R]\times[N]\to[R]$. From here on, we use this last definition of $\pi_{k}$,
which maps constraint $j_{1}$ that variable $i$ participates in to another
constraint $j_{2}$ that variable $i$ participates in, and identity otherwise.

Now consider a _rigid_ quantum proof, i.e. of the form
$\ket{\psi}=\frac{1}{\sqrt{R}}\sum_{j\in[R]}\ket{j}\ket{\vec{v}_{j}}$. Since
there are a polynomial number of variables and constraints, we can efficiently
transform $\ket{\psi}$ to $\ket{\phi^{\prime}}$, where

$\displaystyle\ket{\phi^{\prime}}:=\frac{1}{\sqrt{q\cdot
R}}\sum_{j\in[R]}\sum_{i\in\mathcal{C}_{j}}\ket{j}\ket{\vec{v}_{j}}\ket{i}\ket{v_{j}(i)}\,.$

Here, $i\in\mathcal{C}_{j}$ are the variables participating in
$\mathcal{C}_{j}$, and $v_{j}(i)$ is the value of this variable according to
$\vec{v}_{j}$.

We now would like to construct a unitary on $\ket{\phi^{\prime}}$ that maps
$\ket{j}\ket{i}\ket{value}$ to $\ket{j^{\prime}}\ket{i}\ket{value}$ for some
other constraint $j^{\prime}$ that $i$ participates in. In completeness, this
unitary would leave the state unchanged. Notice that from the perspective of
such a unitary, the second register containing $\ket{\vec{v}_{j}}$ is “junk”.
Fortunately, we can measure out the second register in the Hadamard basis, and
reject if the outcome is _not_ $\ket{+}$. All _rigid_ states will observe
outcome $\ket{+}$ with probability $\frac{1}{\kappa}$; one can see this by
writing the second register in the Hadamard basis.

Suppose the observed outcome is $\ket{+}$; let us call the postselected state
$\ket{\phi}$, where

$\displaystyle\ket{\phi}:=\frac{1}{\sqrt{q\cdot R}}\sum_{j\in
R}\sum_{i\in\mathcal{C}_{j}}\ket{j}\ket{i}\ket{v_{j}(i)}\,.$

For each $k\in[d]$, we now implement the in-place transformation $\Pi_{k}$
according to $\pi_{k}:[R]\times[N]\to[R]$, where

$\displaystyle\Pi_{k}:\ket{j}\ket{i}\ket{v_{j}(i)}\rightarrow\ket{\pi_{k}(j,i)}\ket{i}\ket{v_{j}(i)}\,.$

Recall that the map $(j,i)\mapsto(\pi_{k}(j,i),i)$ is a permutation. Since we
have access both to this permutation and its inverse, we can implement
$\Pi_{k}$.

Note that in a satisfiable instance, $\Pi_{k}\ket{\phi}=\ket{\phi}$. By
contrast, if $v_{j}(i)\neq v_{j^{\prime}}(i)$,
$\ket{j^{\prime}}\ket{i}\ket{v_{j}(i)}$ is orthogonal to $\ket{\phi}$. Hence,
$\bra{\phi}\Pi_{k}\ket{\phi}$ is the fraction of satisfied “consistency
constraints” observed by $\pi_{k}$. We use the _Hadamard test_ to measure this
value, in a similar way to the _Spectral test_ in [BFM22]. Note that unlike
the swap test, the Hadamard test only uses one copy of a quantum state.

######  Definition 12 (Hadamard test).

Let $\ket{\psi}$ be a quantum state and $U$ a unitary operator.

  1. 1.

Prepend a control qubit to $\ket{\psi}$, to create $\ket{0}\ket{\psi}$.

  2. 2.

Apply a Hadamard on the control qubit, to create
$\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})\ket{\psi}$.

  3. 3.

Apply $U$, controlled by the control qubit, to create
$\frac{1}{\sqrt{2}}\left(\ket{0}\ket{\psi}+\ket{1}U\ket{\psi}\right)$.

  4. 4.

Apply a Hadamard on the control qubit, to create
$\frac{1}{2}\ket{0}\left(\ket{\psi}+U\ket{\psi}\right)+\frac{1}{2}\ket{1}\left(\ket{\psi}-U\ket{\psi}\right)$.

  5. 5.

Measure the control qubit, and accept if the output is $0$.

The success probability is then

$\displaystyle\frac{1}{4}\left\|\ket{\psi}+U\ket{\psi}\right\|^{2}=\frac{1}{2}+\frac{1}{4}\bra{\psi}U+U^{\dagger}\ket{\psi}=\frac{1}{2}+\frac{\real\bra{\psi}U\ket{\psi}}{2}\,.$

We now can describe the constraint tests together:

  1. (i)

With probability $\frac{1}{qd\kappa+1}$, check _satisfiability_. This succeeds
with probability $1-\frac{u_{s}}{R}$.

  2. (ii)

With probability $\frac{qd\kappa}{qd\kappa+1}$, generate
$\ket{\phi^{\prime}}$, and measure the second register in the Hadamard basis.
If the output state is not $\ket{+}$, reject. Otherwise, choose a random
$k\in[d]$, and perform a Hadamard test with $\Pi_{k}$. This succeeds with
probability
$\frac{1}{\kappa}(\frac{1}{2}+\frac{1}{2}\mathbb{E}_{k}[\real\bra{\phi}\Pi_{k}\ket{\phi}])=\frac{1}{\kappa}(1-\frac{u_{e}}{qdR})$.121212Note
that in our protocol, $\bra{\phi}\Pi_{k}\ket{\phi}$ is always real because
$\ket{\phi}$ and $\Pi_{k}$ have real values.

The overall success probability of the constraint tests is

$\displaystyle\frac{1}{qd\kappa+1}(1-\frac{u_{s}}{R})+\frac{qd\kappa}{qd\kappa+1}\left(\frac{1}{\kappa}\cdot(1-\frac{u_{e}}{qdR})\right)=\frac{qd+1}{qd\kappa+1}-\frac{u_{e}+u_{s}}{R\cdot(qd\kappa+1)}\,.$

We now show a constant gap between completeness and soundness. In
completeness, $u_{e}=u_{s}=0$, so $\ket{\psi}$ passes the constraint tests
with probability $C^{\textnormal{YES}}:=\frac{qd+1}{qd\kappa+1}$. In
soundness, recall that $\mathop{\bf val\/}(\mathcal{C})\leq\delta$, so by 11,
any _rigid_ quantum proof passes the constraint tests with probability at most
$C^{\textnormal{YES}}-\frac{1-\delta}{qd\kappa+1}$. We now apply Lemma 10: any
quantum proof that passes _Density test_ and _Validity test_ with
probabilities too similar to that in completeness must pass the constraint
tests with probability less than $C^{\textnormal{YES}}$.

######  Corollary 13.

In soundness, if $D(\ket{\psi})=\frac{1}{\kappa}-d_{1}$ and
$V(\ket{\psi})=1-\frac{1}{\kappa}-d_{2}$, then

$\displaystyle C(\ket{\psi})\leq
C^{\textnormal{YES}}-\frac{1-\delta}{qd\kappa+1}+\left(\kappa
d_{1}+(\kappa+1)\sqrt{\kappa\cdot d_{2}}\right)^{1/2}\,.$

###  3.3 Analysis

In the protocol, Arthur applies _Density test_ , _Validity test_ , or
_constraint tests_ with probability $p_{1},p_{2},p_{3}$, respectively, where
$p_{3}=1-p_{1}-p_{2}$.

We start by analyzing the success probability of the protocol in completeness.
Here, $\mathop{\bf val\/}(\mathcal{C})=1$, and the quantum proof
$\ket{\psi}=\frac{1}{R}\sum_{j}\ket{j}\ket{\vec{v}_{j}}$ is such that
$\vec{v}_{j}$ is a satisfying assignment to the variables that participate in
$\mathcal{C}_{j}$. The success probability for each test is exactly
$\frac{1}{\kappa}$, $1-\frac{1}{\kappa}$, and $C^{\textnormal{YES}}$,
respectively. So the success probability of the protocol in completeness is
$P_{\textnormal{YES}}=\frac{p_{1}}{\kappa}+p_{2}(1-\frac{1}{\kappa})+p_{3}C^{\textnormal{YES}}$.

We now choose the probabilities $p_{1},p_{2},p_{3}$. Choose
$\lambda:=\frac{1-\delta}{qd\kappa+1}$.

  1. 1.

We first set a _distance threshold_ $\varepsilon:=\frac{\lambda}{\Gamma}$ for
a large enough constant $\Gamma(\kappa,q,d,\delta)$ satisfying

$\displaystyle\left(\kappa\varepsilon+(\kappa+1)\sqrt{\kappa\cdot\varepsilon}\right)^{1/2}\leq\frac{\lambda}{2}\,.$

  2. 2.

Let $Z:=\frac{1}{2}+1+\frac{\varepsilon}{4(1-C^{\textnormal{YES}})}$. Then let

$\displaystyle p_{1}$ $\displaystyle=\frac{1}{2}\cdot\frac{1}{Z}$
$\displaystyle p_{2}$ $\displaystyle=\frac{1}{Z}$ $\displaystyle p_{3}$
$\displaystyle=\frac{\varepsilon}{4(1-C^{\textnormal{YES}})}\cdot\frac{1}{Z}\,.$

Now we study soundness, i.e. when $\mathop{\bf val\/}(\mathcal{C})\leq\delta$.
We again denote the quantum proof as $\ket{\psi}$. We divide up the analysis
into a few parts:

  1. 1.

A quantum proof that is “too sparse” (i.e. $D(\ket{\psi})=\frac{1}{\kappa}-d$
for any $d\geq\varepsilon$) is detected by _Density test_.

$\displaystyle P_{\textnormal{NO}}$
$\displaystyle=p_{1}(\frac{1}{\kappa}-d)+p_{2}V(\ket{\psi})+p_{3}C(\ket{\psi})$
$\displaystyle\leq P_{\textnormal{YES}}-p_{1}d+p_{3}(1-C^{\textnormal{YES}})$
$\displaystyle\leq
P_{\textnormal{YES}}-p_{1}\varepsilon+p_{3}(1-C^{\textnormal{YES}})$
$\displaystyle=P_{\textnormal{YES}}-\frac{\varepsilon}{2Z}+\frac{\varepsilon}{4Z}=P_{\textnormal{YES}}-\frac{\varepsilon}{4Z}\,.$

  2. 2.

A quantum proof that is “too dense” (i.e. $D(\ket{\psi})=\frac{1}{\kappa}+d$
for any $d\geq\varepsilon$) is detected by _Validity test_.

$\displaystyle P_{\textnormal{NO}}$
$\displaystyle=p_{1}(\frac{1}{\kappa}+d)+p_{2}V(\ket{\psi})+p_{3}C(\ket{\psi})$
$\displaystyle\leq
p_{1}(\frac{1}{\kappa}+d)+p_{2}(1-\frac{1}{\kappa}-d)+p_{3}$
$\displaystyle=P_{\textnormal{YES}}-(p_{2}-p_{1})d+p_{3}(1-C^{\textnormal{YES}})$
$\displaystyle\leq
P_{\textnormal{YES}}-(p_{2}-p_{1})\varepsilon+p_{3}(1-C^{\textnormal{YES}})$
$\displaystyle=P_{\textnormal{YES}}-\frac{\varepsilon}{2Z}+\frac{\varepsilon}{4Z}=P_{\textnormal{YES}}-\frac{\varepsilon}{4Z}\,,$

where the first inequality follows from Lemma 7.

  3. 3.

A quantum proof that is “the right density” (i.e.
$D(\ket{\psi})=\frac{1}{\kappa}+d_{1}$ for $|d_{1}|\leq\varepsilon$) but far
from “valid” ($V(\ket{\psi})=1-\frac{1}{\kappa}-d_{2}$ for
$d_{2}\geq\varepsilon$) is detected by _Validity test_ when $p_{2}>p_{1}$.

$\displaystyle P_{\textnormal{NO}}$ $\displaystyle\leq
p_{1}(\frac{1}{\kappa}+|d_{1}|)+p_{2}(1-\frac{1}{\kappa}-d_{2})+p_{3}$
$\displaystyle\leq
P_{\textnormal{YES}}+p_{1}|d_{1}|-p_{2}d_{2}+p_{3}(1-C^{\textnormal{YES}})$
$\displaystyle\leq
P_{\textnormal{YES}}-(p_{2}-p_{1})\varepsilon+p_{3}(1-C^{\textnormal{YES}})$
$\displaystyle=P_{\textnormal{YES}}-\frac{\varepsilon}{4Z}\,.$

  4. 4.

Lastly, a quantum proof that is nearly _rigid_ (i.e.
$D(\ket{\psi})=\frac{1}{\kappa}+d_{1}$ and
$V(\ket{\psi})=1-\frac{1}{\kappa}-d_{2}$ for any
$|d_{1}|,d_{2}\leq\varepsilon$) is detected by the constraint tests.

$\displaystyle P_{\textnormal{NO}}$
$\displaystyle=p_{1}(\frac{1}{\kappa}+d_{1})+p_{2}(1-\frac{1}{\kappa}-d_{2})+p_{3}C(\ket{\psi})$
$\displaystyle\leq
P_{\textnormal{YES}}+p_{1}d_{1}-p_{2}d_{2}+p_{3}\left(-\frac{1-\delta}{qd\kappa+1}+\left(\kappa
d_{1}+(\kappa+1)\sqrt{\kappa\cdot d_{2}}\right)^{1/2}\right)$
$\displaystyle\leq
P_{\textnormal{YES}}+p_{1}d_{1}-p_{2}d_{2}-p_{3}\frac{\lambda}{2}\,.$

The first inequality follows from Corollary 13, and the second inequality
holds by our choice of $\varepsilon$. Note that $d_{2}\geq 0$ by Lemma 6. By
Lemma 7, if $d_{1}\geq 0$, then $d_{1}\leq d_{2}$; otherwise $d_{1}\leq d_{2}$
trivially. So then

$\displaystyle P_{\textnormal{NO}}$ $\displaystyle\leq
P_{\textnormal{YES}}-(p_{2}-p_{1})d_{2}-p_{3}\frac{\lambda}{2}\leq
P_{\textnormal{YES}}-\frac{\varepsilon\lambda}{8(1-C^{\textnormal{YES}})Z}\,.$

Combining these cases proves the following result:

######  Theorem 14.

Given an instance of $(1,\delta)$-GapCSP, the ${\mathsf{QMA}}^{+}_{\log}$
protocol succeeds with probability $P^{\textnormal{YES}}$ in completeness and
at most $P^{\textnormal{YES}}-\Delta$ in soundness for some constants
$1>P^{\textnormal{YES}}>\Delta>0$.

######  Corollary 15.

There exist constants $1>P^{\textnormal{YES}}>\Delta>0$ such that
${\mathsf{NP}}\subseteq{\mathsf{QMA}}^{+}_{\log}$ with completeness
$P^{\textnormal{YES}}$ and soundness $P^{\textnormal{YES}}-\Delta$.

##  4 ${\mathsf{QMA}}^{+}$ protocol for ${\mathsf{NEXP}}$

Our goal in this section is to modify the previous protocol to solve an
${\mathsf{NEXP}}$-complete problem. Again by the PCP theorem, the _succinct_
$(1,\delta)$-GapCSP problem with exponentially many variables and clauses is
${\mathsf{NEXP}}$-complete. The _succinctness_ allows us to efficiently
describe the problem input. What remains is to ensure that the verifier’s
protocol is efficient. Previously, the unitary transformations were efficient
because the verifier handled $\mathrm{poly}(n)$-size graphs. Furthermore, the
expanders used to check the equality constraints for each variable may have
different sizes. Now that there can be exponentially many possibilities for
the size of each cluster, naively applying the previous technique is not
efficient. These challenges were addressed in [JW23] by considering a PCP
construction for ${\mathsf{NEXP}}$ with strong properties.

######  Theorem 16 ([JW23]).

There is a ${\mathsf{NEXP}}$-hard $(1,\delta)$-GapCSP instance for some
$(N=2^{\mathrm{poly}(n)},R=2^{\mathrm{poly}(n)},q=O(1),\Sigma=\\{0,1\\})$-CSP
system $\mathcal{C}$ that is both _$\tau$ -strongly uniform_ for some constant
$\tau$ and $\mathrm{polylog}(NR)$-_doubly explicit_.

Informally, every constraint in a _succinct_ CSP system must be computable in
polynomial time. The _doubly explicit_ property further requires the existence
of efficient maps from variables to constraints _and_ from constraints to
variables. Intuitively, these maps allow us to efficiently implement the
Hadamard test of the consistency checks.

We include the formal definition of these properties. Define
$\mathop{Adj\/}_{\mathcal{C}}(j)$ to be the list of variables participating in
$\mathcal{C}_{j}$, and $\mathop{Adj\/}_{V}(i)$ be the list of constraints that
depend on variable $i$.

######  Definition 17 (Doubly explicit CSP).

A $(N,R,q,\Sigma)$-CSP system $\mathcal{C}$ is $Z(N,R)$-_doubly explicit_ if
for all $i\in[N]$ and $j\in[R]$, the following are computable in time
$Z(N,R)$:

  1. (i)

Cardinality of $\mathop{Adj\/}_{V}(i)$ and $\mathop{Adj\/}_{\mathcal{C}}(j)$
for all $i\in[N]$ and $j\in[R]$.

  2. (ii)

$\mathop{Adj\/}_{\mathcal{C}}^{\text{ind}}:[R]\times[N]\rightarrow[q]$; if $i$
participates in $\mathcal{C}_{j}$, then
$\mathop{Adj\/}_{\mathcal{C}}^{\text{ind}}(j,i)=\imath$ is the index of $i$ in
$\mathop{Adj\/}_{\mathcal{C}}(j)$.

  3. (iii)

$\mathop{Adj\/}_{\mathcal{C}}^{\text{id}}:[R]\times[q]\rightarrow[N]$;
$\mathop{Adj\/}_{\mathcal{C}}^{\text{id}}(j,\imath)=i$ is the $\imath$-th
variable of $\mathop{Adj\/}_{\mathcal{C}}(j)$.

  4. (iv)

$\mathop{Adj\/}_{V}^{\text{ind}}:[N]\times[R]\rightarrow[R]$; if $i$
participates in $\mathcal{C}_{j}$, then
$\mathop{Adj\/}_{V}^{\text{ind}}(i,j)=\jmath$ is the index of $j$ in
$\mathop{Adj\/}_{V}(i)$.

  5. (v)

$\mathop{Adj\/}_{V}^{\text{id}}:[N]\times[R]\rightarrow[R]$;
$\mathop{Adj\/}_{V}^{\text{id}}(i,\jmath)=j$ is the $\jmath$-th variable
$\mathop{Adj\/}_{V}(i)$.

This property alone is not enough for efficient regularization: the verifier
must know how to implement an expander of size
$\left|\mathop{Adj\/}_{V}(i)\right|$ for _all_ variables $i$. The _strongly
uniform_ property resolves this complication.

######  Definition 18 (Strongly uniform CSP).

Let $\tau\in\mathbb{N}$. A $(N,R,q,\Sigma)$-CSP system $\mathcal{C}$ is
$\tau$-strongly uniform if the variable set $[N]$ can be partitioned into at
most $\tau$ different subsets $\bigcup_{y}V_{y}$ such that
$|\mathop{Adj\/}_{V}(i)|=|\mathop{Adj\/}_{V}(j)|=n_{k}$ if $i$ and $j$ belong
to the same part $V_{k}$. Furthermore, the part $k\in[\tau]$ can be determined
in time $\mathrm{polylog}(NR)$.

A $\tau$-strongly uniform CSP system allows the verifier to use $\tau$
different (possibly exponential size) $d$-regular expanders. These can be
constructed in polynomial time:

######  Theorem 19 (Doubly explicit expander graphs [Lub09, Alo21]).

There is a constant $d$ such that the following explicit constructions of
expander graphs exist:

  1. 1.

For every $n$, there is a $d$-regular graph on $n$ vertices.

  2. 2.

For every prime $p>17$, there is a $d$-regular graph on $n=p(p^{2}-1)$
vertices, and the graph can be decomposed into $d$ permutations
$\pi_{1},\dots,\pi_{d}$ that can each be evaluated in time
$\mathrm{polylog}(n)$.131313In fact, since these graphs are Cayley graphs,
both the permutations and their inverses can be evaluated in time
$\mathrm{polylog}(n)$. We use both $\pi_{k}$ and $\pi_{k}^{-1}$ in the
constraint tests to implement the unitary $\mathcal{M}_{k}$.

Furthermore, the neighbors of each variable can be listed in
$\mathrm{polylog}(n)$, and the graphs have Cheeger constant at least 2.

With this theorem, the verifier can choose a large constant $n_{0}$, and use
Construction 1 if $n_{i}\leq n_{0}$. Otherwise, the verifier can cover
_almost_ all $n_{i}$ vertices with an explicit expander using Construction 2.

######  Theorem 20 (Primes in short intervals [Che13]).

There is an absolute constant $k_{0}$ such that for any integer $k>k_{0}$,
there is a prime in the interval $[k-4k^{2/3},k]$.

We modify the protocol to expect the quantum proof
$\ket{p_{1},p_{2},\dots,p_{\tau}}\otimes\frac{1}{R}\sum_{j\in
R}\ket{j}\ket{\vec{v}_{j}}$ such that each $p_{i}\in[\lfloor
n_{i}^{1/3}\rfloor-4\lfloor n_{i}^{1/3}\rfloor^{2/3},\lfloor
n_{i}^{1/3}\rfloor]$. The verifier measures the primes, and can always check
that every $p_{i}$ is a prime number in the required range. The rest of the
analysis is similar to the ${\mathsf{NP}}$ protocol, but regularized using
these efficient expanders. We first explain how to efficiently implement the
_constraint tests_ , and then analyze the ${\mathsf{QMA}}^{+}$ protocol.

###  4.1 Efficient constraint tests

We show how to efficiently implement _consistency_ checks that imply a version
of 11. Fix any vertex $i$. Let $n$ be the number of constraints that depend on
$i$ and $p$ be the corresponding prime. Let $n_{0}$ be a large enough
constant. If $n\leq n_{0}$, then use Construction 1 $d$-regular expander to
wire new copies of the vertex together, just as for ${\mathsf{NP}}$.
Otherwise, use Construction 2 to generate a $d$-regular expander graph of size
$p(p^{2}-1)\in[n-O(n^{8/9}),n]$ that wires nearly all copies of the vertex
together. Then add $d$ self-loops for the remaining vertices. The number of
vertices with self loops is at most some $\eta n$ (for some small constant
$\eta$) since $p(p^{2}-1)\geq n-O(n^{8/9})$; we can make $\eta$ arbitrarily
small by choosing a large enough $n_{0}$.

######  Claim 21 ([JW23]).

Consider a $(N,R,q,\Sigma)$-CSP system $\mathcal{C}$, and apply _efficient
regularization_. If $\mathop{\bf val\/}(\mathcal{C})=1$, then all “consistency
constraints” can be simultaneously satisfied. If $\mathop{\bf
val\/}(\mathcal{C})\leq\delta$, then the total number of unsatisfied
constraints is at least $(1-\delta-q\eta)R$.

The analysis of 21 is similar to 11. The additional factor of $q\eta$ comes
from the self-loop constraints; these can be satisfied without violating any
“consistency constraint”.

After measuring the primes, let the verifier act on the space
$\mathbb{C}^{R}\otimes\mathbb{C}^{\kappa}\otimes\mathbb{C}^{N}\otimes\mathbb{C}^{|\Sigma|}$.
We explicitly define the unitary operators that are used in the
${\mathsf{NP}}$ protocol. These definitions exactly match [JW23]. First,
operator $\mathcal{A}$ expands the values from the list of values of variables
involved in each constraint:

$\displaystyle\mathcal{A}:\ket{j}\ket{v}\ket{0}\ket{0}$
$\displaystyle\rightarrow\frac{1}{q}\sum_{r=1}^{q}\ket{j}\ket{\vec{v}}\ket{i_{r}}\ket{v_{r}}\,,$

Here, $v$ is the list of values of variables involved in constraint $j$,
$i_{r}$ is the $r$-th variable involved in $j$, and $v_{r}$ is the value of
$i_{r}$ according to $v$. Next, define the permutation operators
$\mathcal{M}_{k}$ for each $k\in[d]$ that implement the $d$ permutations of
each efficiently constructed expander:

$\displaystyle\mathcal{M}_{k}:\ket{j}\ket{v}\ket{i}\ket{v^{\prime}}\rightarrow\ket{\Pi_{k}(j,i)}\ket{v}\ket{i}\ket{v^{\prime}}$

The last operation computes the constraints in superposition:

$\displaystyle\mathcal{B}\ket{j}\ket{v}\ket{0}\rightarrow\ket{j}\ket{v}\ket{\mathcal{C}_{j}(v)}$

######  Theorem 22 ([JW23]).

$\mathcal{A},\mathcal{B},\mathcal{M}_{k}$ can be implemented by
${\mathsf{BQP}}$ circuits.

###  4.2 Analysis

The analysis is nearly the same as in the ${\mathsf{NP}}$ protocol, with the
minor difference that the verifier also receives $p_{1},\ldots,p_{\tau}$ in
the quantum proof. The rigidity tests are unchanged. For the constraint tests,
the verifier can use the explicit operators
$\mathcal{A},\mathcal{B},\mathcal{M}_{k}$:

  1. (i)

For _satisfiability_ , the prover computes $\mathcal{B}\ket{\psi}\ket{0}$ and
measures the second qubit in the standard basis.

  2. (ii)

For _consistency_ , the prover computes $\mathcal{A}\ket{\psi}$, selects
random $d\in[k]$, and uses $\mathcal{M}_{k}$ in Hadamard test.

We already know that for a quantum proof of the valid form, we can write the
success probability as:

$\displaystyle C(\ket{\psi})$
$\displaystyle=\frac{qd+1}{qd\kappa+1}-\frac{u_{e}+u_{s}}{R\cdot(qd\kappa+1)}$

To be able to analyze soundness, all that is left is to reprove Corollary 13
to handle the subtle difference between 21 and 11. Let
$D(\ket{\psi})=\frac{1}{\kappa}\pm d_{1}$ and
$V(\ket{\psi})=1-\frac{1}{\kappa}-d_{2}$, then we can write:

$\displaystyle C(\ket{\psi})$
$\displaystyle=C^{\textnormal{YES}}-\frac{u_{e}+u_{s}}{R\cdot(qd\kappa+1)}$
$\displaystyle\leq
C^{\textnormal{YES}}-\frac{R\cdot(1-\delta-q\eta)}{R\cdot(qd\kappa+1)}+\left(\kappa
d_{1}+(\kappa+1)\sqrt{\kappa\cdot d_{2}}\right)^{1/2}\,.$

We can choose a small enough $\eta$ (via large enough $n_{0}$) so that $\eta
q<\frac{1-\delta}{2}$.

######  Corollary 23.

If $D(\ket{\psi})=\frac{1}{\kappa}\pm d_{1}$ and
$V(\psi)=1-\frac{1}{\kappa}-d_{2}$, then:

$C(\ket{\psi})\leq
C^{\textnormal{YES}}-\frac{1-\delta}{2\left(qd\kappa+1\right)}+\left(\kappa
d_{1}+(\kappa+1)\sqrt{\kappa\cdot d_{2}}\right)^{1/2}$

For soundness, the same analysis of Section 3.3 goes through by reducing
$\lambda$ by a factor of $2$; this change comes from Corollary 23, which
handles the extra $q\eta$ self-loop constraints. All together:

######  Theorem 24.

Consider $(1,\delta)$-GapCSP with a
$(N=2^{\mathrm{poly}(n)},R=2^{\mathrm{poly}(n)},q=O(1),\Sigma=\\{0,1\\})$-CSP
system that is $\mathrm{polylog}(NR)$-doubly explicit and $O(1)$-strongly
uniform. The ${\mathsf{QMA}}^{+}$ protocol solves this problem with
completeness $c$ and soundness $s$ for some constants $1>c>s>0$.

######  Corollary 25.

There exist constants $1>c>s>0$ such that
${\mathsf{NEXP}}\subseteq{\mathsf{QMA}}^{+}_{c,s}$.

##  5 Subtle features of ${\mathsf{QMA}}^{+}$

###  5.1 Promise symmetry matters

One can imagine restricting to proofs with non-negative amplitudes _only_ in
completeness. But this class is equal to ${\mathsf{QMA}}$:

######  Fact 26.

Consider the class ${\mathsf{QMA}}^{+^{\prime}}$, where the proof must have
non-negative amplitudes _only in completeness_. Since subset states have non-
negative amplitudes,
${\mathsf{SQMA}}\subseteq{\mathsf{QMA}}^{+^{\prime}}\subseteq{\mathsf{QMA}}$.
By [GKS14], ${\mathsf{SQMA}}={\mathsf{QMA}}^{+^{\prime}}={\mathsf{QMA}}$.

Instead, ${\mathsf{QMA}}^{+}$ also restricts the proof in soundness, which
reduces the ways Merlin can “deceive” Arthur. This increases the power of the
complexity class:

######  Corollary 27.

Notice that
${\mathsf{QMA}}^{+^{\prime}}_{c,s}\subseteq{\mathsf{QMA}}^{+}_{c,s}$ for any
choice of $0\leq c,s\leq 1$, since any ${\mathsf{QMA}}^{+^{\prime}}_{c,s}$
protocol is also a ${\mathsf{QMA}}^{+}_{c,s}$ protocol. Since
${\mathsf{QMA}}={\mathsf{QMA}}^{+^{\prime}}$,
${\mathsf{QMA}}\subseteq{\mathsf{QMA}}^{+}_{c,s}$ whenever $c<1$ and
$c-s\geq\frac{1}{p(n)}$ for any polynomial $p(n)$.

In general, suppose $\mathcal{R}$ is a set of quantum states that approximate
all quantum states (i.e. an $\epsilon$-covering) by at least an inverse
polynomial in number of qubits. Then ${\mathsf{QMA}}$ is equal to
${\mathsf{QMA}}$ restricted to $\mathcal{R}$ in completeness, and at most
${\mathsf{QMA}}$ restricted to $\mathcal{R}$ in both completeness and
soundness.

Furthermore, classes that modify ${\mathsf{QMA}}$ only in completeness enjoy
promise gap amplification through parallel repetition. This does not hold for
promise-symmetric modifications. We provide a simple example of how parallel
repetition fails to amplify the promise gap of ${\mathsf{QMA}}^{+}$:

######  Fact 28.

Consider a Hermitian and positive semidefinite matrix $M$. Let
$\|M\|_{+}:=\max_{\ket{v}\geq 0}\frac{\|M\ket{v}\|_{2}}{\|\ket{v}\|_{2}}$ be
the maximum value among real non-negative vectors. Then it is possible for
$\|M\otimes M\|_{+}>\|M\|_{+}^{2}$.

###### Proof.

Consider two qubits and the projector $M=\ket{x_{-}}\bra{x_{-}}$, where $M$
projects into the Pauli-X basis (i.e.
$\ket{x_{-}}=\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})$). Then
$\|M\|_{+}=\frac{1}{\sqrt{2}}$, maximized at $\ket{0}$ or $\ket{1}$. But using
the state $\ket{\chi}=\frac{1}{\sqrt{2}}(\ket{00}+\ket{11})$, $\|M\otimes
M\|_{+}\geq\|M\ket{\chi}\|=\frac{1}{\sqrt{2}}>\|M\|_{+}^{2}$. ∎

###  5.2 ${\mathsf{QMA}}^{+}$ at some constant gap equals ${\mathsf{QMA}}$

Perhaps surprisingly, ${\mathsf{QMA}}^{+}_{c,s}$ _equals_ ${\mathsf{QMA}}$ for
some constants $1>c>s>0$. This is because every quantum state can be
approximated (up to a constant) by a quantum state _without relative phase_ :

######  Proposition 29.

${\mathsf{QMA}}^{+}_{c,s}\subseteq{\mathsf{QMA}}_{c,4s}$.

###### Proof.

Consider a problem in ${\mathsf{QMA}}^{+}_{c,s}$, and let $\Pi_{1}$ be its
accepting operator. We will use the same circuit in ${\mathsf{QMA}}$, and
analyze the new completeness and soundness.

  * •

_(completeness)_ The same completeness proof is a valid proof for
${\mathsf{QMA}}$, accepting with completeness $c$.

  * •

_(soundness)_ Recall that $\bra{\chi}\Pi_{1}\ket{\chi}\leq s$ for any
$\ket{\chi}$ with non-negative amplitudes.

Consider any state $\ket{\psi}$ with _real_ (but possibly negative)
amplitudes. Separate and normalize its positive entries and negative entries,
i.e. $\ket{\psi}=\sqrt{p}\ket{\psi_{+}}-\sqrt{1-p}\ket{\psi_{-}}$. Notice that
$\bra{\psi_{+}}\ket{\psi_{-}}=0$, so $\ket{\psi}$ is of unit norm. Then

$\displaystyle\bra{\psi}\Pi_{1}\ket{\psi}$
$\displaystyle=p\bra{\psi_{+}}\Pi_{1}\ket{\psi_{+}}+(1-p)\bra{\psi_{-}}\Pi_{1}\ket{\psi_{-}}-\sqrt{p(1-p)}(\bra{\psi_{-}}\Pi_{1}\ket{\psi_{+}}+\bra{\psi_{+}}\Pi_{1}\ket{\psi_{-}})$
$\displaystyle\leq
p\bra{\psi_{+}}\Pi_{1}\ket{\psi_{+}}+(1-p)\bra{\psi_{-}}\Pi_{1}\ket{\psi_{-}}+2\sqrt{p(1-p)}\sqrt{\bra{\psi_{-}}\Pi_{1}\ket{\psi_{-}}\bra{\psi_{+}}\Pi_{1}\ket{\psi_{+}}}$
$\displaystyle\leq s+2s\sqrt{p(1-p)}\leq 2s\,,$

where the first inequality holds by Cauchy-Schwarz because $\Pi_{1}$ is
positive semidefinite.

Similarly, consider any state with arbitrary amplitudes. Separate and
normalize its real and imaginary entries, i.e.
$\ket{\phi}=\sqrt{p^{\prime}}\ket{\phi_{\mathbb{R}}}+i\sqrt{1-p^{\prime}}\ket{\phi_{i\mathbb{R}}}$.
Notice that $\ket{\phi}$ is still unit norm. By the same calculation, one
finds that $\bra{\phi}\Pi_{1}\ket{\phi}\leq 4s$.

∎

######  Corollary 30.

For any $0<\varepsilon<0.2$,
${\mathsf{QMA}}^{+}_{0.8+\varepsilon,0.2}={\mathsf{QMA}}$.

###### Proof.

${\mathsf{QMA}}^{+}_{0.8+\varepsilon,0.2}\subseteq{\mathsf{QMA}}$ follows from
Proposition 29. The other direction follows from Corollary 27. ∎

This is a strange phenomenon: depending on the choice of constants $c>s$,
${\mathsf{QMA}}^{+}_{c,s}$ could be as small as ${\mathsf{QMA}}$ and as large
as ${\mathsf{NEXP}}$!141414 Note that the same phenomenon holds for
${\mathsf{QMA}}^{+}(2)$ and ${\mathsf{QMA}}(2)$ with nearly the same proof.
This is why [JW23] was perceived as “just a constant gap away” from proving
${\mathsf{QMA}}(2)={\mathsf{NEXP}}$. See Figure 2 for a pictorial description.
An implication of our work is that assuming
${\mathsf{EXP}}\neq{\mathsf{NEXP}}$, ${\mathsf{QMA}}^{+}$ simply _cannot_ be
amplified.

##  6 Open questions

  1. 1.

What is the relationship of ${\mathsf{QMA}}$ and ${\mathsf{QMA}}(2)$? Our
result does not immediately say anything about ${\mathsf{QMA}}$ and
${\mathsf{QMA}}(2)$. It only suggests that for ${\mathsf{QMA}}$, the
restriction of _relative phase_ is maximally strong. For example, it is
possible that ${\mathsf{QMA}}(2)={\mathsf{NEXP}}$; i.e. the restriction of
_entanglement_ across a fixed barrier may be just as powerful. In fact,
showing ${\mathsf{QMA}}(2)={\mathsf{QMA}}^{+}(2)$ is still an open route to
proving ${\mathsf{QMA}}(2)={\mathsf{NEXP}}$, but in light of this work,
amplification for ${\mathsf{QMA}}^{+}(2)$ must crucially rely on the
unentanglement promise.

  2. 2.

Are other complexity classes sensitive to different constant-sized promise
gaps? We show that for ${\mathsf{QMA}}^{+}_{c,s}$, the parameter $\frac{c}{s}$
can be “tuned” to change the power of the class from ${\mathsf{QMA}}$ to
${\mathsf{NEXP}}$ (see also Figure 2). Do other complexity classes drastically
change power with different promise gaps? One similar class is
${\mathsf{SBQP}}$ [Kup15], which equals ${\mathsf{BQP}}_{c,s}$ when
$\frac{c}{s}=2$ (but unlike our work, $c$ and $s$ are exponentially small).
However, when $\frac{c}{s}$ is allowed to be any number above $1$,
${\mathsf{BQP}}_{c,s}$ is equal to ${\mathsf{PP}}$ [DGF22]. Note that relative
to oracles, ${\mathsf{SBQP}}$ is not closed under intersection, which was used
to separate it from ${\mathsf{QMA}}$ [AKKT20].

  3. 3.

State complexity vs. decision complexity? Although we prove that there are
constants $c_{1},s_{1},c_{2},s_{2}$ such that
${\mathsf{QMA}}^{+}_{c_{1},s_{1}}={\mathsf{QMA}}^{+}(2)_{c_{2},s_{2}}$, we do
not prove the existence of any _product test_ (as in [HM13]). In fact, it is
possible that no product test exists! This would show a separation between the
complexity of _decision problems_ and _state synthesis problems_ ; i.e.
${\mathsf{QMA}}^{+}={\mathsf{QMA}}^{+}(2)$ but
${\mathsf{stateQMA}}^{+}\neq{\mathsf{stateQMA}}^{+}(2)$. In fact, it is even
possible that ${\mathsf{QMA}}={\mathsf{QMA}}(2)$ but
${\mathsf{stateQMA}}\neq{\mathsf{stateQMA}}(2)$. This inquiry can help us
understand whether (or how) _the power of unentanglement_ is useful when
solving _decision problems_.

## Acknowledgements

Thanks to Zachary Remscrim for collaborating on early stages of this project.
Thanks to Noam Lifshitz, Dor Minzer, and Kevin Pratt for answering questions
about algebraic constructions of expanders. Thanks to Srinivasan Arunachalam,
Fernando Granha Jeronimo, Supartha Podder, and Pei Wu for comments on a draft
of this manuscript.

BF and RB acknowledge support from AFOSR (award number FA9550-21-1-0008). This
material is based upon work partially supported by the National Science
Foundation under Grant CCF-2044923 (CAREER) and by the U.S. Department of
Energy, Office of Science, National Quantum Information Science Research
Centers as well as by DOE QuantISED grant DE-SC0020360. KM acknowledges
support from the National Science Foundation Graduate Research Fellowship
Program under Grant No. DGE-1746045. Any opinions, findings, and conclusions
or recommendations expressed in this material are those of the author(s) and
do not necessarily reflect the views of the National Science Foundation.

## References

  * [Aar21] Scott Aaronson.  Open Problems Related to Quantum Query Complexity, 2021.  arXiv:2109.06917.
  * [ABD+08] Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, and Peter Shor.  The Power of Unentanglement, 2008.  arXiv:0804.0802.
  * [AKKT20] Scott Aaronson, Robin Kothari, William Kretschmer, and Justin Thaler.  Quantum Lower Bounds for Approximate Counting via Laurent Polynomials, 2020.  URL https://drops.dagstuhl.de/opus/volltexte/2020/12559/.
  * [ALM+98] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy.  Proof Verification and the Hardness of Approximation Problems.  J. ACM, 45(3):501–555, 1998.  URL https://doi.org/10.1145/278298.278306.
  * [Alo21] Noga Alon.  Explicit expanders of every degree and size.  Combinatorica, pages 1–17, 2021.  arXiv:2003.11673.
  * [AS92] Sanjeev Arora and Shmuel Safra.  Probabilistic Checking of Proofs; A New Characterization of NP.  In 33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, USA, 24-27 October 1992, pages 2–13. IEEE Computer Society, 1992.  URL https://doi.org/10.1109/SFCS.1992.267824.
  * [BC23] Anne Broadbent and Eric Culf.  Rigidity for Monogamy-Of-Entanglement Games, 2023.  URL https://drops.dagstuhl.de/opus/volltexte/2023/17531/.
  * [BFM22] Roozbeh Bassirian, Bill Fefferman, and Kunal Marwaha.  On the power of nonstandard quantum oracles.  2022\.  arXiv:2212.00098.
  * [BT10] Hugue Blier and Alain Tapp.  A quantum characterization of NP, 2010.  arXiv:0709.0738.
  * [Bur11] Samuel Burer.  Copositive programming.  In Handbook on semidefinite, conic and polynomial optimization, pages 201–218. Springer, 2011.  URL https://link.springer.com/chapter/10.1007/978-1-4614-0769-0_8.
  * [CD10] Jing Chen and Andrew Drucker.  Short multi-prover quantum proofs for SAT without entangled measurements.  2010\.  arXiv:1011.0716.
  * [CF11] Alessandro Chiesa and Michael A Forbes.  Improved soundness for QMA with multiple provers.  2011\.  arXiv:1108.2098.
  * [Che13] Yuanyou Furui Cheng.  Explicit Estimate on Primes between Consecutive Cubes, 2013.  arXiv:0810.2113.
  * [CHSH69] John F Clauser, Michael A Horne, Abner Shimony, and Richard A Holt.  Proposed experiment to test local hidden-variable theories.  Physical review letters, 23(15):880, 1969.  URL https://doi.org/10.1103/PhysRevLett.23.880.
  * [CMMN20] David Cui, Arthur Mehta, Hamoon Mousavi, and Seyed Sajjad Nezhadi.  A generalization of CHSH and the algebraic structure of optimal strategies.  Quantum, 4:346, oct 2020.  arXiv:1911.01593.
  * [DGF22] Abhinav Deshpande, Alexey V Gorshkov, and Bill Fefferman.  Importance of the Spectral gap in Estimating Ground-State Energies.  PRX Quantum, 3(4):040327, 2022.  arXiv:2007.11582.
  * [Din07] Irit Dinur.  The PCP theorem by gap amplification.  Journal of the ACM (JACM), 54(3):12–es, 2007.  URL https://dl.acm.org/doi/abs/10.1145/1236457.1236459.
  * [Gha09] Sevag Gharibian.  Strong NP-Hardness of the Quantum Separability Problem, 2009.  arXiv:0810.4507.
  * [GKS14] Alex B. Grilo, Iordanis Kerenidis, and Jamie Sikora.  QMA with subset state witnesses, 2014.  arXiv:1410.2882.
  * [GNN12] François Le Gall, Shota Nakagawa, and Harumichi Nishimura.  On QMA protocols with two short quantum proofs.  Quantum Inf. Comput., 12(7-8):589–600, 2012.  URL https://doi.org/10.26421/QIC12.7-8-4.
  * [GSS+18] Sevag Gharibian, Miklos Santha, Jamie Sikora, Aarthi Sundaram, and Justin Yirka.  Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2), 2018.  URL http://drops.dagstuhl.de/opus/volltexte/2018/9640/.
  * [Har04] Prahladh Harsha.  Robust PCPs of proximity and shorter PCPs.  PhD thesis, Massachusetts Institute of Technology, 2004.  URL https://dspace.mit.edu/bitstream/handle/1721.1/26720/59552830-MIT.pdf.
  * [HM13] Aram W. Harrow and Ashley Montanaro.  Testing product states, quantum Merlin-Arthur games and tensor optimization.  Journal of the ACM (JACM), 60(1):1–43, 2013.  arXiv:1001.0017.
  * [JNV+21] Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen.  Mip*= re.  Communications of the ACM, 64(11):131–138, 2021.  arXiv:2001.04383.
  * [JW23] Fernando Granha Jeronimo and Pei Wu.  The Power of Unentangled Quantum Proofs with Non-negative Amplitudes.  55th Annual ACM Symposium on Theory of Computing, 2023.  URL https://doi.org/10.1145/3564246.3585248.
  * [KMY03] Hirotada Kobayashi, Keiji Matsumoto, and Tomoyuki Yamakami.  Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur?, 2003.  arXiv:quant-ph/0306051.
  * [Kup15] Greg Kuperberg.  How hard is it to approximate the Jones polynomial?  Theory of Computing, 11(1):183–219, 2015.  URL https://doi.org/10.4086/toc.2015.v011a006.
  * [Lub09] Alexander Lubotzky.  Finite simple groups of Lie type as expanders, 2009.  arXiv:0904.3411.
  * [McK13] Matthew McKague.  On the power quantum computation over real Hilbert spaces.  International Journal of Quantum Information, 11(01):1350001, feb 2013.  arXiv:1109.0795.
  * [MW05] Chris Marriott and John Watrous.  Quantum Arthur-Merlin Games, 2005.  arXiv:cs/0506068.
  * [MY04] Dominic Mayers and Andrew Yao.  Self testing quantum apparatus, 2004.  arXiv:quant-ph/0307205.
  * [NZ23] Anand Natarajan and Tina Zhang.  Quantum free games.  2023\.  arXiv:2302.04322.
  * [Per12] Attila Pereszlényi.  Multi-Prover Quantum Merlin-Arthur Proof Systems with Small Gap, 2012\.  arXiv:1205.2761.
  * [RUV13] Ben W Reichardt, Falk Unger, and Umesh Vazirani.  Classical command of quantum systems.  Nature, 496(7446):456–460, 2013.  URL https://doi.org/10.1038/nature12035.
  * [SY22] Adrian She and Henry Yuen.  Unitary property testing lower bounds by polynomials, 2022.  arXiv:2210.05885.
  * [Tsi93] Boris S Tsirelson.  Some results and problems on quantum Bell-type inequalities.  Hadronic Journal Supplement, 8(4):329–345, 1993.  URL http://www.math.tau.ac.il/~tsirel/download/hadron.pdf.
  * [Xu23] Jianwei Xu.  Quantifying the phase of quantum states, 2023.  arXiv:2304.09028.