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

4 pages, 2 figures

References in corpus (3)

• Classical simulation versus universality in measurement based quantum computation
• Efficient classical simulation of the semi-classical Quantum Fourier Transform
• Efficient classical simulation of the approximate quantum Fourier transform

Cited by in corpus (5)

• Joint weak value for all order coupling using continuous variable and qubit probe
• Interference versus success probability in quantum algorithms with imperfections
• Understanding the Quantum Computational Speed-up via De-quantisation
• Cooling ultracold bosons in optical lattices by spectral transform
• Simulations of Shor's Algorithm using Matrix Product States