Quantum Advantage in Proof Systems Without Entanglement

In order to formalize the notion of “arrangement” of provers and verifiers, we introduce a position mapping, which maps provers and verifiers to points in a metric space:

We work in a relativistic setting in which all communication is subject to the speed-of-light constraint. Concretely, a message sent at time $t$ from a party located at $x\in 𝒳$ to a party at $y\in 𝒳$ must be received no earlier than time $t+𝖽(x,y)$. We formalize this constraint via a transmission function, which specifies the recipient of a message and the time at which it is delivered.

In the honest setting, message delivery is straightforward: if the verifier $𝖵$ sends a message towards the honest prover $𝖯$ at time $t$, then the message is delivered to the prover at time $t+𝖽(𝖵,𝖯)$. However, in the malicious setting, messages sent by the verifier may be arbitrarily intercepted and redirected by malicious provers. To model this behaviour, we introduce a more powerful malicious transmission function (see Definition 13), which always delivers verifier messages first to the nearest prover. This modelling choice is without loss of generality: a malicious strategy can always place a prover at every verifier location, ensuring that verifier messages are received in the next time step and can then be forwarded to any other party of the adversary’s choosing. We analyse and justify this modelling choice in greater detail in Section 3.2 and Remark 14.

We introduce new positional proof systems, called (quantum) positional multi-prover interactive proofs ((Q)PMIPs). A (Q)PMIP for a relation $ℛ$ consists of a set of honest provers and verifiers, a metric space $(𝒳,𝖽)$, an honest position mapping $𝗉$, a timeout value $T$ and an output predicate (or measurement in the quantum case) $P_{\mathrm{𝗈𝗎𝗍𝗉𝗎𝗍}}$.

The protocol proceeds in discrete timesteps. At each timestep $t\in [T]$, provers and verifiers can send messages to each other. These messages are transmitted via the transmission function. At the end of the protocol, the verifiers jointly decide to accept or reject by applying $P_{\mathrm{𝗈𝗎𝗍𝗉𝗎𝗍}}$ to their transcripts.

Completeness says that for any $𝕩\in ℒ(ℛ)$, the honest provers at the positions specified by the honest position mapping $𝗉$ will always convince the verifiers, while soundness requires that for any $𝕩\notin ℒ(ℛ)$, any number of malicious provers at any positions cannot convince the verifier except with small probability. We give the formal definition in Section 3.3.

We define the “positional” complexity classes $\mathrm{𝐏𝐌𝐈𝐏}[𝗉]$ (resp. ${\mathrm{𝐐𝐏𝐌𝐈𝐏}}^{𝗌}[𝗉]$) as the set of languages decidable by a PMIP (resp. QPMIP) defined on the metric space $(𝒳,𝖽)$ with the honest position mapping $𝗉$. The formal QPMIP definition appears in Definition 18; the PMIP definition is the analogous classical restriction. The term “positional” is reflected in the sense that the size of these complexity classes are dependent on the position mapping $𝗉$.

Note that in the classical case, all messages are classical so can be copied and broadcasted. In particular, a malicious prover strategy can place a prover at each verifier position and relay the verifier messages to all other parties. In the quantum case however, messages may be quantum states and this is not possible due to no-cloning. This difference leads to a significant separation in the classical and quantum model as we will elaborate on below.

Fix a verifier $𝖵$, suppose the distance between $𝖵$ and the nearest honest prover to it is $r$, then any party that is able to interact with $𝖵$ as quickly as the closest honest prover must be within a ball that is centred at $𝖵$ with radius $r$. We call this region the min-ball of $𝖵$. The min-ball captures the tightest response window that $𝖵$ can impose: any response that takes time more than $2\cdot r$ can come from malicious provers outside of the ball, while any faster response is physically impossible for any honest provers.

With this definition, we can restate the part about PMIP in Theorem 1. What we prove is a stronger result that says the min-ball condition exactly characterizes the dichotomy for classical PMIP:

