Beyond Binary: Quantum and Biologically-Inspired Computing

CS 301 Lecture, Dr. Lawlor, 2005/11/23
This pre-Thanksgiving break lecture is purely for your own edification--this material won't show up on the test.

Quantum Computers

Quantum computers seem like contrived nonsense until you understand the background physics, so we'll start with a physics lesson.

The fact that light acts like a wave is well-known: interference phenomena are common, from the colors shining off a CD to oil drops on concrete to the double-slit experiment a peacock's tail to Newton's Rings. You can play with wave and interference phenomena online using Paul Falstad's Ripple Tank Applet. and Olympus Microscope's double-slit experiment. The weirdest part about wave phenomena is destructive interference: two out-of-phase waves can cancel each other out to give nothing (like in noise-cancelling headphones). Destructive interference is what cancels out most colors in an oil sheen, and what creates the dark spots in the double-slit experiment.

In 1924 Louis de Broglie (in a 9-page PhD thesis in physics) proposed that even matter acts as waves, and gives an equation for the wavelength. This bizarre idea is now universally accepted--interference of electrons was demonstrated experimentally three years later by Davisson, Germer, and Thomson. 1926 Erwin Schrödinger invented the "Schrödinger Equation" to describe how wavefunctions for light and matter change as time progresses. This is still the defining equation in quantum mechanics.

This was a very curious time, because Millikan's oil-drop experiments (in 1909-1913) had shown very clearly that electrons were particles, not waves--he'd even measured the mass and charge of an electron. Einstein had shown in 1905 that the photoelectric effect was best explained by considering light as a series of particles (called photons), not waves. So we've got the strange situation where experiments are telling us two totally contradictary things.

In a nutshell, the wave/particle contradiction boils down to this:

Wavelike: Electrons have to be waves because they can interfere with one another. Particles shouldn't ever cancel each other out (destructive interference), but electrons and photons do cancel each other out (e.g., in the double-slit experiment).
Particlelike: Electrons have to be particles because they're "quantized": the mass and charge of a clump of electrons is always measured to be an integer multiple of the mass and charge of a single electron. Waves should be able to dissipate smoothly, so you should be able to capture half an electron wave, but in real experiments, this just never happens!

Particle-like properties makes macroscopic sense. There are lots of things, like ball bearings, that come in discrete chunks. It's a little weird to imagine a ball bearing that you can't split into pieces (or melt down), but it's not totally unnatural.

Wave-like properties seem insane when applied to matter. You can't somehow roll together two ball bearings (at the right angles perhaps?) so that when they collide you're left with zero ball bearings (destructive interference).

The current explanation of these two separate facts is, essentially, two separate theories:

Wavelike: Electrons and photons really are described by a wavefunction that evolves through time according to Schrödinger's equation. A single electron's wavefunction can cancel itself out in places, as can the (coupled) wavefunctions of two or more "entangled" electrons. Thus electrons and photons really act like waves. The official name for this process is "unitary evolution".
Particlelike: Electrons and photons are always measured as discrete particles, with probability according to the square of the wavefunction. That is, when acting in a wavelike way, the particle extends across space and sits in a superposition of different locations, but when you look at it, it makes up its mind and is actually observed in a single spot. This means the very act of observation ("measuring") perturbs the system, and makes it act a different way (the Heisenberg Uncertainty Principle). This amazing fact can itself be experimentally verified--adding an electron detector to the double-slit experiment destroys the interference pattern! Nobody's clear on exactly what constitutes a "measurement", but it's clear anything that we can see or directly measure causes stuff to act like particles; it only acts like waves when "nobody's watching". The official name for this process is "state-vector reduction" or "wavefunction collapse".

The "many worlds" interpretation of particlelike behavior is that when you observe it, the particle in effect just extends its own indecision to you the observer. So when you ask where the particle "is", you actually split into a superposition of an infinite number of copies that each receive different answers. Since you're just one of those copies, you think the particle just gave you one definitive answer. But from that point onward, you should exhibit wavelike behavior--you'd have to avoid certain activities because they'd destructively interfere with those of your other copies. This is of course insane, and nobody has ever been able to experimentally demonstrate wavelike behavior on macroscopic objects, but that still might be exactly what happens! There are other interpretations of particlelike behavior, including Roger Penrose's theory that the particlelike wavefunction collapse is a relativistic effect that occurs when superposition effects would distort Einstein's spacetime into topologically incompatible shapes--the wavefunction collapse is in effect what keeps spacetime intact.

Quantum Computing

Luckily, for quantum computation, all we need is some wavelike and particlelike behavior, and (somehow!) we do indeed get it. The idea is to build a "quantum register" made of "quantum bits" that store not just 0 or 1; but the superposition of the two! For example, one qubit can be built out of a block of negatively charged silicon with two small positively-doped "wells". Electrons like to stay in the wells, and avoid the (repulsive) negative region. If an electron is in the left well, that marks a 0. If it's in the right well, that marks a 1. If the electron's wavefunction extends to both wells, that marks the superposition of 0 and 1. Here's a picture of two adjacent wells, where both have trapped electrons (click the picture to go to the IBM research site describing the process).

Atomic Force Feedback Microscope Well Image

If we connect wires between two adjacent wells, the electrons that (maybe) are in the wells interact as waves. If we connect circuitry between the wells, the electrons will seep out into the circuitry--so we can hence perform calculations on these quantum bits! If we're very careful (and this is the hard part), the calculations will stay wavelike.

Why do you care if your quantum computation stays wavelike? Well, imagine you've got a 1000-qubit register where all the bits are in the superposition of 0 and 1. If you feed that register into a quantum circuit, the circuit's output is the superposition of all the outputs of all 1000-bit inputs. If you now carefully collapse the circuit's output to a particular value, the inputs will also collapse due to entanglement. But this means you can now trivially find the input for any output, or invert any function!

For example, consider multiplication (Peter Shor described a theoretical quantum multiplication circuit in 1994). On a normal machine, it's easy (polynomial time in the number of digits) to multiply two long numbers, but it's really hard (exponential time in the number of digits) to find the factors of the product of two numbers. But on a quantum machine, it's polynomial time for either one!

Practical Difficulties with Quantum Computers

If many inputs correspond to the same output, the wavefunction will collapse to a randomly chosen valid input. This means even in a perfectly designed and manufactured quantum computer, you'd have to run your programs several times through to make sure you're getting the unique right answer, and not one of several possible answers. For example, a quantum multiplication circuit might give you the inputs X and 1 for the output X, even if X is composite! A quantum computer is also limited by the size of its inputs, although techniques exist (similar to multiple precision arithmetic) for splitting a big problem into smaller machine-sized pieces.

The real practical problem with quantum computers is that of "decoherence"--premature wavefunction collapse. If the electrons involved interact with too much of the outside world, they cease to behave in a wavelike fashion too early, and then you're back to normal circuitry. The largest quantum computers actually built so far have only two or three qbits, which means they're not at all useful--even grade schoolers can already factor 3-bit numbers. With larger quantum computers manufacturing defects, thermal noise, and leakage current destroy wavefunctions before they can do useful work. But a huge variety of electron (and other particle) containment devices are being tried and built, so useful quantum computers may someday be built. Or perhaps there is some physical limitation on the scale of wavelike effects, and hence quantum computers will always be limited to a too-small number of bits or too-simple circuitry.

Biologically-Inspired Computing

As components get smaller and faster, ordinary computers are getting more and more sensitive to small disturbances. Already, cosmic rays can impact server uptimes. Anecdotally, there's a curious fact about space travel. Due to the higher radiation:

Typical computers lock up about once a day (including flight computers, laptops, digital cameras, etc.) and must be rebooted.
Human beings have never been observed to lock up, and have never needed to be rebooted. This is a good thing, because a spaceship with an insane or catatonic crew might have trouble returning to Earth.

