betaFeedback

WorksPhysics and Astronomy

Scrambling leads to entanglement cost in NLQC

Abstract

In a non-local quantum computation (NLQC), shared entanglement along with a single simultaneous round of quantum communication is used to implement a joint channel. NLQC has many applications, most of which benefit from an understanding of lower bounds on the entanglement needed to implement a given channel as an NLQC. However, the properties of a channel that lead to it having an entanglement cost in NLQC have remained unclear, with most lower bounds only applying to specially constructed examples. Here, we give a new lower bound technique for unitaries based on scrambling: we find that a unitary has zero entanglement cost if and only if it does not scramble. Further, we find that the tripartite mutual information, an entropic object that quantifies the degree of scrambling, provides a quantitative lower bound on entanglement cost in NLQC. This is the first known lower bound on entanglement cost for unitaries in NLQC which is faithful. Our results also relate scrambling and NLQC for the first time. Leveraging the faithful scrambling based bound, we then show that the controllable correlation, an earlier studied quantity, is also a faithful lower bound, resolving an earlier conjecture of Cleve and May.

Introduction

In a non-local quantum computation (NLQC), shared entanglement along with a single simultaneous round of quantum communication is used to implement a joint channel. See Figure 1. NLQC has many applications and connections to other subjects, including in quantum position verification [1, 2], classical information theoretic cryptography [3, 4, 5], communication complexity [6], quantum complexity [7, 8], classical complexity [9, 10], quantum gravity [8, 11, 12, 13, 14], uncloneable cryptography [15], Hamiltonian complexity [16], and other topics; see [17] for a review. We are especially interested in lower bounding the entanglement needed to implement channels in the form of an NLQC. In the context of quantum position-verification, entanglement lower bounds on NLQC give guarantee’s on how difficult it is to attack a position-verification scheme. In the context of quantum gravity, entanglement lower bounds relate to how large of a spacetime region is needed to implement the given quantum channel. In fact, in all of the applications of NLQC, understanding the amount of entanglement needed is a key question.

Figure 1. Local and non-local computations. a) A channel TA′B′→CD\mathcal{T}_{A'B'\to CD} is implemented by directly interacting the input systems. b) A non-local quantum computation. The goal is for the action of this circuit on the ABAB systems to approximate the channel TA′B′→CD\mathcal{T}_{A'B'\to CD}.

In this article, we are interested in lower bounds on entanglement in NLQC. In previous work, most lower bounds have been constructed for specific channels or families of channels [2, 4, 18, 19, 20, 21, 22]. Here, we are interested in general purpose lower bound techniques. Given a channel, we would like to be able to perform a straightforward calculation that lower bounds its entanglement cost. Ideally, the lower bound computed would have a simple meaning, and consequently reveal a property of the channel related to entanglement cost.

We provide a new lower bound technique that relates the entanglement cost of unitaries to the physics of scrambling. A quantum channel is said to scramble quantum information if information which is initially localized in the inputs becomes delocalized in the outputs. Scrambling is closely related to chaos, and has been well-studied in the context of gravity and quantum many-body systems [23]. We find that those unitaries with zero entanglement cost are exactly those which do not scramble information. Specifically, the tripartite mutual information was proposed as a measure of scrambling [24]; we find the tripartite mutual information is zero if and only if the unitary has zero entanglement cost, and further provides a quantitative lower bound on the entanglement cost of a unitary.1

The tripartite mutual information scrambling quantity [24] is defined as follows. Consider a bipartite unitary UA′B′→CDU_{A'B'\to CD}. Define the Choi state of this unitary (see Figure 2),

Figure 2. Choi state of the bipartite unitary UA′B′→CDU_{A'B'\to CD}. The lower cups represent maximally entangled states on AA′AA' and BB′BB', and AA, BB are reference systems.

∣χU⟩ABCD=UA′B′→CD∣Ψ+⟩AA′∣Ψ+⟩BB′(1)\left|\chi^U\right\rangle_{ABCD}=U_{A'B'\to CD}\left|\Psi^+\right\rangle_{AA'}\left|\Psi^+\right\rangle_{BB'} \tag*{(1)}

and consider the entropic quantity,

J(U)=−I3(A:C:D)χ(2)J(U)=-I_3(A:C:D)_{\chi} \tag*{(2)}

where

I3(A:C:D)χ≔I(A:C)χ+I(A:D)χ−I(A:CD)χ(3)I_3(A:C:D)_{\chi}\coloneqq I(A:C)_{\chi}+I(A:D)_{\chi}-I(A:CD)_{\chi} \tag*{(3)}

and I(X:Y)I(X:Y) is the quantum mutual information. The quantity I3I_3 is known as the tripartite mutual information. We call J(U)J(U) the scrambling quantity. Intuitively, I3I_3 becomes negative, and hence J(U)J(U) becomes positive, when the correlation with AA is held jointly in CDCD, but not in CC or DD alone — in other words, J(U)J(U) is positive when the correlation with AA has scrambled into CC and DD. Define E(U)E(U) as the minimal entanglement needed to implement UU as an NLQC, as quantified by the entanglement of formation in the resource state. We show that

E(U)≥J(U)2.(4)E(U)\ge\frac{J(U)}{2}. \tag*{(4)}

This relates entanglement cost in NLQC and scrambling: Unitaries that are highly scrambling have large entanglement cost in NLQC. As desired, this bound is straightforward to compute and relates to a simple and physically meaningful property of the unitary.

Leveraging insights from the study of scrambling, we gain an understanding of when this lower bound returns zero, J(U)=0J(U)=0. As shown in [25], this occurs exactly when

UA′B′→CD=(Sab→C⊗Ta′b′→D)(MA′→aa′⊗NB′→bb′)(5)U_{A'B'\to CD}=(S_{ab\to C}\otimes T_{a'b'\to D})(M_{A'\to aa'}\otimes N_{B'\to bb'}) \tag*{(5)}

for unitaries SS, TT, MM, NN. We call such unitaries subsystem SWAP unitaries. Remarkably, subsystem SWAP unitaries are also implementable with zero entanglement cost: indeed the above explicitly defines an NLQC protocol of the form shown in Figure 1b, with no shared entanglement used. This means that the scrambling lower bound is faithful: if J(U)=0J(U)=0 we have that UU is a subsystem SWAP, and hence implementable with zero entanglement cost. This is the first known faithful lower bound on entanglement cost for unitaries in NLQC.2

An earlier lower bound on the entanglement cost of unitaries in NLQC is based on the controllable correlation. The controllable correlation is defined as follows. Consider a unitary UA′B′→CDU_{A'B'\to CD} and choose any state PAA′P_{AA'}, and any state ϕB′\phi_{B'}. Then, we consider the state

ωAC(ϕ)=tr⁡D(UA′B′→CD(PAA′⊗ϕB′)UA′B′→CD†).(6)\omega_{AC}(\phi)=\operatorname{tr}_{D}\left(U_{A'B'\to CD}\left(P_{AA'}\otimes\phi_{B'}\right)U^\dagger_{A'B'\to CD}\right). \tag*{(6)}

The controllable correlation is defined by

CCopt⁡(U)=max⁡P,ϕ1,ϕ2(I(A:C)ω(ϕ1)−I(A:C)ω(ϕ2)).(7)CC^{\operatorname{opt}}(U)=\max_{P,\phi^{1},\phi^{2}}\left(I(A:C)_{\omega(\phi^{1})}-I(A:C)_{\omega(\phi^{2})}\right). \tag*{(7)}

The work [26] proves that

E(U)≥CCopt⁡(U)2.(8)E(U)\ge\frac{CC^{\operatorname{opt}}(U)}{2}. \tag*{(8)}

The controllable correlation reveals another mechanism leading to the unitary UU requiring entanglement: If the choice of input on B′B' can adjust the correlation in A:CA:C, then UU requires entanglement to implement. Further, how much the correlation across A:CA:C can be adjusted provides a quantitative lower bound on entanglement cost.

A conjecture in [26] asked if the controllable correlation is a faithful measure for entanglement cost. Leveraging our results on scrambling lower bounds for entanglement cost, we can prove the controllable correlation is indeed faithful. We find that, conveniently,

CCopt⁡(U)=0⇒J(U)=0(9)CC^{\operatorname{opt}}(U)=0\Rightarrow J(U)=0 \tag*{(9)}

which suffices to show the controllable correlation is also faithful: when CCopt⁡(U)=0CC^{\operatorname{opt}}(U)=0 we have J(U)=0J(U)=0, and hence UU is a subsystem SWAP, so UU has zero entanglement cost.

It is interesting to compare the two lower bound techniques discussed here: the controllable correlation and the scrambling quantity. While they are both faithful, and hence both zero for the same set of unitaries, they are nonetheless distinct bounds. We give an explicit example where the controllable correlation is larger than the scrambling quantity, and another example where the scrambling quantity is larger than the controllable correlation. This reinforces that the two quantities capture qualitatively distinct properties of unitaries that lead to entanglement cost. Taken together, our two bounds begin to give a general understanding of which properties of a unitary are tied to its entanglement cost as an NLQC.

Organization of this paper: In § 2 we fix our notation and give some standard quantum information results we make use of in our work. § 3 deals with our lower bound based on scrambling: § 3.1 gives background on the physics of scrambling, and § 3.2 gives the proof of the scrambling based lower bound. § 3.3 then covers a few properties of the bound, including achieving the maximal value of the bound. In § 4, we revisit the controllable correlation lower bound, in particular proving it is faithful. In § 5, we discuss a relationship between the controllable correlation and the scrambling bound, and in particular show they are incomparable. We conclude with some open problems and discussion in § 6.

Background and tools

