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.

arXiv comment4 pages, 2 figures

References in corpus (6)

• Efficient classical simulation of slightly entangled quantum computations
• On the role of entanglement in quantum computational speed-up
• Semiclassical Fourier Transform for Quantum Computation
• 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 (8)

• Quantum interference as a resource for quantum speedup
• Weak Values as Context Dependent Values of Observables and Born's Rule
• Joint weak value for all order coupling using continuous variable and qubit probe
• Interference versus success probability in quantum algorithms with imperfections
• Cat state, sub-Planck structure and weak measurement
• 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