The proper choice of q is described in Ref. [10]. The result of the modular exponentiation can be held in an auxiliary register: Measuring the auxiliary register will randomly select one of its values, z = y $^{l}$(mod N ) for some 0 ≤ l < r , and will also filter out from the main register only those values of a for which y a = z . Since the series y $^{a}$(mod N ) is periodic in a with a period r , the values of a that remain will make out an arithmetic progression with a common difference r , and an initial term l . The main register will then be in a state we refer to as the periodic state of q qubits, with period r and shift l (following Ref. [28]): This ends the preprocessing stage of Shor’s algorithm, and here the QFT is applied. In anal- ogy to the discrete Fourier transform (DFT), the QFT is used in order to reveal periodicities in its input [1]. In particular, the amplitudes of the state | ψ q r,l 〉 make out a periodic series, and when the DFT is applied to it, the resulting series can be approximated by a periodic series of the same sort, that is, one in which the indices of the nonzero terms make out an arithmetic progression. In the resulting series, though, the common difference is Q/r , the initial term is zero, and additional phases are added. This can be seen through the exact formula for the resulting series ( y$_{j}$ ) Q − 1 j =0 , given by Since applying the QFT to a quantum state is equivalent to applying the DFT to its ampli- tudes, the action of the QFT on periodic states can be approximately described as: where relative phases are ignored. Within this approximation, the QFT induces two changes in the periodic state, in analogy with the DFT: the period is changed from r to Q/r , and the shift is changed from l to 0 (Fig. 1). This removal of the shift is the crucial effect that makes it possible to extract the period in the next step, in which a measurement is performed. The 6 | ψ q r,l 〉 QF T − − → | ψ q Q/r, 0 〉 , (8) y$_{j}$ = 1 √$_{QA}$ sin ( πjrA/Q ) sin ( πjr/Q ) e − j $_{Q}$2 πi [ l + 1 $_{2}$r ( A − 1) ] . (7) | ψ q r,l 〉 = 1 √$_{A}$ A − 1 ∑ j =0 | l + jr 〉 ; A = ⌈ Q − l r ⌉ . (6) | ψ 〉 = 1 √$_{Q}$ Q − 1 ∑ a =0 | a 〉| y a mod N 〉 . (5)