Radical introduction to quantum computing

Published: May 24th 2010 (monday), 20:44

On the English section of the "Quantasia" discussion board Milo Wolff, father of the WSM theory, started an interesting thread about microchips. He asked about our ideas and thoughts on what the WSM theory could introduce into the subject of the production and working of michrochips.

Larry Pruitt showed recent works on making three-dimensional integrated circuits. It would be based on stacking many layers of semiconductors in a form of a sandwich ;-)

Of course stacking microchips can save space and faciliate cooling. It's an interesting idea too to build a microchip as a real 3D structure. I hope we will see this technology soon.

But there are limits of that technology, which might be approached quicker than we suspect.

One of these limits is the scaling factor: We can't build a microchip smaller than a certain size (13 micrometers AFAIK), because of interferences between circuits and heating problems. Even if we invent a way to make smaller chips, Heisenberg says we're in trouble when approaching the atomic scale (Though WSM can help in this particular area, because it changes the way we look on Heisenberg's uncertainty.)

And there's a problem with the sole structure of present computers and the principles of computing, which lies in transfering information (data) between each part of the computer.

The limits of the von Neumann's architecture

Every present computer is built using the von Neumann's architecture, which means it has a central processing unit (CPU) and operational memory (RAM). Data and programs (which are also data) are stored in RAM and they have to be transfered to the CPU first to make any calculation on them possible. And after computing the result, they're sent back to the RAM. This costs time, and it has a speed limit: for electromagnetic signals the speed of these transfers can't exceed the speed of light.

This architecture also means that it can't be parallelized (don't confuse with paralyzed ), because there's only one data bus connecting the CPU and RAM, and it's one-way only! Microchips producers are multiplying the cores on their CPUs to speed them up. But it doesn't help that much, because of this bottle-neck (one bus, one-way only). There are ways to overcome this problem a little, by using double/triple-gateway memory, but it needs wider buses, more power consumption, increases microchips' complication etc.

Distributed computing

Richard Feynman (who had been interested in computation technology too) knew about these problems and once said that there's only one solution to this problem: data have to be computed in the place they are stored. This is a great idea, because it wipes out a problem of transfering data from one place to another! CPUs have a bunch of internal registers and cache memory to store more data "in the place they're computed".

But the real breakthrough will be when we distribute the computing power from one big central processing unit to a network of smaller procesing units bundled with their own piece of memory and interconnect them each other. This architecture is called distributed network computing or cloud computing. It reduces the problem of transfering data to the minimum, it can be greately parallelized (don't confuse with "paralyzed" ;-)), and it allows for easy scaling (you simply add more microchips).

Distributed thoughts

There are "computers" already using this technology, but not human-made. One of them is… a human brain! The brain is built from neurons (brain cells). Each neuron is a cell with many inputs (dendrites) and one output (axon) (which may spread at the end to conduct signals to many other neurons). At the end of each of its input, there is a small gap called synapse. This little gap conducts electrochemical signals the more you use it, so it's a form of memory. And each neuron sums up signals from its many inputs and when they are stronger than a given threshold, it fires up a signal on its output axon. So it's also a simple computational device.

Thus, amy single neuron is the best marriage of memory and processing unit, all in one place, and the whole brain is the best distributed computing network! Data are processed in the place they're stored – at each neuron – and one piece of information could be distributed over the whole brain (which also means that it's less vulnerable to physical damages – Jennifer should read this!).

Computations in this kind of "computer" are higly parallelized: many neurons can work in parallel, each one on the different part of the problem and at the same time, and build up the answer together. That's why our brains can do many things, like pattern recognition (voice, faces etc.), free associations etc., which present microchips can't. And neural networks can "program theirselves" (learn), what present computers can't do.

Universal computer

There's another distributed computer, which you probably didn't know and didn't even suspect. And it has even more in common with WSM! It is... our Universe! Yes, you heard that right. The Universe is a perfect distributed computer! It came to me in a dream I had some time ago. Let's see why:

The Universe is built from googolplexes of atoms, and each atom is a connection of memory and processor in one place. Its energetic quantum state is its memory: when you set the atom in a quantum state, it'll stay in that state forever, until iterrupted by something from the outside (see Milo Wolff's book "Exploring the Physics of the Unknown Universe" on page 234 for the experiment proving this). And it is an arithmometer too: it sums up amplitudes of the waves coming from all the neighbouring atoms in the known Universe and changes its own quantum state according to them. So it computes and remembers.

