# On Basing One-way Permutations on NP-hard Problems under Quantum Reductions

Nai-Hui Chia  Department of Computer Science and Engineering, The Pennsylvania
State University, University Park, PA, 16802, USA.  Sean Hallgren Partially
supported by National Science Foundation awards CNS-1617802 and CCF-1618287,
and by the National Security Agency (NSA) under Army Research Office (ARO)
contract number W911NF-12-1-0541. Department of Computer Science and
Engineering, The Pennsylvania State University, University Park, PA, 16802,
USA.  Fang Song  Computer Science Department, Portland State University,
Portland, OR, 97201, USA

###### Abstract

A fundamental pursuit in complexity theory concerns reducing worst-case
problems to average-case problems. There exist complexity classes such as
PSPACE that admit worst-case to average-case reductions. Many other classes
such as NP, however, the evidence so far is typically negative, in the sense
that the existence of such reductions would cause collapses of the polynomial
hierarchy. Basing cryptography, e.g., the average-case hardness of inverting
one-way permutations, on NP-completeness is a particularly intriguing
instance. We initiate a study of the quantum analogues of these questions and
show that if NP-complete problems reduce to inverting one-way permutations
using certain types of quantum reductions, then coNP $\subseteq$ QIP(2).

##  1 Introduction

A fundamental question in complexity theory is whether or not worst-case
problems have reductions to average-case problems. A special case, random-
self-reductions, concerns reducing worst-case problems to average-case
problems of the same type. Random-self-reductions exist for complete sets of
some classes such as PSPACE, EXP and #P. Such reductions are not known to
exist for NP-complete problems. Fortnow and Feigenbaum [FF93] showed that sets
which are complete for any level of the polynomial hierarchy are not (non-
adaptively) random-self-reducible unless the polynomial hierarchy collapses,
giving negative evidence for this possibility.

More broadly, one can ask when the worst-case instances of one problem can be
reduced to random instances of a different problem, including basing
cryptographic primitives on NP-complete problems. Namely, can we reduce NP-
complete problems to breaking the security of cryptosystems? It has been shown
that approximating several worst-case lattice problems reduce to average-case
lattice problems [Ajt96, Mic04, MR07]. Additionally, Regev [Reg04a, Reg05] and
Ajtai and Dwork [AD97] propose cryptosystems, where breaking these
cryptosystems on average is as hard as solving some worst-case lattice
problems. However, the worst-case lattice problems mentioned above are in
NP$\cap$coNP, which are believed not NP-complete.

The pursuit of basing cryptographic primitives on NP-hardness has largely
ended up negative. For instance, if one can reduce NP-complete problems to
inverting one-way permutations [Bra79], size-verifiable one-way functions
[AGGM06, BB15], single-server single-round private information retrieval
[LV15], or weak fully homomorphic evaluation of sensitive collection of
functions [BL13], then the polynomial hierarchy collapses. In this paper we
bring this question in the quantum computing paradigm: can cryptographic
primitives be based on NP-complete or QMA-complete problems if we allow
_quantum_ reductions?

Quantum reductions have been shown to be useful in cryptography. Regev
[Reg04b] showed that the unique shortest vector problem reduces to random
subset sum problems via a quantum reduction. In addition, GapSVP and SIVP
reduce to the learning with errors (LWE) problem via quantum reductions
[Reg05]. There are no known classical reductions between these problems under
the same parameters. Therefore, these are examples where quantum reductions
appear to be more powerful than classical reductions, when reducing from
worst-case to average-case problems. Kawachi and Yamakami [KY10] proved
several hard-core predicates using quantum reductions, inspired by earlier
work on the quantum Goldreich-Levin theorem [AC02] and the quantum algorithm
for the Legendre symbol [VDHI06].

We will consider the quantum analogues of two families of classical
reductions. The first is called a _locally random reduction_ [FF93]. In this
model, there are two classical algorithms $G$ and $R$, where the first
algorithm $G$ generates queries to the oracle for the average-case problem
according to a given distribution, and the second algorithm $R$ uses the
answers to solve the worst-case problem. Reductions between lattice problems
in [Ajt96, Mic04, MR07] are locally random reductions with queries generated
according to the uniform distribution. It is worth noting that the reduction
in [Reg05] also follows the definition of locally random reductions except
that $G$ and $R$ are quantum algorithms.

The other general type of reduction is the _worst-case to average-case
reduction_ defined by Bogdanov and Trevisan [BT06]. In this model there are
also two classical algorithms $G$ and $R$, one to generate queries and the
other to use the answers and solve the problem. However, in this model, $G$
can generate queries in an arbitrary way, but the oracle is allowed to answer
incorrectly on some predefined set of queries.

In this work, we first give two examples where quantum reductions from worst-
case to average-case problems exist but classical reductions do not. Then our
main contribution is showing that the existence of some quantum reductions
implies unknown consequences in complexity. We consider the quantum analogues
of locally random reductions and worst-case to average-case reductions. We
define locally quantum reductions to consist of two quantum circuits $G$ and
$R$. The unitary $G$ generates superposition queries for the oracle of the
average-case problem with the restriction that the coefficients of those
queries match a given distribution. The unitary $R$ solves the problem based
on the answers from the oracle. We then define quantum worst-case to average-
case reductions, also by two quantum circuits $G$ and $R$. The unitary $G$
generates arbitrary superposition queries for the average-case problem. The
unitary $R$ uses the results of the queries to solve the worst-case problem.
As in the classical case, this oracle may answer incorrectly on some
predefined set of queries. Both locally random reductions and worst-case to
average-case reductions are special cases of their quantum analogues. We
describe our main theorems informally:

######  Theorem 1.1.

The existence of locally quantum reductions where the queries are non-adaptive
and are according to smooth-computable distributions from an NP-complete
problem (or QMA-complete problem) to the task of inverting one-way
permutations implies coNP (or coQMA) $\subseteq$ QIP($2$).

A distribution $\mathcal{D}$ is smooth-computable if its maximum and minimum
are only polynomially larger and smaller than the average, and given any $x$,
the probability $\Pr_{x\sim\mathcal{D}}[x]$ can be computed efficiently. In
particular, this handles uniform distributions. Though, Theorem 1.1 requires
the given distribution to be smooth-computable, to the best of our knowledge,
known reductions from worst-case to average-case problems only use the uniform
distribution [FF93, Ajt96, Mic04, MR07, Reg05, Reg04a, AD97].

The containment coNP $\subseteq$ QIP($2$) is not as strong as the classical
result that the polynomial hierarchy collapses. However, it is an open problem
and thus a non-trivial consequence of the existence of these reductions. We
know very little about QIP($2$). So far, it is only known that QMA$\subseteq$
QIP($2$)$\subseteq$ QIP($3$)=PSPACE and there are only a few problems [Ros09,
HMW14, KLGN15] that are known to be in QIP(2) that are not known to be in AM
or QMA.

In order to describe the approach, we first describe the classical approach.
The classical proof strategy is to assume that a language $L$ has a random
reduction to some problem $L^{\prime}$, and then construct an interactive
proof for $\overline{L}$ that induces a collapse. For example, if $L$ is NP-
complete and has a random reduction to inverting a one-way permutation, then
there is a two round protocol for deciding if $x\in\overline{L}$. The verifier
runs the generator $G$ to generate the queries for the one-way permutation and
sends them to the prover. The prover then sends back the answers. Because the
verifier can evaluate the one-way permutation, the prover’s answers can be
checked, and then $R$ is run to decide if $x\in L$. Finally, the verifier can
give the opposite answer. This results in a two round protocol for
$\overline{L}$. Therefore if such a reduction exists, then coNP $\subseteq$
AM, giving a collapse. There are much more complicated constructions when
other average-case problems are considered, for example, for reducing worst-
case NP-complete problems to distributional NP problems. It is more difficult
to find an interactive proof in this case because if the prover answers
$y\not\in L^{\prime}$, then the verifier has no way to verify this.
Nevertheless, with classical non-adaptive reductions it is possible to
construct a protocol for $\overline{L}$ [BT06].

Carrying over the proof strategy to the quantum setting requires resolving
several difficulties. We use the unitaries $G$ and $R$ from the reduction to
construct a quantum interactive proof for $\overline{L}$. First the unitary
$G$ is used to create superposition queries which are sent to the prover. An
honest prover will answer the superposition queries for the average-case
language and send the states back. The verifier can then use the unitary $R$
to decide whether to accept or reject. The first difficultly that arises in
following this approach is that superposition queries are being used, which
makes it harder to verify that the prover is not cheating than it is for
classical answers. Another limiting factor also immediately arises in the
quantum case that does not exist in the classical case. For classical
reductions and protocols, it is fine to create a protocol with many (but still
constant) rounds of communication, because there is an equivalent two round
protocol. This is done in [BT06] where upper and lower bound protocols are
used to bound the sizes of sets. However, in the quantum case, we are limited
to finding quantum interactive proofs with only two rounds to begin with,
since QIP($m$) = QIP(3) = PSPACE. Finding a quantum protocol that is limited
even to three rounds would only allow the conclusion that coNP $\subseteq$
QIP($m$) = PSPACE, which does not yield a non-trivial result.

The main technical challenge is to ensure that the prover provides the answers
honestly in superposition to the average-case problem. A cheating prover would
try to return some other state that makes the unitary $R$ answer in the
opposite way than it should. Should the prover return such a state, the
verifier must be able to detect this. Our approach is to let the verifier
create a superposition of two states: the query state that is needed for the
reduction, and a trap state with the property that it can be used to detect
that the prover is cheating. We show that there is a trap state so that
whenever the prover changes the query part of the superposition, then the trap
part of the superposition must also change, and that this can be detected by
the verifier.

Our work also provides another example of a QIP(2) protocol, which differs
from the way previous QIP($2$) protocols are designed. Compared to QIP($3$)
$=$ PSPACE and QIP(1) $=$ QMA, less is known about the power of QIP($2$).
There is a complete problem for QIP($2$), called the close image problem
[KW00, Ros09]. This problem resembles the acceptance condition for the
verifier in a quantum interactive proof system [Ros09, KW00]. There are two
QIP(2) protocols for other problems. The first is for testing the separability
of a bipartite state generated by a quantum circuit [HMW14]. The second
studies a generalized version of public coins to the quantum setting, where
instead of coins, EPR pairs are used [KLGN15]. The definitions of the problems
in [HMW14, KLGN15] ask whether the output of a given quantum circuit is close
to the totally mixed state [KLGN15] or close to any separable state [HMW14].
These definitions give a way to build QIP($2$) protocols by applying Ulhmann’s
theorem. Due to the way our problem is defined, one cannot build a QIP($2$)
protocol by directly following Ulhmann’s theorem.

The definitions of the problems in [HMW14, KLGN15] ask whether the output of a
given quantum circuit is close to the totally mixed state [KLGN15] or close

There are several open questions. Do adaptive and/or non-smooth-computable
quantum reductions from NP-complete problems to inverting one-way permutations
exist? For cryptographic primitives which security are not based on NP-
complete problems under classical reductions, can NP-complete problems reduce
to them if quantum reductions are allowed? Is it possible to rule out a
quantum reduction from NP-complete problems to average-case problems in NP?
Since we know very little about QIP($2$), can we show that QIP($2$) $\neq$
QMA, QIP($2$) $\neq$ AM, or coNP$\nsubseteq$ QIP($2$)?

##  2 Preliminaries

For a finite set $X$, $\left\lvert X\right\rvert$ denotes the size of $X$. We
use $x\leftarrow X$ to mean that $x$ is drawn uniformly at random from $X$.
$\operatorname{poly}(\cdot)$ denotes an unspecified polynomial, and
$\operatorname{negl}(n)$ denotes a negligible function in $n$. A function
$\epsilon(n)$ is _negligible_ if for all polynomials $p(n)$,
$\epsilon(n)<1/p(n)$ for large enough $n$. Classical efficient computation is
described by probabilistic polynomial time (PPT) algorithms.

We assume basic familiarity with quantum information formalism. In this paper,
_quantum register_ represents a collection of qubits that we view as a single
unit. We typically use capital letters to denote a register and the Hilbert
space associated with it. A quantum channel $\Phi$ describes any physically
admissible transformation of quantum states, which is mathematically a
completely positive, trace-preserving linear map.

We recall the definitions of _quantum interactive proofs_ (QIP) and _one-way
permutations_.

######  Definition 2.1 (QIP($m$)).

A promise problem $A=(A_{yes},A_{no})$ is in the complexity class QIP($m$) if
there exists a polynomial-time quantum verifier which exchanges quantum
messages with a prover and has the properties:

  * •

(Completeness) For $x\in A_{yes}$, there exists a prover who can convince the
verifier to accept $x$ with probability at least $2/3$ by exchanging at most
$m$ messages.

  * •

(Soundness) For $x\in A_{no}$, no prover can convince the verifier with
probability greater than $1/3$ by exchanging at most $m$ messages.

The length of the messages exchanged between the verifier and the prover are
$O(\operatorname{poly}(|x|))$.

Without loss of generality, the behaviors of the prover and the verifier can
always be described as unitaries. It has been shown that
QIP($m$)=QIP($3$)=PSPACE for $m>3$ [KW00, JJUW11]. In this work, we focus on
the class QIP($2$). It is known that completeness and soundness can be reduced
to negligibly small [JUW09].

######  Definition 2.2 (One-way permutation).

$f:\\{0,1\\}^{*}\rightarrow\\{0,1\\}^{*}$ is a one-way permutation if

  * •

for every $n$, $f$ is a polynomial-time computable permutation over
$\\{0,1\\}^{n}$ by either quantum or classical algorithms, and

  * •

