YITP-18-05

# Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the
second level of the Fourier hierarchy

Tomoyuki Morimae<EMAIL_ADDRESS>Yukawa Institute for
Theoretical Physics, Kyoto University, Kitashirakawa Oiwakecho, Sakyo-ku,
Kyoto 606-8502, Japan  Department of Computer Science, Gunma University, 1-5-1
Tenjincho, Kiryu, Gunma, 376-0052, Japan  JST, PRESTO, 4-1-8 Honcho,
Kawaguchi, Saitama, 332-0012, Japan  Yuki Takeuchi
<EMAIL_ADDRESS>Graduate School of Engineering Science, Osaka
University, Toyonaka, Osaka 560-8531, Japan  NTT Communication Science
Laboratories, NTT Corporation, 3-1 Morinosato Wakamiya, Atsugi, Kanagawa
243-0198, Japan  Harumichi Nishimura<EMAIL_ADDRESS>Graduate
School of Informatics, Nagoya University, Furocho, Chikusaku, Nagoya, Aichi,
464-8601, Japan

###### Abstract

We introduce a simple sub-universal quantum computing model, which we call the
Hadamard-classical circuit with one-qubit (HC1Q) model. It consists of a
classical reversible circuit sandwiched by two layers of Hadamard gates, and
therefore it is in the second level of the Fourier hierarchy FH . We show that
output probability distributions of the HC1Q model cannot be classically
efficiently sampled within a multiplicative error unless the polynomial-time
hierarchy collapses to the second level. The proof technique is different from
those used for previous sub-universal models, such as IQP, Boson Sampling, and
DQC1, and therefore the technique itself might be useful for finding other
sub-universal models that are hard to classically simulate. We also study the
classical verification of quantum computing in the second level of the Fourier
hierarchy. To this end, we define a promise problem, which we call the
probability distribution distinguishability with maximum norm (PDD-Max). It is
a promise problem to decide whether output probability distributions of two
quantum circuits are far apart or close. We show that PDD-Max is BQP-complete,
but if the two circuits are restricted to some types in the second level of
the Fourier hierarchy, such as the HC1Q model or the IQP model, PDD-Max has a
Merlin-Arthur system with quantum polynomial-time Merlin and classical
probabilistic polynomial-time Arthur.

##  I Introduction

###  I.1 Quantum supremacy of the HC1Q model

The Fourier hierarchy FH  is a hierarchy of restricted quantum circuits. The
$k$th level of the Fourier hierarchy, FHk, is the class of quantum circuits
with $k$ layers of Hadamard gates and all other gates preserving the
computational basis. The second level, FH2, is the most important, because
circuits in FH2 are used in many algorithms, such as Simon’s algorithm Simon
and Shor’s factoring algorithm Shor . The instantaneous quantum polynomial-
time (IQP) model BJS ; BMS  is also in FH2:

######  Definition 1 (IQP)

The IQP model on $N$ qubits is the following quantum computing model:

  * 1.

The initial state is $|0^{N}\rangle$.

  * 2.

The unitary $H^{\otimes N}DH^{\otimes N}$ is applied. Here $H$ is the Hadamard
gate, and $D$ is a quantum circuit consisting of only $Z$-diagonal gates, such
as $Z$, $CZ$, $CCZ$, and $e^{i\theta Z}$, etc.

  * 3.

All qubits are measured in the computational basis.

The IQP model is a well-known example of sub-universal quantum computing
models whose output probability distributions cannot be classically
efficiently sampled unless the polynomial-time hierarchy collapses. Since a
collapse of the polynomial-time hierarchy is considered as highly unlikely in
computer science, it shows the hardness of classically simulating the IQP
model. Other sub-universal models that exhibit similar quantum supremacy are
also known, such as the depth four model TD , the Boson sampling model AA ,
the DQC1 model KL ; MFF ; M ; Kobayashi ; KobayashiICALP , the Fourier
sampling model BU , the conjugated Clifford model AFK , and the random circuit
model random .

The first main result of the present paper is to add another simple model in
FH2 to the above list of sub-universal models that exhibit quantum supremacy.
We define the Hadamard-classical circuit with one-qubit (HC1Q) model as
follows:

######  Definition 2 (HC1Q)

The Hadamard-classical circuit with one-qubit (HC1Q) model on $N$ qubits is
the following quantum computing model (see Fig. 1(a)):

  * 1.

The initial state is $|0^{N}\rangle$.

  * 2.

$H^{\otimes(N-1)}\otimes I$ is applied.

  * 3.

A polynomial-time uniformly-generated classical reversible circuit

$\displaystyle C:\\{0,1\\}^{N}\ni w\mapsto C(w)\in\\{0,1\\}^{N}$

is applied “coherently”.

  * 4.

$H^{\otimes(N-1)}\otimes I$ is applied.

  * 5.

All qubits are measured in the computational basis.

Figure 1:  (a) The HC1Q model. $M$ is the computational-basis measurement. A
single line with the slash represents a set of $N-1$ qubits. The Hadamard gate
$H$ is applied on each qubit. The measurement $M$ is done on each qubit. (b)
The circuit similar to HC1Q model, but the last $|0\rangle$ qubit is removed.
(c) The generalization of the HC1Q model, which we call the HC$m$Q model.

We show that the HC1Q model is universal with a postselection. More precisely,
we show the following:

###### Theorem 3

Let $U$ be a polynomial-time uniformly-generated quantum circuit acting on $n$
qubits that consists of $poly(n)$ number of Hadamard gates and classical
reversible gates, such as $X$, CNOT, and Toffoli. Then from $U$ we can
efficiently construct an HC1Q circuit on $N=poly(n)$ qubits such that a
postselection on some output qubits generates the state $U|0^{n}\rangle$.

Since Hadamard plus classical gates are universal, Theorem 3 shows that HC1Q
model is universal with a postselection. A proof of the theorem is given in
Sec. II. The proof is based on a new idea that is different from those used in
the previous results TD ; BJS ; AA ; MFF . Proofs for the depth-four model TD
, the Boson sampling model AA , and the IQP model BJS  use gadgets that insert
gates in a post hoc way by using postselections. (For example, the IQP model
is not universal because Hadamard gates can be applied only in the first layer
and the last layer, but the so-called Hadamard gadget BJS  enables
realizations of Hadamard gates in any place of the IQP model by using
postselections.) The proof for the DQC1 model MFF  uses a postselection to
initialize the maximally-mixed state $I^{\otimes n}/2^{n}$ to the pure state
$|0^{n}\rangle$. As is explained in Sec. II, our proof is different from
those: from $U$, we first construct a polynomial-time non-deterministic
algorithm. From the polynomial-time non-deterministic algorithm, we next
construct a classical deterministic polynomial-time circuit $C$. We finally
show that the HC1Q circuit $(H^{\otimes N-1}\otimes I)C(H^{\otimes N-1}\otimes
I)$ can generate $U|0^{n}\rangle$ with a postselection. This idea itself seems
to be useful for finding other new sub-universal models that exhibit quantum
supremacy. We do not know relations between our technique and previous ones.

By using the arguments of Ref. BJS ; MFF ; AA , we obtain the following
corollary of Theorem 3, which is quantum supremacy of the HC1Q model:

###### Corollary 4

Output probability distributions of the HC1Q model cannot be classically
efficiently sampled within a multiplicative error $\epsilon<1$ unless the
polynomial-time hierarchy collapses to the third level.

Here, we say that a probability distribution $\\{p_{z}\\}_{z}$ is classically
efficiently sampled within a multiplicative error $\epsilon$ if there exists a
classical probabilistic polynomial-time algorithm such that

$\displaystyle|p_{z}-q_{z}|\leq\epsilon p_{z}$

for all $z$, where $q_{z}$ is the probability that the algorithm outputs $z$.

The corollary demonstrates an interesting “phase transition” between classical
and quantum. To see it, let us consider the circuit of Fig. 1(b), which is
obtained by removing the last $|0\rangle$ qubit of the HC1Q model (Fig. 1(a)).
Here,

$\displaystyle C^{\prime}:\\{0,1\\}^{N-1}\ni w\mapsto
C^{\prime}(w)\in\\{0,1\\}^{N-1}$

is a polynomial-time uniformly-generated classical reversible circuit. The
circuit of Fig. 1(b) is trivially classically simulatable, since $C^{\prime}$
is a permutation on $\\{0,1\\}^{N-1}$ and therefore

$\displaystyle
C^{\prime}|+\rangle^{\otimes(N-1)}=\frac{1}{\sqrt{2^{N-1}}}\sum_{x\in\\{0,1\\}^{N-1}}|C^{\prime}(x)\rangle=|+\rangle^{\otimes(N-1)},$

where $|+\rangle\equiv(|0\rangle+|1\rangle)/\sqrt{2}$. Our result therefore
suggests that the addition of a single $|0\rangle$ qubit to the trivial
circuit of Fig. 1(b) changes its complexity dramatically.

The third level collapse of the polynomial-time hierarchy for the depth-four
model, the Boson sampling model, the IQP model, and the DQC1 model can be
improved to the second level collapse Kobayashi ; KobayashiICALP . In Sec.
III, we show that the same improvement is possible for the HC1Q model:

###### Theorem 5

Output probability distributions of the HC1Q model cannot be classically
efficiently sampled within a multiplicative error $\epsilon<1$ unless the
polynomial-time hierarchy collapses to the second level.

A natural question is whether the above supremacy results still hold when the
number of qubits measured is much reduced. It is known that for the $N$-qubit
IQP model probability distributions of measurement results on $O(\log(N))$
number of qubits can be classically exactly sampled in polynomial time BJS .
In Sec. IV we show an analogous result for the HC1Q model:

###### Theorem 6

Probability distributions of measurement results on $O(\log(N))$ number of
qubits in the HC1Q model can be classically sampled in polynomial time within
a $1/poly(N)$ L1-norm error.

It is possible to extend this result to a generalized version of the HC1Q
model, which we call the HC$m$Q model:

######  Definition 7 (HC$m$Q)

The Hadamard-classical circuit with $m$-qubit (HC$m$Q) model on $N$ qubits is
the following quantum computing model (see Fig. 1(c)):

  * 1.

The initial state is $|0^{N}\rangle$.

  * 2.

$H^{\otimes(N-m)}\otimes I^{\otimes m}$ is applied.

  * 3.

A polynomial-time uniformly-generated classical reversible circuit

$\displaystyle C:\\{0,1\\}^{N}\ni w\mapsto C(w)\in\\{0,1\\}^{N}$

is applied “coherently”.

  * 4.

$H^{\otimes(N-m)}\otimes I^{\otimes m}$ is applied.

  * 5.

All qubits are measured in the computational basis.

###### Theorem 8

Probability distributions of measurement results on $O(\log(N))$ number of
qubits in the HC$m$Q model can be classically sampled in polynomial time
within a $1/poly(N)$ L1-norm error.

Its proof is omitted since it is similar to that of Theorem 6.

At this moment, we do not know which sub-universal model is the most promising
for experimental realizations, but the HC1Q model should be useful for certain
experimental setups due to its simple structure.

###  I.2 The verification of quantum computing in the second level of the
Fourier hierarchy

In this paper, we also study the classical verification of quantum computing.
It is a long-standing open problem whether quantum computing is classically
verifiable. More precisely, it is open whether any problem $L$ in BQP has an
interactive proof system with a quantum polynomial-time prover and a classical
probabilistic polynomial-time verifier.

###### Definition 9

We say that a problem $L$ has an interactive proof system with a quantum
polynomial-time prover if there exists a classical probabilistic polynomial-
time verifier such that

  * •

If $x\in L$ then there exists a quantum polynomial-time prover such that the
verifier accepts with probability at least $2/3$.

  * •

If $x\notin L$ then for any prover the verifier accepts with probability at
most $1/3$.

(Note that in this definition, the prover is in quantum polynomial-time only
for yes instances, i.e., when the prover is honest. For no instances, the
computational power of the malicious prover is unbounded.)

Answering the open question is important not only for practical applications
of cloud quantum computing but also for foundations of computer science and
quantum physics AharonovVazirani . In fact, several partial solutions to the
open problem have been obtained. They are categorized into the following four
types:

  * 1.

Several verification protocols MNS ; posthoc  and verifiable blind quantum
computing protocols FK ; Aharonov ; HM ; Broadbent ; Andru_review  demonstrate
that if the verifier has a weak quantum ability, such as preparations or
measurements of single-qubit quantum states, any BQP problem can be verified
with a quantum polynomial-time prover.

  * 2.

If multiple entangling quantum polynomial-time provers who are not
communicating with each other are allowed, any BQP problem is verified with a
classical polynomial-time verifier MattMBQC ; RUV ; Ji .

  * 3.

Since BQP is contained in IP defIP , a natural approach to the open problem is
to restrict the prover of IP to quantum polynomial-time when the problem is in
BQP. In fact, recently, a step in this line has been obtained in Ref.
AharonovGreen . The authors of Ref. AharonovGreen  have constructed a new
interactive proof system that verifies the value of the trace of operators
with a postBQP prover and a classical polynomial-time verifier.

  * 4.

It has been shown recently that the classical verification of quantum
computing is possible if a certain problem is assumed to be hard for quantum
computing Mahadev .

Actually, the answer to the open problem is unconditionally yes if we consider
specific BQP problems. For example, it is known that the recursive Fourier
sampling BV  has an interactive proof system with a quantum polynomial-time
prover and a classical polynomial-time verifier who communicate polynomial
number of messages MattFourier . Furthermore, it has been shown recently that
calculating orders of solvable groups has an interactive proof system with a
quantum polynomial-time prover and a classical polynomial-time verifier who
exchange two or three messages LeGall . Finally, it was suggested in Ref.
Tommaso  that a problem of deciding whether there exist some results that
occur with high probability or not for circuits in FH2 has a Merlin-Arthur
system with quantum polynomial-time Merlin.

###### Definition 10

We say that a problem $L$ has a Merlin-Arthur system with a quantum
polynomial-time Merlin if $L$ has an interactive proof system with a quantum
polynomial-time prover (Merlin) and a classical probabilistic polynomial-time
verifier (Arthur) where only a single message transmission is done from the
prover to the verifier.

The second main result of the present paper is to introduce another problem in
BQP that is classically verifiable. More precisely, we define the following
promise problem that we call Probability Distribution Distinguishability with
Maximum Norm (PDD-Max):

######  Definition 11 (PDD-Max)

Given a classical description of two quantum circuits $U_{1}$ and $U_{2}$
acting on $N$ qubits that consist of $poly(N)$ number of elementary gates, and
parameters $a$ and $b$ such that $0\leq b<a\leq 1$ and $a-b\geq 1/poly(N)$,
decide

  * •

YES: there exists $z\in\\{0,1\\}^{N}$ such that $|p_{z}-q_{z}|\geq a$.

  * •

NO: for any $z\in\\{0,1\\}^{N}$, $|p_{z}-q_{z}|\leq b$.

Here, $p_{z}\equiv|\langle z|U_{1}|0^{N}\rangle|^{2}$ and $q_{z}\equiv|\langle
z|U_{2}|0^{N}\rangle|^{2}$.

We first show that PDD-Max exactly characterizes the power of BQP:

###### Theorem 12

PDD-Max is BQP-complete (under polynomial-time many-one reduction).

Its proof is given in Sec. V. (Note that if two circuits are classical, PDD-
Max is BPP-complete; we have only to replace the controlled-$H$ gate in Fig. 3
with a controlled-random-bit-flip gate.)

We next show that if $U_{1}$ and $U_{2}$ of PDD-Max are restricted to the HC1Q
model, PDD-Max is classically verifiable:

###### Theorem 13

If two circuits $U_{1}$ and $U_{2}$ are in the form of the HC1Q model, PDD-Max
has a Merlin-Arthur system with quantum polynomial-time Merlin.

The proof of Theorem 13 is given in Sec. VI. A similar proof holds for the IQP
model and the HC$m$Q model (including the Simon-type circuits) (see Sec.
VII.1).

These results demonstrate that if we restrict the circuits of PDD-Max to the
form of the HC1Q model, it is another example of problems that is classically
verifiable. These results also suggest that such a restriction of PDD-Max is
not BQP-hard, since BQP is not believed to be in MA defMA .

The classical verifiability of PDD-Max for restricted circuits does not seem
to be directly related to the classical verification of quantum supremacy,
such as the verification of the IQP model, but it is an important future
research subject to explore any relation between them.

###  I.3 Preliminary

In this paper, we often use the following well known inequality:

######  Theorem 14 (Chernoff-Hoeffding bound)

Let $X_{1},...,X_{T}$ be identically and independently distributed real random
variables with $|X_{i}|\leq 1$ for every $i=1,...,T$. Then

$\displaystyle{\rm
Pr}\Big{[}\Big{|}\frac{1}{T}\sum_{i=1}^{T}X_{i}-E(X_{i})\Big{|}\leq\epsilon\Big{]}\geq
1-2e^{-\frac{T\epsilon^{2}}{2}}.$

In the following sections, we give proofs of theorems. In the last section,
Sec. VII, we provide some discussions.

##  II Proof of Theorem 3

In this section, we show Theorem 3. We are given a unitary operator

$\displaystyle U=u_{t}...u_{2}u_{1}$

acting on $n$ qubits, where $u_{i}$ is the Hadamard gate $H$ or a classical
gate for all $i=1,2,...,t$. From $U$, we define

$\displaystyle U^{\prime}\equiv u_{t+n}...u_{t+1}U,$

where $u_{t+i}$ is $H$ acting on $i$th qubit ($i=1,2,...,n$).

The outline of our proof is as follows. We first construct a polynomial-time
non-deterministic algorithm from $U^{\prime}$. We next define a polynomial-
time quantum unitary operator $W$, which consists of only classical gates,
from the polynomial-time non-deterministic algorithm. We finally show that the
HC1Q model of Fig. 2 that uses $W$ is universal with a postselection.

Figure 2:  The quantum circuit with a postselection. The first $h$ qubits, the
$(h+1)$th qubit, and the last qubit are postselected to $|0^{h}\rangle$,
$|1\rangle$, and $|1\rangle$, respectively.

