Fast versions of Shor's quantum factoring algorithm

Abstract

We present fast and highly parallelized versions of Shor's algorithm. With a sizable quantum computer it would then be possible to factor numbers with millions of digits. The main algorithm presented here uses FFT-based fast integer multiplication. The quick reader can just read the introduction and the ``Results'' section.

37 pages, LaTeX, 1 figure

Cited by in corpus (25)

• Surface codes: Towards practical large-scale quantum computation
• Addition on a Quantum Computer
• Fast Quantum Modular Exponentiation
• Factoring with Qutrits: Shor's Algorithm on Ternary and Metaplectic Quantum Architectures
• Requirements for fault-tolerant factoring on an atom-optics quantum computer
• Introduction to Quantum Algorithms
• Shor's algorithm on a nearest-neighbor machine
• A quantum primality test with order finding
• Robustness of QMA against witness noise
• Efficient rate-adaptive reconciliation for continuous-variable quantum key distribution
• Shor's discrete logarithm quantum algorithm for elliptic curves
• Efficient Construction of a Control Modular Adder on a Carry-Lookahead Adder Using Relative-phase Toffoli Gates
• Quantum Plain and Carry Look-Ahead Adders
• Towards Large-Scale Quantum Computation
• Circuit for Shor's algorithm using 2n+3 qubits
• Quantum Addition Circuits and Unbounded Fan-Out
• Windowed quantum arithmetic
• CNOT-count optimized quantum circuit of the Shor's algorithm
• Quantum locally linear embedding for nonlinear dimensionality reduction
• Entanglement and its Role in Shor's Algorithm
• Approximate encoded permutations and piecewise quantum adders
• New Approachs to Quantum Computer Simulaton in a Classical Supercomputer
• Classical Control of Large-Scale Quantum Computers
• Programming quantum computers using 3-D puzzles, coffee cups, and doughnuts
• A quantum algorithm for computing the Carmichael function