Linear gate bounds against natural functions for position-verification

Abstract

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. We prove the number of quantum gates plus single qubit measurements needed to implement a function $f$ is lower bounded linearly by the communication complexity of $f$ in the simultaneous message passing model with shared entanglement. Taking $f(x,y)={\sum }_i{x}_i{y}_i$ to be the inner product function, we obtain a $\Omega (n)$ lower bound on quantum gates plus single qubit measurements. The scheme is feasible for a prover with linear classical resources and $O(1)$ quantum resources, and secure against sub-linear quantum resources.

v5 is a polish of v4, correcting typos and some numerical values. v3 contained an error which v4/5 correct