Intuitively, the min-ball condition characterizes whether relativistic timing constraints enforce informational independence between verifiers. Each verifier can require responses within a time window determined by the distance to its closest honest prover. If, for every pair of verifiers, information generated near one verifier can reach the other within this window, then timing constraints do not prevent malicious provers from globally sharing all verifier messages. In this case, the PMIP protocol effectively collapses to an IP. Conversely, if there exists a pair of verifiers whose response windows are too short to permit such communication, then the arrangement enforces separation, and the complexity class is as big as $\mathrm{𝐌𝐈𝐏}$. In the classical setting, the min-ball condition is precisely the geometric criterion that separates these two regimes.

To formalize this intuition and prove that violation of the min-ball condition implies $\mathrm{𝐏𝐌𝐈𝐏}[𝗉]=\mathrm{𝐈𝐏}$, we introduce a canonical interactive proof (IP). Given a PMIP protocol with $T$ timesteps, we define a $T$-round IP in which, in each round $t\in [T]$, the IP verifier internally simulates all PMIP verifier at timestep $t$, while the IP prover internally simulates all PMIP provers at timestep $t$.

The canonical IP is trivially complete. We then show that it is also sound whenever the min-ball condition is violated. The key observation is that any cheating prover strategy for the canonical IP can be simulated by a coalition of malicious PMIP provers. Even if each PMIP verifier enforces the tightest possible timing constraint by communicating only with its nearest honest prover, violation of the min-ball condition guarantees that there is still sufficient time for information originating at one verifier to reach any other verifier. As a result, a malicious strategy can place a prover at each verifier location; these provers collectively obtain all verifier messages in time (up to known time shifts) and can locally simulate the behavior of a cheating canonical IP prover.

The above argument relies on the fact that classical information can be freely copied: a single canonical IP prover can be perfectly simulated by multiple provers placed at the verifier positions. This argument, however, does not carry over to the quantum setting. Even when the min-ball condition is violated, it is in general impossible to simulate multiple spatially separated copies of a single coherent quantum prover, due to the no-cloning principle.

Nevertheless, if all min-balls under position mapping $𝗉$ have a nonempty mutual intersection, then we can show that ${\mathrm{𝐐𝐏𝐌𝐈𝐏}}^{𝗌}[𝗉]=\mathrm{𝐈𝐏}$. Indeed, in this case a single quantum prover located at the intersection point can faithfully simulate a single quantum prover and communicate with all QPMIP verifiers within the required time bounds.

This leaves an intermediate regime of particular interest: the quantum setting in which the min-ball condition is violated, but the min-balls do not admit a common intersection. Understanding the power of QPMIP protocols in this regime is one of the central motivations for our analysis.

To provide some intuition on how to obtain a lower bound on ${\mathrm{𝐐𝐏𝐌𝐈𝐏}}^{𝗌}[𝗉]$, we consider a minimal two-prover, one-round setting in the regime of interest, where verifier min-balls pairwise intersect but admit no common intersection, as illustrated in Figure 1. In this configuration, ${𝖯}_1$ and ${𝖯}_2$ correspond to the two honest provers, and they are exactly at the intersection of the min-balls for ${𝖵}_1$ and ${𝖵}_3$, and for ${𝖵}_2$ and ${𝖵}_3$ respectively. Our goal is to argue that the soundness of some QPMIP construction with parties positioned as in this configuration is upper bounded by the soundness of the underlying MIP.

Recall that in an MIP, soundness relies on the fact that each prover’s response is independent of the other prover’s query. In the positional setting, however, if ${𝖵}_1$ and ${𝖵}_2$ were to send the MIP queries in the clear, then a malicious prover placed at the intersection of the min-balls of ${𝖵}_1$ and ${𝖵}_2$ could receive both queries in time and respond to each verifier with answers that depend on both queries, thereby violating the MIP soundness condition. The two red paths in Figure 1 illustrate a similar attack strategy by malicious provers orchestrating the path so that the response to ${𝖵}_2$ depends on the query sent by ${𝖵}_1$, made possible because the min-balls of ${𝖵}_1$ and ${𝖵}_2$ intersect.