for every quantum polynomial-time algorithm $A$,
$\Pr_{x\leftarrow\\{0,1\\}^{n}}(A(f(x))=x)=\operatorname{negl}(n)$.

We denote the task of inverting a one-way permutation as Inv-OWP.

###  2.1 Locally random reductions and worst-case to average-case reductions

We review classical definitions of worst-case to average-case reductions. The
basic notion is a _distributional_ problem. We denote $\mathcal{P}^{\prime}$
an arbitrary decision problem, search problem or promise problem. We will only
consider the case where $\mathcal{P}^{\prime}$ corresponds to inverting one-
way permutations.

######  Definition 2.3.

Let $\mathcal{P}^{\prime}$ be a problem and $\mathcal{D}$ a collection of
distributions $\\{\mathcal{D}_{n}\\}_{n\in\mathbb{N}}$. The distributional
problem $(\mathcal{P}^{\prime},\mathcal{D})$ is: given an instance $x$ chosen
randomly according to $\mathcal{D}_{n}$, compute $\mathcal{P}^{\prime}(x)$.

We first adapt a notion of Feigenbaum and Fortnow [FF93].

######  Definition 2.4 (non-adaptive locally random reduction $(G,R)$ ).

Let $k$ and $\ell$ be variables polynomial in the input length $n$ and let
$r\leftarrow\\{0,1\\}^{\ell}$. A decision problem $\mathcal{P}$ is non-
adaptively locally random reducible to a distributional problem
$(\mathcal{P}^{\prime},\mathcal{D})$ if there are polynomial-time algorithms
$R$ and $G$ satisfying:

  * •

For all $n$ and $x\in\\{0,1\\}^{n}$,
$\mathcal{P}(x)=R(x,r,\mathcal{P}^{\prime}(G(1,x,r)),\dots,\mathcal{P}^{\prime}(G(k,x,r)))$
for at least $3/4$ of all $r\in\\{0,1\\}^{\ell}$.

  * •

For $1\leq i\leq k$, if $x_{1}\neq x_{2}$ and $|x_{1}|=|x_{2}|$ then
$\Pr_{r}[G(i,x_{1},r)=y]=\Pr_{r}[G(i,x_{2},r)=y]=\Pr[y\sim\mathcal{D}_{|x_{1}|}]$.

We note that Definition 2.4 is equivalent to the Definition 2.1 in [FF93]. In
Definition 2.4, we assume that all queries are drawn from the same
distribution instead of different distributions. However, the assumption can
be made without loss of generality since one can apply a random permutation to
the queries before sending them to the oracle and undo the permutation before
applying $R$. This way, the distributions of each query are the same.

If we only consider $\mathcal{D}$ to be the uniform distribution, then this
reduction is a special case considered by Feigenbaum et al. in [FKN90]. One
can also define _adaptive_ locally random reductions by allowing the algorithm
$G$ in Definition 2.4 to generate queries depending on the previous queries
and answers.

If $\mathcal{P}=\mathcal{P^{\prime}}$, then the reduction is also called a
random-self reduction [FF93]. It has been shown that the set of complete
problems in PSPACE, EXP and #P are random-self reducible [FF93]. On the other
hand, it has been shown that NP-complete problems are not non-adaptive random-
self reducible unless the polynomial hierarchy collapses to the third level
[FF93].

The definition of Feigenbaum and Fortnow assumes a perfect solver for the
average-case problem. This restriction is weakened in a later work by Bogdanov
and Trevisan [BT06].

######  Definition 2.5 (non-adaptive worst-case to average-case reduction).

Let $k$ and $\ell$ be variables polynomial in the input length $n$, and $r$ is
a random string chosen uniformly at random from $\\{0,1\\}^{\ell}$. A decision
problem $\mathcal{P}$ is non-adaptive worst-case to average-case reducible to
$(\mathcal{P}^{\prime},\mathcal{D})$ with average hardness $\delta$ if there
are polynomial-time algorithms $R$ and $G$ satisfying the properties that: For
any $n\in\mathbb{N}$

  * •

On all inputs $x\in\\{0,1\\}^{n}$, $G(x,r)$ outputs $y_{1},\dots,y_{k}$.

  * •

For any $\mathcal{P}^{\prime\prime}$ which is $\delta$-close to
$\mathcal{P}^{\prime}$ with respect to $\mathcal{D}$,
$\Pr_{r}[R(x,r,\mathcal{P}^{\prime\prime}(y_{1}),\dots,\mathcal{P}^{\prime\prime}(y_{k}))=\mathcal{P}(x)]>2/3.$

Similarly, an adaptive worst-case to average-case reduction is defined by
including previous queries and answers to the arguments of $G$.

It has been shown that NP-complete problems are not non-adaptive worst-case to
average-case reducible to themselves, unless the polynomial hierarchy
collapses to the third level [BT06]. In addition, the existence of a non-
adaptive worst-case to average-case reduction from NP-hard problem to
inverting a one-way function implies that the polynomial hierarchy collapses
to the second level [AGGM06] and the existence of a worst-case to average-case
reduction from an NP-hard problem to inverting a size verifiable one-way
function implies that the polynomial hierarchy collapses to the second level
[AGGM06, BB15].

##  3 Locally quantum reductions and quantum worst-case to average-case
reductions

In this section we define the quantum analogues of non-adaptive locally random
reductions given in Definition 2.4 and non-adaptive worst-case to average-case
reductions given in Definition 2.5, which are introduced in Section 2.1.

######  Definition 3.1 (non-adaptive locally quantum reduction $(G,R)$).

A decision problem $\mathcal{P}$ is non-adaptive locally quantum reducible to
a distributional problem $(\mathcal{P}^{\prime},\mathcal{D})$ if there are two
polynomial-time implementable unitaries $R$ and $G$ such that for all $n$ and
$x\in\\{0,1\\}^{n}$

  * •

The generator $G$ creates $k$ superposition queries, with query amplitudes
based on the distribution $\mathcal{D}$:
$G|0\rangle_{MV}|x\rangle=|Q_{x,1}\rangle\otimes\cdots\otimes|Q_{x,k}\rangle|x\rangle$
where
$|Q_{x,i}\rangle=\sum_{q\in{\mathbb{Z}_{2}^{m}}}\sqrt{d_{q}}|q,0\rangle_{M}|w_{x,i}(q)\rangle_{V}$
for $i\in[k]$ and $d_{q}$ is the probability that $q$ is drawn from
$\mathcal{D}_{n}$

  * •

$R$ takes responses of the queries and decides whether or not $\mathcal{P}(x)$
is true:

$\displaystyle
R|Q_{x,1}^{H},\dots,Q_{x,k}^{H}\rangle=\sqrt{p}|\mathcal{P}(x)\rangle|\psi_{x}^{0}\rangle+\sqrt{1-p}|1-\mathcal{P}(x)\rangle|\psi_{x}^{1}\rangle$

where $p\geq 2/3$ and
$|Q_{x,i}^{H}\rangle=\sum_{q\in{\mathbb{Z}_{2}^{m}}}\sqrt{d_{q}}|q,\mathcal{P}^{\prime}(q)\rangle_{M}|w_{x,i}(q)\rangle_{V}$,
for $i\in[k]$.

We introduce $\delta$-close problems to define the generalized notion of
worst-case to average-case reduction.

######  Definition 3.2.

A problem $\mathcal{P}^{\prime\prime}$ is $\delta$-close to another problem
$\mathcal{P}^{\prime}$ with respect to $\mathcal{D}$ if for all $n$,
$\Pr_{x\sim\mathcal{D}_{n}}(\mathcal{P}^{\prime\prime}(x)\neq\mathcal{P}^{\prime}(x))<\delta$.

######  Definition 3.3 (non-adaptive quantum worst-case to average-case
reduction).

A decision problem $\mathcal{P}$ is non-adaptive quantum worst-case to
average-case reducible to $(\mathcal{P}^{\prime},\mathcal{D})$ with average
hardness $\delta$ if there are polynomial-time computable unitaries $R$ and
$G$ such that for any $n\in\mathbb{N}$ and $x$

  * •

The generator $G$ creates $k$ superposition queries:

$\displaystyle
G|0\rangle_{MV}|x\rangle=|Q_{x,1}\rangle\otimes\cdots\otimes|Q_{x,k}\rangle|x\rangle,$
(1)

where
$|Q_{x,i}\rangle=\sum_{q\in{\mathbb{Z}_{2}^{m}}}c_{x,q,i}|q,0\rangle_{M}|w_{x,i}(q)\rangle_{V},\quad\text{for
}i\in[k]$.

  * •

$R$: for any $\mathcal{P}^{\prime\prime}$ which is $\delta$-close to
$\mathcal{P}$ with respect to $\mathcal{D}$,

$\displaystyle
R|Q_{x,1}^{H},\dots,Q_{x,k}^{H}\rangle=\sqrt{p}|\mathcal{P}(x)\rangle|\psi_{x}^{0}\rangle+\sqrt{1-p}|1-\mathcal{P}(x)\rangle|\psi_{x}^{1}\rangle,$
(2)

where $p\geq 2/3$ and
$|Q_{x,i}^{H}\rangle=\sum_{q\in{\mathbb{Z}_{2}^{m}}}c_{x,q,i}|q,\mathcal{P}^{\prime\prime}(q)\rangle_{M}|w_{x,i}(q)\rangle_{V}$,
for $i\in[k]$.

The variables $m$ and $k$ are polynomial in the input length $n$.

Compared to locally quantum reductions, quantum worst-case to average-case
reductions do not require the queries to be drawn from a certain distribution.
Instead, we consider an oracle for $\mathcal{P}^{\prime}$ that can err
sometimes, which is captured by $\delta$-close problems
$\mathcal{P}^{\prime\prime}$.

$1-p$ is called the error of the reduction. The choice of $p=2/3$ is
arbitrary, since it can be reduced effectively.

###  3.1 Discussion of the definitions: special cases

Classical queries. If $G$ outputs classical queries, then we can already
derive a negative result, analogous to a classical result by Brassard [Bra79].

######  Theorem 3.4.

If there is a non-adaptive quantum reduction $L\leq_{R,G}\textsf{Inv-OWP}$
where $G$ produces classical queries, then $L\in$ QIP$(2)$ with classical
interactions.

###### Proof.

The protocol is as follows: The verifier first applies $G$ to generate queries
and sends these queries to the prover. Then, the prover simulates the oracle
for Inv-OWP and sends the responses back. Finally, the verifier checks if the
responses are correct by computing the permutation. If the prover is not
cheating, the verifier applies $R$ and accepts if $R$ accepts. Otherwise, the
verifier rejects. Note that the prover can only give the correct answer for
Inv-OWP. Otherwise, the verifier rejects. ∎

The proof for Theorem 3.4 above is similar to the proof in [Bra79] except that
the verifier who applies quantum reduction needs to send the queries by
itself. The reason is that the randomness of a quantum circuit is from the
nature of quantum mechanism. So, the verifier cannot make its randomness to be
public. In addition, we do not know if the theorem above is correct when the
quantum reduction is adaptive.

EPR queries. As another special case, we consider that $w_{x,i}(q)$ is the
identity function in Definition 3.1. Namely $G$ generates $k$ identical copies
of $|\Psi\rangle^{\otimes m}=\sum_{q}|q\rangle|q\rangle$, where
$\Psi=\frac{1}{\sqrt{2}}(|00\rangle+|11\rangle)$ is an EPR-pair. Then half of
the EPR-pairs are submitted as queries to the solver of the average-case
problem. Note the reduced density of each query is totally mixed, and this
looks a natural generalization of classical uniform queries. Nonetheless, we
show that this is too strong a constraint that trivializes the study of worst-
to-average reductions, as far as OWP is concerned.

######  Proposition 3.5.

If there is a reduction $L\leq_{R,G}\textsf{Inv-OWP}$ where $G$ issues EPR-
queries, then $L\in$ BQP.

###### Proof.

The key (and simple) observation is that a uniform superposition over a set is
_invariant_ under an arbitrary permutation. This means that a quantum
reduction could create the correct state that otherwise would require invoking
an inverting oracle $I$ of the OWP $f$. Namely applying $I$ on an EPR query
gives us

$\displaystyle\sum_{q}|q,q\rangle\overset{I}{\mapsto}\sum_{q}|q,q,f^{-1}(q)\rangle\,.$

This can be created without help of $I$ as follows:

$|0,0,0\rangle\mapsto\sum_{q}|q,0,0\rangle\overset{f}{\mapsto}\sum_{q}|q,f(q),f(q)\rangle=\sum_{q^{\prime}}|f^{-1}(q^{\prime}),q^{\prime},q^{\prime}\rangle\overset{\mathrm{SWAP}_{1,3}}{\mapsto}\sum_{q^{\prime}}|q^{\prime},q^{\prime},f^{-1}(q^{\prime})\rangle\,.$

∎

######  Remark 1.

Consequently, it is _necessary_ that the query states maintain more
sophisticated correlations between the query register and the work register of
the reduction. We note the same phenomenon also occur classically. Namely,
although the marginal distribution of each query is _uniformly_ random, it is
important that the internal state of the reduction should not be independent
of the queries. Otherwise, existence of such a reduction will trivialize the
language under consideration to fall in BPP.

##  4 Uniform one-query locally quantum reduction to Inv-OWP

In this section we consider quantum reductions that make _one-query_ only. It
demonstrates the main idea of our general result with a cleaner analysis.
Section 5 will handle multiple non-adaptive queries. Let $f$ be a one-way
permutation on $\left\\{0,1\right\\}^{n}$, and let $U_{f}$ be a unitary
quantum circuit computing it. That is, $U_{f}|x,0\rangle=|x,f(x)\rangle$. Note
that $U_{f}|f^{-1}(x),0\rangle=|f^{-1}(x),x\rangle$. A uniform one-query
locally quantum reduction for $L$ works as follows:

$\displaystyle|x,0\rangle|0\rangle$ $\displaystyle\stackrel{{\scriptstyle
G}}{{\longrightarrow}}$
$\displaystyle\frac{1}{\sqrt{2^{m}}}\sum_{q\in\mathbb{Z}_{2}^{m}}|q,0\rangle|w_{x}(q)\rangle$
(3) $\displaystyle\overset{O_{f^{-1}}}{\longrightarrow}$
$\displaystyle\frac{1}{\sqrt{2^{m}}}\sum_{q\in\mathbb{Z}_{2}^{m}}|q,f^{-1}(q)\rangle|w_{x}(q)\rangle\stackrel{{\scriptstyle
R}}{{\longrightarrow}}a_{0}|0\rangle|\psi_{x,0}\rangle+a_{1}|1\rangle|\psi_{x,1}\rangle,$
(4)

where $|a_{1}|^{2}\geq 1-\epsilon$ if $x\in L$ and $|a_{1}|^{2}\leq\epsilon$
if $x\notin L$ is the probability the reduction accepts.

The main theorem we are going to prove in this section is

######  Theorem 4.1.

Suppose there exists a one-query uniform locally quantum reduction with
exponentially small error $\epsilon$ from a worst-case decision problem $L$ to
the task of inverting a polynomial-time computable permutation. Then there
exists a $QIP($2$)$ protocol with completeness $1-\epsilon/2$ and soundness
$1/2+2\sqrt{\epsilon}$ for $\overline{L}$

To prove Theorem 4.1, we are going to give a QIP($2$) protocol for
$\overline{L}$ by using the reduction.

###  4.1 The protocol for $\overline{L}$

We are given the uniform one-query locally quantum reduction $(G,R)$. We
enlarge the size of register $V$ and define a unitary $C$ which performs a
CNOT on the first register of $M$ into the second register of $V$:
$|q,x\rangle_{M}|y,z\rangle_{V}\stackrel{{\scriptstyle
C}}{{\longrightarrow}}|q,x\rangle_{M}|y,z\oplus q\rangle_{V}$. The whole
protocol takes place in the space
$\mathcal{H}_{P}\otimes\mathcal{H}_{M}\otimes\mathcal{H}_{V}\otimes\mathcal{H}_{\Pi}$
where $P$ is the private register of the prover, $M$ is the register exchanged
between the prover and the verifier, $V$ and $\Pi$ are registers which are
private to the verifier.

We describe some states that are crucial in the protocol.

  * •

The verifier prepares the state
$|S\rangle_{MV\Pi}=\frac{1}{\sqrt{2}}(|Q\rangle_{MV}|0\rangle_{\Pi}+|T\rangle_{MV}|1\rangle_{\Pi})$,
where

$\displaystyle|Q\rangle_{MV}=\frac{1}{\sqrt{2^{n}}}\sum_{q\in\mathbb{Z}_{2}^{m}}|q,0\rangle_{M}|w_{x}(q),q\rangle_{V}$
(5)

without the extra copy of $q$ in the register $V$ is the query state generated
from $G$ as in Equation 3, and

$\displaystyle|T\rangle_{MV}=\frac{1}{\sqrt{2^{n}}}\sum_{q\in\mathbb{Z}_{2}^{m}}|q,0\rangle_{M}|0,q\rangle_{V}$
(6)

is the trap state, which will be used to catch a cheating prover.

  * •

The honest prover replies
$|S^{H}\rangle_{MV\Pi}=\frac{1}{\sqrt{2}}(|Q^{H}\rangle_{MV}|0\rangle_{\Pi}+|T^{H}\rangle_{MV}|1\rangle_{\Pi})$,
where

$\displaystyle|Q^{H}\rangle_{MV}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2^{n}}}\sum_{q\in\mathbb{Z}_{2}^{m}}|q,f^{-1}(q)\rangle_{M}|w_{x}(q),q\rangle_{V}$
(7) $\displaystyle|T^{H}\rangle_{MV}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2^{n}}}\sum_{q\in\mathbb{Z}_{2}^{m}}|q,f^{-1}(q)\rangle_{M}|0,q\rangle_{V}.$
(8)

The state $|Q^{H}\rangle$ without the extra copy of $q$ in register $V$ is the
state the actual reduction $R$ gets after querying the oracle as in Equation
4. The state $|T^{H}\rangle$ can be mapped to $|0\rangle_{MV}$ efficiently as
shown below. This gives the verifier an efficient way to check if
$|T^{H}\rangle$ is changed significantly.

We do the following to map $|T^{H}\rangle_{MV}$ back to $|0\rangle_{MV}$
efficiently

$\displaystyle\sum_{q\in\mathbb{Z}_{2}^{m}}|q,f^{-1}(q)\rangle_{M}|0,q\rangle_{V}$
$\displaystyle\xrightarrow{C}$
$\displaystyle\sum_{q}|q,f^{-1}(q)\rangle_{M}|0,q\oplus q\rangle_{V}$
$\displaystyle\xrightarrow{U_{f}}$ $\displaystyle\sum_{q}|q\oplus
f(f^{-1}(q)),f^{-1}(q)\rangle_{M}|0,0\rangle_{V}\xrightarrow{F}|0,0\rangle_{M}|0,0\rangle_{V}.$

Here $U_{f}$ is applied from the second register of $M$ into the first, and
$F$ is applied to the second register of $M$. The last two steps use the
property that $f$ can be evaluated efficiently and $f$ is a permutation.

Given the reduction $(G,R)$, we can get a QIP($2$) protocol for $L$ by
answering the same as $R$ and a protocol for $\overline{L}$ by flipping $R$’s
answer. The QIP($2$) protocol for $\overline{L}$ is described in Protocol 1.

The protocol takes place in the space
$\mathcal{H}_{P}\otimes\mathcal{H}_{M}\otimes\mathcal{H}_{V}\otimes\mathcal{H}_{\Pi}$
where $P$ is the private register of the prover, $M$ is the register exchanged
between the prover and the verifier, and $V$ and $\Pi$ are registers which are
private to the verifier. 1. _The verifier’s query._ The verifier prepares
$|S\rangle_{MV\Pi}:=\frac{1}{\sqrt{2}}(|Q\rangle_{MV}|0\rangle_{\Pi}+|T\rangle_{MV}|1\rangle_{\Pi}).$
The message register $M$ is sent to the prover, and the verifier keeps $V$ and
$\Pi$. This is generated by conditioning on the register $\Pi$, which is
initialized in $|+\rangle$. If $\Pi=0$, $G$ is applied and then $q$ is copied
to the second part of the verifier’s internal register $V$, which produces
$|Q\rangle_{MV}$. If $\Pi=1$, compute the Fourier transform followed by CNOT
to create $|T\rangle_{MV}$, a trap state we use to catch a cheating prover. 2.
_The prover’s response._ The prover applies some unitary $U_{PM}$ on register
$M$ and its private register $P$ and sends the message register back to the
verifier. 3. _The verifier’s verification._ The verifier applies $C$ to erase
$q$ in $V$. The verifier then measures $\Pi$ to obtain $b\in\\{0,1\\}$, and
does the following: • (Computation verification) If $b=0$, apply $R$ on $MV$
and measure the output qubit. Accept if the outcome is $0$. • (Trap
verification) If $b=1$, apply $V_{T}$ on $MV$ and measure $MV$. Accept if the
outcome is all $0$, (i.e., if the reduction rejects). Protocol 1 QIP(2)
protocol for $\overline{L}$ using a one-query locally quantum reduction.

###  4.2 Lemmas for proving Theorem 4.1

In this section, we prove Lemma 4.2, Lemma 4.4 and Claim 4.3, which we use to
prove Theorem 4.1.

Lemma 4.2 is an immediate consequence of the fact two purifications of the
same state are related by an isometry. In fact, this exactly explains why the
entanglement fidelity is well defined [Sch96].

######  Lemma 4.2.

Let $\rho_{A}$ be a state in some Hilbert space. Let $|\phi\rangle_{AB}$ and
$|\psi\rangle_{AB}$ be two purifications of $\rho_{A}$, i.e.,
$\operatorname{Tr}_{B}(|\phi\rangle\langle\phi|_{AB})=\operatorname{Tr}_{B}(|\psi\rangle\langle\psi|_{AB})=\rho_{A}$.
Let $\Psi_{A}:\mathcal{H}_{A}\rightarrow\mathcal{H}_{A}$ be a quantum channel.
Let $\rho_{AB}:=(\Psi_{A}\otimes I_{B})(|\phi\rangle\langle\phi|_{AB})$ and
$\sigma_{AB}:=(\Psi_{A}\otimes I_{B})(|\psi\rangle\langle\psi|_{AB})$, where
the notation $\Psi_{A}\otimes I_{B}$ means that the channel is only applied on
the space $\mathcal{H}_{A}$ and space $\mathcal{H}_{B}$ is not changed. Then
$\langle\phi|\rho_{AB}|\phi\rangle=\langle\psi|\sigma_{AB}|\psi\rangle$.

###### Proof.

Observe that (e.g., by Schmidt decomposition) there is a unitary $U_{B}$
operating only on $B$ such that $I_{A}\otimes
U_{B}|\psi\rangle_{AB}=|\phi\rangle_{AB}$. Then

$\displaystyle\langle\phi|\rho_{AB}|\phi\rangle$ (9) $\displaystyle=$
$\displaystyle\langle\phi|(\Psi_{A}\otimes
I_{B})((|\phi\rangle\langle\phi|)_{AB})|\phi\rangle$ $\displaystyle=$
$\displaystyle\langle\psi|(I_{A}\otimes U_{B}^{\dagger})(\Psi_{A}\otimes
I_{B})(I_{A}\otimes U_{B}(|\psi\rangle\langle\psi|)_{AB}I_{A}\otimes
U_{B}^{\dagger})(I_{A}\otimes U_{B})|\psi\rangle$ $\displaystyle=$
$\displaystyle\sum_{\ell}\langle\psi|(I_{A}\otimes
U_{B}^{\dagger})(E_{A}^{\ell}\otimes I_{B})(I_{A}\otimes
U_{B}(|\psi\rangle\langle\psi|)_{AB}I_{A}\otimes
U_{B}^{\dagger})(E_{A}^{\ell\dagger}\otimes I_{B})(I_{A}\otimes
U_{B})|\psi\rangle$ $\displaystyle=$
$\displaystyle\sum_{\ell}\langle\psi|(E_{A}^{\ell}\otimes
I_{B})((|\psi\rangle\langle\psi|)_{AB})(E_{A}^{\ell\dagger}\otimes
I_{B})|\psi\rangle$ $\displaystyle=$
$\displaystyle\langle\psi|(\Psi_{A}\otimes
I_{B})((|\psi\rangle\langle\psi|)_{AB})|\psi\rangle$ $\displaystyle=$
$\displaystyle\langle\psi|\sigma_{AB}|\psi\rangle.$

The operators $\\{E_{A}^{\ell}\\}$ in Equation 9 are the operation elements of
the channel $\Psi_{A}$, where $(\Psi_{A}\otimes
I_{B})((|\phi\rangle\langle\phi|)_{AB})=\sum_{\ell}(E_{A}^{\ell}\otimes
I_{B})((|\phi\rangle\langle\phi|)_{AB})(E_{A}^{\ell\dagger}\otimes I_{B})$ and
$(\Psi_{A}\otimes
I_{B})((|\psi\rangle\langle\psi|)_{AB})=\sum_{\ell}(E_{A}^{\ell}\otimes
I_{B})((|\psi\rangle\langle\psi|)_{AB})(E_{A}^{\ell\dagger}\otimes I_{B})$.
Equation 4.2 is correct due to the property that $(A\otimes B)(C\otimes
D)=(AC)\otimes(BD)$. ∎

Without loss of generality, we can always represent the prover’s operator
$U_{PM}$ as $U^{\prime}_{PM}O_{f^{-1}}$ where $U^{\prime}_{PM}$ is an
arbitrary unitary the cheating prover may apply. Let

$\sigma^{U^{\prime}}_{Q}=\operatorname{Tr}_{P}(U^{\prime}_{PM}\otimes
I_{V}(|0\rangle\langle 0|\otimes|Q^{H}\rangle\langle
Q^{H}|)U^{\prime\dagger}_{PM}\otimes I_{V})$

and

$\sigma^{U^{\prime}}_{T}=\operatorname{Tr}_{P}(U^{\prime}_{PM}\otimes
I_{V}(|0\rangle\langle 0|\otimes|T^{H}\rangle\langle
T^{H}|)U^{\prime\dagger}_{PM}\otimes I_{V}).$

The following claim shows that for any unitaries the prover applies, the
change on $|T^{H}\rangle$ is as much as the change on $|Q^{H}\rangle$.

######  Claim 4.3.

For an arbitrary $U^{\prime}_{PM}$, let $|Q^{H}\rangle_{MV}$ and
$|T^{H}\rangle_{MV}$ be as defined in Equation 7 and Equation 8, and let
$\sigma^{U^{\prime}}_{Q}$ and $\sigma^{U^{\prime}}_{T}$ be as above. Then
$\langle Q^{H}|\sigma_{Q}^{U^{\prime}}|Q^{H}\rangle=\langle
T^{H}|\sigma_{T}^{U^{\prime}}|T^{H}\rangle$.

###### Proof.

