TRADING CLASSICAL FOR QUANTUM COMPUTATION USING INDIRECTION
Rodney Van Meter · 2005
Modular exponentiation is the most expensive portion of Shor’s algorithm. We show that it is possible to reduce the number of quantum modular multiplications necessary by a factor of , at a cost of adding temporary storage space and associated machinery for a table of entries, and performing times as many classical modular multiplications. The storage space may be a quantum-addressable classical memory, or pure quantum memory. With classical computation as much as times as fast as quantum computation, values of from 2 to 30 seem attractive; physically feasible values depend on the implementation of the memory.