monthdayyeardate[] ,

#  How hard is it to fake entanglement? A complexity theoretic view of
nonlocality and its applications to delegating quantum computation

Khashayar Barooti
EPFL

Grzegorz Głuch111Correspondence to<EMAIL_ADDRESS>NOT IN SUBMISSION TO
ANY OTHER CONFERENCES
EPFL

Marc-Olivier Renou
ICFO-Institut de Ciencies Fotoniques,
The Barcelona Institute of Science and Technology

###### Abstract

Is it possible to operationally distinguish every entangled state from all
separable states? This is a long-standing open question in quantum
information. More concretely, assuming that two non-communicating parties
interact classically with a verifier, can the verifier distinguish the
following two cases: (i) the parties have access to an entangled state, (ii)
they have access to a separable state only (a local hidden variable model). In
this work, we define a computational version of state non-locality, and show
that if every entangled state exhibits such non-locality then $\BQP\neq\PP$.

Surprisingly, we demonstrate how this result implies that if a one-round
delegation of quantum computation (DQC) exists then $\BQP\neq\PP$. This gives
a necessary complexity-theoretic assumption needed for the existence of such
DQC. Our proof technique essentially builds a framework that allows one to
give stronger lower-bounds for DQC by proving upper-bounds for the complexity
of local-hidden-variable models.

##  1 Intro

Axioms of quantum theory define states of a quantum system to be operators on
a Hilbert space. Consider a state $\rho_{AB}$ that is shared between two
parties $\mathbf{A}$ and $\mathbf{B}$. Such a state can fall into one of the
following categories. Either it is a _separable state_ , i.e., a state that
can be written as
$\sigma_{AB}=\sum_{i}p_{i}\sigma_{A}^{(k)}\otimes\sigma_{B}^{(k)}$. If not, it
is called _entangled_. This separation relies purely on a mathematical
formalism. The question of Entanglement = Nonlocality
($\mathtt{ENT}\stackrel{{\scriptstyle?}}{{=}}\mathtt{NL}$) asks whether there
is an operational (theory-independent) distinction between separable and
entangled states.

More formally we ask if it is true that for every entangled state $\rho_{AB}$
there exists a game/experiment between $\mathbf{A},\mathbf{B}$ and a verifier
$\mathbf{V}$ that distinguishes between two cases: (i) $\mathbf{A}$ and
$\mathbf{B}$ share $\rho_{AB}$ versus (ii) $\mathbf{A}$ and $\mathbf{B}$ share
only a separable state $\sigma_{AB}$. The game is akin to the multi-prover
interactive proof setup. More concretely, $\mathbf{A}$ and $\mathbf{B}$ are
spatially separated so that they cannot communicate, then $\mathbf{V}$
exchanges messages with both of them and at the end decides if $\mathbf{A}$
and $\mathbf{B}$ held only a separable state. The verifier $\mathbf{V}$ wins
the game if her answer is correct with high probability. Whether such a game
exists for every entangled state is the
$\mathtt{ENT}\stackrel{{\scriptstyle?}}{{=}}\mathtt{NL}$ question.

The seminal paper Bell (1964) initiated the study of quantum nonlocality, that
is, of those correlations obtained when performing local measurements on
entangled states that do not have a classical analogue. It showed that there
exists an entangled state (an EPR pair) for which there exists an experiment
distinguishing cases (i) and (ii). Initially, it was believed that
$\mathtt{ENT}=\NL$. This is in fact true for pure states (Gisin, 1991).
However, in 1989, Werner introduced (Werner (1989)) entangled states, for
which a local model can be constructed. What this means is that all
correlations obtainable with these entangled states can be reproduced in a
setting where $\mathbf{A}$ and $\mathbf{B}$ hold only a separable state. The
first simulation held only for projective measurements but it was later
generalized to all POVMs (Barrett, 2002). This implies that no experiment
distinguishes the two cases for these states and that the relation between
$\mathtt{ENT}$ and $\NL$ is more nuanced.

These surprising results suggest that no operational definition exists behind
the mathematical concept of entanglement, at least in this model. As a
consequence new models were introduced and in some cases, equality was proven.
One can tweak the model in many ways, e.g., allowing quantum communication
between $\mathbf{V}$ and $\mathbf{A},\mathbf{B}$, considering multi-round
games instead of a one-question, one answer setting of the Bell scenario, or
allowing more than one copy of $\rho_{AB}$ to be accessible at a time. It is
probably fair to say that a satisfying answer to the $\mathtt{ENT}=\NL$ has
not been found to date. For a more detailed history of the problem see Section
2.

##### Contribution.

We define a new notion of non-locality. We call a state $\rho$ not-
efficiently-local ($\mathtt{NeL}$ for short) if there exists a probability
distribution arising from local measurements of $\rho$ such that no efficient,
non-communicating parties (sharing a separable state) can simulate this
distribution. In the spirit of the extended quantum Church-Turing thesis, by
efficient we mean implementable by $\BQP$ circuits.

We ask the following question How hard is it to fake entanglement? We prove
that a particular way of faking entanglement, i.e., the Hirsh local model
((Hirsch et al., 2013)) for 1-round protocols, can be implemented in $\PP$.
More concretely, for some entangled state $\rho_{AB}$, we show how to simulate
any strategy of $\mathbf{A},\mathbf{B}\in\BQP$ having access to a $\rho_{AB}$
by $\mathbf{A}^{\prime},\mathbf{B}^{\prime}\in\PP$ with access only to some
separable state $\sigma_{AB}$. This means that local simulation in the Bell
scenario is at most as hard as $\PP$. This implies that
$\mathtt{ENT}=\mathtt{NeL}\implies\BQP\neq\PP$. To the best of our knowledge
computational complexity of local models was never studied before.

##### Delegation of Quantum Computation.

Surprisingly the fact that Hirsch’s local model can be implemented in
$\PostBQP$ has implications for the delegation of quantum computation (DQC).
DQC is a problem where a classical client delegates and verifies computation
done by a more powerful quantum server. A breakthrough result in the field,
Mahadev (2018), gave the first, fully classical, protocol for DQC with a
relaxed requirement, i.e. guaranteeing soundness only against provers that are
quantum polynomial time. The authors proved the soundness of their DQC
assuming the quantum hardness of learning with error (LWE) problem. With this
assumption, this result establishes, under QLWE assumption,
$\BQP\subseteq\IP[\BQP,\BQP]$, i.e. a DQC with efficient ($\BQP$) honest
provers and sound against $\BQP$ adversaries.

We can view this result as establishing sufficient complexity-theoretic
assumptions needed for the existence of a DQC sound against $\BQP$. In this
paper, we ask what are the necessary assumptions. We show that if there exists
a single round extended DQC (Definition 3) which is sound against $\BQP$ then
$\BQP\neq\PP$. This is the promised necessary assumption. Interestingly the
same assumption, i.e. $\BQP\neq\PP$, was proved to be necessary (Kretschmer
(2021)) for an existence of a cryptographic primitive called pseudorandom
state generation.

##### Proof techniques.

To prove our result about DQC we crucially use the first result, i.e
$\mathtt{ENT}=\mathtt{NeL}\implies\BQP\neq\PP$. More concretely, we assume
towards contradiction that a single round extended DQC sound against $\BQP$
exists and that $\BQP=\PP$. Next, we build a protocol certifying
$\mathtt{ENT}=\mathtt{NeL}$ by using two copies of this DQC to control the
behavior of the provers. This contradicts the first result.

We believe that this is a novel technique for proving lower bounds for DQC.
The two proofs together give a framework for showing stronger results about
limits of DQC. Finding a local hidden variable model implementable in a lower
complexity class or holding for more rounds of interaction, would imply
stronger lower bounds.

##  2 Entanglement vs Non-locality - A Brief History

In this section, we introduce the definitions of entanglement and non-locality
and give a brief history of the
$\mathtt{ENT}\stackrel{{\scriptstyle?}}{{=}}\NL$ problem. We recommend
Augusiak et al. (2014) for a more detailed survey about non-locality.

We start by defining a notion of entanglement.

##### Entanglement.

For $\rho_{AB}\in\mathcal{S}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})$ we say it
is _separable_ if it can be expressed as
$\rho_{AB}=\sum_{k}p_{k}\sigma_{A}^{(k)}\otimes\sigma_{B}^{(k)}$ for some
$\sigma_{A}^{(k)}\in\mathcal{S}(\mathcal{H}_{A}),\sigma_{B}^{(k)}\in\mathcal{S}(\mathcal{H}_{B}),p_{k}>0,\sum_{k}p_{k}=1$.
Otherwise, we call it _entangled_. The most famous example of an entangled
state is the Bell state, also known as an EPR pair,
$\left|\phi^{+}\right\rangle=\frac{1}{\sqrt{2}}(\left|00\right\rangle+\left|11\right\rangle)$.
The notion of entanglement is a purely mathematical notion and a priori
doesn’t carry any operational meaning.

Next, we introduce the notion of non-locality in a way that is often presented
in the physics literature. This definition will change slightly once we
consider computational aspects (see Definition 2).

##### Non-Locality.

For a probability distribution $\mathbb{P}(a,b|x,y)$ we say $\mathbb{P}$ is
local if there exist probability distributions $\mathbb{P}_{1}(a|x,\lambda)$
and $\mathbb{P}_{2}(b|y,\lambda)$ and $\lambda$ such that

$\mathbb{P}(a,b|x,y)=\int_{\lambda}d\lambda\ \mathbb{P}_{1}(a|x,\lambda)\
\mathbb{P}_{2}(b|y,\lambda),$ (1)

where $\lambda$ is understood as a local hidden variable. Operationally this
means that there exist $\mathbf{A}$ and $\mathbf{B}$, sharing randomness
$\lambda$, such that their joint distribution replicates $\mathbb{P}$. If a
probability distribution is not local, we call it non-local.

The Bell experiment (Bell (1964)), also known as the CHSH game, is one of the
first examples that show non-locality of quantum correlations. In this game,
two non-communicating parties are given single-bit inputs, $x$ and $y$
respectively, that are uniformly distributed and are expected to reply with
single bit answers, $a$ and $b$, such that $x\land
y\stackrel{{\scriptstyle(*)}}{{=}}a\oplus b$. It can be shown that for any
local strategy (satisfying (1)), the probability of $(*)$ is upper-bounded by
$75\%$. It can also be shown that if the parties share a
$\left|\phi^{+}\right\rangle$, they can satisfy $(*)$ with $\approx 85\%$.
Hence, this shows an example of a non-local probability distribution, i.e.
$\left|\phi^{+}\right\rangle$ is non-local. This it the strongest model, in
which entanglement can be certified. The term certified usually means that we
assume quantum theory (QT) but the Bell experiment proves more, i.e. that a
theory governing the behaviour of $\mathbf{A},\mathbf{B}$ must contain some
notion of entanglement. Later the result from Bell (1964) was improved
((Gisin, 1991)) to show that all pure entangled states are non-local.

As we mentioned in the introduction, for a long time it was believed that
$\mathtt{ENT}=\NL$. A surprising result was presented by Werner (Werner
(1989)), in which it was shown that for a class of entangled states, every
distribution obtained by projective measurements can be simulated locally. Let
us give more details.

For $p\in[0,1]$ let
$\rho(p)\in\mathcal{S}(\mathbbm{C}^{2}\otimes\mathbbm{C}^{2})$ be defined as

$\rho(p):=p\left|\psi_{-}\right\rangle\left\langle\psi_{-}\right|+\frac{1-p}{4}\mathbbm{1},$
(2)

where
$\left|\psi_{-}\right\rangle=\frac{1}{\sqrt{2}}(\left|01\right\rangle-\left|10\right\rangle)$.
These states are known as the Werner states. It was shown in Werner (1989)
that $\rho_{AB}(p)$ is entangled if and only if $p>\frac{1}{3}$.

Figure 1: The two qubit Werner state
$p\left|\psi_{-}\right\rangle\left\langle\psi_{-}\right|+(1-p)\frac{\mathbb{I}}{4}$.
State $\rho(p)$ is entangled exactly for $p>\frac{1}{3}$ however all POVMs can
be simulated locally as long as $p<\frac{5}{12}$.

However, Werner showed that for any $p\leq\frac{1}{2}$, all projective
measurements on $\rho(p)$ can be simulated locally, i.e. expressed as in (1).
This result was further generalized to all POVMs when $p<5/12$ (Barrett
(2002)). Figure 1 summarizes the guarantees given for $\rho(p)$ for different
values of $p$. Does this necessarily mean that all probability distributions
arising from such states are local? In this model yes, in others not
necessarily.

As we mentioned, after the results of Werner (1989) and Barrett (2002) other
models were considered. In Buscemi (2012) equality of $\mathtt{ENT}$ and $\NL$
was shown in the Bell scenario, in a model where $\mathbf{V}$ can send quantum
states to $\mathbf{A}$ and $\mathbf{B}$. A follow-up result (Bowles et al.
(2018)) showed equivalence in a model with two additional parties: Charlie and
Daisy. To certify entanglement, EPR pairs are shared between $\mathbf{A}$ and
Charlie, and $\mathbf{B}$ and Daisy. This allows $\mathbf{V}$ to self-test the
measurements made by $\mathbf{A},\mathbf{B}$ on $\rho_{AB}$. In this model,
all the parties communicate with $\mathbf{V}$ classically. There are also some
improvements on local simulation, e.g. in Hirsch et al. (2016) it was shown
that there exist states with local models for all protocols with local
filtering. Local filtering refers to a situation where $\mathbf{A},\mathbf{B}$
first apply local operations, send one bit each to $\mathbf{V}$, receive a
challenge from $\mathbf{V}$ and reply. Thus it is a special case of $3$
message protocols, instead of $2$ messages in the Bell scenario. This case is
akin to $\Sigma$ protocols in cryptography. The question remains open for the
sequential scenario with more messages.

