$C_{i}$ there are $10$ corresponding clauses $C^{\prime}_{i,j}$, $j\in[10]$
such that, if a given assignment $x$ satisfies a clause $C_{i}$ of $\phi(x)$,
then exactly $7$ clauses of $C^{\prime}_{i,j}$ can be satisfied, and for those
$C_{i}$ that are not satisfied by $x$, at most $6$ clauses of
$C^{\prime}_{i,j}$ are satisfied. Note that if $\phi(x)=1$, we then must have
that $\phi^{\prime}(x)=7/10$, and that if $\phi(x)\leq\gamma$, we have that
$\phi^{\prime}(x)\leq 7/10\gamma+6/10(1-\gamma)=(\gamma+6)/10$. Hence, it is
still $\mathsf{NP}$-hard to distinguish between those cases, and the promise
gap between the yes\- and the no-case is
$\frac{1}{10}(1-\gamma)=:\gamma^{\prime}$, which is some constant. Let us now
map $\phi^{\prime}(x)$ into a $2$-local diagonal Hamiltonian $H^{\prime}$ such
that $\bra{x}H^{\prime}\ket{x}=\phi(x)$. This can be done without any circuit-
to-Hamiltonian mapping, see for example [Had21]. By our choice of
$\phi^{\prime}(x)$, we have already ensured that the Hamiltonian is
(sub)-normalized. To turn the problem into a minimization problem, one can
simply invert the spectrum by letting $H=I-H^{\prime}$ (note that
$H^{\prime}\succeq 0)$. The eigenvectors of $H$ are basis vectors – and thus
themselves classically evaluatable states for which $\zeta=1=\mathcal{O}(1)$ –
and its eigenvalues are precisely the function evaluations of $1-\phi(x)$.
Hence, setting $a:=3/10$ and $b:=(4-\gamma)/10$ gives us
$\delta=\gamma^{\prime}=\mathcal{O}(1)$. ∎

Theorem 5.1 now gives us a very easy way to establish the following upper
bounds on $\mathsf{CGaLH}(k,\delta,\zeta)$ when the required precision
$\delta$ is only constant. Combined with Lemma 5.3, we obtain the following
result, reminiscent of Theorem 5 in [GLG22].

######  Theorem 5.2.

$\mathsf{CGaLH}(k,\delta,\zeta)$ is $\mathsf{NP}$-complete for
$k=\mathcal{O}(\log(n))$, and constants $\delta\in(0,1]$ and $\zeta\in(0,1]$.
Furthermore, when $\zeta=\Omega(1/\mathop{poly}(n))$ we have that
$\mathsf{CGaLH}(k,\delta,\zeta)$ is in $\mathsf{NqP}$.

###### Proof.

$\mathsf{NP}$-Hardness follows from Lemma 5.3. The containment statements
follow from Theorem 5.1, in which the proposed algorithm for
$m=\mathcal{O}(n^{k})$, $\delta\in(0,1]$ constant runs in polynomial time when
$\zeta$ is constant and in quasi-polynomial time when
$\zeta=\Omega(1/\mathop{poly}(n))$ (using the fact that
$\mathcal{O}(n^{\log(n)})=2^{\mathcal{O}(\log^{c}(n))}$ for some constant
$c>0$). ∎

Moreover, by a little more careful inspection one can show that the problem’s
hardness depends on how $\zeta$ and $\delta$ relate to one another, as shown
in the following theorem.

######  Theorem 5.3.

Let $f(n):\mathbb{N}\rightarrow\mathbb{R}_{>0}$,
$g(n):\mathbb{N}\rightarrow\mathbb{R}_{>0}$ be some arbitrary functions with
the property that there exists some $n_{0}$, such that for all $n<n_{0}$ we
that $1/g(n)-1/f(n)=\Omega(1/\exp(n))$. Then we have that
$\mathsf{CGaLH}(k,\delta,\zeta)$ is $\mathsf{NP}$-complete for $k\geq 2$,
$\delta=1/g(n)$ and $\zeta\geq 1-1/f(n)$.

###### Proof.

Hardness: $\mathsf{NP}$-hardness follows again trivially from Theorem 5.3, by
taking $g(n)=\mathcal{O}(1)$ and letting $f(n)$ be some arbitrarily large
function such that $f(n)\gg g(n)$, which gives a loose lower bound on $\zeta$
which can be as large as exactly $1$.

Containment: To prove this we split the regime into the $n\geq n_{0}$ case and
the $n<n_{0}$ case, giving separate algorithms for both cases.

#####  $n<n_{0}$ case:

In this setting we have that $n\in[1,n_{0}]$, which is a bounded domain.
Therefore, we can run the algorithm considered in the proof of Theorem 5.1
with the worst case parameter settings on this interval, which is for
$\delta^{*}=\max_{n\in[n_{0}+1]}g(n)$ and $\zeta^{*}=\min_{n\in[n_{0}+1]}f(n)$
222222Since $n$ is a discrete variable on a bounded domain of constant size,
one can always solve these optimization problems in constant time by brute-
force search.. Since both $\delta^{*}$ and $\zeta^{*}$ are then constants,
this results in an algorithm that runs in a time polynomial in $n$ and, as
long as $1\leq n\leq n_{0}$, be able to distinguish between the yes and no-
cases.

#####  $n\geq n_{0}$ case:

The verifier expect to be given a $\text{desc}(u)$ such that
$|\bra{u}\ket{\phi_{0}}|^{2}\geq\zeta=1-1/f(n)$ and checks if
$\bra{u}H\ket{u}\leq a+1/f(n)$. Since $H$ is a sum of local terms, by Lemma
5.2 the verifier can efficiently calculate $\bra{u}H\ket{u}$ (since this is a
polynomial in $H$ of degree $1$) when given $\text{desc}(u)$. Let us now check
completeness and soundness of this simple protocol. By the definition of the
problem, we must have that $\norm{H}\leq 1$. We write
$\ket{u}=\alpha_{1}\ket{\phi_{0}}+\alpha_{2}\ket{\phi_{0}^{\perp}}$, where
$|\alpha_{1}|^{2}+|\alpha_{2}|^{2}=1$. Note that
$|\alpha_{2}|^{2}=1-\norm{\Pi_{\text{gs}}\ket{u}}^{2}\geq
1-\zeta\geq\frac{1}{f(n)}$. Therefore, we must have that in the yes-case

$\displaystyle\bra{u}H\ket{u}$
$\displaystyle=|\alpha_{1}|^{2}\bra{\phi_{0}}H\ket{\phi_{0}}+|\alpha_{2}|^{2}\bra{\phi_{0}^{\perp}}H\ket{\phi_{0}^{\perp}}$
$\displaystyle\leq
a+|\alpha_{2}|^{2}\bra{\phi_{0}^{\perp}}H\ket{\phi_{0}^{\perp}}$
$\displaystyle\leq a+\norm{H}/f(n)$ $\displaystyle\leq a+1/f(n).$

In the no-case, we can simply evoke the variational principle

$\displaystyle\bra{u}H\ket{u}$ $\displaystyle\geq\lambda_{0}(H)\geq
b=a+1/g(n)\geq a+1/f(n)+\Omega(1/exp(n)),$

for all $\ket{u}$. Therefore, both cases are inverse exponentially separated,
and can therefore be distinguished from one another. ∎

##  6 Quantum-classical probabilistically checkable proofs

In this section we initiate the study of a new complexity class that sits
right between the classical and quantum PCPs. First, let us recall some basic
definitions and facts about PCPs.

######  Definition 6.1 (Probabilistically checkable proofs (PCPs)).

Let $n\in\mathbb{N}$ be the input size and
$q:\mathbb{N}\rightarrow\mathbb{N},r:\mathbb{N}\rightarrow\mathbb{N}$. A
promise problem $A=(A_{\text{yes}},A_{\text{no}})$ has a
$(r(n),q(n))$-$\mathsf{PCP}$ verifier if there exists a polynomial-time
probabilistic algorithm $V$ which takes an input $x\in\\{0,1\\}^{n}$, and has
random access to a string $\pi\in\\{0,1\\}^{*}$ of length at most
$q(n)2^{r(n)}$, uses at most $r(n)$ random coins and makes at most $q(n)$ non-
adaptive queries to locations of $\pi$, such that

  * •

Completeness. If $x\in A_{\text{yes}}$, then there is a proof $\pi$ such that
$V^{\pi}(x)$ accepts with certainty.

  * •

Soundness. If $y\in A_{\text{no}}$, then for all proofs $\pi$ we have that
$V^{\pi}(x)$ accepts with probability at most $\frac{1}{2}$.

A promise problem $A=(A_{\text{yes}},A_{\text{no}})$ belongs to
$\mathsf{PCP}[q,r]$ if it has a $(r(n),q(n))$-$\mathsf{PCP}$ verifier.

The celebrated PCP theorem states that
$\mathsf{NP}=\mathsf{PCP}[\mathcal{O}(1),\mathcal{O}(\log n)]$ [ALM+98, AS98].
It also implies that there exists a constant $\alpha$ such that it is
$\mathsf{NP}$-hard to decide for a constraint satisfaction problem with
‘promise gap’ $\alpha$. Dinur [Din07] showed that this implication can be
obtained directly, by reducing from a constraint satisfaction problem with
inverse polynomial promise gap to one with a constant promise gap, whilst
retaining $\mathsf{NP}$-hardness. This type of reduction is commonly referred
to as gap amplification.

A quantum variant to $\mathsf{PCP}$ can naturally be defined as follows
[AALV09, AAV13].

######  Definition 6.2 (Quantum Probabilistically Checkable Proofs
($\mathsf{QPCP}$)).

Let $n\in\mathbb{N}$ be the input size and
$p,q:\mathbb{N}\rightarrow\mathbb{N}$, $c,s:\mathbb{R}_{\geq
0}\rightarrow\mathbb{R}_{\geq 0}$ with $c-s>0$. A promise problem
$A=(A_{\text{yes}},A_{\text{no}})$ has a
$(p(n),q(n),c,s)$-$\mathsf{QPCP}$-verifier if there exists a quantum algorithm
$V$ which acts on an input $\ket{x}$ and a polynomial number of ancilla
qubits, and takes an additional input a quantum state
$\ket{\xi}\in\mathbb{C}^{2^{p(n)}}$, from which it is allowed to access at
most $q(n)$ qubits, followed by a measurement of the first qubit after which
it accepts only if the outcome is $\ket{1}$, such that

  * Completeness. If $x\in A_{\text{yes}}$, then there is a quantum state $\ket{\xi}$ such that the verifier accepts with probability at least $c$,

  * Soundness. If $y\in A_{\text{no}}$, then for all quantum states $\ket{\xi}$ the verifier accepts with probability at most $s$.

A promise problem $A=(A_{\text{yes}},A_{\text{no}})$ belongs to
$\mathsf{QPCP}[p,q,c,s]$ if it has a $(p(n),q(n),c,s)$-$\mathsf{QPCP}$
verifier. If $p(n)\leq\mathop{poly}(n)$, $c=2/3$, and $s=1/3$, we simply write
$\mathsf{QPCP}[q]$.

And likewise, there is a formulation of the quantum PCP conjecture, using the
above notion quantum probabilistically checkable proofs (QPCPs).

######  Conjecture 6.1 (QPCP conjecture - proof verification version).

There exists a constant $q\in\mathbb{N}$ such that

$\displaystyle\mathsf{QMA}=\mathsf{QPCP}[q].$

As in the classical PCP theorem, there exist equivalent formulations of the
QPCP conjecture. In particular, one can formulate the PCP theorem in terms of
_inapproximability_ of constraint satisfaction problems (CSPs), analogously to
the classical setting. In the context of the quantum complexity classes
(notably $\mathsf{QMA}$), ‘quantum’ CSPs are generalized by local Hamiltonian
problems. The formulation of the quantum PCP conjecture in terms of
inapproximability of local Hamiltonians is:

######  Conjecture 6.2 (QPCP conjecture - gap amplification version).

There exists a (quantum) reduction from the local Hamiltonian problem with
promise gap $\Omega(1/\mathop{poly}(n))$ to another instance of the local
Hamiltonian problem with promise gap $\Omega(1)$.

It is well known that, at least under _quantum reductions_ , both conjectures
are in fact equivalent:

######  Fact 6.1 ([AALV09]).

Conjecture 6.1 holds if and only if conjecture 6.2 holds.

###  6.1 Quantum-classical PCPs

We now consider the notion of a quantum PCP conjecture that, intuitively,
conjectures the existence of polynomial-time quantum verifiers for
$\mathsf{QCMA}$ problems that need only check a constant number of (the now
classical) bits of the proof to satisfy constant completeness and soundness
requirements. More formally, this reads as:

######  Definition 6.3 (Quantum-Classical Probabilistically Checkable Proofs
($\mathsf{QCPCP}$)).

