11affiliationtext: QuSoft, University of Amsterdam & Quantinuum, Partnership
House, Carlisle Place, London22affiliationtext: QuSoft & CWI, Amsterdam, the
Netherlands

# Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local
Hamiltonians

Harry Buhrman  Jonas Helsen  Jordi Weggemans To whom correspondence should be
addressed. Email<EMAIL_ADDRESS>
###### Abstract

We define a general formulation of quantum PCPs, which captures adaptivity and
multiple unentangled provers, and give a detailed construction of the quantum
reduction to a local Hamiltonian with a constant promise gap. The reduction
turns out to be a versatile subroutine to prove properties of quantum PCPs,
allowing us to show:

  1. (i)

Non-adaptive quantum PCPs can simulate adaptive quantum PCPs when the number
of proof queries is constant. In fact, this can even be shown to hold when the
non-adaptive quantum PCP picks the proof indices simply _uniformly_ at random
from a subset of all possible index combinations, answering an open question
by Aharonov, Arad, Landau and Vazirani (STOC ’09).

  2. (ii)

If the $q$-local Hamiltonian problem with constant promise gap can be solved
in $\mathsf{QCMA}$, then $\mathsf{QPCP}[q]\subseteq\mathsf{QCMA}$ for any
$q\in\mathcal{O}(1)$.

  3. (iii)

If $\mathsf{QMA}(k)$ has a quantum PCP for any $k\leq\mathrm{poly}(n)$, then
$\mathsf{QMA}(2)=\mathsf{QMA}$, connecting two of the longest-standing open
problems in quantum complexity theory.

Moreover, we also show that there exists (quantum) oracles relative to which
certain quantum PCP statements are false. Hence, any attempt to prove the
quantum PCP conjecture requires, just as was the case for the classical PCP
theorem, (quantumly) non-relativizing techniques.

###### Contents

  1. 1 Introduction
    1. 1.1 Quantum PCPs are constant promise gap local Hamiltonians
    2. 1.2 Results from applying the reduction
      1. 1.2.1 Upper bounds on quantum PCPs
      2. 1.2.2 Adaptive and non-adaptive quantum PCPs
      3. 1.2.3 Quantum PCPs for $\mathsf{QMA}(k)$
    3. 1.3 Proofs of the quantum PCP theorem do not relativize
    4. 1.4 Discussion and open problems
  2. 2 Preliminaries
    1. 2.1 Notation
    2. 2.2 Complexity theory
  3. 3 Quantum probabilistically checkable proofs
  4. 4 Local Hamiltonians from quantum PCPs
    1. 4.1 Learning the Hamiltonian
    2. 4.2 Local smoothings of local Hamiltonians
    3. 4.3 Kitaev’s energy estimation protocol
  5. 5 Applications
    1. 5.1 Proof checking versus local Hamiltonian formulations of quantum PCP
    2. 5.2 Adaptive versus non-adaptive quantum PCPs
    3. 5.3 A quantum PCP for $\mathsf{QMA}(2)$ implies $\mathsf{QMA}(2)=\mathsf{QMA}$
  6. 6 Proofs of quantum PCP theorems do not (quantumly) relativise
    1. 6.1 Quantum proof discretisation
    2. 6.2 Oracle separations
  7. A Strong error reduction for non-adaptive quantum PCPs with near-perfect completeness
  8. B Sufficient error bounds for learning weighted Hamiltonians from non-adaptive quantum PCPs
  9. C Proof of Corollary 4.1
  10. D A classical oracle separation

##  1 Introduction

Arguably the most fundamental result in classical complexity theory is the
Cook-Levin Theorem [Coo71, Lev73], which states that constraint satisfaction
problems (CSPs) are $\mathsf{NP}$-complete. Kitaev showed that there exists a
natural analogue in the quantum world: local Hamiltonian problems, which can
be viewed as a quantum generalisation of classical constraint satisfaction
problems, are complete for the class $\mathsf{QMA}$, which is a quantum
generalisation of $\mathsf{NP}$ [KSV02].111There are many possible quantum
generalisations of $\mathsf{NP}$, see [Gha23] for a recent review.

There are many variants of $\mathsf{NP}$, which a priori seem either more
powerful or more restrictive, but turn out to be equal to $\mathsf{NP}$.
Examples of these are interactive proof systems of various flavours with a
deterministic verifier, and perhaps most surprisingly and importantly,
probabilistically checkable proof systems (PCPs) [ALM+98]. A PCP has a
polynomial-time probabilistic verifier with query access to a proof (provided
by a prover). Usually, a PCP is specified by two parameters: the number of
random coins the verifier is allowed to use (which also upper bounds the
length of the proof as some exponential in the number of coins) and the number
of queries it can make to the proof. The PCP theorem [ALM+98, AS98], which
originated from a long line of research on the complexity of interactive proof
systems, states that all decision problems in $\mathsf{NP}$ can be decided,
with a constant probability of error, by only using a logarithmic number of
coin flips and by querying a constant number of bits of the proof.
Equivalently, it implies that it is $\mathsf{NP}$-hard to decide whether an
instance of a CSP is either completely satisfiable or no more than a constant
fraction of its constraints can be satisfied, which is usually referred to as
the _hardness of approximation_ formulation of the PCP theorem. It is also
possible to prove the PCP theorem by reducing a CSP directly to another CSP
which has the above property. This sort of transformation, due to Dinur
[Din07], is usually referred to as _gap amplification_ , referring to the
increase in the difference (the gap) in the fraction of constraints which can
be satisfied in both the Yes\- and No-instances.

Naturally, quantum complexity theorists have proposed proof-checking and
hardness of approximation versions of a quantum PCP conjecture. The hardness
of approximation formulation states that the local Hamiltonian problem with
constant promise gap, relative to the operator norm of the Hamiltonian, is
$\mathsf{QMA}$-hard. This formulation of the quantum PCP conjecture has been
the predominant focus of the quantum PCP literature, and progress has been
made in giving evidence both in favour and against the conjecture. Amongst the
positive are the NLTS theorem and its cousins, excluding a large set of
potential $\mathsf{NP}$-witnesses [ABN23, CCNN23b, AGK23, CCNN23a, HATH23].
Evidence against (assuming $\mathsf{NP}\neq\mathsf{QMA}$) are results showing
that under many extra constraints one poses on the local Hamiltonian problem
(constraining e.g. the interaction graph or ground space structure) the
problem is classically solvable when the relative promise gap is constant,
whilst the problem remains (quantumly) hard when the gap is inverse polynomial
[BBT09, BH13, AG19, GLG22, CFG+23, WFC23].

The proof-checking formulation of the quantum PCP conjecture, which states
that one can solve any promise problem in $\mathsf{QMA}$ by using a quantum
verifier which only accesses a constant number of qubits from a quantum proof,
has received considerably less attention. The reason for this is that is not
hard to show that both conjectures are equivalent under quantum reductions.
This was already pointed out in the first work which proposed a quantum PCP
formulation [AALV09].222Whilst this is widely known in the community, this
reduction has (as far as the authors are aware) never been written down in
full detail except in the works of [Gri18] and [HATH23], which both consider
quantum PCPs that are not (or at least shown to be) fully general. In both
these works a quantum PCP is defined as a collection of POVMs, each of which
acts on an ancilla register and a small part of the provided quantum proof.
The verifier decides on which POVM it is going to use by sampling from a
classical probability distribution (in [Gri18] this is simply the uniform
distribution). Perhaps that is why, even after more than two decades since the
question of the existence of a quantum PCP was first posited [AN02], many
basic questions regarding the proof-checking formulation have not been
addressed. For example, as already raised in [AALV09], how robust are
definitions of quantum PCPs under subtle changes, e.g. the choice of picking
the distribution over which the proof qubits are selected? Are adaptive
queries to the proof more powerful than non-adaptive in the constant query
setting or are they the same as is the case for the classical setting? Are
there perhaps non-equivalent variations of quantum PCPs, similar to the many
natural variations of $\mathsf{QMA}$?

Motivated by these questions, this work is concerned with studying the
properties of quantum PCPs through proof verification. Studying the connection
between quantum PCPs and local Hamiltonians turns out to be a powerful tool
for showing basic properties of quantum PCPs.

###  1.1 Quantum PCPs are constant promise gap local Hamiltonians

We give a detailed definition of a quantum PCP verifier, which allows for
adaptive queries as well as quantum proofs consisting of multiple unentangled
quantum states given by different unentangled provers. Informally (see
definition 3.1 for the full definition) the verifier makes $q$ queries to a
quantum proof in the following way:

  * •

The verifier takes as an input a string $x$ of size $n$ (which will be
hardcoded into the circuits), has a polynomial-sized ancilla register (which
we will call the workspace) and a proof register containing $k$ unentangled
quantum proofs of some specified size depending on $n$. Generally, $k=1$
unless specified otherwise.

  * •

The verifier is going to do the following $q$ times. At stage $t\in[q]$,
suppose the quantum PCP has decided to act on proof qubits from the set
$I=\\{i_{1},\dots,i_{t-1}\\}$. The quantum PCP then applies a polynomial-time
quantum circuit to the workspace and the proof qubits with indices
$i_{1},\dots,i_{t-1}$ followed by a measurement of some designated qubits to
determine which next index $i_{t}$ is going to be added to the set $I$.

  * •

Finally, another polynomial-time circuit is applied to the workspace and the
proof qubits with indices $i_{1},\dots,i_{q}$ and a single designated output
qubit is measured in the computational basis. The quantum PCP accepts if and
only if the outcome is $\ket{1}$.

Note that this quantum PCP is adaptive, and a non-adaptive quantum PCP would
be one where all the circuits applied between the measurements used to decide
the indices are simply the identity operator (so that all proof qubits which
are going to be accessed are decided all at once). One can then construct
complexity classes based on this verifier in a general setting, where we also
include the possibility of multiple provers. We show that there exists a local
Hamiltonian with PSD terms whose expectation value has a one-on-one
correspondence with the acceptance probabilities of the quantum PCP given a
quantum proof.

######  Lemma 1.1 (Informal) (from Lemma 4.2).

Let $x$ be an input and $V_{x}$ a $q$-query quantum PCP verifier with $x$
hardcoded into it. Then there exists a $q$-local Hamiltonian $H_{x}$ such that

$\displaystyle\mathbb{P}[V_{x}\text{ accepts
}\ket{\xi}]=1-\bra{\xi}H_{x}\ket{\xi},$

where $H_{x}=\sum_{i\in[m]}H_{x,i}$ with each $H_{x,i}$ PSD and $\norm{H}\leq
1$.

Usually, the quantum PCP conjecture is framed in a different form than the one
this Hamiltonian is in: one assumes that $H$ is of the form
$H=\sum_{i\in[m]}H_{i}$ with $0\preceq H_{i}\preceq 1$ and that
$\lambda_{\textup{min}}(H)\leq\alpha m$ or $\lambda_{\textup{min}}(H)\geq\beta
m$. These Hamiltonians can be easily rewritten in the same form as $H_{x}$ by
letting $H^{\prime}=\sum_{i\in[m]}H^{\prime}_{i}$ with
$H^{\prime}_{i}:=H_{i}/m$, such that
$\lambda_{\textup{min}}(H^{\prime})\leq\alpha$ or
$\lambda_{\textup{min}}(H^{\prime})\geq\beta$. However, this formulation
implicitly assumes that in the latter case at least a constant fraction of the
terms contribute of the order of $\sim\frac{1}{m}$ to the ground state energy,
which means that the energy is relatively spread out over all terms. For our
definition of quantum PCPs, this does not necessarily have to be the case.
This difference is subtle but important: one can no longer pick a constant
number of terms uniformly at random and measure their energy to solve the
corresponding local Hamiltonian problem, as only a small $o(1)$ fraction of
the terms might have large energy. Nevertheless, we show that there exists a
transformation from any such Hamiltonian to another one which does satisfy
this property, at the cost of increasing the locality by a factor of two and
decreasing the promise gap exponentially in the locality, which is still
constant if the locality is constant (Lemma 4.5).

Now we have shown that the probability that a $\mathsf{QPCP}$-verifier accepts
a certain proof is equivalent to the expectation value of some Hamiltonian, we
still need to show that the descriptions of the local terms can be obtained
efficiently. For this, it is well-known that one can adopt a quantum reduction
[AALV09]. We show that a quantum reduction also exists for our general
formulation of quantum PCPs. Moreover, by a simple trick, we find that we can
round the Hamiltonian in such a way that every time the reduction succeeds
(which can be done with a success probability exponentially close to one) it
produces exactly the same Hamiltonian.

######  Theorem 1.1 (Informal) (from Theorem 4.1 and Corollary 4.1).

Let $x$ be an input. There exists a quantum reduction from a $q$-query quantum
PCP with circuit $V_{x}$ to a $q$-local Hamiltonian $\hat{H}_{x}$ such that

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

which succeeds with probability $1-\delta$ and runs in time
$\mathrm{poly}(n,1/\epsilon,\log(1/\delta))$. Moreover, this reduction can be
made such that it produces the same Hamiltonian every time it succeeds.

The specificity of the reduction (i.e. it always yields the same Hamiltonian
and the acceptance probability is directly encoded in the energy of the
Hamiltonian) makes it a useful tool in deriving a variety of statements about
quantum PCPs, since quantum PCPs themselves can perform the reduction.

###  1.2 Results from applying the reduction

All applications are derived by adopting variations of the following general
strategy:

  1. 1.

The reduction of a quantum PCP to a local Hamiltonian is used as a pre-
processing step of some larger protocol, rounding to a fixed Hamiltonian with
high success probability.

  2. 2.

One uses tricks of Hamiltonian complexity to manipulate and solve the
corresponding local Hamiltonian problems.

It is important to emphasise that by this strategy, the reductions we propose
are simply classical polynomial-time reductions, even though they involve
quantum reductions. The reason for this is that the quantum reductions are
absorbed into the quantum protocols as pre-processing steps. A disadvantage of
this strategy is that it in general fails to preserve perfect completeness.

####  1.2.1 Upper bounds on quantum PCPs

By a result of [WFC23], it seems unlikely that there exists a classical
reduction that satisfies the same properties as Theorem 1.1, as that would
show that $\mathsf{BQP}\subseteq\mathsf{QCPCP}\subseteq\mathsf{NP}$.333Here
$\mathsf{QCPCP}$ is just as $\mathsf{QPCP}$ but with the promises for
classical proofs instead of quantum proofs, similar to what $\mathsf{QCMA}$ is
to $\mathsf{QMA}$. The other direction (going from a local Hamiltonian with
constant to a $\mathsf{QPCP}$ verification circuit) is easy to show through
Kitaev’s original $\mathsf{QMA}$ verification circuit for the local
Hamiltonian problem (see Protocol 4.3), once the Hamiltonian has been
transformed in the required form (equally bounded operator norm on all local
terms). Hence, if one shows that $\mathsf{QPCP}[q]\subseteq\mathcal{C}$ for
some complexity class $\mathcal{C}$ that can perform polynomial-time classical
reductions (so any class $\mathcal{C}\supseteq P$ would suffice), then the
local Hamiltonian problem with constant promise gap is in $\mathcal{C}$ as
well. However, since the reduction from $\mathsf{QPCP}$ to a local Hamiltonian
is a quantum reduction, such a statement does not hold in the other direction.
Weaker conclusions can be drawn however.

Perhaps the easiest application of this method is to show that an upper bound
on the local Hamiltonian problem with a constant promise gap implies an upper
bound on quantum PCPs with the same locality.

######  Theorem 1.2 (Informal) (from Theorem 5.1).

If the $q$-local Hamiltonian problem with constant promise gap is in
$\mathsf{QCMA}$, then $\mathsf{QPCP}[q]\subseteq\mathsf{QCMA}$.

This entails that, assuming $\mathsf{QMA}\neq\mathsf{QCMA}$, disproving
$\mathsf{QMA}$-hardness for either the proof verification or Hamiltonian
formulation of the quantum PCP conjecture (by placing it in $\mathsf{QCMA}$)
does indeed disprove the other (similar to how proving $\mathsf{QMA}$ hardness
of one implies $\mathsf{QMA}$-hardness of the other.)

####  1.2.2 Adaptive and non-adaptive quantum PCPs

It is a well-known fact that non-adaptive PCPs can simulate adaptive PCPs in
the classical setting when the number of proof queries is only allowed to be
constant. This can easily be shown by simulating the adaptive-quantum PCP
verifier over all possible local proof settings for a fixed setting of the
randomness, after which the actual proof can be used to check which setting
was correct. However, such tricks seem to have no quantum analogue, as it is
generally impossible to fix the inherent randomness (or ‘quantumness’) in a
quantum algorithm [AIK21]. However, we can show that a quantum analogue of
this result still holds.

######  Theorem 1.3 (Informal) (from Theorem 5.2).

Non-adaptive quantum PCPs can simulate adaptive quantum PCPs when the number
of proof queries is constant.

In fact, we are able to prove something stronger: we show that any constant
query PCP can be simulated by a quantum PCP that picks the indices of the
proof bits it is going to access uniform at random from a subset of all
possible index choices, resolves an open question of [AALV09] (Remark 4 in the
main text).444This also shows that that the quantum PCP formulation as in
[Gri18] is in fact fully general when one considers quantum PCPs which only
make a constant number of proof queries. We prove these results by showing
that there exists a non-adaptive quantum PCP verifier for the local
Hamiltonian induced by the adaptive quantum PCP, which only has its promise
gap exponentially smaller in the locality. Weak error reduction can then be
used to boost the promise gap back to its original value.

####  1.2.3 Quantum PCPs for $\mathsf{QMA}(k)$

Finally, we consider a quantum PCP in the $\mathsf{QMA}(k)$ setting: the
complexity class $\mathsf{QMA}(k)$ is a generalisation of $\mathsf{QMA}$ where
there are multiple uninteracting provers, which are guaranteed to be
unentangled with each other. It is known that
$\mathsf{QMA}(k)=\mathsf{QMA}(2)$ by the result of Harrow and Montanaro
[HM13], but is generally believed that $\mathsf{QMA}\neq\mathsf{QMA}(2)$ since
there are problems known to be in $\mathsf{QMA}(2)$ but not known to be in
$\mathsf{QMA}$ [LCV07, ABD+08, Bei10, BT09]. Moreover, the best upper bound we
have on $\mathsf{QMA}(2)$ is that it is contained in $\mathsf{NEXP}$, which
follows by just guessing exponential-size classical descriptions of the two
quantum proofs. The reason for this is that the maximum acceptance probability
of a $\mathsf{QMA}(2)$ verifier is with respect to separable states, which
means that the corresponding maximisation problem is no longer convex. Another
surprising fact is that the separable local Hamiltonian problem is
$\mathsf{QMA}$-complete, and we only have that that a separable Hamiltonian
problem becomes $\mathsf{QMA}(2)$-complete when one considers sparse
Hamiltonians, for the individual terms can only have a polynomial number of
non-zero entries but do not have to be local [CS12]. Since our quantum
reduction from a quantum PCP always produces a local Hamiltonian irrespective
of the number of provers, a simple generalisation of the protocol of [CS12] to
the $k$-separable local Hamiltonian setting allows us to show the following.

