Perimeter QI

I’ve recently put my book / very long review article Entanglement cost in non-local quantum computation up on the arXiv. As well, I’m currently teaching a mini-course covering a portion of the book at PI. 

The above is probably the extent of the “useful information” portion of this post. (Below is much less useful, but hopefully interesting!)

Those of you who’ve interacted with me will know non-local quantum computation (NLQC) has occupied a great deal of my thinking for some time now. I started thinking seriously about it already in 2018, early in my PhD, when I realized it was related to the AdS/CFT correspondence. That realization launched me on the subsequent 8-year journey leading up to today, culminating in this book.

Reflecting back over the development of the subject, it both feels like progress has been moving incredibly fast, with a major surprise every few years, and at the same time that we’ve been completely stuck. Both perspectives are true, but they are true relative to somewhat different sets of problems around NLQC. 

On the fast progress side, we’ve had amazing developments in finding new connections between NLQC and other subjects. Initially, NLQC was understood as relevant only to quantum position-verification. Then came the connection to AdS/CFT. Now, we understand the reach of NLQC goes even further. For instance, we know that some well studied subjects in classical information-theoretic cryptography are classical analogues of NLQC. We also saw that NLQC techniques could be applied to give new communication complexity class separations, saw surprising connections to Hamiltonian simulation, built stronger connections to computational complexity theory, and saw an appearance of NLQC in unclonable secret sharing — over the past 8 years NLQC has been reaching out into many arms of quantum information, touching on and bridging a set of otherwise unrelated subjects. 

All of these applications push us to want to better understand one key question about NLQC: how much entanglement does it cost? This question re-appears when trying to prove security of position-verification schemes, when thinking about its implications for quantum gravity, and so on. There seems to be no getting around or away from this question. 

In trying to understand entanglement cost, progress on some key problems is stuck. We still don’t know, for instance, if the worst-case cost of an NLQC is exponential (despite some impressive efforts). As well, the best upper bound for a general unitary, currently exponential in the T-depth, hasn’t improved since 2015. The best lower bound on any NLQC is still linear in the number of input qubits. 

That we still don’t know these things is a bit embarrassing. 

On the other hand, another thing we’ve learned in the last 8 years is that we shouldn’t be too embarrassed about these things. In fact, the connections to the many other subjects have shown that some of these problems are likely very hard, in that they are analogous to or would solve long-standing open classical problems. For instance, exponential lower bounds for worst-case functions are not known in the classical analogue settings, nor are super-linear lower bounds. Regarding the state of upper bounds, we’ve seen that even the bound we have, while apparently weak (in that it grows quickly with the T-depth), is powerful enough to resolve a long-standing open problem in communication complexity. So maybe us NLQC practitioners can hold our heads a bit higher. 

As well, I can happily report that we have solved at least one of the most embarrassing open problems about NLQC! A very simple question we didn’t know the answer to just a few years ago was the entanglement cost of a CNOT gate — the very simplest non-trivial operation in this context. Now, we have a lower bound of 1 on the entanglement of formation of any state, mixed or pure, that is used to implement a CNOT in the NLQC model. This matches the known 1 EPR pair upper bound. For this beautiful little fact we owe Richard Cleve, who asked me about the CNOT gate and continued to poke at the problem and eventually devised the proof strategy, long after I’d gotten distracted with other things (upon stepping back in my role was mostly to formalize and refine the proof). Generalizing the technique, we also were able to give a technique for proving entanglement lower bounds in the NLQC model for unitaries (this improves on the previous situation, where baroque lower bound strategies were devised for each operation separately). 

So we’ve come a long way, but I still feel the biggest open problems are standing. 

Recently, I visited UT Austin and caught up with the inimitable Scott Aaronson, who was keen to chat about NLQC and the connection to AdS/CFT that started me on the subject. In particular, he was asking about a tension that has motivated a lot of my work here, but which I (perhaps unfortunately) had largely delegated to some back shelf of my mind. Scott’s enthusiasm quickly got me thinking about the problem again though.

To describe the tension here, let me say a little bit more about the connection between AdS/CFT and NLQC. AdS/CFT says that two apparently very different theories are secretly equivalent. One theory lives in a special kind of spacetime called an AdS spacetime, has d+1 dimensions, and includes gravity. The other theory lives in a fixed, non-gravitational, spacetime and involves only quantum mechanics. The puzzle of AdS/CFT is to understand how physics in higher dimensions with gravity can be reproduced by a non-gravitational, lower dimensional theory. 

The connection to NLQC is this: interactions that happen in the AdS bulk are reproduced as NLQC’s in the CFT. 