Let $n\in\mathbb{N}$ be the input size and
$p,q:\mathbb{N}\rightarrow\mathbb{N}$, $c,s:\mathbb{R}_{\geq
0}\rightarrow\mathbb{R}_{\geq 0}$ with $c-s>0$. . A promise problem
$A=(A_{\text{yes}},A_{\text{no}})$ has a
$(p(n),q(n),c,s)$-$\mathsf{QCPCP}$-verifier if there exists a quantum
algorithm $V$ which acts on an input $\ket{x}$ and a polynomial number of
ancilla qubits, plus an additional bit string $y\in\\{0,1\\}^{2^{p(n)}}$ from
which it is allowed to read at most $q(n)$ bits (non-adaptively), followed by
a measurement of the first qubit, after which it accepts only if the outcome
is $\ket{1}$, and satisfies:

  * Completeness. If $x\in A_{\text{yes}}$, then there is a basis state state $\ket{y}$ such that the verifier accepts with probability at least $c$,

  * Soundness. If $y\in A_{\text{no}}$, then for all basis states $\ket{y}$ the verifier accepts with probability at most $s$.

A promise problem $A=(A_{\text{yes}},A_{\text{no}})$ belongs to
$\mathsf{QCPCP}[p,q,c,s]$ if it has a $(p(n),q(n),c,s)$-$\mathsf{QCPCP}$
verifier. If $p(n)=\mathcal{O}(\mathop{poly}(n))$, $c=2/3$, and $s=1/3$, we
simply write $\mathsf{QCPCP}[q]$.

We remark that there are likely several ways to characterise a PCP for
$\mathsf{QCMA}$, with some being more or less natural than others. With that
said, we believe that the above characterisation is well-motivated for the
following reasons:

  1. 1.

It is a natural definition following the structure of a $\mathsf{QPCP}$
verifier as in Definition 6.2, now with proofs given as in the standard
definition of $\mathsf{QCMA}$ (see Definition 2.5).

  2. 2.

$\mathsf{QCPCP}[\mathcal{O}(1)]$ captures the power of $\mathsf{BQP}$ as well
as $\mathsf{NP}$ (via the PCP theorem), which are both believed to be strictly
different complexity classes. Since techniques used to prove the PCP theorem
are difficult (or impossible) to translate to the quantum setting [AAV13],
studying $\mathsf{QCPCP}[\mathcal{O}(1)]$ might provide a fruitful direction
with which to obtain the first non-trivial lower bound on the complexity of
$\mathsf{QPCP}[\mathcal{O}(1)]$. Indeed, the currently best known lower bound
on the complexity of $\mathsf{QPCP}[\mathcal{O}(1)]$ is $\mathsf{NP}$ via the
PCP theorem, so does not yet even capture $\mathsf{BQP}$.

Given this definition for QCPCPs, our ‘quantum-classical’ PCP conjecture is
naturally formulated as follows.

######  Conjecture 6.3 (quantum-classical PCP conjecture).

There exists a constant $q\in\mathbb{N}$ such that

$\displaystyle\mathsf{QCMA}=\mathsf{QCPCP}[q].$

Figure 5:  Known inclusions between some complexity classes and our proposed
class $\mathsf{QCPCP}[k]$, with $k=\mathcal{O}(1)$. A line drawn from
complexity class $A$ to another class $B$, where $B$ is placed above $A$ means
that $A\subseteq B$. Note that the complexity of our proposed class
$\mathsf{QCPCP}[\mathcal{O}(1)]$ is non-trivial, as it contains both
$\mathsf{NP}$ and $\mathsf{BQP}$ for which it is believed that both
$\mathsf{BQP}\not\subset\mathsf{NP}$ and $\mathsf{BQP}\not\supset\mathsf{NP}$.

If true, this conjecture would give a ‘$\mathsf{QCMA}$ lower bound’ on the
power of quantum PCP systems, showing that a PCP theorem holds for (quantum)
classes above $\mathsf{NP}$, taking a step towards proving the quantum PCP
conjecture. If it is false, but the quantum PCP conjecture is true, then this
suggests that $\mathsf{QPCP}$ systems must take advantage of the quantumness
of their proofs to obtain a probabilistically checkable proof system. In
particular, since $\mathsf{QCMA}\subseteq\mathsf{QMA}$, this would imply the
existence of a quantum PCP system for every problem in $\mathsf{QCMA}$, but
_not_ a quantum-classical one, even though the problem admits a classical
proof that can be efficiently verified when we are allowed to look at all of
its bits.

Note that we have that $\mathsf{QCPCP}[\mathcal{O}(1)]$ trivially contains
$\mathsf{CGaLH}(k,\zeta,\delta)$ whenever $k=\mathcal{O}(\log n)$
$\zeta=\Omega(1)$ and $\delta=\Omega(1)$, since we have shown in Theorem 5.2
that this problem is in $\mathsf{NP}$ and therefore admits a classical PCP
system to solve the problem. This would not apriori be clear if we considered
guiding states as in Definition 3.1, as we do not know a PCP for the class
$\mathsf{MA}$.

####  6.1.1 Useful facts about $\mathsf{QCPCP}$

We begin by showing two basic properties of $\mathsf{QCPCP}$, which we make
use of later on. First, we show the simple fact that $\mathsf{QCPCP}$, just as
is the case for $\mathsf{PCP}$, allows for error reduction at the cost of
extra queries to the proof.

######  Proposition 6.1 (Strong error reduction for $\mathsf{QCPCP}$).

The completeness and soundness parameters in $\mathsf{QCPCP}$ can be made
exponentially close in some $t\in\mathbb{N}$ to $1$ and $0$, respectively,
i.e. $c=1-2^{-\mathcal{O}(t)}$ and $s=2^{-\mathcal{O}(t)}$, by making $tq$
instead of $q$ queries to the classical proof.

###### Proof.

This follows from a standard parallel repetition argument, running the
$\mathsf{QCPCP}$ protocol $t$ times in parallel and taking a majority vote on
the outcomes. Since the proof is classical, it does not matter if the same
parts of the proof are queried multiple times by different runs, unlike the
case when the proof is quantum. By taking a majority vote on the $t$ outcomes,
this yields the desired result by a Chernoff bound. ∎

Figure 6: General quantum circuits for nonadaptive QCPCPs
($\mathsf{QCPCP}[q]$, top) versus adaptive ones ($\mathsf{QCPCP}_{A}[q]$,
bottom). When we talk about making a ‘query’ to the classical proof we mean a
single read/write procedure, where a single proof bit is read from the proof
and then used to initialise a qubit into the basis state corresponding to the
value of the bit. To determine which part of the proof must be read, a
measurement of some designated index qubits is performed, which outputs a
basis state(s) corresponding to index (indices) of the proof. The entire post-
measurement state is allowed to be an input to a subsequent quantum circuit.

Second, we show that when one is interested in
$\mathsf{QCPCP}[\mathcal{O}(1)]$, the non-adaptiveness restriction in the
definition does not limit the power of the class. The proof of this is similar
to how one would prove it for $\mathsf{PCP}[\mathcal{O}(1),\mathcal{O}(\log
n)]$, but encounters one difficulty. In the classical setting, the
probabilistic PCP verifier can be replaced by a deterministic one that has an
auxiliary input for a string which is taken uniformly at random. This way, one
can ‘fix the randomness’ in the verifier, and the queries to the proof form a
decision tree on the choices over the values of the proof bits, of which only
one path can correspond to the actual proof. However, in the quantum setting
there is no such equivalent notion of ‘fixing quantumness’, and therefore at
every step the circuit might output different values for the indices of the
proof that are supposed to be queried, even when all preceding steps gave the
same indices and yielded identical values for the proof queries as compared to
another run. Fortunately, it is easy to fix this by simply running the circuit
many times in a simulated manner, using randomly chosen ‘fake’ proof bits. The
probability that one matches the actual proof bits with the randomly chosen
ones is small, but still constant when the number of queries to the proof is
constant. We formalize this in the following theorem.

######  Theorem 6.1.

Let $\mathsf{QCPCP}_{A}$ be just as $\mathsf{QCPCP}$ but with the power to
make adaptive queries to the proof. We have that

$\displaystyle\mathsf{QCPCP}[\mathcal{O}(1)]=\mathsf{QCPCP}_{A}[\mathcal{O}(1)].$

###### Proof.

The ‘$\subseteq$’ is trivial since adaptive queries generalise non-adaptive
ones, so we only have to show ‘$\supseteq$’. Let $V$ be the circuit
description of an adaptive $\mathsf{QCPCP}[\mathcal{O}(1)]$ protocol which
makes $q$ queries to a classical proof $y$. W.l.o.g., we can view $V$ as a
quantum circuit that consists of applying a unitary $V_{0}$ to the input and
some ancilla qubits all initialized in $\ket{0}$, followed by a measurement to
determine which bit of the proof to read, after which a new qubit is
initialized in the basis state corresponding to the proof bit value, followed
by another unitary $V_{1}$ that acts on all qubits, and so on, until at the
end a measurement of a single designated output qubit is performed to decide
whether to accept or reject (see Figure 6). We can simulate $V$ on proof $y$
non-adaptively in the following way. For a total of $T=C2^{q}$ times, with
$C>1$ some constant, we pick a $z\in\\{0,1\\}^{q}$ uniformly at random, and
run circuit $V$ where the answers to the proof queries are taken to be the
bits of $z$. The final output qubit is measured as usual. This yields a total
of $T$ tuples $(z,i_{1},\dots,i_{q},o)$, where the first entry indicates the
value of the sampled $z\in\\{0,1\\}^{q}$, the second the $q$ indices of the
bits that were supposed to be queried by $V$, and the third the outcome of the
final measurement, which has $o=1$ if the circuit accepted and $o=0$ if it
rejected. For all $T$ simulations, we can check if each
$(z,i_{1},\dots,i_{q})$ is consistent with the actual proof $y$, i.e. whether
$z_{i_{l}}=y_{i_{l}}$ for all $l\in[q]$, which requires at most
$qT=qC2^{q}=\mathcal{O}(1)$ queries to $y$. Since the probability that a
randomly selected $z$ is consistent with the proof $y$ is $1/2^{q}$, we have
that the probability that at least one of the $z$ values in the tuples is
consistent with the proof satisfies

$\displaystyle\mathbb{P}[\text{At least one $z_{i_{1}},\dots,z_{i_{q}}$
consistent with $y$}]\geq 1-\left(1-\frac{1}{2^{q}}\right)^{T}\geq
1-\frac{1}{1+\frac{T}{2^{q}}}=\frac{T}{2^{q}+T}=\frac{C}{1+C}.$

Now we loop over all collected tuples, and for the first tuple we encounter
that is consistent with the proof we check $o$: if $o=1$ we accept, and if
$o=0$ we reject. If all of the tuples are inconsistent with the proof, we
reject. Hence, if the $\mathsf{QCPCP}_{A}$ protocol has completeness $c$ and
soundness $s$, this $\mathsf{QCPCP}$ protocol has completeness
$c^{\prime}=2C/3(1+C)$ and soundness $1/3$. We then have that the yes\- and
no-cases are separated by at least

$\displaystyle\frac{2C}{3(1+C)}-\frac{1}{3}=\Omega(1).$

if $C>1$. This can easily be boosted such that the completeness and soundness
are $\geq 2/3$ and $\leq 1/3$ at the cost of a constant multiplicative factor
in the number of queries, by adopting the strong error reduction of
Proposition 6.1. Hence,
$\mathsf{QCPCP}[\mathcal{O}(1)]\supseteq\mathsf{QCPCP}_{A}[\mathcal{O}(1)]$,
completing the proof. ∎

######  Remark 6.1.

The above proof actually holds for all quantum algorithms that have ‘non-
quantum’ query access to a classical string and make only a constant of such
queries.

There is an interesting observation one can make when looking more closely at
the proof of Theorem 6.1: the resulting non-adaptive protocol employs a
quantum circuit only for generating indices/output data needed for queries
from the proof. Hence, once the queries are made, all subsequent checks can be
performed classically. This means a quantum-classical PCP that is restricted
to only using quantum circuits before the proof is accessed is just as
powerful as the more general definition as per Definition 6.3. In the next
subsection we will see that this idea allows one to put a non-trivial upper
bound on the complexity of QCPCPs that make only a constant number of queries
to the proof.

###  6.2 Upper bound on $\mathsf{QCPCP}$ with constant proof queries

Here we show that $\mathsf{QCPCP}$ with a constant number of proof queries is
contained in $\mathsf{BQP}^{\mathsf{NP}[1]}$, i.e. in $\mathsf{BQP}$ with only
a single query to an $\mathsf{NP}$-oracle. The proof is rather long, but the
idea is simple: just as is the case for $\mathsf{QPCP}$, a _quantum_ reduction
can be used to transform a $\mathsf{QCPCP}$ system into a local Hamiltonian
problem. However, since the proof is now classical, we can either use the
CNOT-trick of Lemma 4.1 to ensure that the resulting Hamiltonian problem is
diagonal in the computational basis, or directly learn a diagonal (i.e.
classical) Hamiltonian that captures the input/output behaviour of the
$\mathsf{QCPCP}$-circuit on basis state inputs.232323We use the language of
Hamiltonians here to be consistent with the $\mathsf{QPCP}$ setting, but this
is not necessary. Since the Hamiltonian is classical, we might as well say
that we learn a polynomial $P:\\{0,1\\}^{p(n)}\rightarrow\mathbb{R}_{\geq 0}$.
The main technical work required is to derive sufficient parameters in the
reduction, thereby ensuring that the reduction succeeds with the desired
success probability. We first prove a lemma which upper bounds the norm
difference between a certain ‘learned’ Hamiltonian satisfying certain accuracy
constraints, and the actual Hamiltonian.

######  Lemma 6.1.

Let $H=\sum_{i\in[m]}w_{i}H_{i}$ be a $k$-local Hamiltonian consisting of
weights $w_{i}\in[0,1]$ such that $\sum_{i\in[m]}w_{i}=W$, and $k$-local terms
$H_{i}$ for which $\norm{H_{i}}\leq 1$ for all $i\in[m]$. Let
$\Omega_{\geq\gamma}=\\{i|w_{i}\geq\gamma\\}$ and
$\Omega_{<\gamma}=[m]\setminus\Omega_{\geq\gamma}$, for some parameter
$\gamma\in[0,1]$. Suppose
$\tilde{H}=\sum_{i\in\Omega_{\geq\gamma}}\tilde{w}_{i}\tilde{H}_{i}$ is
another Hamiltonian such that, for all $i\in\Omega_{\geq\gamma}$, we have
$\absolutevalue{\tilde{w}_{i}-w_{i}}\leq\epsilon_{0}$ and
$\norm{H_{i}-\tilde{H}_{i}}\leq\epsilon_{1}$. Then

$\displaystyle\norm{H-\tilde{H}}\leq
m(\gamma+\epsilon_{0})+(W+m\epsilon_{0})\epsilon_{1}$

###### Proof.

$\displaystyle\norm{H-\tilde{H}}$
$\displaystyle=\norm{\sum_{i\in\Omega_{\geq\gamma}}\tilde{w}_{i}\tilde{H}_{i}-\sum_{i\in[m]}w_{i}H_{i}}$
$\displaystyle\leq\sum_{i\in\Omega_{\geq\gamma}}\norm{\tilde{w}_{i}\tilde{H}_{i}-w_{i}H_{i}}+\norm{\sum_{i\in\Omega_{<\gamma}}w_{i}H_{i}}$
$\displaystyle\leq
m\gamma+\sum_{i\in\Omega_{\geq\gamma}}\norm{\tilde{w}_{i}\tilde{H}_{i}-w_{i}H_{i}}$
$\displaystyle\leq
m\gamma+\sum_{i\in\Omega_{\geq\gamma}}\norm{\tilde{w}_{i}\left(\tilde{H}_{i}-{H}_{i}\right)+H_{i}\left(\tilde{w}_{i}-w_{i}\right)}$
$\displaystyle\leq
m\gamma+\sum_{i\in\Omega_{\geq\gamma}}\norm{\tilde{w}_{i}\left(\tilde{H}_{i}-{H}_{i}\right)}+\norm{H_{i}\left(\tilde{w}_{i}-w_{i}\right)}$
$\displaystyle\leq
m\gamma+\sum_{i\in\Omega_{\geq\gamma}}\tilde{w}_{i}\norm{\tilde{H}_{i}-{H}_{i}}+\norm{H_{i}}\absolutevalue{\tilde{w}_{i}-w_{i}}$
$\displaystyle\leq
m\gamma+\sum_{i\in\Omega_{\geq\gamma}}\left(w_{i}+\epsilon_{0}\right)\epsilon_{1}+\epsilon_{0}$
$\displaystyle\leq m(\gamma+\epsilon_{0})+(W+m\epsilon_{0})\epsilon_{1},$

where in going from line $1$ to line $2$ we used the triangle inequality and
the definition of $\Omega_{\geq\gamma}$, from line $3$ to $4$ again the
definition of $\Omega_{\geq\gamma}$, from line $4$ to line $5$ the triangle
inequality, from line $5$ to $6$ the absolute homogeneity of the norm, from
$6$ to $7$ and $7$ to $8$ the properties on norm and absolute value
differences as stated in the lemma. ∎

We will also use the fact that the learning of the Hamiltonian parameters in
the reduction can be viewed as the well-known ‘Double dixie cup’ problem
[New60]. In this problem, which is a generalization of the coupon collector
problem, a collector wants to obtain $m$ copies of each element from a set of
$n$ elements, via a procedure where every item is sampled with equal
probability. In our setting, we have that the probability over the items is
non-uniform. However, it is straightforward to obtain an upper bound on the
non-uniform double dixie cup problem in terms of the expectation value in the
uniform setting, as illustrated by the following lemma:

######  Lemma 6.2 (Upper bound on the non-uniform double dixie cup problem).

Given samples from the set $S_{n}=[n]$, according to a distribution
$\mathcal{P}$, where $\min_{i\in[n]}\mathcal{P}(i)\geq\gamma$, let
$T^{\mathcal{P}}_{m}(S_{n})$ be the random variable indicating the first time
that all elements in $S_{n}$ have been sampled at least $m$ times according to
distribution $\mathcal{P}$. We write $T_{m}(S_{n})$ when the distribution over
$S_{n}$ is uniform. We have that

$\displaystyle\mathbb{E}[T^{\mathcal{P}}_{m}(S_{n})]\leq\mathbb{E}[T_{m}(S_{\lceil
1/\gamma\rceil})],$

where $S_{\lceil 1/\gamma\rceil}=[\lceil 1/\gamma\rceil]$ and

$\displaystyle\mathbb{E}[T_{m}(S_{\lceil 1/\gamma\rceil})]=\lceil
1/\gamma\rceil\ln\lceil 1/\gamma\rceil+(m-1)\lceil 1/\gamma\rceil\ln\ln\lceil
1/\gamma\rceil+\mathcal{O}\left(\lceil 1/\gamma\rceil\right).$

###### Proof.

W.l.o.g., let the first $n$ items of $S_{\lceil 1/\gamma\rceil}$ correspond to
the items in $S_{n}$. We have for all $i\in[n]$ that
$\mathcal{P}(i)\geq\gamma\geq\mathbb{P}[\text{sample $i$ from $S_{\lceil
1/\gamma\rceil}$}]$. Hence, if we have seen all elements of $S_{\lceil
1/\gamma\rceil}$ at least $m$ times, we also have seen all elements of $S_{n}$
at least $m$ times, from which it follows that

$\displaystyle\mathbb{E}[T^{\mathcal{P}}_{m}(n)]\leq\mathbb{E}[T_{m}(S_{\lceil
1/\gamma\rceil})],$

where

$\displaystyle\mathbb{E}[T_{m}(S_{\lceil 1/\gamma\rceil})]=\lceil
1/\gamma\rceil\ln\lceil 1/\gamma\rceil+(m-1)\lceil 1/\gamma\rceil\ln\ln\lceil
1/\gamma\rceil+\mathcal{O}\left(\lceil 1/\gamma\rceil\right)$

is by the result of [New60]. ∎

We are now in a position to show the quantum reduction, which proceeds by
learning the probability distribution over which indices of the proof string
are queried by the verifier circuit, as well as the probability that the
verification circuit $V$ of the QCPCP-verifier accepts when those proof bits
take on particular values.

######  Lemma 6.3.

Let $q\in\mathbb{N}$ be some constant and $x$ an input with $|x|=n$. Consider
a $\mathsf{QCPCP}[q]$ protocol with verification circuit $V_{x}$ (which is $V$
but with the input $x$ hardcoded into the circuit), and proof
$y\in\\{0,1\\}^{p(n)}$, and let

$\displaystyle\mathcal{P}_{x}(i_{1},\dots,i_{q})=\mathbb{P}[V_{x}\text{
queries the proof at indices }(i_{1},\dots,i_{q})]$

and

$\displaystyle\lambda_{x,(i_{1},\dots,i_{q})}(z)=\mathbb{P}[V_{x}\text{
accepts given proof bits $i_{1},\dots,i_{q}$ are queried and are given by
$y_{i_{1}}=z_{1},\dots,y_{i_{q}}=z_{q}$}].$

Let $\Omega=[(i_{1},\dots,i_{q}):i_{j}\in[p(n)],\forall j\in[q]]$,
$\Omega_{\geq\gamma}=\\{(i_{1},\dots,i_{q})\in\Omega|\mathcal{P}_{x}(i_{1},\dots,i_{q})\geq\gamma\\}$
and $\Omega_{<\gamma}=\Omega\setminus\Omega_{\geq\gamma}$, for some parameter
$\gamma\in[0,1]$. Then there exists a quantum algorithm that, for all
$(i_{1},\dots,i_{q})\in\Omega_{\geq\gamma}$ and all $z\in\\{0,1\\}^{q}$,
provides estimates $\tilde{\mathcal{P}}_{x}(i_{1},\dots,i_{q})$ and
$\tilde{\lambda}_{x,(i_{1},\dots,i_{q})}(z)$ such that

$\displaystyle\absolutevalue{\tilde{\mathcal{P}}_{x}(i_{1},\dots,i_{q})-\mathcal{P}_{x}(i_{1},\dots,i_{q})}\leq\epsilon_{0},$

and

$\displaystyle\absolutevalue{\tilde{\lambda}_{x,(i_{1},\dots,i_{q})}(z)-{\lambda}_{x,(i_{1},\dots,i_{q})}(z)}\leq\epsilon_{1},$

with probability $1-\delta$, and runs in time
$\leq\mathop{poly}(n,1/\gamma,\epsilon_{0},\epsilon_{1},1/\delta)$.

###### Proof.

Let $t\in[T]$ for some $T\in\mathbb{N}$ to be specified later, and let
$O^{t,z}=((i^{t,z}_{1},\dots,i^{t,z}_{k}),o^{t,z})$ be the tuple resulting
from the $t$’th simulation of $V_{x}$, in which the proof $y$ was supposed to
be queried at indices $i_{1},\dots,i_{q}$ and in which those bits were
assigned the values $y_{i_{1}}=z_{1},\dots,y_{i_{q}}=z_{q}$. Now consider the
following quantum algorithm:

  * •

For $z\in\\{0,1\\}^{q}$:

    * –

Simulate $V$ for a total of $T$ times to obtain samples
$\\{O^{t,z}\\}_{t\in[T]}$.

    * –

For all observed $(i_{1}^{t,z},\dots,i_{q}^{t,z})$, set

$\displaystyle\tilde{\lambda}_{x,(i_{1},\dots,i_{q})}(z):=\frac{\text{\text{\\#
times $o^{t,z}=1|i_{1},\dots,i_{q}$ observed }}}{\text{\\# times
$i_{1},\dots,i_{q}$ observed }}.$

  * •

For all observed $(i_{1}^{t,z},\dots,i_{q}^{t,z})$, set

$\displaystyle\tilde{\mathcal{P}}_{x}(i_{1},\dots,i_{q})=\sum_{z\in\\{0,1\\}^{q}}\frac{\text{\\#
times $(i_{1}^{t,z},\dots,i_{q}^{t,z})$ observed}}{2^{q}T}.$

The intuition is that in each tuple $\\{O^{t,z}\\}_{t\in[T]}$, the
$(i_{1}^{t,z},\dots,i_{q}^{t,z})$ give us information to estimate the
${\mathcal{P}_{x}}(i_{1},\dots,i_{q})$’s and the combination
$(i_{1}^{t,z},\dots,i_{q}^{t,z}),o^{t,z}$ allows us to estimate the
${\lambda}_{x,(i_{1},\dots,i_{q})}(z)$’s. Let us now show that there exists a
$T$ not too large such that the criteria of the theorem are satisfied. Since
the $\mathcal{P}_{x}(i_{1},\dots,i_{q})$ form a discrete distribution over the
set $\Omega$, we know by a standard result in learning theory (see for example
[Can20]) that a total of

$\displaystyle\Theta\left(\frac{|\Omega|+\log(1/\delta_{0})}{\epsilon_{0}^{2}}\right)$

samples of $O^{t,z}$ (the ‘$z$’-value is in fact irrelevant here) suffices to
get, with probability at least $1-\delta_{0}$, estimates
$\tilde{\mathcal{P}}_{x}(i_{1},\dots,i_{q})$ which satisfy

$\displaystyle\absolutevalue{\tilde{\mathcal{P}}_{x}(i_{1},\dots,i_{q})-\mathcal{P}_{x}(i_{1},\dots,i_{q})}\leq\epsilon_{0}.$

To learn estimates $\tilde{\lambda}_{x,(i_{1},\dots,i_{q})}(z)$ for a single
index configuration $(i_{1},\dots,i_{q})$ and proof configuration $z$,
Hoeffding’s inequality tells us that we only need

$\displaystyle
S_{\lambda}:=\mathcal{O}\left(\frac{\log\left(1/\delta_{1}\right)}{\epsilon_{1}^{2}}\right)$

samples of $O^{t,z}$ to have that
$\absolutevalue{\tilde{\lambda}_{x,(i_{1},\dots,i_{q})}(z)-{\lambda}_{x,(i_{1},\dots,i_{q})}(z)}\leq\epsilon_{1},$
with probability $1-\delta_{1}$. By Lemma 6.2, we have that the expected
number of samples needed such that this condition is met for all
$i_{1},\dots,i_{q}\in\Omega_{\geq\gamma}$ is upper bounded by

