228
12 Cryptocurrencies
Fig. 12.13 Circuit to determine the binary representation φ = q 1 /2 + q 2 /4 + q 3 /8 of the phase φ
of the eigenstate |u of the operator U
state |u, given by U |u = e
2πiφ
|u. The operator U is controlled by a qubit, which
entangles phase and qubit. Moreover, we assume that the phase is approximated
by φ = q 1 /2 + q 2 /4 + q 3 /8, where q 1 , q 2 , and q 3 provide a binary representation
of φ. Figure 12.13 illustrates the phase-estimation circuit, which consists of three
qubits, initialized to |0, and subsequently put into a superpositioned state with the
Hadamard operators H . The second register describes the eigenstate |u, which experiences a phase shift of e
2πikφ when passing the operator U
k . Entangling with the
controlling qubit causes the phase of the |1 component to acquire the additional
phase factor e
2πikφ . If we now express the phase φ through its binary representation,
we recover the description on the right-hand side in Fig. 12.13. Note that these additional phase factors look exactly like the result of the QFT in Fig. 12.12. Since the
QFT is invertible, we simply patch the circuit from Fig. 12.12, but in reverse order,
onto the right-hand side of Fig. 12.13. Adding measuring gauges to the output then
allows us to recover the bit-pattern that describes the phase φ.
Now we have all the tools available to determine the order r from the beginning of
this section and defined through x
r
= 1 (mod N ) . All we need to do is to construct
a unitary operator U which allows us to translate the search for r to a search for
a phase φ. Let us consider the states |x
k
(mod N ) and the operator U defined by
U |x
k
(mod N ) = |x x
k
(mod N ) = |x
k+1
(mod N ). Guided by the idea that the sum
of all states within one period r repeats itself under the operation of U we realize that
r −1
k=0 |x
k
(mod N ) is an eigenvector of U with eigenvalue 1. Likewise, it is easy to
show that
|u s =
1
√
r
r −1
k=0
e
−2πiks/r
|x
k
(mod N )
(12.41)
is an eigenvector of U with eigenvalue e
2πis/r for all 0 ≤ s ≤ r − 1. Note that the
phase we are looking for is here given as φ = s/r . The problem is that we do
not know r and therefore cannot determine the eigenvector to directly apply the
phase estimation method from the previous paragraph. It turns out, however, that the
sum of the r different |u s adds up to |1, or
1/
√
r
r −1
s=0 |u s = |1, such that we
simply initialize the vector |u for the phase estimation as |1. Running the phase
12 Cryptocurrencies
Fig. 12.13 Circuit to determine the binary representation φ = q 1 /2 + q 2 /4 + q 3 /8 of the phase φ
of the eigenstate |u of the operator U
state |u, given by U |u = e
2πiφ
|u. The operator U is controlled by a qubit, which
entangles phase and qubit. Moreover, we assume that the phase is approximated
by φ = q 1 /2 + q 2 /4 + q 3 /8, where q 1 , q 2 , and q 3 provide a binary representation
of φ. Figure 12.13 illustrates the phase-estimation circuit, which consists of three
qubits, initialized to |0, and subsequently put into a superpositioned state with the
Hadamard operators H . The second register describes the eigenstate |u, which experiences a phase shift of e
2πikφ when passing the operator U
k . Entangling with the
controlling qubit causes the phase of the |1 component to acquire the additional
phase factor e
2πikφ . If we now express the phase φ through its binary representation,
we recover the description on the right-hand side in Fig. 12.13. Note that these additional phase factors look exactly like the result of the QFT in Fig. 12.12. Since the
QFT is invertible, we simply patch the circuit from Fig. 12.12, but in reverse order,
onto the right-hand side of Fig. 12.13. Adding measuring gauges to the output then
allows us to recover the bit-pattern that describes the phase φ.
Now we have all the tools available to determine the order r from the beginning of
this section and defined through x
r
= 1 (mod N ) . All we need to do is to construct
a unitary operator U which allows us to translate the search for r to a search for
a phase φ. Let us consider the states |x
k
(mod N ) and the operator U defined by
U |x
k
(mod N ) = |x x
k
(mod N ) = |x
k+1
(mod N ). Guided by the idea that the sum
of all states within one period r repeats itself under the operation of U we realize that
r −1
k=0 |x
k
(mod N ) is an eigenvector of U with eigenvalue 1. Likewise, it is easy to
show that
|u s =
1
√
r
r −1
k=0
e
−2πiks/r
|x
k
(mod N )
(12.41)
is an eigenvector of U with eigenvalue e
2πis/r for all 0 ≤ s ≤ r − 1. Note that the
phase we are looking for is here given as φ = s/r . The problem is that we do
not know r and therefore cannot determine the eigenvector to directly apply the
phase estimation method from the previous paragraph. It turns out, however, that the
sum of the r different |u s adds up to |1, or
1/
√
r
r −1
s=0 |u s = |1, such that we
simply initialize the vector |u for the phase estimation as |1. Running the phase