text:
# Measurement of the relative branching ratio BR(𝚵_𝒄⁺→𝒑⁺𝑲⁻𝝅⁺)/BR(𝚵_𝒄⁺→𝚵⁻𝝅⁺𝝅⁺)

## Abstract

We report the observation of the Cabibbo suppressed decay $`\mathrm{\Xi }_c^+pK^{}\pi ^+`$ using data collected with the FOCUS spectrometer during the 1996–97 Fermilab fixed target run. We find a $`\mathrm{\Xi }_c^+`$ signal peak of $`202\pm 35`$ events. We have measured the relative branching ratios BR$`(\mathrm{\Xi }_c^+pK^{}\pi ^+)/`$BR$`(\mathrm{\Xi }_c^+\mathrm{\Xi }^{}\pi ^+\pi ^+)=0.234\pm 0.047\pm 0.022`$ and BR$`(\mathrm{\Xi }_c^+p\overline{K}^{}(892)^0)/`$BR$`(\mathrm{\Xi }_c^+pK^{}\pi ^+)=0.54\pm 0.09\pm 0.05`$.

The FOCUS Collaboration

thanks: Present Address: Instituto de Fisica y Matematicas, Universidad Michoacana de San Nicolas de Hidalgo, Morelia, Mich., Mexico 58040thanks: Present Address: Instituto de Física, Faculdad de Ingenierí a, Univ. de la República, Montevideo, Uruguaythanks: Present Address: Instituto de Física, Universidade Federal da Bahia, Salvador, Brazilthanks: Present Address: INFN sezione di Milano, Milano, Italythanks: Present Address: Instituto de Física, Universidad Autónoma de Puebla,thanks: Present Address: National Center for Atmospheric Research, Boulder, COthanks: Present Address: Vanderbilt University, Nashville, TN 37235thanks: Present Address: Korea Research Institute of Standards and Science, P.O.Box 102, Yusong-Ku, Taejon 305-600, South Koreathanks: Present Address: University of Colorado, Boulder 80309thanks: Present Address: Dipartimento di Chimica e Fisica per l’Ingegneria e per i Materiali, Universitá di Brescia and INFN sezione di Paviathanks: Present Address: Nat. Inst. of Phys and Nucl. Eng., Bucharest, Romaniathanks: Present Address: Lucent Technologythanks: Present Address: Adams State College, Alamosa, CO 81102

Much less is known about the decays and branching fractions of the charm baryons in comparison to the charm mesons; even less is known about charm baryons containing strange quarks. In this article, we confirm the existence of the Cabibbo-suppressed decay of the $`\mathrm{\Xi }_c^+`$ baryon: $`\mathrm{\Xi }_c^+pK^{}\pi ^+`$ (conjugate states should be implicitly assumed throughout this paper), which was observed for the first time only recently . We also provide new information on the two-body decay $`\mathrm{\Xi }_c^+p\overline{K}^{}(892)^0`$.

FOCUS is a high energy photo-production experiment at Fermilab designed to study charmed particle physics. Charmed hadrons were produced by the interaction of a photon beam on a beryllium oxide (BeO) target. Different target setups were used during the data taking; about 2/3 of the data were collected using a segmented BeO target interleaved with high resolution silicon detectors (TS). The decay products were reconstructed using a large acceptance multi-particle spectrometer. A vertex detector (SSD) composed of 12 planes of silicon was used to provide high resolution tracking in the region immediately downstream of the target, thus allowing the identification and separation of the charm production and decay vertices. Downstream of the SSD, tracking and momentum measurement were accomplished with five station of multi-wire proportional chambers and two large aperture magnets operated with opposite polarity. Three multi-cell Čerenkov counters operating in threshold mode allowed identification of charged electrons, pions, kaons, and protons over a large momentum range. The spectrometer also contained a hadron calorimeter, two electromagnetic calorimeters, and two muon detectors.

Events were selected which contained at least one identified proton track, one kaon track, and one pion track. The proton and pion had the same charge while the kaon had an opposite charge.

Due to a priori likelihoods, the tightest Čerenkov cuts were placed on the proton, the loosest cuts on the pion. The proton candidate was selected by requiring that the proton hypothesis was favored (by the Čerenkov analysis algorithm) over both the kaon and pion hypotheses by 0.7 and 4.0 units of likelihood, respectively. The kaon candidate was selected by requiring the kaon hypothesis to be favored over the pion hypothesis by 2.5 units of likelihood and not disfavoured by the proton hypothesis by more than 1 unit of likelihood. For the pion candidate, we required that the pion hypothesis was within 8.0 units of likelihood of the most likely hypothesis. A more detailed discussion of the Čerenkov analysis algorithm may be found elsewhere . All the candidate particles were also required to be inconsistent with a muon hypothesis using the muon detectors and also to be inconsistent with an electron-positron pair. Furthermore kaon candidates were required to have a momentum greater than 8 GeV/$`c`$.

Known meson reflections where another particle was misidentified as the proton were reduced by raising Čerenkov requirements on the proton candidate for combinations compatible with the decay modes $`(D_s^+),D^+,D_s^+K^+K^{}\pi ^+`$, and $`D^+K^{}\pi ^+\pi ^+`$. A significant background contribution from $`\varphi (1020)K^+K^{}`$ was suppressed in the same manner.

The process $`\mathrm{\Xi }_c^+\mathrm{\Xi }^{}\pi ^+\pi ^+`$ has been selected as the normalization channel. For this decay pions have been subjected to similar Čerenkov cuts to reduce systematics, while $`\mathrm{\Xi }^{}`$ hyperons were fully reconstructed via the channel $`\mathrm{\Xi }^{}\mathrm{\Lambda }^0\pi ^{}`$. The $`\mathrm{\Lambda }\pi `$ invariant mass was required to fall within three standard deviation of the known $`\mathrm{\Xi }^{}`$ mass.

After the candidate tracks were selected, the event was reconstructed using a candidate driven vertex algorithm which is described in detail elsewhere . The algorithm forms a secondary vertex from the candidate tracks and uses the total momentum vector as a seed to construct a primary vertex by intersecting the seed with other tracks in the event. The procedure returns the confidence level of the fits for the secondary (CLS) and primary (CLP) vertices plus the detachment significance between the two, $`\mathrm{}/\sigma _{\mathrm{}}`$, where $`\mathrm{}`$ is the distance between the vertices and $`\sigma _{\mathrm{}}`$ is its error. In this analysis, the $`\mathrm{}/\sigma _{\mathrm{}}`$ variable is the most powerful tool in extracting the charm signal from the background. The same algorithm also returns an estimator of the relative isolation of the obtained vertices. This estimator (ISO1) is the confidence level that tracks forming the secondary vertex might instead come from the primary vertex. The described set of variables provides a good description of the topological configuration of the event such that an appropriate set of cuts on them effectively rejects the background.

We require $`\mathrm{}/\sigma _{\mathrm{}}>8`$ as a compromise between the requirements to have good statistics and a good signal to noise ratio. The same vertexing cuts, CLS$`1\%`$, CLP$`1\%`$, and ISO1$`<95\%`$ were used for both the Cabibbo suppressed channel and the normalization channel. For the Cabibbo suppressed decay we further require the proper time resolution of the candidate to be less than 75 fs. Also, the primary vertex is required to have at least two tracks in addition to the charm seed.

Using these selection criteria, we obtain the mass plots for the $`pK^{}\pi ^+`$ and $`\mathrm{\Xi }^{}\pi ^+\pi ^+`$ combinations shown in Figure 1 (a,b) respectively. In Figure 1 (a) the signal is clearly visible in the inset while in the full view the $`\mathrm{\Lambda }_c^+pK^{}\pi ^+`$ mode dominates. The fit to the invariant mass distribution is performed with a Gaussian function for the $`\mathrm{\Xi }_c^+pK^{}\pi ^+`$ signal and a straight line for the background. In Figure 1 (b) the fit to the $`\mathrm{\Xi }^{}\pi ^+\pi ^+`$ invariant mass distribution is also performed using a Gaussian signal and a linear background. The fits yield $`202\pm 35`$ events for the $`\mathrm{\Xi }_c^+pK^{}\pi ^+`$ channel and $`133\pm 14`$ events for the $`\mathrm{\Xi }_c^+\mathrm{\Xi }^{}\pi ^+\pi ^+`$ channel. A cleaner sample for the $`\mathrm{\Xi }_c^+pK^{}\pi ^+`$ can be achieved, as shown in Figure 2, by means of tighter Čerenkov cuts and a tighter requirement on the detachment significance $`\mathrm{}/\sigma _{\mathrm{}}`$.

The efficiencies for the two decay modes were determined using a Monte Carlo simulation. The efficiency ratio for the two modes was found to be $`\epsilon _{\mathrm{\Xi }^{}\pi ^+\pi ^+}/\epsilon _{pK^{}\pi ^+}=0.1539\pm 0.0033`$. Correcting by this factor, the branching ratio is calculated to be $`0.234\pm 0.047`$ (statistical error only).

Extensive systematic studies and consistency checks were performed on the branching ratio measurement. The behaviour of the $`\mathrm{\Xi }_c^+pK^{}\pi ^+`$ and $`\mathrm{\Xi }_c^+\mathrm{\Xi }^{}\pi ^+\pi ^+`$ signals with each of the cuts used in the analysis was investigated and compared to the Monte Carlo predictions. Also, split samples studies were performed which included separation into two different run periods, into particle and anti-particle, and into high and low momentum for the heaviest daughter particle. We checked that the results were consistent for different topologies for the reconstructed $`\mathrm{\Xi }^{}`$ hyperons and for different histogram binning and fit conditions. The results were compatible within errors with the quoted branching ratio. From all these studies, summarized in Figure 3 and in Table 1, we estimate an upper limit to the systematic error to be 0.022.

We have further investigated the resonant components of the $`\mathrm{\Xi }_c^+pK^{}\pi ^+`$ decay. Figure 4 (a) shows the Dalitz plot obtained for a value of $`\mathrm{}/\sigma _{\mathrm{}}>`$10. In the plot it is possible to recognize the presence of the $`\overline{K}^{}(892)^0`$ meson. Due to the relatively high background level the resonant components have been evaluated from the sideband subtracted two-body invariant mass spectra. No structures compatible with $`\mathrm{\Delta }`$ resonances have been observed (Figure 4 (b)), while we observe structures of excited hyperons in the regions around 1.6 GeV/$`c^2`$ and at the edge of phase space around 2.25 GeV/$`c^2`$ as shown in Figure 4 (c). However, they are not stable enough against variations in the analysis cuts and changes in the selection of sideband regions for us to quote branching fractions for them. Thus we limited our consideration to the resonant component of the $`\mathrm{\Xi }_c^+pK^{}\pi ^+`$ where the $`K^{}`$ and $`\pi `$ form a $`\overline{K}^{}(892)^0`$ meson (Figure 4 (d)). The signal has been normalized using the value from the fitted three body invariant mass plot. All the fits were performed using Breit-Wigner distributions for the signals and linear backgrounds. the signal widths have been constrained to those predicted by the Monte Carlo. The Monte Carlo simulation indicated a small (6%) difference in efficiency between the resonant and non-resonant components of the decay which has been taken into account. We determine the branching ratio to be: $`\mathrm{\Gamma }(\mathrm{\Xi }_c^+p\overline{K}^{}(892)^0)\mathrm{BR}(\overline{K}^{}(892)^0K^{}\pi ^+)/\mathrm{\Gamma }(\mathrm{\Xi }_c^+pK^{}\pi ^+)=0.36\pm 0.06`$ (stat). Assuming Isospin conservation in the process $`\overline{K}^{}(892)^0K\pi `$ we can correct this value for unobserved $`\overline{K}^0\pi ^0`$ decays, thus we get: $`\mathrm{\Gamma }(\mathrm{\Xi }_c^+p\overline{K}^{}(892)^0)/\mathrm{\Gamma }(\mathrm{\Xi }_c^+pK^{}\pi ^+)=0.54\pm 0.09(\mathrm{stat})`$. The consistency of the result has been tested using different sets of tighter cuts and different choices for the sidebands. Using the fit variant method on the obtained result we estimate an upper limit to the systematic error to be 0.03 when only charged decays are considered and 0.05 after the correction for the neutral process are taken into account.

