Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1310.7954 · Leibniz international proceedings in informatics

Quantum Hedging in Two-Round Prover-Verifier Interactions

Srinivasan Arunachalam, Abel Molina, Russo, Vincent

Published Oct 29, 2013• 4 citations
arXivHTMLPDF

Abstract

We consider the problem of a particular kind of quantum correlation that arises in some two-party games. In these games, one player is presented with a question they must answer, yielding an outcome of either 'win' or 'lose'. Molina and Watrous (arXiv:1104.1140) studied such a game that exhibited a perfect form of hedging, where the risk of losing a first game can completely offset the corresponding risk for a second game. This is a non-classical quantum phenomenon, and establishes the impossibility of performing strong error-reduction for quantum interactive proof systems by parallel repetition, unlike for classical interactive proof systems. We take a step in this article towards a better understanding of the hedging phenomenon by giving a complete characterization of when perfect hedging is possible for a natural generalization of the game in arXiv:1104.1140. Exploring in a different direction the subject of quantum hedging, and motivated by implementation concerns regarding loss-tolerance, we also consider a variation of the protocol where the player who receives the question can choose to restart the game rather than return an answer. We show that in this setting there is no possible hedging for any game played with state spaces corresponding to finite-dimensional complex Euclidean spaces.

DOI
10.4230/lipics.tqc.2017.5

Related papers

Quantum Coin Hedging, and a Counter Measure

Maor Ganz, Or Sattath

A quantum board game is a multi-round protocol between a single quantum player against the quantum board. Molina and Watrous discovered quantum hedging. They gave an example for perfect quantum hedging: a board game with winning probability < 1, such that the player can win with certainty at least 1-out-of-2 quantum board games played in parallel. Here we show that perfect quantum hedging occurs in a cryptographic protocol – quantum coin flipping. For this reason, when cryptographic protocols are composed in parallel, hedging may introduce serious challenges into their analysis. We also show that hedging cannot occur when playing two-outcome board games in sequence. This is done by showing a formula for the value of sequential two-outcome board games, which depends only on the optimal value of a single board game; this formula applies in a more general setting of possible target functions, in which hedging is only a special case.

arXiv:1703.03887•Leibniz international proceedings in informatics•Mar 11, 2017•1 citation

Parallel Repetition of Prover-Verifier Quantum Interactions

Abel Molina

In this thesis, we answer several questions about the behaviour of prover-verifier interactions under parallel repetition when quantum information is allowed, and the verifier acts independently in them. We first consider the case in which a value is associated with each of the possible outcomes of an interaction. We prove that it is not possible for the prover to improve on the optimum average value per repetition by repeating the protocol multiple times in parallel. We look then at games in which the outcomes are classified into two types, winning outcomes and losing outcomes. We ask what is the optimal probability for the prover of winning at least k times out of n parallel repetitions, given that the optimal probability of winning when only one repetition is considered is $p$. A reasonable conjecture for the answer would be \sum_{m \geq k} {n \choose m} p^m (1-p)^{n-m}, as that is the answer when it is optimal for the prover to act independently. This is known to be the correct answer when k=n, and also in the classical case. It is also correct in some generalizations of the classical case that we will discuss later. We will show how this cannot be extended to all cases, presenting an example of an interaction with k=1,n=2 in which p\approx 0.85, but it is possible to always win at least once. We will then give some upper bounds on the optimal probability for the prover of winning k times out of n parallel repetitions. These bounds are expressed as a function of p. Finally, we will connect our results to the study of error reduction for quantum interactive proofs using parallel repetition.

arXiv:1203.4885•Mar 22, 2012•0 citations

Quantum interaction can superactivate cheating under parallel repetition

Archishna Bhattacharyya, Laura Mančinska, Yuming Zhao

