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:2608.03986

A lower bound on the classical simulation cost of star-network correlations

Martin J. Renner

quant-phSubmitted Aug 4, 2026• Announced Aug 5, 2026• 0 citations
arXivHTMLPDF

Abstract

It is well established that quantum strategies outperform classical ones in several communication tasks. We study the quantum communication complexity of correlations arising from joint measurements on quantum systems distributed across a star network, where several parties each send a quantum system to a central node. We introduce an exclusion task that can be solved perfectly when each party sends a quantum $d$-level system, but would require a large classical message otherwise. In fact, the task cannot be solved with certainty if each of the $n$ parties sends a classical message with less than $n^{(d-1)}$ symbols. This implies an advantage of using quantum over classical messages in that scenario that scales with both, the dimension of the quantum system and the number of systems measured simultaneously. As an application, this shows that no finite-size classical description of a qubit suffices to reproduce the statistics of a joint measurement on sufficiently many qubits.

Comments
5+4 pages

Related papers

The cost of classically simulating quantum communication is as high as it could be

Riccardo Castellano, Pavel Sekatski, Nicolas Brunner

A long-standing open question is to characterize the classical communication cost of simulating the correlations arising from measurements on finite-dimensional quantum systems. We consider this question in the prepare-and-measure scenario. First we construct a classical simulation model involving a finite average number of bits of one-way communication that simulates exactly the correlations arising from arbitrary $d$-dimensional quantum states and arbitrary measurements. Second, we show that no classical simulation protocol involving a finite average message dimension can exist for $d\geq 4$, hence strengthening a recent result of de Gois, Santos and Vieira. Our first result relies on a more general simulation theorem which can be applied to certain continuous variable (i.e. infinite-dimensional) quantum systems, and even beyond quantum theory, e.g. to generalized probabilistic theories. In particular, we show that multimode Gaussian states of bounded average energy and general Gaussian measurements admit an exact classical simulation with a finite expected number of bits. Overall, our results show that the classical simulation cost of quantum communication is essentially as high as it could be.

quant-pharXiv:2610.19060•Oct 15, 2026•0 citations

Bounding the classical cost of simulating quantum behaviors in the prepare-and-measure scenario

Sebastian Schlösser, Matthias Kleinmann

We study the prepare-and-measure scenario in which Alice transmits a quantum system to Bob, who then performs a quantum measurement. The quantum state of the system is unknown to Bob, and the measurement is unknown to Alice. It has recently been shown that shared randomness and two bits of classical communication are necessary and sufficient to simulate the transmission of a qubit. We show that the communication cost can be reduced to an average of $1.89$ bits. We then study restricted sets of state preparations: First, for a restriction to real-valued qubit states, if the communication of a classical trit is sufficient, we show that the corresponding protocol must have a convoluted form. We then reduce the smallest qubit scenario requiring two bits of classical communication to only $6$ state preparations and $5$ measurements. For a qutrit, it is not known whether the communication cost is finite; we identify a scenario that requires at least $5$ classical messages, already for the simulation of the real qutrit. Finally, we develop a method for restricted sets of states, that allows us to lower bound the classical communication cost based solely on the set of quantum states.

quant-pharXiv:2603.01255•Mar 3, 2026•0 citations

Lower bound on the communication cost of simulating bipartite quantum correlations

Tamás Vértesi, Erika Bene

Suppose Alice and Bob share a maximally entangled state of any finite dimension and each perform two-outcome measurements on the respective part of the state. It is known, due to the recent result of Regev and Toner, that if a classical model is augmented with two bits of communication, then all the quantum correlations arising from these measurements can be reproduced. Here, we show that two bits of communication are in fact necessary for the perfect simulation. In particular, we prove that a pair of maximally entangled four-dimensional quantum systems cannot be simulated by a classical model augmented by only one bit of communication.

arXiv:0904.1390•Physical Review A•Dec 8, 2009•15 citations

Interaction in Quantum Communication

Hartmut Klauck, Ashwin Nayak, Amnon Ta‐Shma +1 more

In some scenarios there are ways of conveying information with many fewer, even exponentially fewer, qubits than possible classically. Moreover, some of these methods have a very simple structure-they involve only few message exchanges between the communicating parties. It is therefore natural to ask whether every classical protocol may be transformed to a "simpler" quantum protocol-one that has similar efficiency, but uses fewer message exchanges. We show that for any constant k, there is a problem such that its k+1 message classical communication complexity is exponentially smaller than its k message quantum communication complexity. This, in particular, proves a round hierarchy theorem for quantum communication complexity, and implies, via a simple reduction, an Omega(N1k/) lower bound for k message quantum protocols for Set Disjointness for constant k. Enroute, we prove information-theoretic lemmas, and define a related measure of correlation, the informational distance, that we believe may be of significance in other contexts as well