$\displaystyle\left\lceil\frac{1}{\gamma}\right\rceil\ln\left\lceil\frac{1}{\gamma}\right\rceil+(S_{\lambda}-1)\left\lceil\frac{1}{\gamma}\right\rceil\ln\ln\left\lceil\frac{1}{\gamma}\right\rceil+\mathcal{O}\left(\left\lceil\frac{1}{\gamma}\right\rceil\right),$

which by Markov’s inequality means that

$\displaystyle\frac{1}{\delta_{\lambda}}\left(\left\lceil\frac{1}{\gamma}\right\rceil\ln\left\lceil\frac{1}{\gamma}\right\rceil+(S_{\lambda}-1)\left\lceil\frac{1}{\gamma}\right\rceil\ln\ln\left\lceil\frac{1}{\gamma}\right\rceil+\mathcal{O}\left(\left\lceil\frac{1}{\gamma}\right\rceil\right)\right)$

samples of $O^{t,z}$ suffice to turn this into an algorithm that achieves
success probability $\geq 1-\delta_{\lambda}$. To ensure that our entire
algorithm succeeds with probability $1-\delta$, we require that

$\displaystyle(1-\delta_{\lambda})^{2^{q}}(1-\delta_{0})(1-\delta_{1})^{2^{q}\left\lceil\frac{1}{\gamma}\right\rceil}\geq
1-\delta,$

which can be achieved by setting $\delta_{\lambda}=\delta/(2^{q+2})$,
$\delta_{0}=\delta/4$ and $\delta_{1}=\delta/(\lceil 1/\gamma\rceil 2^{q+2})$.
Then the total number of samples $T$ that we must take satisfies

$\displaystyle T$
$\displaystyle\leq\max\\{\Theta\left(\frac{\left\lceil\frac{1}{\gamma}\right\rceil+\log(1/\delta_{0})}{\epsilon_{0}^{2}}\right),\frac{2^{q}}{\delta_{\lambda}}\left(\left\lceil\frac{1}{\gamma}\right\rceil\ln\left\lceil\frac{1}{\gamma}\right\rceil+(T_{p}-1)\left\lceil\frac{1}{\gamma}\right\rceil\ln\ln\left\lceil\frac{1}{\gamma}\right\rceil+\mathcal{O}\left(\left\lceil\frac{1}{\gamma}\right\rceil\right)\right)\\}$
$\displaystyle\leq\max\\{\Theta\left(\frac{\left\lceil\frac{1}{\gamma}\right\rceil+\log\left(\frac{1}{\delta}\right)}{\epsilon_{0}^{2}}\right),\frac{2^{2(q+1)}}{\delta}\left(\left\lceil\frac{1}{\gamma}\right\rceil\ln\left\lceil\frac{1}{\gamma}\right\rceil+\mathcal{O}\left(\frac{q\log\left(\left\lceil\frac{1}{\gamma}\right\rceil/\delta\right)}{\epsilon_{1}^{2}}\right)\left\lceil\frac{1}{\gamma}\right\rceil\ln\ln\left\lceil\frac{1}{\gamma}\right\rceil\right)\\}$

which yields a total runtime of $\mathcal{O}(\mathop{poly}(n,\lceil
1/\gamma\rceil,1/\delta,1/\epsilon_{1},1/\epsilon_{0}))$ when
$q=\mathcal{O}(1)$. ∎

We now have all the ingredients to obtain the main result of this section.

######  Theorem 6.2.

For all constant $q\in\mathbb{N}$, we have that

$\displaystyle\mathsf{QCPCP}[q]\subseteq\mathsf{BQP}^{\mathsf{NP}[1]}.$

###### Proof.

Consider a QCPCP protocol with verification circuit $V_{x}$ (which is again
$V$ with input $x$ hardwired into the circuit) which makes $q=\mathcal{O}(1)$
non-adapative queries to a proof $y\in\\{0,1\\}^{p(n)}$. Let
$\ket{\psi}=\ket{x}\ket{0^{l(n)}}\ket{y}$. We have that242424We write
$1-\bra{y}H_{x}\ket{y}$ only to follow the convention that the local
Hamiltonian problem is usually stated as a minimization problem.

$\displaystyle\mathbb{P}[\mathsf{QCPCP}\text{ protocol accepts }y]$
$\displaystyle=\sum_{(i_{1},\dots,i_{q})\in\Omega}\mathcal{P}_{x}(i_{1},\dots,i_{q})\lambda_{x,(i_{1},\dots,i_{q})}(y_{i_{1}},\dots,y_{i_{q}})$
$\displaystyle=\bra{y}\sum_{(i_{1},\dots,i_{q})\in\Omega}\mathcal{P}_{x}(i_{1},\dots,i_{q})\sum_{z\in\\{0,1\\}^{q}}\lambda_{x,(i_{1},\dots,i_{q})}(z)|z\rangle\langle
z|\ket{y}$ $\displaystyle=1-\bra{y}H_{x}\ket{y},$

where $H_{x}$ is a Hamiltonian that is diagonal in the computational basis,
and takes the form

$\displaystyle
H_{x}=\sum_{(i_{1},\dots,i_{q})\in\Omega}\mathcal{P}_{x}(i_{1},\dots,i_{q})H_{x,(i_{1},\dots,i_{q})}\,,$

with $q$-local terms given by

$\displaystyle
H_{x,(i_{1},\dots,i_{q})}=\sum_{z\in\\{0,1\\}^{q}}(1-\lambda_{x,(i_{1},\dots,i_{q})}(z))|z\rangle\langle
z|.$

Here $\ket{z}\bra{z}$ should be read as $\ket{z}\bra{z}_{i_{1},\dots,i_{q}}$,
as it only acts on the $q$ qubits with indices $i_{1},\dots i_{q}$. By Lemmas
6.1, 6.2, and 6.3, there exists a polynomial-time quantum algorithm that finds
an estimated Hamiltonian

$\displaystyle\tilde{H}_{x}=\sum_{(i_{1},\dots,i_{q})\in\Omega_{\epsilon_{D}}}\tilde{\mathcal{P}}_{x}(i_{1},\dots,i_{q})\tilde{H}_{x,(i_{1},\dots,i_{q})},$

where

$\displaystyle\tilde{H}_{x,(i_{1},\dots,i_{q})}=\sum_{z\in\\{0,1\\}^{q}}(1-\tilde{\lambda}_{x,(i_{1},\dots,i_{q})})(z)|z\rangle\langle
z|\,,$

such that $\norm{\tilde{H}_{x}-H_{x}}\leq\epsilon$ with probability $\geq
1-\delta$. This means that with probability $\geq 1-\delta$, we have:

  * •

$x\in P_{\sc yes}\Rightarrow\exists
y\in\\{0,1\\}^{p(n)}:\bra{y}\tilde{H}_{x}\ket{y}\leq\frac{1}{3}+\epsilon$

  * •

$x\in P_{\sc no}\Rightarrow\forall
y\in\\{0,1\\}^{p(n)}:\bra{y}\tilde{H}_{x}\ket{y}\geq\frac{2}{3}-\epsilon$ .

Note that $\frac{1}{3}+\epsilon$ and $\frac{2}{3}-\epsilon$ are separated by a
constant for any constant $\epsilon<1/6$. Since our reduction created a
_diagonal_ (and thus classical) Hamiltonian, which is a
$\mathsf{CGaLH}(q,\zeta,\delta)$ instance with $\zeta=1$ and
$\delta=\Omega(1)$, the corresponding $q$-local Hamiltonian problem can be
solved in $\mathsf{NP}$.252525We would like to stress here that the
$\mathsf{NP}$ containment only holds because all complexity classes considered
are defined as classes of promise problems and not just languages. However,
the promise on the final diagonal Hamiltonian eigenvalue problem can be
removed by using that (i) every diagonal entry of each local term is only
learned to a certain number of bits of precision and (ii) the eigenvalues of a
sum of diagonal matrices are given by the sums of the eigenvalues (here we
have to consider the full matrix, so also with the tensored identities which
are left out in the notation). This way, one knows exactly what values the
eigenvalues of the final Hamiltonian can take, and one can simply modify the
completeness and soundness parameters such that they are both represented
exactly by a certain number of bits and have a promise gap which is given by
the difference between two successive numbers in the used binary
representation. The promise gap will shrink considerably (and no longer be
constant), but this is fine as the diagonal local Hamiltonian problem will
still be in $\mathsf{NP}$ (it is even for an exponentially small promise gap).
The $\mathsf{BQP}^{\mathsf{NP}[1]}$ protocol would then consist of performing
the quantum reduction to obtain the $\mathsf{CGaLH}(q,\zeta,\delta)$ instance,
followed by a single call to an $\mathsf{NP}$ oracle. This protocol succeeds
with the same success probability as the reduction (which can be made
exponentially close to $1$ with polynomial overhead), which ensures
completeness $\geq 1-\delta\geq 2/3$ and soundness $\leq\delta\leq 1/3$ for
any $\delta\leq 1/3$.

∎

The above theorem yields an interesting implication in a world where the
quantum-classical PCP conjecture is true, as illustrated by the following
corollary.

######  Corollary 6.1.

If Conjecture 6.3 is true, then we have that
$\mathsf{NP}^{\mathsf{BQP}}\subseteq\mathsf{BQP}^{\mathsf{NP}}$.

###### Proof.

We only have to show that $\mathsf{NP}^{\mathsf{BQP}}\subseteq\mathsf{QCMA}$,
since if Conjecture 6.3 is true it implies that
$\mathsf{QCMA}\subseteq\mathsf{QCPCP}\subseteq\mathsf{BQP}^{\mathsf{NP}[1]}\subseteq\mathsf{BQP}^{\mathsf{NP}}$
by Theorem 6.2. Let $q(n):\mathbb{N}\rightarrow\mathbb{N}$ be a polynomial and
$M^{\Pi}(x,y)$ be a deterministic polynomial-time verification circuit that
uses as an additional input a proof $y$ and make queries to a $\mathsf{BQP}$
oracle $\Pi=(\Pi_{\text{yes}},\Pi_{\text{no}},\Pi_{\text{inv}})$ at most
$q(n)$ times as a black box. We define $z\in\\{0,1,\perp\\}^{q(n)}$ as the
string that describes the sets that each query input belonged to (here
‘$\perp$’ indicates $\Pi_{\text{inv}}$). Define $I=\\{i:z_{i}=0\text{ or
}z_{i}=1\\}$. Since $M^{\Pi}$ is deterministic, we have that any string
$z^{\prime}$ that matches $z$ on all indices $I$ must produce the same output,
so all of such $z^{\prime}$s can be considered correct query strings. For each
$i\in I$, a $\mathsf{QCMA}$ verifier can, conditioned on all previous $z_{j}$
for $j<i$ being computed such that it matches the first $i-1$ bits of a
correct query string, perform the $\mathsf{BQP}$ computation required to
compute $z_{i}$ with success probability exponentially close to $1$ (this
follows by the fact that $\mathsf{BQP}$ allows for probability amplification).
If $i\in[q(n)]\setminus I$, any output will match in a correct query string in
this case. Since there are a total of $q(n)\leq\mathop{poly}(n)$ such queries,
the overall success probability of simulating a query sequence can be made
$\geq 2/3$. The $\mathsf{QCMA}$ protocol then simply simulates $M^{\Pi}$ by
executing all operations in $M$ directly and replacing every oracle call by a
direct $\mathsf{BQP}$-computation, which can be easily made to succeed with
success probability $\geq 2/3$, ensuring completeness and soundness. ∎

An implication of Corollary 6.1 is that it can be used to show that under the
assumption $\mathsf{NP}\subseteq\mathsf{BQP}$ and the quantum-classical PCP
conjecture being true, we have that $\mathsf{PH}\subseteq\mathsf{BQP}$, where
the class $\mathsf{PH}$ is the union of all complexity classes in the
polynomial hierarchy, i.e.
$\mathsf{PH}=\mathsf{P}^{\mathsf{NP}^{\mathsf{NP}^{\dots}}}$. This follows
from

$\displaystyle\mathsf{NP}^{\mathsf{NP}}\subseteq\mathsf{NP}^{\mathsf{BQP}}\subseteq\mathsf{BQP}^{\mathsf{NP}}\subseteq\mathsf{BQP}^{\mathsf{BQP}}=\mathsf{BQP},$

where the first and the third ‘$\subseteq$’ are by assumption, the second is
by the assumption of Conjecture 6.3 to be true and the last equality follows
from the fact that $\mathsf{BQP}$ is self-low. We then have that
$\mathsf{PH}\subseteq\mathsf{BQP}$ follows by induction, just as is the case
for $\mathsf{BPP}$ [Zac88].262626See also
https://blog.computationalcomplexity.org/2005/12/pulling-out-quantumness.html.
Moreover, this would also imply that under these assumptions
$\mathsf{QCMA}\subseteq\mathsf{BQP}$, since

$\displaystyle\mathsf{QCMA}\subseteq\mathsf{QCPCP}[\mathcal{O}(1)]\subseteq\mathsf{BQP}^{\mathsf{NP}}\subseteq\mathsf{BQP}^{\mathsf{BQP}}\subseteq\mathsf{BQP}.$

