Royal Society Publishing

Efficient distributed quantum computing

Robert Beals , Stephen Brierley , Oliver Gray , Aram W. Harrow , Samuel Kutin , Noah Linden , Dan Shepherd , Mark Stather


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.

  • Received November 21, 2012.
  • Accepted January 24, 2013.
View Full Text