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

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.

Figure 1

The quantum circuit for Shor’s algorithm. The empty triangles on the left side represent the computational basis input state, the shaded triangles on the right represent measurements in the computational basis, and the boxes denoted by $H$ stand for Hadamard gates. The QFT together with the output measurements can be replaced by the semiclassical circuit in Fig. 2.

Figure 2

The semiclassical QFT circuit. The triangles denote measurements in the computational basis and the dashed lines signify the fact that the application of the different single-qubit phase gates (denoted by $P_i$) is conditioned on the outcomes of those measurements.