A quantum computer doesn’t need to be a single large device but could be built from a network of small parts, new research from the University of Bristol has demonstrated. As a result, building such a computer would be easier to achieve.
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.
We provide algorithms for eﬃciently 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-oﬀ 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 eﬃcient scheme for routing quantum packets. The application of this data-moving algorithm is to distributed quantum computing. We provide an eﬃcient 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 ﬂying) qubits dramatically increases the power of a distributed quantum computer. Using only O(logN) connections per node enables eﬃcient 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 suﬃce.
We have presented a new algorithm for accessing quantum memory in parallel. The algorithm is a modiﬁcation 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 eﬃcient; 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 eﬃciently performs multiple simultaneous searches over a physical database, and answered an open problem posed by Grover and Rudolph by demonstrating an improved spacetime trade-oﬀ for the Element Distinctness problem. It seems likely that this framework for eﬃcient communication in parallel quantum computing will be a useful subroutine in other memory-intensive quantum algorithms, such as triangle ﬁnding, or more generally for frameworks such as learning graphs.