Fast Quantum Modular Exponentiation
arXiv:quant-ph/0408006 · doi:10.1103/PhysRevA.71.052320
Abstract
We present a detailed analysis of the impact on 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 exponentiate 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 architecture, for n=128. Addition on a neighbor-only architecture is limited to O(n) time when non-neighbor architectures can reach O(log n), demonstrating that physical characteristics of a computing device have an important impact on both real-world running time and asymptotic behavior. Our results will help guide experimental implementations of quantum algorithms and devices.
to appear in PRA 71(5); RevTeX, 12 pages, 12 figures; v2 revision is substantial, with new algorithmic variants, much shorter and clearer text, and revised equation formatting
References in corpus (15)
- Quantum Computation with Quantum Dots
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Elementary gates for quantum computation
- Quantum Networks for Elementary Arithmetic Operations
- Quantum oscillations in two coupled charge qubits
- Quantum Logic Gates in Optical Lattices
- A new quantum ripple-carry addition circuit
- An all silicon quantum computer
- Efficient Networks for Quantum Factoring
- Scalable quantum computing with Josephson charge qubits
- Addition on a Quantum Computer
- Fast versions of Shor's quantum factoring algorithm
- Quantum Carry-Save Arithmetic
- Fault-Tolerant Logical Gate Networks for CSS Codes
- Compiling Quantum Circuits using the Palindrome Transform
Cited by in corpus (73)
- Large Scale Modular Quantum Computer Architecture with Atomic Memory and Photonic Interconnects
- How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
- Realization of a scalable Shor algorithm
- Synthesis and Optimization of Reversible Circuits - A Survey
- Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning
- Quantum computational finance: Monte Carlo pricing of financial derivatives
- Quantum Circuit Simplification and Level Compaction
- The Bitter Truth About Quantum Algorithms in the NISQ Era
- Automated optimization of large quantum circuits with continuous parameters
- Novel constructions for the fault-tolerant Toffoli gate
- Layered architecture for quantum computing
- Quantum arithmetic with the Quantum Fourier Transform
- Simulating chemistry efficiently on fault-tolerant quantum computers
- Compiler Design for Distributed Quantum Computing
- Quantum Circuit Placement
- Factoring with Qutrits: Shor's Algorithm on Ternary and Metaplectic Quantum Architectures
- Distributed Quantum Computation Architecture Using Semiconductor Nanophotonics
- Fault-Tolerant High Level Quantum Circuits: Form, Compilation and Description
- Architectural design for a topological cluster state quantum computer
- Requirements for fault-tolerant factoring on an atom-optics quantum computer
- Extracting Success from IBM's 20-Qubit Machines Using Error-Aware Compilation
- Linear-Depth Quantum Circuits for n-qubit Toffoli gates with no Ancilla
- Arithmetic on a Distributed-Memory Quantum Multicomputer
- Communication Links for Distributed Quantum Computation
- Recursive quantum repeater networks
- Resource Requirements for Fault-Tolerant Quantum Simulation: The Transverse Ising Model Ground State
- Shor's algorithm on a nearest-neighbor machine
- T-count optimization and Reed-Muller codes
- Arithmetic Circuits for Multilevel Qudits Based on Quantum Fourier Transform
- Designing a Million-Qubit Quantum Computer Using Resource Performance Simulator
- Reduction of Qubits in Quantum Algorithm for Monte Carlo Simulation by Pseudo-random Number Generator
- Faster Quantum Number Factoring via Circuit Synthesis
- An -depth Quantum Adder on a 2D NTC Quantum Computer Architecture
- Large-Scale Simulation of Shor's Quantum Factoring Algorithm
- Fault-tolerant Operations for Universal Blind Quantum Computation
- Linear and logarithmic time compositions of quantum many-body operators
- High Performance Quantum Modular Multipliers
- A quantum primality test with order finding
- Scaling laws for Shor's algorithm with a banded quantum Fourier transform
- Robustness of QMA against witness noise
- Efficient rate-adaptive reconciliation for continuous-variable quantum key distribution
- Circuit Design for A Measurement-Based Quantum Carry-Lookahead Adder
- A tree tensor network approach to simulating Shor's algorithm
- Quantum state preparation via engineered ancilla resetting
- Tensor-product vs. geometric-product coding
- On the Effect of Quantum Interaction Distance on Quantum Addition Circuits
- Efficient Construction of a Control Modular Adder on a Carry-Lookahead Adder Using Relative-phase Toffoli Gates
- Towards Large-Scale Quantum Computation
- Logic Synthesis for Fault-Tolerant Quantum Computers
- A high-fidelity method for a single-step -bit Toffoli gate in trapped ions
- Shor's factorization algorithm with a single control qubit and imperfections
- Non-Markovian Dynamics of a Single Excitation within Many-Body Dissipative Systems
- Unitary Entanglement Construction in Hierarchical Networks
- Computation at a distance
- Optimal Quantum Circuits for Nearest-Neighbor Architectures
- Effects of imperfections for Shor's factorization algorithm
- Distillation protocols for Fourier states in quantum computing
- Resource-aware System Architecture Model for Implementation of Quantum aided Byzantine Agreement on Quantum Repeater Networks
- Resource Analysis of Low-Overhead Transversal Architectures for Reconfigurable Atom Arrays
- On the Design and Optimization of a Quantum Polynomial-Time Attack on Elliptic Curve Cryptography
- Entanglement and its Role in Shor's Algorithm
- A high-level comparison of state-of-the-art quantum algorithms for breaking asymmetric cryptography
- A Quantum Performance Simulator based on fidelity and fault-path counting
- A quantum algorithm for greatest common divisor problem
- Simplified Factoring Algorithms for Validating Small-Scale Quantum Information Processing Technologies
- Integrated Optical Approach to Trapped Ion Quantum Computation
- Offloading Quantum Computation by Superposition Masking
- Quantum oracles for the finite element method
- Classical Control of Large-Scale Quantum Computers
- Truncated Modular Exponentiation Operators: A Strategy for Quantum Factoring
- A Multilayer Network Approach to Quantum Computing
- Synthesis of Quantum Circuits with an Island Genetic Algorithm
- A quantum algorithm for computing the Carmichael function