interact in a limited way, allowing us to access some global properties of the resulting states. Finding special situations where such a global property is the solution to some computational problem (like the period in Shor’s algorithm is the solution to the factoring problem) is in fact the essence of quantum algorithm design. The role of entanglement in this model of quantum speedup is to allow quantum parallelism to reach its full extent, since product states cover a very small range compared with all possible superpositions [1]. 

To exemplify this model for specific algorithms, one must try to distinguish the role of quantum parallelism and quantum interference in each algorithm. In the case of Shor’s algorithm, a superposition is built in the preprocessing stage, in a manner that does not make use of interference (modular exponentiation is performed on each computational basis state separately). This superposition in fact already contains the desired information (the period), and the QFT is merely needed to extract this information (by canceling the shift). Therefore, it can be argued that the preprocessing stage is where quantum parallelism is used, and the QFT introduces quantum interference. This claim is supported by the fact that the QFT does not increase the entanglement of the register. 

## VII. SUMMARY 

We have shown that periodic states play an important role in Shor’s factoring algorithm and pointed out that this is also true for other quantum algorithms that rely on the QFT. Focusing on entanglement as a necessary resource for quantum speedup, we set as our goal to explain the result presented in Ref. [7], according to which the QFT hardly affects the entanglement of periodic states. For this purpose we analyzed the entanglement of periodic states using the Groverian entanglement measure. We derived an approximated formula for the Groverian entanglement of periodic states and showed evidence to support it. Using this approximated formula, we presented a model that explains the aforementioned result. Finally, we argued that this result and the model that explains it strengthen our understanding as to the source of quantum computational speedup in Shor’s algorithm and in general. 

[1] A. Ekert and R. Jozsa, Phil. Trans. R. Soc. London A 356 , 1769 (1998). 