##  3 Modeling

Now we are ready to introduce our model and our definition of non-locality. As
our model is different from the standard setup we define the game and describe
allowed actions very carefully.

######  Definition 1.

(Game) For
$k,n\in\mathbb{N},\rho_{AB}\in\mathcal{S}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})$
we define $\mathcal{G}(\rho_{AB},k,n)$ to be a game between
$\mathbf{A},\mathbf{B}$ and $\mathbf{V}$. $\mathcal{G}$ is played in one of
two modes. $\mathbf{A},\mathbf{B}$ will have access to either (i) $\rho_{AB}$
or (ii) a separable (classical) state $\sigma_{AB}$. First, the
hyperparameters $k,n$ are distributed to all parties and one of the modes is
chosen. The mode is not known to $\mathbf{V}$. $\mathcal{G}$ proceeds in $k$
rounds.

In each round $\mathbf{A}$ and $\mathbf{B}$ are given their respective share
of $\rho_{AB}$ in mode (i) or of $\sigma_{AB}$ in mode (ii) and are forbidden
to communicate. Then

  1. 1.

$\mathbf{V}$ sends a message $a$ to $\mathbf{A}$ and $b$ to $\mathbf{B}$,
where $a,b\in\\{0,1\\}^{p(n)}$,222$p$ is a fixed polynomial.

  2. 2.

$\mathbf{A},\mathbf{B}$ compute their answers
$x_{a},x_{b}\in\\{0,1\\}^{q(n)}$.333$q$ is also a fixed polynomial. They can
operate on their respective shares of $\rho_{AB}$ in mode (i) or access their
share of $\sigma_{AB}$ in mode (ii). The computational modelling of the
behaviour of $\mathbf{A},\mathbf{B}$ is discussed below.

  3. 3.

Answers $x_{a},x_{b}$ are sent to $\mathbf{V}$, which stores them.

Then, the next round is started in a fully iid fashion, i.e.
$\mathbf{A},\mathbf{B}$ no longer have access to the previous $\rho_{AB}$, nor
$\sigma_{AB}$ and the internal state of $\mathbf{A},\mathbf{B}$ is reset.
After the $k$-th round, $\mathbf{V}$ outputs, based on $x_{a},x_{b}$’s, either
YES or NO.444$\mathbf{V}$’s actions might be adaptive from round to round.

Next, we define the new notion of non-locality.

######  Definition 2.

(not-$\mathfrak{C}$-local) For a complexity class $\mathfrak{C}$ and a state
$\rho_{AB}\in\mathcal{S}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})$ we say that
$\rho_{AB}$ is not-$\mathfrak{C}$-local if for every sufficiently small
$\delta$ there exists $k\in\mathbb{N}$, a game
$\mathcal{G}(\rho_{AB},k,\cdot)$,
$\mathbf{A}_{\BQP}(\cdot),\mathbf{B}_{\BQP}(\cdot)\in\BQP(\cdot)$ and a
polynomial $p$ such that for every $n\in\mathbb{N}$

  1. 1.

(Completeness) If $\mathcal{G}(\rho_{AB},k,n)$ was run in mode (i) with
$\mathbf{A}_{\BQP}(n),\mathbf{B}_{\BQP}(n)$ then

$\mathbb{P}[\mathbf{V}\text{ accepts}]\geq 1-\delta,$

  2. 2.

(Soundness) For every $\mathbf{A},\mathbf{B}\in\mathfrak{C}$ if
$\mathcal{G}(\rho_{AB},k,n)$ was run in mode (ii) with $\mathbf{A},\mathbf{B}$
then

$\mathbb{P}[\mathbf{V}\text{ accepts}]\leq 1-\delta-\frac{1}{p(n)}.$

##### Computational modelling.

As we are interested in the computational power of $\mathbf{A},\mathbf{B}$ we
need to model their behaviour. We assume the quantum Church-Turing hypothesis
that a quantum Turing machine can simulate any realistic model of computation.
Moreover, we assume (completeness in Definition 2) that honest
$\mathbf{A},\mathbf{B}$ run in polynomial time. More formally, we assume that
for every $n\in\mathbb{N}$ honest $\mathbf{A}_{\BQP}(n)$’s answer is the
result of applying some unitary on
$\rho_{A}\otimes\left|a\right\rangle\otimes\left|0^{q(n)-p(n)-1}\right\rangle$
for some polynomial $q(n)$ and measuring all555Wlog we can assume that
$\mathbf{A}$ and $\mathbf{B}$ measure all the qubits as an honest protocol
when the parties send a superset of information is also a valid protocol
because $\mathbf{V}$ can just ignore the extra bits. qubits in the
computational basis. This models the property that $\mathbf{A}_{\BQP}$ has
access to only polynomially many qubits. Next, by the Solovay-Kitaev theorem,
we say that the number of gates $t$ from a universal gate set needed to
approximate this unitary to within $\epsilon$ grows like
$\text{polylog}(1/\epsilon)$. Finally, we use a result from Aharonov (2003) to
argue that we can assume that the gate set used is equal to
$\\{\text{Toffoli},\text{Hadamard}\\}$ with only polylogarithmic in
$(n,t,1/\epsilon)$ blowup in the number of gates. Note that the gate set
$\\{\text{Toffoli},H\\}$ is not universal in the standard sense as both
matrices contain only real entries. However, it is enough for our purposes as
we are interested in computational universality (see Aharonov (2003)).

To summarize, there exists a family of circuits
$\\{C^{\mathbf{A}}_{n}\\}_{n\geq 1}$ acting on $q(n)$ qubits with $t(n)$ gates
(for some polynomials $q,t$) such that for every $n\in\mathbb{N}$ we have that
$\mathbf{A}_{\BQP}(n)$’s answer is the result of applying $C_{n}^{\mathbf{A}}$
on
$\rho_{A}\otimes\left|a\right\rangle\otimes\left|0\right\rangle^{q(n)-p(n)-1}$
and measuring all qubits in the computational basis. For $\mathbf{B}_{\BQP}$
the situation is analogous, i.e. there is a family of circuits
$\\{C^{\mathbf{B}}_{n}\\}_{n\geq 1}$ such that the answer of
$\mathbf{B}_{\BQP}(n)$ is the result of applying $C_{n}^{\mathbf{B}}$ on
$\rho_{B}\otimes\left|b\right\rangle\otimes\left|0\right\rangle^{q(n)-p(n)-1}$
and measuring all qubits in the computational basis.666Note that we can assume
wlog that both circuits operate on $q(n)$ qubits.

For the complexity theoretic upper bound on the local-hidden-variable
simulation we consider $\mathbf{A},\mathbf{B}$ in $\PostBQP$. By this we mean
that $\mathbf{A}$ and $\mathbf{B}$ are modeled as quantum circuits also but
with the ability to perform post-selection. This is the ability to post-select
on a particular qubit being $\left|1\right\rangle$. More concretely, for a
state $\sum_{x\in\\{0,1\\}^{n}}\alpha_{x}\left|x\right\rangle$ if the post-
selection is applied to the first qubit then the resulting state is

$\left(\sum_{x^{\prime}\in\\{0,1\\}^{n-1}}|\alpha_{1x^{\prime}}|^{2}\right)^{-1}\sum_{x^{\prime}\in\\{0,1\\}^{n-1}}\alpha_{1x^{\prime}}\left|1x^{\prime}\right\rangle.$

We can think of post-selection as a new 1-qubit gate that can be applied to a
chosen qubit. In the seminal result Aaronson (2005) it was shown that
$\PostBQP=\PP$. The class $\PP$ consists of problems solvable by an $\NP$
machine such that (i) if the answer is yes then at least $\frac{1}{2}$ of
computation paths accept, (ii) if the answer is no then less than
$\frac{1}{2}$ of computation paths accept.

##### Access to $\sigma_{AB}$.

In mode (ii) of the game (Definition 1) $\mathbf{A},\mathbf{B}$ have access to
a separable state
$\sigma_{AB}\in\mathcal{S}(\mathcal{H}_{A}\otimes\mathcal{H}_{B}),\
\sigma_{AB}=\sum_{k}p_{k}\sigma_{A}^{(k)}\otimes\sigma_{B}^{(k)}$. We assume
that $\mathbf{A}$ and $\mathbf{B}$ have special registers, where, at the
beginning of each round, $k$ is sampled according to $p_{k}$ and a state
$\sigma_{A}^{(k)}$ is placed in $\mathbf{A}$’s register and $\sigma_{B}^{(k)}$
is placed in $\mathbf{B}$’s register. Note that when we assume that
$\mathbf{A},\mathbf{B}\in\PostBQP(n)$ it implies that $\sigma_{AB}$ is a state
on at most $\poly(n)$ qubits.

When there are no restrictions on computational capabilities of
$\mathbf{A},\mathbf{B}$ then $\sigma_{AB}$ can be thought of as public
randomness. This is the case because any distribution $\\{p_{k}\\}$ can be
approximated to high precision with access to an infinite string of common
randomness and every separable state on finite-dimensional space can be
approximated by local operations. But note that once we limit the
computational power of $\mathbf{A},\mathbf{B}$ the equivalence is not clear.
Thus, we state all our results in terms of separable states, not public
randomness.

##  4 Main result

With the story of the entanglement vs nonlocality question behind us and our
model of computation introduced we can state the computational version of the
$\mathtt{ENT}=\mathtt{NL}$ question.

######  Conjecture 1 ($\mathtt{ENT}=\mathtt{NeL}$).

For every finite-dimensional $\mathcal{H}_{A},\mathcal{H}_{B}$ and every
$\rho_{AB}\in\mathcal{S}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})$, such that
$\rho_{AB}$ is entangled, $\rho_{AB}$ is not-efficiently-local.

We note that the other implication is trivial as any separable state is
simulatable by itself.

The main theorem of the paper can be stated as

######  Theorem 1.

$\mathtt{ENT}=\mathtt{NeL}\Rightarrow\BQP\neq\PostBQP(=\PP)$.

The proof is deferred to Appendix B. As we discussed before the proof designs
an algorithm in $\PostBQP$ that implements some local model.

###  4.1 Implications of Theorem 1 for Delegation of Quantum Computation

As we discussed, Theorem 1 is informal in its own right but surprisingly it
also implies necessary complexity theoretic separations needed for existence
of delegation of quantum computation protocols (DQC).

A DQC is an interactive protocol $(\mathbf{V},*)$ between an efficient
classical verifier $\mathbf{V}\in\BPP$ and a prover. For a complexity class
$\mathfrak{C}$ we say a DQC protocol is $\BQP$-complete and
$\mathfrak{C}$-sound if, on input $(C,x)$, where $C$ is a quantum circuit and
$x$ is a classical bit string, the following two conditions hold:

  1. 1.

There exists an honest prover $\mathbf{P}\in\BQP$ such that the interaction
between $\mathbf{V}$ and $\mathbf{P}$ is accepted with overwhelming
probability.

  2. 2.

For any malicious prover $\widetilde{\mathbf{P}}\in\mathfrak{C}$, if the
interaction of $\widetilde{\mathbf{P}}$ and $\mathbf{V}$ is accepted with
overwhelming probability, then the distribution of the output of $\mathbf{V}$
is close to the distribution of measuring the output qubit of $\mathcal{C}$
ran on $\left|x\right\rangle$.777The distance can either be the total
variation distance or defined by computational indistinguishability.

Naturally the bigger the $\mathfrak{C}$ the harder it is to design such a
protocol. The extreme is to allow $\mathfrak{C}=\texttt{ALL}$, which
translates to a question whether $\BQP\subseteq\IP[\BQP,\texttt{ALL}]$, i.e.
do all languages in $\BQP$ have interactive proofs with efficient honest
provers sound against all adversaries. The smallest complexity class for which
the question makes sense is $\mathfrak{C}=\BQP$. This is the setting we focus
on here.

The first construction of a $\BQP$-sound DQC was presented by Mahadev (2018),
where the authors showed how to achieve it under the QLWE assumption, i.e.
that no quantum polynomial time prover can solve the learning with errors
problem. Not long after, several new variants of this protocol appeared in the
literature. In Gheorghiu and Vidick (2019) it was showed how to build a blind
version of this protocol by forcing the prover to prepare a quantum state
blindly. In Alagic et al. (2020), using a Fiat-Shamir-like argument and
parallel repetition of the Mahadev protocol, the authors showed how to
implement this protocol in a single round of communication in the quantum-
random-oracle-model (QROM). This shows that the quantum hardness of LWE + QROM
gives sufficient complexity-theoretic assumptions required to achieve a
single-round DQC.

Figure 2: Relationship between computational complexity classes.

##### Our result.

We show what are the necessary complexity theoretic assumptions for a
$\BQP$-sound DQC. More concretely we prove that the existence of an extended,
single-round delegation of quantum computation (EDQC, see Definition 3)
implies $\BQP\neq\PP$888Another way of phrasing our result is that there does
not exist a single-round EDQC which is $\BQP$-complete and $\PP$-sound..

It is important to note that it was already known that existence of a constant
round DQC sound against all adversaries implies $\BQP\subseteq\AM$ ((Aaronson,
2010)). We want to emphasize that our conclusion of $\BQP\neq\PP$ is
incomparable with $\BQP\subseteq\AM$. Consult Figure 2 for known relationships
between complexity classes of interest.

We elaborate on why the conclusion $\BQP\neq\PP$ is interesting. To do that we
give an example of a cryptographic primitive that has recently attracted a lot
of attention and whose existence was shown to require $\BQP\neq\PP$ also.
Pseudorandom states, introduced in Ji et al. (2018), are efficiently-
computable quantum states that are computationally indistinguishable from
Haar-random states. One-way functions imply the existence of pseudorandom
states, but Kretschmer et al. (2022) constructed an oracle relative to which
there are no one-way functions but pseudorandom states still exist. This
influenced Ananth et al. (2021) to design cryptographic primitives based on
PRS. In another work (Morimae and Yamakawa (2022)) it has been shown that PRSs
are enough to construct quantum bit commitments and signatures. Interestingly
Kretschmer (2021) proved that $\BQP\neq\PP$ is a necessary condition for the
existence of pseudo-random quantum state generators (PRSG). This is exactly
the same complexity theoretic separation implied by our result.

