2026-07-23T13:57:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22639 2026-04-17T05:31:42Z ddc:004 open_access

Rank Lower Bounds on Non-Local Quantum Computation Asadi, Vahid R. Culf, Eric May, Alex Non-local quantum computation quantum position-verification conditional disclosure of secrets A non-local quantum computation (NLQC) replaces an interaction between two quantum systems with a single simultaneous round of communication and shared entanglement. We study two classes of NLQC, f-routing and f-BB84, which are of relevance to classical information theoretic cryptography and quantum position-verification. We give the first non-trivial lower bounds on entanglement in both settings, but are restricted to lower bounding protocols with perfect correctness. Within this setting, we give a lower bound on the Schmidt rank of any entangled state that completes these tasks for a given function f(x,y) in terms of the rank of a matrix g(x,y) whose entries are zero when f(x,y) = 0, and strictly positive otherwise. This also leads to a lower bound on the Schmidt rank in terms of the non-deterministic quantum communication complexity of f(x,y). Because of a relationship between f-routing and the conditional disclosure of secrets (CDS) primitive studied in information theoretic cryptography, we obtain a new technique for lower bounding the randomness complexity of CDS. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vahid R. Asadi and Eric Culf and Alex May 2025 Is Part Of LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2025.11 urn:nbn:de:0030-drops-226399 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.11 eng https://creativecommons.org/licenses/by/4.0/legalcode