Linear gate bounds against natural functions for position-verification

A quantum position-verification scheme attempts to verify the spatial location of a prover. The prover is issued a challenge with quantum and classical inputs and must respond with appropriate timings. We consider two well-studied position-verification schemes known as f-routing and f-BB84. Both schemes require an honest prover to locally compute a classical function f of inputs of length n, and manipulate $O(1)$ size quantum systems. Taking f(x,y)=∑ᵢ xᵢ yᵢ to be the inner product function, we prove that a dishonest prover must execute Ω(n) quantum gates or single qubit measurements. Our proof uses a reduction to simultaneous message passing with classical communication and shared entanglement. The scheme is feasible for a prover with polynomial classical resources and $O(1)$ quantum resources, and secure against sub-linear quantum resources.