Also, I suppose I had better state my credentials for even
talking about the subject with some degree of credibility at all. I have strange reading habits, and for the
last 30 years I have enjoyed picking up the odd popularization of quantum
physics and trying to determine what it all meant. In fact, a lot of the most recent physics
news has related to quantum physics, and this has meant that the latest
presentations are able to a much greater degree to fit quantum physics into an
overall physics theory that has some hope of making some sense of quantum
physics’ weirdnesses. As far as theory
of algorithms goes, I have a much greater background, due to my luck in taking
courses from Profs. Hopcroft and Hartmanis, two of the true greats of computing
science and applied mathematics in their insights and their summarizations of
the field of “theory of algorithms and computing.” And, of course, I have tried to keep an eye
on developments in this field since.
So where’s the fun?
Well, it is in the wedding of the two areas listed above – quantum physics
and theory of algorithms – that produces some mind-bending ways of looking at
the world. Here, I’ll only touch on the
stuff relevant to quantum computing.
The Quantum Physics of Quantum Computing
I think it’s safe to say that most if not all of us grew up
with the nice, tidy world of the atom with its electrons, protons, and
neutrons, and its little solar system in which clouds of electrons at various
distances orbited a central nucleus.
Later decomposition of the atom all the way to quarks didn’t
fundamentally challenge this view – but quantum physics did and does.
Quantum physics says that at low energy levels, the unit is
the “quantum,” and that this quantum unit is not so much like a discrete unit
but as to a collection of probabilities of that particle’s “state” summing to one. As we combine more and more quanta and reach
higher levels of energy in the real world, the average behavior of these quanta
comes to dominate, and so we wind up in the world that we perceive, with
seemingly stable solar-system atoms, because the odds of the entire atom
flickering out of existence or changing fundamentally are so small.
Now, some quanta change constantly, and some don’t. For those that don’t, it is useful for
quantum computing purposes to think of their collection of probabilities as a superposition of “states”. One qubit, for example, can be thought of as
a superposition of two possible states of spin of an electron – effectively, “0”
and “1”. And now things get really weird: Two quanta can become “entangled”, either by
direct physical interaction with other quanta or (according to Wikipedia), at
least conceptually, by the act of our measuring what really is the state of the
qubit. To put it another way, the moment
we measure the qubit, the qubit tells us what its value really is – 0 or 1 –
and it no longer is a collection of probabilities. [ Please bear in mind that this is a model of
how quanta behave, not their actual behavior -- nobody knows yet what really
happens]
It’s quantum entanglement by direct physical interaction
pre-measurement that really matters to quantum computing – and here things get
even weirder. Say you have two qubits
entangled with each other. Then quantum entanglement means that no matter how far apart the two qubits are,
when you measure them simultaneously the discovered value of one is some
function of the discovered value of the other (for example, the two will yield
the same value) – what Einstein called “spooky action at a distance.” Physicists have already shown that if there
is any communication going on at all between two qubits, it happens at hundreds
of times the speed of light.
The meaning of this for quantum computing is that you can
create a computer with two qubits, and that quantum computer will have four
states (actually, in some cases as many as 16), each with its own probability. You can then perform various operations in
parallel on each qubit, changing each state accordingly, and get an output
(effectively, measuring the qubits).
That output will have a certain probability of being right. Recreate the qubits and do it again; after
several iterations, you very probably have the right answer.
One final important fact about qubits: After a while, it is extraordinarily likely
that they will decohere – that is,
they will lose their original states.
One obvious reason for this is that in the real world, quanta are
wandering around constantly, and so when they wander by a qubit during a
computation they change that qubit’s stored state. This is one of the things that make creating
an effective quantum computer so difficult – you have to isolate your qubits
carefully to avoid them decohering before you have finished your computation.
The Algorithmic Theory of Quantum Computing
So now, hopefully,
you are wondering how this strange quantum world of probabilities at a distance
translates to faster computing. To
figure this out, we enter the equally strange world of the theory of algorithms.
The theory of algorithms begins with Godel’s Incompleteness
Theorem. Kurt Godel is an unsung giant
of mathematics – one Ph.D. student’s oral exam consisted in its entirety of the
request “Name five theorems of Godel”, the point being that each theorem opened
up an entirely new branch of mathematics.
In terms of the theory of algorithms and computing, what Godel’s
Incompleteness Theorem says, more or less, that there are certain classes of
problems (involving infinity) for which one can never create an algorithm (solution) that will deliver the right
answer in all cases. Because there is a
one-to-one mapping between algorithms and mathematical solutions, we say such
problems are unsolvable. David Hilbert
the mathematician, at the start of the 20th century, posed 20 hard
problems for mathematicians to solve; several of them have been proven to be
unsolvable, and hence uncomputable.
By the 1960s, people had used similar methods to establish
several more classifications of problem “hardness”. The most important one was where the minimum
time for an algorithm was exponential (some constant times 2**n, where n is
[more or less] the most computationally expensive operation in the algorithm) rather
than polynomial (some constant times n ** q, q less than 3). In the typical case, once n got above 30 or
40, exponential-minimum-time problems like Presburger arithmetic were effectively unsolvable in any time short of
the ending of the universe.
It has proved extraordinarily hard to figure out where the
boundary between polynomial and exponential algorithms lies. One insight has been that if one pursues all
the possible solutions to some problems on some imagined computer offering
infinite parallelism, they can be solved in polynomial time – the “NP” class of
problems. Certain real-world problems
like the traveling salesman problem (figure out the minimum-cost travel
sequencing to n destinations for any traveling salesperson) are indeed
NP-solvable. But no one can figure out a
way to determine if those problems are solvable in polynomial time without such
parallelism – whether P=NP. In any case,
it would be a major boon if some computing approach allowed P-time solution of
at least some of those problems.
But even if we can’t find such an approach via quantum
computing, it would still be very worthwhile for all classifications of algorithms
(except unsolvable, of course!) to find a way to get to an “approximate”
solution faster. Thus, for example, if
we can come to a solution to the traveling salesman problem that 99 times out
of 100 is within a small distance of the “real” best solution, and do so in
polynomial time on average, then we will be happy with that. And thus, despite its probabilistic nature –
or possibly because of it – quantum computing may help with both the weird
world of “presently effectively unsolvable” exponential-time problems and with the
more normal world of speeding up solvable ones.
How All This Applies To Today’s Quantum Computing
The world of qubits as it exists today appears to have two
advantages over “classical” computers in attempting to speed up computation:
1.
Greater parallelism. That is, you don’t sequence the computations
and output; instead, within each and every qubit, they are performed pretty
much at the exact same time.
2.
The ability to get “close enough”
probabilistically. As noted above, you
can choose how much likelihood of being right you want, and as long as it isn’t
absolute certainty, the number of iterations needed to get to a “good enough”
answer on average should be less than the number of computations in classical
computing.
However, there are two significant disadvantages, as well:
(a) The “sweet spot” of quantum
computing is the case where the number of inputs (my interpretation: the number of needed “states” in the quantum
computer) is equal to the number of outputs needed to reach a “good enough”
answer. Outside of that “sweet spot”,
quantum computing must use all sorts of costly contortions, e.g., repetition of
the entire computation the same number of times when the number of states does
not cover all the possible outcomes you are examining to find the right answer.
(b) When you need a very high
probability or certainty of getting the right answer, or, failing that, you
need to know how likely you are to be very close to the correct answer, you
need a lot more runs of your quantum computer.
To see how this might work out in practice, let’s take the “searching
the database” problem and use (more or less) Grover’s Algorithm (no Sesame
Street jokes, please). We have 1023 different values in 1023 different slots in our
database, and we want to find out if the number “123456” is in the database,
and if so, where (sorry, it’s a small database, but no bit-mapped indexing
allowed). We declare that each
possibility is equal, so there is a 1/1024 chance of each outcome. We use 10 qubits to encode each such
possibility as an equally probable “state”.
The classical computing algorithm will find-and-compare all
1023 values before coming to a conclusion.
Grover’s Algorithm states that on average, the quantum computer will
take sqrt(1024) or about 33 iterations before (on average) it will have found
the right answer/location. Score one for
quantum computing, right?
Well, leave aside for a moment the flaws of my example and
the questions it raises (e.g., why can’t a computer do the same sort of probabilistic
search?) Instead, let’s note that it appears that in this example the
disadvantages of quantum computing are minimized. I configured the problem to be in quantum
computing’s algorithmic “sweet spot”, and effectively only asked that there be
a greater than 50% probability of having the right answer. If all you want to know is where the data is
located, then you will indeed on average take 33 iterations to find that
out. If you want to be sure that the number
is or isn’t in the database, then your best solution is the classical one –
1024 find-and-compares, without the added baggage of restarting that quantum
computing brings with it.
And I haven’t even mentioned that so far, we’ve only scaled
up to 5 qubits available for researchers, and that as we scale further and our
computations take longer, decoherence becomes even more of a problem.
So that’s why I dropped that downer of a conclusion
above. It’s early days yet; but there’s
a lot of difficult work still to come in scaling quantum computing, with no
guarantee of success, and the range of long-term use cases still appears less
than broad – and possibly very narrow.
Oh, Well, Fun Take-Aways
So while we wait and wait, here are some wonderful
weirdnesses of the wedding of quantum physics and theory of algorithms to think
about:
·
You can’t be in two places at once. Not.
Simply create two quantum copies of yourself in your present “state.” Keeping them isolated (details, details),
move one of them halfway around the world.
Measure both simultaneously. They
will both be identical at that moment in time.
·
Things are either true or false. Not.
Things are either true, or they are false, or whether they are true or
false is undecidable.
·
Explanations of quantum computing are often incoherent, and whether they convey
anything of value is undecidable.
No comments:
Post a Comment