####  4.1.1 Extended Delegation of Quantum Computation

We are ready to give a definition of an extended delegation of quantum
computation (EDQC). Informally speaking, for a circuit $\mathcal{C}$ our
definition guarantees that: (i) there exists an efficient verifier and an
efficient prover such that the prover can choose any state
$\rho_{QE}\in\mathcal{S}(\mathbbm{C}^{2}\otimes\mathcal{H}_{E})$ such that the
bit collected by the verifier will be distributed equally to measuring the
output qubit of $U_{\mathcal{C}}\left|x\right\rangle\rho_{Q}$, moreover the
post-measurement state of $\rho_{E}$ is exactly as if $\mathcal{C}$ was
applied, (ii) for every $\BQP$ prover accepted with high probability there
exists a 1-qubit state $\rho$ such that the output collected by the verifier
is, for every classical $x$, close to the distribution of measuring
$U_{\mathcal{C}}\left|x\right\rangle\rho$.

######  Definition 3 (EDQC).

Let $\mathcal{C}$ be a classical description of a quantum circuit on $k$
qubits that operates on two registers: $V$ of $k-1$ qubits and $Q$ of one
qubit999 Note that we could have considered a more general definition, where
the $Q$ register holds more than $1$ qubit. The definition generalizes
naturally. We chose to stick to this version for simplicity and because our
result implies that the more general protocol is not possible also.. We say
that $\mathfrak{P}$ is a 1-round protocol for extended delegation of quantum
computation (EDQC) if the following holds. For a security parameter
$\ell\in\mathbb{N}$, $\mathfrak{P}(\mathcal{C})$ expects questions
$q\in\\{0,1\\}^{n(\ell)}$ and answers $a\in\\{0,1\\}^{n(\ell)}$ for some
polynomial $n$. $\mathbf{V}$ is expected to accept or reject and upon
acceptance return $b\in\\{0,1\\}$. Moreover, there exists
$\mathbf{V}\in\text{PPT}(\ell)$ such that

  * •

(Completeness) There exists $\mathbf{P}\in\BQP(\ell)$ such that for every
$x\in\\{0,1\\}^{k-1}$ and every
$\rho_{QE}\in\mathcal{S}(\mathbbm{C}^{2}\otimes\mathcal{H}_{E})$ if $\rho_{Q}$
is given to $\mathbf{P}$ then the following hold

    * –

$\mathbf{V}$ accepts the interaction with probability $1$,

    * –

over the randomness of $\mathbf{V}$ and $\mathbf{P}$ the distribution of $b$
is equal to the distribution of measuring the last qubit ($Q$ register) of
$U_{\mathcal{C}}\left|x\right\rangle_{V}\rho_{Q}$,

    * –

$\rho_{E}$ is equal to the post-measurement state after measuring the $Q$
register conditioned on obtaining $b$. More formally it is the normalization
of

$\textnormal{Tr}_{VQ}\left[(\mathbb{I}_{V}\otimes\left|b\right\rangle_{Q}\left\langle
b\right|_{Q}\otimes\mathbb{I}_{E})(U_{\mathcal{C}}\otimes\mathbb{I}_{E})\left|x\right\rangle_{V}\rho_{QE}\right].$

  * •

(Soundness) There exists $c$ such that for every $\epsilon>0$, sufficiently
large $\ell$, for every $\mathbf{P}\in\BQP(\ell)$ that is accepted with
probability $1-\epsilon$, there exists
$\rho_{Q}\in\mathcal{S}(\mathbbm{C}^{2})$ such that for every
$x\in\\{0,1\\}^{k-1}$ the distribution of $b$ is in $O(\epsilon^{-c})$ total
variation distance of the distribution of measuring the last qubit of
$U_{\mathcal{C}}\left|x\right\rangle_{V}\rho_{Q}$.

Now we state the main theorem of this section.

######  Theorem 2.

Existence of EDQC implies $\BQP\neq\PostBQP$.

Proof of Theorem 2 is deferred to Appendix B.2. On a high levelwe design a
transformation that converts the semi-quantum protocol from Buscemi (2012)
(see Appendix B.1) to a 1-round protocol that certifies entanglement of all
entangled states against $\BQP$ adversaries, i.e. exitance of EDQC implies
$\mathtt{ENT}=\mathtt{NeL}$. Now invoking Theorem 1 we deduce that existence
of such an experiment would imply $\BQP\neq\PostBQP$.

###  4.2 Why this definition of EDQC?

In this section we briefly discuss how the EDQC introduced in Definition 3
relates to other notions of DQC from the literature. We argue that all non-
standard requirements of EDQC are similar to properties of DQC already
considered in the constructions based on LWE. There are 3 crucial differences
between EDQC and more standard versions of DQC. We

  1. 1.

require single round of communication,

  2. 2.

allow the prover to select a part of the input to the circuit,

  3. 3.

don’t allow the prover to select this input adaptively.

Let’s elaborate on each point. The first difference is that we require the
protocol to be single round. Although the original delegation protocol from
(Mahadev, 2018) requires several rounds of interaction, Alagic et al. (Alagic
et al., 2020) described how this protocol can be transformed into a single
round protocol in the QROM. This is done by a technique similar to the Fiat-
Shamir transform and parallel repetitions of the measurement protocol from
Mahadev (2018).

As we discussed in the intro our proof technique could in principle be
generalized beyond single round setting. We focused on a single-round local
simulation but in Hirsch et al. (2016) the authors describe a local hidden
variable model (LHVM) for a more general setting. They consider filtering
experiments (3 message experiments resembling $\Sigma$-protocols). If one
proves that this LHVMs can be realized in $\PostBQP$ then Theorem 2
automatically extends to $3$-message EDQCs. Similarly if one introduces a LHVM
for sequential measurement games the theorem would naturally extend to EDQCs
with multiple rounds.

The second non-standard feature is that the prover plugs in a part of the
input not controlled by the verifier (the state $\rho_{Q}$). We argue that
this should be possible to realize in DQC protocols that rely on Kitaev’s
local-hamiltonian reduction. This is similar to how the Mahadev protocol can
be extended to realize verification of QMA, for instance in Bartusek et al.
(2022). To realize this functionality one can remove terms from the
Hamiltonian that correspond to the portion of input that the verifier does not
control (removing a part of $H_{\text{in}}$). An in-depth description of the
guarantees, when the penalty terms corresponding to the input are partially
removed, can also be found in (Barooti et al., 2021, Lemma 4).

The final difference from the standard setup is that, $\rho$ from the
soundness property of Definition 3 is assumed to have no dependence on the
input $x$. Intuitively this means that the adversary is not allowed to choose
the circuit input states adaptively, i.e., dependent on $x$. This property is
reminiscent of blindness - second after verifiability property of interest for
DQC. It is clear that our property does not directly imply blindness, at least
in the case of multi-round protocols, as, for instance, if the prover was to
commit to a state and receive the input in the clear our property would still
hold but the protocol would not be blind.

Although it seems that standard definitions of blindness, i.e.
indistinguishably of the views for different values of $x$, would imply this
property, a formal proof seems to be non-trivial. The main issue is that the
state $\rho$ (Definition 3) is an abstract state, that the prover does not
necessarily need to have access to. Hence, we can not argue that $\rho$ is
only dependent on the randomness of the verifier and the question $q$. If the
definition is stronger and implies that the prover _holds_ the state,
similarly to guarantees in Vidick and Zhang (2021), it might be possible to
show that blindness implies our property.

## References

  * Aaronson (2005) S. Aaronson.  Quantum computing, postselection, and probabilistic polynomial-time.  _Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences_ , 461, 01 2005.  doi: 10.1098/rspa.2005.1546.
  * Aaronson (2010) S. Aaronson.  BQP and the polynomial hierarchy.  In L. J. Schulman, editor, _Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010_ , pages 141–150. ACM, 2010.  doi: 10.1145/1806689.1806711.  URL https://doi.org/10.1145/1806689.1806711.
  * Aharonov (2003) D. Aharonov.  A simple proof that toffoli and hadamard are quantum universal.  _arXiv: Quantum Physics_ , 2003.
  * Alagic et al. (2020) G. Alagic, A. M. Childs, A. B. Grilo, and S.-H. Hung.  Non-interactive classical verification of quantum computation.  _IACR Cryptol. ePrint Arch._ , 2020:1422, 2020.
  * Ananth et al. (2021) P. Ananth, L. Qian, and H. Yuen.  Cryptography from pseudorandom quantum states.  Cryptology ePrint Archive, Paper 2021/1663, 2021.  URL https://eprint.iacr.org/2021/1663.  https://eprint.iacr.org/2021/1663.
  * Augusiak et al. (2014) R. Augusiak, M. Demianowicz, and A. Acín.  Local hidden–variable models for entangled quantum states.  _Journal of Physics A: Mathematical and Theoretical_ , 47, 05 2014\.  doi: 10.1088/1751-8113/47/42/424002.
  * Barooti et al. (2021) K. Barooti, G. Gluch, and R. L. Urbanke.  Provable adversarial robustness in the quantum model.  _CoRR_ , abs/2112.09625, 2021.  URL https://arxiv.org/abs/2112.09625.
  * Barrett (2002) J. Barrett.  Nonsequential positive-operator-valued measurements on entangled mixed states do not always violate a bell inequality.  _Phys. Rev. A_ , 65:042302, Mar 2002.  doi: 10.1103/PhysRevA.65.042302.  URL https://link.aps.org/doi/10.1103/PhysRevA.65.042302.
  * Bartusek et al. (2022) J. Bartusek, Y. T. Kalai, A. Lombardi, F. Ma, G. Malavolta, V. Vaikuntanathan, T. Vidick, and L. Yang.  Succinct classical verification of quantum computation.  In Y. Dodis and T. Shrimpton, editors, _Advances in Cryptology - CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15-18, 2022, Proceedings, Part II_ , volume 13508 of _Lecture Notes in Computer Science_ , pages 195–211. Springer, 2022.  doi: 10.1007/978-3-031-15979-4\\_7.  URL https://doi.org/10.1007/978-3-031-15979-4_7.
  * Bell (1964) J. S. Bell.  On the einstein podolsky rosen paradox.  _Physics Physique Fizika_ , 1:195–200, Nov 1964.  doi: 10.1103/PhysicsPhysiqueFizika.1.195.  URL https://link.aps.org/doi/10.1103/PhysicsPhysiqueFizika.1.195.
  * Bowles et al. (2018) J. Bowles, I. Šupić, D. Cavalcanti, and A. Acín.  Device-independent entanglement certification of all entangled states.  _Phys. Rev. Lett._ , 121:180503, Oct 2018.  doi: 10.1103/PhysRevLett.121.180503.  URL https://link.aps.org/doi/10.1103/PhysRevLett.121.180503.
  * Buscemi (2012) F. Buscemi.  All entangled quantum states are nonlocal.  _Phys. Rev. Lett._ , 108:200401, May 2012.  doi: 10.1103/PhysRevLett.108.200401.  URL https://link.aps.org/doi/10.1103/PhysRevLett.108.200401.
  * Gheorghiu and Vidick (2019) A. Gheorghiu and T. Vidick.  Computationally-secure and composable remote state preparation.  11 2019.  doi: 10.1109/FOCS.2019.00066.
  * Gisin (1991) N. Gisin.  Bell’s inequality holds for all non-product states.  _Physics Letters A_ , 154(5):201–202, 1991.  ISSN 0375-9601.  doi: https://doi.org/10.1016/0375-9601(91)90805-I.  URL https://www.sciencedirect.com/science/article/pii/037596019190805I.
  * Hirsch et al. (2013) F. Hirsch, M. T. Quintino, J. Bowles, and N. Brunner.  Genuine hidden quantum nonlocality.  _Physical review letters_ , 111 16:160402, 2013.
  * Hirsch et al. (2016) F. Hirsch, M. T. Quintino, J. Bowles, T. Vértesi, and N. Brunner.  Entanglement without hidden nonlocality.  _New Journal of Physics_ , 18(11):113019, nov 2016\.  doi: 10.1088/1367-2630/18/11/113019.  URL https://dx.doi.org/10.1088/1367-2630/18/11/113019.
  * Horodecki et al. (1996) M. Horodecki, P. Horodecki, and R. Horodecki.  Separability of mixed states: necessary and sufficient conditions.  _Physics Letters A_ , 223(1):1–8, 1996.  ISSN 0375-9601.  doi: https://doi.org/10.1016/S0375-9601(96)00706-2.  URL https://www.sciencedirect.com/science/article/pii/S0375960196007062.
  * Ji et al. (2018) Z. Ji, Y.-K. Liu, and F. Song.  Pseudorandom quantum states.  Cryptology ePrint Archive, Paper 2018/544, 2018.  URL https://eprint.iacr.org/2018/544.  https://eprint.iacr.org/2018/544.
  * Kretschmer (2021) W. Kretschmer.  Quantum pseudorandomness and classical complexity.  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.  doi: 10.4230/LIPICS.TQC.2021.2.  URL https://drops.dagstuhl.de/opus/volltexte/2021/13997/.
  * Kretschmer et al. (2022) W. Kretschmer, L. Qian, M. Sinha, and A. Tal.  Quantum cryptography in algorithmica, 2022.  URL https://arxiv.org/abs/2212.00879.
  * Mahadev (2018) U. Mahadev.  Classical verification of quantum computations.  _2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 259–267, 2018.
  * Morimae and Yamakawa (2022) T. Morimae and T. Yamakawa.  Quantum commitments and signatures without one-way functions.  In _Advances in Cryptology – CRYPTO 2022_ , pages 269–295. Springer Nature Switzerland, 2022.  doi: 10.1007/978-3-031-15802-5_10.  URL https://doi.org/10.1007%2F978-3-031-15802-5_10.
  * Vidick and Zhang (2021) T. Vidick and T. Zhang.  Classical proofs of quantum knowledge.  In A. Canteaut and F. Standaert, editors, _Advances in Cryptology - EUROCRYPT 2021 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17-21, 2021, Proceedings, Part II_ , volume 12697 of _Lecture Notes in Computer Science_ , pages 630–660. Springer, 2021.  doi: 10.1007/978-3-030-77886-6\\_22.  URL https://doi.org/10.1007/978-3-030-77886-6_22.
  * Werner (1989) R. F. Werner.  Quantum states with einstein-podolsky-rosen correlations admitting a hidden-variable model.  _Phys. Rev. A_ , 40:4277–4281, Oct 1989.  doi: 10.1103/PhysRevA.40.4277.  URL https://link.aps.org/doi/10.1103/PhysRevA.40.4277.

