  A non-local quantum computation (NLQC) replaces an interaction between two
quantum systems with a single simultaneous round of communication and shared
entanglement. We study two classes of NLQC, $f$-routing and $f$-BB84, which are
of relevance to classical information theoretic cryptography and quantum
position-verification. We give the first non-trivial lower bounds on
entanglement in both settings, but are restricted to lower bounding protocols
with perfect correctness. Within this setting, we give a lower bound on the
Schmidt rank of any entangled state that completes these tasks for a given
function $f(x,y)$ in terms of the rank of a matrix $g(x,y)$ whose entries are
zero when $f(x,y)=0$, and strictly positive otherwise. This also leads to a
lower bound on the Schmidt rank in terms of the non-deterministic quantum
communication complexity of $f(x,y)$. Because of a relationship between
$f$-routing and the conditional disclosure of secrets (CDS) primitive studied
in information theoretic cryptography, we obtain a new technique for lower
bounding the randomness complexity of CDS.
