Non-local computation of quantum circuits with small light cones

Abstract

The task of non-local quantum computation requires implementation of a unitary on n qubits between two parties with only one round of communication, ideally with minimal pre-shared entanglement. We introduce a new protocol that makes use of the fact that port-based teleportation costs much less entanglement when done only on a small number of qubits at a time. Whereas previous protocols have entanglement cost independent of the unitary or scaling with its complexity, the cost of the new protocol scales with the non-locality of the unitary. Specifically, it takes the form ∼ n 4 V with V the maximum volume of a past light cone in a circuit implementing the unitary. Thus we can implement unitary circuits with V ∼ O (1) using polynomial entanglement, and those with V ∼ polylog( n ) using quasi-polynomial entanglement. For a general unitary circuit with d layers of k -qubit gates V is at most k d , but if geometric locality is imposed it is at most polynomial in d . We give an explicit class of unitaries for which our protocol’s entanglement cost scales better than any known protocol. We also show that several extensions can be made without signif-icantly affecting the entanglement cost – arbitrary local pre- and post-processing; global Clif-ford pre- and post-processing; and the addition of a polynomial number of auxiliary systems.