We represent the prover’s behavior $U^{\prime}_{PM}$ on the state
$|Q^{H}\rangle$ and $|T^{H}\rangle$ as a noisy channel $\Psi_{M}^{U^{\prime}}$
operating on register $M$, which is formally defined as follows:

$\displaystyle\mbox{For all
}\rho\in\mathcal{H}_{P}\otimes\mathcal{H}_{M}\otimes\mathcal{H}_{V},\mbox{
}(\Psi_{M}^{U^{\prime}}\otimes
I_{V})(\rho):=\operatorname{Tr}_{P}((U^{\prime}_{PM}\otimes
I_{V})\rho(U^{\prime\dagger}_{PM}\otimes I_{V})).$

Therefore,

$(\Psi_{M}^{U^{\prime}}\otimes I_{V})(|Q^{H}\rangle\langle
Q^{H}|)=\sigma^{U^{\prime}}_{Q}$

and

$(\Psi_{M}^{U^{\prime}}\otimes I_{V})(|T^{H}\rangle\langle
T^{H}|)=\sigma^{U^{\prime}}_{T}.$

$|T^{H}\rangle$ and $|Q^{H}\rangle$ are actually two purifications of a mixed
state on register $M$ since $\operatorname{Tr}_{V}(|Q^{H}\rangle\langle
Q^{H}|)=\operatorname{Tr}_{V}(|T^{H}\rangle\langle T^{H}|)$, and by Lemma 4.2,
we can conclude that

$\langle Q^{H}|\sigma_{Q}^{U^{\prime}}|Q^{H}\rangle=\langle
T^{H}|\sigma_{T}^{U^{\prime}}|T^{H}\rangle.$

∎

Given a state $|\phi\rangle$ and a projector $\Pi_{S}$, Lemma 4.4 is shows
that the state $\rho$ which maximizes the quantity
$\operatorname{Tr}(\Pi_{S}\rho)+\langle\phi|\rho|\phi\rangle$ is the bijection
of $|\phi\rangle$ and its projection on $\Pi_{S}$.

######  Lemma 4.4.

Let $S\subseteq\mathcal{H}$ be a subspace and $\Pi_{S}$ be the projection
operator on $S$. Let $|\phi\rangle$ be a state such that
$\langle\phi|\Pi_{S}|\phi\rangle=\sin^{2}\theta$, for some
$\theta\in[0,\pi/2]$. Then for any density operator $\rho\in D(\mathcal{H})$,
$\operatorname{Tr}(\Pi_{S}\rho)+\langle\phi|\rho|\phi\rangle\leq
1+\sin\theta$.

###### Proof.

We first prove this lemma for any pure state $\rho=|\psi\rangle\langle\psi|$.
Let $\text{dim}(S)=k$. Let
$|v_{0}\rangle:=\frac{\Pi_{S}|\phi\rangle}{\|\Pi_{S}|\phi\rangle\|}$ and
$|v_{k}\rangle:=\frac{|\phi\rangle-|v_{0}\rangle}{\||\phi\rangle-|v_{0}\rangle\|}$.
Clearly, $|v_{k}\rangle\perp|v_{0}\rangle$, and
$|\phi\rangle=\sin\theta|v_{0}\rangle+\cos\theta|v_{k}\rangle$. Then we pick
$\\{|v_{1}\rangle,\ldots,|v_{k-1}\rangle\\}$ in $S$ such that
$\\{|v_{0}\rangle,\ldots,|v_{k-1}\rangle\\}$ form an orthonormal basis for
$S$. As a result, $\\{|v_{0}\rangle,\ldots,|v_{k}\rangle\\}$ will be an
orthonormal basis for $\tilde{S}:=\text{span}(S\cup|\phi\rangle)$. Consider
any $\rho=|\psi\rangle\langle\psi|$ with $|\psi\rangle\in\tilde{S}$. Then
$|\psi\rangle$ can be written as

$|\psi\rangle=\sum_{i=0}^{k}\alpha_{i}|v_{i}\rangle,\quad\sum_{i}|\alpha_{i}|^{2}=1\,.$
(11)

We have that

$\displaystyle\langle\phi|(|\psi\rangle\langle\psi|)|\phi\rangle$
$\displaystyle=$
$\displaystyle|\alpha_{0}\sin\theta+\alpha_{k}\cos\theta|^{2}=|\alpha_{0}|^{2}\sin^{2}\theta+|\alpha_{k}|^{2}\cos^{2}\theta+\sin\theta\cos\theta(\alpha_{0}\alpha^{*}_{k}+\alpha_{0}^{*}\alpha_{k})\,;$
$\displaystyle\operatorname{Tr}(\Pi_{S}|\psi\rangle\langle\psi|)$
$\displaystyle=$
$\displaystyle\sum_{i=0}^{k-1}|\alpha_{i}|^{2}=1-|\alpha_{k}|^{2}\,.$

Therefore

$\displaystyle\operatorname{Tr}(\Pi_{S}|\psi\rangle\langle\psi|)+\langle\phi|(|\psi\rangle\langle\psi|)|\phi\rangle$
$\displaystyle=$ $\displaystyle
1+\sin^{2}\theta|\alpha_{0}|^{2}+(\cos^{2}\theta-1)|\alpha_{k}|^{2}+\sin\theta\cos\theta(\alpha_{0}\alpha_{k}^{*}+\alpha_{0}^{*}\alpha_{k})$
$\displaystyle=$ $\displaystyle
1+\sin\theta\cdot\left(\sin\theta(|\alpha_{0}|^{2}-|\alpha_{k}|^{2})+\cos\theta(\alpha_{0}\alpha_{k}^{*}+\alpha_{0}^{*}\alpha_{k})\right)$
$\displaystyle\leq$ $\displaystyle
1+\sin\theta\cdot(\sin\theta(|\alpha_{0}|^{2}-|\alpha_{k}|^{2})+2\cos\theta(|\alpha_{0}||\alpha_{k}|)).$
(13)

Since the expression in Equation 13 is strictly increasing with $|\alpha_{0}|$
and independent to $|\alpha_{1}|,\dots|\alpha_{k-1}|$, we can suppose the
optimal $|\psi\rangle$ for Equation 4.2 is on the subspace spanned by
$|v_{0}\rangle$ and $|v_{k}\rangle$ without loss of generality. Thus we let
$|\alpha_{0}|=\cos\theta_{0}$ and $|\alpha_{k}|=\sin\theta_{0}$ and the upper
bound for Equation 13 as below

$\displaystyle
1+\sin\theta\cdot(\sin\theta(|\alpha_{0}|^{2}-|\alpha_{k}|^{2})+2\cos\theta(|\alpha_{0}||\alpha_{k}|))$
$\displaystyle=$ $\displaystyle
1+\sin\theta(\sin\theta(\cos^{2}\theta_{0}-\sin^{2}\theta_{0})+2\cos\theta\cos\theta_{0}\sin\theta_{0})$
$\displaystyle=$ $\displaystyle 1+\sin\theta(\sin\theta\cos
2\theta_{0}+\cos\theta\sin 2\theta_{0})$ $\displaystyle=$ $\displaystyle
1+\sin\theta(\sin(\theta+2\theta_{0}))$ $\displaystyle\leq$ $\displaystyle
1+\sin\theta.$

The maximum is achieved when $\theta_{0}=\frac{1}{2}(\pi/2-\theta)$, i.e.,
when $|\psi\rangle$ bisects $|\phi\rangle$ and $|v_{0}\rangle$.

For an arbitrary mixed state
$\rho:=\sum_{i}p_{i}|\psi_{i}\rangle\langle\psi_{i}|$ with $\sum_{i}p_{i}=1$,
$p_{i}\geq 0$.

$\operatorname{Tr}(\Pi_{S}\rho)+\langle\phi|\rho|\phi\rangle=\sum_{i}p_{i}\left(\operatorname{Tr}(\Pi_{S}|\psi_{i}\rangle\langle\psi_{i}|)+\langle\phi|(|\psi_{i}\rangle\langle\psi_{i}|\right)|\phi\rangle)\leq
1+\sin\theta\,.$

∎

###  4.3 Proof of Theorem 4.1

The intuition behind the soundness proof is that the two branches
(conditioning on register $\Pi$) of verifier’s verification are competing and
the prover cannot cheat one without also changing the other. When the input
$x\notin L$, a cheating prover must apply an operation far from $O_{f^{-1}}$
on $|Q\rangle$ to make $R$ accept. We will show that when it applies such an
operation, it must move the trap state $|T\rangle$ far from the correct state
$|T^{H}\rangle$ which will be detected by the verifier. Now, we can finish the
proof by showing the completeness and soundness of the protocol.

###### Proof of Theorem 4.1.

We introduce some notation first. Let the state of the entire system after the
prover’s action be

$\frac{1}{\sqrt{2}}(|\psi_{0}\rangle_{PMV}|0\rangle_{B}+|\psi_{1}\rangle_{PMV}|1\rangle_{B})\,.$

If the prover is honest, then
$|\psi_{0}\rangle=|0\rangle_{P}|Q^{H}\rangle,\quad|\psi_{1}\rangle=|0\rangle_{P}|T^{H}\rangle$.

If the prover is dishonest, we can always assume that $O_{f^{-1}}$ is applied
honestly, followed by an arbitrary unitary $\tilde{U}$ on its work register
$P$ and message register $M$. In this case

$|\psi_{0}\rangle=\tilde{U}\otimes
I_{V}(|0\rangle_{P}|Q^{H}\rangle_{MV}),\quad|\psi_{1}\rangle=\tilde{U}\otimes
I_{V}(|0\rangle_{P}|T^{H}\rangle_{MV})\,.$

For ease of notation, define
$\rho_{0}:=\operatorname{Tr}_{P}(|\psi_{0}\rangle\langle\psi_{0}|_{PMV})$ and
$\rho_{1}:=\operatorname{Tr}_{P}(|\psi_{1}\rangle\langle\psi_{1}|_{PMV})$.

Let $\Pi_{R}$ be the projection to the acceptance subspace
$S_{\text{acc}}\subseteq\mathcal{H}_{M}\otimes\mathcal{H}_{V}$ induced by $R$.
Observe that the verifier accepts with probability

$\displaystyle p_{\text{succ}}$ $\displaystyle:=$
$\displaystyle\frac{1}{2}(p_{0}+p_{1})\,,\quad\text{where
}p_{0}=\operatorname{Tr}(\Pi_{R}\rho_{0})\,,\quad p_{1}=\langle
T^{H}|\rho_{1}|T^{H}\rangle\,.$

Completeness. If $x\in\bar{L}$, then $\rho_{0}=|Q^{H}\rangle\langle Q^{H}|$
and $\rho_{1}=|T^{H}\rangle\langle T^{H}|$. Therefore,
$p_{0}=\operatorname{Tr}(\Pi_{R}\rho_{0})\geq 1-\varepsilon$ by our hypothesis
on the reduction. Meanwhile $p_{1}=\langle T^{H}|\rho_{1}|T^{H}\rangle=1$.
Therefore $p_{\text{succ}}=\frac{1}{2}(p_{0}+p_{1})\geq 1-\varepsilon/2$.

Soundness. Suppose that $x\notin\bar{L}$. By Claim 4.3, we have that
$p_{1}=\langle T^{H}|\rho_{1}|T^{H}\rangle=\langle
Q^{H}|\rho_{0}|Q^{H}\rangle$. Therefore

$p_{\text{succ}}=\frac{1}{2}(p_{0}+p_{1})=\frac{1}{2}(\operatorname{Tr}(\Pi_{R}\rho_{0})+\langle
Q^{H}|\rho_{0}|Q^{H}\rangle)\,.$

Since $x\notin\bar{L}$, we know that
$RC|Q^{H}\rangle=\sqrt{\delta}|0\rangle|\phi_{x,0}\rangle+\sqrt{1-\delta}|1\rangle|\phi_{x,1}\rangle$
with $\delta\leq\varepsilon$. Therefore, $\langle
Q^{H}|\Pi_{R}|Q^{H}\rangle\leq\varepsilon$, i.e., $|Q^{H}\rangle$ is almost
orthogonal to the acceptance subspace $S_{\text{acc}}$. Then from the prover’s
perspective, to maximize the verifier’s accepting probability, it needs to
find a state whose projection on $|Q^{H}\rangle$ and $S_{\text{acc}}$ combined
is maximized. By Lemma 4.4, the maximum is achieved by a state bisecting
$|Q^{H}\rangle$ and its projection on $S_{\text{acc}}$, and we conclude that
$p_{\text{succ}}=\frac{1}{2}(\operatorname{Tr}(\Pi_{R}\rho_{0})+\langle
Q^{H}|\rho_{0}|Q^{H}\rangle)\leq\frac{1}{2}(1+\sqrt{\varepsilon}).$

∎

######  Corollary 4.5.

If there exists a uniform one-query locally quantum reduction from a worst-
case NP-hard decision problem to inverting a one-way permutation, then coNP
$\subseteq$ QIP$(2)$.

###### Proof.

Suppose $L$ is NP-hard, and it reduces to Inv-OWP via a uniform one-query
quantum locally random reduction. By Theorem 4.1, $\overline{L}\in{QIP(2)}$,
hence $coNP\subseteq{QIP(2)}$. ∎

######  Corollary 4.6.

If there exists a uniform one-query locally quantum reduction from a worst-
case promise problem which is QMA-hard to inverting a one-way permutation,
then coQMA $\subseteq$ QIP$(2)$

###### Proof.

Suppose $L$ is QMA-hard and there exists a uniform one-query quantum locally
random reduction from $L$ to Inv-OWP. By Theorem 4.1,
$\overline{L}\in{QIP(2)}$. This implies $coQMA\subseteq{QIP(2)}$. ∎

