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• 7 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•25 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•5 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•1 citation

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•16 citations

A Quantum Measurement Scenario which Requires Exponential Classical Communication for Simulation

Allison Coates

In this paper we consider the following question: how many bits of classical communication and shared random bits are necessary to simulate a quantum protocol involving Alice and Bob where they share k entangled quantum bits and do not communicate at all. We prove that 2^k classical bits are necessary, even if the classical protocol is allowed an εchance of failure.

arXiv:quant-ph/0203112•Mar 21, 2002•7 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•3 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.
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.
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.