######  Theorem 1.4 (Informal) (from Theorem 5.3).

If $\mathsf{QMA}{(k)}$ has a quantum PCP for any $2\leq
k\leq\mathrm{poly}(n)$, then we have that $\mathsf{QMA}{(2)}=\mathsf{QMA}$.

This shows a connection between two of the biggest open problems in quantum
complexity. In particular, if one believes that a quantum PCP conjecture for
$\mathsf{QMA}$ should hold and that $\mathsf{QMA}(2)\neq\mathsf{QMA}$, then
any proof of the quantum PCP conjecture should not translate to the multiple
unentangled prover setting.

###  1.3 Proofs of the quantum PCP theorem do not relativize

In the final section, we will show that Aaronson and Kuperberg’s quantum
oracle [AK07] under which $\mathsf{QCMA}\neq\mathsf{QMA}$ we also have that
the quantum PCP conjecture is false. Their oracle separation is fundamentally
based on a lower bound combined with a counting argument, which exploits the
fact that there are doubly exponential quantum states (with small pairwise
fidelities) but only an exponential number of classical proofs. The reason
this lower bound cannot be applied directly to $\mathsf{QPCP}$ comes from the
fact that the total number of quantum proofs that can be given is the same as
for $\mathsf{QMA}$. However, from the verifiers perspective, the total number
of proofs he observes is limited by a set of local density matrices and
indices indicating from what part of the global state this density matrix
comes from. Using this observation, we can define an artificial variation of
$\mathsf{QPCP}$, denoted $\mathsf{QPCP}_{\epsilon}$, which can be viewed as a
‘proof-discretized’-version of $\mathsf{QPCP}$. Informally, this class can be
viewed as a variant to $\mathsf{QPCP}$ where after the verifier decides which
parts of the proof are going to be accessed, some ‘magical operation’ takes
this part of the proof and projects it onto the density matrix closest to it
from some fixed finite set. We can show that with respect to all oracles, this
new class contains $\mathsf{QPCP}$, so any oracle separation between
$\mathsf{QMA}$ and $\mathsf{QPCP}_{\epsilon}$ also separates $\mathsf{QPCP}$
and $\mathsf{QMA}$.

######  Theorem 1.5 (Informal) (from Theorem 6.1 and Corollary 6.1).

There exists a quantum (classical) oracle relative to which the polylog
(constant) quantum PCP conjecture is false.

Since for any oracle $X$ that encodes a $\mathsf{PSPACE}$-complete language we
have that $\mathsf{QPCP}[q]^{X}=\mathsf{QMA}^{X}$, since the inclusions
$\mathsf{QPCP}[k,q]\subseteq\mathsf{QMA}\subseteq\mathsf{PSPACE}$ all
relativize with respect to all classical oracles and
$\mathsf{PSPACE}^{\mathsf{PSPACE}}=\mathsf{PSPACE}$, we have that this result
implies that proving the quantum PCP conjecture by showing
$\mathsf{QPCP}[q]=\mathsf{QMA}$ for some constant $q\in\mathcal{O}(1)$
requires non-relativizing techniques, just as was the case for the classical
PCP theorem [For94].

Perhaps the most important takeaway from this result is that it should apply
to any quantum oracle separation involving $\mathsf{QMA}$ which exploits the
fact that there are doubly exponentially many proofs in $\mathsf{QMA}$.
Therefore, all oracle separations between $\mathsf{QMA}$ and $\mathsf{QCMA}$
based on such an argument immediately yield an oracle relative to which the
quantum PCP conjecture is false.

###  1.4 Discussion and open problems

We have studied the quantum PCP conjecture from in the proof-checking
formulation (as opposed to the more popular local Hamiltonian formulation).
Ironically, many of our results follow from leveraging the reduction to the
local Hamiltonian problem. Our results take the form of both novel statements,
and formal proofs of what we think of as ”folklore knowledge”, i.e. results we
suspect are known to be true but for which we could not find a proof in the
literature. Given the renewed interest in the quantum PCP conjecture we
believe this was an effort worth undertaking. We conclude by listing several
questions on quantum PCPs which we have not yet resolved but believe are
interesting avenues for future work.

##### Quantum PCPs with perfect completeness

A major downside of our technique – that is to leverage the $\mathsf{QPCP}$ to
local Hamiltonian quantum reduction – is that it fails to preserve perfect
completeness, which is due to the Hamiltonian being learned only up to some
small error. It is an open question whether other techniques can be used to
obtain similar results in the perfect completeness setting, for example
whether non-adaptive quantum PCPs can simulate adaptive ones when the number
of quantum proof queries is only allowed to be constant.

##### Strong error reduction

It is easy to show that non-adaptive quantum PCPs with near-perfect
completeness allow, just like $\mathsf{QMA}$ [MW05], for strong error
reduction (Appendix A). However, we do not know whether this also holds in the
general case. The idea of taking polynomials of the Hamiltonian to manipulate
its spectrum seems not to be compatible with Kitaev’s energy estimation
protocol, as this in general introduces coefficients that can be negative and
have large absolute values, which is incompatible with Kitaev’s energy
estimation protocol (Subsection 4.3) which requires each term to have to be
PSD and have operator norm at most one.

##### Acknowledgements

JW was supported by the Dutch Ministry of Economic Affairs and Climate Policy
(EZK), as part of the Quantum Delta NL programme. JH acknowledges support from
the Quantum Software Consortium (NWO Zwaartekracht 024.003.037) and a Veni
grant (NWO Veni 222.331).

##  2 Preliminaries

###  2.1 Notation

For a Hilbert space $\mathcal{H}$ of dimensional $d$, we denote
$\mathcal{D}(\mathcal{H})=\\{\rho\in\text{PSD}(\mathcal{H}),\tr[\rho]=1\\}$,
where $\text{PSD}(\mathcal{H})$ is the set of all positive semidefinite
matrices in $\mathcal{H}$, for the set of all density matrices in
$\mathcal{H}$. For the set of all $d$-dimensional pure states, we write
$\mathcal{P}(\mathcal{H})=\\{\rho\in\text{PSD}(\mathcal{H}),\tr[\rho^{2}]=1\\}$
(normally defined as $\mathbb{CP}^{d-1}$, i.e. complex projective space with
dimension $d-1)$.

###  2.2 Complexity theory

We start by recalling the basic definitions from complexity theory classes
used in this work.

######  Definition 2.1 ($\mathsf{QMA}{(k)}$).

Let $n\in\mathbb{N}$ be the input size. A promise problem
$A=(A_{\text{yes}},A_{\text{no}})$ is in $\mathsf{QMA}[k,c,s]$ if and only if
there exists a polynomial-time uniform family of quantum circuits
$\\{V_{n}\\}$ and a polynomial $p$, where $V_{n}$ takes as input a string
$x\in\\{0,1\\}^{n}$ and a $kp(n)$-qubit witness quantum state $\ket{\psi}$ and
decides on acceptance or rejection of $x$ such that

  * •

if $x\in A_{\textup{yes}}$ then there exist $p(n)$-qubit witness states
$\ket{\psi_{j}}\in\left(\mathbb{C}^{2}\right)^{\otimes p(n)}$, $j\in[k]$, such
that $V_{n}$ accepts $(x,\otimes_{j\in[k]}\ket{\psi_{j}})$ with probability
$\geq c$,

  * •

if $x\in A_{\textup{no}}$ then for all
$\ket{\psi_{j}}\in\left(\mathbb{C}^{2}\right)^{\otimes p(n)}$, $j\in[k]$, we
have that $V_{n}$ accepts $(x,\otimes_{j\in[k]}\ket{\psi_{j}})$ with
probability $\leq s$,

where $c-s=\Omega(1/\mathrm{poly}(n))$. If $c=2/3$ and $s=1/3$, we abbreviate
to $\mathsf{QMA}(k)$, and if $k=1$, we have $\mathsf{QMA}=\mathsf{QMA}(1)$.

######  Definition 2.1a ($\mathsf{QCMA}$).

This has the same definition as $\mathsf{QMA}$ but where the promises hold
with respect to computational basis states $\ket{y}$, where $|y|=p(n)$. In
this case we trivially have $\mathsf{QCMA}[k]=\mathsf{QCMA}$ for all
$k\leq\mathrm{poly}(n)$.

By a result of Harrow and Montanaro, it is known that $\mathsf{QMA}$ with $2$
unentangled provers can simulate any polynomial number of unentangled provers.

######  Lemma 2.1 ([HM13]).

For any $2\leq k\leq\mathrm{poly}(n)$, we have

$\displaystyle\mathsf{QMA}(k)=\mathsf{QMA}(2).$

######  Fact 2.1.

For any $1\leq k\leq\mathrm{poly}(n)$, the completeness and soundness
parameters in $\mathsf{QMA}(k)$ and $\mathsf{QCMA}$ can be made exponentially
close to $1$ and $0$, respectively, i.e. $c=1-2^{-\mathcal{O}(n)}$ and
$s=2^{-\mathcal{O}(n)}$.

The $q$-local $k$-separable local Hamiltonian problem generalises the
$q$-local Hamiltonian problem (which is the case for $k=1$) by giving a
promise on the energies of all low-energy of $k$-fold tensor products, where
each quantum state in the tensor product lives on a pre-determined number of
qubits. It is shown to be $\mathsf{QMA}$-complete in the case where $k=2$ in
[CS12].

######  Definition 2.2 ($k$-separable local Hamiltonian problem).

$k,q$-$\mathsf{LH}[\delta]$
Input: A $q$-local Hamiltonian $H$ with $\|H\|\leq 1$ acting on $n$ qubits,
threshold parameters $a,b\in\mathbb{R}$ such that $b-a\geq\delta>0$. We call
$\delta$ the promise gap.
Promise: We have that either one of the following two holds:

  1. (i)

There exists a quantum state $\xi=\otimes_{j\in[k]}\xi_{j}$, such that
$\tr[H\xi]\leq a$

  2. (ii)

For all quantum states $\xi=\otimes_{j\in[k]}\xi_{j}$ we have that
$\tr[H\xi]\geq b$.

Output:

  * •

If case (i) holds, output yes.

  * •

If case (ii) holds,, output no.

##  3 Quantum probabilistically checkable proofs

The bulk of this section is taken up a definition of a quantum PCP. Our
definition is more detailed than that given in [AAV13], and more general than
the definitions in [HATH23, Gri18], in that we also include the ability to
query proof qubits adaptively. Moreover, we allow for the possibility of
having multiple provers (i.e. unentangled proofs). Once we have this
definition in place we can define an associated complexity class
$\mathsf{QPCP}$. For convenience, we also explicitly define a non-adaptive
version. We finish up by arguing that weak error reduction (and limited strong
error reduction) is possible in $\mathsf{QPCP}$.

######  Definition 3.1 (quantum PCP verifier).

Let $p_{1},p_{2}:\mathbb{N}\rightarrow\mathbb{N}$, and $n\in\mathbb{N}$ be the
input size. A $(k,q,p_{1},p_{2})\text{-}\mathsf{QPCP}_{\textup{A}}$-verifier
$V$ consists of the following:

  * •

a $n$-qubit input register $A$ initialised in input $\ket{x}$,
$x\in\\{0,1\\}^{n}$;

  * •

a $p_{1}$-qubit ancilla register $B$ initialised in $\ket{0}^{\otimes
p_{1}(n)}$;

  * •

a $kp_{2}$-qubit proof register, $C$ initialised in
$\ket{\xi}=\otimes_{j=1}^{k}\ket{\xi^{j}}$ for some quantum witnesses
$\ket{\xi^{j}}\in\left(\mathbb{C}^{2}\right)^{\otimes p_{2}(n)}$ for all
$j\in[k]$;

  * •

a collection of PVMs $\Pi^{t}=\\{\Pi_{i_{t}}^{t}\\}$, $t\in[q]$,
$\Pi^{\text{output}}=\\{\Pi_{0}^{\text{output}},\Pi_{1}^{\text{output}}\\}$;

  * •

collection of circuits $V^{t^{\prime}}$, $t^{\prime}\in\\{0\\}\cup[q]$, where
circuit $V^{t^{\prime}}$ only acts on at most $t^{\prime}$ qubits of the proof
register.

Let $I=\emptyset$ be the set of all proof indices to be accessed. The quantum
PCP verifier acts as follows:

  1. 1.

For $t\in[q]$: it applies the circuit $V_{t-1}$ to registers $A$, $B$ and
qubits $I$ from $C$ , performs the measurement $\Pi^{t}$ and adds outcome
$i_{t}$ to the set $I$;

  2. 2.

It applies $V_{q}$ followed by a measurement of $\Pi^{\text{output}}$ and
returns ‘accept’ if the outcome was $\ket{1}$, and ‘reject’ if the outcome was
$\ket{0}$.

If $p_{1},p_{2}$ are polynomially bounded functions, then we we abbreviate to
a $(k,q)$-$\mathsf{QPCP}$ verifier.

######  Remark 1.

We will often write $V_{x}$ to denote the verifier circuit with the input $x$
hardcoded at the start of the circuit.

######  Definition 3.1a (non-adaptive quantum PCP verifier).

A non-adaptive $(p_{1}(n),q)$-$\mathsf{QPCP}_{\textup{NA}}$-verifier is just
as the $\mathsf{QPCP}$ verifier but applies all PVMs $\\{\Pi^{t}\\}$ all at
once, which means that $V^{t^{\prime}}=I$ for all $t^{\prime}\in[q-1]$ .
Equivalently, there is a single PVM $\Pi=\\{\Pi_{i_{1},\dots,i_{q}}\\}$ which
determines all $q(n)$-qubits to be accessed.

######  Definition 3.2 ($\mathsf{QPCP}$).

Let $n\in\mathbb{N}$ be the input size, and $x\in\\{0,1\\}^{n}$ some input. A
promise problem $A=(A_{\textup{yes}},A_{\textup{no}})$ belongs to
$\mathsf{QPCP}[k,q,p,c,s]$ if and only if there exists a uniform family of
polynomial-time $(k,q,\mathrm{poly}(n),p(n))$-$\mathsf{QPCP}$ verifier
circuits $\\{V_{n}\\}$ such that

  * Completeness. If $x\in A_{\textup{yes}}$, then there exist quantum states $\xi^{j}\in\left(\mathbb{C}^{2}\right)^{\otimes p(n)}$, $j\in[k]$, such that $V_{n}$ accepts $(x,\otimes_{j=1}^{k}\xi^{j})$ with probability at least $c$,

  * Soundness. If $y\in A_{\textup{no}}$, then for all quantum states $\xi^{j}\in\left(\mathbb{C}^{2}\right)^{\otimes p(n)}$, $j\in[k]$, we have that $V_{n}$ accepts $(x,\otimes_{j=1}^{k}\xi^{j})$ with probability at most $s$,

If $p(n)\leq\mathrm{poly}(n)$, $c=2/3$, and $s=1/3$, we simply write
$\mathsf{QPCP}[k,q]$, and if $k=1$ we abbreviate to $\mathsf{QPCP}[q]$.

######  Definition 3.2a ($\mathsf{QPCP}_{\textup{NA}}$).

This follows the same definition as for $\mathsf{QPCP}$ but now with a non-
adaptive $\mathsf{QPCP}$-verifier as per Definition 3.1a.

fig.tex

Figure 1: Visualisation of a $k$-prover quantum PCP which allows for $q$
adaptive queries to the provided quantum proof through intermediate
measurements, as per Definition 3.1.

We can easily show that in the single-prover setting we have weak error
reduction by parallel repetition by the same argument in [AN02].

######  Lemma 3.1 (Weak error reduction for the single prover case).

$\mathsf{QPCP}[c,s,1,q]=\mathsf{QPCP}[1-2^{-\mathcal{O}(t)},2^{-\mathcal{O}(t)},1,tq]$.

###### Proof.

This follows from a standard parallel repetition argument, where one has to
take special care of the fact that the proof can be entangled. Let
$\mathcal{A}$ be the $\mathsf{QPCP}$ protocol. Arthur expects to be given the
proof $\xi^{\otimes t}$, runs $\mathcal{A}$ $t$ times in parallel acting only
one $q$ qubits of each $\xi$, measures the output qubit and takes a majority
vote on the outcomes. Completeness follows directly from a standard Chernoff
bound. For soundness, let $\rho$ be the $p(n)t$-qubit proof that Merlin gives
instead of $\xi^{\otimes t}$. Let $X_{i}\in\\{0,1\\}$ be the random variable
that indicates whether the $i$’th run of the parallel repetition accepted
($X_{i}=1$) or not ($X_{i}=0$). We have that
$\mathbb{E}[X_{1}]\leq\frac{1}{3}$ since soundness holds with respect to all
quantum proofs. Now for $X_{2}$ we have that its expectation depends on the
outcome of $X_{1}$. However, we still must have the soundness condition, so we
have that $\mathbb{E}[X_{2}|X_{1}=j]\leq 1/3$ for all possible outcomes
$j\in\\{0,1\\}$. Since this holds for any $i$, we can upper bound the
acceptance probability by polynomially many independent Bernoulli trials with
bias $1/3$. Again by a standard Chernoff bound, we have that a majority vote
on the outcomes ensures that the overall acceptance probability is $\leq
2^{-\Omega(t)}$. ∎

When we have near-perfect completeness, strong error reduction is also
possible for non-adaptive quantum PCPs.

######  Claim 3.1.

[Strong error reduction for non-adaptive QPCPs with near-perfect
completeness]. For any $l\in\mathcal{O}(1)$ it holds that
$\mathsf{QPCP}_{\textup{NA}}[q,c,s,1]=\mathsf{QPCP}_{\textup{NA}}[tq,c^{\prime},s^{\prime},1]$
with $c=1-2^{-\Omega(n)}$, $s=1/2$ and $c^{\prime}=1-2^{-\Omega(n)}$,
$s^{\prime}=2^{-\mathcal{O}(l)}$.

The proof can be found in Appendix A.

##  4 Local Hamiltonians from quantum PCPs

The core of this section is Theorem 4.1, which argues that we can, from a
$\mathsf{QPCP}$ verification circuit (as in Definition 3.1) efficiently
produce a local Hamiltonian, such that the expectation value of a proof state
is given by its acceptance probability by the verifier circuit. Our
construction broadly follows the ideas in [Gri18], but also includes the more
general adaptive verifier case. This leads to a slightly more general class of
local Hamiltonians than is usually assumed in the quantum PCP literature, and
we have to perform some extra tricks to obtain the traditional Hamiltonian.

We begin by proving a basic lemma, which expresses the probability that a
proof $\xi$ gets rejected by the quantum PCP verifier $V$ conditioned on
taking the query path $(i_{1},\dots,i_{q})$, in terms of the PVMs and circuits
of $V$. Throughout this work, we make a distinction between indices indicated
surrounded by brackets (e.g. ‘$(i_{1},\dots,i_{q})$’) and those that are not
(e.g. ‘$i_{1},\dots,i_{q}$’) to make a distinction where the order does matter
(the former) and where it does not (the latter).