##  Appendix A Preliminaries

$\mathcal{H}$ always denotes a finite-dimensional Hilbert space. For
$k\in\mathbb{N}$ we use $[k]:=\\{0,1\dots,k-1\\}$. We denote by
$\mathcal{P}(\mathcal{H})$ the set of positive semi-definite linear operators
from $\mathcal{H}$ to itself. We define the set of normalized quantum states
$\mathcal{S}(\mathcal{H}):=\\{\rho\in\mathcal{P}(\mathcal{H}):\textnormal{Tr}[\rho]=1\\}$.
We also define the set of pure states
$\Omega(\mathcal{H}):=\\{\left|\lambda\right\rangle\in\mathcal{H}\
|\left\langle\lambda\middle|\lambda\right\rangle=1\\}$. We denote by
$\omega(\mathcal{H})$ the unique distribution over $\Omega(\mathcal{H})$
invariant under unitaries and by $\mathbbm{1}$ the identity operator. For pure
states, $\left|\lambda\right\rangle\in\Omega(\mathcal{H})$, we often
interchangeably use $\left|\lambda\right\rangle$ and
$\left|\lambda\right\rangle\left\langle\lambda\right|$. We write
$\mathcal{H}_{AB}=\mathcal{H}_{A}\otimes\mathcal{H}_{B}$ for a bipartite
system and $\rho_{AB}\in\mathcal{S}(\mathcal{H}_{AB})$ for a bipartite state.
$\rho_{A}=\textnormal{Tr}_{B}[\rho_{AB}],\rho_{B}=\textnormal{Tr}_{A}[\rho_{AB}]$
denote the corresponding reduced densities.

A collection of $k$ operators $\mathcal{A}=\\{\mathcal{A}_{i}\\}_{i=0}^{k-1}$,
where $\mathcal{A}_{i}\in\mathcal{P}(\mathcal{H})$ is called a _$k$ -outcome_
POVM if $\sum_{i=0}^{k-1}\mathcal{A}_{i}=\mathbbm{1}$. The probability of
obtaining outcome $i\in[k]$ when $\mathcal{A}$ is measured on a state
$\rho\in\mathcal{S}(\mathcal{H})$ is equal to
$p(i|\mathcal{A})=\textnormal{Tr}[\mathcal{A}_{a}\rho]$. For our applications
we can, without loss of generality, assume that all $\mathcal{A}_{i}$ are rank
one. It is because any measurement with operators of rank larger than one can
always be realized as a measurement with rank-one operators. More concretely
for every $i\in[k]$ we can write
$\mathcal{A}_{i}=\sum_{j}\eta_{i}^{(j)}P_{i}^{(j)}$ with
$\eta_{i}^{(j)}\in(0,1]$ and $P_{i}^{(j)}$ being the rank-one projectors of
$\mathcal{A}_{i}$. Now $\mathcal{A}_{i,j}=\eta_{i}^{(j)}P_{i}^{(j)}$ is a
POVM, which is a finer grained version of $\\{\mathcal{A}_{i}\\}$. To
reproduce the statistics of the original POVM one simply applies the finer
POVM and forgets the result $j$. Thus for every $i\in[k]$ we can write
$\mathcal{A}_{i}=\eta_{i}P_{i}$, where $\eta_{i}\in(0,1]$ and $P_{i}$ is a
rank-one projection.

##  Appendix B Proof of Theorem 1

Before we prove Theorem 1 we show some helpful lemmas. The first lemma shows
that there exists a $\PostBQP$ algorithm that given access to $\poly$ copies
of a pair of states can compute the square of the dot product of some
corresponding pair of states up to exponential precision. The core of the
proof is a combination of a binary-search-like procedure with a technique from
Aaronson [2005]. This technique allows, for a state
$a\left|0\right\rangle+b\left|1\right\rangle$, where $a,b>0$, to design a
$\PostBQP$ algorithm that, when given access to polynomially many copies of
the state, computes $a,b$ up to exponential precision.

######  Lemma 1.

(Dot product estimation) There exists a uniform family of $\PostBQP(n)$
circuits $\\{C^{<\cdot,\cdot>}_{n}\\}_{n}$ such that for all pairs of states
$\left|\psi\right\rangle=a\left|0\right\rangle+b\left|1\right\rangle$ and
$\left|\psi^{\prime}\right\rangle=\text{Re}(a^{\prime})\left|00\right\rangle+\text{Im}(a^{\prime})\left|01\right\rangle+\text{Re}(b^{\prime})\left|10\right\rangle+\text{Im}(b^{\prime})\left|11\right\rangle$,
where $a,b\in\mathbb{R},a^{\prime},b^{\prime}\in\mathbbm{C}$ the following
holds. For every $n\in\mathbb{N}$, if $C^{<\cdot,\cdot>}_{n}$ is given access
to $\poly(n)$ copies of $\left|\psi\right\rangle$ and
$\left|\psi^{\prime}\right\rangle$ and
$|a|,|b|,|\text{Re}(a^{\prime})|,|\text{Im}(a^{\prime})|,|\text{Re}(b^{\prime})|,|\text{Im}(b^{\prime})|\in\\{0\\}\cup(2^{-n},2^{n})$
then $C^{<\cdot,\cdot>}_{n}$ returns $v\in\mathbb{R}$, which with probability
$1-2^{-\Omega(n)}$, satisfies

$\left|v-|aa^{\prime}+bb^{\prime}|^{2}\right|\leq 2^{-\Omega(n)}.$

###### Proof.

The full algorithm will consist of a series of subroutines.

##### Subroutine 1.

Take two states $x\left|0\right\rangle+y\left|1\right\rangle$ and
$x^{\prime}\left|0\right\rangle+y^{\prime}\left|1\right\rangle$, apply the
CNOT gate on them and postselect on the second qubit being
$\left|0\right\rangle$. The result is

$\frac{xx^{\prime}\left|0\right\rangle+yy^{\prime}\left|1\right\rangle}{\sqrt{(xx^{\prime})^{2}+(yy^{\prime})^{2}}}.$

##### Subroutine 2.

For a state $x\left|0\right\rangle+y\left|1\right\rangle$ take its two copies,
apply the CNOT gate and postselect on the second qubit being
$\left|0\right\rangle$. The result is

$\frac{x^{2}\left|0\right\rangle+y^{2}\left|1\right\rangle}{\sqrt{x^{4}+y^{4}}}.$

##### Subroutine 3.

For $\beta\in\mathbb{R}$ and a state
$x\left|0\right\rangle+y\left|1\right\rangle$ prepare
$\frac{1}{\sqrt{1+\beta^{2}}}(\left|0\right\rangle+\beta\left|1\right\rangle)(x\left|0\right\rangle+y\left|1\right\rangle)$,
apply the CNOT gate on it and postselect on the second qubit being
$\left|0\right\rangle$. The result is

$\frac{x\left|0\right\rangle+\beta
y\left|1\right\rangle}{\sqrt{x^{2}+\beta^{2}y^{2}}}.$

##### Subroutine 4. (inspired by Aaronson [2005]).

For a state $c\left|0\right\rangle+d\left|1\right\rangle$, where
$c,d\in\\{0\\}\cup\left(2^{-O(m)},2^{O(m)}\right)$ 101010Note that we used $m$
instead of $n$ here as the parameter. We do it because the subroutine will be
used later with $m=\poly(n)$., and real, positive numbers $\alpha,\beta$
prepare a state
$\alpha\left|0\right\rangle(c\left|0\right\rangle+d\left|1\right\rangle)+\beta\left|1\right\rangle
H(c\left|0\right\rangle+d\left|1\right\rangle)$ and postselect on the second
qubit being $\left|1\right\rangle$. The result is

$\left|\phi_{\beta/\alpha}\right\rangle:=\frac{\alpha
c\left|0\right\rangle+\frac{\beta}{\sqrt{2}}(c-d)\left|1\right\rangle}{\sqrt{\alpha^{2}c^{2}+\frac{\beta^{2}}{2}(c-d)^{2}}}.$
(3)

Assume $c>d+2^{-O(m)}$. We claim that there exists $i\in[-O(m),O(m)]$ such
that if we set $\beta/\alpha=2^{i}$ then $\left|\phi_{2^{i}}\right\rangle$ is
close to the state $\left|+\right\rangle$, i.e.

$|\left\langle+\middle|\phi_{2^{i}}\right\rangle|\geq\frac{1+\sqrt{2}}{\sqrt{6}}>0.985.$
(4)

From the assumption that $c>d+2^{-O(m)}$ we have that there exists
$i\in[-O(m),O(m)]$ such that $\left|\phi_{2^{i}}\right\rangle$ and
$\left|\phi_{2^{i+1}}\right\rangle$ fall on opposite sides of
$\left|+\right\rangle$ (in the first quadrant). The worst case is
$\left\langle+\middle|\phi_{2^{i}}\right\rangle=\left\langle+\middle|\phi_{2^{i+1}}\right\rangle$,
which happens for
$\left|\phi_{2^{i}}\right\rangle=\sqrt{\frac{2}{3}}\left|0\right\rangle+\sqrt{\frac{1}{3}}\left|1\right\rangle,\left|\phi_{2^{i+1}}\right\rangle=\sqrt{\frac{1}{3}}\left|0\right\rangle+\sqrt{\frac{2}{3}}\left|1\right\rangle$.
These give exactly the bound from (4).

Second case is when $c<d$ then $\left|\phi_{2^{i}}\right\rangle$ never lies in
the first or third quadrants and thus
$|\left\langle+\middle|\phi_{2^{i}}\right\rangle|<\frac{1}{\sqrt{2}}<0.985$.
The two facts together imply that repeating the procedure $\poly(m)$ times we
can distinguish $c>d+2^{-O(m)}$ from $c<d$ with probability $1-2^{-m}$.

##### Subroutine 5 (Binary search).

If for a state $x\left|0\right\rangle+y\left|1\right\rangle$ we run Subroutine
2. and 3. with $\beta>0$ we obtain $\frac{x^{2}\left|0\right\rangle+\beta
y^{2}\left|1\right\rangle}{\sqrt{x^{4}+\beta^{2}y^{4}}}$. If both of the
amplitudes $\in\\{0\\}\cup\left(2^{-O(m)},2^{O(m)}\right)$ we can run
Subroutine 4. to distinguish between $x^{2}>\beta
y^{2}+\sqrt{x^{4}+\beta^{2}y^{4}}\cdot 2^{-O(m)}$ and $x^{2}<\beta y^{2}$.
This means that we can run a binary-search-like algorithm with $\poly(n)$
repetitions of Subroutine 4. (with parameter $m=\poly(n)$) such that with
probability $1-2^{-n}$ we find $\beta_{0}>0$ such that

$|x^{2}-\beta_{0}y^{2}|\leq 2^{-2n}.$

##### Algorithm.

By assumption of the lemma we can run Subroutine 5. on
$\left|\psi\right\rangle$, $\left|\psi^{\prime}\right\rangle$ postselected on
the second qubit being $\left|0\right\rangle$, $\left|\psi\right\rangle$
postselected on the second qubit being $\left|1\right\rangle$ and
$\left|\psi^{\prime}\right\rangle$ after measuring the second qubit to find
$\beta_{0},\beta_{0}^{\prime},\beta_{0}^{\prime\prime},\beta_{0}^{\prime\prime\prime}$
that satisfy

$\displaystyle|a^{2}-\beta_{0}b^{2}|\leq
2^{-2n},|\text{Re}(a^{\prime})^{2}-\beta_{0}^{\prime}\text{Re}(b^{\prime})^{2}|\leq
2^{-2n}$
$\displaystyle|\text{Im}(b^{\prime})^{2}-\beta_{0}^{\prime\prime}\text{Im}(b^{\prime})^{2}|\leq
2^{-2n},|(\text{Re}(a^{\prime})^{2}+\text{Im}(a^{\prime})^{2})-\beta_{0}^{\prime\prime\prime}(\text{Re}(b^{\prime})^{2}+\text{Im}(b^{\prime})^{2})|\leq
2^{-2n}.$ (5)

Note that the quantity of interest is equal to

$[a\text{Re}(a^{\prime})+b\text{Re}(b^{\prime})]^{2}+[a\text{Im}(a^{\prime})+b\text{Im}(b^{\prime})]^{2}.$
(6)

If we run Subroutine 1. on $\left|\psi\right\rangle$ and
$\left|\psi^{\prime}\right\rangle$ postselected on the second qubit being
$\left|0\right\rangle$ followed by Subroutine 3. with parameter
$1/\sqrt{\beta_{0}\beta_{0}^{\prime}}$. The result is

