ch. The following discussion, which can be skipped to keep the focus on this chapter, addresses some fine points about the success probability and the implementation cost of the order-finding algorithm. Suffice it to state that the algorithm efficiently yields the order of N and that the complexity or cost is O(L³), namely, that the answer can be obtained in polynomial time. Discussion (i) Since the above determination of s/r (and hence of r) is only probabilistic, there exists a finite chance that it may fail. As we have seen, the probability of failure is, at most, E, which can be made arbitrarily small through an adequate choice of the control register size, K. Independently of such probability considerations, checking whether or not the determination is successful is immediate: it is only necessary to calculate x mod M and verify that the result is unity. In case of failure, the algorithm may be repeated, with the probability of failing again being, at most, E2. Another possibility of failure (x mod M # 1) is that S and r turn out to have a common factor, or be not co-prime. In this case the continued fraction algorithm yields a multiple of r. Recall that the phase estimation produces an estimate of s/r with S E {0, 1, 2, r 1} being a uniformly distributed random number. There Shor's factorization algorithm is, indeed, a finite chance that S, r is not co-prime. It has been established from theory that the number of primes under a given integer r is at least r/ Inr 4 This means that any positive number less than r, as selected at random, has a probability of at least 1/ Inr of being prime. Therefore, the probability that S, r (0 < S < r, r < N) are co-prime is at least 1/1nr > 1/ In N. Hence, it takes one to implement the phase measurement up to In N times to obtain with reasonably high probability a co-prime pair s', r' for which r' = r. (ii) What is the cost of implementing the order-finding algorithm? Looking at Fig. 20.3, we observe that the corresponding quantum circuit includes (a) K Hadamard gates (HOK)