In conclusion we determine the branching ratio of the Cabibbo suppressed channel $`\mathrm{\Xi }_c^+pK^{}\pi ^+`$ with respect to the Cabibbo favoured mode $`\mathrm{\Xi }_c^+\mathrm{\Xi }^{}\pi ^+\pi ^+`$ to be:

$$\mathrm{BR}\frac{(\mathrm{\Xi }_c^+pK^{}\pi ^+)}{(\mathrm{\Xi }_c^+\mathrm{\Xi }^{}\pi ^+\pi ^+)}=0.234\pm 0.047(\mathrm{stat})\pm 0.022(\mathrm{syst}).$$

This result is in good agreement with SELEX measurement , $`\mathrm{BR}(\mathrm{\Xi }_c^+pK^{}\pi ^+)/\mathrm{BR}(\mathrm{\Xi }_c^+\mathrm{\Xi }^{}\pi ^+\pi ^+)=0.20\pm 0.04\pm 0.02`$. We measure the relative branching ratio BR$`(\mathrm{\Xi }_c^+p\overline{K}^{}(892)^0)/`$BR$`(\mathrm{\Xi }_c^+pK^{}\pi ^+)`$:

$$\mathrm{BR}\frac{(\mathrm{\Xi }_c^+p\overline{K}^{}(892)^0)}{(\mathrm{\Xi }_c^+pK^{}\pi ^+)}=0.54\pm 0.09(\mathrm{stat})\pm 0.05(\mathrm{syst})$$

and detect the presence of ($`Kp`$) hyperon formations, but no evidence of $`\mathrm{\Delta }`$ isobars.

We wish to acknowledge the assistance of the staffs of Fermi National Accelerator Laboratory, the INFN of Italy and the physics department of the collaborating institutions. This research was supported in part by the U. S. National Science Foundation, the U. S. Department of Energy, the Italian Istituto Nazionale di Fisica Nucleare and Ministero dell’Università e della Ricerca Scientifica e Tecnologica, the Brazilian Conselho Nacional de Desenvolvimento Científico e Tecnológico, CONACyT-México, the Korean Ministry of Education, and the Korean Science and Engineering Foundation.


format: text

text:
# Quantum Multi-Prover Interactive Proof Systems with Limited Prior Entanglement

## 1 Introduction

After Deutsch  gave the first formal treatment of quantum computation, a number of papers have provided evidence that quantum computation has much more power than classical computation for solving certain computational tasks, including notable Shor’s integer factoring algorithm . Watrous  showed that it might be also the case for single-prover interactive proof systems, by constructing a constant-round quantum interactive protocol for a $`\mathrm{PSPACE}`$-complete language, which is impossible for classical interactive proof systems unless the polynomial-time hierarchy collapses to $`\mathrm{AM}`$ . A natural question to ask is how strong a quantum analogue of multi-prover interactive proof systems is. This paper gives the first step for this question, by proving that the class of languages having quantum multi-prover interactive proof systems is necessarily contained in non-deterministic exponential time ($`\mathrm{NEXP}`$), under the assumption that provers are allowed to share at most polynomially many prior-entangled qubits. This might even suggest that, under such an assumption, quantum multi-prover interactive proof systems are weaker than classical ones, since Cleve  reported that a pair of provers sharing polynomially many entangled qubits can in some sense cheat a classical verifier.

Interactive proof systems were introduced by Babai  and Goldwasser, Micali, and Rackoff . An interactive proof system consists of an interaction between a computationally unbounded prover and a polynomial-time probabilistic verifier. The prover attempts to convince the verifier that a given input string satisfies some property, while the verifier tries to verify the validity of the assertion of the prover. A language $`L`$ is said to have an interactive proof system if there exists a verifier $`V`$ such that (i) in the case the input is in $`L`$, there exists a prover $`P`$ that can convince $`V`$ with certainty, and (ii) in the case the input is not in $`L`$, no prover $`P^{}`$ can convince $`V`$ with probability more than $`1/2`$. It is well-known that the class of languages having interactive proof systems, denoted by $`\mathrm{IP}`$, is equal to $`\mathrm{PSPACE}`$, shown by Shamir  based on the work of Lund, Fortnow, Karloff, and Nisan , and on the result of Papadimitriou  (see also ).

Quantum interactive proof systems were introduced by Watrous  in terms of quantum circuits. He showed that every language in $`\mathrm{PSPACE}`$ has a quantum interactive protocol, with exponentially small one-sided error, in which the prover and the verifier exchange only three messages. A consecutive work of Kitaev and Watrous  showed that any quantum interactive protocol, even with two-sided bounded error, can be parallelized to a three-message quantum protocol with exponentially small one-sided error. They also showed that the class of languages having quantum interactive proof systems is necessarily contained in deterministic exponential time ($`\mathrm{EXP}`$).

A multi-prover interactive proof system, introduced by Ben-Or, Goldwasser, Kilian, and Wigderson , is an extension of a (single-prover) interactive proof system in which a verifier communicates with not only one but multiple provers, while provers cannot communicate with each other prover and cannot know messages exchanged between the verifier and other provers. A language $`L`$ is said to have a multi-prover interactive proof system if, for some $`k`$ denoting the number of provers, there exists a verifier $`V`$ such that (i) in the case the input is in $`L`$, there exist provers $`P_1,\mathrm{},P_k`$ that can convince $`V`$ with certainty, and (ii) in the case the input is not in $`L`$, no set of provers $`P_1^{},\mathrm{},P_k^{}`$ can convince $`V`$ with probability more than $`1/2`$. Babai, Fortnow, and Lund , combining the result by Fortnow, Rompel, and Sipser , showed that the class of languages having multi-prover interactive proof systems, denoted by $`\mathrm{MIP}`$, is equal to $`\mathrm{NEXP}`$. A sequence of papers by Cai, Condon, and Lipton , Feige , and Lapidot and Shamir  led to a result of Feige and Lovász  that every language in $`\mathrm{NEXP}`$ has a two-prover interactive proof system with just one round (i.e. two messages) of communication (meaning that the verifier sends one question to each of the provers in parallel, then receives their responses), with exponentially small one-sided error.

In this paper we first define quantum multi-prover interactive proof systems by naturally extending the quantum single-prover model. Perhaps the most important and interesting difference between quantum and classical multi-prover interactive proofs is that provers may share entanglement a priori. Particular cases are protocols with two provers initially sharing lots of EPR pairs. For the sake of generality, we may allow protocols with any number of provers and with any kind of prior entanglement, not limited to EPR-type ones. Although sharing classical randomness among provers does not change the power of classical multi-prover interactive proofs (unless zero-knowledge properties are taken into account ), sharing prior entanglement does have a possibility both to strengthen and to weaken the power of quantum multi-prover interactive proofs. In fact, while sharing prior entanglement may increase the power of cheating provers as shown by Cleve , it may be possible for a quantum verifier to turn the prior entanglement among provers to his advantage.

The main result of this paper is to show the $`\mathrm{NEXP}`$ upper bound for quantum multi-prover interactive proof systems under the assumption that provers are allowed to share at most polynomially many prior-entangled qubits. That is, polynomially many prior-entangled qubits among provers cannot be advantageous to a quantum verifier. As a special case of this result, it is proved that, if provers do not share any prior entanglement with each other, the class of languages having quantum multi-prover interactive proof systems is equal to $`\mathrm{NEXP}`$. Another result related to these is that, in the case the prover does not have his private qubits, the class of languages having quantum single-prover interactive proof systems is also equal to $`\mathrm{NEXP}`$. This special model of quantum single-prover interactive proofs can be regarded as a quantum counterpart of a probabilistic oracle machine  in the sense that there is no private space for the prover during the protocol, and thus we call this model as a quantum oracle circuit. Our result shows that quantumization of probabilistic oracle machines does not change the power of the model.

To prove the $`\mathrm{NEXP}`$ upper bound of quantum multi-prover interactive proof systems, a key idea is to bound the number of private qubits of provers without diminishing the computational power of them. Suppose that each prover has only polynomially many private qubits during the protocol. Then the total number of qubits of the quantum multi-prover interactive proof system is polynomially bounded, and we can show that it can be simulated classically in non-deterministic exponential time. Now the point is whether space-bounded quantum provers (i.e. provers can apply any unitary transformations on their spaces, but the number of qubits in their spaces is bounded polynomial with respect to the input length) are as powerful as space-unbounded quantum provers or not. Under the assumption that provers are allowed to share at most polynomially many prior-entangled qubits, we show that, even with only polynomially many private qubits, each prover can do everything that he could with as many qubits as he likes, in the sense that the verifier cannot distinguish the difference at all. For this, we also prove one fundamental property on quantum information theory using the entanglement measure introduced by Nielsen . Apart from quantum interactive proof systems, this property itself is also of interest and worth while stating.

The remainder of this paper is organized as follows. In Section 2 we briefly review basic notations and definitions in quantum computation and quantum information theory. In Section 3 we give a formal definition of quantum multi-prover interactive proof systems and quantum oracle circuits. In Section 4 we show our main result of the $`\mathrm{NEXP}`$ upper bound of quantum multi-prover interactive proof systems. In Section 5 we focus on the prior unentangled cases and on quantum oracle circuits. Finally we conclude with Section 6, which summarizes our results and mentions a number of open problems related to our work.

## 2 Quantum Fundamentals

Here we briefly review basic notations and definitions in quantum computation and quantum information theory. Detailed descriptions are, for instance, in .

A pure state is described by a unit vector in some Hilbert space. In particular, an $`n`$-dimensional pure state is a unit vector $`|\psi `$ in $`^n`$. Let $`\{|e_1,\mathrm{},|e_n\}`$ be an orthonormal basis for $`^n`$. Then any pure state in $`^n`$ can be described as $`_{i=1}^n\alpha _i|e_i`$ for some $`\alpha _1,\mathrm{},\alpha _n,_{i=1}^n|\alpha _i|^2=1`$.

A mixed state is a classical probability distribution $`(p_i,|\psi _i)`$, $`0p_i1`$, $`_ip_i=1`$ over pure states $`|\psi _i`$. This can be interpreted as being in the pure state $`|\psi _i`$ with probability $`p_i`$. A mixed state is often described in the form of a density matrix $`\rho =_ip_i|\psi _i\psi _i|`$. Any density matrix is positive semidefinite and has trace $`1`$.

If a unitary transformation $`U`$ is applied to a state $`|\psi `$, the state becomes $`U|\psi `$. In the form of density matrices, a state $`\rho `$ changes to $`U\rho U^{}`$ after $`U`$ is applied.

One of the important operations to density matrices is the trace-out operation. Given a density matrix $`\rho `$ over $`𝒦`$, the state after tracing out $`𝒦`$ is a density matrix over $``$ described by

$$\mathrm{tr}_𝒦\rho =\underset{i=1}{\overset{n}{}}(I_{}e_i|)\rho (I_{}|e_i)$$

for any orthonormal basis $`\{|e_1,\mathrm{},|e_n\}`$ of $`𝒦`$, where $`n`$ is the dimension of $`𝒦`$ and $`I_{}`$ is the identity operator over $``$. To perform this operation on some part of a quantum system gives a partial view of the quantum system with respect to the remaining part.

One of the important concepts in quantum physics is a measurement. Any collection of linear operators $`\{A_1,\mathrm{},A_k\}`$ satisfying $`_{i=1}^kA_i^{}A_i=I`$ defines a measurement. If a system is in a pure state $`|\psi `$, such a measurement results in $`i`$ with probability $`A_i|\psi ^2`$, and the state becomes $`A_i|\psi /A_i|\psi `$. If a system is in a mixed state with a density matrix $`\rho `$, the result $`i`$ is observed with probability $`\mathrm{tr}(A_i\rho A_i^{})`$, and the state after the measurement is with a density matrix $`A_i\rho A_i^{}/\mathrm{tr}(A_i\rho A_i^{})`$. A special class of measurements are projection or von Neumann measurements in which $`\{A_1,\mathrm{},A_k\}`$ is a collection of orthonormal projections. In this scheme, an observable is a decomposition of $``$ into orthogonal subspaces $`_1,\mathrm{},_k`$, that is, $`=_1\mathrm{}_k`$. It is important to note that two mixed states having the identical density matrix cannot be distinguished at all by any measurement.

