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.
1/32

1/32

2/32

2/32

3/32

3/32

4/32

4/32

5/32

5/32

6/32

6/32

7/32

7/32

8/32

8/32

9/32

9/32

10/32

10/32

11/32

11/32

12/32

12/32

13/32

13/32

14/32

14/32

15/32

15/32

16/32

16/32

17/32

17/32

18/32

18/32

19/32

19/32

20/32

20/32

21/32

21/32

22/32

22/32

23/32

23/32

24/32

24/32

25/32

25/32

26/32

26/32

27/32

27/32

28/32

28/32

29/32

29/32

30/32

30/32

31/32

31/32

32/32

32/32