arXiv:2610.19060
The cost of classically simulating quantum communication is as high as it could be
Riccardo Castellano, Pavel Sekatski, Nicolas Brunner
Abstract
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.
AI Summary
The paper asks how much one-way classical communication, assisted by unlimited shared randomness, is needed to reproduce exactly prepare-and-measure correlations for arbitrary qudit states and POVMs. It distinguishes worst-case alphabet size, expected alphabet size, and expected bit cost $\mathbb E[\log_2 D_\lambda]$, where the shared randomness determines the message alphabet. For $d\geq4$, every measurable exact simulation must have $\mathbb E[D_\lambda]=\infty$, strengthening the previously known impossibility of a bounded alphabet. Nevertheless, every finite-dimensional quantum system admits an exact simulation using $O(d\log d)$ expected bits, with communication tail $\Pr(\log_2D_\lambda\geq k)\leq C_d2^{-k/(2d-2)}$. The construction also yields one-way simulations of arbitrary bipartite finite-dimensional entangled-state correlations. The upper bound follows from a general theorem: polynomial covering growth under a measurement-dependent “mass deficit,” measuring probability mass not common to all inputs in a cell, suffices for finite expected communication. A geometrically distributed shared resolution selects a nested partition; recursive lower-envelope decoders recover the target distribution exactly. The lower bound extends an existing fixed-fidelity zero-slope argument using dominated convergence. Applications include deterministic approximate qudit simulation with $D(q\|p)\leq K_dN^{-1/(d-1)}$ for alphabet size $N$, and exact simulation of energy-bounded multimode Gaussian states under general-dyne and homodyne measurements, using $O(n^2\log E+n^2\log n)$ expected bits at large energy. Optimal expected-cost scaling and tail exponents remain open, as do multipartite one-way extensions and whether the Gaussian setting permits finite expected alphabet size.
ChatGPT Sol 5.6 and ChatGPT Astra 6.0 have contributed via extensive dialogues with the authors. This helped prove the statements, as well as identifying and correcting errors.
Error found: The discussion after the main simulation theorem claims O(d) expected bits for arbitrary bipartite Bell correlations, but the supplied protocol and conditional-state reduction establish only O(d log d).
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 11 pages of main, 11 of appendix. 1 figure