Posted

Andreas Bluhm, Simon Höfer, Alex May, Mikka Stasiuk, Philip Verduyn Lunel, Henry Yuen (Jun 02 2025).
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 ff-measure and ff-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 ff-measure. For instance, we obtain sub-exponential upper bounds on ff-measure for all functions, and efficient protocols for functions in the complexity class ModkL\mathsf{Mod}_k\mathsf{L}. Beyond this, we study a number of other examples of NLQC tasks and their relationships.

Order by:

Want to join this discussion?

Join our community today and start discussing with our members by participating in exciting events, competitions, and challenges. Sign up now to engage with quantum experts!