This observation shows that MIP queries cannot be transmitted in the clear. Instead, the verifiers must jointly encode each query using an encryption mechanism reminiscent of secret sharing. Crucially, the shares must be distributed so that only a prover located at the honest position can receive all of them early enough to decrypt the query and respond in time.

At first glance, the scheme we seek resembles a standard position verification (PV) protocol. Recall that in a position verification protocol, the verifiers always accept an honest prover located at the honest position, while no coalition of malicious provers – none of which are at the honest position – can fool the verifier except with small probability. It is known that position verification is impossible in both the classical and quantum settings if malicious provers are allowed to share an unbounded amount of entanglement. However, Buhrman et al. [4] showed that secure position verification is achievable in the quantum setting under the no prior entanglement (no-PE) model. Motivated by this result, we likewise restrict our attention to the no-PE model throughout this work.

Position verification protocol from [4].

• $\mathrm{■}$

  The verifiers jointly sample a random challenge string $x$ and a random measurement basis $\theta$, and send the state $H^{\theta }|x⟩$ to the honest prover $𝖯$ in a way that they arrive at $𝖯$ at the same time $t^{\ast }$.

• $\mathrm{■}$

  $𝖯$ measures the state in basis $\theta$ to get an outcome $x$, and sends $x$ back to both verifiers. Verifiers accept iff. they both receive the correct $x$.

In Figure 1, suppose that verifiers ${𝖵}_1$ and ${𝖵}_3$ execute the position verification protocol described above, with ${𝖯}_1$ designated as the honest prover. (Symmetrically, ${𝖵}_2$ and ${𝖵}_3$ may run the same protocol with ${𝖯}_2$ as the honest prover; since the two cases are symmetric, we focus on the former.) In this setting, position verification guarantees that only the honest prover ${𝖯}_1$ can compute the challenge $x$ at time $t^{\ast }$.

If we were to use such a bit $x$ independently to mask each bit of the MIP query ${𝗊}_1$, and have the verifier send the masked query to ${𝖯}_1$, then only the honest prover would be able to recover ${𝗊}_1$ at time $t^{\ast }$. Moreover, any coalition of provers located elsewhere – in particular, provers positioned so that they can communicate with ${𝖵}_2$ starting from time $t^{\ast }$ – would be unable to learn anything about ${𝗊}_1$ except with small probability, since they cannot compute $x$ in time.

However, this guarantee is insufficient for our purposes. What we require is the substantially stronger condition that no such coalition can learn ${𝗊}_1$ at any time prior to ${𝖵}_2$ receiving its response, that is, before time $t^{\ast }+𝖽({𝖯}_2,{𝖵}_2)$. Without additional restrictions, this stronger guarantee does not hold. For example, since the min-ball condition is violated, malicious provers can redirect all messages from ${𝖵}_1$ and ${𝖵}_3$ directly to ${𝖵}_2$ within the required time bounds. In this case, a prover positioned at ${𝖵}_2$ can learn the query ${𝗊}_1$ in time and produce a response that depends on both queries.

A violation of the min-ball condition allows for communication between malicious provers within the response windows of the verifiers. To circumvent this, we design a cryptographic primitive that can be used to encrypt the MIP queries in a way that no coalition of provers can learn the query value until it is “too late” to coordinate a cheating response to another verifier. We call this primitive a positional hardcore bit (PHB) scheme.

The soundness condition is the “best possible”: the time $\widehat{t}$ is exactly the time when a prover at the honest location, having computed $b$ at time $t^{\ast }$, can send $b$ to the closest ${\widetilde{𝖯}}_i$. It is therefore impossible to require that the malicious provers not learn $b$ at time $\widehat{t}$. It remains to show the existence of this strong positional primitive.

It is not clear how to ensure unguessability of $b$ for the period of time asked for in Definition 6; indeed, redirection of messages meant for $𝖯$ to $\widetilde{𝖯}$ may allow it to learn the bit $b$ at a time prior to $\widehat{t}$, which would violate the soundness condition.

