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 2ωentries, and performing 2ω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 1013times as fast as quantum computation, values of ω from 2 to 30 seem attractive; physically feasible values depend on the implementation of the memory.
|Title of host publication||Realizing Controllable Quantum States|
|Subtitle of host publication||Mesoscopic Superconductivity and Spintronics - In the Light of Quantum Computation|
|Publisher||World Scientific Publishing Co.|
|Number of pages||6|
|Publication status||Published - 2005 Jan 1|
ASJC Scopus subject areas
- Physics and Astronomy(all)