##  5 Uniform non-adaptive locally quantum reduction to Inv-OWP

In Section 4, we concern the special case of locally quantum reduction with
only one query and negligible error. In this section, we are going to
generalize Theorem 4.1 such that the existence of a uniform non-adaptive
(multiple-queries) locally quantum reduction with constant error implies
coNP$\subseteq$QIP($2$).

Let $f$ be a one-way permutation, and let $U_{f}$ be a circuit computing it. A
uniform non-adaptive locally quantum reduction $(G,R)$ from a decision problem
to the task of inverting $f$ is defined as:

$\displaystyle|x,0\rangle$ $\displaystyle\stackrel{{\scriptstyle
G}}{{\longrightarrow}}$
$\displaystyle\frac{1}{\sqrt{2^{mk}}}\sum_{q_{1},\dots,q_{k}\in\mathbb{Z}_{2}^{m}}|q_{1},0,w_{x,1}(q_{1})\rangle\otimes\cdots\otimes|q_{k},0,w_{x,k}(q_{k})\rangle$
$\displaystyle\stackrel{{\scriptstyle O_{f^{-1}}}}{{\longrightarrow}}$
$\displaystyle\frac{1}{\sqrt{2^{mk}}}\sum_{q_{1},\dots,q_{k}\in\mathbb{Z}_{2}^{m}}|q_{1},f^{-1}(q_{1}),w_{x,1}(q_{1})\rangle\otimes\cdots\otimes|q_{k},f^{-1}(q_{k}),w_{x,k}(q_{k})\rangle$
$\displaystyle\stackrel{{\scriptstyle R}}{{\longrightarrow}}$ $\displaystyle
a_{0}|0\rangle|\psi_{x,0}\rangle+a_{1}|1\rangle|\psi_{x,1}\rangle,$

where $|a_{1}|^{2}\geq 2/3$ if $x\in L$ and $|a_{1}|^{2}\leq 1/3$ if $x\notin
L$ is the probability the reduction accepts.

######  Theorem 5.1.

Suppose there exists a uniform non-adaptive locally quantum reduction $(G,R)$
from a worst-case decision problem $L$ to Inv-OWP. Then, there exists a
$QIP(2)$ protocol with completeness $1-\epsilon/2$ and soundness
$1/2+2\sqrt{\epsilon}$ for $\overline{L}$, where $\epsilon$ is negligible.

###  5.1 Main theorem

Before giving the main theorem, we first show that the error of locally
quantum reductions and quantum worst-case to average-case reductions can be
reduced by parallel repetition.

######  Lemma 5.2 (Error reduction).

The error of locally quantum reductions and quantum worst-case to average-case
reductions can be reduced to an exponential small parameter $\epsilon$ in
polynomial time and polynomial number of queries.

###### Proof.

The error of both reductions can be reduced by parallel repetition. The new
reduction ($R^{\prime},G^{\prime}$) is described as follows:

  1. 1.

$G^{\prime}$ operates $G$ $t$ times to generate $t$ copies of
$|Q_{x,1}\rangle\otimes\cdots\otimes|Q_{x,k}\rangle$ and send all copies to
the oracle in parallel, where $t$ is polynomial in the input length $n$.

  2. 2.

After getting all $t$ responses $|Q_{x,1}^{H},\dots,Q_{x,k}^{H}\rangle$ from
the oracle, $R^{\prime}$ operates $R$ $t$ times and make the majority vote. If
more than $t/2$ copies are accepted, $R^{\prime}$ accepts; otherwise,
$R^{\prime}$ rejects.

For completeness, the probability that $(G^{\prime},R^{\prime})$ rejects is
$\sum_{u<\frac{t}{2}}{{t}\choose{u}}\frac{2}{3}^{u}(1-\frac{2}{3})^{t-u}$. For
soundness, the probability that $(G^{\prime},R^{\prime})$ accepts is
$\sum_{u>\frac{t}{2}}{{t}\choose{u}}\frac{1}{3}^{u}(1-\frac{1}{3})^{t-u}$.
Both are negligible. ∎

We are going to show that such reduction does not exist unless coNP
$\subseteq$ QIP($2$).

###### Proof.

The error can be reduced to an exponentially small parameter $\epsilon$ by
applying Lemma 5.2. The idea of the protocol for multiple queries is the same
as the protocol in Protocol 1 for one query. The verifier generates a
superposition of the query state and the trap state and sends part of the
state to the prover. In the following, we will give a QIP(2) protocol which is
similar to the protocol in Protocol 1 for $\overline{L}$.

By Lemma 5.2, the error of a quantum locally random $(G,R)$ can be reduced to
an exponentially small parameter $\epsilon$ by parallel repetition, where we
suppose $G$ is operated $t$ times and each time it generates $k$ queries. We
denote the new reduction as $(G^{\prime},R^{\prime})$.

Now, we introduce the new query state and the trap state the verifier
generates. By applying $G^{\prime}$ and $C$, the verifier generates

$|Q_{1,1}\rangle|Q_{1,2}\rangle\otimes\cdots\otimes|Q_{t,k}\rangle,$

where

$|Q_{i,j}\rangle=\frac{1}{\sqrt{2^{m}}}\sum_{q\in\mathbb{Z}_{2}^{m}}|q,0\rangle|w_{x,j}(q),q\rangle\mbox{
for }1\leq i\leq t,1\leq j\leq k.$

Note that $i$ indicates the $i$-th copy generated from the parallel repetition
in Lemma 5.2. Also, the verifier generates $|T\rangle^{\otimes tk}$, where
$|T\rangle$ is defined in Equation 6.

Then, we rearrange the qubits such that the first two registers of all
$|Q_{i,j}\rangle$ and $|T\rangle$ are moved to the beginning in sequence as
follows:

$\displaystyle|Q_{1,1},\dots,Q_{t,k}\rangle$ $\displaystyle\rightarrow$
$\displaystyle|\hat{Q}\rangle_{MV}=\frac{1}{2^{mkt/2}}\sum_{\hat{q}\in\mathbb{Z}_{2}^{mkt}}|\hat{q},0\rangle_{M}|w_{x}(\hat{q}),\hat{q}\rangle_{V}$
(14)

and

$\displaystyle|T\rangle^{\otimes k}$ $\displaystyle\rightarrow$
$\displaystyle|\hat{T}\rangle_{MV}=\frac{1}{2^{mkt/2}}\sum_{\hat{q}\in\mathbb{Z}_{2}^{mkt}}|\hat{q},0\rangle_{M}|0,\hat{q}\rangle_{V}.$
(15)

where $\hat{q}=[q_{1,1},\dots,q_{1,k},\dots,q_{t,1},\dots,q_{t,k}]$ and
$w_{x}(\hat{q})=[w_{x,1}(q_{1,1}),\dots,w_{x,k}(q_{t,k})].$ For example, given
a state of two queries
$\sum_{q,q^{\prime}}|q,0\rangle|w_{x,1}(q),q\rangle|q^{\prime},0\rangle|w_{x,2}(q),q^{\prime}\rangle$,
following the rearrangement, we represent it as
$\sum_{q,q^{\prime}}|qq^{\prime},0\rangle|w_{x,1}(q)w_{x,2}(q^{\prime}),qq^{\prime}\rangle$.

Similarly, we define

$\displaystyle|\hat{Q}^{H}\rangle_{MV}=\frac{1}{2^{mkt/2}}\sum_{\hat{q}\in\mathbb{Z}_{2}^{mkt}}|\hat{q},f^{-1}(\hat{q})\rangle_{M}|w_{x}(\hat{q}),\hat{q}\rangle_{V}$

and

$\displaystyle|\hat{T}^{H}\rangle_{MV}=\frac{1}{2^{mkt/2}}\sum_{\hat{q}\in\mathbb{Z}_{2}^{mkt}}|\hat{q},f^{-1}(\hat{q})\rangle_{M}|0,\hat{q}\rangle_{V},$

where $f^{-1}(\hat{q})=(f^{-1}(q_{1,1}),\dots,f^{-1}(q_{t,k})).$

The protocol takes place in the space
$\mathcal{H}_{P}\otimes\mathcal{H}_{M}\otimes\mathcal{H}_{V}\otimes\mathcal{H}_{\Pi}$
where $P$ is the private register of the prover, $M$ is the register exchanged
between the prover and the verifier, and $V$ and $\Pi$ are registers which are
private to the verifier. 1. _The verifier’s query._ The verifier prepares the
state below. The message register $M$ is sent to the prover.
$\displaystyle|\hat{S}\rangle_{MV\Pi}:=\frac{1}{\sqrt{2}}(|\hat{Q}\rangle_{MV}|0\rangle_{\Pi}+|\hat{T}\rangle_{MV}|1\rangle_{\Pi}).$
2. _The prover’s response._ The prover applies some unitary $U_{PM}$ on
register $M$ and its private register $P$ and sends the message register back
to the verifier. 3. _The verifier’s verification._ The verifier applies $C$ to
erase $\hat{q}$ in $V$. The verifier then measures $\Pi$ to obtain
$b\in\\{0,1\\}$, and does the following: • (Computation verification) If
$b=0$, apply $R^{\prime}$ on $MV$ and measure the output qubit. Accept if the
outcome is $0$. • (Trap verification) If $b=1$, apply $V_{T}$ on each
$|T\rangle$ in $MV$ and measure $MV$. Accept if the outcome is the all $0$
string. Protocol 2 QIP(2) protocol for $\overline{L}$ using a non-adaptive
locally quantum reduction.

The QIP($2$) protocol for $\overline{L}$ is shown in Protocol 2. Note that the
prover’s behavior $U_{PM}$ can be represented as $U^{\prime}_{PM}O_{f^{-1}}$
where $U^{\prime}_{PM}$ is an arbitrary unitary a cheating prover may apply.
In the following, we show that the protocol in Protocol 2 is a QIP($2$)
protocol for $\overline{L}$ .

For the completeness condition, when $x\in\overline{L}$, the verifier accepts
with probability $\geq 1-\epsilon/2$ via the same calculation in Section 4.

For the soundness condition, assume $x\notin\overline{L}$. Let

$\hat{\sigma}^{U^{\prime}}_{Q}=\operatorname{Tr}_{P}(U^{\prime}_{PM}\otimes
I_{V}(|0\rangle\langle
0|\otimes|\hat{Q}^{H}\rangle\langle\hat{Q}^{H}|)U^{\prime\dagger}_{PM}\otimes
I_{V})$

and

$\hat{\sigma}^{U^{\prime}}_{T}=\operatorname{Tr}_{P}(U^{\prime}_{PM}\otimes
I_{V}(|0\rangle\langle
0|\otimes|\hat{T}^{H}\rangle\langle\hat{T}^{H}|)U^{\prime\dagger}_{PM}\otimes
I_{V}).$

Since $|\hat{T}^{H}\rangle$ and $|\hat{Q}^{H}\rangle$ are two purifications of
the mixed state
$\operatorname{Tr}_{V}(|\hat{Q}^{H}\rangle\langle\hat{Q}^{H}|)$ on register
$M$,

$\displaystyle\langle\hat{Q}^{H}|\hat{\sigma}^{U^{\prime}}_{Q}|\hat{Q}^{H}\rangle=\langle\hat{T}^{H}|\hat{\sigma}^{U^{\prime}}_{T}|\hat{T}^{H}\rangle$
(16)

by Lemma 4.2. Then, we do a similar calculation as in the proof of soundness
for Theorem 4.1, which gives an upper bound $1/2+\sqrt{\epsilon}$ on the
probability that the verifier accepts. ∎

The following two corollaries follow from Theorem 5.1, which proofs are the
same as the proof for Corollary 4.5 and Corollary 4.6.

######  Corollary 5.3.

If there exists a uniform non-adaptive quantum locally random reduction from a
worst-case decision problem which is NP-hard to the task of inverting a one-
way permutation, then coNP $\subseteq$ QIP$(2)$.

######  Corollary 5.4.

If there exists a uniform non-adaptive quantum locally random reduction from a
worst-case promise problem which is QMA-hard to the task of inverting a one-
way permutation, then coQMA $\subseteq$ QIP$(2)$.

##  6 Smooth locally quantum reductions to Inv-OWP

In this section, we study non-adaptive quantum reductions which generate
queries according to smooth-computable distributions. We show that the
existence of such reductions also imply $coNP\subseteq QIP(2)$.

The difficulty to apply Protocol 1 and Protocol 2 to non-uniform distributions
is that we do not know how to construct a trap state that can be mapped to
$|0\rangle$ efficiently and has the state in the message register be
indistinguishable from the actual query state. Here we show that if the
distribution is smooth-computable, then the verifier can use the same trap
state by applying quantum rejection sampling [ORR13] to prevent the prover
from cheating.

######  Definition 6.1 (Smooth-computable distributions).

A distribution $\mathcal{D}=\\{\mathcal{D}_{n}:n\in\mathbb{N}\\}$ is said to
be smooth-computable if it satisfies the following properties. Let
$d_{q}=\Pr[q\sim\mathcal{D}_{n}]$, $d_{min,n}=\min_{q\in\\{0,1\\}^{n}}d_{q}$
and $d_{max,n}=max_{q\in\\{0,1\\}^{n}}d_{q}$.

  1. 1.

For $n\in\mathbb{N}$, for all $q$ where $|q|=n$, the function
$f_{n}:f_{n}(q)=d_{q}$ is polynomial-time computable.

  2. 2.

For $n\in\mathbb{N}$, $2^{n}d_{min,n}\geq\frac{1}{poly(n)}$ and
$2^{n}d_{max,n}\leq poly(n)$.

