# Fast quantum modular exponentiation

@article{Meter2005FastQM, title={Fast quantum modular exponentiation}, author={Rodney Van Meter and Kohei M. Itoh}, journal={Physical Review A}, year={2005}, volume={71}, pages={052320} }

We present a detailed analysis of the impact on quantum modular exponentiation of architectural features and possible concurrent gate execution. Various arithmetic algorithms are evaluated for execution time, potential concurrency, and space tradeoffs. We find that to exponentia te an n-bit number, for storage space 100n (twenty times the minimum 5n), we can execute modular exponentiation two hundred to seven hundred times faster than optimized versions of the basic algorithms, depending on… Expand

#### Figures and Tables from this paper

#### 160 Citations

High Performance Quantum Modular Multipliers

- Physics, Computer Science
- ArXiv
- 2018

We present a novel set of reversible modular multipliers applicable to quantum computing, derived from three classical techniques: 1) traditional integer division, 2) Montgomery residue arithmetic,… Expand

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

- Mathematics, Physics
- 2006

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… Expand

Constant-optimized quantum circuits for modular multiplication and exponentiation

- Mathematics, Computer Science
- Quantum Inf. Comput.
- 2012

In the context of modular exponentiation, this work offers several constant-factor improvements, as well as an improvement by a constant additive term that is significant for few-qubit circuits arising in ongoing laboratory experiments with Shor's algorithm. Expand

Architectural implications of quantum computing technologies

- Computer Science
- ACM J. Emerg. Technol. Comput. Syst.
- 2006

This article presents a classification scheme for quantum computing technologies that is based on the characteristics most relevant to computer systems architecture and uses this taxonomy to explore architectural implications for common arithmetic circuits, examine the implementation of quantum error correction, and discuss cluster-state quantum computation. Expand

Optimization of quantum computer architecture using a resource-performance simulator

- Computer Science
- 2015 Design, Automation & Test in Europe Conference & Exhibition (DATE)
- 2015

A simulation tool is developed that estimates the performance and resource requirements for running a quantum circuit on various quantum architectures as a function of the underlying DPs and finds that the latency of the adder circuit execution can be adequately eliminated with a small increase in entangling qubits. Expand

Low-depth quantum architectures for factoring

- Mathematics
- 2013

Quantum computing is a new field which combines computer science and quantum physics. Its most famous result, Shor's factoring algorithm, would enable us to one day compromise the widely-used RSA… Expand

Fast quantum modular exponentiation architecture for Shor's factoring algorithm

- Computer Science, Mathematics
- Quantum Inf. Comput.
- 2014

We present a novel and efficient, in terms of circuit depth, design for Shor's quantum factorization algorithm. The circuit effectively utilizes a diverse set of adders based on the Quantum Fourier… Expand

Faster Quantum Number Factoring via Circuit Synthesis

- Physics, Computer Science
- ArXiv
- 2013

A circuit-synthesis procedure exploits spectral properties of multiplication operators and constructs optimized circuits from the traces of the execution of an appropriate GCD algorithm, reducing gate counts and circuit latency by up to 4-5 times. Expand

A Realizable Distributed Ion-Trap Quantum Computer

- Computer Science
- HiPC
- 2006

This work explores the parallelization of modular exponentiation, the substantially dominant portion of Shor's algorithm, on multi-chip ion-trap systems with photon-mediated communication between chips, and indicates that a 1024-bit RSA key can be factored in 13 days given 4300 ions in a multi- chip system. Expand

A logarithmic-depth quantum carry-lookahead adder

- Mathematics, Computer Science
- Quantum Inf. Comput.
- 2006

This work reduces the cost of addition dramatically with only a slight increase in the number of required qubits, and can be used within current modularmultiplication circuits to reduce substantially the run-time of Shor's algorithm. Expand

#### References

SHOWING 1-10 OF 39 REFERENCES

Quantum networks for elementary arithmetic operations.

- Physics, Medicine
- Physical review. A, Atomic, molecular, and optical physics
- 1996

This work provides an explicit construction of quantum networks effecting basic arithmetic operations: from addition to modular exponentiation, and shows that the auxiliary memory required to perform this operation in a reversible way grows linearly with the size of the number to be factorized. Expand

A logarithmic-depth quantum carry-lookahead adder

- Mathematics, Computer Science
- Quantum Inf. Comput.
- 2006

This work reduces the cost of addition dramatically with only a slight increase in the number of required qubits, and can be used within current modularmultiplication circuits to reduce substantially the run-time of Shor's algorithm. Expand

Efficient networks for quantum factoring.

- Physics, Medicine
- Physical review. A, Atomic, molecular, and optical physics
- 1996

The number of memory quantum bits (qubits) and the number of operations required to perform factorization, using the algorithm suggested by Shor are estimated. Expand

Compiling Quantum Circuits using the Palindrome Transform

- Mathematics, Physics
- 2003

The design and optimization of quantum circuits is central to quantum computation. This paper presents new algorithms for compiling arbitrary 2 n ×2 n unitary matrices into efficient circuits of (… Expand

Algorithms for quantum computation: discrete logarithms and factoring

- Mathematics, Computer Science
- Proceedings 35th Annual Symposium on Foundations of Computer Science
- 1994

Las Vegas algorithms for finding discrete logarithms and factoring integers on a quantum computer that take a number of steps which is polynomial in the input size, e.g., the number of digits of the integer to be factored are given. Expand

Quantum Carry-Save Arithmetic

- Physics, Mathematics
- 1998

This paper shows how to design efficient arithmetic elements out of quantum gates using "carry-save" techniques borrowed from classical computer design. This allows bit-parallel evaluation of all the… Expand

Fast versions of Shor's quantum factoring algorithm

- Computer Science, Physics
- 1998

Fast and highly parallelized versions of Shor's algorithm are presented, which with a sizable quantum computer it would then be possible to factor numbers with millions of digits. Expand

Fault-tolerant logical gate networks for Calderbank-Shor-Steane codes

- Physics
- 2005

Fault-tolerant logical operations for qubits encoded by Calderbank-Shor-Steane codes are discussed, with emphasis on methods that apply to codes of high rate, encoding k qubits per block with k>1. It… Expand

Quantum Computation and Quantum Information

- Physics
- 2000

Preface Acknowledgement Nomenclature and notation Part I. Fundamental Concepts: 1. Introduction and overview 2. Introduction to quantum mechanics 3. Introduction to computer science Part II. Quantum… Expand

Addition on a Quantum Computer

- Physics, Mathematics
- 2000

A new method for computing sums on a quantum computer is introduced. This technique uses the quantum Fourier transform and reduces the number of qubits necessary for addition by removing the need for… Expand