12.10 Quantum Computing
229
Fig. 12.14 Circuit to determine the order r from (12.36). The operator U is constructed to increment the power k of a state |x k (mod N ). The left-hand part of the circuit determines a binary
representation of φ = s/r and the inverse quantum Fourier-transfrom makes the individual qubits
visible on the gauges. See the text for details and for definitions of the symbols
estimation multiple times then produces phases with different ratios s/r , but the
values corresponding to the correct period r show up more often.
Figure 12.14 illustrates the algorithm to find r for N = 15, which requires m =
4 qubits to describe the eigenstate |u that is initialized to |1, as shown on the
bottom left of the figure. The eigenstate |u passes through eight controlled unitary
transformations U
2
j for j = 0, . . . , 7 and the corresponding phase increments 2
j
φ
are entangled with the qubits of the phase-measurement circuit, shown in the upper
part of the figure. In order to obtain an accurate measurement of the phase φ = s/r ,
which is the ratio of two four-bit numbers, we choose 2m = 8 qubits for the phaseestimation circuit, which also explains the number of unitary transformations. The
rest of the phase-estimation circuit is, as before, composed of Hadamard gates, the
inverse QFT, and the measuring gauges to determine the bit-pattern that describes
the phase φ = s/r . Note that φ is given in terms of a fractional binary expansion. In
a final step we therefore have to find a fraction s/r that is close to the measured φ
and has a denominator r
that is smaller than N , which can be done using continued
fraction expansion. Such a value of r
is then a candidate for the period r that
determines the factors of N and thus solves the factoring problem as discussed in the
first paragraph of this section. We emphasize that the number of quantum gates that
are required can be shown to scale with the number of bits m required to describe N
as the m
3 [22]. In contrast, testing all prime numbers smaller than
√
N scales with
2
m/2 and is not feasible for very large numbers.
Note that we need 3m = 12 qubits to factor the four-bit number N = 15. Finding
the factors with a large number of bit, say N = 300 would require a circuit with 900
qubits, which well beyond what is currently feasible. Moreover, the construction
of the controlled-U gates is very difficult and presently poses a limitation to scale
the algorithm to larger m. Presently the largest number factored is 21. So, for the
time being, algorithms such as RSA, appear to be safe. And should more powerful
229
Fig. 12.14 Circuit to determine the order r from (12.36). The operator U is constructed to increment the power k of a state |x k (mod N ). The left-hand part of the circuit determines a binary
representation of φ = s/r and the inverse quantum Fourier-transfrom makes the individual qubits
visible on the gauges. See the text for details and for definitions of the symbols
estimation multiple times then produces phases with different ratios s/r , but the
values corresponding to the correct period r show up more often.
Figure 12.14 illustrates the algorithm to find r for N = 15, which requires m =
4 qubits to describe the eigenstate |u that is initialized to |1, as shown on the
bottom left of the figure. The eigenstate |u passes through eight controlled unitary
transformations U
2
j for j = 0, . . . , 7 and the corresponding phase increments 2
j
φ
are entangled with the qubits of the phase-measurement circuit, shown in the upper
part of the figure. In order to obtain an accurate measurement of the phase φ = s/r ,
which is the ratio of two four-bit numbers, we choose 2m = 8 qubits for the phaseestimation circuit, which also explains the number of unitary transformations. The
rest of the phase-estimation circuit is, as before, composed of Hadamard gates, the
inverse QFT, and the measuring gauges to determine the bit-pattern that describes
the phase φ = s/r . Note that φ is given in terms of a fractional binary expansion. In
a final step we therefore have to find a fraction s/r that is close to the measured φ
and has a denominator r
that is smaller than N , which can be done using continued
fraction expansion. Such a value of r
is then a candidate for the period r that
determines the factors of N and thus solves the factoring problem as discussed in the
first paragraph of this section. We emphasize that the number of quantum gates that
are required can be shown to scale with the number of bits m required to describe N
as the m
3 [22]. In contrast, testing all prime numbers smaller than
√
N scales with
2
m/2 and is not feasible for very large numbers.
Note that we need 3m = 12 qubits to factor the four-bit number N = 15. Finding
the factors with a large number of bit, say N = 300 would require a circuit with 900
qubits, which well beyond what is currently feasible. Moreover, the construction
of the controlled-U gates is very difficult and presently poses a limitation to scale
the algorithm to larger m. Presently the largest number factored is 21. So, for the
time being, algorithms such as RSA, appear to be safe. And should more powerful