A 2D NEAREST-NEIGHBOR QUANTUM ARCHITECTURE FOR FACTORING IN POLYLOGARITHMIC DEPTH

We present a 2D nearest-neighbor quantum architecture for Shor's algorithm to factor an n-bit number in O(log(3) 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 model which allows a classical controller and parallel, communicating modules. 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.