{"id":"arxiv/2609.40278","url":"https://arxiv.org/abs/2609.40278","tags":["quant-ph","cs.CC"],"score":0,"title":"Computational Bounds for $f$-Routing","domain":"quant-ph","source":"arxiv","authors":["Oren Renard","Nicholas Spooner"],"reviews":0,"subject":"quant-ph","summary":"The $f$-routing protocol is a leading candidate for quantum position verification (Kent, Munro, and Spiller, 2011), but security guarantees for explicit functions remain limited. We prove unconditional resource lower bounds for uniform attackers; our new techniques bypass communication-complexity bounds central to previous works, which are inherently at most linear in the input length. We show that, for input length $n$ and sufficiently small constant $ε>0$, a uniformly generated strategy using $q$ qubits and having description length $\\mathrm{poly}(q)$, with success probability at least…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-30","reactions":{}}