2012/07/31 by Paul Pham, Krysta M. Svore · 1 citation
Physics and Astronomy · Computer Science · #quant-ph #cs.DS #cs.ET
published as Quantum Information & Computation 13(11 & 12): 937-962(2013) · 29 pages, 14 figures, 3 tables, presented at Reversible Computation Workshop 2012 in Copenhagen. Updated with numerical circuit resource upper bounds and constant-depth quantum unfanout
arxiv created 2013/04/22 · arxiv updated 2013/04/23
We contribute a 2D nearest-neighbor quantum architecture for Shor's algorithm to factor an n-bit number in O(log2(n)) depth. Our implementation uses parallel phase estimation, constant-depth fanout and teleportation, and constant-depth carry-save modular addition. We derive upper bounds on the circuit resources of our architecture under a new 2D nearest-neighbor model which allows a classical controller and parallel, communicating modules. We also contribute a novel constant-depth circuit for unbounded quantum unfanout in our new model. Finally, we provide a comparison to all previous nearest-neighbor factoring implementations. Our circuit results in an exponential improvement in nearest-neighbor circuit depth at the cost of a polynomial increase in circuit size and width.