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:1309.2643 · SIAM Journal on Computing

Noisy Interactive Quantum Communication

Gilles Brassard A, Ashwin Nayak, Alain Tapp, Dave Touchette, Falk Unger

Published Jan 1, 2019• 7 citations
arXivHTMLPDF

Abstract

We study the problem of simulating protocols in a quantum communication setting over noisy channels. This problem falls at the intersection of quantum information theory and quantum communication complexity, and it will be of importance for eventual real-world applications of interactive quantum protocols, which can be proved to have exponentially lower communication costs than their classical counterparts for some problems. These are the first results concerning the quantum version of this problem, originally studied by Schulman in a classical setting [L. J. Schulman, Communication on noisy channels: A coding theorem for computation, in Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, IEEE, 1992, pp. 724--733], [L. J. Schulman, Deterministic coding for interactive communication, in Proceedings of the 25th Annual ACM Symposium on Theory of Computing, ACM, 1993, pp. 747--756]. We simulate a length $N$ quantum communication protocol by a length $O(N)$ protocol with arbitrarily small error. Under adversarial noise, our strategy can withstand, for arbitrarily small $\varepsilon>0$, error rates as high as $1/2-\varepsilon$ when parties preshare perfect entanglement, but the classical channel is noisy. We show that this is optimal. We provide extension of these results in several other models of communication, including when also the entanglement is noisy, and when there is no preshared entanglement but communication is quantum and noisy. We also study the case of random noise, for which we provide simulation protocols with positive communication rates and no preshared entanglement over some quantum channels with quantum capacity $C_Q=0$, proving that $C_Q$ is in general not the right characterization of a channel's capacity for interactive quantum communication. Our results are stated for a general quantum communication protocol in which Alice and Bob collaborate, and these results hold in particular in the quantum communication complexity settings of the Yao and Cleve--Buhrman models.

DOI
10.1137/16m109867x

Related papers

Noisy Interactive Quantum Communication

Gilles Brassard A, Ashwin Nayak, Alain Tapp +2 more

We study the problem of simulating protocols in a quantum communication setting over noisy channels. This problem falls at the intersection of quantum information theory and quantum communication complexity, and will be of importance for eventual real-world applications of interactive quantum protocols, which can be proved to have exponentially lower communication costs than their classical counterparts for some problems. These are the first results concerning the quantum version of this problem, originally studied by Schulman in a classical setting (FOCS '92, STOC '93). We simulate a length N quantum communication protocol by a length O(N) protocol with arbitrarily small error. Our simulation strategy has a far higher communication rate than a naive one that encodes separately each particular round of communication to achieve comparable success. Such a strategy would have a communication rate going to 0 in the worst interaction case as the length of the protocols increases, in contrast to our strategy, which has a communication rate proportional to the capacity of the channel used. Under adversarial noise, our strategy can withstand, for arbitrarily small ε > 0, error rates as high as 1/2 -- ε when parties preshare perfect entanglement, but the classical channel is noisy. We show that this is optimal. Note that in this model, the naive strategy would not work for any constant fraction of errors. We provide extension of these results in several other models of communication, including when also the entanglement is noisy, and when there is no pre-shared entanglement but communication is quantum and noisy. We also study the case of random noise, for which we provide simulation protocols with positive communication rates and no pre-shared entanglement over some quantum channels with quantum capacity Q = 0, proving that Q is in general not the right characterization of a channel's capacity for interactive quantum communication. Our results are stated for a general quantum communication protocol in which Alice and Bob collaborate, and hold in particular in the quantum communication complexity settings of the Yao and Cleve-Buhrman models.

Annual Symposium on Foundations of Computer Science•Oct 1, 2014•13 citations

Capacity approaching coding for low noise interactive quantum communication

Debbie Leung, Ashwin Nayak, Ala Shayeghi +3 more