Both of these implications would provide further evidence that it is unlikely
that $\mathsf{BQP}\subseteq\mathsf{NP}$.

It is known that there exists an oracle relative to which the conclusion of
Corollary 6.1 is not true, i.e. there exists an oracle $A$ relative to which
$\mathsf{NP}^{\mathsf{BQP}^{A}}\not\subset\mathsf{BQP}^{\mathsf{NP}^{A}}$
[AIK21]. Nevertheless, this does not necessarily mean the premise (i.e. the
quantum-classical PCP conjecture) is false: one can also easily construct an
oracle separation between $\mathsf{PCP}$ and $\mathsf{NP}$, and both classes
are now known to be equal [For94]. However, this suggests that, if Conjecture
6.3 is true, showing so likely requires non-relativizing techniques, just as
was the case for the PCP theorem.

##  7 Implications to the quantum PCP conjecture

In this final section, we consider some implications from all previous
sections to the quantum PCP conjecture. We find that our results give insights
into the longstanding open question of whether the reduction from a
$\mathsf{QPCP}$ verifier to a local Hamiltonian with constant promise gap can
be made classical. Furthermore, we give a no-go result for the existence of
quantum gap amplification procedures exhibiting certain properties (unless
$\mathsf{QCMA}=\mathsf{NP}$ or $\mathsf{QCMA}\subseteq\mathsf{NqP}$), and our
results allow us to pose a conjecture which generalizes NLTS (now Theorem
[ABN22]) and provides an alternative to NLSS [GLG22].272727See also [CCNN23],
which proposes a closely-related conjecture independently of this work.

###  7.1 ‘Dequantizing’ the $\mathsf{QPCP}$-to-local-Hamiltonian quantum
reduction

Recall Fact 6.1, which states that the two types of QPCP conjectures (i.e. the
proof verification and local Hamiltonian problem formulations) are known to be
equivalent under _quantum_ reductions. It has also been a longstanding open
question whether the $\mathsf{QPCP}$-to-local-Hamiltonian reduction can be
made classical [AAV13]. However, our definition of $\mathsf{QCPCP}[q]$ shows
that it is unlikely that a reduction having exactly the same properties as the
known quantum reduction exists, as illustrated by the following theorem.

######  Theorem 7.1 (No-go for classical polynomial-time reductions).

Let $q\in\mathbb{N}$ constant. For all constant $\epsilon<1/6$ there cannot
exist a classical polynomial-time reduction from a $\mathsf{QPCP}[q]$ circuit
$V_{x}$ (which is the $\mathsf{QPCP}[q]$ verifier circuit $V$ with the input
$x$ hardwired into it) to a $\mathcal{O}(q)$-local Hamiltonian $H_{x}$ such
that, given a proof $\ket{\psi}$,

$\displaystyle\absolutevalue{\mathbb{P}[V_{x}\text{ accepts
}\ket{\psi}]-\left(1-\bra{\psi}H_{x}\ket{\psi}\right)}\leq\epsilon,$

unless $\mathsf{QCPCP}[q]\subseteq\mathsf{NP}$ (which would imply
$\mathsf{BQP}\subseteq\mathsf{NP}$).

###### Proof.

This follows directly from the fact that a $\mathsf{QPCP}[q]$ protocol can
simulate a $\mathsf{QCPCP}[q]$ protocol by using the exact same verification
circuit $V_{x}$ and asking for basis states as quantum proofs (this can be
forced by measuring the $q$ qubits before any quantum operation acts upon
them). Since one can compute $\bra{y}H_{x}\ket{y}$ efficiently classically for
any basis state $y$ and local Hamiltonian $H_{x}$, we have that the behaviour
of the $\mathsf{QCPCP}$-system given a proof $y$ can be evaluated up to
precision $\epsilon$ by computing $\bra{y}H_{x}\ket{y}$, where $H_{x}$ is the
$\mathcal{O}(q)$-local Hamiltonian induced by the $\mathsf{QPCP}$ verification
circuit $V_{x}$. For any constant $\epsilon<(c-s)/2$ completeness and
soundness are ensured. ∎

###  7.2 Gap amplifications

We now consider the implications of Section 5 to gap amplifications of
guidable local Hamiltonian problems.

######  Theorem 7.2 (No-go’s for quantum-classical gap amplification).

There cannot exist

  1. 1.

A polynomial time classical reduction from an instance of
$\mathsf{CGaLH}(k,\zeta,\delta)$ with $k\geq 2$, some constant $\zeta>0$, and
$\delta=\Theta(1/\mathop{poly}(n))$ to some
$\mathsf{CGaLH}(k^{\prime},\zeta^{\prime},\delta^{\prime})$ with
$k^{\prime}\geq 2$, some constant $\zeta^{\prime}>0$, and
$\delta^{\prime}=\Omega(1)$,

unless $\mathsf{QCMA}=\mathsf{NP}$, and

  1. 2.

A quasi-polynomial time classical reduction from an instance of
$\mathsf{CGaLH}(k,\zeta,\delta)$ with $k\geq 2$,
$\zeta=\Omega(1/\mathop{poly}(n))$, and $\delta=\Theta(1/\mathop{poly}(n))$ to
some $\mathsf{CGaLH}(k^{\prime},\zeta^{\prime},\delta^{\prime})$ with
$k^{\prime}\geq 2$, $\zeta^{\prime}=\Omega(1/\mathop{poly}(n))$, and
$\delta^{\prime}=\Omega(1)$,

unless $\mathsf{QCMA}\subseteq\mathsf{NqP}$.

###### Proof.

These all follow directly from Theorem 5.2. ∎

One can also interpret the no-go results for gap amplifications (points $1$
and $2$ in the above theorem) in a more general setting: if one wants to prove
the QPCP conjecture through a gap amplification procedure a la Dinur, the
procedure needs to have the property that it doesn’t preserve ‘classically
evaluatable’ properties of eigenstates (it cannot even maintain an inverse
polynomial fidelity with such states) unless at the same time showing that
$\mathsf{QCMA}=\mathsf{NP}$ (or $\mathsf{QCMA}\subseteq\mathsf{NqP}$, which is
also very unlikely)! Hence, this result can be viewed as a
‘$\mathsf{QCMA}$-analogy’ to the result from [AG19], where the authors showed
that the existence of quantum gap amplifications that preserve stoqasticity of
Hamiltonians would imply that $\mathsf{NP}=\mathsf{MA}$. We also point out
that it is possible that – even though the complexity of $\mathsf{QGaLH}$ and
$\mathsf{CGaLH}^{*}$ was in the _inverse polynomial_ precision regime the same
for all $\zeta\leq 1-1/\mathop{poly}(n)$ – it might very well be that their
complexities will differ when considering a _constant_ precision, as our
containment results of Section 5 crucially use the properties of classically
evaluatable states. We note that many of the above results can also be easily
adopted to the $\mathsf{MA}$ setting. All obtained results and proofs are
given in Appendix C.2.

###  7.3 Classically evaluatable states and $\mathsf{QPCP}$

Finally, we close by formulating a new conjecture which can be viewed as a
strengthening of the NLTS theorem, or as an alternative to the NLSS conjecture
of [GLG22] in light of our results, and which must hold if the quantum PCP
conjecture is true and $\mathsf{QMA}\neq\mathsf{NP}$.

######  Conjecture 7.1 (NLCES (no low-lying classically-evaluatable states)
conjecture).

There exists a family of local Hamiltonians $\\{H_{n}\\}_{n\in\mathbb{N}}$,
where each $H_{n}$ acts on $n$ qubits, and a constant $\beta>0$, such that for
every classically evaluatable state $\ket{u}\in\mathbb{C}^{2^{n}}$ as in
Definition 3.2, we have that for sufficiently large $n$ that
$\bra{u}H\ket{u}\geq\lambda_{0}(H_{n})+\beta$.

Taking into account our results about the containment of the constant-gapped
classically guidable local Hamiltonian problem in $\mathsf{NP}$ – namely the
insight that what really matters is the fidelity of a classically evaluatable
state with the low-lying energy subspace of the Hamiltonian, and not the
energy of the classically evaluatable state itself – we can also define a
stronger version of the NLCES conjecture, which must hold if the quantum PCP
conjecture holds.

######  Conjecture 7.2 (Strong-NLCES conjecture).

There exists a family of local Hamiltonians $\\{H_{n}\\}_{n\in\mathbb{N}}$,
where each $H_{n}$ acts on $n$ qubits, and a constant $\beta>0$, such that for
sufficiently large $n$ we have that for all classically evaluatable states
$\ket{u}\in\mathbb{C}^{2^{n}}$, as in Definition 3.2, we have that
$\|\Pi_{\lambda_{0}(H_{n})+\beta}\ket{u}\|^{2}=o(1/\mathop{poly}(n))$. Here
$\Pi_{\lambda_{0}(H_{n})+\beta}$ is the projector onto the space spanned by
eigenvectors of $H$ with energy less than $\lambda_{0}(H_{n})+\beta$.

Note that the NLCES Conjecture is strictly weaker than the Strong-NLCES
conjecture, and that both do not necessarily imply the $\mathsf{QPCP}$
conjecture.

## Acknowledgements

The authors thank Sevag Gharibian and François Le Gall for useful discussions
and comments on an earlier version of the manuscript, with a special thanks to
François Le Gall for pointing us towards looking into the implications to the
quantum PCP conjecture. We also thank Harry Burhman for his help regarding
promise classes, Jonas Helsen for helpful discussions, and Ronald de Wolf for
providing feedback on the introduction. We thank the anonymous reviewers for
their helpful comments. CC was supported by Fermioniq B.V., and thanks QuSoft
and CWI for their accommodation whilst this work was completed. MF and JW were
supported by the Dutch Ministry of Economic Affairs and Climate Policy (EZK),
as part of the Quantum Delta NL programme.

