Exponential entanglement cost with simultaneous classical communication
- Fields
- Topics
Problem
Does there exist a family of bipartite unitaries requiring exponentially many shared Bell pairs for fixed-error implementation when classical communication is limited to one simultaneous exchange? For every integer \(n\geq1\), let \(U_n\) act on \(\mathcal H_{A_n}\otimes\mathcal H_{B_n}=(\mathbb C^2)^{\otimes n}\otimes(\mathbb C^2)^{\otimes n}\), with \(n\) qubits held by each party. The allowed protocols \(\Lambda\in\mathrm{LOBC}\) use arbitrary local quantum operations and one simultaneous exchange of classical messages: each outgoing message is fixed before the incoming message is read. No quantum communication or shared entanglement beyond the supplied Bell pairs is allowed.
Define the Bell-pair state and target channel by Eq. (1), where \(\rho\) is an arbitrary input density operator:
For \(0\leq\varepsilon<1/10\), the minimum Bell-pair cost is Eq. (2):
Here \(\|\cdot\|_{\diamond}\) is the diamond norm, including arbitrary reference systems, and the minimum is \(+\infty\) if the feasible set is empty. Each \(\Lambda\) is a deterministic channel returning the two prescribed \(n\)-qubit outputs after discarding auxiliary systems. The question asks whether there exist such a family and constants \(c>0\) and \(\varepsilon_0\in(0,1/10)\) satisfying Eq. (3):
Source
This is the fixed-error formulation of the exponential LOBC entanglement-cost question discussed by Gonzales and Chitambar in Section II, p. 3 of the arXiv version [GC20]. The Bell-pair cost, half-diamond-norm convention, and worst-case family quantifiers make the supplied formulation precise. The simultaneous-classical-message restriction is essential; the broader quantum-message problem discussed by May is distinct [May26].
Progress
With unrestricted interactive LOCC, teleporting one input to the other party and teleporting its output back gives
\begin{equation} E_{\mathrm{LOCC}}^{0}(U_n)\leq2n, \tag{4} \end{equation}In Eq. (4), \(E_{\mathrm{LOCC}}^{0}(U_n)\) denotes the minimum Bell-pair cost of exact implementation with unrestricted classical interaction; the two successive teleportations generally violate the simultaneous-message restriction. [BK11]
Port-based teleportation gives a universal sufficient resource bound: Theorem III.1(ii) of [BK11], converted to the half-diamond-norm convention above and rounded to an integer number of ports, yields
\begin{equation} E_{\parallel}^{\varepsilon}(U_n) \leq n\left(1+3\left\lceil\frac{2^{8n+2}}{\varepsilon^2}\right\rceil\right) =O\left(\frac{n\,2^{8n}}{\varepsilon^2}\right), \qquad 0<\varepsilon<1/10. \tag{5} \end{equation}Equation (5) is an achievable upper bound, not a claim that this particular exponent or error dependence is optimal. [BK11]
Theorem 3 of Gonzales and Chitambar (arXiv p. 6) gives a rigorous unbounded separation between interactive and simultaneous classical communication for exact controlled gates: writing \(A_n=A_1A_{\mathrm{rest}}\) for Alice’s first qubit and remaining qubits, define
\begin{equation} D_n:=\sum_{k=0}^{2^n-1}e^{i\theta_k}|k\rangle\langle k|_{B_n}, \qquad \theta_k\in[0,2\pi),\quad\theta_k\neq\theta_l\text{ for }k\neq l, \tag{6} \end{equation}\begin{equation} V_n:=|0\rangle\langle0|_{A_1}\otimes I_{A_{\mathrm{rest}}}\otimes I_{B_n} +|1\rangle\langle1|_{A_1}\otimes I_{A_{\mathrm{rest}}}\otimes D_n, \tag{7} \end{equation}In Eqs. (6) and (7), \(k\) labels Bob’s computational basis and the \(I\) operators are identities on the indicated systems, for which
\begin{equation} E_{\parallel}^{0}(V_n)\geq n, \qquad E_{\mathrm{LOCC}}^{0}(V_n)\leq2. \tag{8} \end{equation}The lower bound in Eq. (8) is linear in the number of qubits and assumes zero error. [GC20]
The July 19, 2026 revision of May’s treatment (version 2, Chapter 13) explicitly leaves exponential entanglement lower bounds open in the more permissive model with a simultaneous exchange of quantum messages; denoting its minimum Bell-pair cost at the same error tolerance by \(E_{\parallel,\mathrm q}^{\varepsilon}(U_n)\), protocol inclusion gives
\begin{equation} E_{\parallel,\mathrm q}^{\varepsilon}(U_n) \leq E_{\parallel}^{\varepsilon}(U_n). \tag{9} \end{equation}By Eq. (9), an exponential lower bound in that model would imply one here, but its unresolved status alone does not establish the status of the classical-message subcase, which is formulated separately in [GC20]. [GC20], [May26]
Comment
No resolution of the stated classical-message, fixed-error exponential lower bound was found in the literature checked through September 9, 2026. An exponential achievable cost does not prove necessity, and an exact-implementation lower bound need not survive a fixed nonzero error tolerance. The question concerns a worst-case family rather than every unitary, and permits protocols tailored to a complete classical description of each \(U_n\), not only black-box protocols. The status audit used public primary sources and later-work searches through 9 September 2026; it was not an exhaustive citation-index audit. The related catalog entry op_96cf7aa1c1be9be2 asks a polynomial support-rank lower bound for an explicit Boolean routing family with arbitrary shared states and unrestricted simultaneous message type. This entry instead asks an exponential Bell-pair lower bound for general bipartite unitary families with classical messages only.