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

Nadav Yoran, Anthony J. Short

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…