We consider the problem of implementing two-party interactive quantum communication over noisy channels, a necessary endeavor if we wish to fully reap quantum advantages for communication. For an arbitrary protocol with n messages, designed for noiseless qudit channels (where d is arbitrary), our main result is a simulation method that fails with probability less than 2−Θ (nє) and uses a qudit channel n (1 + Θ (√є)) times, of which an є fraction can be corrupted adversarially. The simulation is thus capacity achieving to leading order, and we conjecture that it is optimal up to a constant factor in the √є term. Furthermore, the simulation is in a model that does not require pre-shared resources such as randomness or entanglement between the communicating parties. Perhaps surprisingly, this outperforms the best known overhead of 1 + O(√є loglog1/є) in the corresponding classical model, which is also conjectured to be optimal [Haeupler, FOCS’14]. Our work also improves over the best previously known quantum result where the overhead is a non-explicit large constant [Brassard et al., FOCS’14] for low є.

ACM Symposium on Theory of Computing (STOC)•Jun 20, 2018•4 citations

Non-local games and communication complexity with noisy entanglement

Srijita Kundu, Olivier Lalonde

We study the impact of noise on the theories of quantum nonlocality and entanglement-assisted communication complexity. We consider non-local games and entanglement-assisted communication complexity in a model where Alice and Bob may share arbitrarily many noisy EPR pairs. We study four noise models: depolarizing noise, unital noise, biased reset noise, and erasure noise. Our results are as follows: 1. We upper bound the value of the CHSH game under all these noise models in terms of the noise parameter, without any assumptions on the measurements used in the strategy. 2. We prove a parallel repetition theorem for general non-local games under all noise models except biased reset noise; we prove an improved parallel repetition theorem for unique games. Our parallel repetition rate is smaller than the quantum parallel repetition rate for CHSH in a nontrivial noise regime. 3. Using our unique-game parallel repetition theorem and a relation defined by the CHSH game, we prove a separation between communication complexity with noisy vs noiseless entanglement. This implies an $Ω(n)$ two-way communication lower bound for distilling $n$ EPR pairs from noisy EPR pairs, in the same nontrivial noise regime. 4. We show that any interactive entanglement-assisted communication protocol can be simulated by an SMP communication protocol with noisy shared randomness, with an exponential blowup in communication. This generalizes a known result on the simulation of noiseless shared randomness with noisy shared randomness. 5. We show a polynomial lower bound on the number of copies of noisy EPR pairs required to compute the Equality function with constant communication, under all four noise models. The previous result gives a matching upper bound, and moreover, this answers an open question in the literature on whether logarithmically many noisy shared bits suffice for communication.

quant-pharXiv:2609.05122•Sep 7, 2026•0 citations

Capacity Approaching Coding for Low Noise Interactive Quantum Communication Part I: Large Alphabets

Debbie Leung, Ashwin Nayak, Ala Shayeghi +3 more

We consider the problem of implementing two-party interactive quantum communication over noisy channels, a necessary endeavor if we wish to fully reap quantum advantages for communication. For an arbitrary protocol with n messages, designed for a noiseless qudit channel over a poly (n ) size alphabet, our main result is a simulation method that fails with probability less than 2-Θ(nϵ)and uses a qudit channel over the same alphabet n(1 + Θ(√{ϵ} )) times, of which an ϵ fraction can be corrupted adversarially. The simulation is thus capacity achieving to leading order, and we conjecture that it is optimal up to a constant factor in the √{ϵ} term. Furthermore, the simulation is in a model that does not require pre-shared resources such as randomness or entanglement between the communicating parties. Our work improves over the best previously known quantum result where the overhead is a non-explicit large constant [Brassard et al., SICOMP'19] for low ϵ.

arXiv:2001.02818•IEEE Transactions on Information Theory•Jun 8, 2021•2 citations

Noisy Interactive Quantum Communication

Ala Shayeghi

We consider the problem of implementing two-party interactive quantum communication over noisy channels, a necessary endeavor if we wish to fully reap quantum advantages for communication. For an arbitrary protocol with n messages, designed for noiseless qudit channels (where d is arbitrary), our main result is a simulation method that fails with probability less than 2⁻ᶿ⁽ⁿᵋ⁾ and uses a qudit channel n(1 + Θ(√ε)) times, of which ε fraction can be corrupted adversarially. The simulation is thus capacity achieving to leading order, and we conjecture that it is optimal up to a constant factor in the √ε term. Furthermore, the simulation is in a model that does not require pre-shared resources such as randomness or entanglement between the communicating parties. Surprisingly, this outperforms the best known overhead of 1 + O(√(ε log log 1/ε)) in the corresponding \nclassical model, which is also conjectured to be optimal [Haeupler, FOCS’14]. Our work also improves over the best previously known quantum result where the overhead is a non-explicit large constant [Brassard et al., FOCS’14] for small ε.

•Aug 18, 2020•0 citations

Entanglement cost and quantum channel simulation

Mark M. Wilde

This paper proposes a revised definition for the entanglement cost of a quantum channel $\mathcal{N}$. In particular, it is defined here to be the smallest rate at which entanglement is required, in addition to free classical communication, in order to simulate $n$ calls to $\mathcal{N}$, such that the most general discriminator cannot distinguish the $n$ calls to $\mathcal{N}$ from the simulation. The most general discriminator is one who tests the channels in a sequential manner, one after the other, and this discriminator is known as a quantum tester [Chiribella et al., Phys. Rev. Lett. 101, 060401 (2008)] or one who is implementing a quantum costrategy [Gutoski and Watrous, in Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing STOC '07 (ACM Press, New York, 2007), pp. 565--574]. As such, the proposed revised definition of entanglement cost of a quantum channel leads to a rate that cannot be smaller than the previous notion of a channel's entanglement cost [Berta et al., IEEE Trans. Inf. Theory 59, 6779 (2013)], in which the discriminator is limited to distinguishing parallel uses of the channel from the simulation. Under this revised notion, I prove that the entanglement cost of certain teleportation-simulable channels is equal to the entanglement cost of their underlying resource states. Then I find single-letter formulas for the entanglement cost of some fundamental channel models, including dephasing, erasure, three-dimensional Werner-Holevo channels, and epolarizing channels (complements of depolarizing channels), as well as single-mode pure-loss and pure-amplifier bosonic Gaussian channels. These examples demonstrate that the resource theory of entanglement for quantum channels is not reversible. Finally, I discuss how to generalize the basic notions to arbitrary resource theories.

arXiv:1807.11939•Physical Review A•Oct 31, 2018•51 citations
We study the problem of simulating protocols in a quantum communication setting over noisy channels. This problem falls at the intersection of quantum information theory and quantum communication complexity, and it will be of importance for eventual real-world applications of interactive quantum protocols, which can be proved to have exponentially lower communication costs than their classical counterparts for some problems. These are the first results concerning the quantum version of this problem, originally studied by Schulman in a classical setting [L. J. Schulman, Communication on noisy channels: A coding theorem for computation, in Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, IEEE, 1992, pp. 724--733], [L. J. Schulman, Deterministic coding for interactive communication, in Proceedings of the 25th Annual ACM Symposium on Theory of Computing, ACM, 1993, pp. 747--756]. We simulate a length NNN quantum communication protocol by a length O(N)O(N)O(N) protocol with arbitrarily small error. Under adversarial noise, our strategy can withstand, for arbitrarily small ε>0\varepsilon>0ε>0, error rates as high as 1/2−ε1/2-\varepsilon1/2−ε when parties preshare perfect entanglement, but the classical channel is noisy. We show that this is optimal. We provide extension of these results in several other models of communication, including when also the entanglement is noisy, and when there is no preshared entanglement but communication is quantum and noisy. We also study the case of random noise, for which we provide simulation protocols with positive communication rates and no preshared entanglement over some quantum channels with quantum capacity CQ=0C_Q=0CQ​=0, proving that CQC_QCQ​ is in general not the right characterization of a channel's capacity for interactive quantum communication. Our results are stated for a general quantum communication protocol in which Alice and Bob collaborate, and these results hold in particular in the quantum communication complexity settings of the Yao and Cleve--Buhrman models.
We study the problem of simulating protocols in a quantum communication setting over noisy channels. This problem falls at the intersection of quantum information theory and quantum communication complexity, and will be of importance for eventual real-world applications of interactive quantum protocols, which can be proved to have exponentially lower communication costs than their classical counterparts for some problems. These are the first results concerning the quantum version of this problem, originally studied by Schulman in a classical setting (FOCS '92, STOC '93). We simulate a length N quantum communication protocol by a length O(N) protocol with arbitrarily small error. Our simulation strategy has a far higher communication rate than a naive one that encodes separately each particular round of communication to achieve comparable success. Such a strategy would have a communication rate going to 0 in the worst interaction case as the length of the protocols increases, in contrast to our strategy, which has a communication rate proportional to the capacity of the channel used. Under adversarial noise, our strategy can withstand, for arbitrarily small ε > 0, error rates as high as 1/2 -- ε when parties preshare perfect entanglement, but the classical channel is noisy. We show that this is optimal. Note that in this model, the naive strategy would not work for any constant fraction of errors. We provide extension of these results in several other models of communication, including when also the entanglement is noisy, and when there is no pre-shared entanglement but communication is quantum and noisy. We also study the case of random noise, for which we provide simulation protocols with positive communication rates and no pre-shared entanglement over some quantum channels with quantum capacity Q = 0, proving that Q is in general not the right characterization of a channel's capacity for interactive quantum communication. Our results are stated for a general quantum communication protocol in which Alice and Bob collaborate, and hold in particular in the quantum communication complexity settings of the Yao and Cleve-Buhrman models.
We consider the problem of implementing two-party interactive quantum communication over noisy channels, a necessary endeavor if we wish to fully reap quantum advantages for communication. For an arbitrary protocol with n messages, designed for noiseless qudit channels (where d is arbitrary), our main result is a simulation method that fails with probability less than 2−Θ (nє) and uses a qudit channel n (1 + Θ (√є)) times, of which an є fraction can be corrupted adversarially. The simulation is thus capacity achieving to leading order, and we conjecture that it is optimal up to a constant factor in the √є term. Furthermore, the simulation is in a model that does not require pre-shared resources such as randomness or entanglement between the communicating parties. Perhaps surprisingly, this outperforms the best known overhead of 1 + O(√є loglog1/є) in the corresponding classical model, which is also conjectured to be optimal [Haeupler, FOCS’14]. Our work also improves over the best previously known quantum result where the overhead is a non-explicit large constant [Brassard et al., FOCS’14] for low є.
We study the impact of noise on the theories of quantum nonlocality and entanglement-assisted communication complexity. We consider non-local games and entanglement-assisted communication complexity in a model where Alice and Bob may share arbitrarily many noisy EPR pairs. We study four noise models: depolarizing noise, unital noise, biased reset noise, and erasure noise. Our results are as follows: 1. We upper bound the value of the CHSH game under all these noise models in terms of the noise parameter, without any assumptions on the measurements used in the strategy. 2. We prove a parallel repetition theorem for general non-local games under all noise models except biased reset noise; we prove an improved parallel repetition theorem for unique games. Our parallel repetition rate is smaller than the quantum parallel repetition rate for CHSH in a nontrivial noise regime. 3. Using our unique-game parallel repetition theorem and a relation defined by the CHSH game, we prove a separation between communication complexity with noisy vs noiseless entanglement. This implies an Ω(n)Ω(n)Ω(n) two-way communication lower bound for distilling nnn EPR pairs from noisy EPR pairs, in the same nontrivial noise regime. 4. We show that any interactive entanglement-assisted communication protocol can be simulated by an SMP communication protocol with noisy shared randomness, with an exponential blowup in communication. This generalizes a known result on the simulation of noiseless shared randomness with noisy shared randomness. 5. We show a polynomial lower bound on the number of copies of noisy EPR pairs required to compute the Equality function with constant communication, under all four noise models. The previous result gives a matching upper bound, and moreover, this answers an open question in the literature on whether logarithmically many noisy shared bits suffice for communication.
We consider the problem of implementing two-party interactive quantum communication over noisy channels, a necessary endeavor if we wish to fully reap quantum advantages for communication. For an arbitrary protocol with n messages, designed for a noiseless qudit channel over a poly (n ) size alphabet, our main result is a simulation method that fails with probability less than 2-Θ(nϵ)and uses a qudit channel over the same alphabet n(1 + Θ(√{ϵ} )) times, of which an ϵ fraction can be corrupted adversarially. The simulation is thus capacity achieving to leading order, and we conjecture that it is optimal up to a constant factor in the √{ϵ} term. Furthermore, the simulation is in a model that does not require pre-shared resources such as randomness or entanglement between the communicating parties. Our work improves over the best previously known quantum result where the overhead is a non-explicit large constant [Brassard et al., SICOMP'19] for low ϵ.
We consider the problem of implementing two-party interactive quantum communication over noisy channels, a necessary endeavor if we wish to fully reap quantum advantages for communication. For an arbitrary protocol with n messages, designed for noiseless qudit channels (where d is arbitrary), our main result is a simulation method that fails with probability less than 2⁻ᶿ⁽ⁿᵋ⁾ and uses a qudit channel n(1 + Θ(√ε)) times, of which ε fraction can be corrupted adversarially. The simulation is thus capacity achieving to leading order, and we conjecture that it is optimal up to a constant factor in the √ε term. Furthermore, the simulation is in a model that does not require pre-shared resources such as randomness or entanglement between the communicating parties. Surprisingly, this outperforms the best known overhead of 1 + O(√(ε log log 1/ε)) in the corresponding \nclassical model, which is also conjectured to be optimal [Haeupler, FOCS’14]. Our work also improves over the best previously known quantum result where the overhead is a non-explicit large constant [Brassard et al., FOCS’14] for small ε.
This paper proposes a revised definition for the entanglement cost of a quantum channel N\mathcal{N}N. In particular, it is defined here to be the smallest rate at which entanglement is required, in addition to free classical communication, in order to simulate nnn calls to N\mathcal{N}N, such that the most general discriminator cannot distinguish the nnn calls to N\mathcal{N}N from the simulation. The most general discriminator is one who tests the channels in a sequential manner, one after the other, and this discriminator is known as a quantum tester [Chiribella et al., Phys. Rev. Lett. 101, 060401 (2008)] or one who is implementing a quantum costrategy [Gutoski and Watrous, in Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing STOC '07 (ACM Press, New York, 2007), pp. 565--574]. As such, the proposed revised definition of entanglement cost of a quantum channel leads to a rate that cannot be smaller than the previous notion of a channel's entanglement cost [Berta et al., IEEE Trans. Inf. Theory 59, 6779 (2013)], in which the discriminator is limited to distinguishing parallel uses of the channel from the simulation. Under this revised notion, I prove that the entanglement cost of certain teleportation-simulable channels is equal to the entanglement cost of their underlying resource states. Then I find single-letter formulas for the entanglement cost of some fundamental channel models, including dephasing, erasure, three-dimensional Werner-Holevo channels, and epolarizing channels (complements of depolarizing channels), as well as single-mode pure-loss and pure-amplifier bosonic Gaussian channels. These examples demonstrate that the resource theory of entanglement for quantum channels is not reversible. Finally, I discuss how to generalize the basic notions to arbitrary resource theories.