Quantum Supremacy

  • 6 Replies
  • 242 Views
*

Art

  • At the end of the game, the King and Pawn go into the same box.
  • Global Moderator
  • **********************
  • Colossus
  • *
  • 5604
Quantum Supremacy
« on: November 02, 2019, 02:54:53 PM »
This is quite an interesting video which doesn't necessarily promise eternal life but possibly having a 200-year lifespan.
Hmm...not really sure how well that would work for an overpopulated Earth.

I like the part of the simulated robot learns to run away from the laser beam! Cute!
https://www.youtube.com/watch?v=92Ntk4niqPo
In the world of AI, it's the thought that counts!

*

Korrelan

  • Trusty Member
  • ***********
  • Eve
  • *
  • 1488
  • Look into my eyes! WOAH!
    • YouTube
Re: Quantum Supremacy
« Reply #1 on: November 02, 2019, 03:29:31 PM »
There's only one solution to over population... run Art... run... the sandmen are coming...

https://en.wikipedia.org/wiki/Logan%27s_Run_(film)

 :)
It thunk... therefore it is!...    /    Project Page    /    KorrTecx Website

*

AndyGoode

  • Trusty Member
  • ******
  • Autobot
  • *
  • 235
Re: Quantum Supremacy
« Reply #2 on: November 02, 2019, 06:01:43 PM »
A question came up on LinkedIn as to what computational task Google actually did to be able to claim quantum supremacy, since those technical details aren't typically mentioned, especially in popular laymen's articles. For some reason Google removed their posted technical article about the project, but somebody saved it and reposted it. You can see the technical details here...

https://www.docdroid.net/h9oBikj/quantum-supremacy-using-a-programmable-superconducting-processor.pdf

*

LOCKSUIT

  • Emerged from nothing
  • Trusty Member
  • *****************
  • Sentinel
  • *
  • 3640
  • First it wiggles, then it is rewarded.
Re: Quantum Supremacy
« Reply #3 on: November 02, 2019, 08:59:25 PM »
see they show Hide & Seek (blue and red men) OpenAI made, if they add quantum power it will work much deeper.
Emergent

*

AndyGoode

  • Trusty Member
  • ******
  • Autobot
  • *
  • 235
Re: Quantum Supremacy
« Reply #4 on: November 02, 2019, 11:16:22 PM »
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.

*

LOCKSUIT

  • Emerged from nothing
  • Trusty Member
  • *****************
  • Sentinel
  • *
  • 3640
  • First it wiggles, then it is rewarded.
Re: Quantum Supremacy
« Reply #5 on: November 03, 2019, 09:45:57 PM »
Read the leaked Paper and got 4 things from it. Also a related post outside the Paper.

Reading the leaked Nasa Google Paper for quantum supremacy i see 4 ideas for maybe AI and/or compression:
1) giving nodes electrical excitement and then tuning them using magnetic fields
2) averaging each qubit in a graph/batch after gathering many sequences of the ran algorithm
3) making node's neighnors ressonate and equalize with each other ex. the 4 around a node (so all 5, but all do this lol...iterately must scan over it therefore gee)
4) shifts and crosstalk

from https://www.edge.org/conversation/rodney_a_brooks-the-cul-de-sac-of-the-computational-metaphor
"This is a mixture of continuous stuff. It’s a wide world of lots of stuff happening simultaneously with local dynamics. When you look at a particular process, and this happens in genetic algorithms as well as in the artificial life field—you talk about a bunch of these in "Cellular Automata"—you see a ratcheting process in which things ratchet up to order from disorder. It's something that looks like mush, but out of it, because of some local rules, comes order. It’s limited order, but then when you put different pieces together, which locally result in little pieces of order, you sometimes get much more order from the coupling of them. What calculus of that could you develop? I’m thinking there may be something around that, a language for explaining how local, tiny pieces of order cross-coupling across different places couple together to get more order."



Also:
"When you have something that's flapping around all over the place and you want to organize it into a limited set of possibilities, that means there’s irreversibility going on—the number of final states is more than the number of initial states. I don't think that phenomenon, as such, is that profoundly phenomenal."

Similar to the ball rolling down a v-shaped funnel with pinball stubs, no matter starting location at top, it always ends up at bottom of hole and sits there! but cant tell where it started from!!!!
Emergent

*

goaty

  • Trusty Member
  • *******
  • Starship Trooper
  • *
  • 459
Re: Quantum Supremacy
« Reply #6 on: November 04, 2019, 05:15:41 PM »
Deep learning means to me, the computer working out all the symbology itself from the ground up, slowly developing link from previous link.

Whacking a quantum search on a set of rules it needs no development structure. (so its shallow, I agree.)

 


Users Online

15 Guests, 1 User
Users active in past 15 minutes:
Korrelan
[Trusty Member]

Most Online Today: 26. Most Online Ever: 340 (March 26, 2019, 09:47:57 PM)

Articles