Arithmetic on a Distributed-Memory Quantum Multicomputer

The multiplication of superpositions of numbers is a core operation in many quantum algorithms. The standard method for multiplication (both classical and quantum) has a runtime quadratic in the size of the inputs. Quantum circuits with asymptotically fewer gates have been developed, but generally exhibit large overheads, especially in the number of ancilla qubits. In this work, we introduce a new paradigm for sub-quadratic-time quantum multiplication with zero ancilla qubits...

Commercially impactful quantum algorithms such as quantum chemistry and Shor's algorithm require a number of qubits and gates far beyond the capacity of any existing quantum processor. Distributed architectures, which scale horizontally by networking modules, provide a route to commercial utility and will eventually surpass the capability of any single quantum computing module. Such processors consume remote entanglement distributed between modules to realize distributed quan...

Shor's algorithm is one of the most important quantum algorithm proposed by Peter Shor [Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994, pp. 124--134]. Shor's algorithm can factor a large integer with certain probability and costs polynomial time in the length of the input integer. The key step of Shor's algorithm is the order-finding algorithm. Specifically, given an $L$-bit integer $N$, we first randomly pick an integer $a$ with $gcd(a,N)=1...

Recent experimental advances have demonstrated technologies capable of supporting scalable quantum computation. A critical next step is how to put those technologies together into a scalable, fault-tolerant system that is also feasible. We propose a Quantum Logic Array (QLA) microarchitecture that forms the foundation of such a system. The QLA focuses on the communication resources necessary to efficiently support fault-tolerant computations. We leverage the extensive groundw...

Quantum computers can execute algorithms that dramatically outperform classical computation. As the best-known example, Shor discovered an efficient quantum algorithm for factoring integers, whereas factoring appears to be difficult for classical computers. Understanding what other computational problems can be solved significantly faster using quantum algorithms is one of the major challenges in the theory of quantum computation, and such algorithms motivate the formidable t...

We present a brief survey of results where quantum information processing is useful to solve distributed computation tasks. We describe problems that are impossible to solve using classical resources but that become feasible with the help of quantum mechanics. We also give examples where the use of quantum information significantly reduces the need for communication. The main focus of the survey is on communication complexity but we also address other distributed tasks.

This paper presents a novel approach for minimizing the number of teleportations in Distributed Quantum Computing (DQC) using formal methods. Quantum teleportation plays a major role in communicating quantum information. As such, it is desirable to perform as few teleportations as possible when distributing a quantum algorithm on a network of quantum machines. Contrary to most existing methods which rely on graph-theoretic or heuristic search techniques, we propose a drastica...

For most practical applications, quantum algorithms require large resources in terms of qubit number, much larger than those available with current NISQ processors. With the network and communication functionalities provided by the Quantum Internet, Distributed Quantum Computing (DQC) is considered as a scalable approach for increasing the number of available qubits for computational tasks. For DQC to be effective and efficient, a quantum compiler must find the best partition...

Quantum computers require quantum logic, something fundamentally different to classical Boolean logic. This difference leads to a greater efficiency of quantum computation over its classical counter-part. In this review we explain the basic principles of quantum computation, including the construction of basic gates, and networks. We illustrate the power of quantum algorithms using the simple problem of Deutsch, and explain, again in very simple terms, the well known algorith...

We implement the gate teleportation algorithm for teleporting arbitrary two-qubit Clifford gates and the Toffoli gate within the context of multi-node quantum networks, utilizing the SquidASM quantum network simulator. We show how a gate teleportation scheme can be used to implement gate cutting, which is an important approach to realize large circuits in distributed quantum computing environments. The correction operations in teleportation are automatically constructed for a...