A complexity theory for non-local quantum computation

Andreas Bluhm; Simon Höfer; Alex May; Mikka Stasiuk; Philip Verduyn Lunel; Henry Yuen

doi:10.22331/q-2026-07-01-2152

A complexity theory for non-local quantum computation

Andreas Bluhm¹, Simon Höfer¹, Alex May^2,3, Mikka Stasiuk², Philip Verduyn Lunel⁴, and Henry Yuen⁵

¹Univ. Grenoble Alpes, CNRS, Grenoble INP, LIG
²Perimeter Institute for Theoretical Physics
³Institute for Quantum Computing, Waterloo, Ontario
⁴Sorbonne Université, Paris
⁵Columbia University

Published:	2026-07-01, volume 10, page 2152
Editor:	Aleksandrs Belovs
Eprint:	arXiv:2505.23893v3
Doi:	https://doi.org/10.22331/q-2026-07-01-2152
Citation:	Quantum 10, 2152 (2026).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

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$-measure and $f$-route, the two best studied NLQC tasks, are in fact equivalent under $O(1)$ overhead reductions. This result simplifies many existing proofs in the literature and extends several new properties to $f$-measure. For instance, we obtain sub-exponential upper bounds on $f$-measure for all functions, and efficient protocols for functions in the complexity class $\mathsf{Mod}_k\mathsf{L}$. Beyond this, we study a number of other examples of NLQC tasks and their relationships.

► BibTeX data

@article{Bluhm2026complexitytheorynon,
  doi = {10.22331/q-2026-07-01-2152},
  url = {https://doi.org/10.22331/q-2026-07-01-2152},
  title = {A complexity theory for non-local quantum computation},
  author = {Bluhm, Andreas and H{\"{o}}fer, Simon and May, Alex and Stasiuk, Mikka and Verduyn Lunel, Philip and Yuen, Henry},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {10},
  pages = {2152},
  month = jul,
  year = {2026}
}

► 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—Atomic, Molecular, and Optical Physics, 84 (1): 012326, 2011. https://doi.org/10.1103/PhysRevA.84.012326.
https://doi.org/10.1103/PhysRevA.84.012326

[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. https://doi.org/10.1137/130913687.
https://doi.org/10.1137/130913687

[3] Alex May. Quantum tasks in holography. Journal of High Energy Physics, 2019 (10): 1–39, 2019. https://doi.org/10.1007/JHEP10(2019)233.
https://doi.org/10.1007/JHEP10(2019)233

[4] Alex May, Geoff Penington, and Jonathan Sorce. Holographic scattering requires a connected entanglement wedge. Journal of High Energy Physics, 2020 (8): 1–34, 2020. https://doi.org/10.1007/JHEP08(2020)132.
https://doi.org/10.1007/JHEP08(2020)132

[5] Alex May. Complexity and entanglement in non-local computation and holography. Quantum, 6: 864, 2022. https://doi.org/10.22331/q-2022-11-28-864.
https://doi.org/10.22331/q-2022-11-28-864

[6] Aleksander M Kubicki, Alex May, and David Pérez-Garcia. Constraints on physical computers in holographic spacetimes. SciPost Physics, 16 (1): 024, 2024. https://doi.org/10.21468/SciPostPhys.16.1.024.
https://doi.org/10.21468/SciPostPhys.16.1.024

[7] 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. https://doi.org/10.22331/q-2024-06-27-1387.
https://doi.org/10.22331/q-2024-06-27-1387

[8] Vahid R Asadi, Kohdai Kuroiwa, Debbie Leung, Alex May, Sabrina Pasterski, and Chris Waddell. Conditional disclosure of secrets with quantum resources. arXiv preprint arXiv:2404.14491, 2024. https://doi.org/10.22331/q-2025-10-16-1885.
https://doi.org/10.22331/q-2025-10-16-1885
arXiv:2404.14491

[9] Uma Girish, Alex May, Leo Orshansky, and Chris Waddell. Comparing classical and quantum conditional disclosure of secrets. Quantum, 10: 2049, April 2026. ISSN 2521-327X. 10.22331/q-2026-04-01-2049. URL https://doi.org/10.22331/q-2026-04-01-2049.
https://doi.org/10.22331/q-2026-04-01-2049

[10] 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. https://doi.org/10.1007/978-981-96-0947-5_5.
https://doi.org/10.1007/978-981-96-0947-5_5

[11] 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. https://doi.org/10.1007/JHEP08(2024)152.
https://doi.org/10.1007/JHEP08(2024)152
arXiv:2401.09058

[12] Harry Buhrman, Serge Fehr, Christian Schaffner, and Florian Speelman. The garden-hose model. In Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, pages 145–158, 2013. https://doi.org/10.1145/2422436.2422455.
https://doi.org/10.1145/2422436.2422455

[13] Joy Cree and Alex May. Code-routing: a new attack on position verification. Quantum, 7: 1079, 2023. https://doi.org/10.22331/q-2023-08-09-1079.
https://doi.org/10.22331/q-2023-08-09-1079

[14] 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. 10.1088/1367-2630/13/9/093036.
https://doi.org/10.1088/1367-2630/13/9/093036

[15] 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. 10.1088/1367-2630/15/10/103002.
https://doi.org/10.1088/1367-2630/15/10/103002

[16] 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, 2022a. https://doi.org/10.1038/s41567-022-01577-0.
https://doi.org/10.1038/s41567-022-01577-0

[17] Alvin Gonzales and Eric Chitambar. Bounds on instantaneous nonlocal quantum computation. IEEE Transactions on Information Theory, 66 (5): 2951–2963, 2019. 10.1109/TIT.2019.2950190.
https://doi.org/10.1109/TIT.2019.2950190

[18] Vahid Asadi, Richard Cleve, Eric Culf, and Alex May. Linear gate bounds against natural functions for position-verification. Quantum, 9: 1604, 2025a. https://doi.org/10.22331/q-2025-01-21-1604.
https://doi.org/10.22331/q-2025-01-21-1604

[19] Vahid R. Asadi, Eric Culf, and Alex May. Rank Lower Bounds on Non-Local Quantum Computation. In Raghu Meka, editor, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025), volume 325 of Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1–11:18, Dagstuhl, Germany, 2025b. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 978-3-95977-361-4. 10.4230/LIPIcs.ITCS.2025.11. URL https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.11.
https://doi.org/10.4230/LIPIcs.ITCS.2025.11

[20] Yael Gertner, Yuval Ishai, Eyal Kushilevitz, and Tal Malkin. Protecting data privacy in private information retrieval schemes. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pages 151–160, 1998. 10.1006/jcss.1999.1689.
https://doi.org/10.1006/jcss.1999.1689

[21] Yuval Ishai and Eyal Kushilevitz. Private simultaneous messages protocols with applications. In Proceedings of the 5th Israeli Symposium on Theory of Computing and Systems, pages 174–183. IEEE, 1997. 10.1109/ISTCS.1997.595170.
https://doi.org/10.1109/ISTCS.1997.595170

[22] Andreas Bluhm, Matthias Christandl, and Florian Speelman. A single-qubit position verification protocol that is secure against multi-qubit attacks. Nature Physics, 18 (6): 623–626, 2022b. https://doi.org/10.1038/s41567-022-01577-0.
https://doi.org/10.1038/s41567-022-01577-0

[23] Llorenç Escolà-Farràs and Florian Speelman. Quantum position verification in one shot: parallel repetition of the $ f $-BB84 and $ f $-routing protocols. arXiv preprint arXiv:2503.09544, 2025. https://doi.org/10.48550/arXiv.2503.09544.
https://doi.org/10.48550/arXiv.2503.09544
arXiv:2503.09544

[24] Rene Allerstorfer, Andreas Bluhm, Harry Buhrman, Matthias Christandl, Llorenç Escolà-Farràs, Florian Speelman, and Philip Verduyn Lunel. Making existing quantum position verification protocols secure against arbitrary transmission loss. Physical Review Letters, 135 (26): 260801, 2025. https://doi.org/10.1103/szwj-s7r6.
https://doi.org/10.1103/szwj-s7r6

[25] Hoi-Kwan Lau and Hoi-Kwong Lo. Insecurity of position-based quantum-cryptography protocols against entanglement attacks. Physical Review A—Atomic, Molecular, and Optical Physics, 83 (1): 012322, 2011. https://doi.org/10.1103/PhysRevA.83.012322.
https://doi.org/10.1103/PhysRevA.83.012322

[26] Scott Aaronson, Yosi Atia, and Leonard Susskind. On the hardness of detecting macroscopic superpositions. arXiv preprint arXiv:2009.07450, 2020. https://doi.org/10.48550/arXiv.2009.07450.
https://doi.org/10.48550/arXiv.2009.07450
arXiv:2009.07450

[27] Alexei Yu Kitaev, Alexander Shen, and Mikhail N Vyalyi. Classical and quantum computation, volume 47 of Graduate Studies in Mathematics. American Mathematical Society, 2002. http://doi.org/10.1090/gsm/047.
https://doi.org/10.1090/gsm/047

[28] Mark M Wilde. Quantum information theory. Cambridge University Press, 2013. http://doi.org/10.1017/9781316809976.
https://doi.org/10.1017/9781316809976

[29] Joseph M Renes and Jean-Christian Boileau. Conjectured strong complementary information tradeoff. Physical Review Letters, 103 (2): 020402, 2009. https://doi.org/10.1103/PhysRevLett.103.020402.
https://doi.org/10.1103/PhysRevLett.103.020402

[30] Mario Berta, Matthias Christandl, Roger Colbeck, Joseph M Renes, and Renato Renner. The uncertainty principle in the presence of quantum memory. Nature Physics, 6 (9): 659–662, 2010. https://doi.org/10.1038/nphys1734.
https://doi.org/10.1038/nphys1734

[31] Marius Junge, Aleksander M Kubicki, Carlos Palazuelos, and David Pérez-García. Geometry of Banach spaces: a new route towards position based cryptography. Communications in Mathematical Physics, 394 (2): 625–678, 2022. https://doi.org/10.1007/s00220-022-04407-9.
https://doi.org/10.1007/s00220-022-04407-9

[32] John Bostanci, Yuval Efron, Tony Metger, Alexander Poremba, Luowen Qian, and Henry Yuen. Unitary Complexity and the Uhlmann Transformation Problem. In Shubhangi Saraf, editor, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026), volume 362 of Leibniz International Proceedings in Informatics (LIPIcs), pages 24:1–24:17, Dagstuhl, Germany, 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 978-3-95977-410-9. 10.4230/LIPIcs.ITCS.2026.24. URL https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.24.
https://doi.org/10.4230/LIPIcs.ITCS.2026.24

[33] Minki Hhan, Tomoyuki Morimae, and Takashi Yamakawa. From the hardness of detecting superpositions to cryptography: Quantum public key encryption and commitments. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 639–667. Springer, 2023. https://doi.org/10.1007/978-3-031-30545-0_22.
https://doi.org/10.1007/978-3-031-30545-0_22

[34] Tomoyuki Morimae, Shogo Yamada, and Takashi Yamakawa. Quantum unpredictability. In International Conference on the Theory and Application of Cryptology and Information Security, pages 3–32. Springer, 2025. https://doi.org/10.1007/978-981-96-0947-5_1.
https://doi.org/10.1007/978-981-96-0947-5_1

[35] Wim van Dam and Patrick Hayden. Universal entanglement transformations without communication. Physical Review A, 67 (6): 060302, 2003. https://doi.org/10.1103/PhysRevA.67.060302.
https://doi.org/10.1103/PhysRevA.67.060302

[36] Léo Colisson Palais, Llorenç Escolà-Farràs, and Florian Speelman. A quantum cloning game with applications to quantum position verification. In 20th Conference on the Theory of Quantum Computation, Communication and Cryptography, 2025. https://doi.org/10.4230/LIPIcs.TQC.2025.2.
https://doi.org/10.4230/LIPIcs.TQC.2025.2

[37] Dominique Unruh. Quantum position verification in the random oracle model. In Advances in Cryptology–CRYPTO 2014: 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part II 34, pages 1–18. Springer, 2014. https://doi.org/10.1007/978-3-662-44381-1_1.
https://doi.org/10.1007/978-3-662-44381-1_1

Cited by

[1] Mohansai Balusu, Gaurav Katoch, Sanhita Parihar, and Shubho R. Roy, "Quantum complexity of nonlocal field theories", Journal of High Energy Physics 2026 3, 162 (2026).

[2] Rene Allerstorfer, Andreas Bluhm, Harry Buhrman, Matthias Christandl, Llorenç Escolà-Farràs, Florian Speelman, and Philip Verduyn Lunel, "Making Existing Quantum Position Verification Protocols Secure Against Arbitrary Transmission Loss", Physical Review Letters 135 26, 260801 (2025).

[3] Vahid R. Asadi, Eric Culf, and Alex May, "Rank lower bounds on non-local quantum computation", arXiv:2402.18647, (2024).

[4] Elena Cáceres, Rafael Carrasco, and Juan F. Pedraza, "Lorentzian threads and nonlocal computation in holography", Physical Review D 113 10, 106024 (2026).

[5] Alex May, "Entanglement cost in non-local quantum computation", arXiv:2605.02840, (2026).

[6] Richard Cleve and Alex May, "Lower bounds on non-local computation from controllable correlation", arXiv:2602.00255, (2026).

[7] Andreas Bluhm, Simon Höfer, Alex May, Florian Speelman, and Philip Verduyn Lunel, "Equivalence of non-local computation tasks beyond Clifford operations", arXiv:2606.26354, (2026).

The above citations are from SAO/NASA ADS (last updated successfully 2026-07-15 13:51:30). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2026-07-15 13:48:02).

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.