We study interactive multiprover games and many-round protocols in which the communication between the verifier and the provers is quantum. Parallel repetition is known to suppress soundness error of classical two-prover games arbitrarily close to zero, as shown by Raz (STOC '95), even with quantum strategies as shown by Yuen (ICALP '16), and Bavarian, Vidick and Yuen (STOC '17). Yet, we show that quantum communication can have the opposite, unexpected effect. Specifically, we exhibit a one-round quantum game and two-round $\mathsf{QMIP}$ protocols whose local (unentangled) value is strictly less than one for a single instance, yet equals one under $n$-fold parallel repetition for every $n \geq 2$. The key is that parallel repetition not only imposes additional winning conditions but also supplies additional quantum resources as entanglement in the exchanged states can be exploited jointly across copies. Our multiround examples build on superactivation of zero-error capacities of quantum channels. To establish this connection, we introduce quantum games and interactive protocols which capture the one-shot zero-error classical and quantum capacities, both with and without entanglement assistance. Our constructions use quantum-state verification and a teleportation-based reduction from two rounds to one. In contrast, when shared entanglement is allowed, we show that parallel repetition cannot increase the entangled value when at most $3$ messages are exchanged, consistent with classical results of Bellare, Impagliazzo and Naor (FOCS '97), and that of single-prover systems by Kitaev and Watrous (STOC '00). Combining this monotonicity with our quantum game-channel correspondence, we show that entanglement-assisted zero-error classical and quantum capacities cannot be superactivated.

quant-pharXiv:2609.31223•Sep 28, 2026•0 citations

Parallel Repetition of Prover-Verifier Quantum Interactions

Abel Molina

In this thesis, we answer several questions about the behaviour of prover-verifier interactions under parallel repetition when quantum information is allowed, and the verifier acts independently in them. \n \nWe first consider the case in which a value is associated with each of the possible outcomes of an interaction. We prove that it is not possible for the prover to improve on the optimum average value per repetition by repeating the protocol multiple times in parallel. \n \nWe look then at games in which the outcomes are classified into two types, winning outcomes and losing outcomes. We ask what is the optimal probability for the prover of winning at least k times out of n parallel repetitions, given that the optimal probability of winning when only one repetition is considered is p. A reasonable conjecture for the answer would be the answer when it is optimal for the prover to act independently. This is known to be the correct answer when k=n. We will show how this cannot be extended to the general case, presenting an example of an interaction with k=1,n=2 in which p is approximately 0.85, but it is possible to always win at least once. We will then give some upper bounds on the optimal probability for the prover of winning k times out of n parallel repetitions. These bounds are expressed as a function of p. \n \nFinally, we connect our results to the study of error reduction for quantum interactive proofs using parallel repetition.

•Jan 1, 2011•0 citations

Hedging bets with correlated quantum strategies

Abel Molina, John Watrous

This paper studies the potential advantages of correlated answers in hypothetical tests of a simple interactive type. In these tests, an individual is presented with a question, to which he or she must respond with an answer, leading to an outcome of pass or fail . In quantum information theoretic variants of these tests, we show it is possible for an individual to correlate their answers across multiple tests in a way that produces a striking non-classical behaviour. Specifically, there exist tests for which no strategy can lead to the outcome pass with certainty, but where answers to multiple, independently administered tests can be correlated so that at least one test is passed with certainty. This phenomenon, which gives rise to a perfect form of hedging when considered in a game-theoretic setting, is quantum in nature: it is not possible in classical variants of the tests we consider.

arXiv:1104.1140•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Apr 11, 2012•11 citations

Strong Parallel Repetition Theorem for Quantum XOR Proof Systems

Richard Cleve, William Slofstra, Falk Unger +1 more

We consider a class of two-prover interactive proof systems where each prover returns a single bit to the verifier and the verifier's verdict is a function of the XOR of the two bits received. We show that, when the provers are allowed to coordinate their behavior using a shared entangled quantum state, a perfect parallel repetition theorem holds in the following sense. The prover's optimal success probability for simultaneously playing a collection of XOR proof systems is exactly the product of the individual optimal success probabilities. This property is remarkable in view of the fact that, in the classical case (where the provers can only utilize classical information), it does not hold. The theorem is proved by analyzing parities of XOR proof systems using semidefinite programming techniques, which we then relate to parallel repetitions of XOR games via Fourier analysis.

arXiv:quant-ph/0608146•Aug 18, 2006•26 citations
We consider the problem of a particular kind of quantum correlation that arises in some two-party games. In these games, one player is presented with a question they must answer, yielding an outcome of either 'win' or 'lose'. Molina and Watrous (arXiv:1104.1140) studied such a game that exhibited a perfect form of hedging, where the risk of losing a first game can completely offset the corresponding risk for a second game. This is a non-classical quantum phenomenon, and establishes the impossibility of performing strong error-reduction for quantum interactive proof systems by parallel repetition, unlike for classical interactive proof systems. We take a step in this article towards a better understanding of the hedging phenomenon by giving a complete characterization of when perfect hedging is possible for a natural generalization of the game in arXiv:1104.1140. Exploring in a different direction the subject of quantum hedging, and motivated by implementation concerns regarding loss-tolerance, we also consider a variation of the protocol where the player who receives the question can choose to restart the game rather than return an answer. We show that in this setting there is no possible hedging for any game played with state spaces corresponding to finite-dimensional complex Euclidean spaces.
A quantum board game is a multi-round protocol between a single quantum player against the quantum board. Molina and Watrous discovered quantum hedging. They gave an example for perfect quantum hedging: a board game with winning probability < 1, such that the player can win with certainty at least 1-out-of-2 quantum board games played in parallel. Here we show that perfect quantum hedging occurs in a cryptographic protocol – quantum coin flipping. For this reason, when cryptographic protocols are composed in parallel, hedging may introduce serious challenges into their analysis. We also show that hedging cannot occur when playing two-outcome board games in sequence. This is done by showing a formula for the value of sequential two-outcome board games, which depends only on the optimal value of a single board game; this formula applies in a more general setting of possible target functions, in which hedging is only a special case.
In this thesis, we answer several questions about the behaviour of prover-verifier interactions under parallel repetition when quantum information is allowed, and the verifier acts independently in them. We first consider the case in which a value is associated with each of the possible outcomes of an interaction. We prove that it is not possible for the prover to improve on the optimum average value per repetition by repeating the protocol multiple times in parallel. We look then at games in which the outcomes are classified into two types, winning outcomes and losing outcomes. We ask what is the optimal probability for the prover of winning at least k times out of n parallel repetitions, given that the optimal probability of winning when only one repetition is considered is ppp. A reasonable conjecture for the answer would be \sum_{m \geq k} {n \choose m} p^m (1-p)^{n-m}, as that is the answer when it is optimal for the prover to act independently. This is known to be the correct answer when k=n, and also in the classical case. It is also correct in some generalizations of the classical case that we will discuss later. We will show how this cannot be extended to all cases, presenting an example of an interaction with k=1,n=2 in which p\approx 0.85, but it is possible to always win at least once. We will then give some upper bounds on the optimal probability for the prover of winning k times out of n parallel repetitions. These bounds are expressed as a function of p. Finally, we will connect our results to the study of error reduction for quantum interactive proofs using parallel repetition.
We study interactive multiprover games and many-round protocols in which the communication between the verifier and the provers is quantum. Parallel repetition is known to suppress soundness error of classical two-prover games arbitrarily close to zero, as shown by Raz (STOC '95), even with quantum strategies as shown by Yuen (ICALP '16), and Bavarian, Vidick and Yuen (STOC '17). Yet, we show that quantum communication can have the opposite, unexpected effect. Specifically, we exhibit a one-round quantum game and two-round QMIP\mathsf{QMIP}QMIP protocols whose local (unentangled) value is strictly less than one for a single instance, yet equals one under nnn-fold parallel repetition for every n≥2n \geq 2n≥2. The key is that parallel repetition not only imposes additional winning conditions but also supplies additional quantum resources as entanglement in the exchanged states can be exploited jointly across copies. Our multiround examples build on superactivation of zero-error capacities of quantum channels. To establish this connection, we introduce quantum games and interactive protocols which capture the one-shot zero-error classical and quantum capacities, both with and without entanglement assistance. Our constructions use quantum-state verification and a teleportation-based reduction from two rounds to one. In contrast, when shared entanglement is allowed, we show that parallel repetition cannot increase the entangled value when at most 333 messages are exchanged, consistent with classical results of Bellare, Impagliazzo and Naor (FOCS '97), and that of single-prover systems by Kitaev and Watrous (STOC '00). Combining this monotonicity with our quantum game-channel correspondence, we show that entanglement-assisted zero-error classical and quantum capacities cannot be superactivated.
In this thesis, we answer several questions about the behaviour of prover-verifier interactions under parallel repetition when quantum information is allowed, and the verifier acts independently in them. \n \nWe first consider the case in which a value is associated with each of the possible outcomes of an interaction. We prove that it is not possible for the prover to improve on the optimum average value per repetition by repeating the protocol multiple times in parallel. \n \nWe look then at games in which the outcomes are classified into two types, winning outcomes and losing outcomes. We ask what is the optimal probability for the prover of winning at least k times out of n parallel repetitions, given that the optimal probability of winning when only one repetition is considered is p. A reasonable conjecture for the answer would be the answer when it is optimal for the prover to act independently. This is known to be the correct answer when k=n. We will show how this cannot be extended to the general case, presenting an example of an interaction with k=1,n=2 in which p is approximately 0.85, but it is possible to always win at least once. We will then give some upper bounds on the optimal probability for the prover of winning k times out of n parallel repetitions. These bounds are expressed as a function of p. \n \nFinally, we connect our results to the study of error reduction for quantum interactive proofs using parallel repetition.
This paper studies the potential advantages of correlated answers in hypothetical tests of a simple interactive type. In these tests, an individual is presented with a question, to which he or she must respond with an answer, leading to an outcome of pass or fail . In quantum information theoretic variants of these tests, we show it is possible for an individual to correlate their answers across multiple tests in a way that produces a striking non-classical behaviour. Specifically, there exist tests for which no strategy can lead to the outcome pass with certainty, but where answers to multiple, independently administered tests can be correlated so that at least one test is passed with certainty. This phenomenon, which gives rise to a perfect form of hedging when considered in a game-theoretic setting, is quantum in nature: it is not possible in classical variants of the tests we consider.
We consider a class of two-prover interactive proof systems where each prover returns a single bit to the verifier and the verifier's verdict is a function of the XOR of the two bits received. We show that, when the provers are allowed to coordinate their behavior using a shared entangled quantum state, a perfect parallel repetition theorem holds in the following sense. The prover's optimal success probability for simultaneously playing a collection of XOR proof systems is exactly the product of the individual optimal success probabilities. This property is remarkable in view of the fact that, in the classical case (where the provers can only utilize classical information), it does not hold. The theorem is proved by analyzing parities of XOR proof systems using semidefinite programming techniques, which we then relate to parallel repetitions of XOR games via Fourier analysis.