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.