{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,22]],"date-time":"2025-12-22T14:50:36Z","timestamp":1766415036437,"version":"3.33.0"},"reference-count":29,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T00:00:00Z","timestamp":1737417600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>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 <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>f<\/mml:mi><\/mml:math>-routing and <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>f<\/mml:mi><\/mml:math>-BB84. Both schemes require an honest prover to locally compute a classical function <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>f<\/mml:mi><\/mml:math> of inputs of length <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>n<\/mml:mi><\/mml:math>, and manipulate <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>O<\/mml:mi><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mn>1<\/mml:mn><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math> size quantum systems. We prove the number of quantum gates plus single qubit measurements needed to implement a function <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>f<\/mml:mi><\/mml:math> is lower bounded linearly by the communication complexity of <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>f<\/mml:mi><\/mml:math> in the simultaneous message passing model with shared entanglement. Taking <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>f<\/mml:mi><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mi>x<\/mml:mi><mml:mo>,<\/mml:mo><mml:mi>y<\/mml:mi><mml:mo stretchy=\"false\">)<\/mml:mo><mml:mo>=<\/mml:mo><mml:munder><mml:mo>&amp;#x2211;<\/mml:mo><mml:mi>i<\/mml:mi><\/mml:munder><mml:msub><mml:mi>x<\/mml:mi><mml:mi>i<\/mml:mi><\/mml:msub><mml:msub><mml:mi>y<\/mml:mi><mml:mi>i<\/mml:mi><\/mml:msub><\/mml:math> to be the inner product function, we obtain a <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi mathvariant=\"normal\">&amp;#x03A9;<\/mml:mi><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math> lower bound on quantum gates plus single qubit measurements. The scheme is feasible for a prover with linear classical resources and <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>O<\/mml:mi><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mn>1<\/mml:mn><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math> quantum resources, and secure against sub-linear quantum resources.<\/jats:p>","DOI":"10.22331\/q-2025-01-21-1604","type":"journal-article","created":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T17:47:46Z","timestamp":1737481666000},"page":"1604","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":2,"title":["Linear gate bounds against natural functions for position-verification"],"prefix":"10.22331","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8354-7463","authenticated-orcid":false,"given":"Vahid","family":"Asadi","sequence":"first","affiliation":[{"name":"Institute for Quantum Computing, Waterloo, Ontario"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard","family":"Cleve","sequence":"additional","affiliation":[{"name":"Institute for Quantum Computing, Waterloo, Ontario"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Culf","sequence":"additional","affiliation":[{"name":"Institute for Quantum Computing, Waterloo, Ontario"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4030-5410","authenticated-orcid":false,"given":"Alex","family":"May","sequence":"additional","affiliation":[{"name":"Institute for Quantum Computing, Waterloo, Ontario"},{"name":"Perimeter Institute for Theoretical Physics, Waterloo, Ontario"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2025,1,21]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.48550\/arXiv.2306.16462"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Alex May. Quantum tasks in holography. Journal of High Energy Physics, 2019 (10): 1\u201339, 2019. https:\/\/doi.org\/10.1007\/JHEP10(2019)233.","DOI":"10.1007\/JHEP10(2019)233"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Alex May, Geoff Penington, and Jonathan Sorce. Holographic scattering requires a connected entanglement wedge. Journal of High Energy Physics, 2020 (8): 1\u201334, 2020. https:\/\/doi.org\/10.1007\/JHEP08(2020)132.","DOI":"10.1007\/JHEP08(2020)132"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Alex May. Holographic quantum tasks with input and output regions. Journal of High Energy Physics, 2021 (8): 1\u201324, 2021. https:\/\/doi.org\/10.1007\/JHEP08(2021)055.","DOI":"10.1007\/JHEP08(2021)055"},{"key":"4","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.22331\/q-2022-11-28-864"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Harriet Apel, Toby Cubitt, Patrick Hayden, Tamara Kohler, and David P\u00e9rez-Garc\u00eda. 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.","DOI":"10.48550\/arXiv.2401.09058"},{"key":"6","doi-asserted-by":"crossref","unstructured":"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\u2013157. Springer, 2025.","DOI":"10.1007\/978-981-96-0947-5_5"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Nishanth Chandran, Vipul Goyal, Ryan Moriarty, and Rafail Ostrovsky. Position based cryptography. In Annual International Cryptology Conference, pages 391\u2013407. Springer, 2009. https:\/\/doi.org\/10.1007\/978-3-642-03356-8_23.","DOI":"10.1007\/978-3-642-03356-8_23"},{"key":"8","unstructured":"Adrian P Kent, William J Munro, Timothy P Spiller, and Raymond G Beausoleil. Tagging systems, July 11 2006. US Patent 7,075,438."},{"key":"9","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevA.84.012326"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Robert Malaney. The quantum car. IEEE Wireless Communications Letters, 5 (6): 624\u2013627, 2016. 10.1109\/LWC.2016.2607740.","DOI":"10.1109\/LWC.2016.2607740"},{"key":"11","doi-asserted-by":"publisher","unstructured":"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\u2013178, 2014. https:\/\/doi.org\/10.1137\/130913687.","DOI":"10.1137\/130913687"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Salman Beigi and Robert K\u00f6nig. 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.","DOI":"10.1088\/1367-2630\/13\/9\/093036"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Marco Tomamichel, Serge Fehr, J\u0119drzej 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.","DOI":"10.1088\/1367-2630\/15\/10\/103002"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Andreas Bluhm, Matthias Christandl, and Florian Speelman. A single-qubit position verification protocol that is secure against multi-qubit attacks. Nature Physics, pages 1\u20134, 2022. https:\/\/doi.org\/10.1038\/s41567-022-01577-0.","DOI":"10.1038\/s41567-022-01577-0"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Alvin Gonzales and Eric Chitambar. Bounds on instantaneous nonlocal quantum computation. IEEE Transactions on Information Theory, 66 (5): 2951\u20132963, 2019. 10.1109\/TIT.2019.2950190.","DOI":"10.1109\/TIT.2019.2950190"},{"key":"16","doi-asserted-by":"publisher","unstructured":"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\u2013158, 2013. https:\/\/doi.org\/10.1145\/2422436.2422455.","DOI":"10.1145\/2422436.2422455"},{"key":"17","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.48550\/arXiv.2202.07812"},{"key":"18","doi-asserted-by":"publisher","unstructured":"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\u20139:24, Dagstuhl, Germany, 2016. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik. ISBN 978-3-95977-019-4. 10.4230\/LIPIcs.TQC.2016.9.","DOI":"10.4230\/LIPIcs.TQC.2016.9"},{"key":"19","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevA.92.052304"},{"key":"20","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.48550\/arXiv.2309.10070"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Rene Allerstorfer, Andreas Bluhm, Harry Buhrman, Matthias Christandl, Lloren\u00e7 Escol\u00e0-Farr\u00e0s, 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.","DOI":"10.48550\/arXiv.2312.12614"},{"key":"22","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.48550\/arXiv.2109.07517"},{"key":"23","doi-asserted-by":"publisher","unstructured":"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\u201374. Springer, 1998. https:\/\/doi.org\/10.1007\/3-540-49208-9_4.","DOI":"10.1007\/3-540-49208-9_4"},{"key":"24","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.103.020402"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Andreas Winter. Tight uniform continuity bounds for quantum entropies: conditional entropy, relative entropy distance and energy constraints. Communications in Mathematical Physics, 347: 291\u2013313, 2016. https:\/\/doi.org\/10.1007\/s00220-016-2609-8.","DOI":"10.1007\/s00220-016-2609-8"},{"key":"26","doi-asserted-by":"publisher","unstructured":"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\u2013704, 2002. https:\/\/doi.org\/10.1145\/509907.510007.","DOI":"10.1145\/509907.510007"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Antonio Anna Mele. Introduction to Haar measure tools in quantum information: A beginner&apos;s tutorial. arXiv preprint arXiv:2307.08956, 2023. 10.22331\/q-2024-05-08-1340.","DOI":"10.22331\/q-2024-05-08-1340"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Alexander A Razborov. Quantum communication complexity of symmetric predicates. Izvestiya: Mathematics, 67 (1): 145, 2003. 10.1070\/IM2003v067n01ABEH000422.","DOI":"10.1070\/IM2003v067n01ABEH000422"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-01-21-1604\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T17:47:53Z","timestamp":1737481673000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-01-21-1604\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,21]]},"references-count":29,"URL":"https:\/\/doi.org\/10.22331\/q-2025-01-21-1604","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,21]]},"article-number":"1604"}}