Proceedings - International Symposium on Computer Architecture/Proceedings

Distributed Arithmetic on a Quantum Multicomputer

Rodney Van Meter, Kae Nemoto, William J. Munro, Kohei M. Itoh

Published Jul 21, 2006• 19 citations

Abstract

We evaluate the performance of quantum arithmetic algorithms run on a distributed quantum computer (a quantum multicomputer). We vary the node capacity and I/O capabilities, and the network topology. The tradeoff of choosing between gates executed remotely, through "tele-ported gates" on entangled pairs of qubits (telegate), versus exchanging the relevant qubits via quantum teleportation, then executing the algorithm using local gates (tele-data), is examined. We show that the teledata approach performs better, and that carry-ripple adders perform well when the teleportation block is decomposed so that the key quantum operations can be parallelized. A node size of only a few logical qubits performs adequately provided that the nodes have two transceiver qubits. A linear network topology performs acceptably for a broad range of system sizes and performance parameters. We therefore recommend pursuing small, high-I/O bandwidth nodes and a simple network. Such a machine will run Shor's algorithm for factoring large numbers efficiently

DOI: 10.1109/isca.2006.19

Related papers

Distributed Arithmetic on a Quantum Multicomputer

Rodney Van Meter, Kae Nemoto, William J. Munro +1 more

We evaluate the performance of quantum arithmetic algorithms run on a distributed quantum computer (a quantum multicomputer). We vary the node capacity and I/O capabilities, and the network topology. The tradeoff of choosing between gates executed remotely, through "teleported gates" on entangled pairs of qubits (telegate), versus exchanging the relevant qubits via quantum teleportation, then executing the algorithm using local gates (teledata), is examined. We show that the teledata approach performs better, and that carry-ripple adders perform well when the teleportation block is decomposed so that the key quantum operations can be parallelized. A node size of only a few logical qubits performs adequately provided that the nodes have two transceiver qubits. A linear network topology performs acceptably for a broad range of system sizes and performance parameters. We therefore recommend pursuing small, high-I/O bandwidth nodes and a simple network. Such a machine will run Shor's algorithm for factoring large numbers efficiently.

ACM SIGARCH Computer Architecture NewsMay 1, 200635 citations

Arithmetic on a distributed-memory quantum multicomputer

Rodney Van Meter, W. J. Munro, Kae Nemoto +1 more

We evaluate the performance of quantum arithmetic algorithms run on a distributed quantum computer (a quantum multicomputer). We vary the node capacity and I/O capabilities, and the network topology. The tradeoff of choosing between gates executed remotely, through “teleported gates” on entangled pairs of qubits (telegate), versus exchanging the relevant qubits via quantum teleportation, then executing the algorithm using local gates (teledata), is examined. We show that the teledata approach performs better, and that carry-ripple adders perform well when the teleportation block is decomposed so that the key quantum operations can be parallelized. A node size of only a few logical qubits performs adequately provided that the nodes have two transceiver qubits. A linear network topology performs acceptably for a broad range of system sizes and performance parameters. We therefore recommend pursuing small, high-I/O bandwidth nodes and a simple network. Such a machine will run Shor's algorithm for factoring large numbers efficiently.

arXiv:quant-ph/0607160ACM Journal on Emerging Technologies in Computing SystemsJan 1, 200865 citations

Arithmetic on a Distributed-Memory Quantum Multicomputer

Van Meter, R, Munro, W J, Kae Nemoto +1 more

We evaluate the performance of quantum arithmetic algorithms run on a distributed quantum computer (a quantum multicomputer). We vary the node capacity and I/O capabilities, and the network topology. The tradeoff of choosing between gates executed remotely, through ``teleported gates'' on entangled pairs of qubits (telegate), versus exchanging the relevant qubits via quantum teleportation, then executing the algorithm using local gates (teledata), is examined. We show that the teledata approach performs better, and that carry-ripple adders perform well when the teleportation block is decomposed so that the key quantum operations can be parallelized. A node size of only a few logical qubits performs adequately provided that the nodes have two transceiver qubits. A linear network topology performs acceptably for a broad range of system sizes and performance parameters. We therefore recommend pursuing small, high-I/O bandwidth nodes and a simple network. Such a machine will run Shor's algorithm for factoring large numbers efficiently.

Jul 24, 200651 citations

Architecture of a Quantum Multicomputer

Rodney Van Meter, William J. Munro, Kae Nemoto

We have created the architecture of a quantum multicomputer and analyzed its performance for running Shor’s algorithm for factoring large numbers. In this paper, we combine fault-tolerance techniques with performance goals for our architecture, which uses a linear interconnect and six logical qubits per node. Our performance target of factoring a 1,024-bit number in one month requires teleporting 6.2 logical qubits per second on each link in the system, which translates to 3,300 physical teleportations per second on each link. A qubus-based interconnect generates Bell pairs of intermediate fidelity that must be purified. Starting from a Bell state with fidelity F = 0.638, as a qubus-based cavity QED interconnect might generate with a qubit-to-qubit loss of 3.4dB, about 1.5 million physical entanglement attempts per second are enough to reach this level of performance.

Jan 1, 20070 citations

Communication Links for Distributed Quantum Computation

Rodney Van Meter, Kae Nemoto, William J. Munro

Distributed quantum computation requires quantum operations that act over a distance on error correction-encoded states of logical qubits, such as the transfer of qubits via teleportation. We evaluate the performance of several quantum error correction (QEC) codes and find that teleportation failure rates of one percent or more are tolerable when two levels of the [[23, 1, 7]] code are used. We present an analysis of performing QEC on QEC-encoded states that span two quantum computers, including the creation of distributed logical zeros. The transfer of the individual qubits of a logical state may be multiplexed in time or space, moving serially across a single link or in parallel across multiple links. We show that the performance and reliability penalty for using serial links is small for a broad range of physical parameters, making serial links preferable for a large, distributed quantum multicomputer when engineering difficulties are considered. Such a multicomputer will be able to factor a 1,024-bit number using Shor's algorithm with a high probability of success.

arXiv:quant-ph/0701043IEEE Transactions on ComputersNov 5, 200753 citations

Architecture of a quantum multicomputer optimized for Shor's factoring algorithm

Van Meter, Rodney Doyle, バンミーター +1 more

The quantum multicomputer consists of a large number of small nodes and a qubus interconnect for creating entangled state between the nodes. The primary metric chosen is the performance of such a system on Shor's algorithm for factoring large numbers: specifically, the quantum modular exponentiation step that is the computational bottleneck. This dissertation introduces a number of optimizations for the modular exponentiation. My algorithms reduce the latency, or circuit depth, to complete the modular exponentiation of an n-bit number from O(n^3) to O(n log^2 n) or O(n^2 log n), depending on architecture. Calculations show that these algorithms are one million times and thirteen thousand times faster, when factoring a 6,000-bit number, depending on architecture. Extending to the quantum multicomputer, five different qubus interconnect topologies are considered, and two forms of carry-ripple adder are found to be the fastest for a wide range of performance parameters. The links in the quantum multicomputer are serial; parallel links would provide only very modest improvements in system reliability and performance. Two levels of the Steane [[23,1,7]] error correction code will adequately protect our data for factoring a 1,024-bit number even when the qubit teleportation failure rate is one percent.

Sep 21, 200638 citations