Now let us consider the following polynomial-time non-deterministic algorithm.

  * 0.

The state of the register is represented by $(s,z)$, where $s\in\\{0,1\\}$ and
$z\in\\{0,1\\}^{n}$.

  * 1.

The initial state of the register is $(s=0,z=0^{n})$.

  * 2.

Repeat the following for $i=1,...,t+n$.

    * 2-a.

If $u_{i}$ is a classical gate (such as $X$, CNOT, or Toffoli) whose
corresponding action on $\\{0,1\\}^{n}$ is

$\displaystyle g:\\{0,1\\}^{n}\ni z\mapsto g(z)\in\\{0,1\\}^{n},$

update the state of the register as

$\displaystyle(s,z)\to(s,g(z)).$

    * 2-b.

If $u_{i}$ is $H$ acting on $j$th qubit, update the state of the register in
the following non-deterministic way:

$\displaystyle(s,z)\to\left\\{\begin{array}[]{ll}(s,z_{1},...,z_{j-1},0,z_{j+1},...,z_{n})\\\
(s\oplus z_{j},z_{1},...,z_{j-1},1,z_{j+1},...,z_{n}).\end{array}\right.$

Let us define $h$ by

$\displaystyle
h\equiv\big{|}\\{i\in\\{1,2,...,t+n\\}~{}|~{}u_{i}=H\\}\big{|},$

i.e., $h$ is the number of $H$ appearing in $U^{\prime}$. The above
polynomial-time non-deterministic algorithm does the non-deterministic
transition $h$ times, and therefore the algorithm has $2^{h}$ computational
paths. We label each path by an $h$-bit string $y\in\\{0,1\\}^{h}$. We write
the final state of the register for the path $y\in\\{0,1\\}^{h}$ by
$(s(y),z(y))$, where $s(y)\in\\{0,1\\}$ and $z(y)\in\\{0,1\\}^{n}$. Then, we
obtain

$\displaystyle
U^{\prime}|0^{n}\rangle=\frac{1}{\sqrt{2^{h}}}\sum_{y\in\\{0,1\\}^{h}}(-1)^{s(y)}|z(y)\rangle.$
(2)

(To help the readers understand the derivation of Eq. (2), we provide a simple
example in Appendix A.)

Note that, for each $y$, we can calculate $s(y)$ and $z(y)$ in classical
polynomial-time. Let us define the polynomial-time unitary operator $W$ by

$\displaystyle
W(|y\rangle\otimes|0\rangle\otimes|0^{n}\rangle)=|y\rangle\otimes|s(y)\rangle\otimes|z(y)\rangle.$

It is easy to see that $W$ can be constructed with only classical gates. Now
we show that the state $H^{\otimes n}U^{\prime}|0^{n}\rangle=U|0^{n}\rangle$
can be generated by the HC1Q model of Fig. 2 that uses $W$ with a
postselection. In Fig. 2, the state immediately before the postselection is

$\displaystyle\frac{1}{\sqrt{2^{n+h+1}}}\sum_{y\in\\{0,1\\}^{h}}(H^{\otimes
h}|y\rangle)\otimes(H|s(y)\rangle)\otimes(H^{\otimes
n}|z(y)\rangle)\otimes|1\rangle+|\psi\rangle\otimes|0\rangle,$ (3)

where $|\psi\rangle$ is a certain $(h+n+1)$-qubit state whose detail is
irrelevant keep . After the postselection, the state becomes

$\displaystyle\frac{1}{\sqrt{2^{h}}}\sum_{y\in\\{0,1\\}^{h}}(-1)^{s(y)}H^{\otimes
n}|z(y)\rangle=H^{\otimes n}U^{\prime}|0^{n}\rangle=U|0^{n}\rangle.$

Hence, we have shown that the HC1Q model of Fig. 2 with a postselection can
generate $U|0^{n}\rangle$ for any unitary $U$ that consists of Hadamard and
classical gates, which means that the HC1Q model is universal with a
postselection.

##  III Proof of Theorem 5

It was shown in Refs. Kobayashi ; KobayashiICALP  that the third level
collapse of the polynomial-time hierarchy for most of the sub-universal models
(including the depth-four model TD , the Boson sampling model AA , the IQP
model BJS , and the DQC1 model MFF ) is improved to the second level collapse.
The idea is to use the class NQP NQP  in stead of postBQP. NQP is a quantum
version of NP, and defined as follows:

######  Definition 15 (NQP)

A promise problem $A=(A_{yes},A_{no})$ is in NQP if and only if there exists a
polynomial-time uniformly-generated family $\\{V_{x}\\}_{x}$ of quantum
circuits such that if $x\in A_{yes}$ then $p_{acc}>0$, and if $x\in A_{no}$
then $p_{acc}=0$. Here $p_{acc}$ is the acceptance probability of $V_{x}$.

If we remember the following definition of NP, it is clear that NQP is a
quantum version of NP.

######  Definition 16 (NP)

A promise problem $A=(A_{yes},A_{no})$ is in NP if and only if there exists a
classical polynomial-time probabilistic algorithm such that if $x\in A_{yes}$
then $p_{acc}>0$, and if $x\in A_{no}$ then $p_{acc}=0$. Here $p_{acc}$ is the
acceptance probability of the classical algorithm.

By using a similar argument of Refs. Kobayashi ; KobayashiICALP , we now show
that the collapse of the polynomial-time hierarchy to the third level for the
HC1Q model can be improved to the second level. Let $A=(A_{yes},A_{no})$ be a
promise problem in NQP. Then there exists a polynomial-time uniformly-
generated family $\\{V_{x}\\}_{x}$ of quantum circuits that satisfies the
above definition of NQP. The outline of our proof is as follows: First, from
$V_{x}$, we construct an HC1Q circuit. Second, we assume that its output
probability distribution is classically efficiently sampled within a
multiplicative error $\epsilon<1$. Finally, we show that then $A$ is in NP,
which means ${\rm NQP}\subseteq{\rm NP}$. It collapses the polynomial-time
hierarchy to the second level, since

$\displaystyle{\rm PH}\subseteq{\rm BP}\cdot{\rm coC}_{=}{\rm P}={\rm
BP}\cdot{\rm NQP}={\rm BP}\cdot{\rm NP}={\rm AM}.$

Now let us give a more precise proof. In Sec. II, we have constructed the HC1Q
circuit of Fig. 2 from a given unitary $U$. Let us repeat the same argument by
replacing $U$ with $V_{x}$. In stead of doing the postselection on the state
of Eq. (3), let us do the projective measurement $\\{\Lambda,I^{\otimes
h+n+2}-\Lambda\\}$ on it, where

$\displaystyle\Lambda\equiv|0\rangle\langle 0|^{\otimes
h}\otimes|1\rangle\langle 1|\otimes|0\rangle\langle 0|\otimes I^{\otimes
n-1}\otimes|1\rangle\langle 1|.$

The probability $p_{\Lambda}$ of obtaining $\Lambda$ is

$\displaystyle p_{\Lambda}=\frac{\langle
0^{n}|V_{x}^{\dagger}(|0\rangle\langle 0|\otimes I^{\otimes
n-1})V_{x}|0^{n}\rangle}{2^{h+n+2}}.$

By the definition of NQP,

$\displaystyle\langle 0^{n}|V_{x}^{\dagger}(|0\rangle\langle 0|\otimes
I^{\otimes n-1})V_{x}|0^{n}\rangle>0$

when $x\in A_{yes}$ and

$\displaystyle\langle 0^{n}|V_{x}^{\dagger}(|0\rangle\langle 0|\otimes
I^{\otimes n-1})V_{x}|0^{n}\rangle=0$

when $x\in A_{no}$. It means that $p_{\Lambda}>0$ when $x\in A_{yes}$ and
$p_{\Lambda}=0$ when $x\in A_{no}$.

Assume that $p_{\Lambda}$ is classically efficiently sampled within a
multiplicative error $\epsilon<1$. It means that there exists a classical
polynomial-time probabilistic algorithm that outputs $0$ or $1$ such that

$\displaystyle|p_{\Lambda}-q_{0}|\leq\epsilon p_{\Lambda},$

where $q_{0}$ is the probability that the classical algorithm outputs 0
(accepts). Then, we can show that $A$ is in NP. In fact, if $x\in A_{yes}$
then

$\displaystyle q_{0}\geq(1-\epsilon)p_{\Lambda}>0.$

If $x\in A_{no}$ then

$\displaystyle q_{0}\leq(1+\epsilon)p_{\Lambda}=0.$

According to Definition 16, $A$ is therefore in NP.

##  IV Proof of Theorem 6

In this section, we show Theorem 6. For simplicity, we assume that the first
$k$ qubits are measured, where $k=O(\log N)$. Generalizations to other $k$
qubits are the same.

The outline of our proof is as follows. We first construct a probability
distribution $\\{q_{z}\\}_{z}$ that can be calculated in classical polynomial
time, and is close to $\\{p_{z}\\}_{z}$ within a $1/poly$ L1-norm. We then
show that we can sample $\\{q_{z}\\}_{z}$ in classical polynomial time.

Let us consider the circuit of Fig. 1 (a). As is shown in Appendix B, the
probability of obtaining the measurement result $z\in\\{0,1\\}^{k}$ for the
first $k$ qubits is

$\displaystyle p_{z}=\frac{1}{2^{N-1}}\sum_{x\in\\{0,1\\}^{N-1}}f(x),$ (4)

where

$\displaystyle f(x)$ $\displaystyle\equiv$
$\displaystyle\frac{1}{2^{k}}\sum_{y\in\\{0,1\\}^{N-1}}(-1)^{z\cdot
C_{1,...,k}(x0)+z\cdot
C_{1,...,k}(y0)}\delta_{C_{k+1,...,N}(x0),C_{k+1,...,N}(y0)}$ $\displaystyle=$
$\displaystyle\frac{1}{2^{k}}\sum_{y\in S}(-1)^{z\cdot C_{1,...,k}(x0)+z\cdot
C_{1,...,k}(y0)},$

$C_{1,...,k}(x0)$ is the first $k$ bits of $C(x0)$, $C_{k+1,...,N}(x0)$ is the
last $N-k$ bits of $C(x0)$, and $S\subseteq\\{0,1\\}^{N-1}$ is defined by

$\displaystyle S$ $\displaystyle\equiv$
$\displaystyle\\{y\in\\{0,1\\}^{N-1}~{}|~{}C_{k+1,...,N}(x0)=C_{k+1,...,N}(y0)\\}.$

The subset $S$ can be obtained in polynomial time in the following way:

  * 1.

Set $S=\\{\\}$.

  * 2.

Repeat the following for all $\alpha\in\\{0,1\\}^{k}$.

    * 2-1.

Calculate $C^{-1}(\alpha C_{k+1,...,N}(x0))$.

    * 2-2.

If $C^{-1}(\alpha C_{k+1,...,N}(x0))=y0$ for certain $y\in\\{0,1\\}^{N-1}$,
add $y$ to $S$.

  * 3.

End.

From the construction, $|S|\leq 2^{k}=poly(N)$. Therefore, the value of $f(x)$
is exactly computable in polynomial time for each $x$. Furthermore,
$|f(x)|\leq 1$ because

$\displaystyle|f(x)|\leq\frac{1}{2^{k}}\sum_{y\in S}|(-1)^{z\cdot
C_{1,...,k}(x0)+z\cdot C_{1,...,k}(y0)}|\leq 1.$

Let us generate random bit strings $x_{1},...,x_{T}\in\\{0,1\\}^{N-1}$. We
then calculate

$\displaystyle\tilde{p}_{z}\equiv\frac{1}{T}\sum_{i=1}^{T}f(x_{i}).$

Note that if we take $X_{i}=f(x_{i})$, then $E(X_{i})=p_{z}$, and therefore
from the Chernoff-Hoeffding bound,

$\displaystyle{\rm Pr}\Big{[}|\tilde{p}_{z}-p_{z}|\leq\epsilon\Big{]}\geq
1-2e^{-\frac{T\epsilon^{2}}{2}}.$

For any polynomial $r$, let us take $\epsilon=\frac{1}{5\times 2^{2k}r}$.
Given $\\{\tilde{p}_{z}\\}_{z}$, define the probability distribution
$\\{q_{z}\\}_{z}$ by

$\displaystyle
q_{z}\equiv\frac{|\tilde{p}_{z}|}{\sum_{z\in\\{0,1\\}^{k}}|\tilde{p}_{z}|}.$

Note that it is well defined, because

$\displaystyle\sum_{z\in\\{0,1\\}^{k}}|\tilde{p}_{z}|>0,$

which is shown as follows:

$\displaystyle\sum_{z\in\\{0,1\\}^{k}}|\tilde{p}_{z}|\geq\sum_{z\in\\{0,1\\}^{k}}\tilde{p}_{z}\geq\sum_{z\in\\{0,1\\}^{k}}(p_{z}-\epsilon)=1-2^{k}\epsilon=1-\frac{1}{5\times
2^{k}r}>0.$

Furthermore, $\\{q_{z}\\}_{z}$ is obtained in polynomial time. The distance
between $\\{p_{z}\\}_{z}$ and $\\{q_{z}\\}_{z}$ is

$\displaystyle\sum_{z\in\\{0,1\\}^{k}}|p_{z}-q_{z}|\leq 5\times
2^{2k}\epsilon=\frac{1}{r}.$

It is shown as follows. First,

$\displaystyle q_{z}$ $\displaystyle=$
$\displaystyle\frac{|\tilde{p}_{z}|}{\sum_{z\in\\{0,1\\}^{k}}|\tilde{p}_{z}|}$
$\displaystyle\leq$ $\displaystyle\frac{p_{z}+\epsilon}{1-2^{k}\epsilon}$
$\displaystyle=$
$\displaystyle(p_{z}+\epsilon)(1+2^{k}\epsilon+o(2^{k}\epsilon))$
$\displaystyle=$ $\displaystyle
p_{z}+p_{z}2^{k}\epsilon+p_{z}o(2^{k}\epsilon)+\epsilon+2^{k}\epsilon^{2}+\epsilon
o(2^{k}\epsilon)$ $\displaystyle\leq$ $\displaystyle p_{z}+5\times
2^{k}\epsilon.$

Second,

$\displaystyle q_{z}$ $\displaystyle=$
$\displaystyle\frac{|\tilde{p}_{z}|}{\sum_{z\in\\{0,1\\}^{k}}|\tilde{p}_{z}|}$
$\displaystyle\geq$ $\displaystyle\frac{p_{z}-\epsilon}{1+2^{k}\epsilon}$
$\displaystyle=$
$\displaystyle(p_{z}-\epsilon)(1-2^{k}\epsilon+o(2^{k}\epsilon))$
$\displaystyle=$ $\displaystyle
p_{z}-p_{z}2^{k}\epsilon+p_{z}o(2^{k}\epsilon)-\epsilon+2^{k}\epsilon^{2}-\epsilon
o(2^{k}\epsilon)$ $\displaystyle\geq$ $\displaystyle p_{z}-5\times
2^{k}\epsilon.$

In this way, we have shown that we can calculate in classical polynomial time
the probability distribution $\\{q_{z}\\}_{z}$ that is close to
$\\{p_{z}\\}_{z}$. Our final task is to show that $\\{q_{z}\\}_{z}$ can be
sampled in classical polynomial time. For simplicity, let us assume that each
$q_{z}$ is represented in the $m$-bit binary:

$\displaystyle q_{z}=\sum_{j=1}^{m}2^{-j}a_{z,j},$

where $a_{z,j}\in\\{0,1\\}$ for $j=1,2,...,m$. (Otherwise, by polynomially
increasing the size of $m$, we obtain exponentially good approximations.) The
following algorithm samples the probability distribution $\\{q_{z}\\}_{z}$.

  * 1.

Randomly generate an $m$-bit string $(w_{1},...,w_{m})\in\\{0,1\\}^{m}$.

  * 2.

Output $z\in\\{0,1\\}^{k}$ such that

$\displaystyle\sum_{y<z}q_{y}\leq\sum_{j=1}^{m}2^{-j}w_{j}<\sum_{y\leq
z}q_{y},$

where $y<z$ and $y\leq z$ mean the standard dictionary order. (For example,
for three bits, $000<001<010<011<100<101<110<111$.)

In summary, we have shown that $\\{p_{z}\\}_{z}$ can be sampled in polynomial
time within a $1/poly(N)$ L1-norm error.

##  V Proof of Theorem 12

In this section, we show Theorem 12. Our proof consists of two parts. In the
first subsection, we show that PDD-Max is BQP-hard. In the second subsection,
we show that PDD-Max is in BQP.

###  V.1 BQP-hardness

Let $A=(A_{yes},A_{no})$ be a promise problem in BQP. It means that there
exists a uniform family $\\{V_{x}\\}_{x}$ of polynomial-size quantum circuits
such that if $x\in A_{yes}$ then $V_{x}$ accepts with probability at least
$1-2^{-r}$, and if $x\in A_{no}$ then $V_{x}$ accepts with probability at most
$2^{-r}$, where $r$ is any polynomial. More precisely, let $V_{x}$ be the
polynomial-size quantum circuit, which acts on $n=poly(|x|)$ qubits,
corresponding to the instance $x$. If we write $V_{x}|0^{n}\rangle$ as

$\displaystyle
V_{x}|0^{n}\rangle=\sqrt{\alpha}|0\rangle\otimes|\phi_{0}\rangle+\sqrt{1-\alpha}|1\rangle\otimes|\phi_{1}\rangle$

with certain $(n-1)$-qubit states $|\phi_{0}\rangle$ and $|\phi_{1}\rangle$,
we have $\alpha\geq 1-2^{-r}$ when $x\in A_{yes}$, and $\alpha\leq 2^{-r}$
when $x\in A_{no}$. Let us consider the circuit of Fig. 3. We call it $U_{1}$.
We also define

$\displaystyle U_{2}\equiv H^{\otimes n+m+1}.$

We now show that deciding $x\in A_{yes}$ or $x\in A_{no}$ can be reduced to a
PDD-Max problem with $U_{1}$ and $U_{2}$, which means that PDD-Max is BQP-
hard. In fact, note that

$\displaystyle
U_{1}|0^{n+m+1}\rangle=\sqrt{\alpha}|0\rangle\otimes|0^{m}\rangle\otimes
V_{x}^{\dagger}(|0\rangle\otimes|\phi_{0}\rangle)+\sqrt{1-\alpha}|1\rangle\otimes|+\rangle^{\otimes
m}\otimes V_{x}^{\dagger}(|1\rangle\otimes|\phi_{1}\rangle).$

Let $p_{z}\equiv|\langle z|U_{1}|0^{n+m+1}\rangle|^{2}$ be the probability
that we obtain $z\in\\{0,1\\}^{n+m+1}$ when we measure all qubits of
$U_{1}|0^{n+m+1}\rangle$ in the computational basis. When $x\in A_{yes}$,

$\displaystyle p_{0^{n+m+1}}=|\langle
0^{n+m+1}|U_{1}|0^{n+m+1}\rangle|^{2}=\alpha|\langle
0^{n}|V_{x}^{\dagger}(|0\rangle\otimes|\phi_{0}\rangle)|^{2}=\alpha^{2}\geq(1-2^{-r})^{2}.$

When $x\in A_{no}$,

$\displaystyle p_{0y}$ $\displaystyle=$ $\displaystyle|\langle
0y|U_{1}|0^{n+m+1}\rangle|^{2}=\alpha\Big{|}\langle
y|\Big{[}|0^{m}\rangle\otimes
V_{x}^{\dagger}(|0\rangle\otimes|\phi_{0}\rangle)\Big{]}\Big{|}^{2}\leq\alpha\leq
2^{-r}$ $\displaystyle p_{1y}$ $\displaystyle=$ $\displaystyle|\langle
1y|U_{1}|0^{n+m+1}\rangle|^{2}=2^{-m}(1-\alpha)|\langle
y_{m+1},...,y_{n+m}|V_{x}^{\dagger}(|1\rangle\otimes|\phi_{1}\rangle)|^{2}\leq
2^{-m}$

for any $y\in\\{0,1\\}^{n+m}$. Let $q_{z}\equiv|\langle
z|U_{2}|0^{n+m+1}\rangle|^{2}$, where $z\in\\{0,1\\}^{n+m+1}$. Since
$U_{2}=H^{\otimes n+m+1}$, it is obvious that $q_{z}=\frac{1}{2^{n+m+1}}$ for
any $z$. Therefore, when $x\in A_{yes}$,

$\displaystyle|p_{0^{n+m+1}}-q_{0^{n+m+1}}|=\Big{|}p_{0^{n+m+1}}-\frac{1}{2^{n+m+1}}\Big{|}\geq(1-2^{-r})^{2}-2^{-(n+m+1)},$

and when $x\in A_{no}$,

$\displaystyle|p_{z}-q_{z}|$ $\displaystyle=$
$\displaystyle\Big{|}p_{z}-\frac{1}{2^{n+m+1}}\Big{|}$ $\displaystyle\leq$
$\displaystyle p_{z}+\frac{1}{2^{n+m+1}}$ $\displaystyle\leq$
$\displaystyle\max(2^{-m},2^{-r})+2^{-(n+m+1)}$

for any $z\in\\{0,1\\}^{n+m+1}$. In this way, we have shown that PDD-Max is
BQP-hard.

Figure 3:  The circuit $U_{1}$ used to show the BQP-hardness of PDD-Max.

###  V.2 In BQP

We next show that PDD-Max is in BQP. We show that the following BQP algorithm
solves PDD-Max with a $1/poly(N)$ completeness-soundness gap (i.e., the gap of
acceptance probabilities between the yes-instances and the no-instances is
lowerbounded by $1/poly(N)$):

  * 1.

Flip a fair coin $s\in\\{0,1\\}$. Generate $U_{s+1}|0^{N}\rangle$, and measure
each qubit in the computational basis. Let $z\in\\{0,1\\}^{N}$ be the
measurement result.

  * 2.

Repeat the following for $i=1,2,...,T$, where $T$ is a polynomial of $N$
specified later.

    * 2-a.

Generate $U_{1}|0^{N}\rangle$, and measure all qubits in the computational
basis. If the result is $z$, then set $X_{i}=1$. Otherwise, set $X_{i}=0$.

  * 3.

Calculate

$\displaystyle\tilde{p}_{z}\equiv\frac{1}{T}\sum_{i=1}^{T}X_{i}.$

Note that $E(X_{i})=1\times p_{z}+0\times(1-p_{z})=p_{z}$, where
$p_{z}\equiv|\langle z|U_{1}|0^{N}\rangle|^{2}$. Therefore, from the Chernoff-
Hoeffding bound, $|\tilde{p}_{z}-p_{z}|\leq\epsilon$ with probability larger
than $1-2e^{-\frac{T\epsilon^{2}}{2}}$. In a similar way, calculate the
estimator $\tilde{q}_{z}$ of $q_{z}\equiv|\langle z|U_{2}|0^{N}\rangle|^{2}$.
From the Chernoff-Hoeffding bound, $|\tilde{q}_{z}-q_{z}|\leq\epsilon$ with
probability larger than $1-2e^{-\frac{T\epsilon^{2}}{2}}$.

  * 4.

Calculate $|\tilde{p}_{z}-\tilde{q}_{z}|$. If
$|\tilde{p}_{z}-\tilde{q}_{z}|\geq a-\frac{a-b}{4}$, accept. Otherwise,
reject.

The intuitive idea of this algorithm is as follows. By the definition of the
PDD-Max, if the answer of the PDD-Max is yes, there exists $z$ such that
$|p_{z}-q_{z}|$ is large. In this case, the probability of obtaining such $z$
in step 1 is large. Therefore let us assume that we obtain such $z$ in step 1.
The step 1 is, in other words, the process to find a candidate of the
solution. In steps 2 and 3, probabilities $p_{z}$ and $q_{z}$ are estimated by
using the Chernoff-Hoeffding bound. Finally, in step 4, we check whether
$|p_{z}-q_{z}|$ is indeed large, and accept with high probability since it is
actually large. If the answer of the PDD-Max is no, on the other hand, there
is no $z$ such that $|p_{z}-q_{z}|$ is large, and therefore in step 4 we do
not conclude that $|p_{z}-q_{z}|$ is large except for some failure
probability. (Note that for general $U_{1}$ and $U_{2}$, estimating $p_{z}$
and $q_{z}$ seems to require BQP power, since it seems to be necessary to
generate $U_{1}|0^{N}\rangle$ and $U_{2}|0^{N}\rangle$. We will see in the
next section that if $U_{1}$ and $U_{2}$ are restricted in FH2, the estimation
of $p_{z}$ and $q_{z}$ can be done in classical polynomial time, and therefore
PDD-Max has a Merlin-Arthur system with quantum polynomial-time Merlin.)

Now let us give a more precise proof that PDD-Max is in BQP. First, let us
consider the case when the answer to PDD-Max is YES. If $z$ obtained in step 1
satisfies $|p_{z}-q_{z}|\geq a$, and if $\tilde{p}_{z}$ and $\tilde{q}_{z}$
calculated in steps 2 and 3 satisfy $|\tilde{p}_{z}-p_{z}|\leq\frac{a-b}{8}$
and $|\tilde{q}_{z}-q_{z}|\leq\frac{a-b}{8}$, we definitely accept in step 4,
because

$\displaystyle a$ $\displaystyle\leq$ $\displaystyle|p_{z}-q_{z}|$
$\displaystyle\leq$ $\displaystyle|p_{z}-\tilde{p}_{z}|+|\tilde{p}_{z}-q_{z}|$
$\displaystyle\leq$
$\displaystyle|p_{z}-\tilde{p}_{z}|+|\tilde{p}_{z}-\tilde{q}_{z}|+|\tilde{q}_{z}-q_{z}|$
$\displaystyle\leq$
$\displaystyle|\tilde{p}_{z}-\tilde{q}_{z}|+\frac{a-b}{4},$

and therefore

$\displaystyle|\tilde{p}_{z}-\tilde{q}_{z}|\geq a-\frac{a-b}{4}.$

The probability $\eta$ of occurring such an event is calculated to be

$\displaystyle\eta$ $\displaystyle\equiv$ $\displaystyle{\rm Pr}[\mbox{$z$
obtained in step 1 satisfies $|p_{z}-q_{z}|\geq a$}]$ $\displaystyle\times{\rm
Pr}\Big{[}|\tilde{p}_{z}-p_{z}|\leq\frac{a-b}{8}\Big{]}\times{\rm
Pr}\Big{[}|\tilde{q}_{z}-q_{z}|\leq\frac{a-b}{8}\Big{]}$ $\displaystyle=$
$\displaystyle\Big{(}\sum_{z:|p_{z}-q_{z}|\geq
a}\frac{p_{z}+q_{z}}{2}\Big{)}\times{\rm
Pr}\Big{[}|\tilde{p}_{z}-p_{z}|\leq\frac{a-b}{8}\Big{]}\times{\rm
Pr}\Big{[}|\tilde{q}_{z}-q_{z}|\leq\frac{a-b}{8}\Big{]}$ $\displaystyle\geq$
$\displaystyle\frac{a}{2}\Big{(}1-2e^{-\frac{T(a-b)^{2}}{128}}\Big{)}^{2}$
$\displaystyle\geq$ $\displaystyle\frac{a}{2}(1-2e^{-k})^{2},$

where we have taken $T\geq\frac{128k}{(a-b)^{2}}$ and $k$ is any polynomial of
$N$. Therefore, the acceptance probability $p_{acc}$ of our protocol is
lowerbounded as

$\displaystyle p_{acc}\geq\eta\geq\frac{a}{2}(1-2e^{-k})^{2}\equiv\alpha.$

Next, let us consider the case when the answer to PDD-Max is NO. If
$|\tilde{p}_{z}-p_{z}|\leq\frac{a-b}{8}$ and
$|\tilde{q}_{z}-q_{z}|\leq\frac{a-b}{8}$, which occurs with probability
$\geq(1-2e^{-k})^{2}$, we definitely reject, because

$\displaystyle|\tilde{p}_{z}-\tilde{q}_{z}|$ $\displaystyle\leq$
$\displaystyle|\tilde{p}_{z}-p_{z}|+|p_{z}-\tilde{q}_{z}|$ $\displaystyle\leq$
$\displaystyle|\tilde{p}_{z}-p_{z}|+|p_{z}-q_{z}|+|q_{z}-\tilde{q}_{z}|$
$\displaystyle\leq$ $\displaystyle\frac{a-b}{4}+b$ $\displaystyle<$
$\displaystyle a-\frac{a-b}{4}.$

The rejection probability $p_{rej}$ is therefore lowerbounded as

$\displaystyle p_{rej}\geq(1-2e^{-k})^{2}.$

Therefore, the acceptance probability $p_{acc}$ is upperbounded as

$\displaystyle p_{acc}=1-p_{rej}\leq
1-(1-2e^{-k})^{2}=4e^{-k}-4e^{-2k}\equiv\beta.$

The completeness-soundness gap is therefore

$\displaystyle\alpha-\beta=\frac{a}{2}(1-2e^{-k})^{2}-(4e^{-k}-4e^{-2k})\geq\frac{1}{poly(N)}$

for sufficiently large $k$, which shows that PDD-Max is in BQP.

##  VI Proof of Theorem 13

In this section, we show Theorem 13. Before giving the proof, let us explain
the intuitive idea. In Sec. V.2, we have seen that PDD-Max is in BQP for
general $U_{1}$ and $U_{2}$. In step 1 of the algorithm, a candidate of the
solution, i.e., $z$ such that $|p_{z}-q_{z}|\geq a$, is obtained by doing
quantum computing. In step 2, another quantum computing is necessary to
estimate $p_{z}$ and $q_{z}$. In the following we will see that if $U_{1}$ and
$U_{2}$ are the HC1Q model, estimations of $p_{z}$ and $q_{z}$ can be done in
classical polynomial-time. Therefore, we can construct the following Merlin-
Arthur protocol with quantum polynomial-time Merlin:

  * 1.

Merlin does the step 1 of the protocol in Sec. V.2, i.e., Merlin generates $z$
and sends it to Arthur.

  * 2.

Arthur verifies $|p_{z}-q_{z}|$ is large.

Now let us show Theorem 13. Our Merlin-Arthur protocol with quantum
polynomial-time Merlin runs as follows.

  * 1.

If Merlin is honest, he flips a fair coin $s\in\\{0,1\\}$. He next generates
$U_{s+1}|0^{N}\rangle$, and measures each qubit in the computational basis to
obtain the result $z\in\\{0,1\\}^{N}$. He sends $z$ to Arthur. If Merlin is
malicious, his computational ability is unbounded, and what he sends to Arthur
can be any $N$ bit string.

  * 2.

Let $T$ be a polynomial of $N$ specified later. Arthur generates
$\\{x^{i}\\}_{i=1}^{T}$ and $\\{y^{i}\\}_{i=1}^{T}$, where each of
$x^{i}\in\\{0,1\\}^{N-1}$ and $y^{i}\in\\{0,1\\}^{N-1}$ is a uniformly and
independently chosen random $N-1$ bit string.

  * 3.

Arthur calculates

$\displaystyle\tilde{p}_{z}\equiv\frac{1}{T}\sum_{i=1}^{T}f(x^{i},y^{i}),$

where

$\displaystyle f(x,y)\equiv(-1)^{\sum_{j=1}^{N-1}[C_{j}(x0)\cdot
z_{j}+C_{j}(y0)\cdot z_{j}]}\delta_{C_{N}(x0),z_{N}}\delta_{C_{N}(y0),z_{N}}.$

Here,

$\displaystyle C:\\{0,1\\}^{N}\ni w\mapsto C(w)\in\\{0,1\\}^{N}$

is the classical circuit in $U_{1}$,

$\displaystyle x0\equiv(x_{1},...,x_{N-1},0),$

$C_{j}(x0)$ is the $j$th bit of $C(x0)\in\\{0,1\\}^{N}$, and $z_{j}$ is the
$j$th bit of $z\in\\{0,1\\}^{N}$. We call $\tilde{p}_{z}$ the estimator of
$p_{z}$. Note that $\tilde{p}_{z}$ can be calculated in classical $poly(N)$
time.

  * 4.

In a similar way, Arthur calculates the estimator $\tilde{q}_{z}$ of $q_{z}$.
If

$\displaystyle|\tilde{p}_{z}-\tilde{q}_{z}|\geq a-\frac{a-b}{4},$

Arthur accepts. Otherwise, he rejects.

Note that

$\displaystyle p_{z}\equiv|\langle
z|U_{1}|0^{N}\rangle|^{2}=\frac{1}{2^{2(N-1)}}\sum_{x,y\in\\{0,1\\}^{N-1}}f(x,y).$
(5)

Its derivation is given in Appendix C. If we set $X_{i}=f(x^{i},y^{i})$, we
have

$\displaystyle
E(X_{i})=\frac{1}{2^{2(N-1)}}\sum_{x,y\in\\{0,1\\}^{N-1}}f(x,y)=p_{z}.$

Therefore, from the Chernoff-Hoeffding bound, the estimator $\tilde{p}_{z}$
satisfies $|\tilde{p}_{z}-p_{z}|\leq\epsilon$ with probability $\geq
1-2e^{-\frac{T\epsilon^{2}}{2}}$. For $\tilde{q}_{z}$, a similar result holds.
In the above protocol, the honest prover is enough to be quantum polynomial-
time.

Now we show that the above protocol can verify PDD-Max. The proof is similar
to that for the BQP case given in Sec. V. First, let us consider the case when
the answer to PDD-Max is yes. If the $z$ that Merlin sends to Arthur satisfies
$|p_{z}-q_{z}|\geq a$, and the estimators $\tilde{p}_{z}$ and $\tilde{q}_{z}$
that Arthur calculates satisfy $|\tilde{p}_{z}-p_{z}|\leq\frac{a-b}{8}$ and
$|\tilde{q}_{z}-q_{z}|\leq\frac{a-b}{8}$, Arthur definitely accepts, because

$\displaystyle|\tilde{p}_{z}-\tilde{q}_{z}|$ $\displaystyle\geq$
$\displaystyle|p_{z}-q_{z}|-|\tilde{p}_{z}-p_{z}|-|\tilde{q}_{z}-q_{z}|$
$\displaystyle\geq$ $\displaystyle a-\frac{a-b}{4}.$

Taking the honest prover in step 1, the probability $\eta$ of occurring such
an event is calculated to be

$\displaystyle\eta$ $\displaystyle\equiv$ $\displaystyle{\rm Pr}[\mbox{Merlin
obtains $z$ such that $|p_{z}-q_{z}|\geq a$}]$ $\displaystyle\times{\rm
Pr}\Big{[}|\tilde{p}_{z}-p_{z}|\leq\frac{a-b}{8}\Big{]}\times{\rm
Pr}\Big{[}|\tilde{q}_{z}-q_{z}|\leq\frac{a-b}{8}\Big{]}$ $\displaystyle=$
$\displaystyle\Big{(}\sum_{z:|p_{z}-q_{z}|\geq
a}\frac{p_{z}+q_{z}}{2}\Big{)}\times{\rm
Pr}\Big{[}|\tilde{p}_{z}-p_{z}|\leq\frac{a-b}{8}\Big{]}\times{\rm
Pr}\Big{[}|\tilde{q}_{z}-q_{z}|\leq\frac{a-b}{8}\Big{]}$ $\displaystyle\geq$
$\displaystyle\frac{a}{2}\Big{(}1-2e^{-\frac{T(a-b)^{2}}{128}}\Big{)}^{2}\geq\frac{a}{2}(1-2e^{-k})^{2},$

where we have taken $T\geq\frac{128k}{(a-b)^{2}}$ and $k$ is any polynomial of
$N$. Therefore, the probability $p_{acc}$ that Arthur accepts in our protocol
is lowerbounded as

$\displaystyle p_{acc}\geq\frac{a}{2}(1-2e^{-k})^{2}\equiv\alpha.$

Next, let us consider the case when the answer to PDD-Max is no. If
$|\tilde{p}_{z}-p_{z}|\leq\frac{a-b}{8}$ and
$|\tilde{q}_{z}-q_{z}|\leq\frac{a-b}{8}$, which occurs with probability
$\geq(1-2e^{-k})^{2}$, Arthur definitely rejects, because

$\displaystyle|\tilde{p}_{z}-\tilde{q}_{z}|$ $\displaystyle\leq$
$\displaystyle|\tilde{p}_{z}-p_{z}|+|p_{z}-q_{z}|+|q_{z}-\tilde{q}_{z}|$
$\displaystyle\leq$ $\displaystyle b+\frac{a-b}{4}<a-\frac{a-b}{4}.$

Therefore, the probability $p_{acc}$ that Arthur accepts in our protocol is
upperbounded as

$\displaystyle p_{acc}\leq 1-(1-2e^{-k})^{2}=4e^{-k}-4e^{-2k}\equiv\beta.$

The completeness-soundness gap is therefore

$\displaystyle\alpha-\beta=\frac{a}{2}(1-2e^{-k})^{2}-(4e^{-k}-4e^{-2k})\geq\frac{1}{poly(N)}$

for sufficiently large $k$, which shows that PDD-Max has a Merlin-Arthur
system with quantum polynomial-time Merlin.

Remarks. To conclude this section, we provide some remarks. Note that the fact
that $p_{z}$ and $q_{z}$ can be estimated in classical polynomial-time seems
to be a special property only for some circuits (such as those in FH2), and we
do not know how to do that for other general circuits. (In particular, in Sec.
VII.2, we will explain why the technique we use for FH2 circuits will not work
for other circuits, such as FH3 circuits.) Furthermore, note that what Arthur
can do is to estimate $p_{z}$ within an additive error given $z$: he cannot
sample $\\{p_{z}\\}_{z}$. (If he can do it, he can solve factoring and Simon’s
problem, for example.)

##  VII Discussion

###  VII.1 Generalizations to other circuits

In the proof of Theorem 13 (Sec. VI), we have considered the HC1Q model.
Similar proofs hold for other circuits in FH2. For example, let us consider
the IQP model. For the IQP model, $f(x,y)$ is a complex-valued function, but
we can use the Chernoff-Hoeffding bound for complex random variables
introduced in Ref. NestSchwarz .

The other example is the HC$m$Q model. We can show a similar result for it. In
fact, the probability $p_{s,t}$ of obtaining the result
$(s,t)\in\\{0,1\\}^{N-m}\times\\{0,1\\}^{m}$ is

$\displaystyle
p_{s,t}=\frac{1}{2^{2(N-m)}}\sum_{x,y\in\\{0,1\\}^{N-m}}(-1)^{C_{1,...,N-m}(x0^{m})\cdot
s+C_{1,...,N-m}(y0^{m})\cdot
s}\delta_{t,C_{N-m+1,...,N}(x0^{m})}\delta_{t,C_{N-m+1,...,N}(y0^{m})},$

and therefore the Chernoff-Hoeffding bound argument can be used. Here,
$C_{1,...,N-m}(x0^{m})$ is the first $N-m$ bits of $C(x0^{m})$, and
$C_{N-m+1,...,N}(x0^{m})$ is the last $m$ bits of $C(x0^{m})$.

Furthermore, we would like to point out that PDD-Max can has a Merlin-Arthur
system with quantum polynomial-time Merlin for other circuits outside of FH2.
The essential point of our proof is that the output probability distributions,
$p_{z}$ and $q_{z}$, of $U_{1}$ and $U_{2}$ can be classically efficiently
estimated. This property itself is not restricted to circuits in FH2, and
therefore we believe that our results should hold for many other circuits
outside of FH2.

###  VII.2 FH3

FH2 circuits have nice structures such that $p_{z}$ and $q_{z}$ can be
estimated in classical polynomial-time. We do not know how to do the same
thing for other circuits such as those in FH3. The reason is as follows. From
a similar calculation given in Appendix C, we can show that the probability
$p_{z}\equiv|\langle z|U|0^{N}\rangle|^{2}$ for an FH3 circuit $U$ satisfies

$\displaystyle p_{z}=\frac{1}{2^{M}}\sum_{x\in\\{0,1\\}^{M}}f(x)$

for certain $M=poly(N)$ and a certain function $f$. However, in this case, we
no longer have $|f(x)|\leq 1$, but $f$ is exponentially increasing as a
function of $N$: $f(x)=2^{s(N)}g(x)$, where $|g(x)|\leq 1$ and $s$ is a
polynomial. Then, by using the Chernoff-Hoeffding bound, we can obtain an
estimator $\xi$ that satisfies

$\displaystyle\Big{|}\xi-\frac{1}{2^{M}}\sum_{x}g(x)\Big{|}\leq\epsilon$

with probability larger than $1-2e^{-\frac{T\epsilon^{2}}{2}}$. The above
inequality means

$\displaystyle\Big{|}\xi-\frac{p_{z}}{2^{s(N)}}\Big{|}\leq\epsilon,$

which also means

$\displaystyle|2^{s(N)}\xi-p_{z}|\leq 2^{s(N)}\epsilon.$

In order to make $2^{s(N)}\epsilon=O(1/poly(N))$, $\epsilon$ must be
exponentially small, which means that $T$ must be exponentially large.
Therefore, we cannot obtain a $1/poly(N)$-precision estimator of $p_{z}$ in
classical polynomial time. Note that it is known that as long as we use $f$ as
a black box, the Chernoff-Hoeffding type bounds are optimal (up to some
factors) Canetti . This is the reason why our previous proof does not work for
other circuits.

###### Acknowledgements.

We thank Keisuke Fujii, Seiichiro Tani, and Francois Le Gall for discussion.
TM is supported by JST ACT-I No.JPMJPR16UP, JST PRESTO, and the Grant-in-Aid
for Young Scientists (B) No.JP17K12637 of JSPS. YT is supported by the Program
for Leading Graduate Schools: Interactive Materials Science Cadet Program and
JSPS Grant-in-Aid for JSPS Research Fellow No.JP17J03503. HN is supported by
the Grant-in-Aid for Scientific Research (A) Nos.26247016, 16H01705 and (C)
No.16K00015 of JSPS.

##  Appendix A Example

Let us consider the simple example where $n=2$, $t=1$, and $U=u_{1}=X\otimes
I$. In this case, $U^{\prime}=u_{3}u_{2}u_{1}$, where

$\displaystyle u_{2}$ $\displaystyle=$ $\displaystyle H\otimes I,$
$\displaystyle u_{3}$ $\displaystyle=$ $\displaystyle I\otimes H.$

The computational tree that represents the non-deterministic algorithm
corresponding to $U^{\prime}$ is given in Fig. 4. Each Hadamard gate in
$U^{\prime}$ corresponds to a non-deterministic transition. The bit string $z$
represents a basis state, and the bit $s$ represents the sign of a basis
state. If we superpose $(-1)^{s(y)}|z(y)\rangle$ for all computational path
$y\in\\{0,1\\}^{2}$, we obtain

$\displaystyle\sum_{y\in\\{0,1\\}^{2}}(-1)^{s(y)}|z(y)\rangle=\Big{[}(-1)^{0}|00\rangle+(-1)^{0}|01\rangle+(-1)^{1}|10\rangle+(-1)^{1}|11\rangle\Big{]}=\sqrt{2^{2}}U^{\prime}|0^{2}\rangle.$

Figure 4:  The computational tree of the non-deterministic algorithm.

##  Appendix B Derivation of Eq. (4)

In this appendix, we show Eq. (4). The initial state is $|0^{N}\rangle$. We
first apply $H^{\otimes(N-1)}\otimes I$. Then the state becomes

$\displaystyle\frac{1}{\sqrt{2^{N-1}}}\sum_{x\in\\{0,1\\}^{N-1}}|x\rangle|0\rangle.$

We apply the classical gate $C$ to obtain

$\displaystyle\frac{1}{\sqrt{2^{N-1}}}\sum_{x\in\\{0,1\\}^{N-1}}|C(x0)\rangle.$

If we project this state onto $(H^{\otimes k}|z\rangle\langle z|H^{\otimes
k})\otimes I^{\otimes N-k}$, where $z\in\\{0,1\\}^{k}$, the state becomes

$\displaystyle\frac{1}{\sqrt{2^{N-1}}}\frac{1}{\sqrt{2^{k}}}\sum_{x\in\\{0,1\\}^{N-1}}(-1)^{C_{1,...,k}(x0)\cdot
z}(H^{\otimes k}|z\rangle)\otimes|C_{k+1,...,N}(x0)\rangle.$

If we calculate its norm, which is the probability $p_{z}$, we obtain Eq. (4).

##  Appendix C Derivation of Eq. (5)

In this appendix, we show Eq. (5). The initial state is $|0^{N}\rangle$. We
first apply $H^{\otimes(N-1)}\otimes I$. Then the state becomes

$\displaystyle\frac{1}{\sqrt{2^{N-1}}}\sum_{x\in\\{0,1\\}^{N-1}}|x\rangle|0\rangle.$

We apply the classical gate $C$ to obtain

$\displaystyle\frac{1}{\sqrt{2^{N-1}}}\sum_{x\in\\{0,1\\}^{N-1}}|C(x0)\rangle.$

We apply the final Hadamard $H^{\otimes(N-1)}\otimes I$ to obtain

$\displaystyle\frac{1}{2^{N-1}}\sum_{x,y\in\\{0,1\\}^{N-1}}(-1)^{\sum_{j=1}^{N-1}C_{j}(x0)\cdot
y_{j}}|y\rangle|C_{N}(x0)\rangle=U_{1}|0^{N}\rangle,$

where $C_{j}(x0)$ is the $j$th bit of $C(x0)$ and $y_{j}$ is the $j$th bit of
$y$. Therefore

$\displaystyle\langle
z|U_{1}|0^{N}\rangle=\frac{1}{2^{N-1}}\sum_{x\in\\{0,1\\}^{N-1}}(-1)^{\sum_{j=1}^{N-1}C_{j}(x0)\cdot
z_{j}}\delta_{C_{N}(x0),z_{N}},$

which finally gives Eq. (5)

$\displaystyle p_{z}=|\langle
z|U_{1}|0^{N}\rangle|^{2}=\frac{1}{2^{2(N-1)}}\sum_{x,y\in\\{0,1\\}^{N-1}}f(x,y).$

## References

  * (1) Y. Shi, Quantum and classical tradeoffs. Theoretical Computer Science 344, 335 (2005). DOI:10.1016/j.tcs.2005.03.053
  * (2) D. R. Simon, On the power of quantum computation. Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS 1994), p.116 (1994). DOI:10.1137/S0097539796298637
  * (3) P. Shor, Algorithms for quantum computation: discrete logarithms and factoring. Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS 1994), p.124 (1994). DOI:10.1109/SFCS.1994.365700
  * (4) M. J. Bremner, R. Jozsa, and D. J. Shepherd, Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proc. R. Soc. A 467, 459 (2011). DOI:10.1098/rspa.2010.0301
  * (5) M. J. Bremner, A. Montanaro, and D. J. Shepherd, Average-case complexity versus approximate simulation of commuting quantum computations. Phys. Rev. Lett. 117, 080501 (2016). DOI:10.1103/PhysRevLett.117.080501
  * (6) B. M. Terhal and D. P. DiVincenzo, Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games. Quant. Inf. Comput. 4, 134 (2004). DOI:10.26421/QIC4.2
  * (7) S. Aaronson and A. Arkhipov, The computational complexity of linear optics. Theory of Computing 9, 143 (2013). DOI:10.1145/1993636.1993682
  * (8) E. Knill, and R. Laflamme, Power of one bit of quantum information. Phys. Rev. Lett. 81, 5672 (1998). DOI:10.1103/PhysRevLett.81.5672
  * (9) T. Morimae, K. Fujii, and J. F. Fitzsimons, Hardness of classically simulating the one clean qubit model. Phys. Rev. Lett. 112, 130502 (2014). DOI:10.1103/PhysRevLett.112.130502
  * (10) T. Morimae, Hardness of classically sampling one clean qubit model with constant total variation distance error. Phys. Rev. A 96, 040302(R) (2017). DOI:10.1103/PhysRevA.96.040302
  * (11) K. Fujii, H. Kobayashi, T. Morimae, H. Nishimura, S. Tamate, and S. Tani, Impossibility of classically simulating one-clean-qubit computation. Phys. Rev. Lett. 120, 200502 (2018). DOI:10.1103/PhysRevLett.120.200502
  * (12) K. Fujii, H. Kobayashi, T. Morimae, H. Nishimura, S. Tamate, and S. Tani, Power of quantum computation with few clean qubits. Proceedings of 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), p.13:1. DOI:10.4230/LIPIcs.ICALP.2016.13
  * (13) B. Fefferman and C. Umans, The power of quantum Fourier sampling. arXiv:1507.05592
  * (14) A. Bouland, J. F. Fitzsimons, and D. E. Koh, Quantum advantage from conjugated Clifford circuits. Proceedings of the 33rd Computational Complexity Conference (CCC2018). DOI:10.4230/LIPIcs.CCC.2018.21
  * (15) A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani, On the complexity and verification of quantum random circuit sampling. Nat. Phys. 2018 DOI:10.1038/s41567-018-0318-2
  * (16) D. Aharonov and U. Vazirani, Is quantum mechanics falsifiable? A computational perspective on the foundations of quantum mechanics. arXiv:1206.3686
  * (17) T. Morimae, D. Nagaj, and N. Schuch, Quantum proofs can be verified using only single-qubit measurements. Phys. Rev. A 93, 022326 (2016). DOI:10.1103/PhysRevA.93.022326
  * (18) J. F. Fitzsimons, M. Hajdušek, and T. Morimae, Post hoc verification of quantum computation. Phys. Rev. Lett. 120, 040501 (2018). DOI:10.1103/PhysRevLett.120.040501
  * (19) J. F. Fitzsimons and E. Kashefi, Unconditionally verifiable blind computation. Phys. Rev. A 96, 012303 (2017). DOI:10.1103/PhysRevA.96.012303
  * (20) D. Aharonov, M. Ben-Or, E. Eban, and U. Mahadev, Interactive proofs for quantum computations. arXiv:1704.04487
  * (21) M. Hayashi and T. Morimae, Verifiable measurement-only blind quantum computing with stabilizer testing. Phys. Rev. Lett. 115, 220502 (2015). DOI:10.1103/PhysRevLett.115.220502
  * (22) A. Broadbent, How to verify quantum computation. Theory of Computing 14, 1 (2018). DOI:10.4086/toc.2018.v014a011
  * (23) A. Gheorghiu, T. Kapourniotis, and E. Kashefi, Verification of quantum computation: an overview of existing approaches. arXiv:1709.06984
  * (24) M. McKague, Interactive proofs for BQP via self-tested graph states. Theory of Computing 12, 1 (2016). DOI:10.4086/toc.2016.v012a003
  * (25) Z. Ji, Classical verification of quantum proofs. Proceedings of the 48th annual ACM symposium on Theory of Computing (STOC 2016) p.885 (2016). DOI:10.1145/2897518.2897634
  * (26) B. W. Reichardt, F. Unger, and U. Vazirani, Classical command of quantum systems. Nature 496, 456 (2013). DOI:10.1038/nature12035
  * (27) IP is the class of promise problems verified by an interactive proof system with a BPP verifier and a prover with unlimited computational ability.
  * (28) D. Aharonov and A. Green, A quantum inspired proof of ${\rm P}^{\\#{\rm P}}\subseteq{\rm IP}$. arXiv:1710.09078
  * (29) U. Mahadev, Classical verification of quantum computations. arXiv:1804.01082
  * (30) E. Bernstein and U. Vazirani, Quantum complexity theory. SIAM Journal on Computing 26, 1411 (1997). DOI:10.1137/S0097539796300921
  * (31) M. McKague, Interactive proofs with efficient quantum prover for recursive Fourier sampling. Chicago Journal of Theoretical Computer Science 6, 1 (2012). DOI:10.4086/cjtcs.0006
  * (32) T. F. Demarie, Y. Ouyang, and J. F. Fitzsimons, Classical verification of quantum circuits containing few basis changes. Phys. Rev. A 97, 042319 (2018). DOI:10.1103/PhysRevA.97.042319
  * (33) F. Le Gall, T. Morimae, H. Nishimura, and Y. Takeuchi, Interactive proofs with polynomial-time quantum prover for computing the order of solvable groups. arXiv:1805.03385
  * (34) Merlin-Arthur (MA) is the class of promise problems that can be verified by a BPP verifier and a prover whose computational ability is unlimited. In MA, the prover first sends a bit string to the verifier, and the verifier then does the computing for the verification.
  * (35) Note that the $(n+1)$-qubit Toffoli gate in Fig. 2 can be implemented with a polynomially many Toffoli gates by using ancilla qubits Barenco . It is known that ancilla qubits do not need to be initialized Barenco . Therefore, we can use $|+\rangle$ states as ancilla qubits, which keeps the circuit of Fig. 2 in the form of Fig. 1(a).
  * (36) A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, H. Weinfurter, Elementary gates for quantum computation. Phys. Rev. A 52 3457 (1995). DOI:10.1103/PhysRevA.52.3457
  * (37) L. M. Adleman, J. DeMarrais, and M. A. Huang, Quantum Computability. SIAM J. Comput. 26 1524 (1997). DOI:10.1137/S0097539795293639
  * (38) M. Schwarz and M. Van den Nest, Simulating quantum circuits with sparse output distributions. arXiv:1310.6749
  * (39) R. Canetti, G. Even, and O. Goldreich, Lower bounds for sampling algorithms for estimating the average. Information Processing Letters 53, 17 (1995).