For any linear operator $`A`$ over $``$, the $`l_2`$-norm of $`A`$ is defined by

$$A=\underset{|\psi \{0\}}{sup}\frac{A|\psi }{|\psi }.$$

## 3 Definitions

### 3.1 Polynomial-Time Uniformly Generated Families of Quantum Circuits

Similar to the model of quantum single-prover interactive proof systems discussed in , we define quantum multi-prover interactive proof systems in terms of quantum circuits. Before proceeding to the definition of quantum multi-prover interactive proof systems, we review the concept of polynomial-time uniformly generated families of quantum circuits.

A family $`\{Q_x\}`$ of quantum circuits is polynomial-time uniformly generated if there exists a deterministic procedure that, on every input $`x`$, outputs a description of $`Q_x`$ and runs in time polynomial in $`n=|x|`$. For simplicity, we assume all input strings are over the alphabet $`\mathrm{\Sigma }=\{0,1\}`$. It is assumed that the circuits in such a family are composed of gates in some reasonable, universal, finite set of quantum gates such as the Shor basis : Hadamard gates, $`\sqrt{\sigma _z}`$ gates, and Toffoli gates. Furthermore, it is assumed that the number of gates in any circuit is not more than the length of the description of that circuit. Therefore $`Q_x`$ must have size polynomial in $`n`$. For convenience, we may identify a circuit $`Q_x`$ with the unitary operator it induces.

It should be mentioned that to permit non-unitary quantum circuits, in particular, to permit measurements at any timing during the computation does not change the computational power of the model in view of time complexity. See  for a detailed description of the equivalence of the unitary and non-unitary quantum circuit models.

### 3.2 Quantum Multi-Prover Interactive Proof Systems

Here we give a formal definition of quantum multi-prover interactive proof systems which is a natural extension of quantum single-prover ones defined by Watrous . In fact, the model of quantum single-prover interactive proof systems discussed in  is a special case of our quantum multi-prover model with the restriction of the number of provers to one.

Let $`k`$ be the number of provers. For every input $`x\mathrm{\Sigma }^{}`$ of length $`n=|x|`$, the entire system of quantum $`k`$-prover interactive proof system consists of $`q(n)=q_𝒱(n)+_{i=1}^k(q__i(n)+q_{𝒫_i}(n))`$ qubits, where $`q_𝒱(n)`$ is the number of qubits that are private to a verifier $`V`$, each $`q_{𝒫_i}(n)`$ is the number of qubits that are private to a prover $`P_i`$, and each $`q__i(n)`$ is the number of message qubits used for communication between $`V`$ and $`P_i`$. Note that no communication is allowed between different provers $`P_i`$ and $`P_j`$. It is assumed that $`q_𝒱`$ and each $`q__i`$ are polynomially bounded functions. Moreover, without loss of generality, we may assume that $`q__1=\mathrm{}=q__k=q_{}`$ and $`q_{𝒫_1}=\mathrm{}=q_{𝒫_k}=q_𝒫`$. Accordingly, the entire system consists of $`q(n)=q_𝒱(n)+k(q_{}(n)+q_𝒫(n))`$ qubits.

Given polynomially bounded functions $`m,q_𝒱,q_{}:^+`$, an $`m`$-message $`(q_𝒱,q_{})`$-restricted quantum verifier $`V`$ for a quantum $`k`$-prover interactive proof system is a polynomial-time computable mapping of the form $`V:\mathrm{\Sigma }^{}\mathrm{\Sigma }^{}`$, where $`\mathrm{\Sigma }=\{0,1\}`$ is the alphabet set. For every input $`x\mathrm{\Sigma }^{}`$ of length $`n`$, $`V`$ uses at most $`q_𝒱(n)`$ qubits for his private space and at most $`q_{}(n)`$ qubits for communication with each prover. The string $`V(x)`$ is interpreted as a $`m(n)/2+1`$-tuple $`(V(x)_1,\mathrm{},V(x)_{m(n)/2+1})`$, with each $`V(x)_j`$ a description of a polynomial-time uniformly generated quantum circuit acting on $`q_𝒱(n)+kq_{}(n)`$ qubits. One of the private qubits of the verifier is designated as the output qubit.

Given polynomially bounded functions $`m,q_{}:^+`$ and a function $`q_𝒫:^+`$, an $`m`$-message $`(q_{},q_𝒫)`$-restricted quantum prover $`P_i`$ for each $`i=1,\mathrm{},k`$ is a mapping of the form $`P_i:\mathrm{\Sigma }^{}\mathrm{\Sigma }^{}`$. For every input $`x\mathrm{\Sigma }^{}`$ of length $`n`$, each $`P_i`$ uses at most $`q_𝒫(n)`$ qubits for his private space and at most $`q_{}(n)`$ qubits for communication with the verifier. The string $`P_i(x)`$ is interpreted as a $`m(n)/2+1/2`$-tuple $`(P_i(x)_1,\mathrm{},P_i(x)_{m(n)/2+1/2})`$, with each $`P_i(x)_j`$ a description of a quantum circuit acting on $`q_{}(n)+q_𝒫(n)`$ qubits. No restrictions are placed on the complexity of the mapping $`P_i`$ (i.e., each $`P_i(x)_j`$ can be an arbitrary unitary transformation). Furthermore, for some function $`q_{\mathrm{ent}}:^+`$ satisfying $`q_{\mathrm{ent}}q_𝒫`$, each $`P_i`$ may have at most $`q_{\mathrm{ent}}(n)`$ qubits among his private qubits that are prior-entangled with some private qubits of other provers. Such a prover $`P_i`$ is said $`q_{\mathrm{ent}}`$-prior-entangled. For the sake of generality, we allow any kind of prior entanglement, not limited to EPR-type ones.

An $`m`$-message $`(q_𝒱,q_{},q_𝒫)`$-restricted quantum $`k`$-prover interactive proof system consists of an $`m`$-message $`(q_𝒱,q_{})`$-restricted quantum verifier $`V`$ and $`m`$-message $`(q_{},q_𝒫)`$-restricted quantum provers $`P_1,\mathrm{},P_k`$. If $`P_1,\mathrm{},P_k`$ are $`q_{\mathrm{ent}}`$-prior-entangled, such a quantum $`k`$-prover interactive proof system is said $`q_{\mathrm{ent}}`$-prior-entangled. Let $`𝒱=l_2(\mathrm{\Sigma }^{q_𝒱})`$, each $`_i=l_2(\mathrm{\Sigma }^q_{})`$, and each $`𝒫_i=l_2(\mathrm{\Sigma }^{q_𝒫})`$ denote the Hilbert spaces corresponding to the private qubits of the verifier, the message qubits between the verifier and the $`i`$th prover, and the private qubits of the $`i`$th prover, respectively. Given a verifier $`V`$, provers $`P_1,\mathrm{},P_k`$, and an input $`x`$ of length $`n`$, we define a circuit $`(P_1(x),\mathrm{},P_k(x),V(x))`$ acting on $`q(n)`$ qubits as follows. If $`m(n)`$ is odd, circuits $`P_1(x)_1,\mathrm{},P_k(x)_1`$, $`V(x)_1`$, $`\mathrm{}`$, $`P_1(x)_{(m(n)+1)/2},\mathrm{},P_k(x)_{(m(n)+1)/2}`$, $`V(x)_{(m(n)+1)/2}`$ are applied in sequence, each $`P_i(x)_j`$ to $`_i𝒫_i`$, and each $`V(x)_j`$ to $`𝒱_1\mathrm{}_k`$. If $`m(n)`$ is even, circuits $`V(x)_1`$, $`P_1(x)_1,\mathrm{},P_k(x)_1`$, $`\mathrm{}`$, $`V(x)_{m(n)/2}`$, $`P_1(x)_{m(n)/2},\mathrm{},P_k(x)_{m(n)/2}`$, $`V(x)_{m(n)/2+1}`$ are applied in sequence. Figure 1 illustrates the situation for the case $`k=2`$ and $`m(n)=3`$. Note that the order of applications of the circuits of the provers at each round has actually no sense since the space $`_i𝒫_i`$ on which the circuits of the $`i`$th prover act is separated from each other prover.

At any given instant, the state of the entire system is a unit vector in the space $`𝒱_1\mathrm{}_k𝒫_1\mathrm{}𝒫_k`$. For instance, in the case $`m(n)=3`$, given an input $`x`$ of length $`n`$, the state of the system after all of the circuits of the provers and the verifier have been applied is

$$V_2P_{k,2}\mathrm{}P_{1,2}V_1P_{k,1}\mathrm{}P_{1,1}|\psi _{\mathrm{init}},$$

where each $`V_j`$ and $`P_{i,j}`$ denotes the extension of $`V(x)_j`$ and $`P_i(x)_j`$, respectively, to the space $`𝒱_1\mathrm{}_k𝒫_1\mathrm{}𝒫_k`$ by tensoring with the identity, and $`|\psi _{\mathrm{init}}𝒱_1\mathrm{}_k𝒫_1\mathrm{}𝒫_k`$ denotes the initial state. In the initial state $`|\psi _{\mathrm{init}}`$ for $`q_{\mathrm{ent}}`$-prior-entangled proof systems, only the first $`q_{\mathrm{ent}}(n)`$ qubits in each $`𝒫_i`$ may be entangled with other qubits in $`𝒫_1\mathrm{}𝒫_k`$. All the qubits other than these prior-entangled ones are initially in the $`|0`$-state.

For every input $`x`$, the probability that the $`(k+1)`$-tuple $`(P_1,\mathrm{},P_k,V)`$ accepts $`x`$ is defined to be the probability that an observation of the output qubit in the basis of $`\{|0,|1\}`$ yields $`|1`$, after the circuit $`(P_1(x),\mathrm{},P_k(x),V(x))`$ is applied to the initial state $`|\psi _{\mathrm{init}}`$.

Although $`k`$, the number of provers, has been treated to be constant so far, the above definition can be naturally extended to the case that $`k:^+`$ is a function of the input length $`n`$. In what follows, we treat $`k`$ as a function. Note that the number of provers possible to communicate with the verifier must be bounded polynomial in $`n`$.

###### Definition 1

Given polynomially bounded functions $`k,m:^+`$, a function $`q_{\mathrm{ent}}:^+`$, and functions $`a,b:^+[0,1]`$, a language $`L`$ is in $`\mathrm{QMIP}(k,m,q_{\mathrm{ent}},a,b)`$ iff there exist polynomially bounded functions $`q_𝒱,q_{}:^+`$ and an $`m`$-message $`(q_𝒱,q_{})`$-restricted quantum verifier $`V`$ for a quantum $`k`$-prover interactive proof system such that, for every input $`x`$ of length $`n`$,

* if $`xL`$, there exist a function $`q_𝒫:^+`$ satisfying $`q_𝒫q_{\mathrm{ent}}`$ and a set of $`k`$ quantum provers $`P_1,\mathrm{},P_k`$ of $`m`$-message $`(q_{},q_𝒫)`$-restricted $`q_{\mathrm{ent}}`$-prior-entangled such that $`(P_1,\mathrm{},P_k,V)`$ accepts $`x`$ with probability at least $`a(n)`$,
* if $`xL`$, for all functions $`q_𝒫^{}:^+`$ satisfying $`q_𝒫^{}q_{\mathrm{ent}}`$ and all sets of $`k`$ quantum provers $`P_1^{},\mathrm{},P_k^{}`$ of $`m`$-message $`(q_{},q_𝒫^{})`$-restricted $`q_{\mathrm{ent}}`$-prior-entangled, $`(P_1^{},\mathrm{},P_k^{},V)`$ accepts $`x`$ with probability at most $`b(n)`$.

