Implementing Shor's Algorithm

Two papers, one brand new and one I had missed earlier in the year:

• Sandy Kutin's "Shor's algorithm on a nearest-neighbor machine" may clear up some of the lingering details of composing adders into the full modular exponentiation needed for Shor, and offers an elegant, efficient overall algorithm. It also appears to call into question (rightfully) some of the simplifying assumptions I made about data movement to combine intermediate results when you do multiple additions in parallel on a very large nearest-neighbor (what I call NTC) machine. Nearest-neighbor is the worst possible architecture, as far as communication costs are concerned. Analyzing it is important in that it sets a floor for performance, but we all hope that for large machines we aren't really limited to NN. The question is, how much richer can we really make the topology, and what effect will that have on performance?


• Christof Zalka's "Shor's algorithm with fewer (pure) qubits" shows how to do Shor for an n-bit number using only 1.5n qubits. I haven't read anything but the first page, but it looks intriguing.

Both papers are potentially important advances toward realistic, efficient implementations of all quantum algorithms using binary integer arithmetic, not just Shor's algorithm. Without this kind of work, we will never know what kind of machine we actually need to build to meet some given performance goal.

I haven't yet read either paper in detail; both are for tomorrow's plane ride.