## References

  * [AALV09] Dorit Aharonov, Itai Arad, Zeph Landau, and Umesh Vazirani.  The detectability lemma and quantum gap amplification.  STOC, pages 417–426, May 2009.  arXiv:0811.3412.
  * [Aar09] Scott Aaronson.  Computational complexity: Why quantum chemistry is hard.  Nature Physics, 5:707--708, October 2009.
  * [Aar10] Scott Aaronson.  BQP and the polynomial hierarchy.  STOC, pages 141--150, June 2010.  arXiv:0910.4698.
  * [AAV13] Dorit Aharonov, Itai Arad, and Thomas Vidick.  Guest column: the quantum PCP conjecture.  ACM SIGACT news, 44(2):47--79, June 2013.  arXiv:1309.7495.
  * [ABN22] Anurag Anshu, Nikolas P. Breuckmann, and Chinmay Nirkhe.  NLTS hamiltonians from good quantum codes.  arXiv preprint, June 2022.  arXiv:2206.13228.
  * [ABOBS22] Dorit Aharonov, Michael Ben-Or, Fernando G.S.L. Brandão, and Or Sattath.  The pursuit of uniqueness: Extending Valiant-Vazirani theorem to the probabilistic and quantum settings.  Quantum, 6:668, March 2022.  arXiv:0810.4840.
  * [ADK+08] Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev.  Adiabatic quantum computation is equivalent to standard quantum computation.  SIAM review, 50(4):755--787, 2008.  arXiv:quant-ph/0405098.
  * [AG04] Scott Aaronson and Daniel Gottesman.  Improved simulation of stabilizer circuits.  Physical Review A, 70(5):052328, 2004.
  * [AG19] Dorit Aharonov and Alex B. Grilo.  Stoquastic PCP vs. Randomness.  FOCS, pages 1000--1023, November 2019.  arXiv:1901.05270.
  * [AGL20] Dorit Aharonov, Alex B. Grilo, and Yupan Liu.  StoqMA vs. MA: the power of error reduction.  arXiv preprint, October 2020.  arXiv:2010.02835.
  * [AIK21] Scott Aaronson, DeVon Ingram, and William Kretschmer.  The acrobatics of bqp.  arXiv preprint arXiv:2111.10409, 2021.
  * [AL18] Tameem Albash and Daniel A. Lidar.  Adiabatic quantum computation.  Rev. Mod. Phys., 90:015002, January 2018.  arXiv:1611.04471 .
  * [AL21] Carlos Ansótegui and Jordi Levy.  Reducing SAT to Max2SAT.  IJCAI, pages 1367--1373, August 2021.
  * [ALM+98] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy.  Proof verification and the hardness of approximation problems.  Journal of the ACM, 45(3):501–555, May 1998.
  * [Ara11] Itai Arad.  A note about a partial no-go theorem for quantum PCP.  Quantum Information & Computation, 11(11-12):1019--1027, November 2011.  arXiv:1012.3319.
  * [AS98] Sanjeev Arora and Shmuel Safra.  Probabilistic checking of proofs: A new characterization of NP.  Journal of the ACM, 45(1):70–122, January 1998.
  * [ASSZ18] Itai Arad, Miklos Santha, Aarthi Sundaram, and Shengyu Zhang.  Linear time algorithm for quantum 2SAT.  Theory of Computing, 14(1):1--27, March 2018.  arXiv:1508.06340.
  * [BBMC20] Bela Bauer, Sergey Bravyi, Mario Motta, and Garnet K. Chan.  Quantum algorithms for quantum chemistry and quantum materials science.  Chemical Reviews, 120(22):12685--12717, October 2020.  arXiv:2001.03685.
  * [BBT06] Sergey Bravyi, Arvid J. Bessen, and Barbara M. Terhal.  Merlin-Arthur games and stoquastic complexity.  arXiv preprint, November 2006.  arXiv:quant-ph/0611021.
  * [BDLT08] Sergey Bravyi, David P. DiVincenzo, Daniel Loss, and Barbara M. Terhal.  Quantum simulation of many-body Hamiltonians using perturbation theory with bounded-strength interactions.  Physical Review Letters, 101:070503, August 2008.  arXiv:0803.2686.
  * [BDSW96] Charles H. Bennett, David P. DiVincenzo, John A. Smolin, and William K. Wootters.  Mixed-state entanglement and quantum error correction.  Physical Review A, 54(5):3824--3851, nov 1996.
  * [Ben80] Paul Benioff.  The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines.  Journal of Statistical Physics, 22(5):563--591, May 1980.
  * [BG22] Anne Broadbent and Alex Bredariol Grilo.  Qma-hardness of consistency of local density matrices with applications to quantum zero-knowledge.  SIAM Journal on Computing, 51(4):1400--1450, 2022.
  * [BGK22] Lennart Bittel, Sevag Gharibian, and Martin Kliesch.  Optimizing the depth of variational quantum algorithms is strongly QCMA-hard to approximate.  arXiv preprint, November 2022.  arXiv:2211.12519.
  * [BH13] Fernando G.S.L. Brandao and Aram W. Harrow.  Product-state approximations to quantum ground states.  STOC, page 871–880, June 2013.  arXiv:1310.0017.
  * [BJS11] Michael J Bremner, Richard Jozsa, and Dan J Shepherd.  Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy.  Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 467(2126):459--472, 2011.
  * [BLH+21] Vera von Burg, Guang Hao Low, Thomas Häner, Damian S. Steiger, Markus Reiher, Martin Roetteler, and Matthias Troyer.  Quantum computing enhanced computational catalysis.  Physical Review Research, 3(3):033055, July 2021.
  * [BMT15] Jacob D. Biamonte, Jason Morton, and Jacob W. Turner.  Tensor network contractions for #SAT.  Journal of Statistical Physics, 160:1389--1404, June 2015.  arXiv:1405.7375.
  * [Bra06] Sergey Bravyi.  Efficient algorithm for a quantum analogue of 2-SAT.  arXiv preprint, February 2006.  arXive:quant-ph/0602108.
  * [Bra15] Sergey Bravyi.  Monte Carlo simulation of stoquastic Hamiltonians.  Quantum Information & Computation, 15(13–14):1122–1140, October 2015.  arXiv:1402.2295.
  * [Can20] Clément L Canonne.  A short note on learning discrete distributions.  arXiv preprint arXiv:2002.11457, 2020.
  * [CCNN23] Nolan J Coble, Matthew Coudron, Jon Nelson, and Seyed Sajjad Nezhadi.  Local hamiltonians with no low-energy stabilizer states.  arXiv preprint arXiv:2302.14755, 2023.
  * [CFG+23] Chris Cade, Marten Folkertsma, Sevag Gharibian, Ryu Hayakawa, François Le Gall, Tomoyuki Morimae, and Jordi Weggemans.  Improved hardness results for the guided local hamiltonian problem.  In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2023.
  * [CFW22] Chris Cade, Marten Folkertsma, and Jordi Weggemans.  Complexity of the guided local Hamiltonian problem: Improved parameters and extension to excited states.  arXiv preprint, July 2022.  arXiv:2207.10097.
  * [CGL+20] Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang.  Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning.  STOC, page 387–400, June 2020.  arXiv:190.06151.
  * [CHM21] Jordan Cotler, Hsin-Yuan Huang, and Jarrod R. McClean.  Revisiting dequantization and quantum advantage in learning tasks.  arXiv preprint, December 2021.  arXiv:2112.00811.
  * [CLN17] Libor Caha, Zeph Landau, and Daniel Nagaj.  The Feynman-Kitaev computer’s clock: bias, gaps, idling and pulse tuning.  arXiv preprint, 2017.  arXiv:1712.07395.
  * [CMP18] Toby S. Cubitt, Ashley Montanaro, and Stephen Piddock.  Universal quantum Hamiltonians.  The National Academy of Science, 115(38):9497--9502, September 2018\.  arXiv:1701.05182.
  * [Coo71] Stephen A. Cook.  The complexity of theorem-proving procedures.  STOC, pages 151--158, May 1971.
  * [DGF22] Abhinav Deshpande, Alexey V. Gorshkov, and Bill Fefferman.  The importance of the spectral gap in estimating ground-state energies.  PRX Quantum, 3(4):040327, December 2022.  arXiv:2207.10250.
  * [Din07] Irit Dinur.  The PCP theorem by gap amplification.  Journal of the ACM, 54(3):12–es, June 2007.
  * [Dru11] Andrew Drucker.  A PCP characterization of AM.  ICALP, pages 581--592, July 2011.  arXiv:1002.3664.
  * [Fey18] Richard P. Feynman.  Simulating physics with computers.  In Feynman and computation, pages 133--153. CRC Press, 2018.
  * [For94] Lance Fortnow.  The role of relativization in complexity theory.  Bulletin of the EATCS, 52:229--243, 1994.
  * [GHLGM22] Sevag Gharibian, Ryu Hayakawa, François Le Gall, and Tomoyuki Morimae.  Improved hardness results for the guided local Hamiltonian problem.  arXiv preprint, July 2022.  arXiv:2207.10250.
  * [GLG22] Sevag Gharibian and François Le Gall.  Dequantizing the quantum singular value transformation: hardness and applications to quantum chemistry and the quantum PCP conjecture.  STOC, pages 19--32, June 2022.  arXiv:2111.09079.
  * [GN16] David Gosset and Daniel Nagaj.  Quantum 3-SAT is $\text{QMA}_{1}$-complete.  SIAM Journal of computing, 45(3):1080--1128, 2016.  arXiv:1302.0290.
  * [Gol06] Oded Goldreich.  On promise problems: A survey.  In Theoretical Computer Science: Essays in Memory of Shimon Even, pages 254--290. Springer, 2006.
  * [Got98] Daniel Gottesman.  The heisenberg representation of quantum computers.  arXiv preprint, 1998.  arXiv:quant-ph/9807006.
  * [GP19] Sevag Gharibian and Ojas Parekh.  Almost optimal classical approximation algorithms for a quantum generalization of Max-Cut.  LIPIcs, 145:31:1--31:17, October 2019.  arXiv:1909.08846.
  * [GR02] Lov Grover and Terry Rudolph.  Creating superpositions that correspond to efficiently integrable probability distributions.  arXiv preprint, August 2002.  arXiv:quant-ph/0208112.
  * [Gri18] Alex B. Grilo.  Quantum proofs, the local Hamiltonian problem and applications.  PhD thesis, Université Sorbonne Paris Cité, April 2018.
  * [GSLW19] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe.  Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics.  STOC, page 193–204, June 2019.  arXiv:1806.01838.
  * [GY19] Sevag Gharibian and Justin Yirka.  The complexity of simulating local measurements on quantum systems.  Quantum, 3:189, 2019.
  * [Had21] Stuart Hadfield.  On the representation of boolean and real functions as Hamiltonians for quantum computing.  ACM Transactions on Quantum Computing, 2(4):1--21, December 2021\.  arXiv:1804.09130.
  * [HC17] Guang Hao Low and Isaac L. Chuang.  Hamiltonian simulation by uniform spectral amplification.  arXiv preprint, July 2017.  arXiv:1707.05391.
  * [H0̊1] Johan Håstad.  Some optimal inapproximability results.  Journal of the ACM, 48(4):798--859, July 2001.
  * [JGS20] Dhawal Jethwani, François Le Gall, and Sanjay K. Singh.  Quantum-inspired classical algorithms for singular value transformation.  LIPIcs, 170:53:1--53:14, August 2020.  arXiv:1910.05699.
  * [JKNN12] Stephen P. Jordan, Hirotada Kobayashi, Daniel Nagaj, and Harumichi Nishimura.  Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems.  Quantum Information & Computation, 12(5-6):461--471, May 2012.  arXiv:1111.5306.
  * [KKR06] Julia Kempe, Alexei Kitaev, and Oded Regev.  The complexity of the local hamiltonian problem.  SIAM Journal on Computing, 35(5):1070--1097, 2006.  arXiv:quant-ph/0406180.
  * [KLR+08] E. Knill, D. Leibfried, R. Reichle, J. Britton, R. B. Blakestad, J. D. Jost, C. Langer, R. Ozeri, S. Seidelin, and D. J. Wineland.  Randomized benchmarking of quantum gates.  Physical Review A, 77(1), jan 2008.
  * [KSV02] Alexei Y. Kitaev, Alexander Shen, and Mikhail N. Vyalyi.  Classical and quantum computation.  Number 47. American Mathematical Society, 2002.
  * [Lev73] Leonid A. Levin.  Universal sequential search problems.  Problemy peredachi informatsii, 9(3):115--116, 1973.
  * [Liu07] Yi-Kai Liu.  Consistency of local density matrices is qma-complete, 2007.
  * [Liu21] Yupan Liu.  StoqMA Meets Distribution Testing.  In Min-Hsiu Hsieh, editor, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021), volume 197 of Leibniz International Proceedings in Informatics (LIPIcs), pages 4:1--4:22, Dagstuhl, Germany, 2021. Schloss Dagstuhl -- Leibniz-Zentrum für Informatik.
  * [LLS+22] Hongbin Liu, Guang Hao Low, Damian S. Steiger, Thomas Häner, Markus Reiher, and Matthias Troyer.  Prospects of quantum computing for molecular sciences.  Materials Theory, 6(1):1--17, March 2022.  arXiv:2102.10081.
  * [LLZ+22] Seunghoon Lee, Joonho Lee, Huanchen Zhai, Yu Tong, Alexander M. Dalzell, Ashutosh Kumar, Phillip Helms, Johnnie Gray, Zhi-Hao Cui, Wenyuan Liu, Michael Kastoryano, Ryan Babbush, John Preskill, David R. Reichman, Earl T. Campbell, Edward F. Valeev, Lin Lin, and Garnet Kin-Lic Chan.  Is there evidence for exponential quantum advantage in quantum chemistry?  arXiv preprint, August 2022.  arXiv:2208.02199.
  * [LT20] Lin Lin and Yu Tong.  Near-optimal ground state preparation.  Quantum, 4:372, December 2020.  arXiv:2002.12508.
  * [MR18] Dmitri Maslov and Martin Roetteler.  Shorter stabilizer circuits via bruhat decomposition and quantum circuit transformations.  IEEE Transactions on Information Theory, 64(7):4729--4738, 2018\.
  * [MW04] Chris Marriott and John Watrous.  Quantum Arthur-Merlin games.  CCC, pages 275--285, June 2004.  arXiv:cs/0506068.
  * [New60] Donald J Newman.  The double dixie cup problem.  The American Mathematical Monthly, 67(1):58--61, 1960.
  * [OIWF22] Bryan O’Gorman, Sandy Irani, James Whitfield, and Bill Fefferman.  Intractability of electronic structure in a fixed basis.  PRX Quantum, 3(2):020322, May 2022.
  * [Orú14] Román Orús.  A practical introduction to tensor networks: Matrix product states and projected entangled pair states.  Annals of physics, 349:117--158, October 2014.  arXiv:1306.2164.
  * [PH11] David Poulin and Matthew B. Hastings.  Markov entropy decomposition: A variational dual for quantum belief propagation.  Physical review letters, 106(8):080403, February 2011.  arXiv:1012.2050.
  * [PM21] Stephen Piddock and Ashley Montanaro.  Universal qudit hamiltonians.  Communications in Mathematical Physics, 382:721--771, 2021.  arXiv:1802.07130.
  * [RT22] Ran Raz and Avishay Tal.  Oracle separation of BQP and PH.  Journal of the ACM, 69(4):1--21, August 2022.
  * [Sch11] Ulrich Schollwöck.  The density-matrix renormalization group: a short introduction.  Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 369(1946):2643--2661, July 2011.
  * [SSV+05] Christian Schön, Enrique Solano, Frank Verstraete, J. Ignacio Cirac, and Michael M. Wolf.  Sequential generation of entangled multiqubit states.  Physical review letters, 95(11):110503, September 2005.  arXiv:quant-ph/0501096.
  * [Ste03] A. M. Steane.  Quantum computing and error correction, 2003.
  * [SWVC07] Norbert Schuch, Michael M Wolf, Frank Verstraete, and J Ignacio Cirac.  Computational complexity of projected entangled pair states.  Physical review letters, 98(14):140506, 2007.
  * [Tan19] Ewin Tang.  A quantum-inspired classical algorithm for recommendation systems.  STOC, pages 217--228, June 2019.  arXiv:1807.04271.
  * [TCC+22] Jules Tilly, Hongxiang Chen, Shuxiang Cao, Dario Picozzi, Kanav Setia, Ying Li, Edward Grant, Leonard Wossnig, Ivan Rungger, George H. Booth, et al.  The variational quantum eigensolver: a review of methods and best practices.  Physics Reports, 986:1--128, November 2022.  arXiv:2111.05176.
  * [TD04] Barbara M. Terhal and David P. DiVincenzo.  Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games.  Quantum Information & Computation, 4(2):134--145, March 2004.  arXiv:quant-ph/0205133.
  * [TME+18] Norm M. Tubman, Carlos Mejuto-Zaera, Jeffrey M. Epstein, Diptarka Hait, Daniel S. Levine, William Huggins, Zhang Jiang, Jarrod R. McClean, Ryan Babbush, Martin Head-Gordon, and K. Birgitta Whaley.  Postponing the orthogonality catastrophe: efficient state preparation for electronic structure simulations on quantum devices.  arXiv preprint, September 2018.  arXiv:1809.05523.
  * [VMC08] Frank Verstraete, Valentin Murg, and J Ignacio Cirac.  Matrix product states, projected entangled pair states, and variational renormalization group methods for quantum spin systems.  Advances in physics, 57(2):143--224, 2008.
  * [WJB03] Pawel Wocjan, Dominik Janzing, and Thomas Beth.  Two QCMA-complete problems.  Quantum Information & Computation, 3(6):635--643, November 2003\.  arXiv:quant-ph/0305090.
  * [Zac88] Stathis Zachos.  Probabilistic quantifiers and games.  Journal of Computer and System Sciences, 36(3):433--451, 1988.