Let $`\mathrm{QMIP}(poly,poly,q_{\mathrm{ent}},a,b)`$ denote the union of the classes $`\mathrm{QMIP}(k,m,q_{\mathrm{ent}},a,b)`$ over all polynomially bounded functions $`k`$ and $`m`$. The class $`\mathrm{QMIP}`$ of languages having quantum multi-prover interactive proof systems is defined as follows.

###### Definition 2

A language $`L`$ is in $`\mathrm{QMIP}`$ iff there exists a function $`q_{\mathrm{ent}}:^+`$ such that, for any function $`q_{\mathrm{ent}}^{}:^+`$ satisfying $`q_{\mathrm{ent}}^{}q_{\mathrm{ent}}`$, $`L`$ is in $`\mathrm{QMIP}(poly,poly,q_{\mathrm{ent}}^{},1,1/2)`$.

Next we define the class $`\mathrm{QMIP}^{(\mathrm{l}.\mathrm{e}.)}`$ of languages having quantum multi-prover interactive proof systems with at most polynomially many prior-entangled qubits.

###### Definition 3

A language $`L`$ is in $`\mathrm{QMIP}^{(\mathrm{l}.\mathrm{e}.)}`$ iff there exists a polynomially bounded function $`q_{\mathrm{ent}}:^+`$ such that, for any polynomially bounded function $`q_{\mathrm{ent}}^{}:^+`$ satisfying $`q_{\mathrm{ent}}^{}q_{\mathrm{ent}}`$, $`L`$ is in $`\mathrm{QMIP}(poly,poly,q_{\mathrm{ent}}^{},1,1/2)`$.

Finally we define the class $`\mathrm{QMIP}^{(\mathrm{n}.\mathrm{e}.)}`$ of languages having quantum multi-prover interactive proof systems without any prior entanglement.

###### Definition 4

A language $`L`$ is in $`\mathrm{QMIP}^{(\mathrm{n}.\mathrm{e}.)}`$ iff $`L`$ is in $`\mathrm{QMIP}(poly,poly,0,1,1/2)`$.

### 3.3 Quantum Oracle Circuits

Consider a situation in which a verifier can communicate with only one prover, but the prover does not have his private qubits. We call this model a quantum oracle circuit, since it can be regarded as a quantum counterpart of a probabilistic oracle machine  in the sense that there is no private space for the prover during the protocol.

For the definition of quantum oracle circuits, we use slightly different terminologies from those in the previous subsection so that they are fitted to the term ‘oracle’ rather than ‘prover’.

Given polynomially bounded functions $`m,q_𝒱,q_𝒪:^+`$, an $`m`$-oracle-call $`(q_𝒱,q_𝒪)`$-restricted quantum verifier $`V`$ for a quantum oracle circuit is a $`2m`$-message $`(q_𝒱,q_𝒪)`$-restricted quantum verifier for a quantum single-prover interactive proof system. A $`q_𝒪`$-restricted quantum oracle $`O`$ for an $`m`$-oracle-call $`(q_𝒱,q_𝒪)`$-restricted quantum verifier is a $`2m`$-message $`(q_𝒪,0)`$-restricted quantum prover. Figure 2 illustrates the situation of a two-oracle-call quantum oracle circuit. Note that our definition of a quantum oracle completely differs from the one by Bennett, Bernstein, Brassard, and Vazirani  in which a quantum oracle is restricted to a unitary transformation that maps $`|y,z`$ to $`|y,zf(y)`$ in one step for an arbitrary function $`f:\{0,1\}^{}\{0,1\}`$.

###### Definition 5

Given a polynomially bounded function $`m:^+`$ and functions $`a,b:^+[0,1]`$, a language $`L`$ is in $`\mathrm{QOC}(m,a,b)`$ iff there exist polynomially bounded functions $`q_𝒱,q_𝒪:^+`$ and an $`m`$-oracle-call $`(q_𝒱,q_𝒪)`$-restricted quantum verifier $`V`$ for a quantum oracle circuit such that, for every input $`x`$ of length $`n`$,

* if $`xL`$, there exists a $`q_𝒪`$-restricted quantum oracle $`O`$ for $`V`$ such that $`V`$ with access to $`O`$ accepts $`x`$ with probability at least $`a(n)`$,
* if $`xL`$, for all $`q_𝒪`$-restricted quantum oracles $`O^{}`$ for $`V`$, $`V`$ with access to $`O^{}`$ accepts $`x`$ with probability at most $`b(n)`$.

Let $`\mathrm{QOC}(poly,a,b)`$ denote the union of the classes $`\mathrm{QOC}(m,a,b)`$ over all polynomially bounded functions $`m`$. The class $`\mathrm{QOC}`$ of languages accepted by quantum oracle circuits is defined as follows.

###### Definition 6

A language $`L`$ is in $`\mathrm{QOC}`$ iff $`L`$ is in $`\mathrm{QOC}(poly,1,1/2)`$.

## 4 $`\mathrm{𝐐𝐌𝐈𝐏}^{\mathbf{(}𝐥\mathbf{.}𝐞\mathbf{.}\mathbf{)}}\mathbf{}\mathrm{𝐍𝐄𝐗𝐏}`$

Now we show that every language having a quantum multi-prover interactive proof system is necessarily in $`\mathrm{NEXP}`$ under the assumption that provers are allowed to share at most polynomially many prior-entangled qubits.

A key idea of our proof is to bound the number of private qubits of provers without diminishing the computational power of them. First, in Subsection 4.1, we explain our bounding technique with the single-prover case, which is much easier to understand. Although our result for the single-prover case only gives the $`\mathrm{NEXP}`$ upper bound for the class $`\mathrm{QIP}`$ of quantum single-prover interactive proofs, it will be much of help to understand our key idea of the proof for the multi-prover case in Subsection 4.2. For simplicity, in this section and after, we often drop the argument $`x`$ and $`n`$ in the various functions defined in the previous section. We also assume that operators acting on subsystems of a given system are extended to the entire system by tensoring with the identity, when it is clear from context upon what part of a system a given operator acts.

### 4.1 Single-Prover Case

First we show that, for any protocol of quantum single-prover interactive proof systems, there exists a quantum single-prover interactive protocol exchanging the same number of messages, in which the prover uses only polynomially many qubits for his private space with respect to input length, and the probability of acceptance is exactly equal to that of the original one. To show this, the following two theorems play very important roles. A point of our proof is how to combine and apply these two to the theory of quantum interactive proof systems.

###### Theorem 7 ()

Let $`|\varphi ,|\psi _1_2`$ satisfy $`\mathrm{tr}__2|\varphi \varphi |=\mathrm{tr}__2|\psi \psi |`$. Then there is a unitary transformation $`U`$ over $`_2`$ such that $`(I__1U)|\varphi =|\psi `$, where $`I__1`$ is the identity operator over $`_1`$.

###### Theorem 8 (, page 110)

Let $`\rho `$ be a density matrix over $`_1`$. Then there exist a Hilbert space $`_2`$ of $`dim(_2)=dim(_1)`$ and a pure state $`|\psi _1_2`$ such that $`\mathrm{tr}__2|\psi \psi |=\rho `$.

Now we give a proof of our claim.

###### Lemma 9

Let $`m,q_𝒱,q_{}:^+`$ be polynomially bounded functions and $`V`$ be an $`m`$-message $`(q_𝒱,q_{})`$-restricted quantum verifier for a quantum single-prover interactive proof system. Then, for any function $`q_𝒫:^+`$ and any $`m`$-message $`(q_{},q_𝒫)`$-restricted quantum prover $`P`$, there exists an $`m`$-message $`(q_{},q_𝒱+q_{})`$-restricted quantum prover $`P^{}`$ such that, for every input $`x`$, the probability of accepting $`x`$ by $`(P^{},V)`$ is exactly equal to the one by $`(P,V)`$.

Proof.  It is assumed that $`q_𝒫q_𝒱+q_{}`$, since there is nothing to show in the case $`q_𝒫<q_𝒱+q_{}`$. It is also assumed that the values of $`m`$ are even (odd cases can be dealt with a similar argument).

Given a protocol $`(P,V)`$ of an $`m`$-message $`(q_𝒱,q_{},q_𝒫)`$-restricted quantum single-prover interactive proof system, we construct an $`m`$-message $`(q_{},q_𝒱+q_{})`$-restricted quantum prover $`P^{}`$ such that the probability of acceptance by $`(P^{},V)`$ is exactly equal to the one by $`(P,V)`$ on every input. We construct $`P^{}`$ by showing, for every input $`x`$, how to construct each $`P_j^{}(x)`$ based on the original $`P_j(x)`$. In the following proof, each $`P_j(x)`$ and $`P_j^{}(x)`$ will be abbreviated as $`P_j`$ and $`P_j^{}`$, respectively.

Let $`𝒫^{}=l_2(\mathrm{\Sigma }^{q_{}+q_𝒱})`$ be the Hilbert space corresponding to the private qubits of $`P^{}`$. Let each $`|\psi _j,|\varphi _j𝒱𝒫`$, for $`1jm/2`$, denote a state of the original $`m`$-message $`(q_𝒱,q_{},q_𝒫)`$-restricted quantum interactive proof system defined in a recursive manner by

$$\begin{array}{cccc}|\varphi _1\hfill & =& V_1|\psi _{\mathrm{init}},\hfill & \\ |\varphi _j\hfill & =& V_jP_{j1}|\varphi _{j1},\hfill & 2jm/2,\hfill \\ |\psi _j\hfill & =& P_j|\varphi _j,\hfill & 1jm/2.\hfill \end{array}$$

Here $`|\psi _{\mathrm{init}}𝒱𝒫`$ is the initial state in which all the qubits are the $`|0`$-states. Notice that $`\mathrm{tr}_𝒫|\psi _j\psi _j|=\mathrm{tr}_𝒫|\varphi _j\varphi _j|`$ for each $`1jm/2`$, since each $`P_j`$ acts only on the qubits in $`𝒫`$.

From Theorem 8, there exist states $`|\psi _j^{},|\varphi _j^{}𝒱𝒫^{}`$ such that

$$\begin{array}{ccc}\mathrm{tr}_𝒫^{}|\varphi _j^{}\varphi _j^{}|\hfill & =& \mathrm{tr}_𝒫|\varphi _j\varphi _j|,\hfill \\ \mathrm{tr}_𝒫^{}|\psi _j^{}\psi _j^{}|\hfill & =& \mathrm{tr}_𝒫|\psi _j\psi _j|,\hfill \end{array}$$

for each $`1jm/2`$. Thus we have

$$\mathrm{tr}_𝒫^{}|\psi _j^{}\psi _j^{}|=\mathrm{tr}_𝒫|\psi _j\psi _j|=\mathrm{tr}_𝒫|\varphi _j\varphi _j|=\mathrm{tr}_𝒫^{}|\varphi _j^{}\varphi _j^{}|,$$

for each $`1jm/2`$.

Therefore, by Theorem 7, there exists a unitary transformation $`P_j^{}`$ acting on $`𝒫^{}`$ such that $`P_j^{}|\varphi _j^{}=|\psi _j^{}`$ for each $`1jm/2`$.

Having defined $`P_j^{}`$, $`|\varphi _j^{}`$, and $`|\psi _j^{}`$ for each $`1jm/2`$, compare the state just before the final measurement is performed in the original protocol and that in the constructed protocol. Let $`|\varphi _{m/2+1}=V_{m/2+1}|\psi _{m/2}`$ and $`|\varphi _{m/2+1}^{}=V_{m/2+1}|\psi _{m/2}^{}`$. These $`|\varphi _{m/2+1}`$ and $`|\varphi _{m/2+1}^{}`$ are exactly the states we want to compare. Noticing that $`\mathrm{tr}_𝒫|\psi _{m/2}\psi _{m/2}|=\mathrm{tr}_𝒫^{}|\psi _{m/2}^{}\psi _{m/2}^{}|`$, we have $`\mathrm{tr}_𝒫|\varphi _{m/2+1}\varphi _{m/2+1}|=\mathrm{tr}_𝒫|\varphi _{m/2+1}^{}\varphi _{m/2+1}^{}|`$, since $`V_{m/2+1}`$ acts only on $`𝒱`$. This implies that the verifier $`V`$ cannot distinguish $`|\varphi _{m/2+1}^{}`$ from $`|\varphi _{m/2+1}`$ at all. Hence, for every input $`x`$, the probability of accepting $`x`$ in the protocol $`(P^{},V)`$ is exactly equal to the one in the original protocol $`(P,V)`$. Thus we have the assertion. $`\mathrm{}`$