$\frac{a\text{Re}(a^{\prime})\left|0\right\rangle+(1/\sqrt{\beta_{0}})b(1/\sqrt{\beta_{0}^{\prime}})\text{Re}(b^{\prime})\left|1\right\rangle}{\sqrt{(a\text{Re}(a^{\prime}))^{2}+1/(\beta_{0}\beta_{0}^{\prime})(b\text{Re}(b^{\prime}))^{2}}},$
(7)

which by (5) and the assumption of the lemma that
$|a|,|b|,|\text{Re}(a^{\prime})|,|\text{Re}(b^{\prime})|\in(2^{-n},2^{n})$ is
close (up to an irrelevant phase) to either $\left|+\right\rangle$ or
$\left|-\right\rangle$. Thus, measuring (7) in the Hadamard basis gives us,
with probability $1-2^{-\Omega(n)}$,
$\text{sgn}(a\text{Re}(a^{\prime})b\text{Re}(b^{\prime}))$. Similarly we
compute $\text{sgn}(a\text{Im}(a^{\prime})b\text{Im}(b^{\prime}))$.

The two signs together with (5) are enough to compute an approximation to (6).
It is because the signs give us information about the relative sign ($+/-$) in
each of the summand in (6), Moreover, (5) allows us to compute all quantities
of interest in (6) (up to a sign), because of the normalization of
$\left|\psi\right\rangle$ and $\left|\psi^{\prime}\right\rangle$. For example,
we can compute $a,b$ up to a relative sign using the fact that $a^{2}+b^{2}=1$
and that $|a^{2}-\beta_{0}b^{2}|\leq 2^{-2n}$.

We conclude, by the union bound, that with probability $1-2^{-\Omega(n)}$ we
compute $v$ satisfying the statement of the lemma. ∎

The next series of lemmas explain how to simulate some entangled states using
only separable states. That is, for some entangled state $\rho_{AB}$ and
measurements applied on it by $\mathbf{A},\mathbf{B}$ we show how to reproduce
the statistics of outcomes by $\mathbf{A}^{\prime},\mathbf{B}^{\prime}$ having
access only to a separable state.

######  Lemma 2 (Werner’s model).

For every $q\leq\frac{1}{2}$ the Werner state $\rho(q)$, defined in (2), is
local for all projective measurements: $\\{P,\mathbb{I}-P\\}$ for $\mathbf{A}$
and $\\{Q,\mathbb{I}-Q\\}$ for $\mathbf{B}$.

###### Proof.

The first step is to show that the statement holds for the maximal value of
$q$, i.e. $q=\frac{1}{2}$. The strategy is as follows:
$\mathbf{A}^{\prime},\mathbf{B}^{\prime}$ share
$\left|\lambda\right\rangle\sim\omega(\mathbbm{C}^{2})$, $\mathbf{A}^{\prime}$
returns $1$ if
$\left\langle\lambda\right|P\left|\lambda\right\rangle<\left\langle\lambda\right|(\mathbb{I}-P)\left|\lambda\right\rangle$
and $0$ otherwise. $\mathbf{B}^{\prime}$ returns $1$ with probability
$\left\langle\lambda\right|Q\left|\lambda\right\rangle$. The proof that this
gives rise to a distribution equal to arising from measuring the projections
on $\rho(\frac{1}{2})$ can be found in [Augusiak et al., 2014, section 3.1].

Now, for any $\rho(q)$ with $q<\frac{1}{2}$ we do the following. We write
$\rho(q)$ as a mixture of $\rho(\frac{1}{2})$ and white noise $\mathbb{I}$,
i.e. $\rho(q)=2q\rho(\frac{1}{2})+\frac{1-2q}{4}\mathbb{I}$. As
$q\leq\frac{1}{2}$, $2q<1$, so we can consider the following strategy for
$\mathbf{A}^{\prime},\mathbf{B}^{\prime}$: With probability $2q$ (that is
coordinated with shared randomness) they perform the strategy as described for
$\rho(\frac{1}{2})$ and with probability $\frac{1-2q}{4}$ they return a
uniformly random bit.

Direct derivation gives us $\mathbb{P}(a,b|P,Q)=\textnormal{Tr}[(P_{a}\otimes
Q_{b})\rho(q)]=2q\cdot\textnormal{Tr}[(P_{a}\otimes
Q_{b})\rho(\frac{1}{2})]+\frac{1-2q}{4}$. This matches the distribution of the
outputs produced by $\mathbf{A}^{\prime}$ and $\mathbf{B}^{\prime}$, as with
probability $2q$ they reproduce the distribution associated with measuring
$\rho(\frac{1}{2})$ and return uniformly random bits with probability $1-2q$.

∎

The following family of entangled states will play an important role.

######  Definition 4.

For $q\in[0,1]$ we define
$\rho_{0}(q)\in\mathcal{S}(\mathbbm{C}^{2}\otimes\mathbbm{C}^{2})$ as

$\rho_{0}(q):=q\left|\psi_{-}\right\rangle\left\langle\psi_{-}\right|+\frac{1-q}{2}\left|0\right\rangle\left\langle
0\right|\otimes\mathbbm{1}.$ (8)

We note that $\rho_{0}(q)$ is entangled for all $q\in(0,1]$.

######  Lemma 3.

For every $q\leq\frac{1}{3}$, the state $\rho_{0}(q)$, defined in (8), is
local for all projective measurements: $\\{P,\mathbb{I}-P\\}$ for $\mathbf{A}$
and $\\{Q,\mathbb{I}-Q\\}$ for $\mathbf{B}$.

###### Proof.

The proof follows a similar strategy to the one of Lemma 2. We write
$\rho_{0}(q)$ as a mixture of the Werner state $\rho(\frac{1}{2})$ and a
separable state.

$\rho_{0}(q)=2q\rho(q)+(1-3q)(\left|0\right\rangle\left\langle
0\right|\otimes\mathbb{I}/2)+q(\left|-\right\rangle\left\langle-\right|\otimes\mathbb{I}/2)$
(9)

Now $\mathbf{B}^{\prime}$ does the following: with probability $2q$, he acts
as described in Lemma 2 for the case of $q=\frac{1}{2}$, and with probability
$1-2q$ outputs a random bit. Alice acts as follows: with probability $2q$ she
acts as in Lemma 2, with probability $1-3q$ measures $P$ on
$\left|0\right\rangle\left\langle 0\right|$ and with probability $q$ measures
$P$ on $\left|-\right\rangle\left\langle-\right|$.

∎

######  Lemma 4.

For every $q>0$ if we set $\sigma_{A,B}=\left|0\right\rangle\left\langle
0\right|$ in the following definition

$\displaystyle\rho^{*}$
$\displaystyle:=\frac{1}{4}\left[\rho_{0}(q)+\rho_{A}\otimes\sigma_{B}+\sigma_{A}\otimes\rho_{B}+\sigma_{A}\otimes\sigma_{B}\right]$
$\displaystyle=\frac{1}{4}\left[q\left|\psi_{-}\right\rangle\left\langle\psi_{-}\right|+(2-q)\left|0\right\rangle\left\langle
0\right|\otimes\frac{\mathbbm{1}}{2}+q\frac{\mathbbm{1}}{2}\otimes\left|0\right\rangle\left\langle
0\right|+(2-q)\left|00\right\rangle\left\langle 00\right|\right]$

where $\rho_{A,B}=\textnormal{Tr}_{B,A}(\rho_{0}(q))$, then $\rho^{*}$ is
entangled.

###### Proof.

The proof is given in Hirsch et al. [2013]. Interestingly the proof strategy
is to give a 2-round protocol for certifying non-locality of $\rho^{*}$. The
statement follows as 2-round non-locality implies entanglement. ∎

######  Lemma 5 (Hirsh’s model).

For $q\leq\frac{1}{2}$ define a state

$\rho^{*}=\frac{1}{4}\left[\rho_{0}(q)+\rho_{A}\otimes\sigma_{B}+\sigma_{A}\otimes\rho_{B}+\sigma_{A}\otimes\sigma_{B}\right],$

where $\sigma_{A,B}$ are arbitrary $2$-dimensional states and
$\rho_{A,B}=\textnormal{Tr}_{B,A}(\rho_{0}(q))$. Then $\rho^{*}$ is local for
all POVMs. Moreover, it is local via Algorithm 1 and 2.

###### Proof.

Direct computation gives us that

$\displaystyle\mathbb{P}[x,y\ |\ \mathcal{A},\mathcal{B}]=$
$\displaystyle\frac{\eta_{x}\xi_{y}}{4}\left(\textnormal{Tr}[(P_{x}\otimes
Q_{y})\rho_{0}]+\textnormal{Tr}[P_{x}\sigma_{A}]\textnormal{Tr}[Q_{y}\sigma_{B}]+\textnormal{Tr}[P_{x}\rho_{A}]\textnormal{Tr}[Q_{y}\sigma_{B}]+\textnormal{Tr}[P_{x}\sigma_{A}]\textnormal{Tr}[Q_{y}\rho_{b}]\right).$
(10)

We consider cases depending on whether $\mathbf{A}^{\prime}$ returned in (i)
line 8 or (ii) line 11 of Algorithm 1 and whether $\mathbf{B}^{\prime}$
returned in (i) line 7 or (ii) line 10 of Algorithm 2.

If both return in (i) then, by Lemma 3, the simulation recovers the statistics
of $\rho_{0}$, the probability is equal to
$\frac{\eta_{x}\xi_{y}}{4}\textnormal{Tr}[(P_{x}\otimes Q_{y})\rho_{0}]$,
which is equal to the first term of (10). If $\mathbf{A}^{\prime}$ return in
(i) and $\mathbf{B}^{\prime}$ returns in (ii) then the probability is
$\frac{1}{4}\textnormal{Tr}[\mathcal{A}_{x}\rho_{A}]\textnormal{Tr}[\mathcal{B}_{y}\sigma_{B}]$.
If $\mathbf{A}^{\prime}$ return in (ii) and $\mathbf{B}^{\prime}$ returns in
(i) then the probability is
$\frac{1}{4}\textnormal{Tr}[\mathcal{A}_{x}\sigma_{A}]\textnormal{Tr}[\mathcal{B}_{y}\rho_{B}]$.
The last case is when both return in (ii) and the probability is then
$\frac{1}{4}\textnormal{Tr}[\mathcal{A}_{x}\sigma_{A}]\textnormal{Tr}[B_{y}\sigma_{B}]$.
Summing all the terms we arrive at (10). ∎

Having established some helpful lemmas about dot product computation in
$\PostBQP$ and ways to simulate some entangled states locally we are ready to
prove Theorem 1. We restate it here for convenience.

See 1

###### Proof.

We will prove the contraposition of the statement, i.e.
$\BQP=\PostBQP\Rightarrow\mathtt{ENT}\neq\mathtt{NL}$. We will give an example
of
$\mathcal{H}_{A},\mathcal{H}_{B},\rho_{AB}\in\mathcal{S}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})$
and show that for sufficiently small $\delta$, for all $k\in\mathbb{N}$ and
all $\mathcal{G}(\rho_{AB},k,\cdot)$ there exists $n\in\mathbb{N}$ such that
one of the two requirements from Definition 2 does not hold.

##### Local model.

Define a state

$\rho^{*}:=\frac{1}{4}\left[\frac{1}{3}\left|\psi_{-}\right\rangle\left\langle\psi_{-}\right|+\frac{5}{3}\left|0\right\rangle\left\langle
0\right|\otimes\frac{\mathbbm{1}}{2}+\frac{1}{3}\cdot\frac{\mathbbm{1}}{2}\otimes\left|0\right\rangle\left\langle
0\right|+\frac{5}{3}\left|00\right\rangle\left\langle 00\right|\right],$

Note that it is a special case of the state from Lemma 4 for $q=\frac{1}{3}$.
By Lemma 5 we know that $\rho^{*}$ is local via Algorithm 1 and 2.

Algorithm 1 Alice’s Simulation

1: Input: parameter $q$, description of
$\rho_{AB}^{*}=\frac{1}{4}\left[\rho_{0}(q)+\rho_{A}\otimes\sigma_{B}+\sigma_{A}\otimes\rho_{B}+\sigma_{A}\otimes\sigma_{B}\right]$,
POVM $\mathcal{A}=\\{\mathcal{A}_{x}\\}_{x}=\\{\eta_{x}P_{x}\\}_{x}$, state
$\left|\lambda\right\rangle\sim\omega(\mathbbm{C}^{2})$.

2: Sample $x$ according to $\eta_{x}/2$

3: Set
$b_{1}=\mathbbm{1}_{\left\langle\lambda\right|P_{x}\left|\lambda\right\rangle<\left\langle\lambda\right|(\mathbb{I}-P_{x})\left|\lambda\right\rangle}$

4: Sample $b_{2}\sim\text{Ber}(\left\langle
0\right|P_{x}\left|0\right\rangle)$

5: Sample $b_{3}\sim\text{Ber}(\left\langle-\right|P_{x}\left|-\right\rangle)$

6: Pick $b$ from $\\{b_{1},b_{2},b_{3}\\}$ with corresponding probabilities
$2q,1-3q,q$

7: if $b=1$ then

8: Return $x$

9: else

10: Sample $x^{\prime}$ according to
$\textnormal{Tr}[\mathcal{A}_{x^{\prime}}\sigma_{A}]$

11: Return $x^{\prime}$

12: end if

Algorithm 2 Bob’s Simulation

1: Input: parameter $q$, description of
$\rho_{AB}^{*}=\frac{1}{4}\left[\rho_{0}(q)+\rho_{A}\otimes\sigma_{B}+\sigma_{A}\otimes\rho_{B}+\sigma_{A}\otimes\sigma_{B}\right]$,
POVM $\mathcal{B}=\\{\mathcal{B}_{y}\\}_{y}=\\{\xi_{y}Q_{y}\\}_{y}$, state
$\left|\lambda\right\rangle\sim\omega(\mathbbm{C}^{2})$.

