rithm, the second step being the order-finding algorithm, to be considered in the next section. These two steps are critical in the final understanding of Shor's algorithm, and this is why we ought to pay extra attention to the following. While based on lessons from previous chapters with no new conceptual difficulty, the quantum phase estimation and its application to order finding involve a few nontrivial properties and results, which must be fully assimilated at each step of the description. 20.1 Phase estimation Assume a unitary operator U, with eigenstate |u) of dimension L, and of unknown complex eigenvalue No = e2irp. where Q is a real number such that 01, is to be determined through the aforementioned "phase estimation" algorithm. Also assume that we are capable of building a family of controlled-UP operators, where p=20,21,.... 2K-1 is any power of two up to K - 1. The phase-estimation (PE) cir- cuit comes in two stages, which we shall call here "front-end" and "back-end" modules, respectively. The PE front-end module is shown in Fig. 20.1. As we observe, its embod- iment includes an input register of K ancilla qubits |0), and the eigenstate lu), which is an L-qubit. Each of the qubits in the input register is submitted to a Hadamard transform (H), the output of which drives an individual controlled-UP gate, according to the array sequence shown at the bottom of the figure. It is easily established that the output register consists of K qubits of the form |0) +e2i with p =20,21,...,2K-1 and leaves invariant the L-qubit lu), as indicated in Fig. 20.1. The tensor-product output can also be rewritten as a sum of K + L qubits of the form |k) (||u):2 (20.1) with N = 2K. This result, in the summation form, will be used later. We shall now interpret the product form. Recall that Q is a real number, such that <<<< 1. Any such number can be represented in binary form, which is noted Q = 0.414243 OK according to the definition: ==0.010203 (20.2) To show this, consider the effect of a controlled-UP gate, noted CUP,