Back when we first found this connection, we realized there would be an interesting implication for how the geometry of AdS needed to relate to entanglement in the CFT: since NLQC’s require entanglement, the boundary would need entanglement in the right places to support the bulk interactions. We were able to verify this, with a rigorous gravity proof that the entanglement would be there whenever NLQC said it ought to be, which we encapsulated in a theorem we called the connected wedge theorem.

Pushing this connection further, we realized that gravity seemed to be telling us something remarkable about NLQC. In particular, consider a subregion with some size in the bulk, which we will characterize in terms of its area, A. The NLQC – AdS/CFT story indicates that whatever computations happen in this region get reproduced in the CFT as NLQC’s, using entanglement that also turns out to be of order A. This is the basic reasoning that leads to the connected wedge theorem. But this is saying something else as well: we might expect we could implement, for instance, polynomially complex computations inside this region, where polynomially complex means polynomial in the size of the region, A. This seems reasonable, and in line with our expectations of how computations work in the real world. But then we’ve reached an apparently unreasonable conclusion – that we should be able to do computations of complexity poly(A), using poly(A) entanglement! 

Poly entanglement for polynomially complex operations is much stronger than the state of the art in NLQC upper bounds. In the context of implementing unitaries, the best we can do is the exponential-in-the-T-depth upper bound I mentioned earlier. For an example called f-routing, which amounts essentially to computing a Boolean function f, the best we can do (roughly) is compute polynomial-sized formulas, a far cry from polynomial-sized circuits. 

So what is going on? There seem to be two options: 1) There exist much more efficient NLQC protocols than have so far been discovered or 2) something funny is happening in holographic AdS spacetimes, wherein polynomial-sized computations cannot be implemented in polynomial-sized regions. In the second option, computation works much differently in holographic AdS spacetimes than in our world, which would suggest these may not be as good models of quantum gravity as we thought. 

So which is it? That question drove my entry into the study of NLQC, but it’s been a few years since I seriously considered it. I’m not sure I have too much new to say about it, except to make a few observations based on what we’ve learned over the last few years. I think these observations can reasonably be interpreted as hints that option 1) is where things may eventually fall (though my confidence in either outcome remains small).

The first hint comes from the study of classical analogues of NLQC, and in particular the conditional  disclosure of secrets primitive, which is related to f-routing. Using the connection between CDS and f-routing, we understood that all examples of f-routing can be implemented using sub-exponential entanglement. That came as a pretty big surprise – the expectation there was that for the worst-case functions the cost would be exponential. But that expectation was wrong, and a remarkable and mathematically sophisticated protocol (from the CDS literature) beat those expectations. So, if we were wrong about f-routing, and there were deeply hidden, surprising protocols that lowered entanglement cost dramatically, maybe something like that could happen again with entanglement cost for more general protocols. I wouldn’t expect sub-exponential costs in the worst case for general unitaries, but polynomial entanglement for polynomially complex operations doesn’t sound so crazy from this standpoint. 

A second hint, also from the CDS literature, is that for some Boolean functions f with high complexity (cryptographic functions that are strongly expected to be outside of P, but inside BQP), we can construct polynomial entanglement cost NLQC protocols. This is one small data point, since we only know a handful of such functions, but it does say that the formula size upper bounds on entanglement cost for Boolean functions are not the end of the story. Maybe these are just isolated cases that happen to have low cost, but it makes it a little bit more plausible to me that there could be a circuit-size based upper bound for the Boolean function case, consistent with the AdS/CFT driven expectation. 

Let me offer one more small observation in favor of 1). In the study of (classical) circuit lower bounds, the best anyone can do is get a linear bound. Getting past that barrier seems to be very difficult. This is similar to the status in NLQC, where the best we can do is get a linear entanglement lower bound. I have wondered if the reason we can’t beat the linear entanglement lower bound is actually because there is a circuit upper bound, in which case a super-linear entanglement lower bound would imply a super-linear circuit lower bound, and hence be something we wouldn’t expect to prove any time soon. 

Of course all of these are admittedly shaky arguments, and reasonable people can disagree. 

In any case, the tension between AdS/CFT and the current status of NLQC is fascinating, and, perhaps more importantly, useful – it led me to the problem, and in fact seeded the initial ideas for some of the developments I’ve contributed there. For instance, the geometrical perspective on NLQC offered by AdS/CFT led me and my collaborators to see the connection between NLQC and classical information-theoretic cryptography. It also led me to consider the role of error-correction in NLQC, eventually leading to new upper bound strategies. Both of these are solid, useful, things we now know about quantum information theory, neither of which requires that you believe in AdS/CFT – the gravity connection was the catalyst, but the results stand on their own. 

So even if we don’t get to resolve this tension anytime soon, I hope it’ll keep leading to new insights into NLQC and its many applications.