see they show Hide & Seek (blue and red men) OpenAI made, if they add quantum power it will work much deeper.
I wouldn't describe the conjectured result as 'deeper,' but rather 'faster, but just as shallow as before...', assuming that there even exist quantum algorithms that would allow a speed-up in that type of application. I once thought I would try to get ahead in the quantum computing world by coming up with my own algorithms, so I looked at the derivation of Shor's Algorithm and Grover's Algorithm to get a feel for how to devise such algorithms. God, just pages and pages of number theory and probability, no easy way to see the big picture of the rationale or derivation. I quickly gave up, and realized why quantum computers are not going to be the salvation of AI: it is extremely hard to come up with algorithms that will allow speed up, which means mostly we're going to be stuck with existing algorithms and computers for the foreseeable future. You need to be an expert in number theory to make progress in that type of algorithm, and there aren't many such experts around, and never will be, due to the years of heavy mathematical education needed.
----------
(p. 180)
3.3.3 Shor's Algorithm
On pp. 33-34 we presented a kind of "physical calculation" by means of
interference on a Mach-Zehnder interferometer. By using chosen phases
with particular periods, we were able to factor (comparatively small)
numbers in polynomial time. The idea could be seen as a special case
of Peter Shor's quantum algorithm [Shor, 1994; Shor, 1997] for factoring
arbitrary whole numbers in particular, because the latter algorithm is
also based on finding periods of the functions it uses.
Classically, we can relate the problem of factoring numbers and finding
the periods of related functions in the following way. Let us factor the
number N = 15, in particular because it is the first number that has
been factored on a real (NMR) quantum computer in 2001 [Vandersypen
et al., 2001].
We choose another integer a that is relatively prime (coprime) (see
p. 67) to N, i.e., gcd(a,N) = 1, where gcd is the greatest common
divisor. So, a could be any number from the set {2, 4, 7, 8, 11, 13, 14}.
Let us choose a = 13. So, a < N = 15. Next, we consider the powers
of a modulo N as shown in Table 3.1. For example, 13^1 (mod 15) =
Table 3.1. Powers of a modulo N exhibit periodicity. Here, the period (order) is
r = 4, a = 13, N = 15, and f(r) = a^r(mod N).
r 1 2 3 4 5 6 7 8 9 10 11 12 13 14
f(r) 13 4 7 1 13 4 7 1 13 4 7 1 13 4
(p. 181)
remainder of 13/15 = 13, 13^2 (mod 15) = remainder of 169/15 = 4, etc.,
and we get that the period of a^r (mod N) is 4. At the same time, the
period is the smallest power for which we get f(r) = 1, i.e., for which
we have
a^r = 1 (mod N), r smallest. (3.76)
This equality hinges on the fact that a is relatively prime to N--otherwise
we cannot get a remainder of 1. Such smallest r is called the order of a
modulo N. Now, Eq. (3.76) yields
(a^(r/2) - 1)(a^(r/2) + 1) = 0 (mod N) = kN, (3.77)
where k is a nonnegative integer, provided the smallest such r is even as
in our case (r = 4). In the above example we have
(13^2 - 1)(13^2 + 1) = 168 x 170 = 28560 = 1904 x 15. (3.78)
This means that (gcd(168, 15) > 1, gcd(170, 15) > 1), and we can make
use of Euclid's algorithm.
In Eq. (3.77), when neither a^(r/2) - 1 nor a^(r/2) + 1 is a multiple of
N, then--since their product is a multiple of N--the greatest common
denominators of a^(r/2) - 1 and N and of a^(r/2) + 1 and N yield factors of
N in polynomial time by means of Euclid's algorithm. In our example,
gcd(168, 15) = 3 and gcd(1970, 15) = 5.
It can be shown that the probability that r is even and that a^(r/2) +- 1
are not exact multiples of N (as we assumed above) is always >= 1/2
[Ekert and Jozsa, 1996]. After R repetitions of the procedure, the prob-
ability of success in factoring N will be >= 1 - 2^(-R).
Thus, we have arrived at a classical procedure in which the only part
which requires exponential time is determining the smallest period of
f(r), i.e., the order of a modulo N. This is the point where Shor's
quantum procedure--which can treat all r's at once--starts.
We begin with two registers of qubits. The first register, |x>, contains
phase variables x element of {0, 1, 2, ...} and the second one, |f(x)>, the values
of the periodic function f(x + r) = f(x), where r element of {0, 1, 2, ...} is the
unknown least period we want to find.
The initial values of the first and second registers are
first register second register
|Psi1> = |0>|0> = |0>|0> ... |0> |0>|0> ... |0>, (3.79)
n times m times
(p. 182)
where we assume that we have enough qubits to carry out the algorithm,
i.e., that N <= 2^n < 2N^2 (otherwise the period r might not divide 2^n)
and that m is also big enough to provide us with a sufficient number
of states in the second register. We create the superposition by apply-
ing a Hadamard gate to each qubit from the first register as we did in
Eq. (3.6) and as shown in Fig. 3.22:
Hhat^(n)|00...0> = Hhat^(n)|0>|0>...|0> = Hhat|0>Hhat|0>...Hhat|0>
= 1/sqrt(2^n) (|0> + |1>)(|0> + |1>) ... (|0> + |1>)
2^n - 1
= 1/sqrt(2^n) SIGMA |j>, (3.80)
j=0
where |j>, j = 0, ..., 2^(n-1) are defined as
|0> = |0>...|0>, |1> = |0>...|1>, ... |2^(n-1)> = |1>...|1>. (3.81)
n n n
The total function at this stage of our procedure reads
2^n - 1
|Psi2> = 1/sqrt(2^n) SIGMA |j>|0>, (3.82)
j=0
where |0> in the second register means |0>|0>...|0>.
[figure]
Figure 3.22 Period-finding algorithm circuit diagram. (1) First register, n qubits.
(2) Second register, m qubits. Box (3) represents the computation of f(j) (j's are
from the 1st register) carried out in a 3rd register, with the obtained values stored
in the 2nd register; values of the 1st register remain unchanged. Operators U = e^(i phi)
implement the quantum Fourier transform [Eq. (3.86)]--the produce of the relevant
|psi> states given by Eq. (3.88) is equal to it, as follows from Eq. (3.89).
(p. 183)
In our example above (N = 15, a = 13), we can choose n = 4 qubits
(2^4 = 16 > 15) and from Eq. (3.82) we get
|Psi2> = 1/sqrt(2^4) (|0> + |1> + ... + |2^4 - 1>)|0>
= 1/sqrt(2^4) (|0000>|0...0> + |0001>|0...0> + ... + |1111>|0...0>). (3.83)
Next, in a separate, third register, we compute f(j) = a^j (mod N) for
each j from the first register and store their values in the second register.
Thus we obtain
2^n - 1
|Psi3> = 1/sqrt(2^n) SIGMA |j>f(j)>. (3.84)
j=0
This stage of the procedure is denoted by box (3) in Fig. 3.22. In our
case, f(j) is given by the second row of Table 3.1 (except for f(0) =
13^0 (mod 15) = 1), and we have
|Psi3> = 1/sqrt(2^4) (|0>|1> + |1>|13> + |2>|4> + |3>|7> + |4>|1> + |5>|13> ... |15>|7>)
= 1/sqrt(2^4) (|0000>|0001> + |0001>|1101> + |0010>|0100> + |0011>|0111>
+ |0100>|0001> + |0101>|1101> ... |1111>|0111>). (3.85)
Here, we have chosen m = n = 4. The number of qubits in the second
register, m, can be smaller, but the number of states, M has to be big
enough to enable a reliable measurement of the period. For example, in
the experiment mentioned above, three qubits (m = 3) were put in the
second register [Vandersypen et al., 2001].
To find the period r of our function f, we apply a quantum Fourier
transform on each state from the first register, because it turns out that
for phases inversely proportional to the period (r) we have constructive
interference and for all the other phases destructive interference. The
quantum Fourier transform on an orthonormal basis |0>, ..., |N - 1> is
defined as the following linear operator:
K-1
|j> -> 1/sqrt(K) SIGMA e^(2 pi i j k / K) |k>. (3.86)
k=0
Thus the function describing the fourth stage of our procedure reads
2^n - 1 2^n - 1
|Psi4> = 1/2^n SIGMA SIGMA e^(2 pi i j k / 2^n) |k>|f(j)>. (3.87)
k=0 j=0
(p. 184)
For each k, the corresponding terms of this function can be implemented
by the quantum circuit shown in Fig. 3.22, where
|psi sub 2^0> = 1/sqrt(2) (|0> + e^(2^(1-n) pi i k) |1>), |psi sub 2^1> = 1/sqrt(2) (|0> + e^(2^(2-n) pi i k) |1>), ...
|psi sub 2^(n-2)> = 1/sqrt(2) (|0> + e^(2^1 pi i k) |1>), |psi sub 2^(n-1)> = 1/sqrt(2) (|0> + e^(2^0) pi i k) |1>), (3.88)
as follows from
(|0> + e^(2^(1-n) pi i k) |1>)(|0> + e^(2^(2-n) pi i k) }1>)
2^n - 1
... (|0> + e^(2^1 pi i k)|1>)(|0> + e^(2^0 pi i k |1>) = SIGMA e^(2 pi i j k / 2^n) |j>. (3.89)
j=0
Now, a measurement of the second register selects all those |f(j)>
that are equal to each other. It singles out the j's of the corresponding
states |j> given by Eq. (3.89). For example, in Eq. (3.85) a detection of
state |13> from the second register singles out |1>, |5>, |9>, and |13> from
the first register, i.e., it selects j = 1, 5, 9, 13. The probability that a
measurement of the first register will confirm that its qubits are in one
of the Fourier states, |k>, follows from Eq. (3.89):
2^n - 1
Pr(k) = 1/2^(2n) |SIGMA e^(2 pi i j k / 2^n)|^2 , for f(j)-selected j's. (3.90)
j=0; sel. j's
Let us estimate this probability, following Shor's reasoning [Shor, 1997].
The j's are either integer multiple [sic] of the period r (see Eq. (3.76)), lr, or,
due to periodicity (see Table 3.1), shifted integer multiples lr+q, where l
and q are nonnegative integers. In our case (see Eq. (3.85)), for instance,
for f(j) = 1 we have j = 0, 4, 8, 12, i.e., j = 4l, l = 0, 1, 2, 3, and for
f(j) = 13 we have j = 1, 5, 9, 13, i.e., j = 4l + q, l = 0, 1, 2, 3, q = 1.
So, let us see what we would get if we knew the period r in advance and
if we assumed that q ~~ 0 (in comparison with 2^n). Then r would divide
2^n exactly and l = j/r in the sum of Eq. (3.90) would range from l = 0
to l = 2^n / (r - 1). The normalization factor in Eq. (3.84) becomes sqrt(r / 2^n).
Thus we can write Eq. (3.90) in the following form:
(2^n / r) - 1 (2^n / r) - 1
Pr(k) = r / 2^(2n) |SIGMA e^(2 pi i (lr+q)k / 2^n)|^2 = r / 2^(2n) |SIGMA e^(2 pi i l r k / 2^n)|^2 . (3.91)
l=0 l=0
If k = 2^ p / r, where p is a nonnegative integer, then Pr(k) = 1/r because
e^(2 pi i l p) = 1 for l, p = 0, 1, 2, .... If not, the terms in Eq. (3.91) cancel each
(p. 185)
other. Hence, we obtain
Pr(k) = 1/r if k is a multiple of 2^n / r
0 otherwise (3.92)
The state of the qubits from the first register for a chosen k at this
final stage of our procedure is
(2^n / r) - 1
|Psi5> = sqrt(r / 2^(2n)) SIGMA e^(2 pi i (lr+q)k / 2^n) |k>
l = 0
(2^n / r) - 1
= sqrt(r / 2^(2n)) (SIGMA e^(2 pi i l r k / 2^n)) e^(2 pi i q k) |k>. (3.93)
l = 0
For k = 2^n p / r th expression in the brackets on the right hand side of
Eq. (3.93) is equal to 2^n / r and the corresponding state is
|Psi5> = 1/sqrt(r) e^(2 pi i q p / r) |p * (2^n / r)>. (3.94)
By measuring the first register, we detect the state with probability 1/r
[Cleve et al., 1998]. The procedure therefore requires repeated measure-
ments, but the number of the repetitions required does not grow expo-
netially with the number of qubits. We obtain 2^n p / r, p = 0, 1, 2, ...
where the values of p are equiprobable. Then we extract r from the ob-
tained 2^n p / r by using the classical continued fraction expansion (poly-
nomially complex procedure) on a classical computer.
In case when r does not divide 2^n we arrive at essentially the same
result. The only difference is that the coefficients of the Fourier trans-
form are no longer represented by sharp values (see Eq. (3.92)) but by
peaks on the closest integers to the multiples of 2^n / r [Shor, 1997].
To see that the above quantum factoring algorithm is of a polynomial
complexity, it is sufficient to sum up the steps of the quantum Fourier
transform procedure, altogether about n^2 steps--each superposition re-
quires only one step. By contrast, the classical Fourier transform takes
about n 2^n steps, thus requiring an exponentially growing time. By ex-
amining the period-finding procedure, we can understand the difference
as follows. If we tried to find the period of function |Psi4| in Eq. (3.84)
directly, it would require a classical trial-and-error procedure and there-
fore an exponential time. Only after we apply the Fourier transform can
we obtain the function |Psi5> (Eqs. (3.93) and (3.94)), which enables de-
tection of the period in a polynomial number of steps and a polynomial
time.
Pavicic, Mladen. 2006.
Quantum Computation and Quantum Communication: Theory and Experiments. New York, NY: Springer Science + Business Media.