### 4.2 $`\mathrm{𝐐𝐌𝐈𝐏}^{\mathbf{(}𝐥\mathbf{.}𝐞\mathbf{.}\mathbf{)}}\mathbf{}\mathrm{𝐍𝐄𝐗𝐏}`$

In the proof of Lemma 9 we decomposed the Hilbert space of the proof system into $`𝒱`$ and $`𝒫`$ and used Theorem 8 by taking $`𝒱`$ as a Hilbert space $`_1`$ of Theorem 8. For $`k`$-prover cases, however, if we focus on one fixed prover $`P_i`$ and decompose the Hilbert space of the proof system into the private space of $`P_i`$ and the rest, Theorem 8 is of no help, because the number of qubits of the proof system out of $`𝒫_i`$ may be no longer bounded polynomial in input length. Instead of Theorem 8, we show the following theorem, which is useful even for $`k`$-prover cases.

###### Theorem 10

Fix a state $`|\varphi `$ in $`_1_2_3`$ and a unitary transformation $`U`$ over $`_2_3`$ arbitrarily, and let $`|\psi `$ denote $`(I__1U)|\varphi `$. Then, for any Hilbert space $`_3^{}`$ of $`dim(_3^{})dim(_3)`$ such that there is a state $`|\varphi ^{}`$ in $`_1_2_3^{}`$ satisfying $`\mathrm{tr}__3^{}|\varphi ^{}\varphi ^{}|=\mathrm{tr}__3|\varphi \varphi |`$, there exist a Hilbert space $`_3^{\prime \prime }`$ of $`dim(_3^{\prime \prime })=(dim(_2))^2dim(_3^{})`$ and a state $`|\psi ^{}`$ in $`_1_2_3^{\prime \prime }`$ such that $`\mathrm{tr}_{_3^{\prime \prime }}|\psi ^{}\psi ^{}|=\mathrm{tr}__3|\psi \psi |`$.

For the proof of Theorem 10, we use the entanglement measure introduced by Nielsen . Let us decompose a vector $`|\xi _1_2`$ into

$$|\xi =\underset{i,j}{}\alpha _{ij}|e_i^1|e_j^2,$$
(1)
where $`\{|e_i^1\}`$ and $`\{|e_i^2\}`$ are orthonormal bases of $`_1`$ and $`_2`$, respectively. Then the entanglement measure $`\mathrm{ent}_2(|\xi ,_1,_2)`$ is defined by the minimum number of non-zero terms in the right hand side of (1), where the minimum is taken over all the possible choices of the bases $`\{|e_i^1\}`$ and $`\{|e_i^2\}`$. The decomposition with the minimum number of non-zero terms is given by the Schmidt decomposition ,

$$|\xi =\underset{i}{}\beta _i|e_i^1|e_i^2,$$

where each $`|e_i^1`$ and $`|e_i^2`$ is a normalized eigenvector of $`\mathrm{tr}__1|\xi \xi |`$ and $`\mathrm{tr}__2|\xi \xi |`$, respectively. Therefore, the entanglement measure $`\mathrm{ent}_2(|\xi ,_1,_2)`$ is nothing but the minimum dimension of the Hilbert space $`_2^{}`$ such that there is a vector $`|\xi ^{}_1_2^{}`$ that satisfies $`\mathrm{tr}__2|\xi \xi |=\mathrm{tr}__2^{}|\xi ^{}\xi ^{}|`$.

We extend the definition of $`\mathrm{ent}_2(,,)`$ to a three-party case. For a vector $`|\zeta _1_2_3`$, define the three-party entanglement measure $`\mathrm{ent}_3(|\zeta ,_1,_2,_3)`$ as the minimum number of non-zero terms in the decomposition

$$|\zeta =\underset{i,j,k}{}\gamma _{ijk}|e_i^1|e_j^2|e_k^3,$$

where $`\{|e_i^j\}`$ denotes an orthonormal basis of the space $`_j`$ for each $`j=1,2,3`$.

Proof of Theorem 10 Since $`\mathrm{ent}_2(|\psi ,_1_2,_3)`$ gives the minimum dimension of $`_3^{\prime \prime }`$ such that there is a state $`|\psi ^{}_1_2_3^{\prime \prime }`$ satisfying $`\mathrm{tr}_{_3^{\prime \prime }}|\psi ^{}\psi ^{}|=\mathrm{tr}__3|\psi \psi |`$, it is sufficient to show that $`\mathrm{ent}_2(|\psi ,_1_2,_3)dim(_3^{})(dim(_2))^2`$. This can be proved as follows:

$`\mathrm{ent}_2(|\psi ,_1_2,_3)`$ $``$ $`\mathrm{ent}_3(|\psi ,_1,_2,_3)`$
$``$ $`\mathrm{ent}_3(|\varphi ,_1,_2,_3)dim(_2)`$
$``$ $`\mathrm{ent}_2(|\varphi ,_1_2,_3)(dim(_2))^2`$
$``$ $`dim(_3^{})(dim(_2))^2.`$
The first inequality directly comes from the definition of the entanglement measure. To prove the second and third inequalities, let $`|\varphi =_{i,j,k}\gamma _{ijk}|e_i^1|e_j^2|e_k^3`$ be the decomposition of $`|\varphi `$ with respect to the orthonormal bases $`\{|e_i^1\}`$, $`\{|e_i^2\}`$, and $`\{|e_i^3\}`$ of $`_1`$, $`_2`$, and $`_3`$, respectively, and let $`|\varphi =_i\beta _i|f_i^{1,2}|f_i^3`$ be that of $`|\varphi `$ with respect to the orthonormal bases $`\{|f_i^{1,2}\}`$ and $`\{|f_i^3\}`$ of $`_1_2`$ and $`_3`$, respectively. The second and third inequalities are the consequences of the equality

$$|\psi =\underset{i,j,k}{}\gamma _{ijk}|e_i^1U(|e_j^2|e_k^3)=\underset{i,j,k}{}\gamma _{ijk}|e_i^1\left(\underset{l=1}{\overset{dim(_2)}{}}\beta _{jkl}^{}|e_{jkl}^2|e_{jkl}^3\right)$$

and the equality

$$|\varphi =\underset{i}{}\beta _i|f_i^{1,2}|f_i^3=\underset{i}{}\beta _i\left(\underset{j=1}{\overset{dim(_2)}{}}\beta _{ij}^{\prime \prime }|f_{ij}^1|f_{ij}^2\right)|f_j^3,$$

respectively, where $`_{l=1}^{dim(_2)}\beta _{jkl}^{}|e_{jkl}^2|e_{jkl}^3`$ and $`_{j=1}^{dim(_2)}\beta _{ij}^{\prime \prime }|f_{ij}^1|f_{ij}^2`$ are the Schmidt decompositions of $`U(|e_j^2|e_k^3)`$ and $`|f_i^{1,2}`$, respectively. The fourth inequality is from the definition of the entanglement measure, which ensures that $`\mathrm{ent}_2(|\varphi ,_1_2,_3)dim(_3^{})`$ holds. $`\mathrm{}`$

Now we are ready to show the following lemma.

###### Lemma 11

Let $`k,m,q_𝒱,q_{},q_{\mathrm{ent}}:^+`$ be polynomially bounded functions and $`V`$ be an $`m`$-message $`(q_𝒱,q_{})`$-restricted quantum verifier for a quantum $`k`$-prover interactive proof system. Then, for any function $`q_𝒫:^+`$ satisfying $`q_𝒫q_{\mathrm{ent}}`$ and any set of $`m`$-message $`(q_{},q_𝒫)`$-restricted $`q_{\mathrm{ent}}`$-prior-entangled quantum provers $`P_1,\mathrm{},P_k`$, there exists a set of $`m`$-message $`(q_{},q_{\mathrm{ent}}+2m/2+1/2q_{})`$-restricted $`q_{\mathrm{ent}}`$-prior-entangled quantum provers $`P_1^{},\mathrm{},P_k^{}`$ such that, for every input $`x`$, the probability of accepting $`x`$ by $`(P_1^{},\mathrm{},P_k^{},V)`$ is exactly equal to the one by $`(P_1,\mathrm{},P_k,V)`$.

Proof.  It is assumed that $`q_𝒫q_{\mathrm{ent}}+2m/2+1/2q_{}`$, since there is nothing to show in the case $`q_𝒫<q_{\mathrm{ent}}+2m/2+1/2q_{}`$. It is also assumed that the values of $`m`$ are even, and thus $`2m/2+1/2q_{}=mq_{}`$ (odd cases can be dealt with a similar argument).

Given a protocol $`(P_1,\mathrm{},P_k,V)`$ of an $`m`$-message $`(q_𝒱,q_{},q_𝒫)`$-restricted $`q_{\mathrm{ent}}`$-prior-entangled quantum $`k`$-prover interactive proof system, we first show that $`P_1`$ can be replaced by an $`m`$-message $`(q_{},q_{\mathrm{ent}}+mq_{})`$-restricted $`q_{\mathrm{ent}}`$-prior-entangled quantum prover $`P_1^{}`$ such that the probability of acceptance by $`(P_1^{},P_2,\mathrm{},P_k,V)`$ is exactly equal to the one by $`(P_1,\mathrm{},P_k,V)`$ on every input. Having shown this, we repeat the same process for each of provers to construct a protocol $`(P_1^{},P_2^{},P_3,\mathrm{},P_k,V)`$ from $`(P_1^{},P_2,P_3,\mathrm{},P_k,V)`$ and so on, and finally we obtain a protocol $`(P_1^{},\mathrm{},P_k^{},V)`$ in which all of $`P_1^{},\mathrm{},P_k^{}`$ are $`m`$-message $`(q_{},q_{\mathrm{ent}}+mq_{})`$-restricted $`q_{\mathrm{ent}}`$-prior-entangled quantum provers. We construct $`P_1^{}`$ by showing, for every input $`x`$, how to construct each $`P_{1,j}^{}(x)`$ based on the original $`P_{1,j}(x)`$. In the following proof, each $`P_{i,j}(x)`$ and $`P_{i,j}^{}(x)`$ will be abbreviated as $`P_{i,j}`$ and $`P_{i,j}^{}`$, respectively.

Let each $`|\psi _j,|\varphi _j𝒱_1\mathrm{}_k𝒫_1\mathrm{}𝒫_k`$, for $`1jm/2`$, denote a state of the original $`m`$-message $`(q_𝒱,q_{},q_𝒫)`$-restricted $`q_{\mathrm{ent}}`$-prior-entangled quantum $`k`$-prover interactive proof system defined in a recursive manner by

$$\begin{array}{cccc}|\varphi _1\hfill & =& V_1|\psi _{\mathrm{init}},\hfill & \\ |\varphi _j\hfill & =& V_jP_{k,j1}\mathrm{}P_{1,j1}|\varphi _{j1},\hfill & 2jm/2,\hfill \\ |\psi _j\hfill & =& P_{1,j}|\varphi _j,\hfill & 1jm/2.\hfill \end{array}$$

Here $`|\psi _{\mathrm{init}}𝒱_1\mathrm{}_k𝒫_1\mathrm{}𝒫_k`$ is the initial state in which the first $`q_{\mathrm{ent}}(n)`$ qubits in each $`𝒫_j`$ may be entangled with private qubits of other provers than $`P_j`$. All the qubits other than these prior-entangled qubits are the $`|0`$-states in the state $`|\psi _{\mathrm{init}}`$. Note that $`\mathrm{tr}_{_1𝒫_1}|\psi _j\psi _j|=\mathrm{tr}_{_1𝒫_1}|\varphi _j\varphi _j|`$, for each $`1jm/2`$.

