Computing in Parallel Universes
When One Universe Just Isn't Enough > Page 1,
2, 3
Back
to contents
So just what is it that makes a quantum computer so powerful? The
basic idea behind it all is called superposition. The superposition
principle says that you can overlap a set of different quantum
states but that each retains its own identity within the mixture.
This is just like superposition of water waves that can pass through
each other and, although they'll interfere with each other when
overlapping, they'll come out the other side intact. The same thing
can happen in a quantum mechanical system.
The trick behind making a quantum computer so effective is to set
it up to run a particular calculation but instead of giving it an
single input, giving it a superposition of all possible inputs. Then
the computer will simultaneously run the calculation on all inputs
and get all the corresponding answers at the same time. This is
quite a bit harder to do in practice than it sounds but that is the
essential idea.
What does this all have to so with parallel universe? Well, when
Richard Feynman said that we have difficulty in understanding what
worldview quantum physics represents, he was referring to this
problem. Quantum mechanics is a wonderfully successful theory in
terms of making real predictions about real systems and getting
accurate answers. But lurking behind it all lie metaphysical
questions that are still not resolved.
For example, the superposition principle can be interpreted in a
variety of ways. One way has to do with the Many Universe model of
quantum physics. In this interpretation, every time a system could
go into different states, the universe splits apart into parallel
universe, one for each choice. In our case, the process of building
the superposition to use as an input to the quantum computer makes
the universe split into a set of universe, one for each possible
universe. The trouble is, we don't know which of those universes we
are in until we look at the quantum state. Unfortunately, forcing the choice of universe like
this destroys our ability for another crucial step of the
problem.
Using the Many Worlds interpretation, once all the calculations
are done, we need to do something tricky to make sure we end up in
the universe that we want. If we just measure the output, we would
end up with an answer selected at random from all the possibilities
- and we might not even know which input that corresponded to.
Instead, we have to make all those parallel universe interfere with
each other in such a way as to make just the single answer we want
pop out. And all of that needs to happen without looking!
This is sounding more and more like science fiction every minute
but the experiments show it works so keep hanging on - the ride
continues.
I said that there are different ways quantum physics can be
interpreted so you don't have to take the multiple universe idea
literally if you don't want to. I personally don't like it much but
I don't have room to go into all the reasons why just here.
Nonetheless, the mental image of all the calculations being done in
parallel universe is pretty catchy and it gives us one way to think
about the whole process until we get more familiar with quantum
philosophy.
Clearly there are a lot of details that need to be worked out to
get all of this to work properly and that is what the physicists are
working on. But before we go any further, we really need to talk
about some applications of this technology.
It's all well and good to say we can do all these calculations at
once (perhaps in parallel universes) but what would we actually use
this for? During the eighties and nineties, a lot of suggestions
were made but none of them provided the motivation to spend large
amounts of money researching the details. That was until Peter Shor
of AT&T Bell Laboratories in New Jersey found the killer app -
how to crack the RSA encryption scheme.
The RSA scheme of public key cryptography is the foundation of
basically all modern information security. Interestingly, it has
never been proven to be secure but relies instead on the apparent
difficulty of factoring large composite number into primes. This
mathematical problem is so difficult that it would take longer than
the age of the universe using the combined computing power of the
whole world to crack a single message encoded with the scheme. Even
if classical computers get much better, the encryption scheme can
always stay ahead.
However, Shor's discovery was that the quantum computer could
crack the problem of factoring large numbers relatively easily in
reasonable amounts of time. This rocked the world of information
security and, since then, the US National Security Agency as well as
many governments and universities have been putting money into
quantum computer research to ensure that they stay ahead of any
subversive groups.
Not only did Shor prove that a quantum computer could solve the
factoring problem quickly but he developed an algorithm to implement
the scheme on a quantum computer. Shor's algorithm is based on
clever number theoretical techniques and we will visit it in detail
in a future article but the basics can be explained to anybody with
high school maths and a bit of time to think about it. Stay
tuned!
The ramifications of this are quite astounding. The NSA is
charged with keeping confidential information secure for a certain
period of time after it is stored or communicated. If the security
of those schemes are suddenly compromised, they will fail to keep
sensitive information secret until enough time has passed that it
can be de-classified. Our credit card transactions that take place
over the web are encrypted with the RSA algorithm - nobody is going
to crack them for the time being but if somebody has a quantum
computer working on the problem, goodbye financial security.
Fortunately quantum physics provides a way to make truly
unbreakable cryptosystems in the form of quantum cryptography but,
again, that is another story for another time.
Next we had better talk about what has actually been made in the
lab - just how powerful are existing quantum computers?
Next page Five bits big - woohoo!
>Page 1,
2, 3
Previous
Features | 
.gif){kind=small}