Loosely speaking, smooth-computable distributions are point-wise close to the
uniform distribution. It is worth noting that Protocol 2 can handle those that
have negligible statistical distance to the uniform distribution. However,
there exists some smooth-computable distribution that has inverse-polynomial
distance from the uniform distribution. In such cases, it is unclear if
soundness still holds in Protocol 2.

Again, we start with the special case of _one-query_ reductions with
negligible error. Generalizing to multiple non-adaptive queries is similar to
the case of uniform distributions before.

Let $f$ be a one-way permutation on $\left\\{0,1\right\\}^{n}$, and let
$U_{f}$ be a quantum circuit computing it. A smooth one-query locally quantum
reduction according to a smooth-computable distribution
$\mathcal{D}=\\{\mathcal{D}_{n}:n\in\mathbb{N}\\}$ proceeds as follows:

$\displaystyle|x,0\rangle|0\rangle$ $\displaystyle\stackrel{{\scriptstyle
G}}{{\longrightarrow}}$
$\displaystyle\frac{1}{\sqrt{2^{m}}}\sum_{q\in\mathbb{Z}_{2}^{m}}\sqrt{d_{q}}|q,0\rangle|w_{x}(q)\rangle$
(17) $\displaystyle\overset{O_{f^{-1}}}{\longrightarrow}$
$\displaystyle\frac{1}{\sqrt{2^{m}}}\sum_{q\in\mathbb{Z}_{2}^{m}}\sqrt{d_{q}}|q,f^{-1}(q)\rangle|w_{x}(q)\rangle\stackrel{{\scriptstyle
R}}{{\longrightarrow}}a_{0}|0\rangle|\psi_{x,0}\rangle+a_{1}|1\rangle|\psi_{x,1}\rangle,$
(18)

where $|a_{1}|^{2}\geq 1-\epsilon$ if $x\in L$ and $|a_{1}|^{2}\leq\epsilon$
if $x\notin L$ is the probability the reduction accepts and $d_{q}$ is the
probability that $q$ is drawn from $\mathcal{D}_{n}$ for $n=|q|$. We can show
the following theorem.

######  Theorem 6.2.

Suppose there exists a one-query smooth locally quantum reduction with
exponentially small error $\epsilon$ from a worst-case decision problem $L$ to
the task of inverting a polynomial-time computable permutation. Then there
exists a $QIP($2$)$ protocol with completeness $1-\epsilon/2$ and soundness
$1/2+2\sqrt{\epsilon}$ for $\overline{L}$

###  6.1 Quantum Rejection Sampling

The proof of Theorem 6.2 relies on the quantum rejection sampling technique in
[ORR13]. We give the definition of the quantum rejection sampling problem and
we adapt their tool in the Lemma 6.4.

######  Definition 6.3 (Quantum rejection sampling problem
$QRSP(\mathcal{D},\mathcal{D}^{\prime},n)$).

Given an oracle
$O_{\mathcal{D}}:|0\rangle\rightarrow\sum_{x=1}^{2^{n}}\sqrt{d_{x}}|\xi_{x}\rangle|x\rangle$
as a unitary, where $d_{x}\sim\mathcal{D}_{n}$ and $|\xi_{x}\rangle$ are some
unknown fixed states. The Quantum rejection sampling problem is to prepare the
state $\sum_{x=1}^{2^{n}}\sqrt{d^{\prime}_{x}}|\xi_{x}\rangle|x\rangle$ for
$d^{\prime}_{x}\sim\mathcal{D}^{\prime}_{n}$.

######  Lemma 6.4.

Let $\mathcal{D}=\\{\mathcal{D}_{n}:n\in\mathbb{N}\\}$ be a smooth-computable
distribution and $\mathcal{U}$ be the uniform distribution. There exists a
quantum poly-time algorithm $QRSampling(\mathcal{D}\rightarrow\mathcal{U})$
that takes $\gamma=(\lceil\frac{1}{2^{n}d_{min,n}}\rceil)^{2}$ copies of
$\sum_{x=1}^{2^{n}}\sqrt{d_{x}}|\xi_{x}\rangle|x\rangle$ and outputs a state
that has negligible trace distance $\delta$ to
$\sum_{x=1}^{2^{n}}\sqrt{\frac{1}{2^{n}}}|\xi_{x}\rangle|x\rangle$. Similarly
$QRSampling(\mathcal{U}\rightarrow\mathcal{D})$ takes $\gamma^{\prime}=(\lceil
2^{n}d_{max,n}\rceil)^{2}$ copies of
$\sum_{x=1}^{2^{n}}\sqrt{\frac{1}{2^{n}}}|\xi_{x}\rangle|x\rangle$ and outputs
a state that has negligible trace distance $\delta^{\prime}$ to
$\sum_{x=1}^{2^{n}}\sqrt{d_{x}}|\xi_{x}\rangle|x\rangle$.

Note that $\gamma$ and $\gamma^{\prime}$ are polynomial in $n$ when
$\mathcal{D}$ is smooth according to Definition 6.1.

###### Proof.

We first show the sample complexity. It has been shown in [ORR13] that
Algorithm 3 can solve the $QRSP(\mathcal{D},\mathcal{D}^{\prime},k)$ exactly
with $1-e^{-\beta}$ with $\beta^{2}$ samples generated from $O_{\mathcal{D}}$
for $\frac{1}{\beta}=min_{x}d_{x}/d_{x}^{\prime}$. In case
$\mathcal{D}=\mathcal{U}$, we have
$\frac{1}{\beta}=min_{x}\frac{1}{2^{n}d_{x}}=\frac{1}{2^{n}d_{max,n}}$. In
case $\mathcal{D}^{\prime}=\mathcal{U}$, we have
$\frac{1}{\beta}=2^{n}d_{min,n}$.

Algorithm 3 can also be done in polynomial time. Consider the case where
$\mathcal{D}^{\prime}=\mathcal{U}$. The Step 2 in Algorithm 3 can be viewed as
a control rotation on the first and the third register.

$S=\sum_{i=1}^{2^{n}}\frac{1}{d_{i}}\begin{bmatrix}\sqrt{d_{i}-\frac{1}{2^{n}\gamma}}&-\sqrt{\frac{1}{2^{n}\gamma}}\\\
\sqrt{\frac{1}{2^{n}\gamma}}&\sqrt{d_{i}-\frac{1}{2^{n}\gamma}}\end{bmatrix}\otimes
I\otimes|i\rangle\langle i|$

By Solovay-Kitaev theorem, any known one-qubit unitary $V$ can be approximated
by $V^{\prime}$ which is implemented by polynomial number of gates from a
finite universal gate set with an exponentially small error
$\delta=max_{|\psi\rangle}\|(V-V^{\prime})|\psi\rangle\|$. Since $\mathcal{D}$
and $\mathcal{U}$ are polynomial-time computable as in Definition 6.1, we can
approximate $S$ in polynomial time. This completes the proof. The analysis for
the case where $\mathcal{D}=\mathcal{U}$ is the same.

Algorithm 3 $QRSampling(\mathcal{D}\rightarrow\mathcal{D}^{\prime})$

1:Let $\frac{1}{\beta}=\min_{x}\frac{d_{x}}{d^{\prime}_{x}}$.

2:Apply $O_{\mathcal{D}}$ to generate
$\sum_{x=1}^{2^{n}}\sqrt{d_{i}}|\xi_{i}\rangle|i\rangle$.

3:Pick $\vec{\alpha}\in\mathbb{R}^{2^{n}}_{+}$ where
$\alpha_{i}=\frac{d^{\prime}_{i}}{\beta}$and rotate the state in the first
register by $S$
$S:|0\rangle(\sum_{x=1}^{2^{n}}\sqrt{d_{i}}|\xi_{i}\rangle|i\rangle)\rightarrow\sum_{x=1}^{2^{n}}(\sqrt{d_{i}-\alpha_{i}}|0\rangle+\sqrt{\alpha_{i}}|1\rangle)|\xi_{i}\rangle|i\rangle.$

4:Measure the first qubit, which gives
$\sum_{i=1}^{2^{n}}\sqrt{d^{\prime}_{i}}|\xi_{i}\rangle|i\rangle$ with
probability $\frac{1}{\beta}$.

5:By repeating steps 2 to 4 $\Theta(\beta^{2})$ times, one can prepare the
state $\sum_{i=1}^{2^{n}}\sqrt{d^{\prime}_{i}}|\xi_{i}\rangle|i\rangle$ with
probability $1-e^{-\beta}$ .

∎

###  6.2 The new protocol for $\overline{L}$ using quantum rejection sampling

Here we describe some states which are used in the protocol.

$\displaystyle|Q_{\mathcal{D}}\rangle_{MV}=\frac{1}{\sqrt{2^{n}}}\sum_{q\in\mathbb{Z}_{2}^{m}}\sqrt{d_{q}}|q,0\rangle_{M}|w_{x}(q),q\rangle_{V},$
(19)

where $|Q_{\mathcal{D}}\rangle_{MV}$ without the copy of $q$ in $V$ is the
query state generated from $G$ as in Equation 17.

$\displaystyle|Q^{H}_{\mathcal{D}}\rangle_{MV}=\frac{1}{\sqrt{2^{n}}}\sum_{q\in\mathbb{Z}_{2}^{m}}\sqrt{d_{q}}|q,f^{-1}(q)\rangle_{M}|w_{x}(q),q\rangle_{V},$
(20)

where $|Q^{H}_{\mathcal{D}}\rangle$ without the extra copy $q$ in register $V$
is the state the actual reduction $R$ gets after querying the oracle as in
Equation 18.

By applying $QRSampling(\mathcal{D}\rightarrow\mathcal{U})$, one can prepare
the state $|\tilde{Q}\rangle$ from $|Q_{\mathcal{D}}\rangle_{MV}$ such that
$D(|\tilde{Q}\rangle,|Q\rangle)\leq\delta$, where $\delta$ is an exponentially
small error. We also define
$|\tilde{Q}^{H}\rangle:=O_{f^{-1}}|\tilde{Q}\rangle$. Similarly, one can
prepare the state $|\tilde{Q}^{H}_{\mathcal{D}}\rangle$ from
$|\tilde{Q}^{H}\rangle$ by $QRSampling(\mathcal{U}\rightarrow\mathcal{D})$
such that
$D(|\tilde{Q}^{H}_{\mathcal{D}}\rangle,|Q^{H}_{\mathcal{D}}\rangle)\leq\delta^{\prime}$,
where $\delta^{\prime}$ is exponentially small.

We give Protocol 4 for $\overline{L}$ with non-adaptive smooth locally quantum
reductions. Its analysis and proof of Theorem 6.2 are deferred in Section 6.3.

Let $\gamma=(\lceil\frac{1}{2^{n}d_{min}}\rceil)^{2}$ and
$\gamma^{\prime}=(\lceil 2^{n}d_{max}\rceil)^{2}$, where
$d_{min}=\min_{q\in\\{0,1\\}^{n}}\Pr[q\sim\mathcal{D}_{n}]$ and
$d_{max}=max_{q\in\\{0,1\\}^{n}}\Pr[q\sim\mathcal{D}_{n}]$. 1. _The verifier’s
query._ The verifier prepares the state
$\displaystyle|S\rangle_{MV\Pi}:=\frac{1}{\sqrt{2}}(|\tilde{Q}\rangle_{M_{1}V_{1}}\otimes\cdots\otimes|\tilde{Q}\rangle_{M_{\gamma^{\prime}}V_{\gamma^{\prime}}}|0\rangle_{\Pi}+|T\rangle_{M_{1}V_{1}}\otimes\cdots\otimes|T\rangle_{M_{\gamma^{\prime}}V_{\gamma^{\prime}}}|1\rangle_{\Pi}).$
The message registers $M_{1},\dots,M_{\gamma^{\prime}}$ are sent to the
prover, and the verifier keeps $V_{1},\dots,V_{\gamma^{\prime}}$ and $\Pi$.
$|\tilde{Q}\rangle$ can be prepared from $\gamma$ copies of
$|Q_{\mathcal{D}}\rangle$ by applying
$QRSampling(\mathcal{D}\rightarrow\mathcal{U})$. 2. _The prover’s response._
The prover applies some unitary $U_{PM_{1}\dots M_{\gamma^{\prime}}}$ on
registers $M_{1}\dots M_{\gamma^{\prime}}$ and its private register $P$ and
sends the message registers back to the verifier. 3. _The verifier’s
verification._ The verifier applies $C$ to erase $q$ in $V_{1}\dots
V_{\gamma^{\prime}}$. The verifier then measures $\Pi$ to obtain
$b\in\\{0,1\\}$, and does the following: • (Computation verification) If
$b=0$, apply $QRSampling(\mathcal{U}\rightarrow\mathcal{D})$ to get a state
$|\tilde{Q}^{H}_{\mathcal{D}}\rangle$, apply $R$ on
$|\tilde{Q}^{H}_{\mathcal{D}}\rangle$ and measure the output qubit. Accept if
the outcome is $0$. • (Trap verification) If $b=1$, apply $V_{T}$ on
$M_{i}V_{i}$ for $i\in[\gamma^{\prime}]$ and measure. Accept if the outcome is
all $0$. Protocol 4 QIP(2) protocol for $\overline{L}$ with non-adaptive
smooth locally quantum reductions.

###  6.3 Proof of Theorem 6.2

###### Proof of Theorem 6.2.

Let the state of the entire system after the prover’s action be

$\frac{1}{\sqrt{2}}(|\tilde{\psi}\rangle_{PM_{1}\dots
M_{\gamma^{\prime}}V_{1}\dots
V_{\gamma^{\prime}}}|0\rangle_{B}+|\phi\rangle_{PM_{1}\dots
M_{\gamma^{\prime}}V_{1}\dots V_{\gamma^{\prime}}}|1\rangle_{B})\,.$