######  Lemma 4.1.

Let $V_{x}$ be a $q$-query adaptive quantum PCP as in Definition 3.1, with
input $x\in\\{0,1\\}^{n}$. Define
$M_{i_{q},x}^{t^{\prime}}=\Pi_{i_{q}}^{t^{\prime}}V_{x}^{t^{\prime}}$ for all
$i_{q},t^{\prime}$. The probability that the quantum PCP rejects a proof $\xi$
conditioned on taking the query path $(i_{1},\dots,i_{q})$ is given by

$\displaystyle\mathbb{P}[V_{x}\text{ rejects
}\xi|(i_{1},\dots,i_{q})]=\frac{\tr[P_{x,(i_{1},\dots,i_{q})}\rho]}{\mathbb{P}[(i_{1},\dots,i_{q})]},$

where $\mathbb{P}[(i_{1},\dots,i_{q})]$ is the probability that
$i_{1},\dots,i_{q}$ are queried (and in this order),
$\rho^{0}=\ket{0}\bra{0}^{\otimes n+p_{1}(n)}\otimes\xi$ and
$P_{x,(i_{1},\dots,i_{q})}$ a $(k+n+p_{1}(n))$-local operator given by

$\displaystyle P_{x,(i_{1},\dots,i_{q})}=M_{i_{1},x}^{1\dagger}\dots
M_{i_{q},x}^{q\dagger}V^{t\dagger}\Pi_{0}V^{t}M_{i_{q},x}^{q}\dots
M_{i_{1},x}^{1}.$

###### Proof.

This follows from a straightforward application of the rules of post-
measurement states of projective measurements. Let
$\rho^{0}=\ket{0}\bra{0}^{\otimes n+p_{1}(n)}\otimes\xi$ be the initial state
(note the extra $n$ term for the original input register). Suppose the first
PVM of the quantum PCP returned $i_{1}$, then we have that the post-
measurement state is equal to

$\displaystyle\rho^{1}=\frac{\Pi_{i_{1}}^{1}V_{x}^{0}\rho
V^{0\dagger}\Pi_{i_{1}}}{\tr[\Pi_{i_{1}}^{1}V_{x}^{0}\rho
V_{x}^{0\dagger}]}=\frac{\Pi_{i_{1}}^{1}V_{x}^{0}\rho
V_{x}^{0\dagger}\Pi^{1}_{i_{1}}}{\mathbb{P}[i_{1}]}=\frac{M_{i_{1},x}^{1}\rho
M_{i_{1},x}^{1\dagger}}{\mathbb{P}[i_{1}]}.$

Similarly, assuming outcome $i_{2}$ for the second query, we have

$\displaystyle\rho^{2}=\frac{\Pi_{i_{2}}^{2}V_{x}^{1}\rho^{1}V_{x}^{1\dagger}\Pi_{i_{2}}}{\tr[\Pi_{i_{2}}^{1}V_{x}^{1}\rho^{1}V_{x}^{1\dagger}]}=\frac{\Pi_{i_{2}}^{2}V_{x}^{1}\rho^{1}V_{x}^{1\dagger}\Pi_{i_{2}}}{\mathbb{P}[i_{2}|i_{1}]}=\frac{M_{i_{2},x}^{2}\rho^{1}M^{2\dagger}}{\mathbb{P}[i_{2}|i_{1}]}=\frac{M_{i_{2},x}^{2}M_{i_{1},x}^{1}\rho
M_{i_{1},x}^{1\dagger}M^{2\dagger}_{i_{2},x}}{\mathbb{P}[i_{2}|i_{1}]\mathbb{P}[i_{1}]}.$

Repeating this procedure $q-2$ more times, assuming outcomes
$i_{3},\dots,i_{q}$, we find that the state after the $q$’th query becomes

$\displaystyle\rho^{q}=\frac{M_{i_{q},x}^{q}\dots M_{i_{1},x}^{1}\rho
M_{i_{1},x}^{1\dagger}\dots
M_{i_{q},x}^{q\dagger}}{\prod_{l=1}^{q}\mathbb{P}[i_{l}|\bigcap_{j=1}^{l-1}i_{j}]}=\frac{M_{i_{q},x}^{q}\dots
M_{i_{1},x}^{1}\rho M_{i_{1},x}^{1\dagger}\dots
M_{i_{q},x}^{q\dagger}}{\mathbb{P}[(i_{1},\dots,i_{q})]},$

by the chain rule of probabilities. Now in the final step of the quantum PCP,
a final circuit $V_{l}$ is applied followed by the PVM $\Pi^{\text{output}}$.
We have that the expected value is then given by

$\displaystyle\mathbb{P}[V\text{ rejects
}\xi|(i_{1},\dots,i_{q})]=\tr[\Pi_{0}V^{q}\rho^{q}V^{q\dagger}]=\frac{\tr[\Pi_{0}V^{q}M_{i_{q},x}^{q}\dots
M_{i_{1},x}^{1}\rho M_{i_{1},x}^{1\dagger}\dots
M_{i_{q},x}^{q\dagger}V^{q\dagger}]}{\mathbb{P}[(i_{1},\dots,i_{q})]}.$

Using the cyclic property of the trace we can write

$\displaystyle\mathbb{P}[V\text{ rejects }\xi|(i_{1},\dots,i_{q})]$
$\displaystyle=\frac{\tr[M_{i_{1},x}^{1\dagger}\dots
M_{i_{q},x}^{q\dagger}V^{q\dagger}\Pi_{0}V^{q}M_{i_{q},x}^{q}\dots
M_{i_{1},x}^{1}\rho]}{\mathbb{P}[(i_{1},\dots,i_{q})]}$
$\displaystyle=\frac{\tr[P_{x,(i_{1},\dots,i_{q})}\rho]}{\mathbb{P}[(i_{1},\dots,i_{q})]},$

with

$\displaystyle P_{x,(i_{1},\dots,i_{q})}=M_{i_{1},x}^{1\dagger}\dots
M_{i_{q},x}^{q\dagger}V^{q\dagger}\Pi_{0}V^{q}M_{i_{q},x}^{q}\dots
M_{i_{1},x}^{1}.$

∎

With this lemma in hand we can argue that, given a verifier circuit, there
always exists a local Hamiltonian that captures the probability of acceptance
of a proof.

######  Lemma 4.2 (Hamiltonians from general quantum PCPs).

Let $q\in\mathbb{N}$ be some constant and $p_{1},p_{2}$ be polynomials. Let
$V_{x}$ be a $\mathsf{QPCP}[k,q,p_{1},p_{2}]$ verification circuit as in
Definition 3.1, with input $x$, $|x|=n$ for some $n\in\mathbb{N}$ and a
$kp_{1}$-qubit quantum proof $\xi=\otimes_{j=1}^{k}\xi^{j}$,
$\xi^{j}\in\mathcal{D}\left(\left(\mathbb{C}^{2}\right)^{\otimes
p_{1}(n)}\right)$. There exists a Hamiltonian $H$ consists of $q$-local PSD
terms acting on $kp_{1}(n)$-qubits such that for all $\xi$ we have

$\displaystyle\mathbb{P}[V_{x}\text{ accepts }\xi]=1-\tr[H_{x}\xi].$ (1)

###### Proof.

Define $\Omega=[p_{2}(n)]^{q}$ such that $|\Omega|=\binom{p_{2}(n)}{q}$. By
the definition of conditional probability

$\displaystyle\mathbb{P}[V_{x}\text{ accesses qubits $i_{1},\dots,i_{q}$ from
$\ket{\xi}$ and rejects }]$
$\displaystyle=\mathbb{P}[(i_{1},\dots,i_{q})]\cdot\mathbb{P}[V\text{ rejects
}\xi|(i_{1},\dots,i_{q})]$
$\displaystyle=\mathbb{P}[(i_{1},\dots,i_{q})]\cdot\frac{\tr[P_{x,(i_{1},\dots,i_{q})}\rho]}{\mathbb{P}[(i_{1},\dots,i_{q})]}$
$\displaystyle=\tr[P_{x,(i_{1},\dots,i_{q})}\sigma_{(i_{1},\dots,i_{q})}],$

where

$\displaystyle\sigma_{i_{1},\dots,i_{q}}=\tr_{\bar{C}_{i_{1},\dots,i_{q}}}\big{[}\xi\otimes\ket{0}\bra{0}^{\otimes
n+p_{2}(n)}\big{]}$

with $\bar{C}_{i_{1},\dots,i_{q}}$ denoting all qubits of $\xi$ except for
those with indices $i_{1},\dots,i_{q}$. Hence, we can write the probability
that $V_{x}$ rejects $\ket{\xi}$ as

$\displaystyle\mathbb{P}[V_{x}\text{ rejects }\ket{\xi}]$
$\displaystyle=\sum_{i_{1},\dots,i_{q}\in\Omega}\sum_{(i_{1},\dots,i_{q})\in\\{(i_{1},\dots,i_{q})\\}!}\tr[P_{x,(i_{1},\dots,i_{q})}\sigma_{i_{1},\dots,i_{q}}].$

For all $i_{1},\dots,i_{q}\in\Omega$, we define the $2^{q}\crossproduct 2^{q}$
matrix $H_{x,i_{1},\dots,i_{q}}$ as

$\displaystyle\bra{\alpha}H_{x,i_{1},\dots,i_{q}}\ket{\beta}$
$\displaystyle:=\sum_{(i_{1},\dots,i_{q})\in\\{(i_{1},\dots,i_{q})\\}!}\left(\bra{0}^{\otimes
p_{1}(n)+n}\otimes\bra{\alpha}\right)P_{x,(i_{1},\dots,i_{q})}\left(\ket{0}^{\otimes
p_{1}(n)+n}\otimes\ket{\beta}\right),$

where $\alpha,\beta\in\\{0,1\\}^{q}$. Observe that for any $q$-local density
matrix $\rho$ we have that the expression

$\displaystyle\tr[H_{x,i_{1},\dots,i_{q}}\rho]$
$\displaystyle=\tr[\sum_{(i_{1},\dots,i_{q})\in\\{(i_{1},\dots,i_{q})\\}!}P_{x,(i_{1},\dots,i_{q})}\ket{0}\bra{0}^{\otimes
n+p_{2}(n)}\otimes\rho]$

is the sum of all probabilities that a query path $(i_{1},\dots,i_{1})$ is
taken and the proof is rejected, taken over all possible permutations of the
indices. Hence, this means that $H_{x,i_{1},\dots,i_{q}}$ is PSD. Now consider
the $q$-local Hamiltonian $H$ defined as

$\displaystyle
H_{x}=\sum_{i_{1},\dots,i_{q}\in\Omega}H_{x,i_{1},\dots,i_{q}}.$

We have that

$\displaystyle\mathbb{P}[V_{x}\text{ accepts }\ket{\xi}]=1-\tr[H_{x}\xi],$

since by the linearity of the trace

$\displaystyle\tr[H_{x}\xi]$
$\displaystyle=\tr[\sum_{i_{1},\dots,i_{q}\in\Omega}\left(H_{x,i_{1},\dots,i_{q}}\otimes\mathbb{I}\right)\xi]$
$\displaystyle=\sum_{i_{1},\dots,i_{q}\in\Omega}\tr[\left(H_{x,i_{1},\dots,i_{q}}\otimes\mathbb{I}\right)\xi]$
$\displaystyle=\sum_{i_{1},\dots,i_{q}\in\Omega}\tr[H_{x,i_{1},\dots,i_{q}}\tr_{\bar{C}_{i_{1},\dots,i_{q}}}[\xi]]$
$\displaystyle=\sum_{i_{1},\dots,i_{q}\in\Omega}\sum_{(i_{1},\dots,i_{q})\in\\{(i_{1},\dots,i_{q})\\}!}\tr[P_{x,(i_{1},\dots,i_{q})}\sigma_{(i_{1},\dots,i_{q})}]$
$\displaystyle=\sum_{i_{1},\dots,i_{q}\in\Omega}\sum_{(i_{1},\dots,i_{q})\in\\{(i_{1},\dots,i_{q})\\}!}\mathbb{P}[(i_{1},\dots,i_{q})]\mathbb{P}[V\text{
rejects }\xi|(i_{1},\dots,i_{q})]$ $\displaystyle=\mathbb{P}[V\text{ rejects
}\xi]$ $\displaystyle=1-\mathbb{P}[V\text{ accepts }\xi],$

which also implies that $H_{x,i_{1},\dots,i_{q}}\preceq 1$ for all
$i_{1},\dots,i_{1}\in\Omega$. ∎

###  4.1 Learning the Hamiltonian

We have shown that the probability that a $\mathsf{QPCP}$ accepts a certain
proof is equivalent to the expectation value of some Hamiltonian. We still
have to show how to obtain the entries of each term efficiently. Before we
state the final protocol, let us argue that we can indeed learn each local
term up to arbitrary (inverse polynomial) precision. To do this we will use
the Hadamard test.

######  Lemma 4.3 (Hadamard test [AJL06]).

Let $\ket{\psi},\ket{\phi}\in\mathbb{C}^{2^{n}}$ be quantum states with state
preparation unitaries $U_{\phi}$, $U_{\psi}$, i.e.
$\ket{\psi}=U_{\psi}\ket{0^{n}}$ and $\ket{\phi}=U_{\phi}\ket{0^{n}}$. Let
$W\in\mathbb{U}(2^{n})$ be some unitary. Then there exists a quantum algorithm
$\mathcal{A}$ that outputs an estimate $\hat{z}$ such that

$\displaystyle\absolutevalue{\hat{z}-\text{Re}(\bra{\psi}W\ket{\phi})}\leq\epsilon$

with probability $\geq 1-\delta$, in

$\displaystyle\mathcal{O}\left(\frac{\log\left(\frac{1}{\delta}\right)}{\epsilon^{2}}\right).$

(controlled) queries to $U_{\psi}$, $U_{\phi}$ and $W$. Similarly, there
exists a quantum algorithm to estimate $\text{Im}(\bra{\psi}W\ket{\phi})$ at
the cost of applying one additional single-qubit gate.

Note that the Hadamard test only works for unitaries. Therefore, for our
purposes we also need the following lemma, which shows that every (local)
projector on a basis state can be written as a linear combination of unitaries
with short circuit depth.

######  Lemma 4.4.

Let $\Pi_{q}=\ket{q}\\!\bra{q}$, $q\in\\{0,1\\}^{k}$ be a projection on a
basis state $\ket{q}$. Then $\Pi_{q}$ can be written as

$\displaystyle\Pi_{q}=\bigotimes_{i\in[n]}\frac{Z_{i}+(1-2q_{i})I}{2}=\sum_{j\in[2^{k}]}\alpha_{i}U_{j},$

where $U_{j}$ are depth $1$ unitaries and $\alpha_{j}\in\\{-1,+1\\}$.

###### Proof.