arXiv:quant-ph/0603135•IEEE Transactions on Information Theory•Jun 1, 2007•43 citations

Bounding Two-Way Average Communication Cost of Simulating Quantum Correlations

Kai-Siang Chen, Gelo Noel M. Tabia, Bo-An Tsai +2 more

Bell nonlocal correlations cannot be reproduced by local hidden-variable models without communication, making classical communication cost a natural quantitative measure of nonlocality. Although finite communication always suffices to simulate any correlation in a fixed finite Bell scenario, determining the minimum amount needed to (exactly) simulate any given nonlocal correlation remains challenging, especially in the average-cost setting. Here, we derive lower bounds on input-average communication cost from nonlocal games, allowing variable-length, fully interactive two-way protocols. When applied to parallel games, these bounds yield explicit finite quantum correlations for which the exact simulation cost exceeds any prescribed finite input-average communication budget. For $n$ parallel Magic-Square-winning correlations, we prove a lower bound of $n\log_2(3/2)$ bits and give a one-way communication protocol that attains this rate asymptotically. For the quantum correlation maximally winning the $n$-copy of the Clauser--Horne--Shimony--Holt nonlocal game, we obtain an input-average lower bound of approximately $0.04627n$ bits for exact simulation. Finally, we formulate a hierarchy of lower bounds and complementary upper bounds using deterministic correlations up to chosen communication costs. Both recover the exact input-average cost at their final levels, and if the bounds agree at lower levels, their common value yields the exact input-average cost without needing to consider all communication strategies.

quant-pharXiv:2610.04648•Oct 6, 2026•0 citations

No-go theorem for generic simulation of qubit channels with finite classical resources

Sahil Gopalkrishna Naik, Mani Zartab, Nicolas Gisin +1 more

Abstract Can quantum processes be simulated using only classical resources? This question delineates the boundary between classical and quantum models and clarifies the origin of quantum advantage in information processing. We address this question through the task of quantum channel simulation, where a sender (Alice) holds the classical description of a quantum state and wishes to transmit it to a receiver (Bob) for measurement. Prior work has shown that, for qubit channels, 2 bits of forward communication with shared randomness suffice to reproduce the statistics of any single-qubit measurement. We argue, however, that true channel simulation requires reproducing statistics of joint measurements—including entangled effects—on Alice’s state and an auxiliary system held by Bob. Such scenarios naturally arise in network communication, where some nodes know the state, while others do not. We prove that a perfect qubit channel cannot be simulated with any finite amount of classical communication, even using the most general multi-round, bidirectional protocols. We further show that this no-go result is rooted in the necessity of reproducing statistics associated with entangled effects. On the other hand, we show that noisy qubit channels, such as depolarizing channels, admit classical simulation, though the required communication diverges as noise decreases.

