Classical simulability and the significance of modular exponentiation in Shor's algorithm

Nadav Yoran, Anthony J. Short

Research output: Contribution to journalArticle (Academic Journal)peer-review

7 Citations (Scopus)


We show that a classical algorithm efficiently simulating the modular exponentiation circuit, for certain product state input and for general product measurements at the output, can efficiently simulate Shor's factoring algorithm. This is done by using the notion of the semiclassical Fourier transform due to Griffith and Niu, and further discussed in the context of Shor's algorithm by Browne.

Original languageEnglish
Article number060302
Pages (from-to)-
Number of pages4
JournalPhysical Review A: Atomic, Molecular and Optical Physics
Issue number6
Publication statusPublished - Dec 2007

Cite this