Foundations of quantum mechanics · Theory (AI-assisted)

The classical complexity of quantum state transmission

Elna Svegborn, Alexander Bernal, Armin Tavakoli

arXiv:2611.26126v1 ↗PDF ↗Submitted 19 November 2026

Question
A sender can transmit a quantum state through a quantum channel, but how much classical communication would it take to let the receiver prepare the same state without any quantum resource, given shared randomness? Earlier work counted classical bits needed to reproduce the statistics of particular measurements. That cost depends on the experiment: in prepare-and-measure tests all qubit correlations can be reproduced with two bits. The paper asks for the cost of reproducing the states themselves, whether that cost is visible in some black-box experiment, and how large it is for noisy states.
Result
A set of states \(\{\rho_x\}\) has an \(r\)-complex classical model if \(\rho_x=\int d\lambda\,q(\lambda)\sum_{c=1}^rp(c|x,\lambda)\sigma_{c,\lambda}\); the least such \(r\) is its classical complexity. Membership is an exact semidefinite program for finite sets. A set lacks an \(r\)-complex model exactly when it produces correlations in a prepare-and-broadcast experiment that no \(r\)-valued classical message can reproduce, so the state-level cost is also a correlation-level cost. For all pure \(d\)-dimensional states mixed with white noise at visibility \(v\), the complexity grows as \(\bigl(A_d/(1-v)\bigr)^{d-1}\) with \(1\le A_d\le C_d\), where \(C_d=\tfrac{d}{d-1}\Gamma(1+\tfrac1{d-1})\); at \(d=16\) and \(v=0.9\) at least \(10^{15}\) symbols are needed. Analytical witnesses for mutually unbiased bases and equiangular frames, and linear programs that bracket the critical visibility for up to 10,000 qubit states, make the quantity testable.

The paper in detail

Alice and Bob agree on a list of states \(\rho_1,\dots,\rho_n\) of dimension \(d\). Alice picks \(x\) and may send one of \(r\) classical symbols, using shared randomness; Bob must end up holding exactly \(\rho_x\). The smallest \(r\) that works is the classical complexity \(r^*\). Some properties are immediate. Distinct pure states cannot be mixed from anything else, so \(r^*=n\) and the complexity of all pure states is infinite. Adding convex combinations of listed states never increases \(r^*\). Without shared randomness, \(r^*\) is the least number of states whose convex hull contains the set. Decomposing Alice's response into deterministic functions turns membership into a semidefinite feasibility problem over \(r^n\) strategies, exact but quickly too large.

Is this cost visible in an experiment that treats every device as a black box? In a prepare-and-measure test, any \(r\)-complex set gives correlations that an \(r\)-valued message reproduces, but not conversely: a fixed measurement on \(d\)-dimensional states can always be simulated with \(d\) symbols, however large the states' complexity. The paper proves that the converse does hold in the prepare-and-broadcast scenario, where the state passes through an arbitrary channel to two separated parties who measure. Replacing Bob's choice of input by trusted quantum inputs and a Bell-basis measurement shows that a classical model of the correlations is a classical model of the states. Self-testing then removes the trust by certifying that a second party prepares those inputs remotely through a maximally entangled pair.

For the whole noisy state space, \(\rho_\psi=v\ket\psi\bra\psi+(1-v)I/d\), the question reduces to one integral: the largest average overlap \(\mathcal I_{d,r}\) between a Haar-random state and the nearest of \(r\) fixed states. An \(r\)-complex model exists exactly when \(v\le(d\mathcal I_{d,r}-1)/(d-1)\). For \(r\le d\) the optimum uses orthogonal states and gives the exact threshold \((H_r-1)/(d-1)\), where \(H_r\) is the harmonic number. For larger \(r\) the bounds \(1-\prod_{c=2}^r\frac{c}{c+1/(d-1)}\le v^*\le1-r^{-1/(d-1)}\) both scale as \(r^{-1/(d-1)}\). Hence the complexity grows exponentially in \(d\) at fixed noise and as a power \(d-1\) of \(1/(1-v)\) at fixed \(d\). The average number of bits lies between \((d-1)\log\frac1{1-v}\) and one bit more.

For devices that prepare a finite target set, simple witnesses certify a lower bound on the complexity. If states aimed at \(m\) mutually unbiased bases admit an \(r\)-complex model, the summed success probability of measuring each in its own basis is at most \(m+\sqrt{m(d-1)(r-1)}\), so noisy MUB states with visibility above \(\sqrt{(r-1)/(m(d-1))}\) are certified to need more than \(r\) symbols; a similar bound holds for equiangular tight frames and SIC sets. For qubits, an active-set linear program gives inner bounds and a Lagrangian or merge certificate gives outer bounds. These bracket the critical visibility of 10,000 near-uniform Bloch vectors with \(r=8\) to \([0.862,0.882]\), and push it above 0.99 once \(r\) reaches about three quarters of the number of states. Turning the huge fundamental costs into robust experiments is left open.

Transferable methods

  1. Reducing the noisy state space to an overlap integral

    Simulating every noisy pure state at once looks like an infinite-dimensional problem. Symmetry makes it one number. A linear witness, the average fidelity of each simulated state with its target, is bounded for any \(r\)-symbol model by the best average overlap with \(r\) fixed states. A randomly rotated copy of the best constellation attains that bound and produces exactly the isotropic noisy states, so the bound is also achievable.

    For the target family the witness is \(W=\int d\psi\,\langle\psi|\rho_\psi|\psi\rangle=v+(1-v)/d\). In an \(r\)-complex model, linearity lets one take Alice's encoding deterministic for each \(\lambda\), so Bob's state is one of \(r\) states \(\sigma_c\), and the witness is at most \[\mathcal I_{d,r}=\max_{\phi_1,\dots,\phi_r}\int d\psi\,\max_c|\langle\psi|\phi_c\rangle|^2.\] Conversely, with shared randomness a Haar unitary \(U\), Alice names the \(c\) maximising \(|\langle\psi|U\phi_c\rangle|^2\) and Bob prepares \(U\ket{\phi_c}\). Averaging over \(U\) commutes with the unitaries fixing \(\psi\), so the output is isotropic around \(\psi\) (editorial step), with fidelity \(\mathcal I_{d,r}\). This gives the threshold \(v^*=(d\mathcal I_{d,r}-1)/(d-1)\).

    Editorial derivation of both bounds. For Haar \(\psi\), the overlap \(X=|\langle\psi|\phi\rangle|^2\) has \(P(X>x)=(1-x)^{d-1}\). A union bound over the \(r\) states gives \(P(\max_cX_c>x)\le\min\{1,r(1-x)^{d-1}\}\), and integrating yields \(\mathcal I_{d,r}\le1-r^{-1/(d-1)}(1-\tfrac1d)\), which is exactly \(v^*\le1-r^{-1/(d-1)}\). Taking the \(r\) states independent and Haar random instead gives \[\mathbb E\max_cX_c=\int_0^1\bigl[1-(1-(1-x)^{d-1})^r\bigr]dx,\] whose visibility equals the paper's lower bound \(1-\prod_{c=2}^r\frac{c}{c+1/(d-1)}\); numerically the two agree to six digits for \(d=2,3,4,8\) and \(r=2,5,20\). So the lower bound is what a random constellation achieves, and the upper bound is what perfectly non-overlapping caps would achieve.

    Editorial check: for qubits \(v^*\) is the mean of \(\max_c\cos\theta_c\) for a uniformly random direction, where \(\theta_c\) is its angle to the \(c\)-th point of the constellation. Monte Carlo gives 0.500 for two antipodal points (the exact value \(H_2-1=\tfrac12\)), 0.745 for the tetrahedron, 0.831 for the octahedron and 0.916 for the icosahedron. These are within 0.5% of the upper bounds 0.75, 0.833 and 0.917, so for qubits the upper bound is nearly attained.

    How to reuse it

    Whenever a resource must simulate a whole unitarily invariant family, the twirl over the symmetry group turns the problem into a single optimisation over a few states. Union bounds over spherical caps and random constellations then give matching scaling laws. The same pair of arguments bounds quantisation of quantum states, random access codes and covering problems in state space.

  2. From a Bell-basis measurement to a state-level witness

    To make the state-level cost visible, the receiver must be able to learn everything about the state, not only the statistics of a chosen measurement. Measuring the incoming state jointly with trusted probe states in a basis of maximally entangled states does this: the effective measurements are transposed, rotated copies of the state itself. Any classical model of these statistics can then be undone into a classical model of the states. Self-testing replaces the trusted probes by states that a second party prepares remotely.

    Let Bob measure his half of the message and a probe in the basis \(\ket{\phi_b}=(I\otimes U_b)\ket{\phi^+}\), where \(\{U_b\}_{b=1}^{d^2}\) is an orthogonal unitary basis. The effective measurement on the probe is \(M_{b|x}=\tfrac1dU_b\rho_x^TU_b^\dagger\). Editorial step: since \((U_b\rho^TU_b^\dagger)^T=U_b^*\rho U_b^T\), conjugating back gives \(U_b^TM_{b|x}^TU_b^*=\rho_x/d\) for every \(b\), and summing over the \(d^2\) outcomes recovers \[\rho_x=\frac1d\sum_bU_b^TM_{b|x}^TU_b^*.\]

    Suppose the statistics have a classical model, \(M_{b|x}=\int d\lambda\,q(\lambda)\sum_cp(c|x,\lambda)G_{b|c,\lambda}\), with Bob's measurement \(G_{\cdot|c,\lambda}\) chosen from the symbol and the randomness. Applying the same linear map gives \(\rho_x=\int d\lambda\,q(\lambda)\sum_cp(c|x,\lambda)\tau_{c,\lambda}\) with \(\tau_{c,\lambda}=\tfrac1d\sum_bU_b^TG_{b|c,\lambda}^TU_b^*\). That operator is positive and has trace \(\tfrac1d\sum_b\operatorname{tr}G_{b|c,\lambda}=1\), so it is a state and the set is \(r\)-complex. Hence a set that is not \(r\)-complex violates some linear witness on these statistics, found by a separating hyperplane and expanded over the probe states.

    In the device-independent version a third party \(C\) shares a Bell pair with Bob. Maximal CHSH violation self-tests the pair and \(C\)'s Pauli measurements, so \(C\)'s outcomes prepare Pauli eigenstates on Bob's side, which serve as the probes. In the prepare-and-broadcast scenario the extra source is folded into the broadcasting channel. The conclusion is that the set's classical complexity equals the message size needed to reproduce all its broadcast correlations; the self-test assumes the ideal, maximal violation.

    How to reuse it

    A joint measurement with a maximally entangled basis turns any state into a set of effective measurements from which it can be reconstructed. This is the standard step behind measurement-device-independent witnesses (entanglement, steering, incompatibility), and it applies to any resource defined at the level of states once one needs an experiment that sees all of it.

Source: Section II (classical communication models, Observation 1), Section III (operational equivalence, Eqs. (5)–(11)), Section IV (Result 2 and Corollary 1, Eqs. (12)–(18)), Section V (Observation 3). Based on the linked paper version. Derivations marked as editorial, and suggested uses in other problems, are editorial guidance rather than results of the paper.

Context & limitations

Why it matters. The classical complexity is to quantum communication what entanglement is to Bell nonlocality: a property of the states, with the prepare-and-broadcast scenario as the experiment that reveals all of it. It shows that the gap between finite and infinite classical cost found in prepare-and-measure experiments (infinite only for \(d\ge4\)) comes from the restricted experiment: once the receiver may broadcast the state to two parties, the cost is infinite already for qubits, and so is the average number of bits. The scaling result puts a concrete price on simulating near-pure, high-dimensional communication classically.

Limitations. The equivalence with prepare-and-broadcast correlations relies on self-testing a maximally entangled auxiliary state from a maximal CHSH violation. That is an idealised, noise-free route, and the authors say that observing large classical complexity in real correlations needs more practical protocols. For the noisy state space the critical visibility is exact only for \(r\le d\); for \(r>d\) only upper and lower bounds are proved, and the constant \(A_d\) is not determined. The qubit inner approximations are heuristic searches; only the outer bounds are certified. The authors state that ChatGPT 5.6 Sol produced the upper and lower bounds on the integral behind the noisy-state result, which they verified, that Claude Opus 4.5 advised on the design of the qubit algorithms, and that ChatGPT polished parts of the text.

Description based on the full arXiv HTML of v1, read 2026-11-21: Sections I–VII (definitions, semidefinite characterisation, operational equivalence, noisy state space, witnesses, algorithms, case studies) and the AI statement. Appendix C (device-independent proof) and Appendix D (integral bounds) were not checked line by line. Editorial checks: Table 1 was recomputed from Eqs. (13)–(14); the lower ends agree, and the upper ends agree with the looser estimate \(r<2(1-v)^{-(d-1)}\) used in the proof of Corollary 1 (Eq. (13) alone gives, for example, 19 rather than 20 at \(d=2\), \(v=0.9\)). The two bounds were rederived as an independent-random-constellation value and a union bound (agreement to six digits for \(d=2,3,4,8\)). For qubits, Monte Carlo over 400,000 directions gives critical visibilities 0.745, 0.831 and 0.916 for tetrahedral, octahedral and icosahedral constellations, against the upper bounds 0.75, 0.833 and 0.917.