Quantum information theory: Trading classical for quantum computation using indirection

Research output: Chapter in Book/Report/Conference proceedingChapter


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.

Original languageEnglish
Title of host publicationRealizing Controllable Quantum States
Subtitle of host publicationMesoscopic Superconductivity and Spintronics - In the Light of Quantum Computation
PublisherWorld Scientific Publishing Co.
Number of pages6
ISBN (Electronic)9789812701619
ISBN (Print)9789812564689
Publication statusPublished - 2005 Jan 1

ASJC Scopus subject areas

  • Physics and Astronomy(all)


Dive into the research topics of 'Quantum information theory: Trading classical for quantum computation using indirection'. Together they form a unique fingerprint.

Cite this