) +13)|2) (20.31) +|8)|1) +9/8) + |10>|4) + |11)|2) + (|0)+(4)+18)+...)1) 1/1/1 + (|1)+15)+9)+...) + (|2) +16)+100++ |4) + (|3) |2) The state /V3) in Eq. (20.31) can also be put in the form: 1/3/3 = x |2), (20.32) Shor's factorization algorithm 2047 = M- - 1 2048 = M Figure 20.5 Plot of the distribution p(k) = |akl2 in the definition interval k E [0, M - 1]. =(1)+15)+19)+--- (20.33) U3)=(12)+16)+10)) If at this stage (3 in Fig. 20.3) we perform a measurement of the second register, which is no longer used, Eq. (20.32) shows that we may obtain at random any of the values Z = 1, 8, 4, or 2, with a uniform probability of 1/4. Such a measurement causes the first register to collapse into the corresponding state /u1> , /uz) , /U3), or |u4) with a new normalization factor of 1/4. We could also make the same measurement at 4, namely, after the first register has been submitted to the inverse Fourier transform, FT+, and even further down in the circuit, i.e., after the first register has been measured. Intuitively, the measurement statistics of the second register are not affected by the transformation and measurement of the first register, and the reverse. This principle can be stated as "any quantum wires whose qubits are not measured at the end of a quantum circuit may yet be assumed to be also measured, without affecting any other measurement statistics." It remains a fine point to analyze this principle academically, but here we shall take its validity for granted. Assume, then, that our measurement of the second register would be Z = 8 (any other value giving identical results as the conclusion). Thus, in the first register, the input to the inverse Fourier transform circuit would be |uz). After transformation, the first register output is (20.34) where p(k) = 10kk2 represents the probability distribution of the final measurement of the first register. The detailed computation of the distribution p(k) is given in Appendix S. The resulting distribution is plotted in Fig. 20.5. As we see from the figure, the distribu