We have that $\ket{0}\\!\bra{0}=(Z+I)/2$ and $\ket{1}\\!\bra{1}=(Z-I)/2$.
Hence, for $q_{i}\in\\{0,1\\}$, we have
$\ket{q_{i}}\bra{q_{i}}=\frac{(Z_{i}+(1-2q_{i})I}{2}$. Since
$\ket{q}\bra{q}=\bigotimes_{i\in[n]}\ket{q_{i}}\bra{q_{i}}$, we have that

$\displaystyle\Pi_{q}=\bigotimes_{i\in[n]}\ket{q_{i}}\bra{q_{i}}=\bigotimes_{i\in[n]}\frac{Z_{i}+(1-2q_{i})I}{2}=\sum_{j\in[2^{k}]}\alpha_{i}U_{j},$
(2)

where the $U_{j}$ are of the form $\alpha_{j}V^{j}_{1}\otimes
V_{2}^{j}\otimes\dots\otimes V_{k}^{j}$ for $V_{i}^{j}\in\\{I,Z\\}$, and thus
have circuit depth $1$. ∎

Before we move to prove the existence of the reduction, we have to define some
parameters. The operators $H_{x,i_{1},\dots,i_{q}}$ are composed of $q+1$
unitaries $V^{t}$, a total of $q$ of $\mathcal{O}(\log n)$-local PVMs (the
$\Pi^{t}$’s), and a single $1$-local PVM (which is $\Pi_{\text{output}}$).
Decomposing every PVM in $H_{x,i_{1},\dots,i_{q}}$ into unitaries, as per
Lemma 4.4, define $\Gamma:=(q+1)2kp_{1}(n)$ to be the total number of
unitaries in the linear combination. Concretely we can write:

$\displaystyle\bra{\alpha}H_{x,i_{1},\dots,i_{q}}\ket{\beta}$
$\displaystyle=\sum_{(i_{1},\dots,i_{q})\in
S(\\{(i_{1},\dots,i_{q})\\}}\sum_{j\in[\Gamma]}\alpha_{j}\left(\bra{0}\otimes\bra{\alpha}\otimes\bra{0}^{\otimes
q(n)}\right)\prod_{l\in[4q+3]}U^{l}_{j,x}\left(\ket{0}\otimes\ket{\beta}\otimes\ket{0}^{\otimes
q(n)}\right),$

where $U^{l}_{j,x}$ are unitaries of depth $1$ or at most $\mathrm{poly}(n)$
and $\alpha_{j}\in\\{-1,+1\\}$. We define

$\displaystyle
z_{(i_{1},\dots,i_{q})}^{\alpha,\beta,j}:=\left(\bra{0}\otimes\bra{\alpha}\otimes\bra{0}^{\otimes
q(n)}\right)\prod_{l\in[4q+3]}U^{l}_{x}\left(\ket{0}\otimes\ket{\beta}\otimes\ket{0}^{\otimes
q(n)}\right),$ (3)

and

$\displaystyle
h_{i_{1},\dots,i_{q}}^{\alpha,\beta}=\sum_{(i_{1},\dots,i_{q})\in
S(\\{(i_{1},\dots,i_{q})\\}}\sum_{j\in[\Gamma]}\alpha_{j}z_{(i_{1},\dots,i_{q})}^{\alpha,\beta,j}$
(4)

such that

$\displaystyle\bra{\alpha}H_{x,i_{1},\dots,i_{q}}\ket{\beta}=h_{i_{1},\dots,i_{q}}^{\alpha,\beta},$

for all $\alpha,\beta,i_{1},\dots,i_{q}$.

######  Theorem 4.1.

Let $q\in\mathbb{N}$ be some constant and $p_{1},p_{2}$ be polynomials. Let
$V_{x}$ be a $\mathsf{QPCP}_{\textup{A}}[k,q,p_{1},p_{2}]$ verification
circuit as in Definition 3.1, taking input $x$, $|x|=n$ for some
$n\in\mathbb{N}$ and a $kp_{1}$-qubit quantum proof $\xi$. For all
$\epsilon>0$ there exists a quantum reduction from $V_{x}$ to a $q$-local
Hamiltonian $\hat{H}_{x}$ with $\norm{\hat{H}_{x}}\leq 1$ such that, given a
proof $\ket{\xi}$,

$\displaystyle\absolutevalue{\mathbb{P}[V_{x}\text{ accepts
}\ket{\xi}]-\left(1-\bra{\xi}\hat{H}_{x}\ket{\xi}\right)}\leq\epsilon.$ (5)

The reduction succeeds with probability $1-\delta$ and runs in time
$\mathrm{poly}(n,1/\epsilon,\log(1/\delta))$.

###### Proof.

The reduction is specified in 4.1 below. We proceed to show its correctness,
by arguing it has the required precision, success probability, and time
complexity.

##### Precision:

Step $1.a$ of Protocol 4.1 produces estimates
$\tilde{z}_{(i_{1},\dots,i_{q})}^{\alpha,\beta,j}$ for the parameters
$z_{(i_{1},\dots,i_{q})}^{\alpha,\beta,j}$ using Lemma 4.3. We have that

$\displaystyle\absolutevalue{z_{(i_{1},\dots,i_{q})}^{\alpha,\beta,j}-\tilde{z}_{(i_{1},\dots,i_{q})}^{\alpha,\beta,j}}\leq
2\epsilon^{\prime},$

since we estimated both the real and imaginary parts up to precision
$\epsilon^{\prime}$.

By the triangle inequality (and $\alpha_{j}\in\\{1,-1\\}$) we now have

$\displaystyle\absolutevalue{\tilde{h}^{\alpha,\beta}_{(i_{1},\dots,i_{q})}-\bra{\alpha}H_{x,i_{1},\dots,i_{q}}\ket{\beta}}\leq
2\Gamma q!\epsilon^{\prime}.$

Since
$\tilde{H}_{x,i_{1},\dots,i_{q}}=\sum_{\alpha,\beta\in\\{0,1\\}^{q}}\tilde{h}^{\alpha,\beta}_{i_{1},\dots,i_{q}}\ket{\alpha}\bra{\beta}$,
we have that

$\displaystyle\norm{\tilde{H}_{x,(i_{1},\dots,i_{q})}-H_{x,i_{1},\dots,i_{q}}}$
$\displaystyle\leq
2^{q}\max_{\alpha,\beta}\absolutevalue{\bra{\alpha}H_{x,i_{1},\dots,i_{q}}\ket{\beta}-\bra{\alpha}\tilde{H}_{x,(i_{1},\dots,i_{q})}\ket{\beta}}$
$\displaystyle\leq 2^{q+1}\Gamma q!\epsilon^{\prime},$

which follows from the bound on the operator norm by the max-norm. Now suppose
that $\tilde{H}_{x,(i_{1},\dots,i_{q})}$ is not PSD. Since
$H_{x,i_{1},\dots,i_{q}}$ is PSD, we have that
$\lambda_{\textup{min}}(\tilde{H}_{x,(i_{1},\dots,i_{q})})\geq-2^{q+1}\Gamma
q!\epsilon^{\prime}$, so we have that adding the identity term can only double
the error to $2^{q+2}\Gamma q!\epsilon^{\prime}$. By the triangle inequality

$\displaystyle\norm{\tilde{H}_{x}-H_{x}}\leq|\Omega|2^{q+2}\Gamma
q!\epsilon^{\prime}\leq\epsilon/4,$

for our choice of $\epsilon^{\prime}$. Finally, the error introduced by step 3
of the protocol can be bounded by

$\displaystyle\norm{\hat{H}_{x}-H_{x}}$
$\displaystyle\leq\norm{\hat{H}_{x}-\tilde{H}_{x}}+\norm{\tilde{H}_{x}-H_{x}}$
$\displaystyle\leq\absolutevalue{\frac{1}{1+\epsilon/4}-1}\norm{\tilde{H}_{x}}+\frac{\epsilon}{4}$
$\displaystyle\leq\frac{\epsilon}{4}(1+\frac{\epsilon}{4})+\frac{\epsilon}{4}$
$\displaystyle=\frac{\epsilon}{2}+\left(\frac{\epsilon}{4}\right)^{2}$
$\displaystyle\leq\epsilon,$

as desired.

##### Success probability:

We have to count the number of times we run the Hadamard test of Lemma 4.3,
each of which succeeds with success probability $\geq 1-\delta^{\prime}$.
Recall that $\Omega$ is the set of all possible indices (when order does not
matter), which is given by $[p_{2}(n)]^{k}$ for proofs of length $p_{2}$. We
run the Hadamard test for a total of $|\Omega|q!4^{q}\Gamma$ times (see the
number of iterations in protocol 4.1), and thus

$\displaystyle(1-\delta^{\prime})^{|\Omega|q!4^{q+1}\Gamma}\geq
1-\delta^{\prime}{|\Omega|q!4^{q+1}\Gamma}=1-\delta,$

using the inequality $(1-x)^{T}\geq 1-Tx$ for all $x\in[0,1]$. Here the extra
factor of two again accounts for the fact that we have to estimate both the
real and imaginary parts.

##### Time complexity:

By definition of $\mathsf{QPCP}[q]$, we have that $V$ has gate complexity
$\mathrm{poly}(n)$. Using Lemma 4.4, we have that $V$, $U_{\phi}$ and
$U_{\psi}$ always have polynomially bounded gate complexities. Filling in our
choice of $\delta^{\prime}$ and $\epsilon^{\prime}$, we have that the total
number of (controlled) applications of $V$, $U_{\phi}$ and $U_{\psi}$ can be
upper bounded as

$\displaystyle\mathcal{O}\left(q!4^{q+1}\Gamma\frac{(|\Omega|2^{q+3}\Gamma
q!)^{2}\log\left(\frac{q!4^{q+1}\Gamma}{\delta}\right)}{\epsilon^{2}}\right)=\mathrm{poly}(n,1/\epsilon,\log(1/\delta))$

since for $k=\mathrm{poly}(n)$ and $q=\mathcal{O}(1)$ we have
$|\Omega|=\mathrm{poly}(n)$ and $\Gamma=\mathrm{poly}(n)$. ∎

Protocol 1: Quantum reduction from $\mathsf{QPCP}{[k,q]}$ to
$q$-$\mathsf{LH}{[\Theta(1)]}$ Input: A
$(k,q,p_{1},p_{2})\text{-}\mathsf{QPCP}$-verifier $V_{x}$ hardwired input $x$,
a precision parameter $\epsilon$ and a desired success probability $\delta$.
Set $\Omega:=[p_{2}(n)]^{q}$, $\Gamma:=2(q+1)kp_{1}(n)$,
$\epsilon^{\prime}:=\frac{\epsilon}{|\Omega|2^{q+4}\Gamma q!}$,
$\delta^{\prime}:=\frac{\delta}{|\Omega|q!4^{q+1}\Gamma}$. 1. For
$i_{1},\dots,i_{q}\in\Omega$ (a) For all
$(i_{1},\dots,i_{q})\in\\{i_{1},\dots,i_{q}\\}!$ i. For
$\alpha\in\\{0,1\\}^{q}$, $\beta\in\\{0,1\\}^{q}$: • For $j\in[\Gamma]$
compute $\alpha_{j},U_{j}$ and estimate
$z_{(i_{1},\dots,i_{q})}^{\alpha,\beta,j}$ as
$\tilde{z}_{(i_{1},\dots,i_{q})}^{\alpha,\beta,j}$ using Lemma 4.3 for both
the real and imaginary part with $V=U_{j}$,
$U_{\theta}=\hat{V}(\otimes_{i=1}^{q}(X_{i})^{\alpha_{i}}\otimes I)$ and
$U_{\phi}=\hat{V}(\otimes_{i=1}^{q}(X_{i})^{\beta_{i}}\otimes I)$,
$\epsilon^{\prime}$ and $\delta^{\prime}$. ii. Set
$\tilde{h}^{\alpha,\beta}_{i_{1},\dots,i_{q}}=\sum_{(i_{1},\dots,i_{q})\in
S(\\{(i_{1},\dots,i_{q})\\}}\sum_{j\in[\Gamma]}\alpha_{j}\tilde{z}_{(i_{1},\dots,i_{q})}^{\alpha,\beta,j}$.
(b) Set
$\tilde{H}_{x,(i_{1},\dots,i_{q})}=\sum_{\alpha,\beta\in\\{0,1\\}^{q}}\tilde{h}^{\alpha,\beta}_{i_{1},\dots,i_{q}}\ket{\alpha}\bra{\beta}$.
(c) Compute $\lambda_{\text{min}}(\tilde{H}_{x,(i_{1},\dots,i_{q})})$. If
$\lambda_{\text{min}}(\tilde{H}_{x,(i_{1},\dots,i_{q})})<0$, let
$\tilde{H}_{x,(i_{1},\dots,i_{q})})\leftarrow\tilde{H}_{x,(i_{1},\dots,i_{q})})-\lambda_{\text{min}}(\tilde{H}_{x,(i_{1},\dots,i_{q})})\mathbb{I}$,
else continue. 2. Let
$\tilde{H}_{x}=\sum_{i_{1},\dots,i_{q}\in\Omega}\tilde{H}_{x,(i_{1},\dots,i_{q})}$.
Output
$\displaystyle\hat{H}_{x}=\frac{\tilde{H}_{x}}{\text{argmax}\\{\norm{\tilde{H}_{x}},1\\}}.$

One can use a simple trick that exploits the freedom we have in the reduction
to set the precision. Since every local term is bounded in the operator norm,
we must also have that for each of these terms the matrix entries are bounded
by $1$. Hence, we can convert a bound in terms of approximation in entry-wise
error to one in having a least a certain number of bits from a certain bit-
wise representation of the value being correct. The advantage of the latter is
that it allows us to make the reduction deterministic in the sense that if it
succeeds, it always produces _exactly_ the same Hamiltonian. This can
alternatively be viewed as having a ‘rounding scheme’ which, with high
probability, always rounds to the same operator in operator space. Though not
strictly needed, this allows one to always reason about the same Hamiltonian
when the reduction is used as a subroutine.

######  Corollary 4.1.

There exists a quantum algorithm which produces a fixed Hamiltonian
$\tilde{H_{x}}$ with probability $1-\delta$ which satifies Eq. (5) for any
$\epsilon>0$ and runs in time $\mathrm{poly}(n,1/\epsilon,\log(1/\delta))$.

We have put the proof of Corollary 4.1 in Appendix C

######  Remark 2.

Unlike these general quantum PCPs, where the probabilities of taking a certain
query path can depend on the proof, we have that for non-adaptive quantum PCPs
the probability distribution over which the proof is accessed only depends on
the input. Generalising the proof of Lemma 6.3 in [WFC23], one can easily
verify that for non-adaptive quantum PCPs the obtained Hamiltonian can be
assumed to be of the form $H_{x}=\sum_{i\in[m]}p_{x,i}H_{x,i}$, where the
$p_{x,i}$’s form a probability distribution and $0\preceq H_{x,i}\preceq 1$
for all $q$-local terms. For these general (adaptive) quantum PCPs, the key
difference is that each term of the Hamiltonian encodes both the probability
that certain parts of the proof are accessed as well as the eventual
probability of acceptance. We have provided sufficient conditions on the error
parameters of the reduction in Appendix B.

###  4.2 Local smoothings of local Hamiltonians

In this subsection we show that one can always transform any Hamiltonian in
the form of $H_{x}$ of Eq. (1) to match the form usually adopted in the
literature; specifically, we want to transform a local Hamiltonian with PSD
terms, operator norm at most $1$ and constant promise gap to another
Hamiltonian such that the promise gap becomes $\Omega(m)$, where $m$ is the
number of terms in the new Hamiltonian, whilst still having that each term
$H_{i}$ is local and satisfies $\norm{H_{i}}\leq 1$. This way, we have that at
least a constant fraction of all the $m$ terms contribute to the energy in the
No-case, which intuitively implies that only a constant number of terms have
to be checked to find out whether the energy of the Hamiltonian is high or low
(see Subsection 4.3). This turns out to be possible at the cost of increasing
the locality by a factor of two and the promise gap by a constant factor.555We
believe such a result might be known in existing literature, but as we could
not find a reference we provide a proof for completeness.

######  Lemma 4.5 (Hamiltonian local smoothing lemma).

Let $H$ be a $q$-local Hamiltonian on $n$-qubits such that
$H=\sum_{i\in[m]}H_{i}$, $\norm{H}\leq 1$ and $\lambda_{\textup{min}}(H)\leq
a$ or $\geq b$ for $b-a=\gamma(m)$. Then there exists a polynomial time
reduction to another $2q$-local Hamiltonian $H^{\prime}$ on $n$ qubits such
that $H^{\prime}=\frac{1}{m}\sum_{i\in[m^{\prime}]}H^{\prime}_{i}$,
$\norm{H^{\prime}_{i}}\leq 1$ for all $i\in[m^{\prime}]$ and
$\lambda_{\textup{min}}(H)\leq\alpha$ or $\geq\beta$ for some $\beta,\alpha$
such that $\beta-\alpha\in\Omega(\gamma(m))$.

###### Proof.

Write $\rho_{d}=\frac{\mathbb{I}_{d}}{d}$ for the $d$-dimensional maximally
mixed state. We have by the variational principle that

$\displaystyle\tr\left[H\rho_{2^{n}}\right]=\tr\left[\sum_{i\in[m]}H_{i}\tr_{\bar{C}_{i}}\left[\rho_{2^{n}}\right]\right]=\tr\left[\sum_{i\in[m]}H_{i}\rho_{2^{q}}\right]=\frac{1}{2^{q}}\sum_{i\in[m]}\tr[H_{i}]\leq\max_{\xi}\tr[H\xi]\leq\norm{H}\leq
1,$

which implies

$\displaystyle\sum_{i\in[m]}\norm{H_{i}}\leq\sum_{i\in[m]}\tr[H_{i}]\leq
2^{q}.$

Since we have that $\norm{H_{i}}\leq\tr[H_{i}]$, since $0\preceq H_{i}\preceq
1$. Now consider $\hat{H}=\sum_{i\in[m]}\hat{H}_{i}$ where
$\hat{H}_{i}=\frac{1}{2^{q+3}}H_{i}$. We have that
$\lambda_{\textup{min}}(\hat{H})\geq\frac{b}{2^{q+3}}$ or
$\lambda_{\textup{min}}(\hat{H})\leq\frac{a}{2^{q+3}}$. Let
$\alpha_{i}=\norm{\hat{H}_{i}}$, for which we know that
$\sum_{i\in[m]}\alpha_{i}\leq\frac{1}{8}$. Define the sets

$\displaystyle L\subseteq[m]\quad$
$\displaystyle:\alpha_{i}\leq\frac{1}{2m}\forall i\in L,$ $\displaystyle
U=[m]\setminus L\quad$ $\displaystyle:\alpha_{i}>\frac{1}{2m}\forall i\in U.$

We must have that $|L|/2m\leq 1/8$, which implies $|L|\leq m/4$ and thus
$|S|\geq 3m/4$. We now want to construct yet another Hamiltonian $\tilde{H}$
of the form

$\displaystyle\tilde{H}=\frac{1}{m}\sum_{i\in[m]}\tilde{H}_{i}$

such that each $\tilde{H_{i}}$ is $\mathcal{O}(1)$-local and has
$\norm{\tilde{H}_{i}}\leq 1$. We will now use the following strategy to turn
the Hamiltonian $\hat{H}$ into $\tilde{H}$ by grouping the terms in a greedy
way:

  1. 1.

Initialise $L^{\prime}:=L$.

  2. 2.

For each $i\in U$, we compute

$\displaystyle
t_{i}=\lceil\frac{\alpha_{i}-\frac{1}{m}}{\frac{1}{m}-\frac{b}{2^{q+1}}}\rceil,$

and add $\frac{2-a}{m}H_{i}$ to the first $t_{i}$ entries $H_{i}$ with $i\in
L^{\prime}$. These $\tilde{H_{i}}$’s become $2q$-local and have operator norm
$\leq 2$. Remove these entries for $L^{\prime}$ and continue.

  3. 3.

Return $\tilde{H}/2$

To prove correctness, we only have to show that we never exceed the number of
entries in $L^{\prime}$. To show this, first notice that

$\displaystyle\frac{\alpha_{i}-\frac{1}{m}}{\frac{1}{m}-\frac{b}{2^{q+1}}}=\left(\alpha_{i}-\frac{1}{m}\right)\frac{m}{1-2^{-q-1}b}\leq\frac{\alpha_{i}m}{1-2^{-q-1}b}\leq
2\alpha_{i}m,$

using that $b\leq 1$ and $q\geq 1$. Therefore,

$\displaystyle\sum_{i\in U}t_{i}=\sum_{i\in
U}\lceil\frac{\alpha_{i}-\frac{1}{m}}{\frac{1-a}{m}}\rceil\leq\sum_{i\in
U}\frac{\alpha_{i}-\frac{1}{m}}{\frac{1-a}{m}}+1\leq\frac{m}{4}+\frac{m}{4}\leq
3m/4,$

which is smaller than the number of terms we could use, since $|L|\geq 3m/4$.
We have that the promise gap has shrunk by a factor $1/2^{q+4}$, which is
still constant when $q$ is constant.

∎

###  4.3 Kitaev’s energy estimation protocol

In this section we saw that general quantum PCP can be transformed into a
local Hamiltonian with a constant promise gap (and a specific form). In the
following sections it will prove useful to have a verifier for the local
Hamiltonian problem suitable for Hamiltonians from quantum PCP verifiers. For
this we will use Kitaev’s $\mathsf{QMA}$-protocol for the local Hamiltonian
problem [KSV02], albeit with a small modification to allow for sampling the
terms according to some probability weights associated with the Hamiltonian.

######  Lemma 4.6 (Kitaev’s energy estimation protocol for weighted local
Hamiltonians).

Let $H=\sum_{i\in[m]}p_{i}H_{i}$ be a $q$-local, $n$-qubit Hamiltonian with
$\sum_{i\in[m]}p_{i}=1$, $p_{i}\geq 0$ and $0\preceq H\preceq 1$ for all
$i\in[m]$. Then given a $n$-qubit quantum state $\ket{\psi}$, there exists a
measurement on $q$ qubits of $\ket{\psi}$ which outputs $1$ with probability

$\displaystyle 1-\bra{\psi}H\ket{\psi}.$ (6)

###### Proof.

This follows from a simple generalisation of Kitaev’s original
$\mathsf{QMA}$-verification protocol [KSV02]. For each $H_{i}$, $i\in[m]$, let
$H_{i}=\sum_{j}\lambda_{i,j}\ket{\lambda_{i,j}}\bra{\lambda_{i,j}}$ be its
spectral decomposition. Define the operator $W_{i}$ as

$\displaystyle
W_{i}\ket{\lambda_{i,j}}\ket{b}=\ket{\lambda_{i,j}}\left(\sqrt{\lambda_{i,j}}\ket{b}+\sqrt{1-\lambda_{i,j}\ket{b\oplus
1}}\right).$ (7)

Let us now show the correctness of Protocol 4.3. For fixed $i$, let
$\ket{\psi}=\sum_{j}\alpha_{i,j}\ket{\lambda_{i,j}}\ket{\gamma_{i,j}}$ be the
Schmidt decomposition of $\ket{\psi}$ in the eigenbasis of $H_{i}$. We have
that the probability that this protocol accepts, conditioned on picking term
$i$ is given by

$\displaystyle\mathbb{P}[\mathcal{V}\text{ accepts }\ket{\psi}|i]$
$\displaystyle=\norm{(I\otimes\ket{1}\bra{1})(I\otimes
W_{i})\ket{\psi}\ket{0}}_{2}^{2}$
$\displaystyle=\left(\sum_{j}\bar{\alpha}_{i,j}\bra{\lambda_{i,j}}\bra{\gamma_{i,j}}\bra{0}\right)W^{\dagger}_{i}(I\otimes\ket{1}\bra{1})W_{i}\left(\sum_{j}\alpha_{i,j}\ket{\lambda_{i,j}}\ket{\gamma_{i,j}}\ket{0}\right)$
$\displaystyle=\left(\sum_{j}\bar{\alpha}_{i,j}\sqrt{1-\lambda_{l,j}}\bra{\lambda_{i,j}}\bra{\gamma_{i,j}}\bra{0}\right)\left(I\otimes\ket{1}\bra{1}\right)\left(\sum_{j}\alpha_{i,j}\sqrt{1-\lambda_{i,j}}\ket{\lambda_{i,j}}\ket{\gamma_{i,j}}\ket{0}\right)$
$\displaystyle=\sum_{j}\left(1-\lambda_{i,j}\right)\bar{\alpha}_{i,j}\alpha_{i,j}$
$\displaystyle=1-\bra{\psi}H_{i}\ket{\psi}.$

The overall acceptance probability is then given by the expectation value over
all choices of $i$, which is

$\displaystyle\mathbb{P}[\mathcal{V}\text{ accepts
}\ket{\psi}]=\sum_{i\in[m]}p_{i}\mathbb{P}[\mathcal{V}\text{ accepts
}\ket{\psi}|i]=1-\bra{\psi}\sum_{i\in[m]}p_{i}H_{i}\ket{\psi}=1-\bra{\psi}H\ket{\psi}.$

∎

Protocol 2: Kitaev’s energy estimation protocol (non-uniform) Input: A
$n$-qubit, $q$-local Hamiltonian of the form $H=\sum_{i\in[m]}p_{i}H_{i}$ for
weights $p_{i}$, $\sum_{i}p_{i}=1$. 1. The prover sends the state
$\ket{\psi}$. 2. The verifier picks a $i\in[m]$ with probability $p_{i}$, and
applies $W_{i}$ (from Lemma 4.6) on $\ket{\psi}\ket{0}$, and measures the
final qubit. 3. The verifier accepts if and only if the outcome is $\ket{1}$.

######  Remark 3.

Kitaev’s energy estimation protocol (Protocol 4.3) is in fact a
$\mathsf{QPCP}_{\textup{NA}}(1,q,p,c,s)$-protocol where $c$ and $s$ are the
energies of the Hamiltonian in the Yes\- and No-case, respectively. Using
Lemma 4.5 in combination with weak error reduction (Lemma 3.1), we can
therefore solve any local Hamiltonian with PSD terms having constant promise
gap with Kitaev’s energy estimation protocol.

##  5 Applications

This section contains the main results of the paper, which are all derived
(with varying degrees of overhead) by using the reduction we argued above as a
subroutine. There are three subsections, which can be read more or less
independently.

###  5.1 Proof checking versus local Hamiltonian formulations of quantum PCP

The goal of this subsection is proving theorem 5.1. We will utilize the fact
that any $\mathsf{QCMA}$-verifier would able to perform the reduction in
Protocol 4.1 (up to a polynomial number of bits of precision). This can be
used to show that a $\mathsf{QCMA}$ upper bound on the local Hamiltonian
problem with constant promise gap implies a $\mathsf{QCMA}$ upper bound on a
quantum PCP system with the same locality.

Protocol 3: $\mathsf{QCMA}$ protocol for $\mathsf{QPCP}{[\mathcal{O}(1)]}$
assuming that $q$-$\mathsf{LH{[\Theta(1)]}}\in\mathsf{QCMA}$. Input: A
$(k,q,p_{1},p_{2})\text{-}\mathsf{QPCP}$-verifier $V_{x}$ with input $x$
hardwired into it, completeness and soundness parameters $c,s$.
Set $\epsilon:=(c-s)/4$, $\Gamma:=2(q+1)kp_{1}(n)$, $\eta:=\lceil
q\log_{2}\left(\frac{4\Gamma(\Gamma+1)}{\epsilon}-1\right)\rceil$,
$a:=c+\epsilon/4$ and $b:=c-\epsilon/4$. 1. The prover sends the witness $y$.
2. The verifier performs protocol 4.1 to obtain a $q$-local Hamiltonian
$\hat{H}=\sum_{i\in[m]}H_{i}$ up to $\eta$ bits of precision. 3. It accepts if
and only if the $\mathsf{QCMA}$ protocol with witness $y$ for $(\hat{H},a,b)$
accepts.

######  Theorem 5.1 (Local Hamiltonian versus proof verification).

If the $q$-local Hamiltonian problem with a constant promise gap can be
decided in $\mathsf{QCMA}$, we have that

$\displaystyle\mathsf{QPCP}[q]\subseteq\mathsf{QCMA},$

for all constant $q\in\mathbb{N}$.

###### Proof.

Let $A=(A_{\textup{yes}},A_{\textup{no}})$ be any promise problem in
$\mathsf{QPCP}[q]$, $x$ be an input, $V_{x}$ the $\mathsf{QPCP}$ verifier with
$x$ hardcoded into it and let $H_{x}$ be corresponding local Hamiltonian, as
per Lemma 4.2. Let $a:=c+\epsilon/4$ and $b:=c-\epsilon/4$, such that
$a-b\in\Theta(1)$. By the assumption of the theorem, we must have that there
exists a $\mathsf{QCMA}$ circuit $V$ such that

  * •

if $\lambda_{\textup{min}}(H)\leq a$ $\exists y\in\\{0,1\\}^{p(n)}$ :
$\mathbb{P}[V(H,a,b,\ket{y})\text{ accepts}]\geq 1-\delta^{\prime}$,

  * •

if $\lambda_{\textup{min}}(H)\geq b$ $\forall y\in\\{0,1\\}^{p(n)}$ :
$\mathbb{P}[V(H,a,b,\ket{y})\text{ rejects}]\geq 1-\delta^{\prime}$,

for some polynomial $p(n)$ and any $\delta^{\prime}=\Omega(2^{-n})$, since
$\mathsf{QCMA}$ allows for error reduction. Consider Protocol 5.1: let
$V^{\prime}$ be the $\mathsf{QCMA}$ circuit which first performs the quantum
reduction to find $H$ up to $\eta$ bits of precision and then runs
$V(H,a,b,\ket{y})$. If the reduction succeeds with probability
$1-\delta\geq\sqrt{2/3}$, we have that for $1-\delta^{\prime}=\sqrt{2/3}$ that

  * •

if $x\in A_{\textup{yes}}$ $\exists y\in\\{0,1\\}^{p(n)}$ :
$\mathbb{P}[V^{\prime}(x,\ket{y})\text{ accepts}]\geq 2/3$,

  * •

if $x\in A_{\textup{yes}}$ $\forall y\in\\{0,1\\}^{p(n)}$ :
$\mathbb{P}[V^{\prime}(x,\ket{y})\text{ accepts}]\leq 1/3$,

which means $\mathsf{QPCP}[q]\subseteq\mathsf{QCMA}$. ∎

###  5.2 Adaptive versus non-adaptive quantum PCPs

In this subsection we argue that non-adaptive QPCPs can simulate adaptive
QPCPs, with only constant overhead, similar to the classical case.

We will first prove that we can transform the local Hamiltonian corresponding
to the non-adaptive quantum PCP in a form suitable for Lemma 4.6. We can in
principle use Lemma 4.5 for this, but this has worse parameters than the ones
we can obtain through a more direct approach.

######  Lemma 5.1.

Let $H=\sum_{i\in[m]}H_{i}$ be a Hamiltonian such that $0\preceq H_{i}\preceq
1$ for all $i\in[m]$ and $\norm{H}\leq 1$. Then there exists a polynomial time
reduction to another Hamiltonian $\hat{H}=\sum_{i\in[m]}p_{i}\hat{H}_{i}$ such
that $\norm{\hat{H}_{i}}=1$, $p_{i}\geq 0$ for all $i\in[m]$ and
$\sum_{i\in[m]}p_{i}=1$. Moreover, we have that

$\displaystyle\lambda_{\textup{max}}(\hat{H})-\lambda_{\textup{min}}(\hat{H})\geq\frac{\lambda_{\textup{max}}({H})-\lambda_{\textup{min}}({H})}{2^{q}}$

###### Proof.

Just as was the case in the proof of Lemma 4.5, we have

$\displaystyle\sum_{i\in[m]}\norm{H_{i}}\leq 2^{q}.$

Let’s define $W=\sum_{i\in[m]}\norm{H_{i}}\leq 2^{q}$. We can now construct
the Hamiltonian $\hat{H}$ (in polynomial time) given by

$\displaystyle\hat{H}=\sum_{i\in[m]}p_{i}\hat{H}_{i}$

where

$\displaystyle p_{i}=\frac{\norm{H}}{W},\text{ and
}\hat{H}_{i}=\frac{H_{i}}{\norm{H}_{i}},$

such that $\sum_{i\in[m]}p_{i}=1$ and $\norm{\hat{H}_{i}}=1$ for all
$i\in[m]$. Since $\hat{H}=\frac{H}{W}$, we have that

$\displaystyle\lambda_{\textup{max}}(\hat{H})-\lambda_{\textup{min}}(\hat{H})=\frac{\lambda_{\textup{max}}({H})-\lambda_{\textup{min}}({H})}{W}\geq\frac{\lambda_{\textup{max}}(\hat{H})-\lambda_{\textup{min}}(\hat{H})}{2^{q}}.$

∎

This implies the following corollary, by again using the trick of
incorporating the reduction to a local Hamiltonian as a pre-processing step of
a quantum PCP.

######  Corollary 5.1.

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

$\displaystyle\mathsf{QPCP}[c,s,q]\subseteq\mathsf{QPCP}_{\textup{NA}}[c^{\prime},s^{\prime},q],$

where $c^{\prime}-s^{\prime}\geq\frac{c-s}{2^{q}}$.

By using our error reduction lemma (Lemma 3.1) for non-adaptive quantum PCPs,
we can show that any constant-query non-adaptive quantum PCP can simulate a
constant query adaptive PCP at the cost of an increased constant number of
queries.

Protocol 4: Non-adaptive simulation of an adaptive quantum PCP Input: An
adaptive quantum PCP verifier $V$, input $x$.
Set $\epsilon:=0.01$, $\delta=\delta^{\prime}:=\sqrt{\frac{2}{3}}$,
$\gamma=\frac{1/3-2\epsilon}{2^{q}}$, $\Gamma:=(q+1)2kp_{1}(n)$, $\eta:=\lceil
q\log_{2}\left(\frac{4\Gamma(\Gamma+1)}{\epsilon}-1\right)\rceil$. 1. The
prover sends the state $\ket{\psi}$. 2. The verifier performs protocol 4.1 to
obtain a $q$-local Hamiltonian $H_{x}$ up to $\eta$ bits of precision. 3. The
verifier performs the reduction of Lemma 5.1 to obtain the Hamiltonian
$\hat{H}_{x}$. 4. The verifier uses weak error reduction (Lemma 3.1) for
$\hat{H}_{x}$ and accepts if and only if the outcome is $\ket{1}$.

######  Theorem 5.2 (Adaptive versus non-adaptive).

We have that

$\displaystyle\mathsf{QPCP}[\mathcal{O}(1)]=\mathsf{QPCP}_{\textup{NA}}[\mathcal{O}(1)].$

###### Proof.

$\mathsf{QPCP}_{\textup{A}}[\mathcal{O}(1)]\supseteq\mathsf{QPCP}_{\textup{NA}}[\mathcal{O}(1)]$
is trivial. To show that for any $q\in\mathcal{O}(1)$ we have that there
exists a $q^{\prime}\in\mathcal{O}(1)$ such that
$\mathsf{QPCP}_{\textup{A}}[q]\subseteq\mathsf{QPCP}_{\textup{NA}}[q^{\prime}]$,
we will verify the correctness of Protocol 5.2, which is a
$\mathsf{QPCP}_{\textup{NA}}$ protocol when the number of parallel repetitions
is constant. Let $A=(A_{\textup{yes}},A_{\textup{no}})$ be any promise problem
in $\mathsf{QPCP}_{\textup{A}}[q]$ and $x$ an input.

##### Correctness:

Step 2 of the protocol gives a $q$-local Hamiltonian
$\tilde{H}_{x}=\sum_{i\in[m]}\tilde{H}_{i}$ such that

  * •

$x\in
A_{\textup{yes}}\implies\lambda_{\textup{min}}(\tilde{H}_{x})\leq\frac{1}{3}+\epsilon$,

  * •

$x\in
A_{\textup{no}}\implies\lambda_{\textup{min}}(\tilde{H}_{x})\geq\frac{2}{3}-\epsilon$

with probability $(1-\delta)$. Performing the transformation of Lemma 5.1 to
obtain $\hat{H}$, we have

  * •

$x\in
A_{\textup{yes}}\implies\lambda_{\textup{min}}(\tilde{H}_{x})\leq\frac{\frac{1}{3}+\epsilon}{W}$,

  * •

$x\in
A_{\textup{no}}\implies\lambda_{\textup{min}}(\tilde{H}_{x})\geq\frac{\frac{2}{3}-\epsilon}{W}$,

for some $W\in[\frac{2}{3},2^{q}]$. Kitaev’s energy estimation protocol
(Protocol 4.3) for this Hamiltonian is in fact a
$\mathsf{QPCP}_{\text{NA}}$-protocol with a promise gap of at least

$\displaystyle\gamma:=\frac{\frac{1}{3}-2\epsilon}{2^{q}}\in\Theta(1).$

By applying weak error reduction (Lemma 3.1) we can ensure that conditioning
on the reduction succeeding that the acceptance (resp. rejectance) probability
is $\geq\sqrt{2/3}$ (resp. $\geq\sqrt{2/3}$). We have that the overall
acceptance and rejectance probabilities are then both $\geq 2/3$, since the
reduction succeeds with probability $\geq\sqrt{2/3}$ as well. ∎

We conclude this subsection with the following observation.

######  Remark 4.

An mentioned before, instead of Lemma 5.1 we could have also used Lemma 4.5.
This has worse parameters, but shows that it suffices to use the uniformly
random distribution to decide which proof qubits should be accessed, since we
can use Kitaev’s energy estimation protocol with all $p_{i}=1/m$ for all
$i\in[m]$ with $m$ the number of terms. Since we still need to use weak error
reduction (Lemma 3.1) to boost the completeness and soundness parameters back
to their original values, this will result in a uniform distribution over a
subset of all possible index combinations, since the parallel repetition only
allows for choices that use each supposed copy only once. This answers an open
question by [AALV09] and shows that the definition of a quantum PCP as given
in [Gri18] is in fact fully general.

###  5.3 A quantum PCP for $\mathsf{QMA}(2)$ implies
$\mathsf{QMA}(2)=\mathsf{QMA}$

In this section we prove Theorem 5.3. The proof of this result is based on the
results by [CS12] where it is proven that the $2$-separable local Hamiltonian
problem is in $\mathsf{QMA}$. Since we need a slight generalisation of their
result (namely from $2$-separable to $k$-separable), we include a full proof
for completeness. We start by recalling the definition of the consistency of
local density matrices problem [Liu06].

######  Definition 5.1 (Consistency of local density matrices (CDLM) [Liu06]).

We are given a collection of local density matrices $\\{\rho_{i}\\}_{i\in[m]}$
on $n$ qubits, where each $\rho_{i}$ is a density matrix over qubits
$C_{i}\subset[n]$, and $|C_{i}|\leq k$ for some constant $k$. Each matrix
entry is specified by $\mathrm{poly}(n)$ bits of precision. In addition, we
are given two real numbers $\beta,\alpha$ specified with $\mathrm{poly}(n)$
bits of precision. The problem is to distinguish between the following cases:

  1. 1.

There exists an $n$-qubit mixed state $\sigma$ such that for all $i\in[m]$ we
have $\norm{\tr_{\bar{C}_{i}}[\sigma]-\rho_{i}}\leq\alpha$.

  2. 2.

For all $n$-qubit mixed states $\sigma$ there exists an $i\in[m]$ such that
$\norm{\tr_{\bar{C}_{i}}[\sigma]-\rho_{i}}\geq\beta$.

Liu showed that CDLM is in $\mathsf{QMA}$ for
$\beta/4^{k}=:\epsilon=\Omega(1/\mathrm{poly}(n))$ and $\alpha=0$. Broadbent
and Grilo [BG22] provided a proof for arbitrary $\alpha$ (and
$\epsilon=\beta-\alpha$), but their proof contains a small error.666The proof
relies on Hoeffding’s inequality to show soundness. However, the random
variables it is used on are generally not independent in this setting, since
the proof can be highly entangled.  Liu’s proof can easily be modified to also
incorporate the case for general $\alpha$. We provide a proof here for
completeness.

######  Definition 5.2 ($\mathsf{QMA}+$ [AR03]).

Let $n\in\mathbb{N}$ be the input size. A super-verifier is a classical
polynomial-time randomized algorithm that given an input $\in\\{0,1\\}^{*}x$,
$|x|=n$, outputs a description of a quantum circuit $V$ and two numbers
$r,s\in[0,1]$. A promise problem $A=(A_{\textup{yes}},A_{\textup{no}})$ is in
$\mathsf{QMA}+$ if there exists a super-verifier and polynomials
$p_{1},p_{2},p_{3}$ such that

  * •

$x\in A_{\textup{yes}}$, there exists a $p_{1}(n)$-qubit quantum state $\rho$
such that

$\displaystyle\mathbb{P}_{V,r,s}[|\text{Tr}[\Pi_{1}V\rho\otimes\ket{0\dots
0}\bra{0\dots 0}V^{\dagger}]-r|\leq s]=1.$ (8)

  * •

$x\in A_{\textup{no}}$, then for all $p_{1}(n)$-qubit quantum states $\rho$ we
have

$\displaystyle\mathbb{P}_{V,r,s}[|\text{Tr}[\Pi_{1}V\rho\otimes\ket{0\dots
0}\bra{0\dots 0}V^{\dagger}]-r|\leq s+1/p_{3}(n)]=1-1/p_{2}(1/n).$ (9)

######  Lemma 5.2.

$\textup{CDLM}(\alpha,\beta)$ is in $\mathsf{QMA}$ for any
$\beta/4^{k}-\alpha=:\epsilon=\Omega(1/\mathrm{poly}(n))$.

###### Proof.

This follows the proof of [Liu06], but with arbitrary $\alpha$ (instead of
$\alpha=0$, as is the case in [Liu06]). Consider the following $\mathsf{QMA}+$
(see Definition 5.2) verifier for the CDLM problem:

  1. 1.

Pick a $i\in[m]$ uniformly at random. Choose a Pauli word
$P\in\mathcal{P}_{|C_{i}|}$ uniformly at random. Set
$r=\frac{1}{2}+\frac{1}{2}\text{Tr}[P\rho_{i}]$.

  2. 2.

Output a quantum circuit $V$ which acts on $\xi$ and a fresh ancilla
initialised in $\ket{0}$ in the following: measure the observable
$P_{C_{i}}\otimes I_{\bar{C}_{i}}$ on the state $\xi$, and set its first qubit
in $\ket{1}$ if the measurement outcome is $+1$. If the outcome ie $-1$, do
nothing to the first qubit.

We will now show that this protocol satisfies soundness and completeness, from
which the containment in $\mathsf{QMA}$ directly follows from
$\mathsf{QMA}+=\mathsf{QMA}$ [AR03].

Completeness: We have that for all $i\in[m]$ that

$\displaystyle\text{Tr}\big{[}\Pi_{1}V\rho\otimes\ket{0}\bra{0}V^{\dagger}\big{]}=\text{Tr}\big{[}(P_{C_{i}}\otimes
I_{\bar{C}_{i}})\xi\big{]}.$

Since $\norm{\text{Tr}_{\bar{C}_{i}}[\xi]-\rho_{i}}_{1}\leq\alpha$ for all
$i\in[m]$, we must have (from the definition of $r$ above) that

$\displaystyle\absolutevalue{\text{Tr}[(P_{C_{i}}\otimes
I_{\bar{C}_{i}})\xi]-r}\leq\alpha.$

Therefore,

$\displaystyle\mathbb{P}_{V,r,s}[|\text{Tr}[\Pi_{1}V\rho\otimes\ket{0}\bra{0}V^{\dagger}]-r|\leq\alpha]=1,$
(10)

satisfying the completeness constraint for $\mathsf{QMA}+$.

Soundness: We can write any $2^{k}\crossproduct 2^{k}$ Hermitian matrix $H$ in
the Pauli basis as $H=2^{-k}\sum_{P\in\mathcal{P}_{k}}\text{Tr}[HP]P$.
Therefore,

$\displaystyle\text{Tr}_{\bar{C}_{i}}[\xi]-\rho_{i}=\frac{1}{2^{|C_{i}|}}\sum_{P\in\mathcal{P}_{|C_{i}|}}\gamma_{P}P,$

where

$\displaystyle\gamma_{P}=\text{Tr}[(P_{C_{i}}\otimes
I_{\bar{C}_{i}})\xi]-\text{Tr}[P\rho_{i}].$

By the promise, there must exist an $i\in[m]$ such that

$\displaystyle\beta\leq\norm{\text{Tr}_{\bar{C}_{i}}[\xi]-\rho_{i}}_{1}\leq\sum_{P\in\mathcal{P}_{|C_{i}|}}|\gamma_{P}|,$

using the triangle inequality and $\norm{P}_{1}=2^{|C_{i}|}$. Since
$|\mathcal{P}_{k}|=4^{k}$ there must exist a choice of $C_{i}$ and $P$ such
that $\gamma_{P}\geq\beta/4^{|C_{i}|}$. Consequently,

$\displaystyle\mathbb{P}_{V,r,s}[|\text{Tr}[\Pi_{1}V\rho\otimes\ket{0}\bra{0}V^{\dagger}]-r|\geq\beta/4^{|C_{i}|}]\geq\frac{1}{4^{k}m},$
(11)

implying

$\displaystyle\mathbb{P}_{V,r,s}[|\text{Tr}[\Pi_{1}V\rho\otimes\ket{0}\bra{0}V^{\dagger}]-r|\leq\alpha+\epsilon]\leq
1-\frac{1}{4^{k}m}.$ (12)

∎

We will also need the following simple property of $\mathsf{QMA}$, which shows
that one can compute the AND-function of multiple promise problems in
$\mathsf{QMA}$ with a single $\mathsf{QMA}$-verifier.

######  Lemma 5.3.

Let $A_{1},A_{2},\dots,A_{l}$ be promise problems in $\mathsf{QMA}$, with
respective inputs $x_{1},x_{2},\dots,x_{l}$. Then for all polynomials $p(n)$
we have that there exists a uniform family of quantum circuits $\\{U_{n}\\}$
such that

  1. (i)

If for all $i\in[l]$ $x_{i}\in A_{i,\text{yes}}$, then there exists a proof
$\ket{\psi}$ such that $\mathbb{P}[U_{n}\text{ accepts }\ket{\psi}]\geq
1-2^{-p(n)}$.

  2. (ii)

If there exists an $i\in[l]$ such that $x_{i}\in A_{1,\text{no}}$, then for
all quantum proofs $\ket{\psi}$ we have $\mathbb{P}[U_{n}\text{ accepts
}\ket{\psi}]\leq 2^{-p(n)}$.

###### Proof.

Since $A_{i}\in\mathsf{QMA}$ for all $i\in[l]$, then for $A_{i}$ we have that
for every polynomial $p_{2}(n)$ there exists a uniform family of quantum
circuits $\\{U_{n}^{i}$ such that

  1. 1.

If $x_{i}\in A_{i,\text{yes}}$, then there exists a proof $\ket{\psi}$ such
that $\mathbb{P}[U_{n}^{i}\text{ accepts }\ket{\psi_{i}}]\geq
1-2^{-p_{2}(n)}$.

  2. 2.

If $x_{i}\in A_{i,\text{no}}$, then for all quantum proofs $\ket{\psi}$ we
have $\mathbb{P}[U_{n}^{i}\text{ accepts }\ket{\psi_{i}}]\leq 2^{-p_{2}(n)}$,

by standard error reduction for $\mathsf{QMA}$. The verifier $U_{n}$ will now
do the following: it expects a quantum proof
$\otimes_{i\in[l]}\ket{\psi_{i}}$, runs all $U_{n}^{i}$ in parallel, measures
all $l$ designated output qubits in the computational basis and accepts only
if and only if all measurement outcomes are $\ket{1}$. Case (i) follows
immediately since there exists a state $\otimes_{i\in[l]}\ket{\psi_{i}}$ such
that

$\displaystyle\mathbb{P}[U_{n}\text{ accepts
}\otimes_{i\in[l]}\ket{\psi_{i}}]\geq(1-2^{p_{2}(n)})^{l}\geq 1-2^{-p(n)}$

when $p_{2}(n)\geq p(n)+\log_{2}(l)$ (this follows from the union bound). For
case (ii), we have to argue that it does not help the prover to provide a
highly entangled state to cheat, which can be done in the same way as one
could do to show that $\mathsf{QMA}$ allows for weak error reduction. Let
$i^{*}$ be the $i$ such that for all quantum proofs $\ket{\psi}$ we have that
$U_{n}^{i}$ rejects with probability $\leq 2^{-p_{2}(n)}$. For all $i<i*$ we
have already executed the protocol, and suppose that they all accepted (if
they reject we are done), and that the resulting density of the proof is
$\xi$. By a convexity argument, we have that acceptance probability of all
mixed states is also upper bounded by $2^{-p_{2}(n)}$. Hence, independent of
all the previous outcomes, we have that at step $i^{*}$ the probability that
$U_{n}^{i}$ accepts is $\leq 2^{-p_{2}(n)}$. Since we set $p_{2}(n)\geq p(n)$
in the previous step, case (ii) follows. ∎

Next we show that the $k$-separable $q$-local Hamiltonian problem (Definition
2.2) is in $\mathsf{QMA}$. This relies directly on the $\mathsf{QMA}$
containment of the CDLM problem. We first state a $\mathsf{QMA}$ protocol.

Protocol 5: $\mathsf{QMA}$ protocol for the $k$-separable $q$-local
Hamiltonian problem Input: $m$ $q$-local terms $\\{H_{i}\\}$, completeness and
soundness parameters $b,a$.
Set $a^{\prime}:=a+(b-a)/4$, $b^{\prime}:=b-(b-a)/4$,
$\beta:=\frac{b-a}{2qm}$, $\alpha=\beta/8^{q}$. 1. The prover sends a quantum
witness $\gamma$ and classical witness $\\{\rho_{i}^{j}\\}$ (the verifier can
enforce this by measuring the classical part in the computational basis). 2.
The verifier performs the following three checks: • Check 1: the verifier
checks if all reduced density matrices are indeed PSD and have trace one. •
Check 2: the verifier checks if $\text{Tr}[H\otimes_{j\in[k]}\rho_{j}^{i}]\leq
a^{\prime}$. • Check 3: the verifier runs $k$ parallel
$\textup{CDLM}(\alpha,\beta)$ instances for all $j\in[k]$ up to precision
$\epsilon$ using the single proof $\gamma$. 3. The verifier accepts if and
only if all the above checks are passed.

######  Lemma 5.4.

The $k$-separable $q$-local Hamiltonian problem is in $\mathsf{QMA}$ for any
$b-a\geq 1/\mathrm{poly}(n)$.

###### Proof.

This follows the same ideas as in [CS12], but now for a $k$\- instead of
$2$-separable state.

##### Completeness:

By the promise, there exists a state $\xi=\otimes_{j\in[k]}\xi_{j}$ such that
$\tr[H\xi]\leq a$. The prover sends density matrix descriptions
$\\{\tilde{\xi}_{i}^{j}\\}$ of the reduced density matrices $\xi_{i}^{j}$ up
to precision (in terms of trace distance) $\epsilon=2^{-p(n)}$ for some large
polynomial $p(n)$ such that the second check and fourth check are satisfied
(see below), which is possible when the entries of the density matrices are
specified with a polynomial number of bits. The first check of Protocol 5.3 is
passed. For the second check, we have that

$\displaystyle\sum_{i\in[m]}\tr[H_{i}\otimes_{j\in[k]}\tilde{\xi}_{i}^{j}]\leq
a+mk\epsilon\leq a^{\prime},$

when $\epsilon$ is small enough. For the final check the verifier uses the
witness $\xi$, and by Lemma 5.3 this check can also be made to succeed with
probability $\geq 2/3$. Hence, the overall acceptance probability is $\geq
2/3$.

##### Soundness:

If checks $1$ or $2$ fail we are done. If check $1$ succeeds we can be certain
that every matrix $\rho_{i}^{j}$ is a density matrix up to an exponentially
small correction. If check $2$ succeeds we must have that

$\displaystyle\sum_{i\in[m]}\tr[H_{i}\otimes_{j\in[k]}\rho_{i}^{j}]\leq
a^{\prime}.$

However, according to the promise, we have that for any state
$\xi=\otimes_{j\in[k]}\xi^{j}$

$\displaystyle\sum_{i\in[m]}\tr[H_{i}\otimes_{j\in[k]}\xi_{i}^{j}]\geq
b^{\prime}.$

This means that for our choice of $a^{\prime}$, $b^{\prime}$ we have

$\displaystyle\frac{b-a}{2}$
$\displaystyle\leq\sum_{i\in[m]}\left(\tr[H_{i}\otimes_{j\in[k]}\xi_{i}^{j}]-\tr[H_{i}\otimes_{j\in[k]}\rho_{i}^{j}]\right)$
$\displaystyle=\sum_{i\in[m]}\tr[H_{i}(\otimes_{j\in[k]}\xi_{i}^{j}]-\otimes_{j\in[k]}\rho_{i}^{j})]$
$\displaystyle\leq\sum_{i\in[m]}\norm{\otimes_{j\in[k]}\xi_{i}^{j}]-\otimes_{j\in[k]}\rho_{i}^{j}}_{1}$