We define each $`P_{1,j}^{}`$ recursively. To define $`P_{1,1}^{}`$, consider the states $`|\varphi _1`$ and $`|\psi _1`$. Let $`|\varphi _1^{}=|\varphi _1`$. Since all of the last $`(q_𝒫q_{\mathrm{ent}})`$ qubits in $`𝒫_1`$ in the state $`|\varphi _1`$ are the $`|0`$-states and $`|\psi _1=P_{1,1}|\varphi _1`$, by Theorem 10, there exists a state $`|\psi _1^{}`$ in $`𝒱_1\mathrm{}_k𝒫_1\mathrm{}𝒫_k`$ such that

$$\mathrm{tr}_{𝒫_1}|\psi _1^{}\psi _1^{}|=\mathrm{tr}_{𝒫_1}|\psi _1\psi _1|$$

and all but the first $`q_{\mathrm{ent}}+2q_{}`$ qubits in $`𝒫_1`$ are the $`|0`$-states in the state $`|\psi _1^{}`$. Furthermore we have

$$\mathrm{tr}_{_1𝒫_1}|\psi _1^{}\psi _1^{}|=\mathrm{tr}_{_1𝒫_1}|\psi _1\psi _1|=\mathrm{tr}_{_1𝒫_1}|\varphi _1\varphi _1|=\mathrm{tr}_{_1𝒫_1}|\varphi _1^{}\varphi _1^{}|.$$

Therefore, by Theorem 7, there exists a unitary transformation $`Q_{1,1}`$ acting on $`_1𝒫_1`$ such that $`Q_{1,1}|\varphi _1^{}=|\psi _1^{}`$ and $`Q_{1,1}`$ is of the form $`P_{1,1}^{}I_{q_𝒫q_{\mathrm{ent}}mq_{}}`$, where $`P_{1,1}^{}`$ is a unitary transformation acting on qubits in $`_1`$ and the first $`q_{\mathrm{ent}}+mq_{}`$ qubits of $`𝒫_1`$, and $`I_{q_𝒫q_{\mathrm{ent}}mq_{}}`$ is the $`(q_𝒫q_{\mathrm{ent}}mq_{})`$-dimensional identity matrix.

Assume that $`Q_{1,j}`$, $`|\varphi _j^{}`$, and $`|\psi _j^{}`$ have been defined for each $`j`$, $`1j\xi m/21`$, to satisfy

* | $`|\varphi _1^{}`$ | $`=`$ | $`V_1|\psi _{\mathrm{init}}`$, |
| --- | --- | --- |
| $`|\varphi _j^{}`$ | $`=`$ | $`V_jP_{k,j1}\mathrm{}P_{2,j1}Q_{1,j1}|\varphi _{j1}^{}`$, | $`2j\xi `$, |
| $`|\psi _j^{}`$ | $`=`$ | $`Q_{1,j}|\varphi _j^{},`$ | $`1j\xi `$. |
* $`\mathrm{tr}_{𝒫_1}|\psi _j\psi _j|=\mathrm{tr}_{𝒫_1}|\psi _j^{}\psi _j^{}|`$, $`1j\xi `$.
* All but the first $`q_{\mathrm{ent}}+2(j1)q_{}`$ qubits in $`𝒫_1`$ are the $`|0`$-states in the state $`|\varphi _j^{}`$.
* All but the first $`q_{\mathrm{ent}}+2jq_{}`$ qubits in $`𝒫_1`$ are the $`|0`$-states in the state $`|\psi _j^{}`$.

Notice that $`Q_{1,1}`$, $`|\varphi _1^{}`$, and $`|\psi _1^{}`$ defined above satisfy such conditions. Define $`Q_{1,\xi +1}`$, $`|\varphi _{\xi +1}^{}`$, and $`|\psi _{\xi +1}^{}`$ in the following way to satisfy the above four conditions for $`j=\xi +1`$.

Let $`U_\xi =V_{\xi +1}P_{k,\xi }\mathrm{}P_{2,\xi }`$ and define $`|\varphi _{\xi +1}^{}=U_\xi |\psi _\xi ^{}`$. Then all but the first $`q_{\mathrm{ent}}+2\xi q_{}`$ qubits in $`𝒫_1`$ are the $`|0`$-states in the state $`|\varphi _{\xi +1}^{}`$, since none of $`P_{2,\xi },\mathrm{},P_{k,\xi },V_{\xi +1}`$ acts on the space $`𝒫_1`$ and $`|\psi _\xi ^{}`$ satisfies the fourth condition. Since $`\mathrm{tr}_{𝒫_1}|\psi _\xi \psi _\xi |=\mathrm{tr}_{𝒫_1}|\psi _\xi ^{}\psi _\xi ^{}|`$, by Theorem 7, there exists a unitary transformation $`A_\xi `$ acting on $`𝒫_1`$ such that $`A_\xi |\psi _\xi ^{}=|\psi _\xi `$. Thus we have

$$|\psi _{\xi +1}=P_{1,\xi +1}U_\xi |\psi _\xi =P_{1,\xi +1}U_\xi A_\xi |\psi _\xi ^{}=P_{1,\xi +1}A_\xi U_\xi |\psi _\xi ^{}=P_{1,\xi +1}A_\xi |\varphi _{\xi +1}^{}.$$
(2)
Hence, by Theorem 10, there exists a state $`|\psi _{\xi +1}^{}`$ such that

$$\mathrm{tr}_{𝒫_1}|\psi _{\xi +1}^{}\psi _{\xi +1}^{}|=\mathrm{tr}_{𝒫_1}|\psi _{\xi +1}\psi _{\xi +1}|$$
(3)
and all but the first $`q_{\mathrm{ent}}+2(\xi +1)q_{}`$ qubits in $`𝒫_1`$ are the $`|0`$-states in the state $`|\psi _{\xi +1}^{}`$. From (2) and (3), we have

$$\mathrm{tr}_{_1𝒫_1}|\psi _{\xi +1}^{}\psi _{\xi +1}^{}|=\mathrm{tr}_{_1𝒫_1}|\psi _{\xi +1}\psi _{\xi +1}|=\mathrm{tr}_{_1𝒫_1}|\varphi _{\xi +1}^{}\varphi _{\xi +1}^{}|,$$

since $`P_{1,\xi +1}`$ and $`A_\xi `$ act only on $`_1𝒫_1`$. Therefore, by Theorem 7, there exists a unitary transformation $`Q_{1,\xi +1}`$ acting on $`_1𝒫_1`$ such that $`Q_{1,\xi +1}|\varphi _{\xi +1}^{}=|\psi _{\xi +1}^{}`$. It follows that $`Q_{1,\xi +1}`$ is of the form $`P_{1,\xi +1}^{}I_{q_𝒫q_{\mathrm{ent}}mq_{}}`$, where $`P_{1,\xi +1}^{}`$ is a unitary transformation acting on qubits in $`_1`$ and the first $`q_{\mathrm{ent}}+mq_{}`$ qubits of $`𝒫_1`$, because all of the last $`q_𝒫q_{\mathrm{ent}}mq_{}`$ qubits in $`𝒫_1`$ are the $`|0`$-states in both of the states $`|\varphi _{\xi +1}^{}`$ and $`|\psi _{\xi +1}^{}`$. One can see that $`Q_{1,\xi +1},|\varphi _{\xi +1}^{}`$, and $`|\psi _{\xi +1}^{}`$ satisfy the four conditions above by their construction.

Having defined $`Q_{1,j},|\varphi _j^{},|\psi _j^{}`$ for each $`1jm/2`$, compare the state just before the final measurement is performed in the original protocol and that in the modified protocol applying $`Q_{1,j}`$’s instead of $`P_{1,j}`$’s. For $`U_{m/2}=V_{m/2+1}P_{k,m/2}\mathrm{}P_{2,m/2}`$, let $`|\varphi _{m/2+1}=U_{m/2}|\psi _{m/2}`$ and $`|\varphi _{m/2+1}^{}=U_{m/2}|\psi _{m/2}^{}`$. These $`|\varphi _{m/2+1}`$ and $`|\varphi _{m/2+1}^{}`$ are exactly the states we want to compare. Noticing that $`\mathrm{tr}_{𝒫_1}|\psi _{m/2}\psi _{m/2}|=\mathrm{tr}_{𝒫_1}|\psi _{m/2}^{}\psi _{m/2}^{}|`$, we have $`\mathrm{tr}_{𝒫_1}|\varphi _{m/2+1}\varphi _{m/2+1}|=\mathrm{tr}_{𝒫_1}|\varphi _{m/2+1}^{}\varphi _{m/2+1}^{}|`$, since none of $`P_{2,m/2},\mathrm{},P_{k,m/2},V_{m/2+1}`$ acts on $`𝒫_1`$. Thus we have

$$\mathrm{tr}_{𝒫_1\mathrm{}𝒫_k}|\varphi _{m/2+1}\varphi _{m/2+1}|=\mathrm{tr}_{𝒫_1\mathrm{}𝒫_k}|\varphi _{m/2+1}^{}\varphi _{m/2+1}^{}|,$$

which implies that the verifier $`V`$ cannot distinguish $`|\varphi _{m/2+1}^{}`$ from $`|\varphi _{m/2+1}`$ at all. Hence, for every input $`x`$, the probability of accepting $`x`$ in the protocol $`(Q_1,P_2,\mathrm{},P_k,V)`$ is exactly equal to the one in the original protocol $`(P_1,\mathrm{},P_k,V)`$, and $`Q_1`$ uses only $`q_{\mathrm{ent}}+mq_{}=q_{\mathrm{ent}}+2(m/2)q_{}`$ qubits in his private space. In the protocol $`(Q_1,P_2,\mathrm{},P_k,V)`$, each $`Q_{1,j}`$ is described as $`Q_{1,j}=P_{1,j}^{}I_{q_𝒫q_{\mathrm{ent}}mq_{}}`$, where $`P_{1,\xi +1}^{}`$ is a unitary transformation acting on qubits in $`_1`$ and the first $`q_{\mathrm{ent}}+mq_{}`$ qubits of $`𝒫_1`$. Consequently, by constructing an $`m`$-message $`(q_{},q_{\mathrm{ent}}+mq_{})`$-restricted quantum prover $`P_1^{}`$ from each $`P_{1,j}^{}`$, for every input $`x`$, the probability of accepting $`x`$ in the protocol $`(P_1^{},P_2,\mathrm{},P_k,V)`$ is exactly equal to the one in the original protocol $`(P_1,\mathrm{},P_k,V)`$.

Now we repeat the above process for each of provers, and finally we obtain a protocol $`(P_1^{},\mathrm{},P_k^{},V)`$ in which all $`k`$ provers are $`m`$-message $`(q_{},q_{\mathrm{ent}}+mq_{})`$-restricted quantum provers. It is obvious that, for every input $`x`$, the probability of accepting $`x`$ in the protocol $`(P_1^{},\mathrm{},P_k^{},V)`$ is exactly equal to the one in the original protocol $`(P_1,\mathrm{},P_k,V)`$, and we have the assertion. $`\mathrm{}`$

From Lemma 11, it is straightforward to show the following lemma.

###### Lemma 12

For any polynomially bounded functions $`k,m,q_{\mathrm{ent}}:^+`$, $`\mathrm{QMIP}(k,m,q_{\mathrm{ent}},1,1/2)\mathrm{NEXP}`$.

Proof.  For convenience, we assume that the values of $`m`$ are even (odd cases can be dealt with a similar argument).

Let $`L`$ be a language in $`\mathrm{QMIP}(k,m,q_{\mathrm{ent}},1,1/2)`$. Then, from Definition 1 together with Lemma 11, there exist polynomially bounded functions $`q_𝒱,q_{}:^+`$ and an $`m`$-message $`(q_𝒱,q_{})`$-restricted quantum verifier $`V`$ for a quantum $`k`$-prover interactive proof system such that, for every input $`x`$, (i) if $`x`$ is in $`L`$, there exists a set of $`k`$ quantum provers $`P_1,\mathrm{},P_k`$ of $`m`$-message $`(q_{},q_{\mathrm{ent}}+mq_{})`$-restricted $`q_{\mathrm{ent}}`$-prior-entangled such that $`(P_1,\mathrm{},P_k,V)`$ accepts $`x`$ with certainty, and (ii) if $`x`$ is not in $`L`$, for all sets of $`k`$ quantum provers $`P_1^{},\mathrm{},P_k^{}`$ of $`m`$-message $`(q_{},q_{\mathrm{ent}}+mq_{})`$-restricted $`q_{\mathrm{ent}}`$-prior-entangled, $`(P_1^{},\mathrm{},P_k^{},V)`$ accepts $`x`$ with probability at most $`1/2`$.

