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

Preprint

6 June 2007

preprint
Published by arXiv in arXiv

https://doi.org/10.48550/arXiv.0706.0872

Abstract

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

Keywords

MODULAR EXPONENTIATION
CLASSICAL SIMULABILITY
ALGORITHM EFFICIENTLY
EFFICIENTLY SIMULATE
FOURIER TRANSFORM
SHOR'S ALGORITHM
PRODUCT STATE

All Related Versions

Version 1, 2007-06-06, ArXiv
Published version: Physical Review A, 76 (6), 060302.

This publication has 0 references indexed in Scilit: