Quantum information · Theory (AI-assisted)

Scrambling leads to entanglement cost in NLQC

Atsuya Hasegawa, Alex May

arXiv:2611.23378v1 ↗PDF ↗Submitted 17 November 2026

Question
In a non-local quantum computation, two parties holding the inputs of a bipartite unitary share entanglement, act locally, exchange one simultaneous round of quantum messages and act locally again, so that the outputs come out right. Lower bounds on the entanglement needed control the security of quantum position verification and appear in holography, yet most known bounds apply only to specially built channels. Which property of a unitary forces an entanglement cost, and how large is that cost at least?
Result
Scrambling. For any channel, the entanglement of formation of a resource state that implements it exactly is at least half the scrambling quantity \(J\), a combination of entropies of the channel's Choi state. For a unitary, \(J\) equals the negated tripartite mutual information \(-I_3(A:C:D)\), and \(J(U)=0\) exactly when \(U\) is a subsystem SWAP, which costs no entanglement; the bound is therefore faithful. The earlier controllable-correlation bound is faithful too, settling a conjecture of Cleve and May, and the two bounds are incomparable.

The paper in detail

Non-local quantum computation captures what two separated parties can do with shared entanglement and a single round of simultaneous communication. Each party receives one input, applies a local operation to it and its half of the resource, sends part of the result to the other, and applies a second local operation; the combined outputs must equal those of a fixed channel applied to both inputs. In position verification, an attacker who could do this cheaply could impersonate an honest prover, and in holography the entanglement needed relates to the size of a spacetime region. General lower bounds have been scarce. The controllable-correlation bound of Cleve and May was the main general tool, and whether it vanishes only for unitaries that genuinely need no entanglement was open.

The new bound comes from a single entropy calculation on the Choi state \(\ket{\chi^U}_{ABCD}\), where references \(A\) and \(B\) are maximally entangled with the inputs and \(C\) and \(D\) are the outputs. The scrambling quantity \(J=S(BC)+S(BD)-S(ABC)-S(ABD)\) equals \(I(A:B|C)\) for a unitary, and also \(-I_3(A:C:D)\), which is positive when the correlation with input \(A\) sits jointly in \(CD\) but not in \(C\) or \(D\) separately. Following a pure resource through the protocol, data processing and the chain rule give \(2S(L)\ge J\); convexity of \(J\) extends this to mixed resources with entanglement of formation in place of entropy.

The bound is faithful for unitaries because the scrambling literature already characterises \(J(U)=0\): it holds exactly when \(U=(S\otimes T)(M\otimes N)\), with each party first splitting its input into two pieces and the two final unitaries acting on swapped pieces, which is an NLQC protocol with no entanglement. The maximal value \(2\log d\) is reached by perfect tensors, such as \(\ket{i,j}\mapsto\ket{i+j,i-j}\) for odd \(d\). For the controllable correlation, an averaged version over an ensemble whose mixture is maximally mixed equals a conditional mutual information; when it vanishes, a recovery map exists, the Choi state forms a Markov chain and \(J=0\). Measuring \(B\) shows that \(J\) is at least the averaged controllable correlation, yet the optimised version can exceed \(J\): a controlled SWAP reaches \(CC^{\mathrm{opt}}=2n_A\), the largest possible value.

Small \(J\) does not imply closeness to a subsystem SWAP, so neither bound gives a robust characterisation of nearly free unitaries, and faithful bounds for general channels are open. The authors see the two bounds as capturing different mechanisms, the delocalisation of information and the ability of one party's input to steer correlations at the other's output, and ask how they combine into a fuller account of entanglement cost.