The key insight is that we require $𝖯$ to send an acknowledgement of the receipt of their messages in time. A good acknowledgement should depend strongly on a secret hidden in the verifier messages, so that redirection loses the ability to compute the acknowledgement correctly. This property is reminiscent of the monogamy-of-entanglement property that quantum systems possess: if the acknowledgement can be treated as entangled with a secret private to the verifiers, then either the acknowledgement is computable by the honest prover or by the malicious prover (or none of them), but certainly not by both of them. This motivates our construction of a two-verifier PHB scheme based on the monogamy-of-entanglement game introduced by Tomamichel et al. [9].

A monogamy-of-entanglement game consists of a referee Alice and two non-communicating players Bob and Charlie.

It is clear that the correlation of measurement outcomes provided by entangling $A$ with $B$ (resp. $C$) in ${\rho }_{ABC}$ helps Bob (resp. Charlie) guess Alice’s measurement outcome correctly. However, the monogamy-of-entanglement property says, that $A$ cannot be perfectly correlated with both $B$ and $C$ at the same time: indeed, the game cannot be won with probability more than ${\cos }^2(\pi /8)=1/2+1/2\sqrt{2}$ [9]. Further, the game can be repeated in parallel to amplify the hardness of winning exponentially: measuring $\zeta$ qubits independently in random bases and requiring Bob and Charlie to guess all measurement outcomes correctly reduces the winning probability to ${(1/2+1/2\sqrt{2})}^{\zeta }$ [9], which is negligibly small in $\zeta$. This parallel repetition property is crucial for our construction, as it allows us to amplify the hardness of guessing the measurement outcomes to the point where we can extract a bit that is arbitrarily close to uniform from the measurement outcomes, even conditioned on any quantum side-information the malicious coalition may have about the measurement outcomes.

It turns out that a uniformly sampled hash function²²2We would need to send also the seed used to generate the hash function as part of the verifier messages for the honest prover to compute said bit; this does not affect the MoE analysis since the seed is independent of the distribution of measurement outcomes. from a $1$-universal hash family suffices for this from the leftover hash lemma. We can then use the extracted bit as the hardcore bit $b$ in Definition 6 and the measurement outcomes as the acknowledgement: guessing $b$ requires guessing all the measurement outcomes, and sending the acknowledgement correctly also requires guessing all the measurement outcomes. The monogamy-of-entanglement property then guarantees that up to negligible probability, exactly one of the two can be done, which is exactly what we need for the soundness property. Here is the full hardcore bit protocol for two-verifiers (say ${𝖵}_1$ and ${𝖵}_2$ in the toy example).

Two-verifier hardcore bit generation, informal.

• $\mathrm{■}$

  The verifiers ${𝖵}_1$ and ${𝖵}_2$ jointly sample random strings $x_1,\mathrm{\cdots },x_{\zeta }$ and measurement bases ${\theta }_1,\mathrm{\cdots },{\theta }_{\zeta }$. They also jointly sample a random seed $s$ of appropriate length that fixes a $1$-universal hash function $f_s:{\{0,1\}}^{\zeta }\to \{0,1\}$.

• $\mathrm{■}$

  ${𝖵}_1$ sends $\zeta$ qubits in state ${\otimes }_i{H}^{{\theta }_i}|x_i⟩$ and ${𝖵}_2$ sends $(\theta ,s)$, both to the honest prover $𝖯$, in a way that both messages arrive at $𝖯$ at the same time $t^{\ast }$.

• $\mathrm{■}$

  $𝖯$ measures each qubit $i$ in basis ${\theta }_i$ to obtain the mask $x_1,\mathrm{\cdots },x_{\zeta }$ and sends back $x$ to ${𝖵}_2$ as acknowledgement.

• $\mathrm{■}$

  ${𝖵}_1$ and ${𝖵}_2$ check that the acknowledgement is received correctly and in time; if so, they accept, and reject otherwise.

Note that the honest parties in this protocol only prepare and measure single-qubit states. The soundness analysis of the protocol can be reduced to the analysis of a related monogamy-of-entanglement game via a standard purification technique.

