  Instantaneous non-local quantum computation requires multiple parties to
jointly perform a quantum operation, using pre-shared entanglement and a single
round of simultaneous communication. We study this task for its close
connection to position-based quantum cryptography, but it also has natural
applications in the context of foundations of quantum physics and in
distributed computing. The best known general construction for instantaneous
non-local quantum computation requires a pre-shared state which is
exponentially large in the number of qubits involved in the operation, while
efficient constructions are known for very specific cases only.
  We partially close this gap by presenting new schemes for efficient
instantaneous non-local computation of several classes of quantum circuits,
using the Clifford+T gate set. Our main result is a protocol which uses
entanglement exponential in the T-depth of a quantum circuit, able to perform
non-local computation of quantum circuits with a (poly-)logarithmic number of
layers of T gates with quasi-polynomial entanglement. Our proofs combine ideas
from blind and delegated quantum computation with the garden-hose model, a
combinatorial model of communication complexity which was recently introduced
as a tool for studying certain schemes for quantum position verification. As an
application of our results, we also present an efficient attack on a
recently-proposed scheme for position verification by Chakraborty and
Leverrier.
