Shor's algorithm on a nearest-neighbor machine

Abstract

We give a new ``nested adds'' circuit for implementing Shor's algorithm in linear width and quadratic depth on a nearest-neighbor machine. Our circuit combines Draper's transform adder with approximation ideas of Zalka. The transform adder requires small controlled rotations. We also give another version, with slightly larger depth, using only reversible classical gates. We do not know which version will ultimately be cheaper to implement.

11 pages, 1 color figure

References in corpus (6)

• Elementary gates for quantum computation
• A new quantum ripple-carry addition circuit
• Addition on a Quantum Computer
• Fast Quantum Modular Exponentiation
• Fast versions of Shor's quantum factoring algorithm
• Architecture-Dependent Execution Time of Shor's Algorithm

Cited by in corpus (13)

• Toward the first quantum simulation with quantum speedup
• Synthesis and Optimization of Reversible Circuits - A Survey
• Synthesis of Quantum Circuits for Linear Nearest Neighbor Architectures
• Factoring with Qutrits: Shor's Algorithm on Ternary and Metaplectic Quantum Architectures
• Requirements for fault-tolerant factoring on an atom-optics quantum computer
• Low cost quantum circuits for classically intractable instances of the Hamiltonian dynamics simulation problem
• Synthesis of Reversible Functions Beyond Gate Count and Quantum Cost
• High Performance Quantum Modular Multipliers
• Computation at a distance
• Optimal Quantum Circuits for Nearest-Neighbor Architectures
• Advantages of a modular high-level quantum programming framework
• On the Design and Optimization of a Quantum Polynomial-Time Attack on Elliptic Curve Cryptography
• A quantum circuit to find discrete logarithms on ordinary binary elliptic curves in depth O(log^2 n)