2: Sample $y$ according to $\xi_{y}/2$

3: Sample
$b_{1}\sim\text{Ber}(\left\langle\lambda\right|Q_{y}\left|\lambda\right\rangle)$

4: Sample $b_{2}\sim\text{Ber}(\frac{1}{2})$

5: Pick $b$ from $\\{b_{1},b_{2}\\}$ with corresponding probabilities $2q$ and
$1-2q$

6: if $b=1$ then

7: Return $y$

8: else

9: Sample $y^{\prime}$ according to
$\textnormal{Tr}[\mathcal{B}_{y^{\prime}}\sigma_{B}]$

10: Return $y^{\prime}$

11: end if

Assume towards contradiction that $\rho^{*}$ is nont-$\PostBQP$-local. This
means that for all sufficiently small $\delta_{0}$ there exists
$k\in\mathbb{N}$, a game $\mathcal{G}(\rho^{*},\delta_{0},k,\cdot)$ and
$\mathbf{A}_{\BQP},\mathbf{B}_{\BQP}$ that satisfy conditions of Definition 1.
Fix a polynomial $p$ that certifies that and sufficiently small $\delta_{0}$.
By our modelling we can assume that $\mathbf{A}_{\BQP}$ has a corresponding
family of circuits $\\{C_{n}^{\mathbf{A}}\\}$ and so does $\mathbf{B}_{\BQP}$
with $\\{C_{n}^{\mathbf{B}}\\}$.

##### Circuits and POVMs.

Circuits $C_{n}^{\mathbf{A}}$ and $C_{n}^{\mathbf{B}}$ implicitly define POVMs
$\mathcal{A},\mathcal{B}$. We will express these POVMs in terms of the
unitaries defining the circuits. For the sake of simplicity of notation, we
assume that $a,b=0^{p(n)}$ \- the proof for other $a$’s and $b$’s is
analogous. Let $U_{n}^{\mathbf{A}},U_{n}^{\mathbf{B}}$ be the unitaries
corresponding to $C_{n}^{\mathbf{A}}$ and $C_{n}^{\mathbf{B}}$ respectively.
We have that for every
$\left|\lambda\right\rangle\in\Omega(\mathbbm{C}^{2}),x\in\\{0,1\\}^{q(n)}$

$\mathbb{P}[\mathbf{A}_{\BQP}\text{ outputs }x\text{ on
}\left|\lambda\right\rangle]=\left\langle\lambda\right|\mathcal{A}_{x}\left|\lambda\right\rangle.$

With slight abuse of notation we can write:

$\displaystyle\mathbb{P}[\mathbf{A}_{\BQP}\text{ outputs }x\text{ on
}\left|\lambda\right\rangle]$
$\displaystyle=\left\langle\lambda\right|\mathcal{A}_{x}\left|\lambda\right\rangle$
$\displaystyle=\left\langle\lambda\right|(\mathbb{I}\otimes\left|0\right\rangle^{q(n)-1})^{\dagger}(U_{n}^{\mathbf{A}})^{\dagger}\left|x\right\rangle\left\langle
x\right|U_{n}^{\mathbf{A}}(\mathbb{I}\otimes\left|0\right\rangle^{q(n)-1})\left|\lambda\right\rangle.$

The POVM element $\mathcal{A}_{x}$ can be thus seen as,

$\mathcal{A}_{x}=(\mathbb{I}\otimes\left|0\right\rangle^{q(n)-1})^{\dagger}(U_{n}^{\mathbf{A}})^{\dagger}\left|x\right\rangle\left\langle
x\right|U_{n}^{\mathbf{A}}(\mathbb{I}\otimes\left|0\right\rangle^{q(n)-1}).$
(11)

Let $\left|\phi_{x}\right\rangle$ be an un-normalized vector

$\left|\phi_{x}\right\rangle\left|0\right\rangle^{q(n)-1}=\left(\mathbb{I}\otimes\left|0\right\rangle^{q(n)-1}\left\langle
0\right|^{q(n)-1}\right)(U_{n}^{\mathbf{A}})^{\dagger}\left|x\right\rangle,$
(12)

where we treat $\left|\phi_{x}\right\rangle$ as an element of
$\Omega(\mathbbm{C}^{2})$. Then we have that

$\eta_{x}=\left\langle\phi_{x}\middle|\phi_{x}\right\rangle,\ \
P_{x}=\frac{\left|\phi_{x}\right\rangle\left|0\right\rangle^{q(n)-1}\left\langle
0\right|^{q(n)-1}\left\langle\phi_{x}\right|}{\left\langle\phi_{x}\middle|\phi_{x}\right\rangle}.$
(13)

This is a direct consequence of the observation that:

$(\mathcal{A}_{x})^{2}=\eta_{x}^{2}P_{x}=\eta_{x}\mathcal{A}_{x}.$

plugging in $\mathcal{A}_{x}$ from equation (11) we get to (13).

##### Computation in $\PostBQP$.

Now we want to design $\mathbf{A}^{\prime},\mathbf{B}^{\prime}$ that simulate
answers of $\mathbf{A}_{\BQP},\mathbf{B}_{\BQP}$ to high precision. We will
focus on $\mathbf{A}$, as the proof for $\mathbf{B}$ is analogous. Note that
to implement Algorithm 1 (the situation is analogous for Algorithm 2) it is
enough to be able to

  1. 1.

sample $x$ according to $\eta_{x}/2$,

  2. 2.

compute
$\left\langle\lambda\right|P_{x}\left|\lambda\right\rangle=|(\alpha_{x}\left\langle
0\right|+\beta_{x}\left\langle
1\right|)\left|\lambda\right\rangle|^{2},\left\langle
0\right|P_{x}\left|0\right\rangle,\left\langle-\right|P_{x}\left|-\right\rangle$
to high precision. We will analyze the precision needed and it’s influence on
the final result later in the proof,

  3. 3.

sample $x^{\prime}$ according to
$\textnormal{Tr}[\mathcal{A}_{x^{\prime}}\left|0\right\rangle\left\langle
0\right|]$.

For $\left|\lambda\right\rangle\in\Omega(\mathbbm{C}^{2})$ represented as
$\lambda_{0}\left|0\right\rangle+\lambda_{1}\left|1\right\rangle$, where
$\lambda_{0},\lambda_{1}\in\mathbbm{C}$, define the representation of
$\left|\lambda\right\rangle$ by a state with only real amplitudes as
$\left|\lambda^{\text{real}}\right\rangle:=\text{Re}(\lambda_{0})\left|00\right\rangle+\text{Im}(\lambda_{0})\left|01\right\rangle+\text{Re}(\lambda_{1})\left|10\right\rangle+\text{Im}(\lambda_{1})\left|11\right\rangle$.
Assume $\mathbf{A}^{\prime},\mathbf{B}^{\prime}$ have access to
$\left|\lambda^{\text{real}}\right\rangle_{A}^{\otimes\poly(n)}\otimes\left|\lambda^{\text{real}}\right\rangle_{B}^{\otimes\poly(n)}$,
where $\left|\lambda\right\rangle\sim\omega(\mathbbm{C}^{2})$. To implement:

  1. 1.

$\mathbf{A}^{\prime}$ runs the circuit on
$\left|0\right\rangle\left|0\right\rangle^{q(n)-1}$ with probability
$\frac{1}{2}$ and on $\left|1\right\rangle\left|0\right\rangle^{q(n)-1}$ with
probability $\frac{1}{2}$, and then measures all the qubits to obtain $x$. The
result is equivalent to running the circuit on a qubit with a density matrix
$\rho=\frac{\mathbb{I}}{2}$. By definition, $x$ is distributed according to
$\eta_{x}/2$. This step is thus in $\BQP$.

  2. 2.

According to (12) and (13) the eigenvector of $P_{x}$ is defined by the
amplitudes in front of $\left|0\right\rangle\left|0\right\rangle^{q(n)-1}$ and
$\left|1\right\rangle\left|0\right\rangle^{q(n)-1}$ after the circuit is run
backwards on $\left|x\right\rangle$, i.e. after applying
$(U_{n}^{\mathbf{A}})^{\dagger}$ on $\left|x\right\rangle$. Let the
eigenvector of $P_{x}$ be expressed as

$\alpha_{x}\left|0\right\rangle+\beta_{x}\left|1\right\rangle:=\frac{\left|\phi_{x}\right\rangle}{\sqrt{\left\langle\phi_{x}\middle|\phi_{x}\right\rangle}}.$
(14)

Observe that we can compute the state
$\alpha_{x}\left|0\right\rangle+\beta_{x}\left|1\right\rangle$ in $\PostBQP$.
To do that run the circuit backwards on $\left|x\right\rangle$. Now we want to
postselect on all qubits but the first being $\left|0\right\rangle$. We apply
a negation gate on all these qubits, then compute an AND and write the result
to a fresh ancilla. At the end, we postselect on this ancilla qubit being
$\left|1\right\rangle$. The result is a state
$\alpha_{x}\left|0\right\rangle+\beta_{x}\left|1\right\rangle$. This step
crucially uses the ability to postselect and is the main bottleneck to
implementing this simulation in a lower complexity class.

As we assumed that the circuit uses the gate set $\\{H,\text{Toffoli}\\}$ it
implies $\alpha_{x},\beta_{x}\in\mathbb{R}$. But even more than that the
amplitudes of $(U_{n}^{\mathbf{A}})^{\dagger}\left|x\right\rangle$ can be
expressed as a sum of at most $t(n)$ products of at most $t(n)$ values from
the set $\left\\{1,\frac{1}{\sqrt{2}},\frac{-1}{\sqrt{2}}\right\\}$. It is
because these are the entries of matrices $H$ and Toffoli. Because $t(n)$ is a
polynomial in $n$ this guarantees that

$|\alpha_{x}|,|\beta_{x}|\in\\{0\\}\cup\left(2^{-\poly(n)},2^{\poly(n)}\right).$
(15)

For a parameter $n^{\prime}$ observe that as
$\left|\lambda\right\rangle\sim\omega(\mathbbm{C}^{2})$ we have

$\displaystyle\mathbb{P}\Big{[}|\text{Re}(\lambda_{0})|\not\in(2^{-n^{\prime}},2^{n^{\prime}})\vee|\text{Im}(\lambda_{0})|\not\in(2^{-n^{\prime}},2^{n^{\prime}})\vee$
$\displaystyle|\text{Re}(\lambda_{1})|\not\in(2^{-n^{\prime}},2^{n^{\prime}})\vee|\text{Im}(\lambda_{1})|\not\in(2^{-n^{\prime}},2^{n^{\prime}})\Big{]}\leq
2^{-\Omega(n^{\prime})}.$ (16)

To apply Lemma 1 we need $\alpha_{x},\beta_{x}\in\mathbb{R}$ and
$|\alpha_{x}|,|\beta_{x}|,|\text{Re}(\lambda_{0})|,|\text{Im}(\lambda_{0})|,$
$|\text{Re}(\lambda_{1})|,|\text{Im}(\lambda_{1})|\in\\{0\\}\cup(2^{-n^{\prime}},2^{n^{\prime}})$,
for some parameter $n^{\prime}$. Properties (15) and (16) guarantee that, if
$\mathbf{A}^{\prime}$ sets $n^{\prime}=\poly(n)$ and uses Lemma 1 with
parameter $n^{\prime}$ and her share of
$\left|\lambda^{\text{real}}\right\rangle_{A}^{\otimes\poly(n)}\otimes\left|\lambda^{\text{real}}\right\rangle_{B}^{\otimes\poly(n)}$,
then (by the union bound), with probability $1-2^{-10q(n)}$, she computes $v$
such that

$|v-\left\langle\lambda\right|P_{x}\left|\lambda\right\rangle|\leq
2^{-10q(n)}.$ (17)

Similar argument gives that $\mathbf{A}^{\prime}$ can compute
$v^{\prime},v^{\prime\prime}$ such that with probability $1-2^{-10q(n)}$

$|v^{\prime}-\left\langle
0\right|P_{x}\left|0\right\rangle|,|v^{\prime\prime}-\left\langle-\right|P_{x}\left|-\right\rangle|\leq
2^{-10q(n)}.$ (18)

Setting $n^{\prime}=\poly(n)$ incurs at most a $\poly(n)$ blowup in the number
of states needed.

  3. 3.

$\mathbf{A}^{\prime}$ runs $C_{n}^{\mathbf{A}}$ on
$\left|0\right\rangle\left|0\right\rangle^{q(n)-1}$ and measures all the
qubits to obtain $x^{\prime}$. By definition $x^{\prime}$ is distributed
according to
$\textnormal{Tr}[\mathcal{A}_{x^{\prime}}\left|0\right\rangle\left\langle
0\right|]$.

An analogous algorithm is implemented by $\mathbf{B}^{\prime}$.

##### Approximation errors.

Now we can bound the difference in answer statistics between
$\mathbf{A}^{\prime},\mathbf{B}^{\prime}$ and
$\mathbf{A}_{\BQP},\mathbf{B}_{\BQP}$ that arises from errors coming from
(17), (18) and failure events. By assumption
$\left|\lambda\right\rangle\sim\omega(\mathbbm{C}^{2})$, so with probability
$1-2^{-9q(n)}$

$|\left\langle\lambda\right|P_{x}\left|\lambda\right\rangle-\left\langle\lambda\right|(\mathbb{I}-P_{x})\left|\lambda\right\rangle|>2^{-10q(n)}.$
(19)

Then if (17) holds then the bit $b_{1}$ computed by $\mathbf{A}^{\prime}$ is
correct. By the union bound over failure events (17), (18) and (19) we have
that $\mathbf{A}^{\prime}$ answer differs from Algorithm 1 with probability at
most $3\cdot 2^{-9q(n)}$. A similar argument holds for $\mathbf{B}^{\prime}$.
By the union bound over $\mathbf{A}^{\prime}$ and $\mathbf{B}^{\prime}$ we
obtain

