Efficient distributed quantum computing

TLDR

The authors develop algorithms for efficient parallel quantum memory movement and addressing, apply them to memory‑intensive quantum algorithms, and present a parallel quantum search algorithm that improves time–space trade‑offs for element distinctness and collision finding. They design parallel quantum memory movement and addressing algorithms and a parallel quantum search algorithm that reduces time–space trade‑offs for element distinctness and collision finding. These results show that the standard circuit model can be simulated with low overhead on a realistic distributed quantum computer, enabling algorithm designers to use the circuit model without concern for underlying connectivity.

Abstract

We provide algorithms for efficiently moving and addressing quantum memory in parallel. These imply that the standard circuit model can be simulated with a low overhead by a more realistic model of a distributed quantum computer. As a result, the circuit model can be used by algorithm designers without worrying whether the underlying architecture supports the connectivity of the circuit. In addition, we apply our results to existing memory-intensive quantum algorithms. We present a parallel quantum search algorithm and improve the time–space trade-off for the element distinctness and collision finding problems.