 Figure 20.3 Quantum circuit for order finding. and with the phase Qs = s/r satisfying 0 1. Such eigenstates are defined accord- ing to (20.14) which is left as an easy exercise to prove. Finally, we shall observe that the above-defined eigenstates {|us }) satisfy the properties 1 - 1 (20.15) (20.16) which are also left as easy exercises to prove. The property in Eq. (20.15) is rather convenient, since we do not know how to define the state /us), which is a function of the unknown parameter r to be estimated! Recall, indeed, from the previous section, that if we do not know the eigenstate to input to the phase-estimation circuit, we can still use an eigenstate superposition, here, namely, a known state |1) of some arbitrary qubit dimension L. The nice additional feature is that the coefficients in the superposition correspond to a uniform probability distribution p(s) = = for the register measurement and phase estimation. The next step will show that using |1) as the input to the second register of the phase- estimation circuit yields, as the output of the front-end module, a K superposition of the states |k) x 1xk mod N). The property in Eq. (20.16) then makes it possible by inverse Fourier transform (back-end module) to obtain a fair estimation is of the actual phase Qs = s/r. Let us see now in detail how the state evolves step by step through the phase- estimation circuit, which is represented in Fig. 20.3. We assume that the first, control, and second, target, register sizes are K and L = [log2 N], respectively, with the relation between the two to be specified later on. The controlled-U gates perform the application 20.2 Order finding of operator U, as defined in Eq. (20.12), to the power j = 20,21...2-1=1..K. Consistently, we have for the target qubit |1) (20.17) As seen from Fig. 20.3, the combined register input (1) is (20.18) After passing through the Hadamard gate (2) the state has evolved into³ (20.19) with M = 2K, as a recall. After application of the controlled-Uj gate (3) we obtain the state (20.20)