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

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

Sebastian Schlösser, Matthias Kleinmann

quant-phSubmitted Mar 1, 2026• Announced Mar 3, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Comments
16 pages, 4 figures

Related papers

Classical Cost of Transmitting a Qubit

Martin J. Renner, Armin Tavakoli, Marco Túlio Quintino

We consider general prepare-and-measure scenarios in which Alice can transmit qubit states to Bob, who can perform general measurements in the form of positive operator-valued measures (POVMs). We show that the statistics obtained in any such quantum protocol can be simulated by the purely classical means of shared randomness and two bits of communication. Furthermore, we prove that two bits of communication is the minimal cost of a perfect classical simulation. In addition, we apply our methods to Bell scenarios, which extends the well-known Toner and Bacon protocol. In particular, two bits of communication are enough to simulate all quantum correlations associated to arbitrary local POVMs applied to any entangled two-qubit state.

arXiv:2207.02244•Physical Review Letters•Mar 22, 2023•16 citations

Quantum communication and Bell nonlocality require infinite classical communication to simulate

Carlos de Gois, Thyago S. R. Santos, Carlos Vieira

A quantum system of any fixed dimension can be prepared in a continuum of states, yet it cannot be used to transmit an unlimited amount of classical information. Similarly, the correlations observed between measurement outcomes on separate parts of a shared quantum system can be stronger than classical correlations, but they cannot transmit information. These fundamental limitations suggest that the statistics observed from quantum communication and quantum correlations may admit a simulation using a finite amount of classical communication. This expectation is confirmed in the smallest nontrivial quantum dimension, with two classical bits being necessary and sufficient to exactly simulate qubit communication and all correlations between qubits. Despite significant efforts during the previous decades, this remained the only solved case. Here we resolve both problems for every quantum dimension. The solution reveals an unexpected qualitative transition starting at dimension four: no finite amount of classical communication can exactly simulate ququart communication nor all quantum correlations of two entangled ququarts, even with unlimited shared randomness. One might have expected this transition, if it existed, to appear already for qutrits. Instead, we construct an explicit protocol that exactly simulates qutrit communication using $357$ classical bits, and consequently, all correlations of two entangled qutrits.

quant-pharXiv:2609.04182•Sep 4, 2026•0 citations

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

Near-optimal entanglement-communication tradeoffs for remote state preparation

Srijita Kundu, Olivier Lalonde

We study the following task: Alice is given a classical description of a rank-$k$ projector $P$ on $\mathbb{C}^d$, and Alice and Bob want to prepare the quantum state $P/k$ on Bob's side using shared entanglement and classical communication. The general form of this task is known as remote state preparation (RSP). We give nearly-matching lower and upper bounds for the entanglement cost and communication cost for RSP of the states $P/k$. Ours are the first nearly matching upper and lower bounds for RSP of mixed states, and in the special case of pure states, our lower bound outperforms the best previously known lower bound. Our results show that any pure entangled state that can be used to do RSP of these states with $o(d)$ bits of communication, can distill $\log d$ ebits of entanglement, and conversely, any state that can distill $\log d$ ebits of entanglement can be used to do RSP of these states efficiently. As applications of our results, we rederive a previously-known incompressibility result for states of the form $P/k$, and give a new entanglement-assisted communication protocol for the equality function that uses $\frac{1}{2}\log n + O(1)$ many ebits, and $O(1)$ communication.

quant-pharXiv:2602.09428•Feb 11, 2026•0 citations

Correlations in Entanglement-Assisted Prepare-and-Measure Scenarios

Armin Tavakoli, Jef Pauwels, Erik Woodhead +1 more

We investigate the correlations that can arise between Alice and Bob in prepare-and-measure communication scenarios where the source (Alice) and the measurement device (Bob) can share prior entanglement.The paradigmatic example of such a scenario is the quantum dense-coding protocol, where the communication capacity of a qudit can be doubled if a two-qudit entangled state is shared between Alice and Bob.We provide examples of correlations that actually require more general protocols based on higher-dimensional entangled states.This motivates us to investigate the set of correlations that can be obtained from communicating either a classical or a quantum d-dimensional system in the presence of an unlimited amount of entanglement.We show how such correlations can be characterized by a hierarchy of semidefinite programming relaxations by reducing the problem to a noncommutative polynomial optimization problem.We also introduce an alternative relaxation hierarchy based on the notion of informationally restricted quantum correlations, which, though it represents a strict (nonconverging) relaxation scheme, is less computationally demanding.As an application, we introduce device-independent tests of the dimension of classical and quantum systems that, in contrast to previous results, do not make the implicit assumption that Alice and Bob share no entanglement.We also establish several relations between communication with and without entanglement as resources for creating correlations.