which implies that there must exist an $i$ such that
$\norm{\otimes_{j\in[k]}\xi_{i}]-\otimes_{j\in[k]}\rho_{i}^{j}}_{1}\geq\frac{b-a}{2m}$.
In the worst case, we have that this density matrix lives on $q$ separate
density matrices. However, by the subadditivity property of the trace distance
with respect to tensor products we have that

$\displaystyle\norm{\otimes_{j\in[q]}\xi_{i}^{j}-\otimes_{j\in[q]}\rho_{i}^{j}}\leq\sum_{j\in[q]}\norm{\xi_{i}^{j}-\rho_{i}^{j}},$

which implies that there must exist a $i,j$ such that
$\norm{\xi_{i}^{j}-\rho_{i}^{j}}_{1}\geq\frac{b-a}{2qm}=\beta$. Again by Lemma
5.3, running all $k$ instances of $\textup{CDLM}(\alpha,\beta)$ in parallel
can achieve a probability of success $\geq 2/3$ for detecting a single no-
instance. Hence, we have that overall acceptance probability $\leq 1/3$. ∎

Finally, we arrive at the main result for this section. We will prove it by
arguing that $\mathsf{QPCP}{[k,q]}$ is contained in $\mathsf{QMA}$ for any
$k=\mathrm{poly}(n)$.

Protocol 6: $\mathsf{QMA}$ protocol for $\mathsf{QPCP}{[k,q]}$ Input: An
quantum PCP verifier $V$, input $x$.
Set $\epsilon:=(c-s)/4$, $\eta:=\lceil
q\log_{2}\left(\frac{4\Gamma(\Gamma+1)}{\epsilon}-1\right)\rceil$. 1. The
prover sends the witness $\xi$. 2. Using the reduction of Protocol 4.1, the
verifier learns a Hamiltonian $H$ up to $\eta$ bits of precision. 3. The
verifier runs Protocol 5.3 with $a=c+\epsilon$ and $b=c-\epsilon$, and accepts
if and only if Protocol 5.3 accepts.

######  Theorem 5.3 (PCPs for $\mathsf{QMA}{[k]}$).

If $\mathsf{QMA}{[k]}$ admits a $q$-query quantum PCP for
$q\in\mathcal{O}(1)$, then $\mathsf{QMA}{[2]}=\mathsf{QMA}$.

###### Proof.

$A=(A_{\textup{yes}},A_{\textup{no}})$ be any problem in $\mathsf{QPCP}[k,q]$
with a verifier $V$ and $x$ some input. We have if reduction of step $2$
succeeds with probability $1-\delta^{\prime}\geq\sqrt{2/3}$ and step $3$ also
with probability $1-\delta\geq\sqrt{2/3}$, then we have

  * •

$x\in A_{\textup{yes}}\implies\mathbb{P}[\text{protocol~{}\ref{prot:QMA2}
accepts}]\geq 2/3$,

  * •

$x\in A_{\textup{no}}\implies\mathbb{P}[\text{protocol~{}\ref{prot:QMA2}
accepts}]\leq 1/3$,

which puts the problem in $\mathsf{QMA}$ (and hence
$\mathsf{QPCP}[k,q]\subseteq\mathsf{QMA}$). Since
$\mathsf{QMA}(k)=\mathsf{QMA}(2)$ by [HM13], the result follows by the
assumption that there exists a $k\leq\mathrm{poly}(n)$ such that
$\mathsf{QMA}(k)\subseteq\mathsf{QPCP}[k,q]$ for some $q\in\mathcal{O}(1)$. ∎

##  6 Proofs of quantum PCP theorems do not (quantumly) relativise

###  6.1 Quantum proof discretisation

We start by recalling the definition of $h$-nets on pure states.

######  Definition 6.1 ($h$-net).

Let $\mathcal{H}$ be a $d$-dimensional Hilbert space. We say a set
$P^{d}_{\epsilon}=\\{\ket{\psi_{i}}\\}\subseteq\mathcal{P}(\mathcal{H})$ forms
an $h$-net for $\mathcal{P}(\mathcal{H})$ if for all
$\ket{\phi}\in\mathcal{P}(\mathcal{H})$ there exists a $\ket{\psi_{i}}\in
P^{d}_{h}$ such that $\absolutevalue{\bra{\phi}\ket{\psi_{i}}}\geq h$.

It is known that for all $h$ there exists such a $h$-net of size that scales
roughly exponentially in the dimension, as illustrated by the following lemma.

######  Lemma 6.1 ([BW03]).

Let $\mathcal{H}$ be a $d$-dimensional Hilbert space. For all $0<h<1$, there
exists a $h$-net $P^{d}_{h}$ for $\mathcal{P}(\mathcal{H})$ of size smaller
than

$\displaystyle
C^{\prime}\left(\frac{d^{3/2}\log(2+dh^{2})}{(1-h^{2})^{d}}\right),$

for some universal constant $C^{\prime}>0$.

To the best of our knowledge, no explicit construction has yet been found that
achieves this scaling in $d$.

We give an analogous definition of $h$-nets for mixed states with respect to
trace distance, which we call $\epsilon$-covering sets of density matrices.

######  Definition 6.2 ($\epsilon$-covering set of density matrices).

Let $\mathcal{H}$ be some $d$-dimensional Hilbert space. We say a set of
density matrices
$D^{d}_{\epsilon}=\\{\rho_{i}\\}\subseteq\mathcal{D}(\mathcal{H})$ is
$\epsilon$-covering for $\mathcal{D}(\mathcal{H})$ if for all
$\sigma\in\mathcal{D}(\mathcal{H})$ there exists a $\rho\in D^{d}_{\epsilon}$
such that $\frac{1}{2}\norm{\rho-\sigma}_{1}\leq\epsilon$.

It is easy to show that the existence of an $h$-net implies the existence of a
$\epsilon$-covering set of density matrices with $\epsilon=\sqrt{1-h^{2}}$.

######  Proposition 6.1.

For all $0<\epsilon<1$, there exists a $\epsilon$-covering set of density
matrices $D_{\epsilon}^{d}$ of size smaller than

$\displaystyle C\left(\frac{1}{\epsilon}\right)^{5d},$

for some universal constant $C>0$.

###### Proof.

One can view the $h$-net $P_{\epsilon}^{2d}$ of Lemma 6.1 on a
$2d$-dimensional Hilbert space
$\mathcal{H}=\mathcal{H}_{A}\otimes\mathcal{H}_{B}$, both of equal dimension
$d$, as containing purifications of density matrices from the set
$D_{\epsilon}^{d}\subseteq\mathcal{D}(\mathcal{H}_{A})$. Let $\rho$ be some
arbitrary mixed state in $\mathcal{D}(\mathcal{H})$ and let
$\ket{\psi}\in\mathcal{P}(\mathcal{H}\otimes\mathcal{H})$ be a purification of
$\rho$. Then there must exists a state $\ket{\phi}\in P_{\epsilon}^{2d}$, with
reduced density matrix $\sigma$, such that

