A non-local quantum computation (or NLQC) is a distributed method of performing a quantum computation; the method involves shared entanglement and a single, simultaneous round of communication. NLQC was initially studied as a cheating strategy in the context of quantum position verification, and has since been related to a number of other subjects including computational complexity, aspects of classical information-theoretic cryptography, and the AdS/CFT correspondence, among other subjects.
Introduction
The basic setting for a non-local quantum computation is shown at right. We can view the process as involving two parties, who we refer to as Alice and Bob. In the image Alice is on the left, while Bob is on the right. Their goal is to implement a unitary U A B {\displaystyle U_{AB}} , which acts on the two quantum systems A and B. Alice and Bob share a joint quantum state, which in general may be entangled. Alice holds the quantum system A; Bob holds the quantum system B. In the first round operations, Alice acts on her portion of the entangled state and A, and Bob acts on his end of the entangled system and B. Alice and Bob then exchange quantum communication. Finally, Alice and Bob act on the systems they hold locally again. Non-local quantum computation first appeared in the academic literature in the context of quantum position verification (QPV). In that context, any QPV scheme has a corresponding NLQC, which defines a cheating strategy for that scheme. As a consequence, if every unitary can be implemented as an NLQC, then every QPV scheme can be broken in principle. It was established in a 2014 article that every unitary can be implemented as an NLQC, and hence every QPV scheme can be broken. The protocol given involved using a number of EPR pairs which is doubly-exponential in the input size. Further work has explored reducing this entanglement cost - see entanglement cost below. Other developments in the understanding of NLQC have focussed on its relationships to other subjects .
Connections to other subjects
Quantum position-verification Quantum position-verification was first proposed in a 2006 patent. It subsequently appeared in the academic literature.
Position-verification involves two players, called the prover and the verifier. The verifier sends challenges consisting of quantum or classical messages to the prover. The prover should respond with correct responses to this challenge, and should return the outputs at a correct place and time. If the prover does so, the verifier accepts that the prover is within a certain agreed on spacetime location. A typical set-up is shown at right. One proposed application of QPV is to use location as a method of authenticating a communication channel. In that setting, a parties identity is tied to their physical location. Then, if we can determine where the person we are talking to is located, then we also establish who we are talking to. Examples could include secure bank headquarters or military bases. This is one possible solution to the need for authentication in quantum key distribution protocols. Because every NLQC can be implemented, QPV is not secure without making additional assumptions. A commonly explored setting is to assume the prover has access to a limited amount of quantum entanglement, or has limited access to some other resource. Ideally, the non-local quantum computation (cheating strategy) needs very large resources while the local (honest) strategy is easy. A commonly explored scenario is one where the inputs to the QPV scheme are mostly classical, with only a few qubits of quantum input. The hope is that the honest player can do easy, classical, computations, plus a small quantum operation, while the dishonest prover would need to manipulate large quantum systems. There has been partial progress towards finding practical schemes with these properties. Experimental implementations of QPV schemes have been explored.
The AdS/CFT correspondence In the AdS/CFT correspondence, a d dimensional theory with gravity living in asymptotically anti de Sitter space is described in terms of a d-1 dimensional conformal field theory. Considering the case where d = 2 {\displaystyle d=2} , it was observed in a 2019 paper that local interactions that occur in the AdS space are reproduced in the CFT as non-local quantum computations. This led to the conjecture of a relationship between lightcones in AdS with entanglement in the CFT. Using the Ryu-Takayanagi formula this also relates bulk light cones and bulk extremal surfaces. The resulting geometrical relationship between light cones and extremal surfaces in AdS has been proven.
… excerpt ends here. Continue reading the full article.
