Summary
This paper looks at a special kind of coding task called f-routing used in quantum position verification, which checks where things are based on their signals. The authors show that if someone tries to cheat this system using limited quantum computing resources, the function they can mimic must belong to certain classes of problems solvable within specific time or space boundaries. These results put clear mathematical limits on how powerful a quantum attacker’s strategy can be under different computational restrictions. This could help in designing more secure quantum location verification methods by knowing what kinds of attacks are impossible given computational limits.
What this means in practice
- •For quantum security engineers: Establish limits on attacker quantum resource needs to enhance design of secure quantum location verification protocols.
- •For quantum circuit designers: Guide resource allocation by linking quantum circuit complexity to function classes secure against certain quantum attacks.
A theory result. No direct application yet.
Abstract
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 $1-ε$ on every input, implies the following computational bounds on $f$: 1. If the strategies are arbitrary quantum channels, then $f\in\mathrm{QSZK}(\mathrm{poly}(nq))$, where $\mathrm{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 $\mathrm{poly}(T)$). 2. If the strategies are explicit Pauli-sparse unitaries on $q$ qubits that have at most $s$ nonzero Pauli coefficients, then $f\in\mathrm{DTIME}(\mathrm{poly}(nqs))$. 3. If the strategies are Clifford+T circuits using at most $t$ magic gates, then $f\in\mathrm{DTIME}(\mathrm{poly}(nq2^t))$. 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\le\log n$ bound of Bluhm, Christandl, and Speelman (2022) for inner product function $f=\mathrm{IP}$, at the cost of restricting adversarial computation and increasing honest evaluation complexity.