A complexity theory for non-local quantum computation
Andreas Bluhm, Simon Höfer, Alex May, Mikka Stasiuk, Philip Verduyn Lunel, Henry Yuen · 2025
Read A complexity theory for non-local quantum computation by Andreas Bluhm, Simon Höfer, Alex May, Mikka Stasiuk, Philip Verduyn Lunel, Henry Yuen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-23893.txt.
Introduction
Andreas Bluhm and five co-authors build in 2025 a complexity theory for nonlocal quantum computation. In this setting, two separated parties share entanglement and swap one round of messages instead of interacting directly. A full account of its costs has been out of reach, since it would imply major breakthroughs elsewhere in theory.
The authors take an indirect route instead: they compare tasks by showing how one can be reduced to another with little extra cost. Most notably, they prove that the two best-studied tasks, f-measure and f-route, are in fact equal in hardness. This gives the field a firmer map of what is easy and what is hard.
Catalog record
| CREATOR | Andreas Bluhm, Simon Höfer, Alex May, Mikka Stasiuk, Philip Verduyn Lunel, Henry Yuen |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 110 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-23893
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A complexity theory for non-local quantum computation Andreas Bluhm, Simon Höfer, Alex May, Mikka Stasiuk, Philip Verduyn Lunel, Henry Yuen Abstract Non-local quantum computation (NLQC) replaces a local interaction between two systems with a single round of communication and shared entanglement. Despite many partial results, it is known that a characterization of entanglement cost in at least certain NLQC tasks would imply significant breakthroughs in complexity theory. Here, we avoid these obstructions and take an indirect approach to understanding resource requirements in NLQC, which mimics the approach used by complexity theorists: we study the relative hardness of different NLQC tasks by identifying resource efficient reductions between them. Most significantly, we prove that f f -measure and f f -route, the two best studied NLQC tasks, are in fact equivalent under O ( 1 ) O(1) overhead reductions. This result simplifies many existing proofs in the literature and extends several new properties to f f -measure. For instance, we obtain sub-exponential upper bounds on f f -measure for all functions, and efficient protocols for functions in the complexity class 𝖬𝗈𝖽 k 𝖫 \mathsf{Mod}_{k}\mathsf{L} . Beyond this, we study coherently controlled applications of Pauli operators and more general unitaries. We find relationships among coherent protocols, and show the coherently controlled NLQCs imply classically controlled protocols, suggesting they are harder NLQC tasks. \geometry margin=1.5cm 1]Univ. Grenoble Alpes, CNRS, Grenoble INP, LIG 2]Perimeter Institute for Theoretical Physics 3]Institute for Quantum Computing, Waterloo, Ontario 4]Sorbonne Université, Paris 5]Columbia University 1 Introduction A non-local quantum computation (NLQC) replaces a local interaction of two systems with a single round of communication and shared entanglement (see Figure 1 ). Non-local quantum computation has many applications, including to quantum position-verification (QPV) [ 1 , 2 ] , AdS/CFT [ 3 , 4 , 5 , 6 ] , information-theoretic cryptography [ 7 , 8 , 9 ] , uncloneable secret sharing [ 10 ] , and Hamiltonian complexity [ 11 ] . In all these applications, a key quantity of interest is the amount of entanglement necessary to implement a given computation as a NLQC. Despite the need to understand this, a clear and general characterization of the entanglement cost of a NLQC is still lacking. \mathbfcal{N} (a) \mathbfcal{V}^{L} \mathbfcal{V}^{R} \mathbfcal{W}^{R} \mathbfcal{W}^{L} \Psi (b) Figure 1 : (a) Circuit diagram showing the local implementation of a channel \mathbfcal{N} . Physically, systems A and B are brought together spatially and interacted. (b) Circuit diagram showing the form of a non-local quantum computation. \mathbfcal{V}^{L} , \mathbfcal{V}^{R} , \mathbfcal{W}^{L} , and \mathbfcal{W}^{R} are quantum channels. The triangle labelled \Psi represents the shared, in general entangled, resource state. The goal is to simulate the local channel \mathbfcal{N} . There are fundamental obstructions to obtaining a complete understanding of entanglement cost in NLQC. In particular, entanglement cost in certain NLQC tasks can be upper bounded by complexity measures. Consequently, placing lower bounds on entanglement would imply lower bounds on these measures of complexity, which is a notoriously hard problem. For instance, in the context of a specific scheme known as f -route, there is an upper bound on entanglement cost which is exponential in the memory needed to compute the Boolean function f [ 12 ] . Super-polynomial bounds on f -route for a given function f therefore imply super-logarithmic lower bounds on memory. Thus such lower bounds face complexity barriers: a super-polynomial lower bound for a function in \mathsf{P} (poly-time) would separate \mathsf{L} (logspace) and \mathsf{P} , a long-standing problem in complexity theory. 1 1 1 In fact, somewhat more is true: in [ 13 ] an upper bound which is efficient for functions in Mod_{k}L is given, so that a super-polynomial lower bound on f -route for a function in \mathsf{P} would separate Mod_{k}L , which contains L , and P . In this work we take a new approach to elucidating how entanglement cost is determined in non-local quantum computation. We focus on the question: when is one computation harder to implement non-locally than another? To understand this, we study the relationships among different NLQC tasks, looking for reductions among them. Whenever we find that a protocol for implementing a non-local computation A can be transformed, without too much overhead, into a protocol for implementing a computation B , we know that B is no harder than A . By introducing this notion of a reduction we lay the groundwork for a more complete notion of complexity theory for NLQC. Our strategy mimics the study of reductions among computational problems. Indeed, since we face some of the same obstructions that appear in the study of complexity theory, it is natural to adopt a similar strategy. We can also hope to gain many of the same insights. For instance, studying examples and comparing their hardness gives insight into what makes a problem hard or easy as a NLQC. We can also then try to identify the hardest NLQCs, which provide useful candidates for position-based cryptography. Further, by building a scaffolding of examples and relating them to one another, any new NLQC of interest can be related to these problems and some of its properties understood without studying each new example from scratch. Finally, we can hope to gain insight into complexity theory itself via NLQC: since upper bounds for different NLQC tasks are characterized in terms of different complexity measures, we can hope to learn about these complexity measures by studying reductions among the tasks, or even hope to find lower bounds on complexity measures by lower bounding NLQC tasks. Among the many applications of NLQC, our results are most immediately relevant for the understanding of the security of quantum position-verification. We briefly review the relevance of NLQC to QPV here. In a position-verification scheme, the verifier sends the prover quantum and classical systems and asks for a reply at a set of designated spacetime locations. See Figure 2 for a standard set-up in a spacetime with one spatial dimension. Unfortunately, there is no unconditionally secure QPV scheme; the cheating strategy is exactly to implement a non-local quantum computation in order to simulate the actions of an honest player. Since all computations can be implemented in the NLQC form, it follows that QPV is not secure without making further assumptions. c_{1} c_{2} r_{2} r_{1} t x (a) c_{1} c_{2} r_{2} r_{1} \ket{\Psi} (b) Figure 2 : A standard QPV set-up in 1+1 dimensions. Inputs are given at spacetime locations c_{1} , c_{2} . The prover should apply a designated quantum operation to these inputs, then return the outputs to points r_{1} , r_{2} . a) An honest prover enters the designated spacetime region (grey) to apply the needed quantum operation. b) A dishonest prover attempts to reproduce the same operation while acting outside the spacetime region; their actions take the form of a non-local quantum computation. Figure reproduced from [ 3 ] . Rather than look for unconditional security, we can ask if some computations are much easier to implement in the local, honest, form rather than the non-local, dishonest form. Attention has focused on the case where we limit the entanglement shared by Alice and Bob, where the goal is to show that some computation which is reasonably easy