arXiv:2103.10748•PRX Quantum•Dec 22, 2021•41 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
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.
We consider general prepare-and-measure scenarios in which Alice can transmit qubit states to Bob, who can perform general measurements in the form of positive operator-valued measures (POVMs). We show that the statistics obtained in any such quantum protocol can be simulated by the purely classical means of shared randomness and two bits of communication. Furthermore, we prove that two bits of communication is the minimal cost of a perfect classical simulation. In addition, we apply our methods to Bell scenarios, which extends the well-known Toner and Bacon protocol. In particular, two bits of communication are enough to simulate all quantum correlations associated to arbitrary local POVMs applied to any entangled two-qubit state.
A quantum system of any fixed dimension can be prepared in a continuum of states, yet it cannot be used to transmit an unlimited amount of classical information. Similarly, the correlations observed between measurement outcomes on separate parts of a shared quantum system can be stronger than classical correlations, but they cannot transmit information. These fundamental limitations suggest that the statistics observed from quantum communication and quantum correlations may admit a simulation using a finite amount of classical communication. This expectation is confirmed in the smallest nontrivial quantum dimension, with two classical bits being necessary and sufficient to exactly simulate qubit communication and all correlations between qubits. Despite significant efforts during the previous decades, this remained the only solved case. Here we resolve both problems for every quantum dimension. The solution reveals an unexpected qualitative transition starting at dimension four: no finite amount of classical communication can exactly simulate ququart communication nor all quantum correlations of two entangled ququarts, even with unlimited shared randomness. One might have expected this transition, if it existed, to appear already for qutrits. Instead, we construct an explicit protocol that exactly simulates qutrit communication using 357357357 classical bits, and consequently, all correlations of two entangled qutrits.
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 following task: Alice is given a classical description of a rank-kkk projector PPP on Cd\mathbb{C}^dCd, and Alice and Bob want to prepare the quantum state P/kP/kP/k on Bob's side using shared entanglement and classical communication. The general form of this task is known as remote state preparation (RSP). We give nearly-matching lower and upper bounds for the entanglement cost and communication cost for RSP of the states P/kP/kP/k. Ours are the first nearly matching upper and lower bounds for RSP of mixed states, and in the special case of pure states, our lower bound outperforms the best previously known lower bound. Our results show that any pure entangled state that can be used to do RSP of these states with o(d)o(d)o(d) bits of communication, can distill log⁡d\log dlogd ebits of entanglement, and conversely, any state that can distill log⁡d\log dlogd ebits of entanglement can be used to do RSP of these states efficiently. As applications of our results, we rederive a previously-known incompressibility result for states of the form P/kP/kP/k, and give a new entanglement-assisted communication protocol for the equality function that uses 12log⁡n+O(1)\frac{1}{2}\log n + O(1)21​logn+O(1) many ebits, and O(1)O(1)O(1) communication.
We investigate the correlations that can arise between Alice and Bob in prepare-and-measure communication scenarios where the source (Alice) and the measurement device (Bob) can share prior entanglement.The paradigmatic example of such a scenario is the quantum dense-coding protocol, where the communication capacity of a qudit can be doubled if a two-qudit entangled state is shared between Alice and Bob.We provide examples of correlations that actually require more general protocols based on higher-dimensional entangled states.This motivates us to investigate the set of correlations that can be obtained from communicating either a classical or a quantum d-dimensional system in the presence of an unlimited amount of entanglement.We show how such correlations can be characterized by a hierarchy of semidefinite programming relaxations by reducing the problem to a noncommutative polynomial optimization problem.We also introduce an alternative relaxation hierarchy based on the notion of informationally restricted quantum correlations, which, though it represents a strict (nonconverging) relaxation scheme, is less computationally demanding.As an application, we introduce device-independent tests of the dimension of classical and quantum systems that, in contrast to previous results, do not make the implicit assumption that Alice and Bob share no entanglement.We also establish several relations between communication with and without entanglement as resources for creating correlations.
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.