$\displaystyle\absolutevalue{\bra{\phi}\ket{\psi}}\geq h\iff
1-\absolutevalue{\bra{\phi}\ket{\psi}}^{2}\leq 1-h^{2},$

which means that setting $h:=\sqrt{1-\epsilon^{2}}$ should have that

$\displaystyle\epsilon\geq\sqrt{1-|\bra{\phi}\ket{\psi}|^{2}}=\frac{1}{2}\norm{\ket{\psi}\bra{\psi}-\ket{\phi}\bra{\phi}}_{1}\geq\frac{1}{2}\norm{\rho-\sigma}_{1},$

since the trace distance can only decrease under partial trace. Hence, setting

$\displaystyle{D_{\epsilon}^{d}:=\\{\tr_{\textup{B}}[\ket{\phi}\bra{\phi}]\text{
$:$ }\ket{\phi}\in P_{\epsilon}^{2d}\\}}$

satisfies conditions of Definition 6.2. We can now upper bound the cardinality
of $D_{\epsilon}^{d}$ using Lemma 6.1 as

$\displaystyle|D^{d}_{\epsilon}|$ $\displaystyle\leq
C^{\prime}\left(\frac{(2d)^{3/2}\log(2+2d(1-\epsilon^{2})))}{(\epsilon^{2})^{2d}}\right)$
$\displaystyle\leq C\left(\frac{1}{\epsilon}\right)^{5d}$

for some universal constant $C>0$. ∎

Let us now formally define the proof-discretised version of $\mathsf{QPCP}$,
denoted as $\mathsf{QPCP}_{\epsilon}$. We will use a non-adaptive formulation
of the quantum PCP, since our proof of
$\mathsf{QPCP}_{\textup{A}}[\mathcal{O}(1)]=\mathsf{QPCP}_{\textup{NA}}[\mathcal{O}(1)]$
in Theorem 5.2 relativises.

######  Definition 6.3 (Proof-discretised $\mathsf{QPCP}$).

Let $q\in\mathbb{N}$, $\epsilon\in[0,1]$ be some constant, and let
$\mathcal{H}=\mathbb{C}^{2^{k}}$. Let $D^{2^{k}}_{\epsilon}$ be a
$\epsilon$-covering density matrix set as in Proposition 6.1. Then we define
$\mathsf{QPCP}_{k,\epsilon}[q,c,s]$ as the complexity class which is just as
$\mathsf{QPCP}[k,q,c,s]$, but where the reduced density matrix
$\rho\in\mathcal{D}(\mathcal{H})$ obtained from the proof is projected (and
subsequently re-normalised) on the density matrix $\rho^{\prime}\in
D^{2^{q}}_{\epsilon}$ closest to $\rho$ in trace distance. If $c=2/3$ and
$s=1/3$, we simply write $\mathsf{QPCP}_{\epsilon}[q]$.

Whilst $\mathsf{QPCP}_{\epsilon}$ is a highly artificial class, it will be
helpful for us to prove some results since we can now use counting arguments
on the exact size of the proof space that Merlin sees. However, note that the
definition of this does _not_ put any limitations on the proofs that Merlin
can send, as the projection on a state from the set $D_{\epsilon}^{2^{k}}$
(and following re-normalisation) happens only after the proof has been
received by the verifier. Therefore, the verifier has the guarantee that
Merlin sends a valid quantum state, circumventing the problem of checking the
consistency of the local density matrices with a global quantum state (which
is QMA-hard by the results of [Liu06, BG22]).

Let us now justify that, with respect to all (quantum) oracles, we have that
putting this extra restriction does not limit the power of
$\mathsf{QPCP}_{\epsilon}$ as long as the $\epsilon$-covering set is large
enough.

######  Lemma 6.2.

Let $q\in\mathbb{N}$, $\epsilon\in(0,1/6)$ constant and let
$\mathcal{H}=\mathbb{C}^{2^{k}}$. Let $D^{k^{\prime}}_{\epsilon}$ be a
$\epsilon$-covering density matrix set as in Proposition 6.1. We have that for
all quantum oracles $U$ that

$\mathsf{QPCP}^{U}[k,q]\subseteq\mathsf{QPCP}^{U}_{\epsilon}[k,q,2/3-\epsilon,1/3+\epsilon],$

###### Proof.

Since the proof of
$\mathsf{QPCP}_{\textup{N}}[\mathcal{O}(1)]=\mathsf{QPCP}_{\textup{NA}}\mathcal{O}(1)$
relativises (Theorem 5.2), our assumptions that the PCP is non-adaptive is
w.l.o.g. even in a relativised setting. Let $V_{x}^{U}$ be a
$\mathsf{QPCP}_{\textup{NA}}^{U}$ verification circuit as in Definition 3.1
(but with the input $x$ hardcoded into it) that uses $q(n)$ ancilla qubits and
has access to the quantum oracle $U$, and $x\in\\{0,1\\}^{n}$. We define

$\displaystyle
p_{x}(i_{1},\dots,i_{q}):=\norm{\Pi_{i_{1},\dots,i_{q}}V_{x,0}^{U}\ket{x}\ket{0}^{\otimes
q(n)}}^{2}.$

Let $\xi_{i_{1},\dots,i_{q}}=\tr_{C_{i_{1},\dots,i_{q}}}[\xi]$ and
$\hat{\xi}_{i_{1},\dots,i_{q}}$ be the reduced density matrix that is accessed
by $\mathsf{QPCP}^{U}_{\epsilon}$ instead. Next, define
$\sigma_{i_{1},\dots,i_{q}}=\xi_{i_{1},\dots,i_{q}}\otimes\rho_{i_{1},\dots,i_{q}}$
where $\rho_{i_{1},\dots,i_{q}}$ is the $q(n)+n$-qubit post-measurement state
after the measurement outcome to decide the indices of the proof to be queried
returned $i_{1},\dots,i_{q}$. In similar fashion, define
$\tilde{\sigma}_{i_{1},\dots,i_{q}}$ using $\hat{\xi}_{i_{1},\dots,i_{q}}$. We
have

$\displaystyle\absolutevalue{\mathbb{P}[V_{x}^{U}\text{accepts
}\xi]-\mathbb{P}[\hat{V}_{x}^{U}\text{accepts }\xi]}$
$\displaystyle=\sum_{i_{1},\dots,i_{q}\in\Omega}p_{x}(i_{1},\dots,i_{q})\left(\tr[\Pi^{1}_{\text{output}}V_{x,1}^{U\dagger}(\sigma{i_{1},\dots,i_{q}}-\hat{\sigma}_{i_{1},\dots,i_{q}})V_{x,1}^{U}\Pi^{1}_{\text{output}}]\right)$
$\displaystyle=\sum_{i_{1},\dots,i_{q}\in\Omega}p_{x}(i_{1},\dots,i_{q})\left(\tr[V_{x,1}^{U}\Pi^{1}_{\text{output}}V_{x,1}^{U\dagger}(\sigma_{i_{1},\dots,i_{q}}-\hat{\sigma}_{i_{1},\dots,i_{q}})]\right)$
$\displaystyle\leq\sum_{i_{1},\dots,i_{q}\in\Omega}p_{x}(i_{1},\dots,i_{q})\norm{\sigma_{i_{1},\dots,i_{q}}-\hat{\sigma}_{i_{1},\dots,i_{q}}}_{1}$
$\displaystyle=\sum_{i_{1},\dots,i_{q}\in\Omega}p_{x}(i_{1},\dots,i_{q})\norm{\xi_{i_{1},\dots,i_{q}}-\hat{\xi}_{i_{1},\dots,i_{q}}}_{1}$
$\displaystyle\leq\epsilon,$

where we used the cyclic property of the trace in going from line 1 to line 2
and that the trace distance is preserved under tensor products (with the same
state) in going from line 3 to line 4. ∎

###  6.2 Oracle separations

We will now follow the proof of the oracle separation in [AK07] to show that
the same oracle $U$ that shows $\mathsf{QCMA}^{U}\neq\mathsf{QMA}^{U}$ also
shows that $\mathsf{QPCP}[\mathcal{O}(1)]^{U}\neq\mathsf{QMA}^{U}$. We will
omit most of the details, focusing on the parts where we depart from [AK07].

Let $\mu$ be the uniform probability measure over $\mathcal{P}(\mathcal{H})$.
We will need the notion of $p$-uniform probability measures, which have the
following definition.

######  Definition 6.4 ($p$-uniform probability measures).

For all $p\in[0,1]$, a probability measure $\sigma$ over
$\mathcal{P}(\mathcal{H})$ is called $p$-uniform if $p\sigma\leq\mu$.
Equivalently, $\sigma$ is $p$-uniform if it can be obtained by starting from
$\mu$, and then conditioning on an event that occurs with probability at least
$p$.

We also state the following lemma from [AK07].

######  Lemma 6.3 (Expected fidelity $p$-uniform random states [AK07]).

Let $\mathcal{H}$ be a $d$-dimensional Hilbert space and let $\sigma$ be a
$p$-uniform probability measure over $\mathcal{P}(\mathcal{H})$. Then for all
mixed states $\rho$, we have that

$\displaystyle\mathbb{E}_{\ket{\Psi}\in\sigma}\bra{\Psi}\rho\ket{\Psi}=\mathcal{O}\left(\frac{1+\log
1/p}{d}\right).$

The key idea behind the oracle separation in [AK07] is to provide a lower
bound on a decision version of ‘quantum search’, where one is given a black-
box unitary which either marks a single $n$-qubit quantum state or applies the
identity operation. This is reminiscent of the lower bound on search by using
the OR-function, where one is given a black-box Boolean function which ‘marks’
a single bit string (i.e. $f(x)=1$ for a single $x$) or for all bit strings
outputs $0$ ($f(x)$ for all $x$). By exploiting the fact that there are a
doubly exponential number of quantum states that have small pairwise overlap,
[AK07] can show that a polynomial number of classical bits to point you
towards the right quantum state does not help much, and still requires one to
make an exponential number of queries to the oracle.

######  Lemma 6.4.

Let $q\in\mathbb{N}$ and let $D_{\epsilon}^{2^{q}}$ be a $\epsilon$-covering
set of mixed states on $q$ qubits as per Proposition 6.1. Suppose we are given
oracle access to an $n$-qubit unitary $U$, and want to decide which of the
following holds:

  1. (i)

There exists an $n$-qubit ‘quantum marked state’ $\ket{\Psi}$ such that
$U\ket{\Psi}=-\ket{\Psi}$, but $U\ket{\phi}=\ket{\phi}$ whenever
$\bra{\phi}\ket{\Psi}=0$; or

  2. (ii)

$U=I$ is the identity operator.

Then even if we have a witness tuple $(i_{1},\dots,i_{q},\rho)$, where
$i_{i_{1}},\dots,i_{i_{q}}$ is a set of the $q$ indices and a quantum witness
$\rho\in D_{\epsilon}^{k}$ in support of case (i), we still need

$\displaystyle\Omega\left(\sqrt{\frac{2^{n}}{5\cdot
2^{q}\log(\frac{1}{\epsilon})+q\cdot\mathrm{polylog}(n,q)+C}}\right).$

queries to verify the witness, with a bounded probability of error. Here $C>0$
is some universal constant.

###### Proof.

This follows the same structure as Theorem 3.3 in [AK07], but considers
$q$-qubit proofs from $D_{\epsilon}^{2^{q}}$ instead of classical proofs. Let
$\mathcal{H}$ be a $2^{n}$-dimensional Hilbert space. Let $A$ be a quantum
algorithm that queries the oracle $U$ a total of $T$ times, with the goal to
output $1$ in case (i) and output 0 in case (ii). For each $n$-qubit state
$\ket{\Psi}$, we fix both the indices $(i_{1},\dots,i_{q}),i_{j}\in[p(n)]$ for
all $j\in[q]$ _and_ corresponding quantum witness $\rho\in D_{\epsilon}^{k}$
that maximises the probability that $A$ accepts. Let
$S(i_{1},\dots,i_{q},\rho)$ be the set of $\ket{\Psi}$’s that belong to the
index/state tuple $(i_{1},\dots,i_{q},\rho)$. Then we have that the
$S(i_{1},\dots,i_{q},\rho)$’s form a partition of $\mathcal{P}(\mathcal{H})$,
and hence we must have that there exists a
$(i_{1}^{*},\dots,i_{q}^{*},\rho^{*})$ such that

$\displaystyle\text{Pr}_{\ket{\Psi}\in\mu}\left[\ket{\Psi}\in
S(i_{1}^{*},\dots,i_{q}^{*},\rho^{*})\right]$
$\displaystyle\geq\left(\binom{p(n)}{q}C\left(\frac{1}{\epsilon}\right)^{5\cdot
2^{q}}\right)^{-1}$
$\displaystyle\geq\left(\left(\frac{ep(n)}{q}\right)^{q}C\left(\frac{1}{\epsilon}\right)^{5\cdot
2^{q}}\right)^{-1}=:p$

Since $\rho$ is a $q$-qubit quantum state, there exists a unitary $U$ of
circuit depth $\mathcal{O}(4^{q}\mathrm{poly}(n))$ such that
$U\ket{0}^{\otimes 2q}=\ket{\phi}$ and
$\norm{\tr_{B}[\ket{\phi}\bra{\phi}]-\rho}_{1}\leq 1/\exp(n)$ (by the Solovay-
Kitaev Theorem). We hardcode $U$ and the information $i_{q},\dots,i_{q}$ into
$A$. Now let $\sigma$ be the probability measure over $S(\rho^{*},I^{*})$.
Note that it is $p$-uniform. Following the rest of the steps of the proof in
[AK07, Theorem 3.3], this yields the desired bound of

$\displaystyle T\geq\Omega\left(\sqrt{\frac{2^{n}}{5\cdot
2^{q}\log(\frac{1}{\epsilon})+q\cdot\mathrm{polylog}(n,q)+C}}\right).$

∎

######  Theorem 6.1.

There exists a quantum oracle $U$ relative to which
$\mathsf{QCMA}^{U}\neq\mathsf{QMA}^{U}$ and
$\mathsf{QPCP}[k,q]^{U}\neq\mathsf{QMA}^{U}$, for all $q\in\mathcal{O}(\log
n)$, $1\leq k\leq\mathrm{poly}(n)$.

###### Proof.

This follows from using the same proof as [AK07], Theorem 1.1, using the lower
bound of Lemma 6.4 to show that
$\mathsf{QPCP}_{P^{k^{\prime}}_{\epsilon}}[q]^{U}\neq\mathsf{QMA}^{U}$ for all
constant $q\in\mathcal{O}(\log n)$, from which the separation
$\mathsf{QPCP}[q]^{U}\neq\mathsf{QMA}^{U}$ follows by Lemma 6.2. ∎

We remark that our proof technique should work for any oracle separation
between $\mathsf{QCMA}$ and $\mathsf{QMA}$ that uses counting arguments
exploiting the doubly exponentially large number of quantum states and the
fact that $\mathsf{QCMA}$ has only access to an exponential number of proofs.
This shows that any proof of the quantum PCP conjecture (via the proof
verification formulation) requires (as expected) quantumly non-relativising
techniques.

The previous quantum oracle separations crucially exploit the doubly
exponentially large number of quantum states that have low mutual fidelities.
However, one may wonder whether a similar idea might be used to also show that
for low-complexity states a similar separation holds? It turns out that this
is surprisingly easy, by simply using a similar oracle to the one that
separates $\mathsf{BQP}$ from $\mathsf{NP}$ [BBBV97]. Observe this oracle is
classical, and can alternatively be viewed as a state $1$-design over the set
of all quantum states used in the previous separation. We state the following
result, for which the proof is given in Appendix D.

######  Corollary 6.1.

There exists a classical oracle $\mathcal{O}$ relative to which
$\mathsf{QPCP}[k,q]^{\mathcal{O}}\neq\mathsf{QMA}^{\mathcal{O}}$ (in fact
$\neq\mathsf{NP}^{\mathcal{O}}$) for all $q\in\mathcal{O}(1)$.

Note that a much stronger statement also holds, we can even combine
$\mathsf{QCMA}$ and $\mathsf{QPCP}$ (so a classical proof and quantum proof
which can be accessed locally) and the same separation would still hold.