To simplify the notation, we let $M=M_{1}M_{2}\dots M_{\gamma^{\prime}}$ and
$V=V_{1}V_{2}\dots V_{\gamma^{\prime}}$. If the prover is honest, then

$|\tilde{\psi}\rangle=|0\rangle_{P}|\tilde{Q}^{H}\rangle\otimes\cdots\otimes|\tilde{Q}^{H}\rangle,\quad|\phi\rangle=|0\rangle_{P}|T^{H}\rangle\otimes\cdots\otimes|T^{H}\rangle\,,$

where $F(|\tilde{Q}^{H}\rangle,|Q^{H}\rangle)\geq 1-\delta$ according to Lemma
6.4. If the prover is dishonest, we can always assume that the prover first
applies $O_{f^{-1}}$ honestly and then applies an arbitrary unitary
$\tilde{U}$ on its work register $P$ and message register $M$. In this case

$|\tilde{\psi}\rangle=\tilde{U}_{PM}\otimes
I_{V}(|0\rangle_{P}|\tilde{Q}^{H}\rangle\otimes\cdots\otimes|\tilde{Q}^{H}\rangle),\quad|\phi\rangle=\tilde{U}_{PM}\otimes
I_{V}(|T^{H}\rangle\otimes\cdots\otimes|T^{H}\rangle)\,.$

For ease of notation, we define

$\tilde{\rho}_{0}:=\operatorname{Tr}_{P}(|\tilde{\psi}\rangle\langle\tilde{\psi}|);\quad\rho_{1}:=\operatorname{Tr}_{P}(|\phi\rangle\langle\phi|)\,.$

Let $\Pi_{R}$ be the projection to the acceptance subspace
$S_{\text{acc}}\subseteq\mathcal{H}_{M}\otimes\mathcal{H}_{V}$ induced by the
verifier’s verification. Observe that the verifier accepts with probability

$\displaystyle p_{\text{succ}}:=\frac{1}{2}(p_{0}+p_{1})\,,\quad\text{where
}p_{0}=\operatorname{Tr}(\Pi_{R}\tilde{\rho}_{0})\,,\quad p_{1}=\langle
T^{H}|^{\otimes\gamma^{\prime}}\rho_{1}|T^{H}\rangle^{\otimes\gamma^{\prime}}\,.$

Completeness. If $x\in\bar{L}$, then
$\tilde{\rho}_{0}=|\tilde{Q}^{H}\rangle\langle\tilde{Q}^{H}|$ and
$\rho_{1}=|T^{H}\rangle\langle T^{H}|$. Therefore,
$p_{0}=\operatorname{Tr}(\Pi_{R}\tilde{\rho}_{0})\geq 1-\varepsilon-2\delta$
where $\epsilon$ is from our hypothesis on the reduction and $\delta$ is the
error from the quantum rejection sampling. Meanwhile $p_{1}=\langle
T^{H}|\rho_{1}|T^{H}\rangle=1$. Therefore
$p_{\text{succ}}=\frac{1}{2}(p_{0}+p_{1})\geq 1-(\varepsilon+2\delta)/2$.

Soundness. Suppose that $x\notin\bar{L}$. Let
$|\psi\rangle=\tilde{U}_{PM}\otimes
I_{V}(|0\rangle_{P}|Q^{H}\rangle\otimes\cdots\otimes|Q^{H}\rangle)$ and
$\rho_{0}:=\operatorname{Tr}_{P}(|\psi\rangle\langle\psi|)$. By Claim 4.3, we
have that

$\langle
T^{H}|^{\otimes\gamma^{\prime}}\rho_{1}|T^{H}\rangle^{\otimes\gamma^{\prime}}=\langle
Q^{H}|^{\otimes\gamma^{\prime}}\rho_{0}|Q^{H}\rangle^{\otimes\gamma^{\prime}}\,,$

and then we are going to show that $\langle
T^{H}|^{\otimes\gamma^{\prime}}\rho_{1}|T^{H}\rangle^{\otimes\gamma^{\prime}}$
is close to $\langle
Q^{H}|^{\otimes\gamma^{\prime}}\tilde{\rho}_{0}|Q^{H}\rangle^{\otimes\gamma^{\prime}}$
except for a exponentially small error.

First, by monotonicity of the fidelity, $F(\rho_{0},\tilde{\rho}_{0})\geq
F(|Q^{H}\rangle,|\tilde{Q}^{H}\rangle)\geq 1-\delta$. Then we define the
angles between states $|Q^{H}\rangle^{\otimes\gamma^{\prime}}$, $\rho_{0}$ and
$\tilde{\rho}_{0}$ as

$A(|Q^{H}\rangle^{\otimes\gamma^{\prime}},\rho_{0})=\arccos{F(|Q^{H}\rangle^{\otimes\gamma^{\prime}},\rho_{0})},\quad
A(\tilde{\rho}_{0},\rho_{0})=\arccos{F(\tilde{\rho}_{0},\rho_{0})},\text{
and}$
$A(|Q^{H}\rangle^{\otimes\gamma^{\prime}},\tilde{\rho}_{0})=\arccos{F(|Q^{H}\rangle^{\otimes\gamma^{\prime}},\tilde{\rho}_{0})}.$

By the triangular inequality,

$A(|Q^{H}\rangle^{\otimes\gamma^{\prime}},\tilde{\rho}_{0})\leq
A(|Q^{H}\rangle^{\otimes\gamma^{\prime}},\rho_{0})+A(\tilde{\rho}_{0},\rho_{0}).$

This gives

$\displaystyle F(|Q^{H}\rangle^{\otimes\gamma^{\prime}},\tilde{\rho}_{0})$
$\displaystyle\geq$
$\displaystyle\cos{(A(|Q^{H}\rangle^{\otimes\gamma^{\prime}},\rho_{0})+A(\tilde{\rho}_{0},\rho_{0}))}$
$\displaystyle=$ $\displaystyle
F(|Q^{H}\rangle^{\otimes\gamma^{\prime}},\rho_{0})F(\tilde{\rho}_{0},\rho_{0})-\sqrt{1-F(|Q^{H}\rangle^{\otimes\gamma^{\prime}},\rho_{0})}\sqrt{1-F(\tilde{\rho}_{0},\rho_{0})}$
$\displaystyle\geq$ $\displaystyle
F(|Q^{H}\rangle^{\otimes\gamma^{\prime}},\rho_{0})-2\sqrt{\delta}.$

We can also get an upper bound on
$F(|Q^{H}\rangle^{\otimes\gamma^{\prime}},\tilde{\rho}_{0})$ as follows: By
triangular inequality,

$A(|Q^{H}\rangle^{\otimes\gamma^{\prime}},\tilde{\rho}_{0})\geq
A(|Q^{H}\rangle^{\otimes\gamma^{\prime}},\rho_{0})-A(\tilde{\rho}_{0},\rho_{0}),$

which implies

$\displaystyle F(|Q^{H}\rangle^{\otimes\gamma^{\prime}},\tilde{\rho}_{0})$
$\displaystyle\leq$
$\displaystyle\cos{(A(|Q^{H}\rangle^{\otimes\gamma^{\prime}},\rho_{0})-A(\tilde{\rho}_{0},\rho_{0}))}$
$\displaystyle=$ $\displaystyle
F(|Q^{H}\rangle^{\otimes\gamma^{\prime}},\rho_{0})F(\tilde{\rho}_{0},\rho_{0})+\sqrt{1-F(|Q^{H}\rangle^{\otimes\gamma^{\prime}},\rho_{0})}\sqrt{1-F(\tilde{\rho}_{0},\rho_{0})}$
$\displaystyle\leq$ $\displaystyle
F(|Q^{H}\rangle^{\otimes\gamma^{\prime}},\rho_{0})+\sqrt{\delta}.$

We can conclude that

$\langle
Q^{H}|^{\otimes\gamma^{\prime}}\tilde{\rho}_{0}|Q^{H}\rangle^{\otimes\gamma^{\prime}}=\langle
Q^{H}|^{\otimes\gamma^{\prime}}\rho_{1}|Q^{H}\rangle^{\otimes\gamma^{\prime}}+c\sqrt{\delta}=\langle
T^{H}|^{\otimes\gamma^{\prime}}\rho_{1}|T^{H}\rangle^{\otimes\gamma^{\prime}}+c\sqrt{\delta}$

for $c$ a small constant. Therefore

$p_{\text{succ}}=\frac{1}{2}(p_{0}+p_{1})=\frac{1}{2}(\operatorname{Tr}(\Pi_{R}\tilde{\rho}_{0})+\langle
Q^{H}|^{\otimes\gamma^{\prime}}\tilde{\rho}_{0}|Q^{H}\rangle^{\otimes\gamma^{\prime}}+c\sqrt{\delta})\,.$

By Lemma 4.4, we can give an upper bound on $p_{\text{succ}}$ as follows.

$p_{\text{succ}}=\frac{1}{2}(\operatorname{Tr}(\Pi_{R}\rho_{0})+\langle
Q^{H}|\rho_{0}|Q^{H}\rangle)\leq\frac{1}{2}(1+\sqrt{\varepsilon}+c\sqrt{\delta})\,.$

∎

By the same proof as in Section 5, we can generalize Theorem 6.2 to Theorem
6.5.

######  Theorem 6.5.

Suppose there exists a one-query smooth locally quantum reduction with
constant error from a worst-case decision problem $L$ to Inv-OWP. Then there
exists a $QIP($2$)$ protocol with completeness $1-\epsilon/2$ and soundness
$1/2+2\sqrt{\epsilon}$ for $\overline{L}$, where $\epsilon$ is negligible.

##  7 Non-adaptive quantum worst-case to average-case reduction to Inv-OWP

Here, we consider the non-adaptive quantum worst-case to average-case
reduction defined in Definition 3.3. We show that if the queries are generated
arbitrarily according to known smooth-computable distributions, i.e., the
distributions of each query can be different but are smooth-computable and
known, then the existence of such reductions also implies coNP$\subseteq$
QIP($2$). We call this reduction known smooth non-adaptive quantum worst-case
to average-case reduction.

######  Theorem 7.1.

Suppose there exists a known smooth non-adaptive quantum worst-case to
average-case reduction with average hardness $\delta$ $(G,R)$ from a worst-
case decision problem $L$ to Inv-OWP. Then, there exists a QIP($2$) protocol
with completeness $1-\epsilon/2$ and soundness $1/2+2\sqrt{\epsilon}$ for
$\overline{L}$

###### Proof.

Suppose $(G,R)$ is the reduction and $G$ generates $k$ uniform queries. Given
any function $g$ which is $\delta$-close to $f^{-1}$ as Definition 3.2. Then,
the smooth non-adaptive worst-case to average-case reduction is as follows:

$\displaystyle|x,0\rangle$ $\displaystyle\xrightarrow{G}$
$\displaystyle(\sum_{q}\sqrt{d_{1,q}}|q,0,w_{x}(q)\rangle)\otimes\cdots\otimes(\sum_{q}\sqrt{d_{k,q}}|q,0,w_{x}(q)\rangle)$
$\displaystyle\xrightarrow{O_{g}}$
$\displaystyle(\sum_{q}\sqrt{d_{1,q}}|q,f^{-1}(q),w_{x}(q)\rangle)\otimes\cdots\otimes(\sum_{q}\sqrt{d_{k,q}}|q,f^{-1}(q),w_{x}(q)\rangle)$
$\displaystyle\xrightarrow{R}$
$\displaystyle\sqrt{p}|L(x)\rangle|\psi_{x,0}\rangle+\sqrt{1-p}|1-L(x)\rangle|\psi_{x,1}\rangle,$

where $p\geq 2/3$ and $d_{i,q}$ are the probability that $q$ is drawn from a
smooth-computable distribution $\mathcal{D}^{(i)}_{|q|}$. Note that
$\mathcal{D}^{(i)}_{|q|}$ can be difference from $\mathcal{D}^{(j)}_{|q|}$ for
$i\neq j$. The error of the reduction can be reduced to an exponentially small
parameter $\epsilon$ by Lemma 5.2.

Given such a reduction from $L$ to Inv-OWP, Protocol 4 decides $\overline{L}$.
It is worth noting that since the distribution of each query is known and
smooth-computable, one can apply quantum resampling for uniform distribution
as in Protocol 4. For completeness, the honest prover always simulates
$O_{f^{-1}}$, which is the same honest prover considered in Theorem 6.2.
Hence, the verifier accepts with probability at least $1-\frac{\epsilon}{2}$.
For soundness, if the prover’s operation is $\delta$-close to $O_{f^{-1}}$,
then the verifier accepts with probability $\leq(1+\epsilon)/2$. Else if it
chooses an operation $U^{\prime}_{PM}$ which is not close to any
$\delta$-close oracle for $O_{f^{-1}}$, then the modified trap state must be
far from the original trap state. By the calculation in Section 6, we get the
same upper bound on the soundness. ∎

The following two corollaries follow from Theorem 7.1.

######  Corollary 7.2.

If there exists a known smooth non-adaptive quantum worst-case to average-case
reduction from a worst-case decision problem which is NP-hard to Inv-OWP, then
coNP $\subseteq$ QIP$(2)$

######  Corollary 7.3.

If there exists a known smooth non-adaptive quantum worst-case to average-case
reduction from a worst-case promise problem which is QMA-hard to Inv-OWP, then
coQMA $\subseteq$ QIP$(2)$

##  8 Separation examples

We give two examples demonstrating the distinct landscapes of classical and
quantum worst-case to average-case reductions. Namely, relative to some oracle
and under reasonable computational assumptions, there exist problems (a worst-
case problem and an average-case problem) where there are no classical
reductions, but they admit an efficient quantum reduction. In fact, the
quantum reduction issues non-adaptive _classical_ queries only. This makes the
separation examples strong.

The idea behind the examples is simple. We design the average-case problem in
such a way that to make a meaningful query to a solver for this average-case
problem, one has to solve a problem that is (assumed to be) hard for classical
algorithms but easy on a quantum computer. Our first example is based on a
oracle problem provably hard classically (Simon’s Problem), and the quantum
reduction needs quantum access to the oracle. The second example needs to
assume the existence of problem in BQP that is outside BPP (e.g.,
factorization). In return, we remove the need of quantum access to the oracle.

Both constructions rely on the following assumption.

######  Assumption 1.

There exists language $L\notin$ BQP (hence $L\notin$ BPP too) that admits a
random self-reduction $L\leq_{(R,G)}(L,D)$ for some distribution $D$.

A candidate is the PSPACE-complete problem TQBF, which is known to have a
_non-adaptive_ random self-reduction [FF93]. Assumption 1 will follow, if BQP
$\subsetneq$ PSPACE holds. Hereafter we treat $G$ as non-adaptive in
Assumption 1 for simplicity.

Let $N=2^{n}$, and for each $i\in[N]$, let
$f_{i}:\left\\{0,1\right\\}^{n}\to\left\\{0,1\right\\}^{n}$ be some function,
and $s_{i}\in\left\\{0,1\right\\}^{n}$. We define an oracle
$O:=O_{s_{0},\ldots,s_{N-1}}$ that generalizes Simon’s oracle [Sim97].

$\displaystyle O:|i,x,y,z\rangle\to|i,x,y\oplus
f_{i}(x),z\rangle\,;\quad\text{ where }f_{i}(x)=f_{i}(x^{\prime})\text{ iff.
}x^{\prime}=x\oplus s_{i}\,.$

We assume that all $s_{i},i\in[N]$ are chose uniformly at random. As an
immediate corollary of Simon’s result. We have that

######  Lemma 8.1.

Given $O$, any classical algorithms needs $\Omega(2^{n/2})$ queries to $O$ to
find $s_{i}$ for some $i\in[N]$. For any $i\in[N]$, there is a quantum
algorithm that can find $s_{i}$ with $O(n^{2})$ queries and time.

Construction 1. We construct our first separation example.

  * •

$L_{1}=\textsc{TQBF}=\\{\phi=\phi(v_{1},\ldots,v_{n})\\}$ containing
satisfiable quantified $n$-variable formulae in 3-CNF. Let $L_{1}^{O}$ be the
language $L_{1}$ relative to oracle $O$, which simply ignores $O$.

  * •

$\hat{L}_{1}^{O}:=\\{x=(i,s,\phi):\text{$s=s_{i}$ and $\phi$ is true}\\}$. We
associate $\hat{L}_{1}^{O}$ a distribution $\hat{D}_{1}$, which is uniform on
$N\times\left\\{0,1\right\\}^{n}$ and samples a formula according to $D$ (the
distribution in Assumption 1).

######  Theorem 8.2.

Under Assumption 1, there does not exist a PPT reduction from $L_{1}^{O}$ to
$(\hat{L}_{1}^{O},\hat{D}_{1})$. In contrast, there is a quantum poly-time
_non-adaptive_ reduction
$L_{1}^{O}\leq_{R_{1}^{Q},G_{1}^{Q}}(\hat{L}_{1}^{O},\hat{D}_{1})$.

###### Proof.

Let $A$ be an algorithm that solves the average-case problem
$(\hat{L}_{1}^{O},\hat{D}_{1})$. For simplicity, we assume that $A$ is a
perfect decider, i.e., for a random input $x=(i,s,\phi)\leftarrow\hat{D}_{1}$,
$A(i,s,\phi)=1$ iff. $s=s_{i}$ and $\phi=1$. Any classical reduction is unable
to find $s_{i}$ in polynomial time, hence the solver $A$ is useless. Formally
speaking, if there were such a reduction
$L_{1}^{O}\leq(\hat{L}_{1}^{O},\hat{D}_{1})$, one can turn it into an
efficient solver for Simon’s problem or an efficient decider for $L$. This
violates Lemma 8.1 or Assumption 1.

For the second part, we construct a quantum reduction $(R^{Q}_{1},G^{Q}_{1})$
as follows. Recall that there is a random self-reduction $L\leq_{(R,G)}(L,D)$.
Given a worst-case input $\phi$, $G_{1}^{Q}(\phi)$ runs $G(\phi)$ to get
random $\\{\phi_{j}\\}_{j=1}^{k}$. Then for $j=1,\ldots k$, $G_{1}^{Q}$
generates random $i_{j}\leftarrow[N]$, and runs Simon’s algorithm to find
$s_{i_{j}}$ efficiently. Then the queries to $A$ are
$\\{i_{j},s_{i_{j}},\phi_{j}\\}_{j=1}^{k}$, which are correctly distributed
according to $\hat{D}_{1}$. Therefore $A$ will respond correctly with
$\\{\phi_{j}\overset{?}{=}1\\}$. Then $R_{1}^{Q}$ runs the decision procedure
$R$, which correctly decides $\phi$. ∎

######  Remark 2.

We have designed $O$ to encode exponentially many instances of Simon’s problem
for the technicality of _non-uniform_ reductions. Because otherwise, a
classical reduction could hardwire the solution $s$ and make use of an
average-case solver.

Construction 2. We give another separation example. It is still in the oracle
setting, and we need to make an additional assumption. What we gain is that
the quantum reduction does not need quantum access to the oracle, as opposed
to Example 1 where we need to run Simon’s algorithm with quantum access to the
oracle.

######  Assumption 2.

There exists a classically secure one-way function $f:X\to Y$, which is
invertible by an efficient quantum algorithm.

A natural candidate would be adaption of Factorization. Let
$(p,q)\leftarrow\textsf{Gen}(1^{n})$ be an efficient algorithm that generates
two large primes at random, and define $f(p,q)=pq$. Then it is reasonable to
assume that there exists a Gen algorithm relative to which $f$ is hard to
invert. In fact this is necessary for the RSA assumption, which is the basis
of modern public-key cryptography. This assumption is hence likely to be true
given the current state of art.

Given a function $f$ as in Assumption 2, we define an oracle $H:i\mapsto
y_{i}$ for $i\in[N]$. Here we sample $z_{i}\leftarrow X$ randomly and set
$y_{i}:=f(z_{i})$.

  * •

$L_{2}=\textsc{TQBF}=\\{\phi=\phi(v_{1},\ldots,v_{n})\\}$ containing
satisfiable quantified $n$-variable formulae in 3-CNF. Let $L_{2}^{O}$ be the
language $L$ relative to oracle $H$, which ignores $H$.

  * •

$\hat{L}_{2}^{H}:=\\{x=(i,z,\phi):\text{$f(z)=y_{i}$ and $\phi$ is true}\\}$.
We associate $\hat{L}_{2}^{H}$ a distribution $\hat{D}_{2}$, which is uniform
on $[N]\times X$ and samples a formula according to $D$ (the distribution in
Assumption 1).

######  Remark 3.

For the same reason as above, we introduce the oracle $H$ to encode
superpolynomial-many instances of inverting $f$ to avoid a non-uniform
classical reduction that can hardwire solutions to (at most poly-many)
inversion instances.

Following similar arguments to Theorem 8.2, we can prove the theorem below.
The only change is that in the quantum reduction, we query _classically_ a
random index $i_{j}$ to $H$, and obtain $y_{i_{j}}$. Then we run Shor’s
quantum factorization algorithm to find $z_{i_{j}}:=f^{-1}(y_{i_{j}})$, and
then form correct queries to the solver of $(\hat{L}_{2}^{H},\hat{D}_{2})$.

######  Theorem 8.3.

Under Assumption 1 and 2, there does not exist a classical reduction from
$L_{2}^{H}$ to $(\hat{L}_{2}^{H},\hat{D}_{2})$. In contrast, there is a
quantum poly-time _non-adaptive_ reduction
$L_{2}^{H}\leq_{R_{2}^{Q},G_{2}^{Q}}(\hat{L}_{2}^{H},\hat{D}_{2})$.

## References

  * [AC02] Mark Adcock and Richard Cleve.  A quantum goldreich-levin theorem with cryptographic applications.  In Annual Symposium on Theoretical Aspects of Computer Science, pages 323–334. Springer, 2002.
  * [AD97] Miklós Ajtai and Cynthia Dwork.  A public-key cryptosystem with worst-case/average-case equivalence.  In Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing, STOC ’97, pages 284–293, 1997.
  * [AGGM06] Adi Akavia, Oded Goldreich, Shafi Goldwasser, and Dana Moshkovitz.  On basing one-way functions on np-hardness.  In Proceedings of the Thirty-eighth Annual ACM Symposium on Theory of Computing, STOC ’06, pages 701–710, 2006.
  * [Ajt96] Miklós Ajtai.  Generating hard instances of lattice problems (extended abstract).  In In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 99–108. ACM, 1996.
  * [BB15] Andrej Bogdanov and Christina Brzuska.  On basing size-verifiable one-way functions on np-hardness.  In Theory of Cryptography Conference, pages 1–6. Springer, 2015\.
  * [BL13] Andrej Bogdanov and Chin Ho Lee.  Limits of Provable Security for Homomorphic Encryption, pages 111–128.  Springer Berlin Heidelberg, 2013.
  * [Bra79] Gilles Brassard.  Relativized cryptography.  2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 00(undefined):383–391, 1979.
  * [BT06] Andrej Bogdanov and Luca Trevisan.  On worst-case to average-case reductions for NP problems.  SIAM Journal on Computing, 36(4):1119–1159, 2006.
  * [FF93] Joan Feigenbaum and Lance Fortnow.  Random-self-reducibility of complete sets.  SIAM Journal on Computing, 22(5):994–1005, 1993.  https://doi.org/10.1137/0222061.
  * [FKN90] Joan Feigenbaum, Sampath Kannan, and Noam Nisan.  Lower bounds on random-self-reducibility.  In Proceedings of Fifth Annual Structure in Complexity Theory Conference, pages 100–109. IEEE, 1990.  https://doi.org/10.1109/SCT.1990.113959.
  * [HMW14] Patrick Hayden, Kevin Milner, and Mark M. Wilde.  Two-message quantum interactive proofs and the quantum separability problem.  Quantum Info. Comput., 14(5&6):384–416, April 2014.
  * [JJUW11] Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous.  Qip= pspace.  Journal of the ACM (JACM), 58(6):30, 2011.  Preliminary version in STOC 2010.
  * [JUW09] Rahul Jain, Sarvagya Upadhyay, and John Watrous.  Two-message quantum interactive proofs are in PSPACE.  In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, pages 534–543, 2009.
  * [KLGN15] Hirotada Kobayashi, François Le Gall, and Harumichi Nishimura.  Generalized quantum arthur-merlin games.  In Proceedings of the 30th Conference on Computational Complexity, pages 488–511. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2015.
  * [KW00] Alexei Kitaev and John Watrous.  Parallelization, amplification, and exponential time simulation of quantum interactive proof systems.  In Proceedings of the Thirty-second Annual ACM Symposium on Theory of Computing, STOC ’00, pages 608–617, 2000.
  * [KY10] Akinori Kawachi and Tomoyuki Yamakami.  Quantum hardcore functions by complexity-theoretical quantum list decoding.  SIAM Journal on Computing, 39(7):2941–2969, 2010.
  * [LV15] Tianren Liu and Vinod Vaikuntanathan.  On basing private information retrieval on np-hardness.  Cryptology ePrint Archive, Report 2015/1061, 2015.  http://eprint.iacr.org/2015/1061.
  * [Mic04] Daniele Micciancio.  Almost perfect lattices, the covering radius problem, and applications to Ajtai’s connection factor.  SIAM Journal on Computing, 34(1):118–169, 2004.  Preliminary version in STOC 2002.
  * [MR07] Daniele Micciancio and Oded Regev.  Worst-case to average-case reductions based on gaussian measures.  SIAM J. Comput., 37(1):267–302, 2007.
  * [ORR13] Maris Ozols, Martin Roetteler, and Jérémie Roland.  Quantum rejection sampling.  ACM Trans. Comput. Theory, 5(3):11:1–11:33, August 2013.
  * [Reg04a] Oded Regev.  New lattice-based cryptographic constructions.  J. ACM, 51(6):899–942, 2004.
  * [Reg04b] Oded Regev.  Quantum computation and lattice problems.  SIAM J. Comput., 33(3):738–760, 2004.
  * [Reg05] Oded Regev.  On lattices, learning with errors, random linear codes, and cryptography.  In Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing, STOC ’05, pages 84–93, New York, NY, USA, 2005. ACM.
  * [Ros09] Bill Rosgen.  Computational distinguishability of quantum channels, 2009.
  * [Sch96] Benjamin Schumacher.  Sending entanglement through noisy quantum channels.  Physical Review A, 54(4):2614, 1996.
  * [Sim97] Daniel R Simon.  On the power of quantum computation.  SIAM journal on computing, 26(5):1474–1483, 1997.  https://doi.org/10.1137/S0097539796298637. Preliminary version in FOCS 1994.
  * [VDHI06] Wim Van Dam, Sean Hallgren, and Lawrence Ip.  Quantum algorithms for some hidden shift problems.  SIAM Journal on Computing, 36(3):763–778, 2006.