Efficient Distributed Quantum Computing

Abstract

We provide algorithms for efficiently addressing quantum memory in parallel. These imply that the standard circuit model can be simulated with low overhead by the 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 problems.

Some material rearranged and references added

References in corpus (9)

• Quantum random access memory
• An Elementary Quantum Network of Single Atoms in Optical Cavities
• Architectures for a quantum random access memory
• Quantum Circuit Placement
• Arithmetic on a Distributed-Memory Quantum Multicomputer
• A bridge to lower overhead quantum computation
• Reversible Circuit Optimization via Leaving the Boolean Domain
• Quantum Algorithms for the Triangle Problem
• How significant are the known collision and element distinctness quantum algorithms?