## 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.
  * [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.
  * [ABD+08] Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, and Peter Shor.  The power of unentanglement.  In 2008 23rd Annual IEEE Conference on Computational Complexity, pages 223--236. IEEE, 2008.
  * [ABN23] Anurag Anshu, Nikolas P Breuckmann, and Chinmay Nirkhe.  Nlts hamiltonians from good quantum codes.  In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1090--1096, 2023.
  * [AG19] Dorit Aharonov and Alex Bredariol Grilo.  Stoquastic pcp vs. randomness.  In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1000--1023. IEEE, 2019.
  * [AGK23] Eric R Anschuetz, David Gamarnik, and Bobak Kiani.  Combinatorial nlts from the overlap gap property.  arXiv preprint arXiv:2304.00643, 2023.
  * [AIK21] Scott Aaronson, DeVon Ingram, and William Kretschmer.  The acrobatics of bqp.  arXiv preprint arXiv:2111.10409, 2021.
  * [AJL06] Dorit Aharonov, Vaughan Jones, and Zeph Landau.  A polynomial quantum algorithm for approximating the jones polynomial.  In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 427--436, 2006.
  * [AK07] Scott Aaronson and Greg Kuperberg.  Quantum versus classical proofs and advice.  In Twenty-Second Annual IEEE Conference on Computational Complexity (CCC’07), pages 115--128. IEEE, 2007.
  * [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.
  * [AN02] Dorit Aharonov and Tomer Naveh.  Quantum np-a survey.  arXiv preprint quant-ph/0210077, 2002.
  * [AR03] Dorit Aharonov and Oded Regev.  A lattice problem in quantum np.  In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 210--219. IEEE, 2003.
  * [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.
  * [BBBV97] Charles H Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani.  Strengths and weaknesses of quantum computing.  SIAM journal on Computing, 26(5):1510--1523, 1997.
  * [BBT09] N. Bansal, S. Bravyi, and B.M. Terhal.  Classical approximation schemes for the ground-state energy of quantum and classical ising spin hamiltonians on planar graphs.  Quantum Information and Computation, 9(7-8):701--720, 2009.
  * [Bei10] Salman Beigi.  Np vs qmalog (2).  Quantum Information & Computation, 10(1):141--151, 2010.
  * [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.
  * [BH13] Fernando GSL Brandao and Aram W Harrow.  Product-state approximations to quantum ground states.  In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 871--880, 2013.
  * [BT09] Hugue Blier and Alain Tapp.  All languages in np have very short quantum proofs.  In 2009 Third International Conference on Quantum, Nano and Micro Technologies, pages 34--37. IEEE, 2009.
  * [BW03] Károly Böröczky and Gergely Wintsche.  Covering the sphere by equal spherical balls.  Discrete and Computational Geometry: The Goodman-Pollack Festschrift, pages 235--251, 2003.
  * [CCNN23a] Nolan J Coble, Matthew Coudron, Jon Nelson, and Seyed Sajjad Nezhadi.  Hamiltonians whose low-energy states require $\omega(n)$ t gates.  arXiv preprint arXiv:2310.01347, 2023.
  * [CCNN23b] 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 Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), volume 261 of Leibniz International Proceedings in Informatics (LIPIcs), pages 32:1--32:19, Dagstuhl, Germany, 2023. Schloss Dagstuhl -- Leibniz-Zentrum für Informatik.
  * [Coo71] Stephen A. Cook.  The complexity of theorem-proving procedures.  STOC, pages 151--158, May 1971.
  * [CS12] André Chailloux and Or Sattath.  The complexity of the separable hamiltonian problem.  In 2012 IEEE 27th Conference on Computational Complexity, pages 32--41. IEEE, 2012.
  * [Din07] Irit Dinur.  The PCP theorem by gap amplification.  Journal of the ACM, 54(3):12–es, June 2007.
  * [For94] Lance Fortnow.  The role of relativization in complexity theory.  Bulletin of the EATCS, 52:229--243, 1994.
  * [Gha23] Sevag Gharibian.  The 7 faces of quantum np.  arXiv preprint arXiv:2310.18010, 2023.
  * [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.  In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 19--32, 2022.
  * [Gri18] Alex B. Grilo.  Quantum proofs, the local Hamiltonian problem and applications.  PhD thesis, Université Sorbonne Paris Cité, April 2018.
  * [HATH23] Yaroslav Herasymenko, Anurag Anshu, Barbara Terhal, and Jonas Helsen.  Fermionic hamiltonians without trivial low-energy states.  arXiv preprint arXiv:2307.13730, 2023.
  * [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.
  * [KSV02] Alexei Y. Kitaev, Alexander Shen, and Mikhail N. Vyalyi.  Classical and quantum computation.  American Mathematical Society, 2002.
  * [LCV07] Yi-Kai Liu, Matthias Christandl, and Frank Verstraete.  Quantum computational complexity of the n-representability problem: Qma complete.  Physical review letters, 98(11):110503, 2007.
  * [Lev73] Leonid A. Levin.  Universal sequential search problems.  Problemy peredachi informatsii, 9(3):115--116, 1973.
  * [Liu06] Yi-Kai Liu.  Consistency of local density matrices is qma-complete.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006, Barcelona, Spain, August 28-30 2006. Proceedings, pages 438--449. Springer, 2006\.
  * [MW05] Chris Marriott and John Watrous.  Quantum arthur--merlin games.  computational complexity, 14:122--152, 2005.
  * [WFC23] Jordi Weggemans, Marten Folkertsma, and Chris Cade.  Guidable local hamiltonian problems with implications to heuristic ansatze state preparation and the quantum pcp conjecture.  arXiv preprint arXiv:2302.11578, 2023.

##  Appendix A Strong error reduction for non-adaptive quantum PCPs with near-
perfect completeness

In this appendix we argue that non-adaptive quantum PCPs allow for strong
error reduction, so long as they are nearly perfectly complete. We will use
the well-known gentle measurement lemma.

######  Lemma A.1 (Gentle measurement lemma).

Consider a state $\rho$ and a measurement operator $\Lambda$ where
$0\preceq\Lambda\preceq 1$. Now suppose that $\tr[\Lambda\rho]\geq
1-\epsilon$, where $0<\epsilon\leq 1$. Then the post-measurement state

$\displaystyle\rho^{\prime}=\frac{\sqrt{\Lambda}\rho\sqrt{\Lambda}}{\tr[\Lambda\rho]}$

satisfies $\norm{\rho-\rho^{\prime}}_{1}\leq 2\sqrt{\epsilon}$.

The error reduction protocol will be a variant of the parallel repetition
protocol but now we will use the _same_ quantum proof in all repetitions.

See 3.1

###### Proof.

Let $\mathcal{A}$ be a non-adaptive quantum PCP protocol consisting of
circuits $V_{0}$ and $V_{1}$, and let $\xi$ be the provided quantum proof. Let
$\rho^{0}_{i_{1},\dots,i_{q}}\ket{i_{1}}\bra{i_{1}}\dots\ket{i_{q}}\bra{i_{q}}\otimes\rho_{\text{rest}}$
be the post-measurement state after PVM $\Pi_{1}$ is performed to obtain
indices $i_{1},\dots,i_{q}$. Now let $\rho^{1}_{i_{1},\dots,i_{q}}$ be the
state after $V_{1}$ acts on
$\ket{i_{1}}\bra{i_{1}}\dots\ket{i_{q}}\bra{i_{q}}\otimes\rho_{1}$ and qubits
$i_{1},\dots,i_{q}$ of $\xi$. In the No-case, we have that the soundness
property holds with respect to all proof states. So for every reduced density
matrix $\xi^{\prime}$ after the measurement is performed, we have

$\displaystyle\mathbb{E}_{i_{1},\dots,i_{q}}\left[\tr[\Pi^{1}_{\text{output}}\rho^{0}_{i_{1},\dots,i_{q}}]\right]\leq
1/2.$

Hence, the bound follows from the same argument as in the weak error reduction
case (Lemma 3.1).

In the Yes-case, we have that $\Pi_{0}^{\text{output}}$ satisfies

$\displaystyle\mathbb{E}_{i_{1},\dots,i_{q}}\left[\tr[\Pi^{1}_{\text{output}}\rho^{0}_{i_{1},\dots,i_{q}}]\right]\geq
1-2^{-c_{0}n}$

which implies that

$\displaystyle\mathbb{P}_{i_{1},\dots,i_{q}}[\tr[\Pi^{1}_{\text{output}}\rho^{0}_{i_{1},\dots,i_{q}}]\geq
1-2^{-c_{0}n/2}]\geq 1-2^{c_{0}n/2}.$

By the Lemma A.1, we have that the post-measurement state
$\rho^{{}^{\prime}}_{i_{1},\dots,i_{q}}$ satisfies

$\displaystyle\frac{1}{2}\norm{\rho^{1}_{i_{1},\dots,i_{q}}-\rho^{{}^{\prime}}_{i_{1},\dots,i_{q}}}_{1}\leq
2^{-nc_{0}/4}.$

with probability $\geq 1-2^{c_{0}n/2}$. Hence, we can simply apply
$V_{1}^{\dagger}$ such that the density matrix $\xi^{\prime}$ in the proof
register satisfies

$\displaystyle\frac{1}{2}\norm{\xi^{\prime}-\xi}_{1}\leq 2^{-c_{0}n/4},$

using the fact that the trace distance can only decrease under the partial
trace. Therefore, our new acceptance probability satisfies

$\displaystyle\mathbb{E}_{i_{1},\dots,i_{q}}\left[\tr[\Pi^{1}_{\text{output}}\rho^{0}_{i_{1},\dots,i_{q}}]\right]\geq
1-2^{-c_{0}n}-2^{-c_{0}n/4}\geq 1-2^{-c_{1}n}$

for some constant $c_{1}>c_{0}$. Hence, after $l=\mathcal{O}(1)$ of such
steps, we have that with probability at least

$\displaystyle\prod_{i\in[l]}1-2^{-c_{i}n/2}\geq\left(1-2^{-c_{l}n/2}\right)^{l}$

each step had an acceptance probability $\geq 1-2^{-c_{1}n}$. Hence, the
majority vote definitely accepts with probability at least

$\displaystyle\left(1-2^{-c_{l}n/2}\right)^{l}\left(1-2^{-c_{l}n}\right)^{l}\geq
1-2^{-\Omega(n)},$

when $l\in\mathcal{O}(1)$, as desired. ∎

##  Appendix B Sufficient error bounds for learning weighted Hamiltonians from
non-adaptive quantum PCPs

In the lemma proven in this appendix we give sufficient parameters to adopt
the quantum reduction of [WFC23] to the $\mathsf{QPCP}_{\textup{NA}}$ setting.

######  Lemma B.1.

Let $H=\sum_{i\in[m]}p_{i}H_{i}$ be a $k$-local Hamiltonian consisting of
weights $p_{i}\in[0,1]$ such that $\sum_{i\in[m]}p_{i}=1$, and $k$-local terms
$H_{i}$ for which $\norm{H_{i}}\leq 1$ for all $i\in[m]$. Suppose
$\tilde{H}=\sum_{i\in[m]}\tilde{p}_{i}\tilde{H}_{i}$ is another Hamiltonian
such that, for all $i\in[m]$, we have $\tilde{H}_{i}$ PSD,
$\absolutevalue{\tilde{p}_{i}-p_{i}}\leq\epsilon_{0}$ and
$\norm{H_{i}-\tilde{H}_{i}}\leq\epsilon_{1}$. Let
$\tilde{W}=\sum_{i\in[m]}\tilde{p}_{i}$ and,

$\displaystyle\hat{p}_{i}=\frac{\tilde{p}_{i}}{\tilde{W}},\quad\hat{H}_{i}=\frac{\tilde{H}_{i}}{\text{argmax}_{i\in[m]}\\{\tilde{H}_{i},1\\}}$

for all $i\in[m]$. Then we have that setting

$\displaystyle\epsilon_{0}\leq\frac{\epsilon}{8m^{2}}\quad\epsilon_{1}\leq\frac{\epsilon}{6},$

suffices to have

$\displaystyle\norm{H_{x}-\tilde{H}_{x}}\leq\epsilon.$

###### Proof.

Suppose $\epsilon_{0}<1/2m$. Then

$\displaystyle\absolutevalue{\hat{p}_{i}-p_{i}}$
$\displaystyle=\absolutevalue{\frac{\tilde{p_{i}}}{\tilde{W}}-p_{i}}$
$\displaystyle\leq\frac{p_{i}+\epsilon_{0}}{1-m\epsilon_{0}}-p_{i}$
$\displaystyle=\frac{\epsilon_{0}(mp_{i}+1)}{1-m\epsilon_{0}}$
$\displaystyle\leq\frac{\epsilon_{0}(m+1)}{1-m\epsilon_{0}}$
$\displaystyle\leq 4\epsilon_{0}m.$

For the local terms we have

$\displaystyle\norm{\hat{H}_{i}-H_{i}}$
$\displaystyle\leq\norm{\hat{H}_{i}-\tilde{H}_{i}}+\norm{\tilde{H}_{i}-H_{i}}$
$\displaystyle\leq\absolutevalue{\frac{1}{1+\epsilon_{1}}-1}\norm{\tilde{H}_{i}}+\epsilon_{1}$
$\displaystyle\leq\epsilon_{1}(1+\epsilon_{1})+\epsilon$
$\displaystyle=2\epsilon_{1}+\epsilon_{1}^{2}$

So finally,

$\displaystyle\norm{H-\tilde{H}}$
$\displaystyle=\norm{\sum_{i\in[m]]}\hat{p}_{i}\tilde{H}_{i}-\sum_{i\in[m]}p_{i}H_{i}}$
$\displaystyle\leq\sum_{i\in[m]}\norm{\hat{p}_{i}\tilde{H}_{i}-p_{i}H_{i}}$
$\displaystyle\leq\sum_{i\in[m]}\norm{\hat{p}_{i}\tilde{H}_{i}-p_{i}H_{i}}$
$\displaystyle\leq\sum_{i\in[m]}\norm{\hat{p}_{i}\left(\tilde{H}_{i}-{H}_{i}\right)+H_{i}\left(\hat{p}_{i}-p_{i}\right)}$
$\displaystyle\leq\sum_{i\in[m]}\norm{\hat{p}_{i}\left(\tilde{H}_{i}-{H}_{i}\right)}+\norm{H_{i}\left(\hat{p}_{i}-p_{i}\right)}$
$\displaystyle\leq\sum_{i\in[m]}\hat{p}_{i}\norm{\tilde{H}_{i}-{H}_{i}}+\norm{H_{i}}\absolutevalue{\hat{p}_{i}-p_{i}}$
$\displaystyle\leq 2\epsilon_{1}+\epsilon_{1}^{2}+4m^{2}\epsilon_{0}$

which can be made $\leq\epsilon$ if for example

$\displaystyle\epsilon_{0}\leq\frac{\epsilon}{8m^{2}}\quad\epsilon_{1}\leq\frac{\epsilon}{6}.$

∎

##  Appendix C Proof of Corollary 4.1

See 4.1

###### Proof.

We have that $H_{x}$ (resp. $\tilde{H}_{x}$ are specified by the
$4^{q}\binom{p(n)}{q}$ complex numbers
$\bra{\alpha}H_{x,i_{1},\dots,i_{q}}\ket{\beta}$ (resp.
$\bra{\alpha}\tilde{H}_{x,(i_{1},\dots,i_{q})}\ket{\beta}$). Note that
$\absolutevalue{\bra{\alpha}H_{x,i_{1},\dots,i_{q}}\ket{\beta}}\leq 1$ since

$\displaystyle\absolutevalue{\bra{\alpha}H_{x,i_{1},\dots,i_{q}}\ket{\beta}}\leq\max_{\alpha,\beta}\absolutevalue{\bra{\alpha}H_{x,i_{1},\dots,i_{q}}\ket{\beta}}\leq\norm{H_{x,i_{1},\dots,i_{q}}}\leq
1.$

Therefore, we can adopt the following binary notation to specify the values of
$\bra{\alpha}H_{x,i_{1},\dots,i_{q}}\ket{\beta}\in\mathbb{C}$: we use the
most-significant bit to indicate whether it is the real or complex part, all
remaining bits to specify a value in $[-1,1]$ in evenly spaced intervals. We
have that

$\text{Re}(\bra{\alpha}\tilde{H}_{x,(i_{1},\dots,i_{q})}\ket{\beta})$ is
correct up to $\eta$ bits $\displaystyle\Updownarrow$
$\displaystyle\absolutevalue{\text{Re}(\bra{\alpha}\tilde{H}_{x,(i_{1},\dots,i_{q})}\ket{\beta})-\text{Re}(\bra{\alpha}\tilde{H}_{x,(i_{1},\dots,i_{q})}\ket{\beta})}\leq\frac{2}{\left(2^{\eta}+1\right)}.$

The same argument holds for the imaginary part of
$\bra{\alpha}\tilde{H}_{x,(i_{1},\dots,i_{q})}\ket{\beta}$. By the triangle
inequality, we have that in this case

$\displaystyle\absolutevalue{(\bra{\alpha}\tilde{H}_{x,(i_{1},\dots,i_{q})}\ket{\beta})-(\bra{\alpha}\tilde{H}_{x,(i_{1},\dots,i_{q})}\ket{\beta}}\leq\frac{4}{2^{\eta}+1}:=\epsilon^{\prime}.$

To achieve

$\displaystyle\frac{4}{2^{\eta}+1}\leq\frac{\epsilon}{2^{q}\Gamma(\Gamma+1)},$

it suffices to set

$\displaystyle\eta:=\lceil
q\log_{2}\left(\frac{4\Gamma(\Gamma+1)}{\epsilon}-1\right)\rceil.$

Since the Hadamard test can learn $\eta$ bits of precision in
$\mathcal{O}(2^{\eta})$ time, we have that the time complexity of the
reduction in Protocol 4.1 becomes dependent on $2^{\eta}$ instead of
$1/\epsilon$.

∎

##  Appendix D A classical oracle separation

Here we show that the same idea behind the quantum oracle separation of
Section 6 can be used to give a classical oracle separation. We first prove a
lower bound analogous to the one in Lemma 6.4 but now for ‘classical search’.

######  Lemma D.1.

Let $q\in\mathbb{N}$ and let $D_{\epsilon}^{2^{q}}$ be a $\epsilon$-covering
set of mixed states on $q$ qubits as per Proposition 6.1. Suppose we are given
oracle access to an $n$-qubit unitary $U$, and want to decide which of the
following holds:

  1. (i)

There exists an $n$-bit string $x^{*}$ such that
$\mathcal{O}_{f}\ket{x^{*}}=-\ket{x^{*}}$

  2. (ii)

$\mathcal{O}_{f}\ket{x}=\ket{x}$ for all $x$.

Then even if we have a witness tuple $(i_{1},\dots,i_{q},\rho)$, where
$i_{i_{1}},\dots,i_{i_{q}}$ is a set of the $q$ indices and a quantum witness
$\rho\in D_{\epsilon}^{k}$ in support of case (i), we still need

$\displaystyle\Omega\left(\sqrt{\frac{2^{n}}{\left(\frac{ep(n)}{q}\right)^{q}C\left(\frac{1}{\epsilon}\right)^{5\cdot
2^{q}}}}\right).$

queries to verify the witness, with bounded probability of error. Here $C>0$
is some universal constant.

###### Proof.

Let $\Omega=\\{0,1\\}^{n}$, and let $\sigma$ be any $p$-uniform distribution
over $\Omega$. Then we have that for all $\rho\in\mathcal{D}(\mathcal{H})$

$\displaystyle\max_{\sigma:p\,\text{-uniform}}\mathbb{E}_{\ket{x}\in\sigma}\left[\bra{x}\rho\ket{x}\right]$
$\displaystyle\leq\max_{\sigma:p\,\text{-uniform}}\max_{z\in\Omega}\mathbb{E}_{\ket{x}\in\sigma}\left[\bra{x}\ket{z}\bra{z}\ket{x}\right]$
$\displaystyle=\max_{\sigma:p\,\text{-uniform}}\mathbb{E}_{\ket{x}\in\sigma}\left[\bra{x}\ket{0}\bra{0}\ket{x}\right]$
$\displaystyle=\max_{\sigma:p\,\text{-uniform}}\mathbb{E}_{\ket{x}\in\sigma}\left[\absolutevalue{\bra{0}\ket{x}}^{2}\right],$

by the fact that the expected fidelity is maximised for $\rho$’s that are
basis states and then using the maximisation over $p$-uniform $\rho$ to choose
the maximal $z$ to be $0$. Clearly, this is maximised by conditioning on any
$\log_{2}(1/p)$ of bits being in $0$, which happens with probability
$(1/2)^{\log_{2}(1/p)}=p$. Hence, for any $\sigma$ we have

$\displaystyle\mathbb{E}_{\ket{x}\in\sigma}\left[\absolutevalue{\bra{0}\ket{x}}^{2}\right]$
$\displaystyle\leq\frac{2^{\log_{2}(\frac{1}{p})}}{2^{n}}=\frac{1/p}{2^{n}},$

and thus

$\displaystyle\mathbb{E}_{\ket{x}\in\sigma}\left[\bra{x}\rho\ket{x}\right]$
$\displaystyle\leq\frac{1/p}{2^{n}},$

for all mixed states $\rho$ and all $p$-uniform distributions $\sigma$. Using
the value of $p$ as in Lemma 6.4 , we obtain the lower bound of

$\displaystyle
T\geq\left(\sqrt{\frac{2^{n}}{\left(\frac{ep(n)}{q}\right)^{q}C\left(\frac{1}{\epsilon}\right)^{5\cdot
2^{q}}}}\right).$

∎

Given Lemma D.1, the following corollary follows directly from the same proof
of Theorem 6.1. See 6.1