Quantum 2025 – scientific programme
Parts | Days | Selection | Search | Updates | Downloads | Help
TUE: Tuesday Contributed Sessions
TUE 6: Quantum Computing and Communication: Contributed Session I (Algorithms & Theory)
TUE 6.5: Talk
Tuesday, September 9, 2025, 15:15–15:30, ZHG007
A complexity theory for non-local quantum computation — •Simon Höfer1, Andreas Bluhm1, Alex May2,3, Mikka Stasiuk2, Philip Verduyn Lunel4, and Henry Yuen5 — 1Univ. Grenoble Alpes, CNRS, Grenoble INP, LIG — 2Perimeter Institute for Theoretical Physics — 3Institute for Quantum Computing, Waterloo, Ontario — 4Sorbonne Université, Paris — 5Columbia University
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, so we take an indirect approach to understanding resource requirements in NLQC, by studying the relative hardness of different NLQC tasks by identifying resource efficient reductions between them.
Most significantly, we prove that f-measure and f-route, the two best studied NLQC tasks, are in fact equivalent under reductions, with only constant overhead in the entanglement cost, regardless of the function f.
This result simplifies many existing proofs in the literature and extends several new properties to f-measure, such as sub-exponential upper bounds on entanglement cost.
Beyond this, we study a number of other examples of NLQC tasks and their relationships.
Keywords: Quantum Position Verification; Quantum Computation; Non-locality; Complexity