Many groups of research scientists around the world are trying to build a quantum computer to run algorithms that take advantage of the strange effects of quantum mechanics such as entanglement and superposition. A quantum computer could solve problems in chemistry by simulating many body quantum systems, or break modern cryptographic schemes by quickly factorising large numbers.
Previous research shows that if a quantum algorithm is to offer an exponential speed-up over classical computing, there must be a large entangled state at some point in the computation and it was widely believed that this translates into requiring a single large device.
In a paper published in the Proceedings of the Royal Society A, Dr Steve Brierley of Bristol’s School of Mathematics and colleagues show that, in fact, this is not the case. A network of small quantum computers can implement any quantum algorithm with a small overhead.
The key breakthrough was learning how to efficiently move quantum data between the many sites without causing a collision or destroying the delicate superposition needed in the computation. This allows the different sites to communicate with each other during the computation in much the same way a parallel classical computer would do.
Arxiv – Efficient Distributed Quantum Computing
Abstract
We provide algorithms for efficiently moving and 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 Finding problems.
In classical parallel computing, sorting networks provide an elegant solution to the routing problem and simulation of the parallel RAM model. In this paper, we have demonstrated that they can be applied to quantum computing too. The information about the connectivity of a quantum circuit is available before we run the algorithm (at compile time). Using this classical information we have designed an efficient scheme for routing quantum packets. The application of this data-moving algorithm is to distributed quantum computing. We provide an efficient way of mapping arbitrary unconstrained circuits to limited circuits respecting the locality of a graph.
Our results already apply to nearest neighbour architectures in the case of a circuit that is highly parallel. The case of emulating a circuit with many concurrent operations on a 1D nearest neighbour machine was covered by Hirata et al. The approach is to use the Insertion/Bubble sort to perform all of the operations in O(N) time-steps which compares favorably to performing each gate in turn in O(N2) depth. We put this idea in a general framework applying to any (connected) graph. Along the way we are able to prove that up to polylogarithmic factors, this approach is optimal.
We have shown how the addition of a few long-range (or flying) qubits dramatically increases the power of a distributed quantum computer. Using only O(logN) connections per node enables efficient sorting over the hypercube. A distributed quantum computer with nodes connected according to the hypercube graph would be able to emulate arbitrary quantum circuits with only O(log2 N) overhead. One might expect that a quantum computer requires O(N) connections per node so that each qubit can potentially interact with any other qubit. Our result demonstrates that this is not the case: for a small overhead O(logN) connections suffice.
We have presented a new algorithm for accessing quantum memory in parallel. The algorithm is a modification of the data-moving algorithm used in Sections 2 and 3 but where the destinations are quantum data and no longer restricted to form a permutation.
The algorithm is extremely efficient; it has an overhead that is scarcely larger than any algorithm capable of accessing even a single entry from memory. Theorem 5 implies that N processors can have unrestricted access to a shared quantum memory. It tells us that the quantum parallel RAM and the circuit models are equivalent up to logarithmic factors.
Finally, we demonstrated that the parallel look-up algorithm can be used to optimize existing quantum algorithms. We provided an extension of Grover’s algorithm that efficiently performs multiple simultaneous searches over a physical database, and answered an open problem posed by Grover and Rudolph by demonstrating an improved spacetime trade-off for the Element Distinctness problem. It seems likely that this framework for efficient communication in parallel quantum computing will be a useful subroutine in other memory-intensive quantum algorithms, such as triangle finding, or more generally for frameworks such as learning graphs.
If you liked this article, please give it a quick review on ycombinator or StumbleUpon. Thanks
Brian Wang is a Futurist Thought Leader and a popular Science blogger with 1 million readers per month. His blog Nextbigfuture.com is ranked #1 Science News Blog. It covers many disruptive technology and trends including Space, Robotics, Artificial Intelligence, Medicine, Anti-aging Biotechnology, and Nanotechnology.
Known for identifying cutting edge technologies, he is currently a Co-Founder of a startup and fundraiser for high potential early-stage companies. He is the Head of Research for Allocations for deep technology investments and an Angel Investor at Space Angels.
A frequent speaker at corporations, he has been a TEDx speaker, a Singularity University speaker and guest at numerous interviews for radio and podcasts. He is open to public speaking and advising engagements.