$\big{|}\mathbb{P}[\mathbf{A}_{\BQP}\text{ returns }x\text{ and
}\mathbf{B}_{\BQP}\text{ returns }y]-\mathbb{P}[\mathbf{A}^{\prime}\text{
returns }x\text{ and }\mathbf{B}^{\prime}\text{ returns }y]\big{|}\leq 6\cdot
2^{-9q(n)}\leq 2^{-8q(n)}.$ (20)

##### Final step.

Now we arrive at a contradiction. The game is played $k$ rounds, which means
that $\mathbf{V}$ collects $k$ samples. By (20) and the properties of the TV-
distance we know that these $k$ samples are from a distribution that is
$k\cdot 2^{-8q(n)}$ away in TV-distance from a distribution corresponding to
$\mathbf{A}_{\BQP},\mathbf{B}_{\BQP}$. As there are $2^{2q(n)}$ different
pairs of answers for $\mathbf{A},\mathbf{B}$ then by the properties of the TV-
distance the probability that $\mathbf{V}$ will distinguish the two
distributions is at most

$k\cdot 2^{2q(n)-8q(n)}\leq 2^{-5q(n)},$

which implies, as per completeness in Definition 2 (where it is required that
$\mathbf{V}$ accepts $\mathbf{A}_{\BQP},\mathbf{B}_{\BQP}$ with high
probability) that the interaction is accepted with probability at least

$1-\delta_{0}-2^{-\Omega(n)}.$ (21)

This is a contradiction as $\mathbf{V}$ should, as per soundness in Definition
2, accept the interaction with $\mathbf{A}^{\prime},\mathbf{B}^{\prime}$ with
probability at most $1-\delta_{0}-\frac{1}{p(n)}$ but it does it with at least
(21).

∎

###  B.1 The Buscemi Experiment and Entanglement Witnesses

In this section we introduce the semi-quantum game from Buscemi [2012] that
certifies entanglement of all entangled states in a model, where quantum
communication is allowed. To describe the protocol we first define what an
entanglement witness is.

######  Definition 5 (Entanglement witness).

For an entangled state
$\rho\in\mathcal{S}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})$, an entanglement
witness $W_{\rho}$ with a parameter111111As the set of separable states is
convex we can require a $\eta>0$ separation instead of the usual non-
negative/positive separation. $\eta>0$ is a Hermitian operator acting on
$\mathcal{H}_{A}\otimes\mathcal{H}_{B}$ such that,

$\displaystyle\textnormal{Tr}[W_{\rho}\rho]<-\eta,$
$\displaystyle\textnormal{Tr}[W_{\rho}\sigma]>\eta\text{ for all separable
states }\sigma\in\mathcal{S}(\mathcal{H}_{A}\otimes\mathcal{H}_{B}).$ (22)

Entanglement witnesses were considered in Horodecki et al. [1996] as one of
possible criteria to distinguish entangled and separable states. As the set of
separable states is convex, all entangled states have entanglement witnesses.
Any witness $W_{\rho}$ can be rewritten as

$W_{\rho}=\sum_{x,y}\beta_{x,y}\ \tau_{x}^{\top}\otimes\omega_{y}^{\top},$
(23)

where $\tau_{s},\omega_{t}$ are the projectors onto the corresponding state in
$\\{\left|0\right\rangle,\left|1\right\rangle,\left|+\right\rangle,\left|-\right\rangle,\left|i\right\rangle,\left|-i\right\rangle\\}$.

Let’s describe the Buscemi game. The input to each one of $\mathbf{A}$ and
$\mathbf{B}$ is a single qubit quantum state, chosen uniformly at random from
the set
$\\{\left|0\right\rangle,\left|1\right\rangle,\left|+\right\rangle,\left|-\right\rangle,\left|i\right\rangle,\left|-i\right\rangle\\}$.
$\mathbf{A}$ is expected to return $b_{A}$ and $\mathbf{B}$ to return $b_{B}$,
where $b_{A},b_{B}\in\\{0,1\\}$.

In the game the verifier estimates the value of a score function $I$,

$I=\sum_{x,y}\beta_{x,y}\ \mathbb{P}(b_{A}=1,b_{B}=1\ |\
\tau_{x},\omega_{y}).$

After several runs of the experiment, the verifier computes an estimate of the
score function $\hat{I}$ and claims that the parties held an entangled state
if $\hat{I}$ was negative.

Honest provers, sharing $\rho$, can project their input together with their
share of $\rho$ on a $\left|\phi_{+}\right\rangle$. This would yield
$I=\textnormal{Tr}[W_{\rho}\rho]/4<-\eta/4$. Moreover, it can be proven that
for any separable state and any two provers having access to it,
$\mathbb{E}[\hat{I}]=I>\eta$. Hence, by repeating the process, the verifier
can distinguish the two cases with a probability arbitrarily close to $1$.

###  B.2 Proof of Theorem 2

###### Proof.

Let $\mathfrak{P}$ be a single round EDQC, guaranteeing soundness against all
provers in $\BQP$. We show that this implies that every entangled state is
$\mathtt{NeL}$. More formally let
$\rho_{AB}\in\mathcal{S}(\mathbbm{C}^{2}\otimes\mathbbm{C}^{2})$ be an
entangled state. For every sufficiently small $\delta$ we will show that there
exists $k\in\mathbb{N}$ and a game $\mathcal{G}$ that satisfies Definition 1
for $\mathfrak{C}=\BQP$.

Let $\mathcal{C}$ be a quantum circuit acting on $4$ qubits, with registers:
$A$ of $3$ qubits and $Q$ of $1$ qubit. To every $x\in\\{0,1\\}^{3}$ we
associate
$\tau_{x}\in\\{\left|0\right\rangle,\left|1\right\rangle,\left|+\right\rangle,\left|-\right\rangle,\left|i\right\rangle,\left|-i\right\rangle\\}$
such that the association is surjective. For $x\in\\{0,1\\}^{3}$ and
$\rho_{Q}\in\mathcal{S}(\mathbbm{C}^{2})$ the circuit works as follows,
$U_{\mathcal{C}}\left|x\right\rangle_{A}\rho_{Q}$ first creates $\tau_{x}$ out
of $x$ and then returns the result of the Bell measurement on
$\tau_{x}\otimes\rho_{Q}$. Equivalently its action can be expressed as a
projection onto
$\left|\phi^{+}\right\rangle=\frac{1}{\sqrt{2}}(\left|00\right\rangle+\left|11\right\rangle)$,
i.e. probability of returning $1$ is equal
$\textnormal{Tr}[\left|\phi^{+}\right\rangle\left\langle\phi^{+}\right|(\tau_{x}\otimes\rho_{Q})]$.

##### Game.

Let $\delta\in(0,1)$ and let $W$ be an entanglement witness of $\rho_{AB}$
with parameter $\eta$ . As discussed in Section B.1 one can express the
witness as:

$W=\sum_{x,y\in\\{0,1\\}^{3}}\beta_{x,y}\
\tau_{x}^{\top}\otimes\omega_{y}^{\top},$ (24)

for some real coefficients $\beta_{x,y}$.121212Observe that in expression (24)
there are different pairs $(x,y)$ that map to the same pair of states. It is
because $|\\{0,1\\}^{3}|=8$ but
$|\\{\left|0\right\rangle,\left|1\right\rangle,\left|+\right\rangle,\left|-\right\rangle,\left|i\right\rangle,\left|-i\right\rangle\\}|=6$.
This is inconsequential.

We define
$k=O\left(\frac{\log(1/\delta)}{\eta\min_{x,y}|\beta_{x,y}|}\right)$. The game
proceeds as follows: in each repetition $\mathbf{V}$ samples $x,y\sim
U(\\{0,1\\}^{3})$ and then proceeds with running two independent copies of
$\mathfrak{P}(\mathcal{C},x),\mathfrak{P}(\mathcal{C},y)$ with $\mathbf{A}$
and $\mathbf{B}$ respectively, collects the answers, i.e. bits $b_{A},b_{B}$.
At the end $\mathbf{V}$ computes statistics
$\widehat{\mathbb{P}}(b_{A}=1,b_{B}=1\ |\ \tau_{x},\omega_{y})$ and a score
function corresponding to $W$

$\hat{I}=\sum_{x,y}\beta_{x,y}\ \widehat{\mathbb{P}}(b_{A}=1,b_{B}=1\ |\
\tau_{x},\omega_{y}).$

Finally, $\mathbf{V}$ declares that $\mathbf{A},\mathbf{B}$ held an entangled
state if and only if $\hat{I}<0$. This can be seen as compiling the semi-
quantum game from Buscemi [2012] into a bell-like game with the help of the
EDQC $\mathfrak{P}$.

##### Completeness.

Assume the parties have access to $\rho_{AB}$, i.e. mode (i). By definition of
$\mathfrak{P}$ there exist $\mathbf{A},\mathbf{B}\in\BQP(\ell)$ satisfying the
completeness property of Definition 3. We claim that if they run their
protocol on their respective shares of $\rho_{AB}$ then they certify
completeness of Definition 2.

This strategy yields the following idealized (assuming perfect statistics)
value:

$\displaystyle I$ $\displaystyle=\sum_{x,y\in\\{0,1\\}^{3}}\beta_{x,y}\
\mathbb{P}[b_{A}=1,b_{B}=1\ |\ x,y]$ $\displaystyle=\sum_{x,y}\beta_{x,y}\
\textnormal{Tr}\left[\left(\left|\phi^{+}\right\rangle_{A}\left\langle\phi^{+}\right|_{A}\otimes\left|\phi^{+}\right\rangle_{B}\left\langle\phi^{+}\right|_{B}\right)(\tau_{x}\otimes\rho_{AB}\otimes\omega_{y})\right]$
$\displaystyle=\sum_{x,y}\beta_{x,y}\
\textnormal{Tr}[(\tau_{x}^{\top}\otimes\omega_{y}^{\top})\rho_{AB}]/4$
$\displaystyle=\textnormal{Tr}[W\rho_{AB}]/4$ By (24)
$\displaystyle\leq-\eta/4,$ By (22) (25)

where in the crucial second equality we used the following. To compute
$\mathbb{P}[b_{A}=1,b_{B}=1\ |\ x,y]$ quantum mechanics allows as to think
that first $\mathbf{A}$ performs the measurement and then $\mathbf{B}$
performs his measurement on the post measurement state after actions of
$\mathbf{A}$. By the second property of completeness we have that for every
$s$, $b_{A}$, i.e. the bit collected by $\mathbf{V}$ from $\mathbf{A}$ is
distributed according to
$\textnormal{Tr}[\left|\phi^{+}\right\rangle_{A}\left\langle\phi^{+}\right|_{A}(\tau_{x}\otimes\textnormal{Tr}_{B}[\rho_{AB}])]$.
Next, the third property of completeness guarantees that the postmeasurement
state of $\mathbf{B}$’s share of $\rho_{AB}$ is equal to the post measurement
state of performing the Bell measurement on $\tau_{x}\otimes\rho_{A}$
conditioned on obtaining outcome $b_{A}=1$. This means that $\mathbf{B}$’s
state is

$\frac{\textnormal{Tr}_{A}[(\left|\phi^{+}\right\rangle_{A}\left\langle\phi^{+}\right|_{A}\otimes\mathbb{I})(\tau_{x}\otimes\rho_{AB})]]}{\textnormal{Tr}[\left|\phi^{+}\right\rangle_{A}\left\langle\phi^{+}\right|_{A}(\tau_{x}\otimes\rho_{A})]}.$

Thus the overall probability is exactly

$\displaystyle\mathbb{P}[b_{A}=1,b_{B}=1\ |\ s,t]$
$\displaystyle=\textnormal{Tr}[\left|\phi^{+}\right\rangle_{A}\left\langle\phi^{+}\right|_{A}(\tau_{x}\otimes\rho_{A})]\cdot\frac{\textnormal{Tr}[\left|\phi^{+}\right\rangle_{B}\left\langle\phi^{+}\right|_{B})\left(\textnormal{Tr}_{A}[(\left|\phi^{+}\right\rangle_{A}\left\langle\phi^{+}\right|_{A}\otimes\mathbb{I})(\tau_{x}\otimes\rho_{AB})]\otimes\omega_{t}\right)]}{\textnormal{Tr}[\left|\phi^{+}\right\rangle_{A}\left\langle\phi^{+}\right|_{A}(\tau_{x}\otimes\rho_{A})]}$
$\displaystyle=\textnormal{Tr}[\left|\phi^{+}\right\rangle_{B}\left\langle\phi^{+}\right|_{B}\left(\textnormal{Tr}_{A}[(\left|\phi^{+}\right\rangle_{A}\left\langle\phi^{+}\right|_{A}\otimes\mathbb{I})(\tau_{x}\otimes\rho_{AB})]\otimes\omega_{t}\right)]$
$\displaystyle=\textnormal{Tr}\left(\left(\left|\phi^{+}\right\rangle_{A}\left\langle\phi^{+}\right|_{A}\otimes\left|\phi^{+}\right\rangle_{B}\left\langle\phi^{+}\right|_{B}\right)(\tau_{x}\otimes\rho_{AB}\otimes\omega_{t})\right),$

where we used the properties of partial trace in the last equality. From (25),
setting of
$k=O\left(\frac{\log(1/\delta)}{\eta\min_{s,t}|\beta_{s,t}|}\right)$ and a
standard application of the Chernoff bound we get that with probability
$1-\delta$ we have $|\hat{I}-I|<\eta/4$, hence $\hat{I}\leq 0$ and thus the
interaction is accepted.

##### Soundness.