##  Appendix A Perfect sampling access of MPS and stabilizer states

In this appendix we show that both matrix product states (MPS) and stabilizer
states are samplable states, by checking all three conditions of Definition
3.1.

##### Matrix product states:

Let $u$ be a $N=2^{n}$-dimensional vector described by an MPS of $n$
particles, bounded bond dimension $D$ and local particle dimension $d$.

  1. (i)

Let $\hat{i}$ be the bit representation of $i$. The algorithm $Q_{u}$ can
simply be the evaluation of $\text{Tr}[A_{1}^{(s_{1})}A_{2}^{(s_{2})}\dots
A_{n}^{(s_{n})}]$ for $s=\hat{i}$, which can be done via a naive matrix
multiplication algorithm in time $\mathcal{O}(nD^{3})$, and thus clearly runs
in time $\mathcal{O}\left(\mathop{poly}(\log(N)\right)$ when
$d=\mathcal{O}(\mathop{poly}(n)$, $D=\mathcal{O}(\mathop{poly}(n)$.

  2. (ii)

We will use that expectation values that are a tensor product of $1$-local
observables can be computed efficiently for a MPS im time
$\mathcal{O}(nd^{2}D^{3})$ [VMC08]. We assume that $m$ is already known (see
item (iii)), and that our MPS is therefore normalized. The algorithm
$\mathcal{S}\mathcal{Q}_{u}$ works as follows: one computes the probability
that the first qubit is $1$ by computing the expectation value of the
$1$-local projector $\Pi_{1}=\ket{1}\bra{1}_{1}$. Let
$p_{1}=\bra{u}\Pi_{1}\ket{u}$ and $p_{0}=1-p_{1}$. The algorithm now samples a
bit $j_{1}\in\\{0,1\\}$ according to distribution $\\{p_{0},p_{1}\\}$, and
computes the expectation value of the $2$-local projector $\Pi_{j_{1}1}$ to
obtain $p_{j_{1},1}$ and $p_{j_{1},0}$, from which again a bit is sampled
according to the distribution $p_{j_{1},0},p_{j_{1},1}$. This procedure is
repeated for all $n-2$ remaining sites, which yields a sample $j$ with
probability $|u_{j}|^{2}$. The total time complexity of this procedure is
$\mathcal{O}(n^{2}d^{2}D^{3})=\mathcal{O}(\mathop{poly}(\log N))$, when
$d=\mathcal{O}(\mathop{poly}(n))$ and $D=\mathcal{O}(\mathop{poly}(n))$, as
desired.

  3. (iii)

$m$ can easily be computed by considering the overlap of the MPS with itself,
which can be done in time $\mathcal{O}(npD^{3})$ as the overlap can be viewed
as the expectation value of a $0$-local observable.

##### Stabilizer states:

Let $u\in\mathbb{C}^{2^{n}}$, $N=2^{n}$, be a stabilizer state on $n$ qubits.

  1. (i)

This follows from the fact that basis states are stabilizer states, and that
there exists an algorithm $\mathcal{Q}_{u}$ that computes inner products
between stabilizer states in time
$\mathcal{O}(n^{3})=\mathcal{O}(\mathop{poly}(\log N))$ [AG04].

  2. (ii)

This follows from the fact that stabilizer states can be strongly simulated
(i.e. marginals can be computed), which allows for weak simulation as shown in
[TD04] at overhead $n$ for the cost of strong simulation. Using the strong
simuation algorithm as in [AG04], this gives an algorithm
$\mathcal{S}\mathcal{Q}_{u}$ that runs in time
$\mathcal{O}(n^{3})=\mathcal{O}(\mathop{poly}(\log N))$.

  3. (iii)

$m=1$ by definition.

##  Appendix B MPS to circuit construction

In this section, we show that any MPS on $n$ qubits with bond dimension $D$
can be implemented on a quantum computer up to distance $\epsilon$, with
respect to the $2$-norm, in $\mathcal{O}(nD\log(D)^{2}\log(Dn/\epsilon))$ one-
and two-qubit gates and a $\mathcal{O}(npoly(D))$-time classical pre-
calculation. The result is based on a result from [SSV+05]. For completeness
we will first repeat their result. Let $\mathcal{H}_{A}=\mathbb{C}^{D}$ and
$\mathcal{H}^{B}=\mathbb{C}^{2}$ be the Hilbert spaces characterising a
$D$-dimensional ancillary system and a single qubit, respectively. Then every
MPS of the form

$\ket{\psi}=\bra{\phi_{F}}V_{n}\dots V_{1}\ket{\phi_{I}}$

with arbitrary maps
$V_{k}:\mathcal{H}_{A}\mapsto\mathcal{H}_{A}\otimes\mathcal{H}_{B}$, and
$\ket{\phi_{I}},\ket{\phi_{F}}\in\mathcal{H}_{A}$ is equivalent to a state

$\ket{\psi}=\bra{\tilde{\phi_{F}}}\tilde{V}_{n}\dots\tilde{V}_{1}\ket{\tilde{\phi}_{I}}$

with
$\tilde{V}_{k}:\mathcal{H}_{A}\mapsto\mathcal{H}_{A}\otimes\mathcal{H}_{B}$
isometries and such that the ancillary register decouples in the last step

$\tilde{V}_{n}\dots\tilde{V}_{1}\ket{\tilde{\phi}_{I}}=\ket{\phi_{F}}\otimes\ket{\psi}.$

Note that this is the canonical form of the MPS and can be found using
$\mathcal{O}(npoly(D))$ classical pre-calculation time. The isometries are of
size $2D\times D$ acting on the auxiliary system sequentially and create one
qubit each. Every $\tilde{V}_{k}$ can be embedded into a unitary
$U_{k}:\mathcal{H}_{A}\otimes\mathcal{H}_{B}\mapsto\mathcal{H}_{A}\otimes\mathcal{H}_{B}$
of size $2D\times 2D$, acting on the auxiliary system and a qubit initialised
in $\ket{0}$ such that
$U_{k}\ket{\tilde{\phi}_{k}}\otimes\ket{0}=\tilde{V}_{k}\ket{\tilde{\phi}_{k}}$.
This gives the quantum circuit

$U_{n}\dots U_{1}\ket{\tilde{\phi}_{I}}\ket{0}^{\otimes
n}=\ket{\tilde{\phi}_{F}}\ket{\psi}.$

$\ket{\tilde{\phi_{I}}}$ is a state in $\mathcal{H}_{A}$ which can be
generated on $\lceil\log(D)\rceil$ qubits, up to normalisation. By the
Solovay-Kitaev theorem, this state can be prepared up to distance $\epsilon$
by a circuit of

$\mathcal{O}(\lceil\log(D)\rceil^{2}D\log(\lceil\log(D)\rceil^{2}D/\epsilon))=\mathcal{O}(D\log(D)^{2}\log(1/\epsilon)$

two and one-qubit gates. The unitaries $U_{k}$ act on $\lceil\log(D)\rceil+1$
qubits hence they can be approximated up to error $\epsilon$ in

$\mathcal{O}((\lceil\log(D)\rceil+1)^{2}(D+1)\log((\lceil\log(D)\rceil+1)^{2}(D+1)/\epsilon))=\mathcal{O}(D\log(D)^{2}\log(D/\epsilon)).$

Note that because every unitary incurs an error $\epsilon$ the entire error
can be bounded by $n\epsilon$, setting individual error to
$\epsilon^{\prime}=\frac{\epsilon}{n}$ ensures that the generated state is at
most $\epsilon$ far from the desired state. This results in a circuit of
complexity: $\mathcal{O}(nD\log(D)^{2}\log(nD/\epsilon))$ generating the MPS
up to normalisation.

##  Appendix C Results for $\mathsf{MA}$

Let us define yet another class of guidable local Hamiltonian problems, which
constrains the considered Hamiltonians to be of a specific form.

######  Definition C.1 (Classically Guidable Local Stoquastic Hamiltonian
Problem).

The Classically Guidable Local Stoquastic Hamiltonian Problem, shortened as
$\mathsf{CGaLSH}(k,\delta,\zeta)$, has the same input, promise, extra promise
and output as $\mathsf{CGaLH}(k,\delta,\zeta)$ but with the extra constraint
that the considered Hamiltonian is stoqastic. For our purposes this means that
all $m$ $k$-local terms $H_{i}$ of the Hamiltonian $H=\sum_{i=0}^{m-1}H_{i}$
have real, non-positive off-diagonal matrix elements in the computational
basis.

By adopting the same proof structure as we used to prove Theorem 4.1, we can
obtain a similar result for $\mathsf{CGaLSH}$. For this, we first define a
coherent description of $\mathsf{MA}$, denoted as $\mathsf{MA}_{q}$.

######  Definition C.2 (Coherent classical verifier [BBT06]).

A coherent classical verifier is a tuple $V=(n,n_{w},n_{o},n_{+},U)$, where

$\displaystyle n\quad$ $\displaystyle=$ number of input bits $\displaystyle
n_{w}\quad$ $\displaystyle=$ number of witness bits $\displaystyle n_{0}\quad$
$\displaystyle=$ $\displaystyle\text{number of ancillas }\ket{0}$
$\displaystyle n_{+}\quad$ $\displaystyle=$ $\displaystyle\text{number of
ancillas }\ket{+}$ $\displaystyle U\quad$ $\displaystyle=$ quantum circuit on
$n+n_{w}+n_{0}+n_{+}$ qubits with X, CNOT and Toffoli gates.

The acceptance probability of a coherent classical verifier $V$ on input
string $x\in\\{0,1\\}^{n}$ and witness state
$\ket{\psi}\in\left(\mathbb{C}^{2}\right)^{\otimes n_{w}}$ is defined as

$\displaystyle\text{P}[V;x,\psi]=\bra{\psi_{\text{in}}}U^{\dagger}\Pi_{\text{out}}U\ket{\psi_{\text{in}}},$

where $\ket{\psi_{\text{in}}}=\ket{x}\ket{0}^{\otimes n_{0}}\ket{+}^{\otimes
n_{+}}$ is the initial state and $\Pi_{\text{out}}=\bra{0}\ket{0}\otimes
I_{\text{else}}$ project the first qubit onto the state $\ket{0}$.

######  Definition C.3 ($\mathsf{MA}_{q}$).

The class $\mathsf{MA}_{q}[c,s]$ is the set of all languages
$L\subset\\{0,1\\}^{*}$ for which there exists a (uniform family of) coherent
classical verifier circuit $V$ such that for every $x\in\\{0,1\\}^{*}$ of
length $n=|x|$,

  * •

if $x\in L$ then there exists a $\mathop{poly}(n)$-qubit witness state
$\ket{\psi_{x}}$ such that $V(x,\ket{\psi_{x}})$ accepts with probability
$\geq c(=2/3)$,

  * •

if $x\notin L$ then for every purported $\mathop{poly}(n)$-qubit witness state
$\ket{\psi}$, $V(x,\ket{\psi})$ accepts with probability $\leq s(=1/3)$.

######  Lemma C.1 ([BBT06]).

$\mathsf{MA}=\mathsf{MA}_{q}$

###  C.1 Proof of $\mathsf{MA}$-hardness of the Classically Guidable Local
Stoquastic Hamiltonian problem

######  Theorem C.1.

$\mathsf{CGaLSH}(k,\delta,\zeta)$ is $\mathsf{MA}$-hard for $k\geq 7$,
$\zeta\in(1/\mathop{poly}(n),1-1/\mathop{poly}(n))$ and
$\delta=1/\mathop{poly}(n)$.

###### Proof.

This follows by using a nearly identical construction as have used to prove
Theorem 4.1, but then starting from a $\mathsf{MA}_{q}$ verification circuit
(Definition C.2) instead of a quantum circuit and with some minor changes. Let
us go through the relevant steps of the construction and verify that they
preserve stoquasticity. We will not concern ourselves with reducing the
locality, and hence the parts of the construction needed to achieve this in
the $\mathsf{QCMA}$ setting are left out.

  * •

We have that $\mathsf{MA}_{q}[c,s]=\mathsf{MA}_{q}[1,s]$, since this holds for
$\mathsf{MA}$ and the $\mathsf{MA}_{q}$ verifier has the same acceptance
probability as the $\mathsf{MA}$ verifier.

  * •

The CNOT- and Marriot and Watrous-tricks can be applied as the CNOT gate is
part of the allowed gate-set in Definition C.2.

  * •

One can again use Kitaev’s clock construction with a small penalty $\epsilon$
on $H_{\text{out}}$, where the only terms that are off-diagonal in the
computational basis come from $H_{\text{prop}}$ and $H_{\text{out}}$.
Inspection of these terms confirms that the Hamiltonian is stoquastic [BBT06].
Since the Toffoli gate is a $3$-local gate, we have that our Hamiltonian
becomes $6$-local.

  * •

The block-encoding trick also preserves stoquasticity, as both blocks
themselves are stoquastic. This does increase the locality of the Hamiltonian
by $1$, and therefore it becomes $7$-local.

  * •

Finally, the pre-idling can be done since the identity is trivially in any
gate set.

∎

Somewhat surprisingly, a variant of the guidable local Hamiltonian problem for
stoqastic Hamiltonians was already considered in a work by Bravyi in 2015
[Bra15].282828See also [Liu21], which considers $\mathsf{StoqMA}$ circuit
problems where the witnesses are promised to be of a more restricted form.
However, the considered promise on the guiding state is different, as can be
read from the following definition.

######  Definition C.4 ([Bra15]).

Let $H$ be a stoquastic Hamiltonian. We will say that $H$ admits a guiding
state if and only if there exists a pair of normalized $n$-qubit states
$\psi,\phi$ with non-negative amplitudes in the standard basis such that
$\psi$ is the ground state of $H$, the function
$x\rightarrow\bra{x}\ket{\phi}$ is computable by a classical circuit of size
$\mathop{poly}(n)$, and

$\displaystyle\bra{x}\ket{\phi}\geq\frac{\bra{x}\ket{\psi}}{\mathop{poly}(n)}\quad\text{for
all }x\in\\{0,1\\}^{n}.$

Using the Projection Monte Carlo algorithm with a variable number of walkers,
Bravyi was able to show $\mathsf{MA}$-containment of a guided Stoquastic
Hamiltonian problem that uses guiding states satisfying Definition C.4. Note
that Definition C.4 implies that the fidelity satisfies
$|\bra{\psi}\ket{\phi}|^{2}=\Omega\left(1/\mathop{poly}(n)\right)$, but that
the converse is not necessarily true. Therefore, Bravyi’s result cannot be
directly used to obtain $\mathsf{MA}$-containment of
$\mathsf{CGaLSH}(k,\delta,\zeta)$. We leave this as an open problem for future
work.

###  C.2 PCP statements for $\mathsf{MA}$

For $\mathsf{MA}$ it is not so clear how to define a $\mathsf{PCP}$ statement
in a proof verification version, as the verifiers used in the original
$\mathsf{PCP}$ system are already probabilistic. In [AG19], the authors define
stoqastic $\mathsf{PCP}$ ($\mathsf{SPCP}$) in the following way:

######  Conjecture C.1 (SPCP conjecture - frustration-free Hamiltonian version
[AG19]).

There exist constants $\epsilon>0$, $k^{\prime},d^{\prime}>0$ and an efficient
gap amplification procedure that reduces the problem of deciding if a uniform
stoquastic $d$-degree $k$-local Hamiltonian is frustration-free or at least
inverse polynomially frustrated, to the problem of deciding if a uniform
stoquastic $d^{\prime}$-degree $k^{\prime}$-local Hamiltonian is frustration-
free or at least $\epsilon$ frustrated.

######  Theorem C.2 ([AG19]).

If conjecture C.1 is true, then $\mathsf{MA}=\mathsf{NP}$.

We obtain similar results for our guidable stoquastic Local Hamiltonian
problem, which differs from [AG19] in the fact that the Hamiltonian does not
have to be uniform and the energy decision parameters can be arbitrary real
numbers (instead of zero or bounded away from zero, as is the case in deciding
on the frustration of the Hamiltonian). However, this comes with the extra
constraint that there has to exist a classically describable guiding state, as
per Definition 3.2. Formally, we can define another version of a
$\mathsf{SPCP}$-conjecture in terms of guidable Hamiltonians in the following
way.

######  Conjecture C.2 (SPCP conjecture - guidable Hamiltonian version).

$\mathsf{CGaSLH}(k,\zeta,\delta)$ with $k\geq 2$, some constant $\zeta>0$, and
$\delta=\Omega(1)$ is $\mathsf{MA}$-hard under classical poly-time reductions.

Just as in the $\mathsf{QCMA}$-setting (see Theorem 7.2), we obtain certain
no-go results which must hold if Conjecture C.2 is true.

######  Theorem C.3.

Conjecture C.2 (SPCP conjecture) is true if and only if
$\mathsf{MA}=\mathsf{NP}$.

###### Proof.

The ’$\Longrightarrow$’ implication follows from Theorem 5.2, since
$\mathsf{CGaSLH}(k,\zeta,\delta)$ is a special case of
$\mathsf{CGaLH}(k,\zeta,\delta)$. ‘$\Longleftarrow$’ follows from the fact
that the NP-hard Hamiltonian in Lemma 5.3 is diagonal, which therefore is also
stoquastic. ∎

Furthermore, we can also give no-go results on the existence of stoquastic gap
amplification procedures.

######  Theorem C.4.

There cannot exist

  1. 1.

Stoquastic gap amplification: a polynomial-time classical reduction from an
instance of $\mathsf{CGaSLH}(k,\zeta,\delta)$ with $k\geq 2$, some constant
$\zeta>0$, and $\delta=\Theta(1/\mathop{poly}(n))$ to some
$\mathsf{CGaSLH}(k^{\prime},\zeta^{\prime},\delta^{\prime})$ with
$k^{\prime}\geq 2$, some constant $\zeta^{\prime}>0$, and
$\delta^{\prime}=\Omega(1)$,

unless $\mathsf{MA}=\mathsf{NP}$, and

  1. 2.

Stoquastic gap amplification (2): a quasi-polynomial time classical reduction
from an instance of $\mathsf{CGaSLH}(k,\zeta,\delta)$ with $k\geq 2$,
$\zeta=\Omega(1/\mathop{poly}(n))$, and $\delta=\Theta(1/\mathop{poly}(n))$ to
some $\mathsf{CGaSLH}(k^{\prime},\zeta^{\prime},\delta^{\prime})$ with
$k^{\prime}\geq 2$, $\zeta^{\prime}=\Omega(1/\mathop{poly}(n))$, and
$\delta^{\prime}=\Omega(1)$,

unless $\mathsf{MA}\subseteq\mathsf{NqP}$.

###### Proof.

This follows again from Theorem 5.2. ∎

Hence, these results might provide yet another way, next to [AG19], to
derandomize the class $\mathsf{MA}$ (i.e. show that
$\mathsf{MA}=\mathsf{NP}$).

##  Appendix D QCMA versions of Quantum SAT

The canonical $\mathsf{NP}$-complete problem is satisfiability, and whilst the
general local Hamiltonian problem can be viewed as the ‘quantum analogue’ of
satisfiability, one might argue that an even closer analogue would be the
slightly different problem of quantum satisfiability, introduced in [Bra06].
In quantum satisfiability, shortened as $k$-$\mathsf{QSAT}$, the Hamiltonian
is given by a sum of local projectors and the task is to decide whether there
exists a quantum state $\ket{\xi}$ such that all terms project $\ket{\xi}$ to
zero or the expectation value of $H$ is greater or equal than some inverse
polynomial, for all quantum states. $k$-$\mathsf{QSAT}$ was shown to be
$\mathsf{QMA}_{1}$-complete for $k\geq 3$ [Bra06, GN16], and it can be solved
in linear time classically when $k\leq 2$ [ASSZ18].

In the case of $\mathsf{QMA}$ it is very much unclear whether
$\mathsf{QMA}=\mathsf{QMA}_{1}$, but for $\mathsf{QCMA}$ we know that in fact
$\mathsf{QCMA}=\mathsf{QCMA}_{1}$, as mentioned before. The simple observation
that in our proof of Theorem 4.1 the ground state energy is exactly zero in
the yes-case and inverse polynomially large in the no-case, hints that our
construction actually shows a result for a quantum satisfiability version for
$\mathsf{QCMA}$ (which implies hardness for the more general local Hamiltonian
version), and indeed with some very minor modifications this can be shown to
be the case. First we formally define the ‘$\mathsf{QCMA}$ versions’ of
satisfiability.

######  Definition D.1 (Guidable Quantum Satisfiability).

Guidable Quantum Satisfiability Problems are a class of problems defined as
having the following input, promise, one of the extra promises and output:
Input: A collection $\\{\Pi_{i}:i=1,\dots,m\\}$ of $k$-local projectors acting
on $n$ qubits, a precision parameter $\delta>0$. Let the Hamiltonian
$H=\sum_{i=1}^{m}\Pi_{i}$ be the sum of all these projectors.
Promise: Either there exists a state $\ket{w}$ s.t. $\Pi_{i}\ket{w}=0$ for all
$i=1,\dots,m$ (i.e. $\lambda_{0}(H)=0)$, or otherwise
$\sum_{i=1}^{m}|\innerproduct{y}{\Pi_{i}|y}|\geq\delta$ for all states
$\ket{y}\in\mathbb{C}^{2^{n}}$ (i.e. $\lambda_{0}(H)\geq\delta$).
Extra promises: Denote $\Pi_{\text{gs}}$ for the projection on the subspace
spanned by the ground state of $H$. Then for each problem class, we have that
either one of the following promises hold, each giving a different problem:

  1. 1.

$\mathsf{CGa}\text{-}\mathsf{QSAT}(k,\delta,\zeta)$ Classically Guidable
Quantum Satifisfiability Problem :

There exists a classically evaluatable state $u\in\mathbb{C}^{2^{n}}$ for
which $\norm{\Pi_{\text{gs}}u}^{2}\geq\zeta$.

  2. 2.

$\mathsf{QGa}\text{-}\mathsf{QSAT}(k,\delta,\zeta)$ Quantumly Guidable Quantum
Satifisfiability Problem:

There exists a unitary $V$ implemented by a quantum circuit composed of at
most $T=\mathop{poly}(n)$ gates from a fixed gate set $\mathcal{G}$ that
produces the state $\ket{\phi}=V\ket{0}$, which has
$\norm{\Pi_{\text{gs}}\ket{\phi}}^{2}\geq\zeta$.

Output:

  * •

If $\lambda_{0}(H)=0$, output yes.

  * •

If $\lambda_{0}(H)\geq\delta$, output no.

######  Theorem D.1.

$\mathsf{CGa}\text{-}\mathsf{QSAT}(k,\delta,\zeta)$ is
$\mathsf{QCMA}$-complete for $k\geq 6$, $\delta=\Theta(1/\mathop{poly}(n))$
and $\zeta\in(1/\mathop{poly}(n),1-1/\mathop{poly}(n))$.
$\mathsf{QGa}\text{-}\mathsf{QSAT}(k,\delta,\zeta)$ is
$\mathsf{QCMA}$-complete for $k\geq 6$, $\delta=\Theta(1/\mathop{poly}(n))$
and $\zeta\in(1/\mathop{poly}(n),1]$.

###### Proof.

We will follow the same hardness construction as was used to prove Theorem
4.1, making the following three observations: (i) Definition D.1 requires that
the Hamiltonian is an unweighted sum of projectors. Note that the Hamiltonian
of Eq. (1) is of this form except for the fact that $H_{\text{out}}$ is
weighted by a factor $\epsilon$, which is needed in order to be able to use
Eq. 6. We can easily work around this by instead of multiplying
$H_{\text{out}}$ by a factor $\epsilon$ we add $\lceil 1/\epsilon\rceil$ times
each of the $H_{\text{in}}$, $H_{\text{clock}}$ and $H_{\text{prop}}$ terms,
which allows one to follow the same analysis as when $\epsilon H_{\text{out}}$
was used instead. (ii) $H_{\text{no}}$ of Eq. (4) is a sum of projectors, and
the block-encoding trick used to construct $H$ of Eq. (5) ensures that all
terms remain projectors. (iii) The ground state energy is (before the locality
reduction through the perturbative gadgets, which we do not apply here)
precisely $0$ in the yes-case and inverse polynomially far from zero in the
no-case. This also ensures containment through the use of quantum phase
estimation. Also, note that we do not have to scale down the Hamiltonian as
$\norm{H}\leq 1$ is not required by Definition D.1. ∎