The analysis of the soundness of this hardcore bit protocol comprises two key steps. The first is the establishment, via the parallel-repeated MoE game and properties of seeded extractors, of a negligible upper bound on the advantage that an adversarial coalition has in guessing the hardcore bit $b$ when the malicious prover $\widetilde{𝖯}$ may be treated as one of the two guessing parties in the MoE game and the systems responsible for generating the acknowledgement as the other. Parallel repetition soundness is then shown to imply that the malicious prover’s min-entropy of the measurement outcome $x$ conditioned on its own quantum systems is large enough for the extracted bit $b$ to be sufficiently close to uniform conditioned on the same quantum systems via the leftover hash lemma.

The second step is to show via geometry and timing analysis that a coalition of malicious provers can indeed be treated as one guessing party in the MoE game and the systems generating the acknowledgement the other guessing party. In particular, we need to show that the action of these two parties in the QPMIP is equivalent to them independently performing POVM measurements independently on an appropriate ${\rho }_{ABC}$ with $A$, $B$ and $C$ (with $A$ comprising the “virtual” halves of the Bell pairs that ${𝖵}_1$ holds, and $B$, $C$ naturally comprising the malicious prover and honest prover’s quantum systems respectively) independent of the verifier message $(\theta ,s)$.

A useful insight is that by the triangle inequality, the split between the systems that comprise the malicious provers’s qubits and those that generate the acknowledgement must be done ahead of time $t^{\ast }$, which forces the split of $B$ and $C$ to be independent of $(\theta ,s)$. Of course, it is crucial, since the two guessing parties must work independently in the MoE game, to show that after time $t^{\ast }$, the rest of the QPMIP messaging can be simulated by each of them independently in a way that preserves the distribution of messages received by the coalition and that of the acknowledgement.

The soundness of a one-round MIP relies on the independence of each response from queries sent to other provers. In our situation, the PHB scheme allows us to enforce statistical near-independence in the sense of $\delta$-no-signaling: the response to ${𝖵}_2$ can depend on ${𝗊}_1$, as long as it does not depend on ${𝗊}_1$ in a way that allows ${𝖵}_2$ to guess ${𝗊}_1$ with non-negligible probability. Thus, we are able to show that ${\mathrm{𝐐𝐏𝐌𝐈𝐏}}_{(𝒳,𝖽)}^{𝗌}[𝗉]$ contains every language recognisable by no-signaling MIPs, which are MIPs with soundness guaranteed against such no-signaling strategies. Since the class of languages decidable by no-signaling MIPs is $\mathrm{𝐄𝐗𝐏}$ [7], which is believed to be larger than $\mathrm{𝐏𝐒𝐏𝐀𝐂𝐄}$, this relaxation still demonstrates a quantum advantage: ${\mathrm{𝐌𝐈𝐏}}^{\mathrm{𝗇𝗌}}=\mathrm{𝐄𝐗𝐏}\subseteq {\mathrm{𝐐𝐏𝐌𝐈𝐏}}_{(𝒳,𝖽)}^{𝗌}[𝗉]$. Our proof techniques do not enable us to use standard MIP soundness, which would yield $\mathrm{𝐍𝐄𝐗𝐏}\subseteq {\mathrm{𝐐𝐏𝐌𝐈𝐏}}_{(𝒳,𝖽)}^{𝗌}[𝗉]$; we leave it as an open question to determine the precise complexity of ${\mathrm{𝐐𝐏𝐌𝐈𝐏}}_{(𝒳,𝖽)}^{𝗌}[𝗉]$.

Consider a language $ℒ$ decidable by a $𝗄$-prover one-round MIP with no-signaling soundness ${ϵ}_{\mathrm{𝖬𝖨𝖯}}$; the set of such languages is known to be $\mathrm{𝐄𝐗𝐏}$ [7]. We construct a QPMIP for the same language $ℒ$ with the same number of provers and a position mapping that violates the min-ball condition; the position mapping is a ready generalization of Figure 1. The QPMIP verifiers run independent positional hardcore bit schemes in parallel, one for every bit $j$ of every MIP query ${𝗊}_i$; each hardcore bit $b_{i,j}$ is used to encrypt, via XOR, the corresponding query bit ${𝗊}_i^j$, yielding masked bits $m_{i,j}=b_{i,j}\oplus {𝗊}_i^j$. The masked bits are then sent to the honest provers and a response to the MIP queries is requested at the earliest time that the honest provers can receive the appropriate verifier messages, decrypt the MIP queries, and send back the MIP responses.