arXiv:2501.15807•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Mar 1, 2026•0 citations
It is well established that quantum strategies outperform classical ones in several communication tasks. We study the quantum communication complexity of correlations arising from joint measurements on quantum systems distributed across a star network, where several parties each send a quantum system to a central node. We introduce an exclusion task that can be solved perfectly when each party sends a quantum ddd-level system, but would require a large classical message otherwise. In fact, the task cannot be solved with certainty if each of the nnn parties sends a classical message with less than n(d−1)n^{(d-1)}n(d−1) symbols. This implies an advantage of using quantum over classical messages in that scenario that scales with both, the dimension of the quantum system and the number of systems measured simultaneously. As an application, this shows that no finite-size classical description of a qubit suffices to reproduce the statistics of a joint measurement on sufficiently many qubits.
A long-standing open question is to characterize the classical communication cost of simulating the correlations arising from measurements on finite-dimensional quantum systems. We consider this question in the prepare-and-measure scenario. First we construct a classical simulation model involving a finite average number of bits of one-way communication that simulates exactly the correlations arising from arbitrary ddd-dimensional quantum states and arbitrary measurements. Second, we show that no classical simulation protocol involving a finite average message dimension can exist for d≥4d\geq 4d≥4, hence strengthening a recent result of de Gois, Santos and Vieira. Our first result relies on a more general simulation theorem which can be applied to certain continuous variable (i.e. infinite-dimensional) quantum systems, and even beyond quantum theory, e.g. to generalized probabilistic theories. In particular, we show that multimode Gaussian states of bounded average energy and general Gaussian measurements admit an exact classical simulation with a finite expected number of bits. Overall, our results show that the classical simulation cost of quantum communication is essentially as high as it could be.
We study the prepare-and-measure scenario in which Alice transmits a quantum system to Bob, who then performs a quantum measurement. The quantum state of the system is unknown to Bob, and the measurement is unknown to Alice. It has recently been shown that shared randomness and two bits of classical communication are necessary and sufficient to simulate the transmission of a qubit. We show that the communication cost can be reduced to an average of 1.891.891.89 bits. We then study restricted sets of state preparations: First, for a restriction to real-valued qubit states, if the communication of a classical trit is sufficient, we show that the corresponding protocol must have a convoluted form. We then reduce the smallest qubit scenario requiring two bits of classical communication to only 666 state preparations and 555 measurements. For a qutrit, it is not known whether the communication cost is finite; we identify a scenario that requires at least 555 classical messages, already for the simulation of the real qutrit. Finally, we develop a method for restricted sets of states, that allows us to lower bound the classical communication cost based solely on the set of quantum states.
Suppose Alice and Bob share a maximally entangled state of any finite dimension and each perform two-outcome measurements on the respective part of the state. It is known, due to the recent result of Regev and Toner, that if a classical model is augmented with two bits of communication, then all the quantum correlations arising from these measurements can be reproduced. Here, we show that two bits of communication are in fact necessary for the perfect simulation. In particular, we prove that a pair of maximally entangled four-dimensional quantum systems cannot be simulated by a classical model augmented by only one bit of communication.
In some scenarios there are ways of conveying information with many fewer, even exponentially fewer, qubits than possible classically. Moreover, some of these methods have a very simple structure-they involve only few message exchanges between the communicating parties. It is therefore natural to ask whether every classical protocol may be transformed to a "simpler" quantum protocol-one that has similar efficiency, but uses fewer message exchanges. We show that for any constant k, there is a problem such that its k+1 message classical communication complexity is exponentially smaller than its k message quantum communication complexity. This, in particular, proves a round hierarchy theorem for quantum communication complexity, and implies, via a simple reduction, an Omega(N1k/) lower bound for k message quantum protocols for Set Disjointness for constant k. Enroute, we prove information-theoretic lemmas, and define a related measure of correlation, the informational distance, that we believe may be of significance in other contexts as well
Bell nonlocal correlations cannot be reproduced by local hidden-variable models without communication, making classical communication cost a natural quantitative measure of nonlocality. Although finite communication always suffices to simulate any correlation in a fixed finite Bell scenario, determining the minimum amount needed to (exactly) simulate any given nonlocal correlation remains challenging, especially in the average-cost setting. Here, we derive lower bounds on input-average communication cost from nonlocal games, allowing variable-length, fully interactive two-way protocols. When applied to parallel games, these bounds yield explicit finite quantum correlations for which the exact simulation cost exceeds any prescribed finite input-average communication budget. For nnn parallel Magic-Square-winning correlations, we prove a lower bound of nlog⁡2(3/2)n\log_2(3/2)nlog2​(3/2) bits and give a one-way communication protocol that attains this rate asymptotically. For the quantum correlation maximally winning the nnn-copy of the Clauser--Horne--Shimony--Holt nonlocal game, we obtain an input-average lower bound of approximately 0.04627n0.04627n0.04627n bits for exact simulation. Finally, we formulate a hierarchy of lower bounds and complementary upper bounds using deterministic correlations up to chosen communication costs. Both recover the exact input-average cost at their final levels, and if the bounds agree at lower levels, their common value yields the exact input-average cost without needing to consider all communication strategies.
Abstract Can quantum processes be simulated using only classical resources? This question delineates the boundary between classical and quantum models and clarifies the origin of quantum advantage in information processing. We address this question through the task of quantum channel simulation, where a sender (Alice) holds the classical description of a quantum state and wishes to transmit it to a receiver (Bob) for measurement. Prior work has shown that, for qubit channels, 2 bits of forward communication with shared randomness suffice to reproduce the statistics of any single-qubit measurement. We argue, however, that true channel simulation requires reproducing statistics of joint measurements—including entangled effects—on Alice’s state and an auxiliary system held by Bob. Such scenarios naturally arise in network communication, where some nodes know the state, while others do not. We prove that a perfect qubit channel cannot be simulated with any finite amount of classical communication, even using the most general multi-round, bidirectional protocols. We further show that this no-go result is rooted in the necessity of reproducing statistics associated with entangled effects. On the other hand, we show that noisy qubit channels, such as depolarizing channels, admit classical simulation, though the required communication diverges as noise decreases.