Classical simulability and the significance of modular exponentiation in Shor’s algorithm
- 12 December 2007
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review A
- Vol. 76 (6) , 060302
- https://doi.org/10.1103/physreva.76.060302
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.Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Efficient classical simulation of the approximate quantum Fourier transformPhysical Review A, 2007
- Efficient classical simulation of the quantum Fourier transformNew Journal of Physics, 2007
- Classical simulation versus universality in measurement-based quantum computationPhysical Review A, 2007
- Efficient Classical Simulation of Slightly Entangled Quantum ComputationsPhysical Review Letters, 2003
- On the role of entanglement in quantum-computational speed-upProceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2003
- Semiclassical Fourier Transform for Quantum ComputationPhysical Review Letters, 1996