Completeness of the QPMIP for instances in $ℒ$ is straightforward: the honest provers can compute the hardcore bits and decrypt the MIP queries in time, and respond to the MIP queries in a way that causes the verifiers to accept. The soundness analysis is as follows: for any malicious QPMIP prover strategy, we can define a corresponding colluding malicious MIP prover strategy that simply runs the QPMIP strategy and responds to the MIP queries according to the responses that the QPMIP verifiers receive in this run; clearly, the success probability of this MIP strategy is the same as that of the QPMIP strategy given that the acknowledgements all arrive. We then argue that it must be one of the two cases: either the MIP strategy thus formed is no-signaling, in which case the QPMIP strategy wins with at most ${ϵ}_{\mathrm{𝖬𝖨𝖯}}$ probability, or an acknowledgement is not received correctly in time, in which case the QPMIP verifiers reject anyways. This property is guaranteed by the positional hardcore bit schemes that the verifiers run in parallel; in particular, we narrow down via a hybrid argument to one particular hardcore bit $b_{i,j}$ whose soundness is contradicted when the MIP strategy is signaling.

For the timed quantum communication protocols we consider in this paper, it is useful to think of parties as “provers” and “verifiers”. The provers jointly try to prove some statement (i.e. an instance being in a relation) by answering the verifier queries. At the end of the protocol, the verifiers jointly decide whether to accept or reject.

In particular, we consider $(𝗅+{𝗄}^{\prime })$-party timed quantum communication protocols in which we partition the parties into verifiers $𝒱≔{\{{𝖵}_i\}}_{i\in [𝗅]}$ and (honest or malicious) provers $𝒫≔{\{{\widetilde{𝖯}}_i\}}_{i\in [{𝗄}^{\prime }]}$. When convenient we will sometimes associate $𝒱$ with the set $[𝗅]$ and $𝒫$ with the set $[𝗅+1,𝗅+{𝗄}^{\prime }]$. Since there is a one-to-one mapping between parties and the indices, we use the two interchangeably.

We also rewrite the timed quantum communication protocol tuple as:

in order to distinguish between these two types of parties.

In order to define a proof system that considers provers and verifiers in different arrangements, we introduce a metric space and imagine provers and verifiers at different positions in the metric space. More formally, the proof system additionally depends on the following two ingredients:

• $\mathrm{■}$

  $(𝒳,𝖽)$ is a discrete metric space, equipped with an integer-valued metric $𝖽$ on $𝒳$, i.e., a function $𝖽:𝒳\times 𝒳\to {\mathbb{Z}}_{\ge 0}$.

• $\mathrm{■}$

  $\widetilde{𝗉}$ is an (honest or malicious) position mapping from: $𝒱\cup 𝒫\to 𝒳$ that maps each party to an element in $𝒳$. For every $𝖰\in 𝒱\cup 𝒫$, $\widetilde{𝗉}(𝖰)$ is the “position” assigned to party $𝖰$.

As a shorthand, we denote the distance between two parties ${𝖰}_i,{𝖰}_j\in 𝒱\cup 𝒫$ under the position map $\widetilde{𝗉}$ as

When the position mapping is clear from context, we drop it in the notation and simply write $𝖽({𝖰}_i,{𝖰}_j)$.

Recall that the transmission function $\mathrm{\Lambda }$ is such that if $\mathrm{\Lambda }(i,j,t)=(j^{\prime },t^{\prime })$ then a message sent by party $i$ at time $t$, intended for party $j$, is available at time $t^{\prime }$ to party $j^{\prime }$ (and is $\perp$ if there is no such $t^{\prime },j^{\prime }$). Note that although we defined the transmission function in Definition 7 where $i,j,j^{\prime }$ are all party indices. Since there is a one-to-one mapping between the party indices and the parties, so in the following, we assume that the transmission function is of the form $\mathrm{\Lambda }({𝖰}_i,{𝖰}_j,t)=({𝖰}_{j^{\prime }},t^{\prime })$ where ${𝖰}_i,{𝖰}_j,{𝖰}_{j^{\prime }}$ are parties in $𝒫\cup 𝒱$.

