Non-local quantum computation

This article is an orphan, as no other articles link to it. Please introduce links to this page from related articles. (September 2025)

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,^[1][2] aspects of classical information-theoretic cryptography,^[3] and the AdS/CFT correspondence,^[4] among other subjects.^[5][6]

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 ${\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).^{[7][8][9][10]} 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^[8] 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 .

Quantum position-verification was first proposed in a 2006 patent.^[7] It subsequently appeared in the academic literature.^[9][10]

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.^[11][12] 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.^{[13][14][15][16]}

Experimental implementations of QPV schemes have been explored.^[17]

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 ${\displaystyle d=2}$, it was observed in a 2019 paper^[4] 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.^[18][19]

Conditional disclosure of secrets (CDS)^[20] is a subject in information-theoretic classical cryptography. CDS involves three parties, Alice, Bob and a referee. Alice holds input ${\displaystyle x\in \{0,1\}^{n}}$, Bob holds ${\displaystyle y\in \{0,1\}^{n}}$, and the referee knows both ${\displaystyle x}$ and ${\displaystyle y}$. Additionally, Alice holds a string ${\displaystyle z}$ called the secret. Alice and Bob cannot communicate with one another, but can each send a message to the referee. Given a Boolean function ${\displaystyle f(x,y)}$, the goal is for Alice and Bob's message to reveal the secret if and only if ${\displaystyle f(x,y)=1}$.

CDS is related to an example of NLQC known as ${\displaystyle f}$-routing. In ${\displaystyle f}$-routing, Alice receives a string ${\displaystyle x\in \{0,1\}^{n}}$, Bob receives a string ${\displaystyle y\in \{0,1\}^{n}}$, and Alice receives a small quantum system ${\displaystyle Q}$. This has been studied in the QPV literature as an interesting candidate for secure and practical QPV. In a 2024 paper, it was shown that CDS protocols for a function ${\displaystyle f}$ imply ${\displaystyle f}$-routing protocols for the same function, with the EPR pairs used in the routing protocol upper bounded by the number of random bits used in the CDS protocol. This leads to new, more efficient ${\displaystyle f}$-routing protocols^[3] and new lower bounds on CDS.^[15]

Private simultaneous message passing (PSM)^[21] is a similar setting to CDS, with several applications in classical cryptography. Similar to CDS, PSM is also closely related to an example of NLQC^[3]

The first implementation of general non-local quantum computations used a scheme that relied on quantum teleportation. To implement a unitary acting on ${\displaystyle n}$ qubits, the original protocol uses a number of EPR pairs which grows like ${\displaystyle 2^{2^{\Theta (n)}}}$.^[8] In a 2011 article^[22] this was improved to a single exponential dependence ${\displaystyle 2^{\Theta (n)}}$.

To achieve a singly exponential protocol, a key sub-routine used is the port-teleportation protocol.^[23]

The entanglement cost of implementing a unitary ${\displaystyle U_{AB}}$ has been upper bounded by the circuit complexity of ${\displaystyle U_{AB}}$ two different ways^[1] Consider decomposing ${\displaystyle U}$ into Clifford gates and ${\displaystyle T}$-gates. Let ${\displaystyle k}$ be the minimal number of ${\displaystyle T}$-gates needed in such a decomposition, and let ${\displaystyle n}$ be the number of qubits that ${\displaystyle U}$ acts on. Then the first upper bound is

where ${\displaystyle E(U)}$ is the number of shared maximally entangled pairs of qubits needed to implement ${\displaystyle U}$.

We can also consider the ${\displaystyle T}$-depth of the unitary ${\displaystyle U}$. This is the minimal number of layers of ${\displaystyle T}$ gates, in a circuit that alternates between a layer consisting of an arbitrary Clifford unitary and then a layer of ${\displaystyle T}$-gates on a subset of qubits. Letting ${\displaystyle d}$ be the minimal ${\displaystyle T}$-depth, the second bound is

where again ${\displaystyle E(U)}$ is the number of shared maximally entangled pairs of qubits needed to implement ${\displaystyle U}$.

This article needs additional or more specific categories. Please help out by adding categories to it so that it can be listed with similar articles. (September 2025)