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 (Ω(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.