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.