Shor's algorithm on a nearest-neighbor machine

Samuel A. Kutin

Authors on Pith no claims yet

classification 🪐 quant-ph

keywords adderalgorithmcircuitdepthgivemachinenearest-neighborshor

read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Heterogeneous architectures enable a 138x reduction in physical qubit requirements for fault-tolerant quantum computing under detailed accounting
quant-ph 2026-04 unverdicted novelty 6.0

Heterogeneous quantum architectures with task-specific hardware and QEC encodings deliver up to 138x lower physical-qubit overhead than monolithic baselines for fault-tolerant algorithms, including RSA-2048 factoring ...