Linear gate bounds against natural functions for position-verification

Vahid Asadi; Richard Cleve; Eric Culf; Alex May

doi:10.22331/q-2025-01-21-1604

Linear gate bounds against natural functions for position-verification

Vahid Asadi¹, Richard Cleve¹, Eric Culf¹, and Alex May^1,2

¹Institute for Quantum Computing, Waterloo, Ontario
²Perimeter Institute for Theoretical Physics, Waterloo, Ontario

Published:	2025-01-21, volume 9, page 1604
Editor:	Ulysse Chabaud
Eprint:	arXiv:2402.18648v3
Doi:	https://doi.org/10.22331/q-2025-01-21-1604
Citation:	Quantum 9, 1604 (2025).

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

Updated version: The authors have uploaded version v5 of this work to the arXiv which may contain updates or corrections not contained in the published version v3. The authors left the following comment on the arXiv:

v5 is a polish of v4, correcting typos and some numerical values. v3 contained an error which v4/5 correct

Abstract

A quantum position-verification scheme attempts to verify the spatial location of a prover. The prover is issued a challenge with quantum and classical inputs and must respond with appropriate timings. We consider two well-studied position-verification schemes known as $f$-routing and $f$-BB84. Both schemes require an honest prover to locally compute a classical function $f$ of inputs of length $n$, and manipulate $O(1)$ size quantum systems. We prove the number of quantum gates plus single qubit measurements needed to implement a function $f$ is lower bounded linearly by the communication complexity of $f$ in the simultaneous message passing model with shared entanglement. Taking $f(x,y)=\sum_i x_i y_i$ to be the inner product function, we obtain a $\Omega(n)$ lower bound on quantum gates plus single qubit measurements. The scheme is feasible for a prover with linear classical resources and $O(1)$ quantum resources, and secure against sub-linear quantum resources.

► BibTeX data

@article{Asadi2025lineargatebounds,
  doi = {10.22331/q-2025-01-21-1604},
  url = {https://doi.org/10.22331/q-2025-01-21-1604},
  title = {Linear gate bounds against natural functions for position-verification},
  author = {Asadi, Vahid and Cleve, Richard and Culf, Eric and May, Alex},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1604},
  month = jan,
  year = {2025}
}

► References

[1] Rene Allerstorfer, Harry Buhrman, Alex May, Florian Speelman, and Philip Verduyn Lunel. Relating non-local quantum computation to information theoretic cryptography. arXiv preprint arXiv:2306.16462, 2023a. https://doi.org/10.48550/arXiv.2306.16462.
https://doi.org/10.48550/arXiv.2306.16462
arXiv:2306.16462

[2] 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

[3] 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

[4] Alex May. Holographic quantum tasks with input and output regions. Journal of High Energy Physics, 2021 (8): 1–24, 2021. https://doi.org/10.1007/JHEP08(2021)055.
https://doi.org/10.1007/JHEP08(2021)055

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

[6] 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.48550/arXiv.2401.09058.
https://doi.org/10.48550/arXiv.2401.09058
arXiv:2401.09058

[7] 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.

[8] Nishanth Chandran, Vipul Goyal, Ryan Moriarty, and Rafail Ostrovsky. Position based cryptography. In Annual International Cryptology Conference, pages 391–407. Springer, 2009. https://doi.org/10.1007/978-3-642-03356-8_23.
https://doi.org/10.1007/978-3-642-03356-8_23

[9] Adrian P Kent, William J Munro, Timothy P Spiller, and Raymond G Beausoleil. Tagging systems, July 11 2006. US Patent 7,075,438.

[10] Adrian Kent, William J Munro, and Timothy P Spiller. Quantum tagging: Authenticating location via quantum information and relativistic signaling constraints. Physical Review A, 84 (1): 012326, 2011. https://doi.org/10.1103/PhysRevA.84.012326.
https://doi.org/10.1103/PhysRevA.84.012326

[11] Robert Malaney. The quantum car. IEEE Wireless Communications Letters, 5 (6): 624–627, 2016. 10.1109/LWC.2016.2607740.
https://doi.org/10.1109/LWC.2016.2607740

[12] 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

[13] 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

[14] 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

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

[16] 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

[17] 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

[18] Sam Cree and Alex May. Code-routing: a new attack on position-verification. arXiv preprint arXiv:2202.07812, 2022. https://doi.org/10.48550/arXiv.2202.07812.
https://doi.org/10.48550/arXiv.2202.07812
arXiv:2202.07812

[19] Florian Speelman. Instantaneous Non-Local Computation of Low T-Depth Quantum Circuits. In 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016), volume 61 of Leibniz International Proceedings in Informatics (LIPIcs), pages 9:1–9:24, Dagstuhl, Germany, 2016. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. ISBN 978-3-95977-019-4. 10.4230/LIPIcs.TQC.2016.9.
https://doi.org/10.4230/LIPIcs.TQC.2016.9

[20] Kaushik Chakraborty and Anthony Leverrier. Practical position-based quantum cryptography. Physical Review A, 92 (5): 052304, 2015. https://doi.org/10.1103/PhysRevA.92.052304.
https://doi.org/10.1103/PhysRevA.92.052304

[21] George Cowperthwaite, Adrian Kent, and Damian Pitalua-Garcia. Towards a proof-of-principle experimental demonstration of quantum position verification: working notes. arXiv preprint arXiv:2309.10070, 2023. https://doi.org/10.48550/arXiv.2309.10070.
https://doi.org/10.48550/arXiv.2309.10070
arXiv:2309.10070

[22] 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. arXiv preprint arXiv:2312.12614, 2023b. https://doi.org/10.48550/arXiv.2312.12614.
https://doi.org/10.48550/arXiv.2312.12614
arXiv:2312.12614

[23] Jiahui Liu, Qipeng Liu, and Luowen Qian. Beating classical impossibility of position verification. arXiv preprint arXiv:2109.07517, 2021. https://doi.org/10.48550/arXiv.2109.07517.
https://doi.org/10.48550/arXiv.2109.07517
arXiv:2109.07517

[24] Richard Cleve, Wim Van Dam, Michael Nielsen, and Alain Tapp. Quantum entanglement and the communication complexity of the inner product function. In NASA International Conference on Quantum Computing and Quantum Communications, pages 61–74. Springer, 1998. https://doi.org/10.1007/3-540-49208-9_4.
https://doi.org/10.1007/3-540-49208-9_4

[25] 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

[26] Andreas Winter. Tight uniform continuity bounds for quantum entropies: conditional entropy, relative entropy distance and energy constraints. Communications in Mathematical Physics, 347: 291–313, 2016. https://doi.org/10.1007/s00220-016-2609-8.
https://doi.org/10.1007/s00220-016-2609-8

[27] Ashwin Nayak and Julia Salzman. On communication over an entanglement-assisted quantum channel. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 698–704, 2002. https://doi.org/10.1145/509907.510007.
https://doi.org/10.1145/509907.510007

[28] Antonio Anna Mele. Introduction to Haar measure tools in quantum information: A beginner's tutorial. arXiv preprint arXiv:2307.08956, 2023. 10.22331/q-2024-05-08-1340.
https://doi.org/10.22331/q-2024-05-08-1340
arXiv:2307.08956

[29] Alexander A Razborov. Quantum communication complexity of symmetric predicates. Izvestiya: Mathematics, 67 (1): 145, 2003. 10.1070/IM2003v067n01ABEH000422.
https://doi.org/10.1070/IM2003v067n01ABEH000422

Cited by

[1] Yunkai Wang, Graeme Smith, and Alex May, "Secure Quantum Ranging", Physical Review Letters 135 26, 260802 (2025).

[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] Andreas Bluhm, Simon Höfer, Alex May, Mikka Stasiuk, Philip Verduyn Lunel, and Henry Yuen, "A complexity theory for non-local quantum computation", Quantum 10, 2152 (2026).

[4] Kirsten Kanneworff, Mio Poortvliet, Dirk Bouwmeester, Rene Allerstorfer, Philip Verduyn Lunel, Florian Speelman, Harry Buhrman, Petr Steindl, and Wolfgang Löffler, "Towards experimental demonstration of quantum position verification using single photons", Quantum Science and Technology 10 4, 045004 (2025).

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

[6] Llorenç Escolà-Farràs and Florian Speelman, "Quantum position verification in one shot: parallel repetition of the $f$-BB84 and $f$-routing protocols", arXiv:2503.09544, (2025).

[7] Llorenç Escolà-Farràs, Arpan Akash Ray, Rene Allerstorfer, Boris Škorić, and Florian Speelman, "Continuous-variable quantum position verification secure against entangled attackers", Physical Review A 110 6, 062605 (2024).

[8] Llorenç Escolà-Farràs, Léo Colisson Palais, and Florian Speelman, "A quantum cloning game with applications to quantum position verification", arXiv:2410.22157, (2024).

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

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-12 02:21:34) and SAO/NASA ADS (last updated successfully 2026-08-12 02:21:35). The list may be incomplete as not all publishers provide suitable and complete citation data.

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.