We use log⁡\log to denote the base 2 logarithm. Hilbert spaces are labelled with capital letters, HA\mathcal{H}_A, HB\mathcal{H}_B, ..., etc. Density matrices are labelled with greek letters, ρ\rho, σ\sigma, ω\omega, ..., etc. We use subscripts to track the Hilbert spaces where states live and channels act on, for instance NA→B(σA)=ωB\mathcal{N}_{A\to B}(\sigma_A)=\omega_B. We use dAd_A to denote the dimension of Hilbert space HA\mathcal{H}_A, and nAn_A to denote the log-dimension, nA=log⁡dAn_A=\log d_A.

Entropy: We define the von Neumann entropy of a density matrix ρA\rho_A as

S(A)ρ=−tr⁡(ρAlog⁡ρA).(10)S(A)_{\rho}=-\operatorname{tr}(\rho_A\log\rho_A). \tag*{(10)}

We define the conditional quantum entropy according to

S(A∣B)ρ=S(AB)ρ−S(B)ρ.(11)S(A|B)_{\rho}=S(AB)_{\rho}-S(B)_{\rho}. \tag*{(11)}

The conditional entropy is concave in its input state. That is for ρ=∑ipiρi\rho=\sum_i p_i\rho^i, we have

S(A∣B)ρ≥∑ipiS(A∣B)ρi.(12)S(A|B)_{\rho}\ge\sum_i p_iS(A|B)_{\rho^i}. \tag*{(12)}

A useful property of the entropy is that for pure states ψAB\psi_{AB}, the entropy of subsystems is equal,

S(A)ψ=S(B)ψ.(13)S(A)_{\psi}=S(B)_{\psi}. \tag*{(13)}

When we use this, we say that we exchange subsystems in the entropy using purity.

Mutual information: We define the mutual information as

I(Q:A)ρ=S(Q)ρ+S(A)ρ−S(QA)ρ(14)I(Q:A)_{\rho}=S(Q)_{\rho}+S(A)_{\rho}-S(QA)_{\rho} \tag*{(14)}

and the conditional mutual information by

I(A:C∣B)ρ=S(AB)ρ+S(BC)ρ−S(B)ρ−S(ABC)ρ.(15)I(A:C|B)_{\rho}=S(AB)_{\rho}+S(BC)_{\rho}-S(B)_{\rho}-S(ABC)_{\rho}. \tag*{(15)}

The chain rule relates the conditional mutual information to the mutual information,

I(A:C∣B)ρ=I(A:BC)ρ−I(A:B)ρ.(16)I(A:C|B)_{\rho}=I(A:BC)_{\rho}-I(A:B)_{\rho}. \tag*{(16)}

The strong subadditivity inequality expresses that the conditional mutual information is non-negative, I(A:C∣B)ρ≥0I(A:C|B)_{\rho}\ge0. Moving systems into the conditioning argument does not increase the mutual information,

I(A:BC∣D)ρ≥I(A:B∣CD)ρ.(17)I(A:BC|D)_{\rho}\ge I(A:B|CD)_{\rho}. \tag*{(17)}

The conditional mutual information of a classical quantum state satisfies the following.

Lemma 1 Consider the quantum state ρABX=∑ipiρABi⊗∣i⟩⟨i∣X\rho_{ABX}=\sum_i p_i\rho^i_{AB}\otimes|i\rangle\langle i|_X. Then

I(A:B∣X)ρ=∑ipiI(A:B)ρi(18)I(A:B|X)_{\rho}=\sum_i p_iI(A:B)_{\rho^i} \tag*{(18)}

When I(A:C∣B)ρ=0I(A:C|B)_{\rho}=0, a strong constraint is imposed on the structure of ρ\rho.

Theorem 2 ([27]) Let ωABC\omega_{ABC} be a quantum state. The following are equivalent:

:::`

  1. I(A:C∣B)ω=0I(A:C|B)_\omega=0.

  1. There exists a decomposition of the BB Hilbert space,

HB≃⨁i(HLi⊗HRi)(19)\mathcal{H}_B \simeq\bigoplus_i(\mathcal{H}_{L_i}\otimes\mathcal{H}_{R_i}) \tag*{(19)}

such that ω\omega can be written in the form

ωABC=⨁ipi ωALii⊗ωRiCi.(20)\omega_{ABC}=\bigoplus_i p_i\,\omega^i_{AL_i}\otimes\omega^i_{R_iC}. \tag*{(20)}
  1. There exists a channel RB→AB\mathcal{R}_{B\to AB} such that ωABC=(RB→AB⊗IC)(ωBC)\omega_{ABC}=(\mathcal{R}_{B\to AB}\otimes\mathcal{I}_C)(\omega_{BC}).

We will use the data processing inequality for mutual information, which states that the mutual information I(A:B)I(A:B) cannot increase under any local channel acting on AA and BB.

Lemma 3 Let ρAB\rho_{AB} be a quantum state, and let NA→A′\mathcal{N}_{A\to A'} and MB→B′\mathcal{M}_{B\to B'} be quantum channels. Let σA′B′C=(NA→A′⊗MB→B′)(ρABC)\sigma_{A'B'C}=(\mathcal{N}_{A\to A'}\otimes\mathcal{M}_{B\to B'})(\rho_{ABC}). Then,

I(A:B∣C)ρ≥I(A′:B′∣C)σ.(21)I(A:B|C)_\rho\ge I(A':B'|C)_\sigma. \tag*{(21)}

Quantum channels: Given a quantum channel NB→C\mathcal{N}_{B\to C}, we will make use of the Choi state of the channel,

χACN=NB→C(ΨAB+)=1dA∑i,j∣i⟩⟨j∣A⊗NB→C(∣i⟩⟨j∣B).(22)\chi^{{\mathcal{N}}}_{AC}=\mathcal{N}_{B\to C}(\Psi^+_{AB})=\frac{1}{d_A}\sum_{i,j}|i\rangle\langle j|_A\otimes\mathcal{N}_{B\to C}(|i\rangle\langle j|_B). \tag*{(22)}

We note that the Choi state of a channel uniquely fixes the channel. We also use the diamond norm distance on channels.

Definition 4 Let NB→C,MB→C:L(HB)→L(HC)\mathcal{N}_{B\to C},\mathcal{M}_{B\to C}:\mathcal{L}(\mathcal{H}_B)\to\mathcal{L}(\mathcal{H}_C) be quantum channels. The diamond norm distance is defined by

∥NB→C−MB→C∥⋄=sup⁡dmax⁡ΨAdB∥NB→C(ΨAdB)−MB→C(ΨAdB)∥1(23)\left\|\mathcal{N}_{B\to C}-\mathcal{M}_{B\to C}\right\|_\diamond=\sup_{d}\max_{\Psi_{A_dB}}\left\|\mathcal{N}_{B\to C}(\Psi_{A_dB})-\mathcal{M}_{B\to C}(\Psi_{A_dB})\right\|_1 \tag*{(23)}

where HAd\mathcal{H}_{A_d} is a dd dimensional Hilbert space.

Entanglement: We make use of the following measure of entanglement.

Definition 5 The entanglement of formation is defined as

Ef(A:B)ρ=min⁡{pi,∣ψi⟩}∑ipiS(B)ψi,(24)E_f(A:B)_\rho=\min_{\{p_i,|\psi_i\rangle\}}\sum_i p_i S(B)_{\psi_i}, \tag*{(24)}

where the minimization is over ensembles {pi,∣ψi⟩}\{p_i,|\psi_i\rangle\} such that ρ=∑ipi∣ψi⟩⟨ψi∣\rho=\sum_i p_i|\psi_i\rangle\langle\psi_i|.

Note that this is a faithful measure: Ef(A:B)ρ=0E_f(A:B)_\rho=0 if and only if ρ\rho is separable.

A faithful lower bound from scrambling

Scrambling, tripartite mutual information, and zero-entanglement unitaries

To develop our lower bound strategy our starting point is the observation that at least the following class of unitaries, mentioned in the introduction, can be implemented as NLQCs using zero entanglement.

Definition 6 A unitary UA′B′→CDU_{A'B'\to CD} is said to be a subsystem SWAP unitary if it takes the form

UA′B′→CD=(Sab→C⊗Ta′b′→D)(MA′→aa′⊗NB′→bb′).(25)U_{A'B'\to CD} = (S_{ab\to C} \otimes T_{a'b'\to D})(M_{A'\to aa'} \otimes N_{B'\to bb'}). \tag*{(25)}

where S,T,M,NS,T,M,N are unitaries.

From the form of the NLQC circuit, it is apparent any subsystem SWAP unitary can be implemented without using any entanglement. It is intuitive, but not entirely apparent, that every unitary that can be implemented with zero entanglement should be a subsystem SWAP unitary; plausibly the use of local channels rather than local unitaries could allow a larger class of unitaries to be implemented. Since the overall action is unitary however, we might guess that the subsystem SWAP form accounts for all zero-entanglement cost unitaries. Motivated by this, we begin investigating how to characterize the subsystem SWAP unitaries.

The subsystem SWAP unitaries appear in the scrambling literature, in the context of the following theorem from [25].

Theorem 7 Let UA′B′→CDU_{A'B'\to CD} be a unitary, and define the Choi state for this unitary

∣χU⟩ABCD=UA′B′→CD∣Ψ+⟩A′A∣Ψ+⟩B′B.(26)\left|\chi^U\right\rangle_{ABCD} = U_{A'B'\to CD}\left|\Psi^+\right\rangle_{A'A}\left|\Psi^+\right\rangle_{B'B}. \tag*{(26)}

Then,

I(A:B∣C)χU=0⟺UA′B′→CD is a subsystem SWAP unitary.(27)I(A:B|C)_{\chi^U} = 0 \Longleftrightarrow U_{A'B'\to CD}\text{ is a subsystem SWAP unitary.} \tag*{(27)}

In the Choi state ∣χU⟩\left|\chi^U\right\rangle, because the density matrix on ABAB is maximally mixed and the state on ABCDABCD is pure, it follows from the definition of the tripartite mutual information (equation (3)) that

I3(A:C:D)χU=−I(A:B∣C)χU.(28)I_3(A:C:D)_{\chi^U} = -I(A:B|C)_{\chi^U}. \tag*{(28)}

Thus we can also view the subsystem SWAP unitaries as those whose Choi state has zero tripartite mutual information. This motivates us to recall the previous reasoning for studying the tripartite mutual information, which relates to the physics of scrambling.

From the definition of the tripartite mutual information, we see that it is negative when

I(A:CD)>I(A:C)+I(A:D).(29)I(A:CD) > I(A:C) + I(A:D). \tag*{(29)}

This is saying that it is negative when more correlation with AA is stored jointly in CDCD than in CC and DD taken separately. Considering the subsystem SWAP unitaries, it is clear they do not scramble information in this sense: ignoring the local unitaries (which do not change the correlation measures), the subsystem SWAP keeps information localized, and just rearranges where certain qubits sit.

It is also interesting to recall the relationship between scrambling and chaos found in [24], which is phrased in terms of the tripartite mutual information. To understand the relationship between chaos and scrambling, consider a complete basis of operators on the A′A' Hilbert space, call them {OA′i}i\{O_{A'}^{i}\}_i, and a complete basis of operators on the DD Hilbert space, call them {ODj}j\{O_D^{j}\}_j. A standard diagnostic of chaos in the unitary UA′B′→CDU_{A'B'\to CD} is the out-of-time-order correlation function, or OTOC, defined as

⟨Oi(t)ODjOi(t)ODj⟩=tr⁡(ρCDOi(t)ODjOi(t)ODj).(30)\langle O^{i}(t)O_D^{j}O^{i}(t)O_D^{j}\rangle= \operatorname{tr}\left(\rho_{CD}O^{i}(t)O_D^{j}O^{i}(t)O_D^{j}\right). \tag*{(30)}

Here, by Oi(t)O^{i}(t) we mean the time evolved operator, Oi(t):=UA′B′→CDOA′B′iUA′B′→CD†O^{i}(t) := U_{A'B'\to CD}O_{A'B'}^{i}U_{A'B'\to CD}^{\dagger}, and by ρCD\rho_{CD} we mean the CDCD subsystem of the Choi state.3 We are specifically interested in the value of this correlation function averaged over choice of operator,

⟨Oi(t)ODjOi(t)ODj⟩avg=1dA′2dD2∑i,j⟨Oi(t)ODjOi(t)ODj⟩.(31)\langle O^{i}(t)O_D^{j}O^{i}(t)O_D^{j}\rangle_{\mathrm{avg}} = \frac{1}{d_{A'}^{2}d_{D}^{2}}\sum_{i,j}\langle O^{i}(t)O_D^{j}O^{i}(t)O_D^{j}\rangle. \tag*{(31)}

This averaged OTOC is related in [24] to the tripartite mutual information according to

c02I3(A:C:D)χU/2≤⟨Oi(t)ODjOi(t)ODj⟩avg.(32)c_0 2^{I_3(A:C:D)_{\chi^U}/2} \le\langle O^{i}(t)O_D^{j}O^{i}(t)O_D^{j}\rangle_{\mathrm{avg}}. \tag*{(32)}

Here c0c_0 is a constant related to the minimal values of I3I_3 and the averaged correlation function; we omit these details for simplicity. We see that if the OTOC becomes small, a signature that the evolution of UU is chaotic, then I3I_3 must become negative.

Another appearance of the tripartite mutual information is in holography [28], where it is found that holographic states have I3≤0I_3 \le0 always. Intriguingly, NLQC has also been related to holography in [8, 11, 12], although its role there is not obviously related to the tripartite mutual information or scrambling.

Lower bound on entanglement from scrambling

We are now ready to prove that scrambling gives a lower bound on the entanglement cost of implementing a unitary as an NLQC. We first give a formal definition of the scrambling quantity.

Definition 8 We define the scrambling value J(N)J(\mathcal{N}) of a quantum channel NA′B′→CD\mathcal{N}_{A'B'\to CD} as follows. Take the Choi state of NA′B′→CD\mathcal{N}_{A'B'\to CD}, labelled χABCDN=NA′B′→CD(ΨAA′+⊗ΨBB′+)\chi^{\mathcal{N}}_{ABCD} = \mathcal{N}_{A'B'\to CD}(\Psi^+_{AA'} \otimes\Psi^+_{BB'}), and then define

J(N):=S(BC)χN+S(BD)χN−S(ABC)χN−S(ABD)χN.(33)J(\mathcal{N}) := S(BC)_{\chi^\mathcal{N}} + S(BD)_{\chi^\mathcal{N}} - S(ABC)_{\chi^\mathcal{N}} - S(ABD)_{\chi^\mathcal{N}}. \tag*{(33)}

This quantity is defined so as to appear as the lower bound in our proof below; we call it the scrambling quantity however because of its connection to the tripartite mutual information and scrambling when N\mathcal{N} is taken to be a unitary. Specifically, if we choose a unitary channel so that the Choi state is pure, we have

J(U)=S(BC)χU+S(BD)χU−S(ABC)χU−S(ABD)χU=S(BC)χU+S(AC)χU−S(ABC)χU−S(C)χU=I(A:B∣C)χU=−I3(A:C:D)χU.(34)\begin{aligned} J(U) &= S(BC)_{\chi^U} + S(BD)_{\chi^U} - S(ABC)_{\chi^U} - S(ABD)_{\chi^U} \\ &= S(BC)_{\chi^U} + S(AC)_{\chi^U} - S(ABC)_{\chi^U} - S(C)_{\chi^U} \\ &= I(A:B|C)_{\chi^U} \\ &= -I_3(A:C:D)_{\chi^U}. \tag*{(34)} \end{aligned}

Thus specialized to unitaries our “scrambling quantity” is exactly the tripartite mutual information relevant to scrambling. Before proving our lower bound, we need the following property of the scrambling quantity.

Lemma 9 The scrambling quantity is convex, that is

J(∑ipiNi)≤∑ipiJ(Ni).(35)J\left(\sum_i p_i\mathcal{N}^i\right) \le\sum_i p_i J\left(\mathcal{N}^i\right). \tag*{(35)}

Proof. Let N=∑ipiNi\mathcal{N} = \sum_i p_i\mathcal{N}^i. Then notice that

χN=∑ipiχNi(36)\chi^{\mathcal{N}} = \sum_i p_i \chi^{\mathcal{N}^i} \tag*{(36)}

Now re-express the scrambling quantity as

J(N)=−S(A∣BC)χN−S(A∣BD)χN(37)J(\mathcal{N}) = -S(A|BC)_{\chi^{\mathcal{N}}} - S(A|BD)_{\chi^{\mathcal{N}}} \tag*{(37)}

Now using that the conditional entropy is concave in the input state, we have that JJ is convex, as claimed. ■

When we lower bound the entanglement cost of implementing an NLQC for a given channel, we mean entanglement cost in the following sense.

Definition 10 Consider a channel NA′B′→CD\mathcal{N}_{A'B'\to CD}. Then we define the cost to implement NA′B′→CD\mathcal{N}_{A'B'\to CD} as an NLQC to be the minimal value of Ef(L:R)ΨE_f(L:R)_\Psi, minimized over all resource states ΨLR\Psi_{LR} that suffice to implement N\mathcal{N} exactly.

Finally, we are ready to prove the lower bound on entanglement cost based on the scrambling quantity.

Theorem 11 For any channel N\mathcal{N}, let E(N)E(\mathcal{N}) denote the entanglement cost of N\mathcal{N} (definition 10) and J(N)J(\mathcal{N}) the scrambling value (definition 8). Then

E(N)≥12J(N).(38)E(\mathcal{N}) \ge\frac{1}{2}J(\mathcal{N}). \tag*{(38)}

Proof. Recall that

E(N)=min⁡ΨEf(L:R)Ψ(39)E(\mathcal{N})=\min_{\Psi} E_f(L:R)_{\Psi} \tag*{(39)}

where the minimization is over all states ΨLR\Psi_{LR} that can be used as resource states to implement NA′B′→CD\mathcal{N}_{A'B'\to CD} as an NLQC.

We first consider a pure resource state ΨLR\Psi_{LR} and derive a bound on the entropy of LL. Without loss of generality, we assume the local operations in the NLQC protocol are isometric. Let the local operations and intermediate subsystems be labelled according to:

VA′L→A0A1,WB′R→B0B1,SA0B0→CX,TA1B1→DY.(40)V_{A'L\to A_0A_1}, W_{B'R\to B_0B_1}, S_{A_0B_0\to CX}, T_{A_1B_1\to DY}. \tag*{(40)}

These operations and the labels are shown in Figure 3. Consider the state

An NLQC protocol with pure shared resource

Figure 3. An NLQC protocol with pure shared resource ∣Ψ⟩LR|\Psi\rangle_{LR}. The reference-input pairs AA′AA' and BB′BB' are maximally entangled. The dashed lines mark ∣χ⟩AA0A1BB0B1|\chi\rangle_{AA_0A_1BB_0B_1} and ∣χ′⟩ABCDXY|\chi'\rangle_{ABCDXY}. The systems A1A_1 and B0B_0 are exchanged before SS and TT produce CC, DD, XX, YY. The reference systems AA, BB remain untouched.

∣χ⟩AA0A1BB0B1=(VA′L→A0A1⊗WB′R→B0B1)∣Ψ+⟩AA′∣Ψ+⟩BB′∣Ψ⟩LR.(41)|\chi\rangle_{AA_0A_1BB_0B_1}=\left(V_{A'L\to A_0A_1}\otimes W_{B'R\to B_0B_1}\right)|\Psi^+\rangle_{AA'}|\Psi^+\rangle_{BB'}|\Psi\rangle_{LR}. \tag*{(41)}

First notice that, since local isometries cannot change the mutual information,

2S(L)Ψ=I(L:R)Ψ=I(AA0A1:BB0B1)χ.(42)2S(L)_{\Psi}=I(L:R)_{\Psi}=I(AA_0A_1:BB_0B_1)_{\chi}. \tag*{(42)}

Now, use that

I(AA0A1:BB0B1)χ≥I(AA0:BB0)χ≥I(A:B∣A0B0)χ=I(A:B∣CX)χ′.(43)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'}. \tag*{(43)}

where we define the final state as

∣χ′⟩ABCDXY:=(IAB⊗SA0B0→CX⊗TA1B1→DY)∣χ⟩AA0A1BB0B1.(44)|\chi'\rangle_{ABCDXY}:=(I_{AB}\otimes S_{A_0B_0\to CX}\otimes T_{A_1B_1\to DY})|\chi\rangle_{AA_0A_1BB_0B_1}. \tag*{(44)}

The first inequality uses data processing (lemma 3) applied to the partial trace, the second inequality uses equation (17) twice, and the last equality uses that the map from A0B0A_0B_0 to CXCX is isometric. Combining this with equation (42), we get

2S(L)Ψ≥I(A:B∣CX)χ′.(45)2S(L)_{\Psi}\ge I(A:B|CX)_{\chi'}. \tag*{(45)}

Since XX is an output to the environment and isn’t fixed by the channel N\mathcal{N} (but rather by the isometric extension of N\mathcal{N}), we want to remove it from our bound on S(L)S(L), to obtain a bound that depends only on N\mathcal{N}. To do this, we use that

I(A:B∣CX)χ′=I(A:BCX)χ′−I(A:CX)χ′≥I(A:BC)χ′−I(A:CX)χ′≥I(A:BC)χ′−I(A:CXY)χ′.(46)\begin{aligned} I(A:B|CX)_{\chi'}&=I(A:BCX)_{\chi'}-I(A:CX)_{\chi'}\\ &\ge I(A:BC)_{\chi'}-I(A:CX)_{\chi'}\ge I(A:BC)_{\chi'}-I(A:CXY)_{\chi'}. \tag*{(46)} \end{aligned}

The two inequalities hold from the data processing inequality (lemma 3). Then using purity to exchange subsystems and because AA is maximally mixed, we get that I(A:CXY)χ′=2nA−I(A:BD)χ′I(A:CXY)_{\chi'}=2n_A-I(A:BD)_{\chi'}, so then

I(A:B∣CX)χ′≥I(A:BC)χ′+I(A:BD)χ′−2nA.(47)I(A:B|CX)_{\chi'}\ge I(A:BC)_{\chi'}+I(A:BD)_{\chi'}-2n_A. \tag*{(47)}

Combining this with equation (45), we get

2S(L)≥I(A:BC)χ′+I(A:BD)χ′−2nA.(48)2S(L) \ge I(A:BC)_{\chi'} + I(A:BD)_{\chi'} - 2n_A. \tag*{(48)}

From the definitions

χABCDN=tr⁡XY(χABCDXY′).(49)\chi^{\mathcal{N}}_{ABCD} = \operatorname{tr}_{XY}\left(\chi'_{ABCDXY}\right). \tag*{(49)}

Using that the density matrix on AA is maximally mixed, (48) is equivalently

2S(L)Ψ≥S(BC)χN+S(BD)χN−S(ABC)χN−S(ABD)χN=J(N).(50)2S(L)_{\Psi} \ge S(BC)_{\chi^{\mathcal{N}}} + S(BD)_{\chi^{\mathcal{N}}} - S(ABC)_{\chi^{\mathcal{N}}} - S(ABD)_{\chi^{\mathcal{N}}} = J(\mathcal{N}). \tag*{(50)}

Thus we have

S(L)Ψ≥J(N)2(51)S(L)_{\Psi} \ge\frac{J(\mathcal{N})}{2} \tag*{(51)}

for any pure resource state Ψ\Psi.

Next, we combine this with the definition of the entanglement of formation and convexity of JJ to obtain a lower bound on entanglement cost. Suppose that the resource state is a mixed state Ψ=∑ipiΨi\Psi= \sum_i p_i\Psi^i, where we consider the ensemble decomposition of Ψ\Psi that minimizes ∑ipiS(L)Ψi\sum_i p_iS(L)_{\Psi_i}, i.e. the minimizing ensemble in the definition of the entanglement of formation. Then the channel implemented by the NLQC protocol will be N=∑ipiNi\mathcal{N} = \sum_i p_i\mathcal{N}^i. To implement Ni\mathcal{N}^i, from equation (51) we get that we must have

S(L)Ψi≥J(Ni)2.(52)S(L)_{\Psi_i} \ge\frac{J(\mathcal{N}^i)}{2}. \tag*{(52)}

Now we use this to bound the entanglement of formation,

Ef(L:R)Ψ=∑ipiS(L)Ψi≥∑ipiJ(Ni)2≥J(N)2,(53)E_f(L:R)_{\Psi} = \sum_i p_iS(L)_{\Psi_i} \ge\sum_i p_i\frac{J(\mathcal{N}^i)}{2} \ge\frac{J(\mathcal{N})}{2}, \tag*{(53)}

where the last inequality follows from the convexity of the scrambling quantity (lemma 9). This concludes the proof.

In the context of controllable correlation, only unitaries are given lower bounds. As a consequence, [26] spends considerable effort in proving that channels which are close to unitary also obtain lower bounds. Here, since the bound applies to channels, we can circumvent this analysis: for a channel which is close to a unitary we can obtain a bound directly by evaluating the scrambling quantity for that channel. Further, since J(N)J(\mathcal{N}) is defined in terms of entropy of the Choi state, the entropy is continuous in the input state, and the Choi state is continuous in the channel, we know nearby channels obtain similar lower bounds immediately.

Focusing on the unitary case we find the following theorem, which leads to a complete characterization of unitary channels with zero entanglement cost.

Theorem 12 Considering only unitary channels, the lower bound of theorem 11 is faithful; that is,

J(U)=0⇔U has zero entanglement cost(54)J(U) = 0 \Leftrightarrow U \text{ has zero entanglement cost} \tag*{(54)}

Proof. That J(U)>0J(U) > 0 implies there is an entanglement cost is given by theorem 11. That J(U)=0J(U) = 0 implies the entanglement cost is zero follows from theorem 7: for UU unitary, J(U)=0J(U) = 0 means that UU is a subsystem swap, which can be directly implemented as an entanglement free NLQC. ■

Returning to our discussion of scrambling, we see that a unitary UA′B′→CDU_{A'B'\to CD} has zero entanglement cost if and only if it does not scramble information into CDCD. This gives a simple and physical interpretation of when unitaries have an entanglement cost in NLQC. Further, the lower bound of theorem 11 instructs us that unitaries that more thoroughly scramble information have larger entanglement costs.

Properties of the scrambling bound

Bound maximizing unitaries

We have characterized the cases where, for a unitary UU, J(U)=0J(U)=0. This occurs exactly when UU is a subsystem SWAP unitary. It is also interesting to understand the maximal value of J(U)J(U) and understand when this maximum is saturated. In fact this follows immediately from a discussion in [25], who understand when unitaries are maximally scrambling in the case where d=dA′=dB′=dC=dDd=d_{A'}=d_{B'}=d_C=d_D. For convenience we recall the most relevant points of that discussion briefly here.

First recall that

J(U)=I(A:B∣C)χU(55)J(U)=I(A:B|C)_{\chi^U} \tag*{(55)}

so that

J(U)≤2nA.(56)J(U)\le2n_A. \tag*{(56)}

But also,

I(A:B∣C)χU=S(AC)χU+S(BC)χU−S(C)χU−S(ABC)χU=S(AC)χU+S(AD)χU−S(C)χU−S(D)χU=2S(A)χU−I(A:C)χU−I(A:D)χU=2nA−I(A:C)χU−I(A:D)χU.(57)\begin{aligned} I(A:B|C)_{\chi^U} &= S(AC)_{\chi^U}+S(BC)_{\chi^U}-S(C)_{\chi^U}-S(ABC)_{\chi^U}\\ &=S(AC)_{\chi^U}+S(AD)_{\chi^U}-S(C)_{\chi^U}-S(D)_{\chi^U}\\ &=2S(A)_{\chi^U}-I(A:C)_{\chi^U}-I(A:D)_{\chi^U}\\ &=2n_A-I(A:C)_{\chi^U}-I(A:D)_{\chi^U}. \tag*{(57)} \end{aligned}

This tells us that to achieve maximal scrambling, we need I(A:C)=I(A:D)=0I(A:C)=I(A:D)=0. But now notice that by the definition of χU\chi^U, both χABU\chi^U_{AB} and χCDU\chi^U_{CD} are maximally mixed, so every single system marginal is maximally mixed. But then if χCU,χAU\chi^U_C,\chi^U_A are both maximally mixed and I(A:C)χU=0I(A:C)_{\chi^U}=0, it follows that χACU\chi^U_{AC} is maximally mixed. Similarly χADU\chi^U_{AD} is maximally mixed. Using S(BC)χU=S(AD)χUS(BC)_{\chi^U}=S(AD)_{\chi^U} and that χADU\chi^U_{AD} is maximally mixed, we get that BCBC is maximally mixed. Similarly S(BD)χU=S(AC)χUS(BD)_{\chi^U}=S(AC)_{\chi^U} and χACU\chi^U_{AC} we already found was maximally mixed, so BDBD is as well. Thus every two subsystem marginal of the Choi state χABCDU\chi^U_{ABCD} is maximally mixed, and hence is also maximally entangled across every bipartition.

If a state

∣Ψ⟩ABCD=∑ijklcijkl∣i⟩A∣j⟩B∣k⟩C∣ℓ⟩D(58)|\Psi\rangle_{ABCD}=\sum_{ijkl}c_{ijkl}|i\rangle_A|j\rangle_B|k\rangle_C|\ell\rangle_D \tag*{(58)}

is maximally entangled across every bipartition, we say that cijklc_{ijkl} is a perfect tensor. Given this understanding, we can straightforwardly use perfect tensors to construct examples of J(U)J(U) maximizing unitaries. An example is the unitary, defined for odd dd,

UA′B′→CDperfect∣i⟩A′∣j⟩B′=∣i+j⟩C∣i−j⟩D(59)U^{\mathrm{perfect}}_{A'B'\to CD}|i\rangle_{A'}|j\rangle_{B'}=|i+j\rangle_C|i-j\rangle_D \tag*{(59)}

where all arithmetic is modulo dd. This unitary is defined by a perfect tensor and hence is maximally scrambling, i.e., J(Uperfect)=2log⁡dJ(U^{\mathrm{perfect}})=2\log d. Some further discussion of the information-theoretic properties of maximally scrambling unitaries can be found in [25].

Unitaries with small values of J(U)J(U)

While we showed that J(U)=0J(U)=0 means the unitary UU is a subsystem SWAP unitary, and hence can be implemented with zero entanglement as an NLQC, it is natural to ask if J(U)J(U) small implies that UU must be close to the subsystem SWAP form. This question is actually also already understood in the scrambling literature [25]. We recall their insights that address this question here.

It is possible to construct a sequence of unitaries {Ud}d\{U_d\}_d, one for each choice of local dimension dd, such that as dd becomes large J(Ud)J(U_d) goes to zero, even while UdU_d stays far (in diamond norm) from any subsystem SWAP unitary. This is the content of the following theorem, proven in [25].

Theorem 13 Let dSd_S be an odd constant. Then there is a sequence of bipartite unitaries {Ud}d\{U_d\}_d such that

lim⁡d→∞J(Ud)=0(60)\lim_{d\to\infty} J(U_d)=0 \tag*{(60)}

and

lim inf⁡d→∞inf⁡U0:J(U0)=0∥Ud−U0∥⋄≥1.(61)\liminf_{d\to\infty}\inf_{U_0:J(U_0)=0}\lVert U_d-U_0\rVert_{\diamond}\ge1. \tag*{(61)}

The construction of the unitaries UdU_d is as follows. Let ∣a⟩,∣b⟩\lvert a\rangle,\lvert b\rangle be basis vectors in dd dimensional spaces. Then define UdU_d to act according to

Ud∣a⟩A∣b⟩B={US∣a⟩A′∣b⟩B′if 0≤a,b≤dS−1∣a⟩A′∣b⟩B′otherwiseU_d\lvert a\rangle_A\lvert b\rangle_B= \begin{cases} U_S\lvert a\rangle_{A'}\lvert b\rangle_{B'} & \text{if }0\le a,b\le d_S-1\\ \lvert a\rangle_{A'}\lvert b\rangle_{B'} & \text{otherwise} \end{cases}

where USU_S is any maximally scrambling unitary and dSd_S is a fixed constant. Thus UdU_d acts as a maximally scrambling unitary on a subspace whose relative size goes to zero as dd becomes large.

Faithfulness of the controllable correlation

In this section we relate the scrambling bound and the earlier bound based on controllable correlation [26]. This allows us to prove that the controllable correlation is a faithful lower bound. We begin with recalling the definition of the controllable correlation and investigating some of its properties.

Basic properties of the controllable correlation

We first recall the definition of the controllable correlation.

Definition 14 Consider a unitary UA′B′→CDU_{A'B'\to CD} and choose a state on AA′AA', which we label PAA′P_{AA'}, with nA′=nAn_{A'}=n_A. Define the states

ρACD1=UA′B′→CD(PAA′⊗ϕB′1)UA′B′→CD†,ρACD2=UA′B′→CD(PAA′⊗ϕB′2)UA′B′→CD†.(62)\begin{aligned} \rho^1_{ACD} &= U_{A'B'\to CD}(P_{AA'}\otimes\phi^1_{B'})U^\dagger_{A'B'\to CD},\\ \rho^2_{ACD} &= U_{A'B'\to CD}(P_{AA'}\otimes\phi^2_{B'})U^\dagger_{A'B'\to CD}. \tag*{(62)} \end{aligned}

We say that UA′B′→CDU_{A'B'\to CD} has (λ1,λ2)(\lambda_1,\lambda_2)-controllable correlation if there exist states ϕB′1,ϕB′2\phi^1_{B'},\phi^2_{B'}, and PAA′P_{AA'} such that

λ1=I(A:C)ρ1,λ2=I(A:C)ρ2.(63)\lambda_1=I(A:C)_{\rho^1},\qquad\lambda_2=I(A:C)_{\rho^2}. \tag*{(63)}

We always consider the case where λ1≥λ2\lambda_1\ge\lambda_2. If there is no choice of states PAA′P_{AA'}, ϕB′1\phi^1_{B'}, ϕB′2\phi^2_{B'} such that λ1>λ2\lambda_1>\lambda_2 we say UA′B′→CDU_{A'B'\to CD} is not controllably correlated.

It will be useful to define the quantity

CC(U,P,ϕ1,ϕ2)=I(A:C)ρ1−I(A:C)ρ2(64)CC(U,P,\phi^1,\phi^2)=I(A:C)_{\rho^1}-I(A:C)_{\rho^2} \tag*{(64)}

and then

CCopt(U)=max⁡P,ϕ1,ϕ2CC(U,P,ϕ1,ϕ2).(65)CC^{\mathrm{opt}}(U)=\max_{P,\phi^1,\phi^2}CC(U,P,\phi^1,\phi^2). \tag*{(65)}

In [26], the following lower bound is proven.

Theorem 15. If an NLQCNLQC protocol using a resource Ψ\Psi gives a perfectly correct implementation of UA′B′→CDU_{A'B'\to CD}, then

Ef(L:R)Ψ≥CCopt(U)2.(66)E_f(L:R)_{\Psi}\ge\frac{CC^{\mathrm{opt}}(U)}{2}. \tag*{(66)}

Note that we focus on the perfect case, while [26] allows for an ϵ\epsilon-correct implementation of UA′B′→CDU_{A'B'\to CD} and then proves a lower bound that depends on ϵ\epsilon.

We define a simpler quantity than the optimized controllable correlation, which fixes PAA′=ΨAA′+P_{AA'}=\Psi^+_{AA'}, the maximally entangled state, and does not involve an optimization.

Definition 16. Consider any ensemble E={(pi,ϕB′i)}i=1rE=\{(p_i,\phi^i_{B'})\}_{i=1}^{r}. The averaged controllable correlation using ensemble EE is defined by

CC‾(U,E)=∑ipiI(A:C)ρi−I(A:C)ρ0(67)\overline{CC}(U,E)=\sum_i p_i I(A:C)_{\rho^i}-I(A:C)_{\rho^0} \tag*{(67)}

where, for i≥1i\ge1,

ρACDi=UA′B′→CD(ΨAA′+⊗ϕB′i)UA′B′→CD†.(68)\rho^i_{ACD}=U_{A'B'\to CD}\left(\Psi^+_{AA'}\otimes\phi^i_{B'}\right)U^\dagger_{A'B'\to CD}. \tag*{(68)}

and by ρ0\rho^0 we mean UA′B′→CD(ΨAA′+⊗πB′)UA′B′→CD†U_{A'B'\to CD}\left(\Psi^+_{AA'}\otimes\pi_{B'}\right)U^\dagger_{A'B'\to CD}.

The averaged controllable correlation can also be viewed as a conditional mutual information, as long as the ensemble satisfies ∑ipiϕB′i=πB′\sum_i p_i\phi^i_{B'}=\pi_{B'}, where πB\pi_B is the maximally mixed state.

Lemma 17. Consider any ensemble E={(pi,ϕB′i)}E=\{(p_i,\phi^i_{B'})\} with ∑ipiϕB′i=πB′\sum_i p_i\phi^i_{B'}=\pi_{B'}, where πB′\pi_{B'} is the maximally mixed state. Define

ωACX=∑ipiρACi⊗∣i⟩⟨i∣X(69)\omega_{ACX}=\sum_i p_i\rho^i_{AC}\otimes|i\rangle\langle i|_X \tag*{(69)}

where ρACi=tr⁡D(UA′B′→CD(ΨAA′+⊗ϕB′i)UA′B′→CD†)\rho^i_{AC}=\operatorname{tr}_D\left(U_{A'B'\to CD}\left(\Psi^+_{AA'}\otimes\phi^i_{B'}\right)U^\dagger_{A'B'\to CD}\right), so that ωACX\omega_{ACX} is the output of the unitary if the B′B' subsystem of the state ∑ipiϕB′i⊗∣i⟩⟨i∣X\sum_i p_i\phi^i_{B'}\otimes|i\rangle\langle i|_X is taken as the input on B′B'. Then we have

CC‾(U,E)=I(A:X∣C)ω(70)\overline{CC}(U,E)=I(A:X|C)_{\omega} \tag*{(70)}

Proof. By the chain rule, we have

I(A:X∣C)ω=I(A:CX)ω−I(A:C)ω.(71)I(A:X|C)_{\omega}=I(A:CX)_{\omega}-I(A:C)_{\omega}. \tag*{(71)}

Notice that

ωAC=tr⁡X(∑ipiρACi⊗∣i⟩⟨i∣X)=∑ipiρACi=∑ipitr⁡D(UA′B′→CD(ΨAA′+⊗ϕB′i)UA′B′→CD†)=tr⁡D(UA′B′→CD(ΨAA′+⊗πB′)UA′B′→CD†).(72)\omega_{AC}=\operatorname{tr}_{X}\left(\sum_i p_i\rho_{AC}^{i}\otimes|i\rangle\langle i|_{X}\right) =\sum_i p_i\rho_{AC}^{i} =\sum_i p_i\operatorname{tr}_{D}\left(U_{A'B'\to CD}\left(\Psi^+_{AA'}\otimes\phi_{B'}^{i}\right)U_{A'B'\to CD}^{\dagger}\right) =\operatorname{tr}_{D}\left(U_{A'B'\to CD}\left(\Psi^+_{AA'}\otimes\pi_{B'}\right)U_{A'B'\to CD}^{\dagger}\right). \tag*{(72)}

So then I(A:C)ω=I(A:C)ρ0I(A:C)_{\omega}=I(A:C)_{\rho_0}, and so the second term in (71) matches the second term in the averaged controllable correlation. It remains to show the first terms match, i.e. that I(A:CX)ω=∑ipiI(A:C)ρiI(A:CX)_{\omega}=\sum_i p_i I(A:C)_{\rho^i}. For this, first use the chain rule

I(A:CX)ω=I(A:C∣X)ω+I(A:X)ω(73)I(A:CX)_{\omega}=I(A:C|X)_{\omega}+I(A:X)_{\omega} \tag*{(73)}

and then observe that A:XA:X is uncorrelated, so the second term is zero. Then, use lemma 1 which gives

I(A:CX)ω=I(A:C∣X)ω=∑ipiI(A:C)ρi(74)\begin{aligned} I(A:CX)_{\omega}&=I(A:C|X)_{\omega}\\ &=\sum_i p_i I(A:C)_{\rho^i} \tag*{(74)} \end{aligned}

as claimed. ■

We prove the following relationship between the average and optimized controllable correlations.

Lemma 18 Consider any ensemble E={(pi,ϕB′i)}E=\{(p_i,\phi_{B'}^i)\} with ∑ipiϕB′i=πB′\sum_i p_i\phi_{B'}^i=\pi_{B'}, where πB′\pi_{B'} is the maximally mixed state. Then

CC‾(U,E)≤CCopt(U).(75)\overline{CC}(U,E)\le CC^{\mathrm{opt}}(U). \tag*{(75)}

Proof. Choose i∗i^* where ϕi∗\phi^{i^*} is the state among those in the ensemble EE that has the largest value of I(A:C)ρi∗I(A:C)_{\rho^{i^*}}. Then the controllable correlation CC(U,Ψ+,ϕi∗,π)CC(U,\Psi^+,\phi^{i^*},\pi) would be

CC(U,Ψ+,ϕi∗,π)=I(A:C)ρi∗−I(A:C)ρ0≥I(A:C)ρi−I(A:C)ρ0(76)CC(U,\Psi^+,\phi^{i^*},\pi)=I(A:C)_{\rho^{i^*}}-I(A:C)_{\rho_0} \ge I(A:C)_{\rho^i}-I(A:C)_{\rho_0} \tag*{(76)}

which holds for every ii. But then this also holds on average over ii with respect to the probabilities pip_i, so

CC(U,Ψ+,ϕi∗,π)≥CC‾(U,E)(77)CC(U,\Psi^+,\phi^{i^*},\pi)\ge\overline{CC}(U,E) \tag*{(77)}

and finally CCopt(U)≥CC(U,Ψ+,ϕi∗,π)CC^{\mathrm{opt}}(U)\ge CC(U,\Psi^+,\phi^{i^*},\pi), which proves (75). ■

Note that the above lemma implies that the averaged controllable correlation also gives a lower bound on entanglement cost.

Faithfulness of the controllable correlation

To see that the controllable correlation is faithful, we prove the averaged controllable correlation being zero implies the scrambling value J(U)J(U) is zero. In particular, this holds when the averaged controllable correlation is computed with respect to a complete ensemble, where we say that E={(pi,ϕB′i)}E=\{(p_i,\phi_{B'}^i)\} is a complete ensemble if pi>0p_i>0 for all ii, ∑ipiϕB′i=πB′\sum_i p_i\phi_{B'}^i=\pi_{B'} and {ϕB′i}\{\phi_{B'}^i\} spans the operators on HB′\mathcal{H}_{B'}.

Theorem 19. For every complete ensemble EE, we have that

CC‾(U,E)=0⇒J(U)=0(78)\overline{CC}(U,E)=0 \Rightarrow J(U)=0 \tag*{(78)}

Proof. First, assume that the averaged controllable correlation is zero. From lemma 17, we have

0=CC‾(U,E)=I(A:X∣C)ω.(79)0=\overline{CC}(U,E)=I(A:X|C)_{\omega}. \tag*{(79)}

This tells us, using the recovery theorem (theorem 2), that

ωACX=TC→AC(ωCX).(80)\omega_{ACX}=\mathcal{T}_{C\to AC}(\omega_{CX}). \tag*{(80)}

Recall that

ωACX=∑ipiρACi⊗∣i⟩⟨i∣X.(81)\omega_{ACX}=\sum_i p_i\rho^i_{AC}\otimes|i\rangle\langle i|_X. \tag*{(81)}

Projecting in ⟨i∣X⋅∣i⟩X\langle i|_X\cdot|i\rangle_X to both sides of equation (80), we get

ρACi=TC→AC(ρCi),(82)\rho^i_{AC}=\mathcal{T}_{C\to AC}(\rho^i_C), \tag*{(82)}

where ρCi=tr⁡A(ρACi)\rho^i_C=\operatorname{tr}_A(\rho^i_{AC}). Now define

NA′B′→C(⋅)=tr⁡D(UA′B′→CD(⋅)UA′B′→CD†),(83)\mathcal{N}_{A'B'\to C}(\cdot)=\operatorname{tr}_D\left(U_{A'B'\to CD}(\cdot)U^\dagger_{A'B'\to CD}\right), \tag*{(83)}

and use

ρACi=NA′B′→C(ΨAA′+⊗φB′i)=FB′→AC(φB′i)(84)\rho^i_{AC}=\mathcal{N}_{A'B'\to C}(\Psi^+_{AA'}\otimes\varphi^i_{B'})=\mathcal{F}_{B'\to AC}(\varphi^i_{B'}) \tag*{(84)}

where the last line defines FB′→AC\mathcal{F}_{B'\to AC}, and

ρCi=tr⁡AρACi=NA′B′→C(πA′⊗φB′i)=GB′→C(φB′i)(85)\rho^i_C=\operatorname{tr}_A\rho^i_{AC}=\mathcal{N}_{A'B'\to C}(\pi_{A'}\otimes\varphi^i_{B'})=\mathcal{G}_{B'\to C}(\varphi^i_{B'}) \tag*{(85)}

where the last equality defines GB′→C\mathcal{G}_{B'\to C}. Inserting the last two expressions in equation (82), we have

FB′→AC(φB′i)=TC→AC∘GB′→C(φB′i).(86)\mathcal{F}_{B'\to AC}(\varphi^i_{B'})=\mathcal{T}_{C\to AC}\circ\mathcal{G}_{B'\to C}(\varphi^i_{B'}). \tag*{(86)}

Because the ensemble EE is complete, this holds for a spanning set of φB′i\varphi^i_{B'}, and we get that

FB′→AC=TC→AC∘GB′→C.(87)\mathcal{F}_{B'\to AC}=\mathcal{T}_{C\to AC}\circ\mathcal{G}_{B'\to C}. \tag*{(87)}

Next, let’s look at the Choi state of UA′B′→CDU_{A'B'\to CD}, with DD traced out,

χACBU=tr⁡D(UA′B′→CD(ΨAA′+⊗ΨB′B+)UA′B′→CD†)=NA′B′→C(ΨAA′+⊗ΨB′B+)=FB′→AC(ΨB′B+)(88)\begin{aligned} \chi^U_{ACB} &=\operatorname{tr}_D\left(U_{A'B'\to CD}(\Psi^+_{AA'}\otimes\Psi^+_{B'B})U^\dagger_{A'B'\to CD}\right)\\ &=\mathcal{N}_{A'B'\to C}(\Psi^+_{AA'}\otimes\Psi^+_{B'B})\\ &=\mathcal{F}_{B'\to AC}(\Psi^+_{B'B}) \tag*{(88)} \end{aligned}

where the last line follows from the definition of FB′→AC\mathcal{F}_{B'\to AC}. Now use equation (87), leading to

χACBU=TC→AC∘GB′→C(ΨB′B+)=TC→AC(χCBU).(89)\chi^U_{ACB}=\mathcal{T}_{C\to AC}\circ\mathcal{G}_{B'\to C}(\Psi^+_{B'B})=\mathcal{T}_{C\to AC}(\chi^U_{CB}). \tag*{(89)}

This shows that χACBU\chi^U_{ACB} is a B→C→AB\to C\to A Markov chain, so then J(U)=I(A:B∣C)χU=0J(U)=I(A:B|C)_{\chi^U}=0, as claimed. ■

From here, we immediately obtain the following.

Theorem 20. For any complete ensemble EE, the averaged controllable correlation is faithful. As well, the optimized controllable correlation is faithful.

Proof. To see that the averaged controllable correlation is faithful, use that from theorem 19 we get

CC‾(U,E)=0⇒J(U)=0(90)\overline{CC}(U,E)=0 \Rightarrow J(U)=0 \tag*{(90)}

and from theorem 7, J(U)=0J(U)=0 means UU is a subsystem SWAP unitary, so can be implemented with zero entanglement.

To see that the optimized controllable correlation is faithful we just use lemma 18, which states that

CCopt(U)≥CC‾(U,E)(91)CC^{\mathrm{opt}}(U) \ge\overline{CC}(U,E) \tag*{(91)}

for any complete ensemble EE, so when the optimized controllable correlation is zero, the average controllable correlation is zero, so then the unitary has the subsystem SWAP form and hence has zero cost. ■

Achieving the maximal value

The controllable correlation has the obvious upper bound

CCopt(U)=max⁡PAA′,ϕB′1,ϕB′2(I(A:C)ρ1−I(A:C)ρ2)≤2nA.(92)CC^{\mathrm{opt}}(U)=\max_{P_{AA'},\phi^{1}_{B'},\phi^{2}_{B'}}\left(I(A:C)_{\rho^1}-I(A:C)_{\rho^2}\right)\le2n_A. \tag*{(92)}

In [26], the controllable correlation was computed for a variety of two qubit unitaries. It was observed that the largest obtained value appeared to be 1, even when sampling a large number of Haar random two qubit unitaries, which is suggestive that the controllable correlation actually attains a maximum at nAn_A (since nA=1n_A=1 for a two qubit unitary). However, we can actually saturate the bound of 2nA2n_A easily. Consider the controlled SWAP unitary,

UA′B′→CD=IA′B′⊗∣0⟩⟨0∣B0′+SWAP⁡A′B′⊗∣1⟩⟨1∣B0′.(93)U_{A'B'\to CD}=\mathbb{I}_{A'B'}\otimes\lvert0\rangle\langle0\rvert_{B'_0}+\operatorname{SWAP}_{A'B'}\otimes\lvert1\rangle\langle1\rvert_{B'_0}. \tag*{(93)}

Here B′=B0′B1′B'=B'_0B'_1, and we identify A′→CA'\to C, B′→DB'\to D in the outputs. Choose ϕB′1=∣0⟩⟨0∣B0′⊗πB1′\phi^{1}_{B'}=\lvert0\rangle\langle0\rvert_{B'_0}\otimes\pi_{B'_1}, ϕB′2=∣1⟩⟨1∣B0′⊗πB1′\phi^{2}_{B'}=\lvert1\rangle\langle1\rvert_{B'_0}\otimes\pi_{B'_1}, and PAA′=ΨAA′+P_{AA'}=\Psi^{+}_{AA'}. Then we find that

λ1=I(A:C)ρ1=2nA,\lambda_1=I(A:C)_{\rho^1}=2n_A,
λ2=I(A:C)ρ2=0(94)\lambda_2=I(A:C)_{\rho^2}=0 \tag*{(94)}

so that

CCopt(U)=2nA.(95)CC^{\mathrm{opt}}(U)=2n_A. \tag*{(95)}

Relationship between controllable correlation and the scrambling quantity

So far, we have studied three quantities which provide lower bounds on entanglement cost in NLQC: the optimized controllable correlation CCopt(U)CC^{\mathrm{opt}}(U), the averaged controllable correlation CC‾(U,E)\overline{CC}(U,E), and the scrambling quantity J(U)J(U). We noted already that

CCopt(U)≥CC‾(U,E).(96)CC^{\mathrm{opt}}(U)\ge\overline{CC}(U,E). \tag*{(96)}

It is natural to ask about the remaining relationships among these three quantities. We first of all clarify the relationship between the averaged controllable correlation and the scrambling quantity.

Remark 21 For every ensemble E={(pi,ϕi)}E=\{(p_i,\phi^i)\} such that ∑ipiϕi=π\sum_i p_i\phi^i=\pi, the averaged controllable correlation and the scrambling quantity are related by

J(U)≥CC‾(U,E)(97)J(U) \ge\overline{CC}(U,E) \tag*{(97)}

Proof. Recall that the scrambling quantity is

J(U)=I(A:B∣C)χU(98)J(U)=I(A:B|C)_{\chi^U} \tag*{(98)}

where χU\chi^U is the Choi state of UU,

χABCDU=UA′B′→CD(ΨAA′+⊗ΨBB′+)UA′B′→CD†.(99)\chi^U_{ABCD}=U_{A'B'\to CD}\left(\Psi^+_{AA'}\otimes\Psi^+_{BB'}\right)U^\dagger_{A'B'\to CD}. \tag*{(99)}

Meanwhile by lemma 17

CC‾(U,E)=I(A:X∣C)ω(100)\overline{CC}(U,E)=I(A:X|C)_\omega \tag*{(100)}

where

ωACDX=UA′B′→CD(ΨAA′+⊗∑ipiϕB′i⊗∣i⟩⟨i∣X)UA′B′→CD†.(101)\omega_{ACDX}=U_{A'B'\to CD}\left(\Psi^+_{AA'}\otimes\sum_i p_i\phi^i_{B'}\otimes|i\rangle\langle i|_X\right)U^\dagger_{A'B'\to CD}. \tag*{(101)}

Thus J(U)J(U) and CC‾(U,E)\overline{CC}(U,E) are very similar quantities. To relate them, consider beginning with J(U)J(U) and measuring the BB system with the POVM {ΛBi=pidB(ϕBi)T}i\{\Lambda^i_B=p_i d_B(\phi^i_B)^T\}_i. We can check this is a legitimate POVM, since the Λi\Lambda^i are positive since the ϕi\phi^i are, and ∑iΛi=I\sum_i\Lambda^i=\mathcal{I} because ∑ipiϕi=π\sum_i p_i\phi^i=\pi. Consider measuring the BB subsystem of ΨB′B+\Psi^+_{B'B} using this POVM, and recording the measurement outcome ii in the XX register,

MB→X(ΨB′B+)=∑itr⁡B(ΛBiΨB′B+)⊗∣i⟩⟨i∣X=∑ipiϕB′i⊗∣i⟩⟨i∣X.(102)\begin{aligned} \mathcal{M}_{B\to X}(\Psi^+_{B'B})=\sum_i\operatorname{tr}_B(\Lambda^i_B\Psi^+_{B'B})\otimes|i\rangle\langle i|_X \\ &=\sum_i p_i\phi^i_{B'}\otimes|i\rangle\langle i|_X. \tag*{(102)} \end{aligned}

We get that this is exactly the input state when computing the controllable correlation. But by the data processing inequality (lemma 3), we have that

J(U)=I(A:B∣C)χU≥I(A:X∣C)MB→X(χU)=I(A:X∣C)ω=CC‾(U,E)(103)J(U)=I(A:B|C)_{\chi^U}\ge I(A:X|C)_{\mathcal{M}_{B\to X}(\chi^U)}=I(A:X|C)_\omega=\overline{CC}(U,E) \tag*{(103)}

as claimed. ■

We see that the averaged controllable correlation is bounded above by both the optimized controllable correlation and the scrambling quantity, so provides the weakest lower bound. It remains to understand how J(U)J(U) and CCopt(U)CC^{\mathrm{opt}}(U) are related. In fact, we can observe that they are incomparable, with neither quantity always providing the better bound. Instead, the two quantities provide complementary bounds.

To see this is straightforward: we can simply evaluate both bounds on the unitaries we’ve constructed that maximize each bound.

First, consider the controlled SWAP unitary (equation (93)), which we observed obtains a maximal value for the controllable correlation of 2nA2n_A. For concreteness choose nA=1n_A=1, so that nB=2n_B=2. We found that CCopt(CSWAP)=2CC^{\mathrm{opt}}(\mathrm{CSWAP})=2. Meanwhile, we can straightforwardly evaluate the scrambling quantity, and we find that J(CSWAP)≈0.55J(\mathrm{CSWAP}) \approx0.55. Thus the optimized controllable correlation can be larger than the scrambling quantity.

Next, lets revisit the explicit maximizing unitary we found for the scrambling quantity, the unitary in equation (59). For concreteness choose dA=dB=3d_A = d_B = 3. This achieves the maximal value of the scrambling quantity, J(Uperfect)=2log⁡3J(U^{\mathrm{perfect}}) = 2 \log3. Meanwhile, a numerical evaluation of the optimized controllable correlation returns 1.58 (likely in fact log⁡3\log3). Thus the scrambling quantity can be larger than the controllable correlation.

Discussion

In this work we give a new lower bound on entanglement cost in NLQC. Our bound is based on the scrambling quantity, which for unitary channels reduces to (minus) the tripartite mutual information used as a diagnostic of information scrambling. For unitaries, our bound is faithful: the bound never fails to return a positive entanglement cost if the unitary really does require entanglement. This is the first faithful lower bound for unitaries, and the relationship between scrambling and NLQC is new. Finally, the scrambling quantity can be shown to be zero whenever the controllable correlation is zero, showing that this earlier lower bound is also faithful.

These results begin to illuminate the origin of entanglement cost in NLQC. However, a complete understanding of entanglement cost in NLQC remains far away. Indeed, as noted elsewhere, many questions about entanglement cost in NLQC relate to difficult open problems in complexity theory, and we do not expect to understand these problems in full in the near future. Even many simple questions about entanglement cost in NLQC remain open however. For instance, we now have two faithful lower bounds for entanglement cost in NLQC, and one of them (the scrambling quantity) can be evaluated for any channel. However, the scrambling bound is not faithful for general quantum channels. For example, let UperfectU^{\mathrm{perfect}} be the unitary in (59) with d=3d = 3 and let R(⋅)=∣0⟩⟨0∣\mathcal{R}(\cdot) = |0\rangle\langle0| be the reset channel. Consider N=Uperfect⊗R\mathcal{N} = U^{\mathrm{perfect}} \otimes\mathcal{R} where R\mathcal{R} acts on an additional qutrit held by Alice. Then, J(N)=0J(\mathcal{N}) = 0 and E(N)≥E(Uperfect)≥log⁡3E(\mathcal{N}) \ge E(U^{\mathrm{perfect}}) \ge\log3. An interesting open question is to find a faithful lower bound for quantum channels. More generally, an understanding of the general, qualitative, properties that lead to entanglement cost in channels is still missing—the controllable correlation bound fails to hold in that setting, and the ‘scrambling quantity’ defined on general channels is not clearly related to the scrambling properties of the channel4 or more generally to have a simple meaning.

Addressing generic approaches to bounding entanglement cost in quantum channels may be an interesting, alternative, approach to bounding entanglement cost in the specific channels of the strongest interest. For instance in the ff-routing scenario [1, 9, 10, 29, 30], a qubit is redirected left or right based on a Boolean function ff of classical inputs x,y∈{0,1}nx,y \in\{0,1\}^n. An important goal is to prove a lower bound on entanglement cost that grows super-logarithmically with nn, even while the size of the quantum system is kept fixed. Several partial results in this direction have failed to give fully satisfactory bounds [4, 31, 32, 33]. The scrambling bound given here also fails to give strong entanglement bounds, but we can hope that further understanding of generic properties of channels that lead to entanglement cost can shed light on this problem.

Acknowledgements: A. H. is supported by JSPS KAKENHI grants Nos. 24H00071, 25K24674, 25K24465. A. M. acknowledges the support of the Natural Sciences and Engineering Research Council of Canada (NSERC); this work was supported by an NSERC-UKRI Alliance Grant No. (ALLRP 597823-24). Research at Perimeter Institute is supported in part by the Government of Canada through the Department of Innovation, Science and Economic Development and by the Province of Ontario through the Ministry of Colleges and Universities.

OpenAI Astra and Claude Opus were used extensively to suggest and simplify proofs. Astra initially gave a proof that controllable correlation is faithful. After understanding the proof, which revealed the subsystem SWAP unitaries as exactly the zero entanglement unitaries, we suggested Astra look for a more direct proof that these are the zero entanglement unitaries. Astra then returned with a proof of that claim based on theorem 7. We then observed that another lower bound on entanglement based on the scrambling quantity was being implied by this new proof, and we refined this using help from Claude Opus to develop theorem 11. Further refinements, including the extension of the scrambling bound to general channels, were then done using Claude Opus.

References

  1. [1]Adrian Kent, William J Munro, and Timothy P Spiller. Quantum tagging: Authenticating location via quantum information and relativistic signaling constraints. Physical Review A, 84(1):012326, 2011. DOI: 10.1103/PhysRevA.84.012326.DOI
  2. [2]Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, and Christian Schaffner. Position-based quantum cryptography: Impossibility and constructions. SIAM Journal on Computing, 43(1):150–178, 2014. DOI: 10.1137/130913687.DOI
  3. [3]Rene Allerstorfer, Harry Buhrman, Alex May, Florian Speelman, and Philip Verduyn Lunel. Relating non-local quantum computation to information theoretic cryptography. Quantum, 8:1387, 2024. DOI: 10.22331/q-2024-06-27-1387.DOI
  4. [4]Vahid R. Asadi, Eric Culf, and Alex May. Rank Lower Bounds on Non-Local Quantum Computation. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025), volume 325 of LIPIcs, pages 11:1–11:18, 2025. DOI: 10.4230/LIPIcs.ITCS.2025.11.DOI
  5. [5]Vahid R. Asadi, Kohdai Kuroiwa, Debbie Leung, Alex May, Sabrina Pasterski, and Chris Waddell. Conditional disclosure of secrets with quantum resources. Quantum, 9:1885, 2025.DOI
  6. [6]Uma Girish, Alex May, Natalie Parham, and Henry Yuen. Magic and communication complexity. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC 2026), pages 845–856, 2026.arxiv.org/abs/2510.07246
  7. [7]Florian Speelman. Instantaneous Non-Local Computation of Low T-Depth Quantum Circuits. In 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016), volume 61 of LIPIcs, pages 9:1–9:24, 2016. DOI: 10.4230/LIPIcs.TQC.2016.9.DOI
  8. [8]Alex May. Complexity and entanglement in non-local computation and holography. Quantum, 6:864, 2022. DOI: 10.22331/q-2022-11-28-864.DOI
  9. [9]Harry Buhrman, Serge Fehr, Christian Schaffner, and Florian Speelman. The garden-house model. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science (ITCS 2013), pages 145–158, 2013. DOI: 10.1145/2422436.2422455.DOI
  10. [10]Joy Cree and Alex May. Code-routing: a new attack on position verification. Quantum, 7:1079, 2023.DOI
  11. [11]Alex May. Quantum tasks in holography. Journal of High Energy Physics, 2019(10): 1–39, 2019. DOI: 10.1007/JHEP10(2019)233.DOI
  12. [12]Alex May, Geoff Penington, and Jonathan Sorce. Holographic scattering requires a connected entanglement wedge. Journal of High Energy Physics, 2020(8):1–34, 2020. DOI: 10.1007/JHEP08(2020)132.DOI
  13. [13]Alex May and Michelle Xu. Non-local computation and the black hole interior. Journal of High Energy Physics, 2024(2):79, 2024.arxiv.org/abs/2304.11184
  14. [14]Alex May, Jonathan Sorce, and Beni Yoshida. The connected wedge theorem and its consequences. Journal of High Energy Physics, 2022(11):1–65, 2022.
  15. [15]Prabhanjan Ananth, Vipul Goyal, Jiahui Liu, and Qipeng Liu. Unclonable secret sharing. In International Conference on the Theory and Application of Cryptology and Information Security, pages 129–157. Springer, 2025.arxiv.org/abs/2406.11008
  16. [16]Harriet Apel, Toby Cubitt, Patrick Hayden, Tamara Kohler, and David Pérez-García. Security of position-based quantum cryptography limits Hamiltonian simulation via holography. arXiv preprint arXiv:2401.09058, 2024. DOI: 10.48550/arXiv.2401.09058.DOI
  17. [17]Alex May. Entanglement cost in non-local quantum computation. arXiv preprint arXiv:2605.02840, 2026. DOI: 10.48550/arXiv.2605.02840.DOI
  18. [18]Marco Tomamichel, Serge Fehr, Jędrzej Kaniewski, and Stephanie Wehner. A monogamy-of-entanglement game with applications to device-independent quantum cryptography. New Journal of Physics, 15(10):103002, 2013. DOI: 10.1088/1367-2630/15/10/103002.DOI
  19. [19]Marius Junge, Aleksander M Kubicki, Carlos Palazuelos, and David Pérez-García. Geometry of Banach spaces: a new route towards Position Based Cryptography. arXiv preprint arXiv:2103.16357, 2021. DOI: 10.1007/s00220-022-04407-9.DOI
  20. [20]Isabel M Moreno-Cuadrado, David Perez-Garcia, and Carlos Palazuelos. Exponential lower bounds for low-degree strategies in position-based quantum cryptography. arXiv preprint arXiv:2609.35592, 2026.arxiv.org/abs/2609.35592
  21. [21]Alvin Gonzales and Eric Chitambar. Bounds on instantaneous nonlocal quantum computation. IEEE Transactions on Information Theory, 66(5):2951–2963, 2019. DOI: 10.1109/TIT.2019.2950190.DOI
  22. [22]Salman Beigi and Robert König. Simplified instantaneous non-local quantum computation with applications to position-based cryptography. New Journal of Physics, 13 (9):093036, 2011. DOI: 10.1088/1367-2630/13/9/093036.DOI
  23. [23]Shenglong Xu and Brian Swingle. Scrambling dynamics and out-of-time-ordered correlators in quantum many-body systems. PRX Quantum, 5:010201, 2024. DOI: 10.1103/PRXQuantum.5.010201.DOI
  24. [24]Pavan Hosur, Xiao-Liang Qi, Daniel A Roberts, and Beni Yoshida. Chaos in quantum channels. Journal of High Energy Physics, 2016(2):4, 2016.DOI
  25. [25]Dawei Ding, Patrick Hayden, and Michael Walter. Conditional mutual information of bipartite unitaries and scrambling. Journal of High Energy Physics, 2016(12):1–32, 2016.DOI
  26. [26]Richard Cleve and Alex May. Lower bounds on non-local computation from controllable correlation. arXiv preprint arXiv:2602.00255, 2026.arxiv.org/abs/2602.00255
  27. [27]Patrick Hayden, Richard Jozsa, Denes Petz, and Andreas Winter. Structure of states which satisfy strong subadditivity of quantum entropy with equality. Communications in Mathematical Physics, 246(2):359–374, 2004.
  28. [28]Patrick Hayden, Matthew Headrick, and Alexander Maloney. Holographic mutual information is monogamous. Physical Review D—Particles, Fields, Gravitation, and Cosmology, 87(4):046003, 2013.
  29. [29]Andreas Bluhm, Simon Höfer, Alex May, Mikka Stasiuk, Philip Verduyn Lunel, and Henry Yuen. A complexity theory for non-local quantum computation. Quantum, 10: 2152, 2026. DOI: 10.22331/q-2026-07-01-2152.DOI
  30. [30]Andreas Bluhm, Simon Höfer, Alex May, Florian Speelman, and Philip Verduyn Lunel. Equivalence of non-local computation tasks beyond clifford operations. arXiv preprint arXiv:2606.26354, 2026. DOI: 10.48550/arXiv.2606.26354.DOI
  31. [31]Andreas Bluhm, Matthias Christandl, and Florian Speelman. A single-qubit position verification protocol that is secure against multi-qubit attacks. Nature Physics, pages 1–4, 2022. DOI: 10.1038/s41567-022-01577-0.DOI
  32. [32]Vahid Asadi, Richard Cleve, Eric Culf, and Alex May. Linear gate bounds against natural functions for position-verification. Quantum, 9:1604, 2025. DOI: 10.22331/q-2025-01-21-1604.DOI
  33. [33]Alex May and Philip Verduyn Lunel. Quantum gate lower bounds for loss-tolerant position verification. arXiv preprint arXiv:2608.16495, 2026.arxiv.org/abs/2608.16495

Paper details

vlnc:W_ukabzgbt
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 5

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

OpenAI Astra, Claude Opus (multiple versions)

View statement
Looking for related papers…
Contents