An atom is like a neuron in a reeeeaaally big neural network But it's better than a brain or microchips, because it doesn't need any wires! It uses space itself and waves travelling there to transfer information.

But then I wonder... if the Universe is a great distributed quantum computer, then:

  1. What is the thing it is computing?
  • For whom? Who is the programmer? :-)
  • What will happen when it finish its computation? :-P
  • Will it be the number 42? :-D
  • If it works similarily to the neural network of our brains, then what is the Universe thinking?
  • So we are comming to the astonishing conclusion:
    Energy is information. And the energy is made of waves. So every wave is an information by itself! If we want to benefit from the WSM in producing microchips, then we should drop the idea of a microchip at all, and use quantum waves in itself as a distributed computing grid. Then we'll be able to use any arbitrary matter as a processing and storage material, and use space itself to transfer information. And that will be what I call a real breakthrough! :-D (though not very innovative: the Universe is using this technology from its bare beginnings ;-D ).

    And this connects smoothly to the topic of quantum computers.

    Quantum computers

    Some time ago Allan Turing wrote his paper about the Turing Machine – a generalized model of a computer. Turing's computer consist of a processing head and an (infinitely) long tape which is used as a linear memory. Turing computer reads data and program from the tape, computes them in its head (which may change its internal state then) and stores the outcome on the tape.

    And there is also a basic way to store data: the binary system. Each number can be represented by a set of digits. Binary system uses only two digits: 0 and 1, so it is the most basic. More basic is only the unary system, which has only one digit: "1", and stores a number as a series of 1's, (e.g. number 5 is stored as 11111), but it is highly inefficient (try to store a number 1000 in that system and you understand why ;-J ).

    So these two concepts: binary system and Turing machines, are the bases of construction of all present computers. Any algorithm can be modelled that way, and all present computers using von Neumann's architecture use this concept of computing. It works, but sometimes it needs huge amounts of time to compute things.

    One of the example problems, which present computers have difficulties with, is factorization of big numbers onto prime factors. The longer the number, the more time it needs to factorize. A number long enough will need more time to factorize than the age of the Universe, so mostly all present ciphers and security algorithms are based on this difficulty of factorizing big numbers.

    But there's a different way to build a computer, that nobody had suspected until recent: I speak of the idea of Quantum Computing. And nobody suspected that so many could depend on the way a computer is built! (well, after all, they thought that there's only one way of doing it: the von Neumann's way). And it appears that this new way of computing have a great power. There are algorithms for quantum computers that are very promising: they can factorize a very big number in a glimpse! They can search the database in a square root of the time a current computer needs do the same! How it's possible?

    If you read any book on quantum computing, and understand it (which is very hard! try it yourself :-P ), then they will tell you that instead of using simple binary bits to store information, quantum computers use qubits (quantum bits), which are made of single atoms or particles. Qubits can store more information than binary bits. It's said that in 250 qubits you can store more numbers than there are atoms in the whole Universe! They exploit those special miraculous quantum effects, like quantum entanglement, superposition of probabilities etc. And that's all very complicated (in these books, at least).

    At present it's hard to build a computer that way because of what they call quantum decoherence. In plain English it means that these computers tune out in a short time (a few microseconds is enough). And they don't know yet how to stabilize these atoms to hold the quantum state enough time (and here's a good place to start for the WSM; see the experiment mentioned above).

    There's one more problem: every measurement of the quantum state destroys the superposition and gives only one outcome of many – the one with the greatest "probability". So you can read only one of these results, and do it only once.

    My own thoughts on quantum computing

    Here's a good place for me to write a bit on my own ideas about quantum computing. I've read many books on the subject and I found them very hard and complicated. They use hardcore mathematics and it's all messed with equations and terminology from Quantum Mechanics. And even worse, all the ridiculous beliefs from quantum mechanics, like the idea of probability, point particles, superposition, wavefunction colapse, quantum entanglement and other quantum miracles, fog out that knowledge even further.

    I've spent many time to understand that and break that code, trying to find simplifications. And after some time I think I achieved that goal. When you dig through all that mess, you'll see that for real it's all very simple! All these complications come from the misunderstandings of Quantum Mechanics! But I must admit, if I hadn't knew the WSM, I could never be able to understand that!

    Quantum Computing, the easy way

    When you forget for a moment that what you read is about Quantum Mechanics and look at the formulas only, you'll see that in Quantum Computing they use simple vectors and matrices to operate on these vectors. A vector a magnitude with direction, which is used to store "quantum state" of a qubit. The matrices, which they call quantum gates, are tables of numbers, which store information about how these vectors are manipulated. I've studied 3D computer graphics, where vectors and matrices are ubiquitous. Thakns to that I was able to see that these manipulations are also simple: they are simply coordinate transformations which rotate the vector in a way which leaves its length unchanged (they call it unitary operations).

    And that's it! :-D All the quantum computing lays on that base: you take a vector pointing in some direction and apply these matrix transformations on it to rotate it in many different ways. After you finish, the new direction the vector is pointing to is the final answer. Then you project it onto one of the coordinate axes to "measure" the outcome.

    Where are the quantum particles?

    I don't know how about you, but I don't see any atoms or particles there! So, are the atoms and nanotechnology really needed to build a quantum computer? I believe they're not, and that the benefits of quantum computing are gained not from the miraculous quantum effects of atomic matter, but from the mere fact that they use a different way of storing data. A better "compression method", which allows us to make more calculations at once.
    To illustrate this idea, I'll tell you a story ;-)

    Little Peewee and his box of quantum blocks

    Once upon a time there was a Little Peewee. And he had a box of blocks. There were 10 slots in the box, and each slot can contain one block. Little Peewee can count from 1 to 10 using these box and blocks:
    "Zero" is an empty box.
    "One" is when he puts 1 block in the box.
    "Two" is when he puts 2 blocks there.
    "Three" is when he puts 3 blocks.
    And so on. He can count up to 10, because only 10 blocks fit in the box (and in his head).

    But here comes his father, an IT engineer, and say to him:

    – Little Peewee, you're doing it very inefficient. You're using a unary system for storing numbers. In computer science, we're using more efficient way: a binary system. It's a neat trick which encodes numbers in a special way that can increase the count of numbers you can store in the box.

    – Gee, I didn't know. Can you tell me how it works?

    – Yes of course. First, take a pen and write these numbers over each slot: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512. These are subsequent powers of two. Now, you use the presence of block in each of these slots to tell that the particular power of two is contained in your number:
    "Zero" is an empty box.
    "One" is when you put one block in the first slot, marked as "1".
    "Two" is when you put one block in the slot marked as "2", leaving other slots empty.
    To store "three", you put one block in slot "1" and one in slot "2". It means that the number three is made of one "1" and one "2". 1+2=3.
    To store "four", put one block in slot marked as "4". It means: one "4".
    To store "five", put one block in slot "4" and one in slot "1". It means that five is composed from "4" and "1". 4+1=5
    And so on. This way you can store any number from 0 to 1023, which gives you a total of 1024 different numbers.

    – Wow, dad, it's fantastic! 1024 is far more than 10! But wait… Why 1024?

    – Because you have 10 slots. Each slot can be filled with a block or not, which is 2 possible states. And 2 to the power 10 is 1024.

    – Gee, it's hard. I don't understand these powers. Can you explain it easier?

    – Yes. The last slot in the box means 512 when filled with a block. When you fill all other slots, you'll get 512+256+128+64+32+16+8+4+2+1=1023. With 0 it is 1024 possible numbers.

    – OK, now I get it. Thanks, dad. But… I think to myself… If we can use the binary system to encode more numbers in the same box and using the same number of blocks, then maybe there is some even better way, a better code, which can store even more numbers there? What do you think?

    – No, silly – replied the father – it's impossible. The binary system is the most basic we know. And there is a guy called Shannon, who prooved mathematically that if you have 10 slots and each one can store 1 block, then there are only 1024 possible ways to place these blocks there. It's called information entropy. To store 1024 different numbers, you need at least 10-slot box.

    But then, in a big colorful flash of light, a four-dimensional being from hyperspace appeared in the middle of the room and he said to the father:

    – I watched your discussion from above and I have to tell you that you're wrong. Your son is right: you can use more tricky way to store information.

    He took a pen and on each block he marked a dot on one of its sides. Then he crossed over the powers of two, and wrote above another numbers: 1, 6, 36, 216, 1296, 7776, 46656, 279936, 1679616, 10077696 – the powers of six. After that he put the blocks in the box in a strange way: one block he placed with the dot at the top, the other one he placed "upside down', still other with the dot pointing up, and the last one he put with the dot pointing to the left – each block in a different orientation! Then he said to his shocked observers:

    – Now you can put each block in six different ways, making its marked side pointing in one of six different directions. This gives you 6 to the power of 10, which is 60466176 different numbers.

    – Wow! Over sixty millions of numbers in a 10-slot-only box?! How it's possible?!

    – they both screamed.

    – Well, we call that 'Quantum Computing'. And these 60 millions are only a kick-start. Notice there's really NO limit on how many directions you can point with the block, as far as you can tell which direction it is pointed to.

    – Whoa! – said the father.

    – But wait. How can we tell which direction is the block pointing to?

    – Well – said the Stranger – you can use a coordinate system. For example, you can say that the horizontal axis is '1', and the vertical axis is '0'. When the block is pointed exactly in one of these directions, you have your plain old binary computer. But if you rotate the block in an arbitrary direction, you have a quantum computer. And then you can describe its direction by using these coordinates: you simply look how much the block is horizontal, and how much it is vertical.

    – Gee, it's pure fantasy!

    That was too much for our great heroes' little minds. Their brains nearly boiled when they tried to imagine how many numbers they can stuff into that little box. And the Stranger, which could read in their minds, said to them:

    – Before I disappear from your world, I have to tell you that you can use smaller things than this box to store all these numbers. You can use grains of sand, bacteriae, viruses, molecules, or even single atoms. All matter is capable for computing. In fact, all matter is inteligent, and you're living in an enormous quantum computer we had once built, which you call Universe :-D

    And then he disappeared, upgrading himself back to the higher dimension, leaving his pupils with wide-opened mouths.

    Of course they have tried to share their newly-achieved knowledge with other humans. But human beings, especially the ones who call themselves "modern quantum physicists" ;-J were too stupid (by which I mean: convinced that they know everything already and they're always right ;-P) to understand it. They understood olny slots and blocks, so when they saw a block rotated 30 degrees from its normal position, they said: "This block is '0' and '1' at the same time – a superposition of these states", or "It's a '0' with 25% probability, and '1' with 75% probability". And in the computation proces, when they have been observing the blocks rotating, they said: "Wow, these blocks are entangled! Their '0' and '1' states change simultaneously!" Little Peewee and his father were very disappointed by the scientists, but they hoped that once scientists will be able to understand how these quantum computers work.

    The end :-D

    I hope you liked the story and it helped you to understand what I mean. I think that Quantum Computing isn't really about using atoms and quantum miracles, but it's about using a neat storage system for numbers, which can encode more numbers in one storage element (a qubit).

    The scientists will tell you that it's all because of the quantum superposition. In one binary bit you can store only '0' or '1'. But in qubit you can store an arbitrary superposition of '0' and '1', which allows to store more information there. They say that the qubit "will be '0' and '1' at the same time – a superposition of both". Eg. a '1' with 66% probability, and it will be also '0' with 33% probability. But from the Peewee story you can clearly see that what they call "probability" is really a projection of a vector onto one of the axes, that is, its coordinate or component.

    If the story doesn't convince you, then look at what Hadamard quantum gate does, which is a tool for superimposing quantum states: it takes a vector pointing in '0' or '1' axis direction and rotate it 45 degrees! They call it superposition of '0' and '1' because you can write the new vector as:

    Formula (1)
    (0+1)/sqrt(2)

    When you add two vectors, one pointing in direction |0> and other pointing in direction |1>, then you'll get a vector being a diameter of the square made of these two vectors. It will be at 45 degree angle to both axes, and its length will be sqrt(2), so to normalize its length to be unitary (=1), you have to divide it by its length, which is sqrt(2) of course. Then:

    Formula (2)
    sqrt(2)/sqrt(2) = 1

    Same goes for entanglement. It is created by superimposing the state vector of two qubits, using the same method as above. But since both use different directions, the resulting vector has more dimensions it can rotate in.

    Up to now I see no reasons which could stop us from "emulating" quantum computing on present computers, using vectors and matrices. As every emulation, it could be a bit slower than physical/hardware implementation (multidimensional vectors and big matrices means many coordinates and numbers to compute), but still I don't know why couldn't we use some other hardware implementation than single atoms, which are too hard to manipulate for us at present. What if we can use more macroscopic devices for that? The simpliest device of that kind could be even a bunch of rotating wheels or cogs, with arrows painted on them; sort of the famous Antikythera Mechanism (maybe it was an ancient quantum computer too? ), or the less famous Turing's Zeta function computer, or Leibniz difference machine.

    Or maybe WSM can help us here to use waves and interferences as a computing device?

    What do you think?


    Recent articles
    Most read

    I recommend only the books I have read, and which I've found good and life-changing.