APA
(2026). Computational Bounds for f -Routing. Perimeter Institute. https://pirsa.org/26100081
MLA
Computational Bounds for f -Routing. Perimeter Institute, Oct. 14, 2026, https://pirsa.org/26100081
BibTex
@misc{ pirsa_PIRSA:26100081,
doi = {10.48660/26100081},
url = {https://pirsa.org/26100081},
author = {},
keywords = {Quantum Information},
language = {en},
title = {Computational Bounds for f -Routing},
publisher = {Perimeter Institute},
year = {2026},
month = {oct},
note = {PIRSA:26100081 see, \url{https://pirsa.org}}
}
Abstract
The f-routing protocol is a leading candidate for quantum position verification, 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 poly(q), with success probability at least 1 − ε on every input, implies the following computational bounds on f:
1. If the strategies are arbitrary quantum channels, then f ∈ QSZK(poly(nq)), where QSZK(T )
is the class of languages having quantum statistical zero knowledge proofs in which the verifier
runs in time T (and the simulator in time poly(T )).
2. If the strategies are explicit Pauli-sparse unitaries on q qubits that have at most s nonzero Pauli
coefficients, then f ∈ DTIME(poly(nqs)).
3. If the strategies are Clifford+T circuits using at most t magic gates, then f ∈ DTIME(poly(nq2t)).
Time and space hierarchies then yield explicit functions secure against polynomial and even quasipolynomial qubits q under our computational restrictions. These bounds exceed the q ≤ log n bound of [BCS22] for inner product function f = IP, at the cost of restricting adversarial computation and increasing honest evaluation complexity.