Human brain cells can be killed in large absolute numbers by chemicals such as alchohol and a variety of viruses and bacteria (e.g., meningitis). Yet the brain remains operational (at degraded efficiency) despite such abuse, and rarely suffers significant permanent damage from these injuries. That is, the human brain is a suprisingly fault-tolerant computer. Unfortunately, we have no idea how the human brain operates (see Gerstner's online neuron reverse-engineering attempts). But we can infer it's at least as smart as the reactions of a single cell.

Ecosystem Design

A single cell uses a number of interesting design principles. Many of these same principles are shared by healthy ecosystems, economic markets, functioning democracies, and piles of gravel. I've come to call these principles "ecosystem design":

Many independent decision-makers. Examples: A cell is a complicated collection of separate but interacting proteins. A market is a collection of interacting buyers and sellers. A gravel pile is a collection of interacting pebbles. Results: no central decision-maker means no single point of failure, so the loss of any few small pieces doesn't affect the overall result.
Dynamic equilibrium--lots of small-scale stuff is changing all the time, but the overall averages remain quite constant. Examples: the metabolic rate of a cell is the result of all its pieces, but it's quite predictable overall. A market's overall prices tend to remain fairly stable. A gravel pile's average slope can be predicted to within a few degrees.

As an example, I claim an automobile, CPU, dictatorship, and stack of bricks use "machine design", not ecosystem design: these systems have crucial decisionmaker parts (e.g., the braking system, control unit, dictator, or middle brick) whose failure can dramatically change the entire system. Machine design requires somebody to go in and fix these crucial parts now and then, which is painful.

Ecosystem Design Example

Consider this design problem: you're responsible for maintainance of a city park's pond. Sadly, the pond is right next to a middle school and convenience store, so the pond continually fills up with plastic bottles the junior high schoolers toss into the water. How do you keep the pond free of floating plastic bottles?

The standard machine design responses are top-down social control measures like signs, fines, fences, periodic cleanup drives, or guards; these are extremely expensive per bottle collected. One could also imagine complicated mechanical devices like a bottle-collecting pump, dredge or skimmer, which has the problem that it'll immediately clog up with non-bottle stuff (algae, plants, sticks, rocks).

Ecosystem design offers many alternatives. One is a to design a small bottle-eating critter, like an insect; but living things have their own drawbacks, like escape, extinction, disease, etc. Consider the option of periodically dumping a box of "sticky BBs" into the pond. These would be tiny (1mm) spheres made of a special plastic that sticks only to polyethelene (which the bottles are made of). How would this help eliminate bottles?

Wind blows the stuff in the pond around.
Whenever a bottle runs into a BB, the BB sticks to the bottle.
Hence after a while most of the bottles in the pond accumulate a few BBs.
When two (BB-covered) bottles run into each other, the BBs stick to each other. Since the BBs are stuck to the bottles, that means the bottles stick together.
After a while, all the bottles in the pond will be glued together into one big glob. (See the bizarre video game Katamari Damacy.)

Does this solve the problem? Yes! The pond now has far fewer floating bottles. Instead, it's now got a big clump of stuck-together bottles, which isn't the same thing. A big clump can then be harpooned and hauled out once a month; or it might accumulate dirt and sink; or turned into a planter, etc. Crucially, the inevitable loss of a few dozen, or a few hundred out of the thousands of BBs will have only a minor effect, and the supply is easily replenished.

This is exactly the strategy your body uses to eliminate known invaders like viruses and bacteria (bottles). Your immune system engineers a sequence that literally physically sticks to these invaders, and attaches two copies of the sequence to a Y-shaped protein called an antibody (BB). Each side of the antibody sticks to one invader, which (a) coats invaders in antibodies, which may keep them from operating properly and (b) sticks invaders together into bigger clumps of invaders and antibodies, which can't cause as much trouble as separate invaders and are easier to eliminate completely.

Computing With Biology

Leonard Adleman demonstrated how to use DNA to quickly perform an exhaustive search in parallel. The idea is to dump all the input molecules into a well-mixed test tube. The inputs stick together in various ways, some of which represent the outputs you're looking for. You then have to use chemistry to winnow out the (huge number of) incorrect outputs until you're left with the correct outputs, which you can read off. The advantage is density--since each input letter can be represented by a single molecule, and the computation proceeds in parallel and in 3D, you can theoretically search enormous search spaces quickly.

People are also trying to combine quantum and biological computing--using electrons on biological molecules to represent quantum states. There is even speculation (from Rodger Penrose, see "The Emperor's New Mind" and "Shadows of the Mind") that mammal brains use some sort of quantum computation to do their amazing work.