Transferable methods

  1. Tracing the resource through the protocol to a conditional mutual information

    The entanglement of a pure resource bounds the correlation between the two parties' laboratories at every later stage. After the first local operations and the exchange, one output lab holds \(C\) and some leftover \(X\). Data processing turns the resource's entropy into a conditional mutual information of the references given that lab's systems, and purity removes the leftover, leaving a quantity of the channel alone.

    With isometries \(V_{A'L\to A_0A_1}\) and \(W_{B'R\to B_0B_1}\) followed by \(S_{A_0B_0\to CX}\) and \(T_{A_1B_1\to DY}\), purity and invariance under local isometries give \[2S(L)_\Psi=I(L:R)_\Psi=I(AA_0A_1:BB_0B_1)_\chi\ge I(AA_0:BB_0)_\chi\ge I(A:B|A_0B_0)_\chi=I(A:B|CX)_{\chi'}.\] The middle step uses \(I(A:BC|D)\ge I(A:B|CD)\) twice.

    The leftover \(X\) is removed by the chain rule and data processing, \[I(A:B|CX)\ge I(A:BC)-I(A:CXY),\] and purity with \(A\) maximally mixed gives \[I(A:CXY)=2n_A-I(A:BD).\] Hence \(2S(L)\ge I(A:BC)+I(A:BD)-2n_A\), and expanding the mutual informations with \(S(A)=n_A\) turns the right-hand side into \[S(BC)+S(BD)-S(ABC)-S(ABD)=J(\mathcal N).\] For a unitary, purity of the Choi state turns this into \[I(A:B|C)=2n_A-I(A:C)-I(A:D)=-I_3(A:C:D).\]

    For a mixed resource, take the ensemble that attains the entanglement of formation; component \(i\) implements a channel \(\mathcal N^i\) with \(\sum_ip_i\mathcal N^i=\mathcal N\). Writing \(J=-S(A|BC)-S(A|BD)\), concavity of conditional entropy makes \(J\) convex, so \(E_f\ge\sum_ip_iJ(\mathcal N^i)/2\ge J(\mathcal N)/2\). Editorial check: the identities, CNOT's value \(J=1\) (so at least half an ebit), the perfect-tensor maximum and convexity were confirmed numerically.

    How to reuse it

    For lower bounds on resources consumed by one-round protocols, follow the resource's mutual information through each stage and stop at the first point where it becomes a conditional mutual information of reference systems. The same route gives bounds in position verification and other two-party tasks with simultaneous messages.

  2. Markov chains, recovery maps and faithfulness

    A lower bound is faithful when it vanishes only for operations that are free. Here that follows from a structure theorem: zero conditional mutual information means the state is a quantum Markov chain, and for a unitary's Choi state that chain structure forces the subsystem-SWAP form. The same theorem shows that the controllable correlation vanishes only when \(J\) does.

    A state with \(I(A:C|B)_\omega=0\) splits as \[\omega_{ABC}=\bigoplus_ip_i\,\omega^i_{AL_i}\otimes\omega^i_{R_iC}\] for a decomposition \(\mathcal H_B\simeq\bigoplus_i\mathcal H_{L_i}\otimes\mathcal H_{R_i}\), and equivalently there is a recovery channel \(\mathcal R_{B\to AB}\) with \(\omega_{ABC}=\mathcal R(\omega_{BC})\). For the Choi state of a unitary, \(I(A:B|C)=0\) holds exactly when \(U=(S_{ab\to C}\otimes T_{a'b'\to D})(M_{A'\to aa'}\otimes N_{B'\to bb'})\) (Theorem 7).

    For an ensemble \(\{p_i,\phi^i\}\) on \(B'\) averaging to the maximally mixed state, Lemma 17 gives \[\overline{CC}(U,E)=\sum_ip_iI(A:C)_{\rho^i}-I(A:C)_{\rho^0}=I(A:X|C)_\omega,\] where \(X\) records \(i\). If this vanishes, a recovery map \(\mathcal T_{C\to AC}\) reproduces each \(\rho^i_{AC}\) from \(\rho^i_C\); when the \(\phi^i\) span all operators, linearity gives \(\mathcal F_{B'\to AC}=\mathcal T\circ\mathcal G_{B'\to C}\), and applying both sides to \(\Psi^+_{B'B}\) shows that \(\chi^U_{ACB}=\mathcal T(\chi^U_{CB})\) is Markov, so \(J=0\).

    In the other direction, measuring \(B\) in the Choi state with the POVM \(\Lambda^i=p_i\,d_B\,(\phi^i)^{\mathsf T}\) prepares exactly the classical–quantum input of the averaged quantity, so data processing gives \[J(U)=I(A:B|C)_{\chi^U}\ge I(A:X|C)_\omega=\overline{CC}(U,E).\] The optimised \(CC^{\mathrm{opt}}\) can still exceed \(J\): for a controlled SWAP with one control and one target qubit, choosing the control as \(\ket0\) or \(\ket1\) moves the correlation with \(A\) fully into or out of \(C\), giving \(CC^{\mathrm{opt}}=2\), while editorial computation gives \(J\approx0.549\).

    How to reuse it

    To prove that an entropic lower bound vanishes only on free operations, apply it to the Choi state and look for a Markov-chain structure theorem. Recoverability results then translate “zero bound” into an explicit decomposition, often the very protocol that makes the operation free.

Source: Section 3.1 (Theorem 7), Section 3.2 (Definition 8, Lemma 9, Theorem 11), Section 3.3, Section 4 (Lemma 17, Theorems 19–20), Section 5 (Remark 21). 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. This gives the first faithful general lower bound on the entanglement cost of unitaries in NLQC, and it is easy to compute: no optimisation, just entropies of the Choi state. It links entanglement cost to a standard diagnostic of quantum chaos, since small out-of-time-order correlators force negative tripartite information, and it extends to channels near a unitary without separate robustness arguments.

Limitations. The bound is at most \(2n_A\), so it certifies at most \(n_A\) ebits, the size of one input. It is not robust in the strong sense: unitaries can have \(J\) tending to zero while staying far in diamond norm from every subsystem SWAP. For general channels it is not faithful. Exact implementations are assumed, with continuity of entropy invoked for approximate ones, and the paper does not compare the bound with the entanglement used by known protocols. The authors state that OpenAI Astra and Claude Opus were used extensively to suggest and simplify proofs, and that the scrambling bound and its extension to channels were refined with Claude Opus.

Description based on the full arXiv HTML of v1, read 2026-11-19: Sections 1–5 (background, Theorems 7, 11, 12 and 19–20, the maximal-value constructions, Remark 21 and the incomparability discussion) and the acknowledgements. Editorial checks: for two-qubit gates, numerical Choi states confirm the identities (34) and (57) expressing \(J\) as \(-I_3\) and as a conditional mutual information, to \(10^{-12}\); \(J\) vanishes for the identity, SWAP and random local unitaries, equals 1 for CNOT and lies near 1.1 for Haar-random gates; the qutrit unitary \(\ket{i,j}\mapsto\ket{i+j,i-j}\) gives \(J=2\log_23\); \(J\) of 200 random mixtures of three unitary channels never exceeds the mixture of their \(J\) values; and for the controlled SWAP with \(CC^{\mathrm{opt}}=2\), \(J\approx0.549\).