In the following, we define transmission functions for positional interactions based on the principle that the time it takes for a message to travel between two parties is proportional to the distance between them. More formally, we define a positional transmission function ${\mathrm{\Lambda }}_{(𝒳,𝖽),𝗉}$, which depends on the discrete metric space $(𝒳,𝖽)$ and the position mapping $𝗉$ that maps parties to $𝒳$.

Intuitively, the positional transmission function ${\mathrm{\Lambda }}_{(𝒳,𝖽),𝗉}$ should work as follows: After party ${𝖰}_i$ sends a message to party ${𝖰}_j$’s direction at time $t$, party ${𝖰}_j$ should receive it at time $t+{𝖽}_{𝗉}({𝖰}_i,{𝖰}_j)$. This intuition is precisely captured by the following definition of the unrestricted transmission function:

Our results in the quantum setting consider prover strategies with no pre-shared entanglement. In particular, we work in the No-PE (no pre-shared entanglement) model introduced in [4, 9], which requires that a prover (even if malicious) send no message before it is able to receive a message from a verifier. We define the honest transmission functions under this model below:

However, things are more complicated if the provers are malicious: if we use a “directional” transmission function similar to the honest case, intuitively, it means that the verifiers are sending messages to a direction of their choice, i.e. having an intended receiving party. But since malicious provers may intercept and redirect any verifier messages, they can be transmitted to any party, regardless of who the intended receiver is.

To better capture the behavior of malicious provers, our malicious transmission function always transmits the verifier messages to the nearest malicious prover. This assumption is justified since for any malicious prover strategy under the “directional” transmission function, we can construct an equivalent one under our transmission function: we add a malicious prover at every verifier position so that the verifier messages will always be sent to these provers first. They can then forward the verifier messages to any party of their choice. For compatibility with the honest case, verifier messages still have an intended receiver, which is ignored.

Formally, we define the malicious transmission function as follows:

As initial input, the verifiers receive the instance $𝕩$, security parameter $\lambda$ and common randomness $\rho$. Additionally, honest provers also receive the instance $𝕩$ and common randomness $\tau$. Thus, we define input generation functions $\mathrm{𝖨𝗇𝗉}$ and $\overline{\mathrm{𝖨𝗇𝗉}}$ that generate the input state ${𝝆}_{\mathrm{𝗂𝗇}}$ for the honest and malicious game respectively as:

Since we want the verifiers to jointly decide whether to accept or reject at the end of the protocol, the measurement $P_{\mathrm{𝗈𝗎𝗍𝗉𝗎𝗍}}$ should be a binary projective measurement $\{P_{\mathrm{𝗈𝗎𝗍𝗉𝗎𝗍}},𝐈-P_{\mathrm{𝗈𝗎𝗍𝗉𝗎𝗍}}\}$ that acts trivially on prover internal registers, i.e.,

where $P_{\mathrm{𝗈𝗎𝗍𝗉𝗎𝗍}}^{\left(𝖵\right)}=\{P_{\mathrm{𝗈𝗎𝗍𝗉𝗎𝗍}}^{\left(𝖵\right)},𝐈-P_{\mathrm{𝗈𝗎𝗍𝗉𝗎𝗍}}^{\left(𝖵\right)}\}$ is a binary projective measurement on ${\mathscr{H}}_{I_V}:={⨂}_{i\in 𝒱}{\mathscr{H}}_{I_i}$.

A $𝗹$-verifier $𝗄$-prover Quantum Positional Multi-Prover Interactive Proof (separable $\mathbf{(}𝗅\mathbf{,}𝗄\mathbf{)}$-QPMIP) for a relation $ℛ$ is a tuple:

where $(𝒳,𝖽)$ is a discrete metric space, and $𝗉$ is a position mapping to $𝒳$, $T$ is the timeout value, verifiers ${\{{𝖵}_i\}}_{i\in [𝗅]}$ and honest provers ${\{{𝖯}_i\}}_{i\in [𝗄]}$, and the output measurement $P_{\mathrm{𝗈𝗎𝗍𝗉𝗎𝗍}}$ is a binary projective measurement as specified above. The timeout value $T$ and the number of provers $𝗄$ are $\mathrm{𝗉𝗈𝗅𝗒}(n)$, $𝖽$ and the verifier strategy are computable in $\mathrm{𝗉𝗈𝗅𝗒}(n)$-time.

We associate the following types of timed quantum communication protocols to the $\mathrm{𝖰𝖯𝖬𝖨𝖯}$:

• $\mathrm{■}$

  ${\mathrm{𝗍𝖰𝖢𝖯}}^{𝗌}\left[\mathrm{𝖰𝖯𝖬𝖨𝖯}\right]≔(T,{\mathrm{\Lambda }}_{(𝒳,𝖽),𝗉}^{𝗌},{\{{𝖵}_i\}}_{i\in [𝗅]},{\{{𝖯}_i\}}_{i\in [𝗄]},P_{\mathrm{𝗈𝗎𝗍𝗉𝗎𝗍}})$ describes the honest prover strategy under the separable honest position transmission function ${\mathrm{\Lambda }}_{(𝒳,𝖽),𝗉}^{𝗌}$ (see Definition 12).

• $\mathrm{■}$

  ${\mathrm{𝗍𝖰𝖢𝖯}}^{\mathrm{𝗌𝗂}}\left[\mathrm{𝖰𝖯𝖬𝖨𝖯}\right]=(T,{\mathrm{\Lambda }}_{(𝒳,𝖽),𝗉}^{\mathrm{𝗌𝗂}},{\{{𝖵}_i\}}_{i\in [𝗅]},{\{{𝖯}_i\}}_{i\in [𝗄]},P_{\mathrm{𝗈𝗎𝗍𝗉𝗎𝗍}})$ describes the honest prover strategy under the separable and isolated honest position transmission function ${\mathrm{\Lambda }}_{(𝒳,𝖽),𝗉}^{\mathrm{𝗌𝗂}}$ (see Definition 12).

• $\mathrm{■}$

  ${\overline{\mathrm{𝗍𝖰𝖢𝖯}}}^{𝗌}[\mathrm{𝖰𝖯𝖬𝖨𝖯},{\{{\widetilde{𝖯}}_i\}}_{i\in [{𝗄}^{\prime }]},\widetilde{𝗉}]=(T,{\tilde{\mathrm{\Lambda }}}_{(𝒳,𝖽),\widetilde{𝗉}}^{𝗌},{\{{𝖵}_i\}}_{i\in [𝗅]},{\{{\widetilde{𝖯}}_i\}}_{i\in [{𝗄}^{\prime }]},P_{\mathrm{𝗈𝗎𝗍𝗉𝗎𝗍}})$ describes a malicious prover strategy ${\{{\widetilde{𝖯}}_i\}}_{i\in [{𝗄}^{\prime }]}$ at positions defined by $\widetilde{𝗉}$ under the malicious position transmission function ${\tilde{\mathrm{\Lambda }}}_{(𝒳,𝖽),\widetilde{𝗉}}^{𝗌}$ (see Definition 13).

We say that $\mathrm{𝖰𝖯𝖬𝖨𝖯}$ has (perfect) completeness and soundness error ${ϵ}_{\mathrm{𝖰𝖯𝖬𝖨𝖯}}$ if it satisfies the following two properties:

We adapt the proof for ${\mathrm{𝐐𝐌𝐈𝐏}}^{\mathrm{𝗇𝖾}}\subseteq \mathrm{𝐍𝐄𝐗𝐏}$ (In ${\mathrm{𝐐𝐌𝐈𝐏}}^{\mathrm{𝗇𝖾}}$ a quantum verifier interacts with quantum but unentangled provers) in [10], and show the following theorem: