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

Nadav Yoran; Anthony J. Short

doi:10.1103/PhysRevA.76.060302

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

Nadav Yoran, Anthony J. Short

School of Physics

Research output: Contribution to journal › Article (Academic Journal) › peer-review

7 Citations (Scopus)

Abstract

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 language	English
Article number	060302
Pages (from-to)	-
Number of pages	4
Journal	Physical Review A: Atomic, Molecular and Optical Physics
Volume	76
Issue number	6
DOIs	https://doi.org/10.1103/PhysRevA.76.060302
Publication status	Published - Dec 2007

Access to Document

10.1103/PhysRevA.76.060302

Handle.net

Persistent link

Cite this

@article{48c770a6c84e46609c5364e5430ae28b,

title = "Classical simulability and the significance of modular exponentiation in Shor's algorithm",

abstract = "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.",

author = "Nadav Yoran and Short, {Anthony J.}",

year = "2007",

month = dec,

doi = "10.1103/PhysRevA.76.060302",

language = "English",

volume = "76",

pages = "--",

journal = "Physical Review A: Atomic, Molecular and Optical Physics",

issn = "1050-2947",

publisher = "American Physical Society (APS)",

number = "6",

}

TY - JOUR

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

AU - Yoran, Nadav

AU - Short, Anthony J.

PY - 2007/12

Y1 - 2007/12

N2 - 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.

AB - 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.

U2 - 10.1103/PhysRevA.76.060302

DO - 10.1103/PhysRevA.76.060302

M3 - Article (Academic Journal)

SN - 1050-2947

VL - 76

SP - -

JO - Physical Review A: Atomic, Molecular and Optical Physics

JF - Physical Review A: Atomic, Molecular and Optical Physics

IS - 6

M1 - 060302

ER -

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

Abstract

Access to Document

Handle.net

Fingerprint

Cite this