Let Enc be the $\mathbf{V}$’s deterministic algorithm for generating $q$ that
takes as input $x\in\\{0,1\\}^{3}$ and randomness
$r\in\\{0,1\\}^{\poly(\ell)}$, i.e. $q=\textsc{Enc}(x,r)$ and similarly Dec be
the $\mathbf{V}$’s deterministic algorithm for generating $b$, i.e.
$b=\textsc{Dec}(x,r,a)$. Let $\mathbf{A},\mathbf{B}\in\BQP(\ell)$ be run in
mode (ii), i.e. access to a separable state
$\sigma_{AB}=\sum_{k=1}^{\infty}p_{k}\
\sigma_{A}^{(k)}\otimes\sigma_{B}^{(k)}\in\mathcal{S}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})$.131313We
allow $\sigma_{A}$ to be a convex combination of infinitely many product
states.

Assume towards contradiction that there exists a negligible function negl such
that $\mathbf{V}$ accepts with probability at least
$1-\delta-\text{negl}(\ell)$. Let $\ell$ be large enough so that
$\text{negl}(\ell)\leq\delta$. Then $\mathbf{V}$ accepts with probability
$1-2\delta$.

For simplicity of notation denote the size of the questions and answers in the
protocol as $n=n(\ell)$. For every $q\in\\{0,1\\}^{n}$ let
$\\{\mathcal{A}_{a}(q)\\}_{a\in\\{0,1\\}^{n}}$ be the effective POVM acting on
$\mathcal{H}_{A}$ that defines $\mathbf{A}$’s actions. Similarly for every
$q^{\prime}\in\\{0,1\\}^{n}$ we define
$\\{\mathcal{B}_{a^{\prime}}(q^{\prime})\\}_{a^{\prime}\in\\{0,1\\}^{n}}$ as
the effective POVM acting on $\mathcal{H}_{B}$ for $\mathbf{B}$. Also let
$\\{\mathcal{C}_{b}\\}_{b\in\\{0,1\\}}$ be the effective POVM of circuit
$\mathcal{C}$ acting on $k$ qubits. Denote by $R$ the length of the randomness
$r$ used in ENC. We express the probability of $b_{A}=1,b_{B}=1$. For every
$x,y\in\\{0,1\\}^{3}$

$\displaystyle\mathbb{P}[b_{A}=1,b_{B}=1\ |\ x,y]$
$\displaystyle=2^{-2R}\sum_{r,r^{\prime}}\sum\limits_{\begin{subarray}{c}a:\text{DEC}(x,r,a)=1\\\
a^{\prime}:\text{DEC}(y,r^{\prime},a^{\prime})=1\end{subarray}}\sum_{k}p_{k}\textnormal{Tr}\left[\left(\mathcal{A}_{a}(\text{ENC}(x,r))\otimes\mathcal{B}_{a^{\prime}}(\text{ENC}(y,r^{\prime})\right)\left(\sigma_{A}^{(k)}\otimes\sigma_{B}^{(k)}\right)\right]$
$\displaystyle=\sum_{k}p_{k}2^{-2R}\sum_{r}\sum\limits_{\begin{subarray}{c}a:\text{DEC}(x,r,a)=1\end{subarray}}\sum_{r^{\prime}}\sum\limits_{\begin{subarray}{c}a^{\prime}:\text{DEC}(y,r^{\prime},a^{\prime})=1\end{subarray}}\textnormal{Tr}\left[\mathcal{A}_{a}(\text{ENC}(x,r))\sigma_{A}^{(k)}\right]\textnormal{Tr}\left[\mathcal{B}_{a^{\prime}}(\text{ENC}(y,r^{\prime}))\sigma_{B}^{(k)}\right]$
$\displaystyle=\sum_{k}p_{k}\left(2^{-R}\sum_{r}\sum\limits_{\begin{subarray}{c}a:\text{DEC}(x,r,a)=1\end{subarray}}\textnormal{Tr}\left[\mathcal{A}_{a}(\text{ENC}(x,r))\sigma_{A}^{(k)}\right]\right)\cdot$
$\displaystyle\cdot\left(2^{-R}\sum_{r^{\prime}}\sum\limits_{\begin{subarray}{c}a^{\prime}:\text{DEC}(y,r^{\prime},a^{\prime})=1\end{subarray}}\textnormal{Tr}\left[\mathcal{B}_{a^{\prime}}(\text{ENC}(y,r^{\prime}))\sigma_{B}^{(k)}\right]\right).$
(26)

Now, if $\mathbf{V}$ accepts the whole interaction with probability
$1-2\delta$ then in particular in a single round $\mathbf{V}$ accepts the
delegation part (with $\mathbf{A}$ and $\mathbf{B}$) of the protocol with
probability at least $1-2\delta$. Thus by the Markov inequality there exists a
subset $S\subseteq\mathbb{N}$ such that $\sum_{k\in S}p_{k}\geq 1-2\delta$ and
for every $k\in S$, $\mathbf{A}$’s circuit, when given $\sigma_{A}^{(k)}$
succeeds in $\mathfrak{P}$ with probability $1-4\delta$ for every $x$. Thus if
$\delta$ is sufficiently small then for every $k\in S$ soundness of
$\mathfrak{P}$ holds, which implies that there exists a 1-qubit density matrix
$\rho_{Q}^{k}\in\mathcal{S}(\mathbbm{C}^{2})$ such that

$2^{-R}\sum_{r}\sum\limits_{\begin{subarray}{c}a:\text{DEC}(x,r,a)=1\end{subarray}}\textnormal{Tr}\left[\mathcal{A}_{a}(\text{ENC}(x,r))\sigma_{A}^{(k)}\right]=\textnormal{Tr}\left[\mathcal{C}_{1}(\left|x\right\rangle\otimes\rho_{Q}^{k})\right]\pm
O(\delta^{-c}).$ (27)

and crucially the same $\rho_{Q}^{k}$ can be taken for all $x$. Similar
argument holds for $\mathbf{B}$. Now we can use (27) in (26). We split
$\mathbb{N}$ into two groups, $S$ and $\mathbb{N}\setminus S$. For $k\in S$ we
use (27) and for $k\in\mathbb{N}\setminus S$ we bound
$\left|2^{-R}\sum_{r}\sum\limits_{\begin{subarray}{c}a:\text{DEC}(x,r,a)=1\end{subarray}}\textnormal{Tr}\left[\mathcal{A}_{a}(\text{ENC}(x,r))\sigma_{A}^{(k)}\right]-\textnormal{Tr}\left[\mathcal{C}_{1}(\left|x\right\rangle\otimes\rho_{Q}^{k})\right]\right|$
by $1$. The same operation is performed for $\mathbf{B}$. The result is

$\displaystyle\mathbb{P}[b_{A}=1,b_{B}=1\ |\ x,y]$
$\displaystyle=\sum_{k}p_{k}\textnormal{Tr}\left[\mathcal{C}_{1}(\left|x\right\rangle\otimes\rho_{Q}^{k})\right]\textnormal{Tr}\left[\mathcal{C}_{1}(\left|y\right\rangle\otimes\rho^{{}^{\prime}k}_{Q})\right]\pm(8\delta+O(\delta^{-2c}))$
$\displaystyle\stackrel{{\scriptstyle(1)}}{{=}}\sum_{k}p_{k}\textnormal{Tr}\left[\left|\phi^{+}\right\rangle\left\langle\phi^{+}\right|(\tau_{x}\otimes\rho_{Q}^{k})\right]\textnormal{Tr}\left[\left|\phi^{+}\right\rangle\left\langle\phi^{+}\right|(\omega_{y}\otimes\rho_{Q}^{{}^{\prime}k})\right]\pm
O(\delta^{-2c})$
$\displaystyle\stackrel{{\scriptstyle(2)}}{{=}}\sum_{k}p_{k}\textnormal{Tr}\left[\mathcal{A}_{1}^{k}\tau_{x}\right]\textnormal{Tr}\left[\mathcal{B}_{1}^{k}\omega_{y}\right]\pm
O(\delta^{-2c})$
$\displaystyle=\sum_{k}p_{k}\textnormal{Tr}\left[\left(\mathcal{A}_{1}^{k}\otimes\mathcal{B}_{1}^{k}\right)(\tau_{x}\otimes\omega_{y})\right]\pm
O(\delta^{-2c}),$ (28)

where in (1) we used the definition of $\mathcal{C}$ and in (2) we denoted by
$\mathcal{A}^{k}$ and $\mathcal{B}^{k}$ the effective POVMs acting on
$\tau_{x}$ and $\omega_{y}$ respectively. Again, crucially, the same
$\mathcal{A}^{k}$ ($\mathcal{B}^{k}$) can be taken for all $x$ ($y$) because
the same was true for $\rho_{Q}^{k}$ ($\rho_{Q}^{{}^{\prime}k}$). With (28) we
can express the score function

$\displaystyle I$ $\displaystyle=\sum_{x,y\in\\{0,1\\}^{3}}\beta_{x,y}\
\mathbb{P}[b_{A}=1,b_{B}=1\ |\ x,y]$ $\displaystyle\geq\sum_{x,y}\beta_{x,y}\
\sum_{k}p_{k}\textnormal{Tr}\left[\left(\mathcal{A}_{1}^{k}\otimes\mathcal{B}_{1}^{k}\right)(\tau_{x}\otimes\omega_{y})\right]-\max_{x,y}|\beta_{x,y}|\cdot
O(\delta^{-2c})$
$\displaystyle\stackrel{{\scriptstyle(1)}}{{\geq}}\sum_{k}p_{k}\
\textnormal{Tr}[(\mathcal{A}_{1}^{k}\otimes\mathcal{B}_{1}^{k})W^{\top}]-\eta/2$
$\displaystyle\geq\sum_{k}p_{k}\
\textnormal{Tr}\left[W\left[(\mathcal{A}_{1}^{k})^{\top}\otimes(\mathcal{B}_{1}^{k})^{\top}\right]\right]-\eta/2,$
(29)

where in (1) we used that $\delta$ is sufficiently small, as per Definition 2
the upper bound on $\delta$ can be chosen after $W$ was picked. Because of
(29), (22) and the fact that
$(\mathcal{A}_{1}^{k})^{\top},(\mathcal{B}_{1}^{k})^{\top}$ are positive,
Hermitian, we have that $I\geq\eta-\eta/2\geq\eta/2$. We conclude the proof by
a standard application of the Chernoff bound to argue that with probability
$1-\delta$ we have $\hat{I}>0$. This gives a contradiction with the assumption
that $\mathbf{V}$ accepted the interaction with probability $1-2\delta$.

This proves that in fact if $\mathfrak{P}$ is complete and sound against all
$\BQP$ cheating provers, every entangled state is $\mathtt{NeL}$. Now a direct
application of theorem 1 implies that if such $\mathfrak{P}$ exists
$\BQP\neq\PostBQP$.

∎

##  Appendix C Generalization of Theorem 1

In our proof of Theorem 1 we effectively take any two circuits
$C^{\mathbf{A}}$ and $C^{\mathbf{B}}$ and some state $\rho_{AB}$ and simulate
the statistics generated by them in mode (i) with two $\PostBQP$ circuits of
size $\poly(|C^{\mathbf{A}}|)$ and $\poly(|C^{\mathbf{B}}|)$, where $|\cdot|$
denotes the size of the circuit, i.e. number of gates plus the number of
qubits on which the circuit operates. This means that we can show a more
general result.

What does more general mean? Even when one agrees with the quantum Church-
Turing hypothesis, the choice of the $\BQP$ class in the completeness part of
Definition 2 is somewhat arbitrary. In the following, we define nonlocality
slightly differently. Honest $\mathbf{A},\mathbf{B}$ still apply some quantum
circuit on their input and their share of $\rho_{AB}$ but their circuits are
no longer limited to be of polynomial size with respect to the question size,
i.e. polynomial in $n$. Next, we say that a game is sound if no cheating
provers with polynomially bigger circuits can fool the verifier. Where the
parameter is now the size of the honest circuit. To summarize, we still assume
the quantum Church-Turing hypothesis but we don’t impose any restrictions on
the sizes of honest circuits. More formally

######  Definition 6.

(not-efficiently-local) For a state
$\rho_{AB}\in\mathcal{S}(\mathcal{H}_{A}\otimes\mathcal{H}_{B})$ we say that
$\rho_{AB}$ is not-efficiently-local if for every sufficiently small $\delta$
there exists $k\in\mathbb{N}$, game $\mathcal{G}(\rho_{AB},k,\cdot)$ and
provers $\mathbf{A}_{\text{honest}}(\cdot),\mathbf{B}_{\text{honest}}(\cdot)$
such that for every polynomial $p(\cdot)$ there exists a polynomial $q(\cdot)$
such that for every $n\in\mathbb{N}$

  1. 1.

(Completeness) If $\mathcal{G}(\rho_{AB},k,n)$ was run in mode (i) with
$\mathbf{A}_{\text{honest}}(n),\mathbf{B}_{\text{honest}}(n)$ then

$\mathbb{P}[\mathbf{V}\text{ accepts}]\geq 1-\delta.$

  2. 2.

(Soundness) For every $\mathbf{A},\mathbf{B}$ such that $|\mathbf{A}|\leq
p(|\mathbf{A}_{\text{honest}}(n)|),|\mathbf{B}|\leq
p(|\mathbf{B}_{\text{honest}}(n)|)$ if $\mathcal{G}(\rho_{AB},k,n)$ was run in
mode (ii) with $\mathbf{A},\mathbf{B}$ then

$\mathbb{P}[\mathbf{V}\text{ accepts}]\leq 1-\delta-\frac{1}{q(n)}.$

With this new definition, our proof directly implies that

$\mathtt{ENT}=\mathtt{NeL}\implies\BQP\neq\PostBQP,$

where the $\mathtt{NeL}$ is understood as in Definition 6.