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 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 systems to approximate the channel .
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 . Define the Choi state of this unitary (see Figure 2),
Figure 2. Choi state of the bipartite unitary . The lower cups represent maximally entangled states on and , and , are reference systems.
and consider the entropic quantity,
where
and is the quantum mutual information. The quantity is known as the tripartite mutual information. We call the scrambling quantity. Intuitively, becomes negative, and hence becomes positive, when the correlation with is held jointly in , but not in or alone — in other words, is positive when the correlation with has scrambled into and . Define as the minimal entanglement needed to implement as an NLQC, as quantified by the entanglement of formation in the resource state. We show that
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, . As shown in [25], this occurs exactly when
for unitaries , , , . 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 we have that 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 and choose any state , and any state . Then, we consider the state
The controllable correlation is defined by
The work [26] proves that
The controllable correlation reveals another mechanism leading to the unitary requiring entanglement: If the choice of input on can adjust the correlation in , then requires entanglement to implement. Further, how much the correlation across 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,
which suffices to show the controllable correlation is also faithful: when we have , and hence is a subsystem SWAP, so 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 to denote the base 2 logarithm. Hilbert spaces are labelled with capital letters, , , ..., etc. Density matrices are labelled with greek letters, , , , ..., etc. We use subscripts to track the Hilbert spaces where states live and channels act on, for instance . We use to denote the dimension of Hilbert space , and to denote the log-dimension, .
Entropy: We define the von Neumann entropy of a density matrix as
We define the conditional quantum entropy according to
The conditional entropy is concave in its input state. That is for , we have
A useful property of the entropy is that for pure states , the entropy of subsystems is equal,
When we use this, we say that we exchange subsystems in the entropy using purity.
Mutual information: We define the mutual information as
and the conditional mutual information by
The chain rule relates the conditional mutual information to the mutual information,
The strong subadditivity inequality expresses that the conditional mutual information is non-negative, . Moving systems into the conditioning argument does not increase the mutual information,
The conditional mutual information of a classical quantum state satisfies the following.
Lemma 1 Consider the quantum state . Then
When , a strong constraint is imposed on the structure of .
Theorem 2 ([27]) Let be a quantum state. The following are equivalent:
:::`
.
There exists a decomposition of the Hilbert space,
such that can be written in the form
There exists a channel such that .
We will use the data processing inequality for mutual information, which states that the mutual information cannot increase under any local channel acting on and .
Lemma 3 Let be a quantum state, and let and be quantum channels. Let . Then,
Quantum channels: Given a quantum channel , we will make use of the Choi state of the channel,
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 be quantum channels. The diamond norm distance is defined by
where is a dimensional Hilbert space.
Entanglement: We make use of the following measure of entanglement.
Definition 5 The entanglement of formation is defined as
where the minimization is over ensembles such that .
Note that this is a faithful measure: if and only if 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 is said to be a subsystem SWAP unitary if it takes the form
where 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 be a unitary, and define the Choi state for this unitary
Then,
In the Choi state , because the density matrix on is maximally mixed and the state on is pure, it follows from the definition of the tripartite mutual information (equation (3)) that
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
This is saying that it is negative when more correlation with is stored jointly in than in and 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 Hilbert space, call them , and a complete basis of operators on the Hilbert space, call them . A standard diagnostic of chaos in the unitary is the out-of-time-order correlation function, or OTOC, defined as
Here, by we mean the time evolved operator, , and by we mean the subsystem of the Choi state.3 We are specifically interested in the value of this correlation function averaged over choice of operator,
This averaged OTOC is related in [24] to the tripartite mutual information according to
Here is a constant related to the minimal values of 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 is chaotic, then must become negative.
Another appearance of the tripartite mutual information is in holography [28], where it is found that holographic states have 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 of a quantum channel as follows. Take the Choi state of , labelled , and then define
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 is taken to be a unitary. Specifically, if we choose a unitary channel so that the Choi state is pure, we have
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
Proof. Let . Then notice that
Now re-express the scrambling quantity as
Now using that the conditional entropy is concave in the input state, we have that 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 . Then we define the cost to implement as an NLQC to be the minimal value of , minimized over all resource states that suffice to implement exactly.
Finally, we are ready to prove the lower bound on entanglement cost based on the scrambling quantity.
Theorem 11 For any channel , let denote the entanglement cost of (definition 10) and the scrambling value (definition 8). Then
Proof. Recall that
where the minimization is over all states that can be used as resource states to implement as an NLQC.
We first consider a pure resource state and derive a bound on the entropy of . 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:
These operations and the labels are shown in Figure 3. Consider the state

Figure 3. An NLQC protocol with pure shared resource . The reference-input pairs and are maximally entangled. The dashed lines mark and . The systems and are exchanged before and produce , , , . The reference systems , remain untouched.
First notice that, since local isometries cannot change the mutual information,
Now, use that
where we define the final state as
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 to is isometric. Combining this with equation (42), we get
Since is an output to the environment and isn’t fixed by the channel (but rather by the isometric extension of ), we want to remove it from our bound on , to obtain a bound that depends only on . To do this, we use that
The two inequalities hold from the data processing inequality (lemma 3). Then using purity to exchange subsystems and because is maximally mixed, we get that , so then
Combining this with equation (45), we get
From the definitions
Using that the density matrix on is maximally mixed, (48) is equivalently
Thus we have
for any pure resource state .
Next, we combine this with the definition of the entanglement of formation and convexity of to obtain a lower bound on entanglement cost. Suppose that the resource state is a mixed state , where we consider the ensemble decomposition of that minimizes , i.e. the minimizing ensemble in the definition of the entanglement of formation. Then the channel implemented by the NLQC protocol will be . To implement , from equation (51) we get that we must have
Now we use this to bound the entanglement of formation,
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 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,
Proof. That implies there is an entanglement cost is given by theorem 11. That implies the entanglement cost is zero follows from theorem 7: for unitary, means that 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 has zero entanglement cost if and only if it does not scramble information into . 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 , . This occurs exactly when is a subsystem SWAP unitary. It is also interesting to understand the maximal value of 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 . For convenience we recall the most relevant points of that discussion briefly here.
First recall that
so that
But also,
This tells us that to achieve maximal scrambling, we need . But now notice that by the definition of , both and are maximally mixed, so every single system marginal is maximally mixed. But then if are both maximally mixed and , it follows that is maximally mixed. Similarly is maximally mixed. Using and that is maximally mixed, we get that is maximally mixed. Similarly and we already found was maximally mixed, so is as well. Thus every two subsystem marginal of the Choi state is maximally mixed, and hence is also maximally entangled across every bipartition.
If a state
is maximally entangled across every bipartition, we say that is a perfect tensor. Given this understanding, we can straightforwardly use perfect tensors to construct examples of maximizing unitaries. An example is the unitary, defined for odd ,
where all arithmetic is modulo . This unitary is defined by a perfect tensor and hence is maximally scrambling, i.e., . Some further discussion of the information-theoretic properties of maximally scrambling unitaries can be found in [25].
Unitaries with small values of
While we showed that means the unitary is a subsystem SWAP unitary, and hence can be implemented with zero entanglement as an NLQC, it is natural to ask if small implies that 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 , one for each choice of local dimension , such that as becomes large goes to zero, even while stays far (in diamond norm) from any subsystem SWAP unitary. This is the content of the following theorem, proven in [25].
Theorem 13 Let be an odd constant. Then there is a sequence of bipartite unitaries such that
and
The construction of the unitaries is as follows. Let be basis vectors in dimensional spaces. Then define to act according to
where is any maximally scrambling unitary and is a fixed constant. Thus acts as a maximally scrambling unitary on a subspace whose relative size goes to zero as 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 and choose a state on , which we label , with . Define the states
We say that has -controllable correlation if there exist states , and such that
We always consider the case where . If there is no choice of states , , such that we say is not controllably correlated.
It will be useful to define the quantity
and then
In [26], the following lower bound is proven.
Theorem 15. If an protocol using a resource gives a perfectly correct implementation of , then
Note that we focus on the perfect case, while [26] allows for an -correct implementation of and then proves a lower bound that depends on .
We define a simpler quantity than the optimized controllable correlation, which fixes , the maximally entangled state, and does not involve an optimization.
Definition 16. Consider any ensemble . The averaged controllable correlation using ensemble is defined by
where, for ,
and by we mean .
The averaged controllable correlation can also be viewed as a conditional mutual information, as long as the ensemble satisfies , where is the maximally mixed state.
Lemma 17. Consider any ensemble with , where is the maximally mixed state. Define
where , so that is the output of the unitary if the subsystem of the state is taken as the input on . Then we have
Proof. By the chain rule, we have
Notice that
So then , 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 . For this, first use the chain rule
and then observe that is uncorrelated, so the second term is zero. Then, use lemma 1 which gives
as claimed. ■
We prove the following relationship between the average and optimized controllable correlations.
Lemma 18 Consider any ensemble with , where is the maximally mixed state. Then
Proof. Choose where is the state among those in the ensemble that has the largest value of . Then the controllable correlation would be
which holds for every . But then this also holds on average over with respect to the probabilities , so
and finally , 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 is zero. In particular, this holds when the averaged controllable correlation is computed with respect to a complete ensemble, where we say that is a complete ensemble if for all , and spans the operators on .
Theorem 19. For every complete ensemble , we have that
Proof. First, assume that the averaged controllable correlation is zero. From lemma 17, we have
This tells us, using the recovery theorem (theorem 2), that
Recall that
Projecting in to both sides of equation (80), we get
where . Now define
and use
where the last line defines , and
where the last equality defines . Inserting the last two expressions in equation (82), we have
Because the ensemble is complete, this holds for a spanning set of , and we get that
Next, let’s look at the Choi state of , with traced out,
where the last line follows from the definition of . Now use equation (87), leading to
This shows that is a Markov chain, so then , as claimed. ■
From here, we immediately obtain the following.
Theorem 20. For any complete ensemble , 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
and from theorem 7, means 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
for any complete ensemble , 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
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 (since for a two qubit unitary). However, we can actually saturate the bound of easily. Consider the controlled SWAP unitary,
Here , and we identify , in the outputs. Choose , , and . Then we find that
so that
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 , the averaged controllable correlation , and the scrambling quantity . We noted already that
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 such that , the averaged controllable correlation and the scrambling quantity are related by
Proof. Recall that the scrambling quantity is
where is the Choi state of ,
Meanwhile by lemma 17
where
Thus and are very similar quantities. To relate them, consider beginning with and measuring the system with the POVM . We can check this is a legitimate POVM, since the are positive since the are, and because . Consider measuring the subsystem of using this POVM, and recording the measurement outcome in the register,
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
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 and 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 . For concreteness choose , so that . We found that . Meanwhile, we can straightforwardly evaluate the scrambling quantity, and we find that . 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 . This achieves the maximal value of the scrambling quantity, . Meanwhile, a numerical evaluation of the optimized controllable correlation returns 1.58 (likely in fact ). 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 be the unitary in (59) with and let be the reset channel. Consider where acts on an additional qutrit held by Alice. Then, and . 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 -routing scenario [1, 9, 10, 29, 30], a qubit is redirected left or right based on a Boolean function of classical inputs . An important goal is to prove a lower bound on entanglement cost that grows super-logarithmically with , 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]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]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]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]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]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]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]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]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]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]Joy Cree and Alex May. Code-routing: a new attack on position verification. Quantum, 7:1079, 2023.DOI
- [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]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]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]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]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]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]Alex May. Entanglement cost in non-local quantum computation. arXiv preprint arXiv:2605.02840, 2026. DOI: 10.48550/arXiv.2605.02840.DOI
- [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]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]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]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]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]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]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]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]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]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]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]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]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]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]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]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