For an input $`x`$ of length $`n`$, consider a classical simulation of this quantum $`k`$-prover interactive proof system by a non-deterministic Turing machine. Let $`p_1`$ be arbitrary fixed polynomial. First, for the initial state $`|\psi _{\mathrm{init}}`$, an approximation $`|\stackrel{~}{\psi }_{\mathrm{init}}`$ of $`|\psi _{\mathrm{init}}`$ can be guessed in time non-deterministic exponential in $`n`$ with accuracy of $`|\stackrel{~}{\psi }_{\mathrm{init}}|\psi _{\mathrm{init}}<2^{p_1(n)}`$. Next, since each $`V_j`$ applied in the original proof system is polynomial-time uniformly generated and $`q_𝒱`$ and $`q_{}`$ are polynomially bounded functions, it is routine to show that an approximation $`\stackrel{~}{V}_j`$ of a matrix description of $`V_j`$ can be computed in time exponential in $`n`$ with accuracy of $`\stackrel{~}{V}_jV_j<2^{p_1(n)}`$. Finally, since $`q_{}`$ and $`q_𝒫=q_{\mathrm{ent}}+mq_{}`$ are polynomially bounded functions, for each operation $`P_{i,j}`$ of the $`i`$th prover applied in the original proof system, an approximation $`\stackrel{~}{P}_{i,j}`$ of a matrix description of $`P_{i,j}`$ can be guessed in time non-deterministic exponential in $`n`$ with accuracy of $`\stackrel{~}{P}_{i,j}P_{i,j}<2^{p_1(n)}`$. Thus, for the quantum state

$$|\psi _{\mathrm{final}}=V_{m/2+1}P_{k,m/2}\mathrm{}P_{1,m/2}V_{m/2}\mathrm{}P_{k,1}\mathrm{}P_{1,1}V_1|\psi _{\mathrm{init}},$$

which is the state just before the final measurement in the proof system, the approximation $`|\stackrel{~}{\psi }_{\mathrm{final}}`$ of $`|\psi _{\mathrm{final}}`$ can be computed in time non-deterministic exponential in $`n`$ with accuracy of $`|\stackrel{~}{\psi }_{\mathrm{final}}|\psi _{\mathrm{final}}<2^{p_2(n)}`$ for any fixed polynomial $`p_2`$ by appropriately choosing $`p_1`$.

Now, after having computed $`|\stackrel{~}{\psi }_{\mathrm{final}}`$, a measurement of the output qubit is simulated by summing up squares of the computed amplitudes in the accepting states. The input $`x`$ is accepted if and only if this sum, the computed probability that the measurement results in $`|1`$, is more than $`1\epsilon `$. From the property of the original proof system, this computed probability is more than $`12^{2p_2(n)}`$ if $`x`$ is in $`L`$, while it is less than $`1/2+2^{2p_2(n)}`$ if $`x`$ is not in $`L`$. Thus, taking $`p_2=n`$ and $`\epsilon =2^{2n}`$, the input $`x`$ is accepted if and only if $`x`$ is in $`L`$ and the whole computation is done in time non-deterministic exponential in $`n`$. $`\mathrm{}`$

Hence we have the following theorem.

###### Theorem 13

$`\mathrm{QMIP}^{(\mathrm{l}.\mathrm{e}.)}\mathrm{NEXP}`$.

Note that our upper bound of $`\mathrm{NEXP}`$ holds even if we allow protocols with two-sided bounded error, since the proof of Lemma 11 does not depend on the accepting probabilities $`a,b`$, and the proof of Lemma 12 can be easily modified to two-sided bounded error cases.

## 5 $`\mathrm{𝐐𝐌𝐈𝐏}^{\mathbf{(}𝐧\mathbf{.}𝐞\mathbf{.}\mathbf{)}}\mathbf{=}\mathrm{𝐐𝐎𝐂}\mathbf{=}\mathrm{𝐍𝐄𝐗𝐏}`$

In the previous section, we proved that the class of languages having quantum multi-prover interactive proof systems is necessarily contained in $`\mathrm{NEXP}`$ under the assumption that provers are allowed to share at most polynomially many prior-entangled qubits. As a special case of this, it is proved in this section that, if provers do not share any prior entanglement with each other, the class of languages having quantum multi-prover interactive proof systems is equal to $`\mathrm{NEXP}`$. Another result related to this is that $`\mathrm{QOC}`$ is also equal to $`\mathrm{NEXP}`$, or in other words, the class of languages having quantum single-prover interactive proof systems is also equal to $`\mathrm{NEXP}`$ if a prover does not have his private qubits.

The inclusions $`\mathrm{QMIP}^{(\mathrm{n}.\mathrm{e}.)}\mathrm{NEXP}`$ and $`\mathrm{QOC}\mathrm{NEXP}`$ directly come from Lemma 12. Thus it is sufficient for our claim to show $`\mathrm{NEXP}\mathrm{QMIP}^{(\mathrm{n}.\mathrm{e}.)}\mathrm{QOC}`$. Fortunately, in the cases without prior entanglement, it is easy to show that a quantum verifier can successfully simulate any classical multi-prover protocol, in particular, a one-round two-prover classical interactive protocol that can verify a language in $`\mathrm{NEXP}`$ with exponentially small one-sided error . Thus, we have the following theorem and corollary. The proof of Theorem 14 is straightforward, and thus omitted here (see Appendix A).

###### Theorem 14

$`\mathrm{NEXP}\mathrm{QMIP}^{(\mathrm{n}.\mathrm{e}.)}`$.

###### Corollary 15

For prior unentangled cases, if a language $`L`$ has a quantum multi-prover interactive proof system with two-sided bounded error, then $`L`$ has a two-message quantum two-prover interactive proof system with exponentially small one-sided error.

The remainder of this section is devoted to the proof of $`\mathrm{QMIP}^{(\mathrm{n}.\mathrm{e}.)}\mathrm{QOC}`$.

###### Lemma 16

Let $`k,m:^+`$ be polynomially bounded functions, and $`a,b:^+[0,1]`$ be functions satisfying $`ab`$. Then $`\mathrm{QMIP}(k,m,0,a,b)\mathrm{QOC}(k(m+1)/2,a,b)`$.

Proof.  For simplicity, we assume that the values of $`m`$ are even, and thus $`k(m+1)/2=km/2`$ (odd cases can be proved with a similar argument).

Let $`L`$ be a language in $`\mathrm{QMIP}(k,m,0,a,b)`$. Then, from Definition 1 together with Lemma 11, there exist polynomially bounded functions $`q_𝒱,q_{}:^+`$ and an $`m`$-message $`(q_𝒱,q_{})`$-restricted quantum verifier $`V`$ for a quantum $`k`$-prover interactive proof system such that, for every input $`x`$ of length $`n`$, (i) if $`x`$ is in $`L`$, there exists a set of $`m`$-message $`(q_{},mq_{})`$-restricted quantum provers $`P_1,\mathrm{},P_k`$ without prior entanglement such that $`(P_1,\mathrm{},P_k,V)`$ accepts $`x`$ with probability at least $`a(n)`$, and (ii) if $`x`$ is not in $`L`$, for all sets of $`m`$-message $`(q_{},mq_{})`$-restricted quantum provers $`P_1^{},\mathrm{},P_k^{}`$ without prior entanglement, $`(P_1^{},\mathrm{},P_k^{},V)`$ accepts $`x`$ with probability at most $`b(n)`$.

We construct a $`km/2`$-oracle-call verifier $`V^{\mathrm{QOC}}`$ of a quantum oracle circuit as follows. Let us consider that quantum registers (collections of qubits upon which various transformations are performed) $`𝐖`$, $`𝐌_i`$, and $`𝐏_i`$, for $`1ik`$, are prepared among the private qubits of the verifier $`V^{\mathrm{QOC}}`$, and quantum registers $`𝐌`$ and $`𝐏`$ are prepared among the qubits for oracle calls. $`𝐖`$ consists of $`q_𝒱`$ qubits, each $`𝐌_i`$ and $`𝐌`$ consist of $`q_{}`$ qubits, and each $`𝐏_i`$ and $`𝐏`$ consist of $`q_𝒫=mq_{}`$ qubits. Let $`𝒲^{\mathrm{QOC}}`$, each $`_i^{\mathrm{QOC}}`$, and each $`𝒫_i^{\mathrm{QOC}}`$ denote the Hilbert spaces corresponding to the registers $`𝐖`$, $`𝐌_i`$, and $`𝐏_i`$, respectively. Take the Hilbert space $`𝒱^{\mathrm{QOC}}`$ corresponding to the qubits private to the verifier $`V^{\mathrm{QOC}}`$ as $`𝒱^{\mathrm{QOC}}=𝒲^{\mathrm{QOC}}_1^{\mathrm{QOC}}\mathrm{}_k^{\mathrm{QOC}}𝒫_1^{\mathrm{QOC}}\mathrm{}𝒫_k^{\mathrm{QOC}}`$. Accordingly, the number of private qubits of $`V^{\mathrm{QOC}}`$ is $`q_𝒱^{\mathrm{QOC}}=q_𝒱+k(q_{}+q_𝒫)=q_𝒱+k(m+1)q_{}`$. Let $`^{\mathrm{QOC}}`$ and $`𝒫^{\mathrm{QOC}}`$ denote the Hilbert spaces corresponding to the registers $`𝐌`$ and $`𝐏`$, respectively. Take the Hilbert space $`𝒪^{\mathrm{QOC}}`$ corresponding to the qubits for oracle calls as $`𝒪^{\mathrm{QOC}}=^{\mathrm{QOC}}𝒫^{\mathrm{QOC}}`$. Accordingly, the number of qubits for oracle calls is $`q_𝒪^{\mathrm{QOC}}=q_{}+q_𝒫=(m+1)q_{}`$.

Consider each $`V_j`$, the $`j`$th quantum circuit of the verifier $`V`$ of the original quantum $`k`$-prover interactive proof system, which acts on $`𝒱_1\mathrm{}_k`$. For each $`j`$, let $`U_j^{\mathrm{QOC}}`$ be just the same unitary transformation as $`V_j`$ and $`U_j^{\mathrm{QOC}}`$ acts on $`𝒲^{\mathrm{QOC}}_1^{\mathrm{QOC}}\mathrm{}_k^{\mathrm{QOC}}`$, corresponding to that $`V_j`$ acts on $`𝒱_1\mathrm{}_k`$. Define the verifier $`V^{\mathrm{QOC}}`$ of the corresponding quantum oracle circuit in the following way:

* At the first transformation of $`V^{\mathrm{QOC}}`$, $`V^{\mathrm{QOC}}`$ first applies $`U_1^{\mathrm{QOC}}`$, and then swaps the contents of $`𝐌_1`$ for those of $`𝐌`$.
* At the $`((j1)k+1)`$-th transformation of $`V^{\mathrm{QOC}}`$ for each $`2jm/2`$, $`V^{\mathrm{QOC}}`$ first swaps the contents of $`𝐌`$ and $`𝐏`$ for those of $`𝐌_k`$ and $`𝐏_k`$, respectively, then applies $`U_j^{\mathrm{QOC}}`$, and finally swaps the contents of $`𝐌_1`$ and $`𝐏_1`$ for those of $`𝐌`$ and $`𝐏`$.
* At the $`((j1)k+i)`$-th transformation of $`V^{\mathrm{QOC}}`$ for each $`2ik,1jm/2`$, $`V^{\mathrm{QOC}}`$ first swaps the contents of $`𝐌`$ and $`𝐏`$ for those of $`𝐌_{i1}`$ and $`𝐏_{i1}`$, respectively, then swaps the contents of $`𝐌_i`$ and $`𝐏_i`$ for those of $`𝐌`$ and $`𝐏`$.

