  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)=\sum_i x_i y_i$ to be the inner product function, we prove that a
dishonest prover must execute $\Omega(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.
