Abstract: Non-local quantum computation (NLQC) is a cheating strategy for position-verification schemes, and is closely related to the AdS/CFT correspondence. Here, we connect NLQC to the wider context of information theoretic cryptography by relating it to a number of other cryptographic primitives. We show one special case of NLQC, known as $f$-routing, is equivalent to the quantum analogue of the conditional disclosure of secrets (CDS) primitive, where by equivalent we mean that a protocol for one task gives a protocol for the other with only small overhead in resource cost. We further consider another special case of NLQC, which we call coherent function evaluation (CFE), and show CFE protocols induce similarly efficient protocols for the private simultaneous message passing (PSM) scenario. By relating position-verification to these cryptographic primitives, a number of results in the information theoretic cryptography literature give new implications for NLQC, and vice versa. For NLQC, we obtain the first sub-exponential upper bounds on the worst case cost of $f$-routing, and the first example of an efficient $f$-routing strategy for a problem believed to be outside $P/poly$. For information theoretic cryptography, we obtain a new lower bound on classical CDS with perfect privacy from the quantum non-deterministic communication complexity. Broadly, our work gives new classical analogues of previously purely quantum settings, and consequently new avenues for quantum and classical cryptography to inform each other.
Bio: Alex May is a junior faculty member at the Perimeter Institute for Theoretical Physics. He did his PhD at the University of British Columbia and a post-doc at Stanford University. He works at the interface of quantum information and quantum gravity, with a focus on connections between the AdS/CFT correspondence and quantum cryptography.