* In the case the input $`x`$ of length $`n`$ is in $`L`$:
In the original $`m`$-message quantum $`k`$-prover interactive proof system, there exist $`m`$-message $`(q_{},q_𝒫)`$-restricted prior-unentangled quantum provers $`P_1,\mathrm{},P_k`$ that cause $`V`$ to accept $`x`$ with probability at least $`a(n)`$. Hence, if we let $`O_{(j1)k+i}`$ for each $`1ik,1jm/2`$ be just the same unitary transformation as $`P_{i,j}`$ ($`O_{(j1)k+i}`$ acts on $`𝒪^{\mathrm{QOC}}=^{\mathrm{QOC}}𝒫^{\mathrm{QOC}}`$ corresponding to that $`P_{i,j}`$ acts on $`_i𝒫_i`$), it is obvious that the probability of accepting $`x`$ by $`V^{\mathrm{QOC}}`$ with access to $`O`$ is exactly equal to the one the original $`V`$ accepts it, which is at least $`a(n)`$.
* In the case the input $`x`$ of length $`n`$ is not in $`L`$:
Suppose that there were an oracle $`O^{}`$ that makes the verifier $`V^{\mathrm{QOC}}`$ accept $`x`$ with probability more than $`b(n)`$. Consider $`m`$-message $`(q_{},q_𝒫)`$-restricted prior-unentangled provers $`P_1^{},\mathrm{},P_k^{}`$ of the original $`m`$-message quantum $`k`$-prover interactive proof system such that, for each $`1ik,1jm/2`$, $`P_{i,j}^{}`$ is just the same transformation as $`O_{(j1)k+i}^{}`$ ($`P_{i,j}^{}`$ acts on $`_i𝒫_i`$ corresponding to that $`O_{(j1)k+i}^{}`$ acts on $`^{\mathrm{QOC}}𝒫^{\mathrm{QOC}}`$). By their construction, it is obvious that the probability with which these provers $`P_1^{},\mathrm{},P_k^{}`$ can convince the verifier $`V`$ is exactly equal to the one with which the oracle $`O^{}`$ can, which is more than $`b(n)`$. This contradicts the assumption.

$`\mathrm{}`$

The inclusion $`\mathrm{QMIP}^{(\mathrm{n}.\mathrm{e}.)}\mathrm{QOC}`$ immediately follows from Lemma 16. Thus we have the following theorem.

###### Theorem 17

$`\mathrm{QMIP}^{(\mathrm{n}.\mathrm{e}.)}=\mathrm{QOC}=\mathrm{NEXP}`$.

## 6 Conclusions and Open Problems

This paper analyzed the power of quantum multi-prover interactive proof systems and gave the $`\mathrm{NEXP}`$ upper bound for them in the cases that provers share at most polynomially many prior-entangled qubits. In particular, if provers do not share any prior entanglement with each other, the class of languages having quantum multi-prover interactive proof systems was shown equal to $`\mathrm{NEXP}`$. Related to these, if a prover does not have his private qubits, the class of languages having quantum single-prover interactive proof systems was also shown equal to $`\mathrm{NEXP}`$.

A number of interesting problems remain open regarding quantum interactive proof systems.

* We know very little about the power of general quantum multi-prover interactive proof systems with provers sharing arbitrarily many prior-entangled qubits. Can exponentially many prior-entangled qubits among provers help a quantum verifier to verify a language not in $`\mathrm{NEXP}`$? Does $`\mathrm{NEXP}`$ have quantum multi-prover interactive proof systems with prior-entangled provers?
* Probabilistic oracle machines are closely related to the theory of probabilistic checkable proofs . How is the relation between the quantum oracle circuits introduced in this paper and possible quantum analogues of probabilistic checkable proofs?
* In the classical setting the power of one-message multi-prover interactive proof systems obviously remains same as that of one-message single-prover ones. However, as Kobayashi, Matsumoto, and Yamakami  noticed, it might not be so in the quantum setting. How is the power of one-message quantum multi-prover interactive proof systems (both in the cases with and without prior entanglement)?

## Acknowledgements

The authors are grateful to Richard E. Cleve for explaining how an entangled pair of provers can cheat a classical verifier in some cases, and Lance J. Fortnow for his valuable comments on writing this paper. The authors would also like to thank Hiroshi Imai for his comments and support.

## Appendix

## Appendix A Proof of Theorem 14

It is known that every language in $`\mathrm{NEXP}`$ has a (classical) multi-prover interactive proof system, in particular, a one-round two-prover classical interactive proof system with exponentially small one-sided error . Under the assumption that provers do not share any prior entanglement with each other, it is easy to show that a quantum verifier can successfully simulate such a classical one-round two-prover protocol (cf. ).

Proof of Theorem 14 Given a classical $`k`$-prover interactive protocol, consider such a quantum $`k`$-prover protocol without prior entanglement that a quantum verifier performs measurements in $`\{|0,|1\}`$ basis on every qubit of his part at every time he sends questions to quantum provers and at every time he receives responses from them, and for the rest part of computation the quantum verifier behaves in the same manner as the classical verifier does. Such a protocol can be simulated without intermediate measurements by only using unitary transformations . Furthermore, since there is no prior entanglement among private qubits of the quantum provers, such a quantum protocol makes no difference from a classical protocol in which a classical verifier chooses a set of $`k`$ classical provers probabilistically at the beginning of the protocol. Therefore, in such a quantum $`k`$-prover protocol, for every input, the quantum provers can be only as powerful as the classical provers, i.e., the quantum provers can behave just in the same way as the classical provers do, while no set of $`k`$ quantum provers can convince the quantum verifier with probability more than the maximum probability with which a set of $`k`$ classical provers can convince the classical verifier.

Now we explain in more detail. Let $`L`$ be a language in $`\mathrm{NEXP}`$, then $`L`$ has a one-round two-prover interactive proof system. Let $`V`$ be the classical verifier of this one-round two-prover interactive proof system. We construct a two-message quantum two-prover interactive proof system by just simulating this classical protocol.

Assume that, just after the classical verifier $`V`$ has sent questions to the provers $`P_1`$ and $`P_2`$, the contents of $`V`$’s private tape, the question to $`P_1`$, and the question to $`P_2`$ are $`v`$, $`q_1`$, and $`q_2`$, respectively, with probability $`p(v,q_1,q_2)`$. Our two-message quantum verifier $`V^{(\mathrm{Q})}`$ prepares the quantum registers $`𝐕`$, $`𝐐_1`$, $`𝐐_2`$, $`𝐀_1`$, and $`𝐀_2`$ among his private qubits. $`V^{(\mathrm{Q})}`$ first stores $`v`$, $`q_1`$, and $`q_2`$ in $`𝐕`$, $`𝐐_1`$, and $`𝐐_2`$, respectively, then copies the contents of each $`𝐐_i`$ to the message qubits shared with a quantum prover $`P_i^{(\mathrm{Q})}`$. That is, $`V^{(\mathrm{Q})}`$ prepares the superposition

$$\underset{v,q_1,q_2}{}\left(\sqrt{p(v,q_1,q_2)}\underset{𝐕}{\underset{}{|v}}\underset{𝐐_1}{\underset{}{|q_1}}\underset{𝐐_2}{\underset{}{|q_2}}\underset{𝐀_1}{\underset{}{|0}}\underset{𝐀_2}{\underset{}{|0}}\underset{𝐌_1}{\underset{}{|q_1}}\underset{𝐏_1}{\underset{}{|0}}\underset{𝐌_2}{\underset{}{|q_2}}\underset{𝐏_2}{\underset{}{|0}}\right),$$

where, for each $`i=1,2`$, $`𝐌_i`$ denotes the quantum register that consists of the message qubits between $`V^{(\mathrm{Q})}`$ and $`P_i^{(\mathrm{Q})}`$, and $`𝐏_i`$ denotes the quantum register that consists of $`P_i^{(\mathrm{Q})}`$’s private qubits.

Next the quantum provers $`P_1^{(\mathrm{Q})}`$ and $`P_2^{(\mathrm{Q})}`$ apply some unitary transformations on their qubits. Now the state becomes

$`{\displaystyle \underset{v,q_1,q_2}{}}\{\sqrt{p(v,q_1,q_2)}\underset{𝐕}{\underset{}{|v}}\underset{𝐐_1}{\underset{}{|q_1}}\underset{𝐐_2}{\underset{}{|q_2}}\underset{𝐀_1}{\underset{}{|0}}\underset{𝐀_2}{\underset{}{|0}}`$
$`\left({\displaystyle \underset{a_1}{}}\alpha _1(q_1,a_1)\underset{𝐌_1}{\underset{}{|a_1}}\underset{𝐏_1}{\underset{}{|\psi _1(q_1,a_1)}}\right)\left({\displaystyle \underset{a_2}{}}\alpha _2(q_2,a_2)\underset{𝐌_2}{\underset{}{|a_2}}\underset{𝐏_2}{\underset{}{|\psi _2(q_2,a_2)}}\right)\}`$
$`=`$ $`{\displaystyle \underset{v,q_1,q_2,a_1,a_2}{}}(\sqrt{p(v,q_1,q_2)}\alpha _1(q_1,a_1)\alpha _2(q_2,a_2)`$
$`\times \underset{𝐕}{\underset{}{|v}}\underset{𝐐_1}{\underset{}{|q_1}}\underset{𝐐_2}{\underset{}{|q_2}}\underset{𝐀_1}{\underset{}{|0}}\underset{𝐀_2}{\underset{}{|0}}\underset{𝐌_1}{\underset{}{|a_1}}\underset{𝐏_1}{\underset{}{|\psi _1(q_1,a_1)}}\underset{𝐌_2}{\underset{}{|a_2}}\underset{𝐏_2}{\underset{}{|\psi _2(q_2,a_2)}}),`$
where each $`\alpha _i(q_i,a_i)`$ denotes the transition amplitude and each $`|\psi _i(q_i,a_i)`$ is a unit vector in the private space of $`P_i^{(\mathrm{Q})}`$.

Finally, $`V^{(\mathrm{Q})}`$ copies the contents of the message qubits shared with the quantum prover $`P_i^{(\mathrm{Q})}`$ to $`𝐀_i`$ to have the following state

$$\underset{v,q_1,q_2,a_1,a_2}{}\left(\sqrt{p(v,q_1,q_2)}\alpha _1(q_1,a_1)\alpha _2(q_2,a_2)\underset{𝐕}{\underset{}{|v}}\underset{𝐐_1}{\underset{}{|q_1}}\underset{𝐐_2}{\underset{}{|q_2}}\underset{𝐀_1}{\underset{}{|a_1}}\underset{𝐀_2}{\underset{}{|a_2}}\underset{𝐌_1}{\underset{}{|a_1}}\underset{𝐏_1}{\underset{}{|\psi _1(q_1,a_1)}}\underset{𝐌_2}{\underset{}{|a_2}}\underset{𝐏_2}{\underset{}{|\psi _2(q_2,a_2)}}\right),$$

and does just the same computation as the classical verifier $`V`$ using $`𝐕`$, $`𝐌_1`$ and $`𝐌_2`$. $`V^{(\mathrm{Q})}`$ accepts the input if and only if $`V`$ accepts it.

* In the case the input $`x`$ of length $`n`$ is in $`L`$:
The quantum provers have only to answer in just the same way as the classical provers do, and $`V^{(\mathrm{Q})}`$ accepts $`x`$ with probability $`1`$.
* In the case the input $`x`$ of length $`n`$ is not in $`L`$:
Since no quantum interference occurs among the computational paths with different 4-tuple $`(q_1,q_2,a_1,a_2)`$, and from the fact that any pair of classical provers cannot convince the classical verifier with probability more than $`1/2`$ (actually $`1/2^n`$), it is obvious that, for any pair of quantum provers, $`V^{(\mathrm{Q})}`$ accepts $`x`$ with probability at most $`1/2`$ (actually $`1/2^n`$).

$`\mathrm{}`$