Someone brought up a "quantum processor" or "quantum computing" the other day. What is it? How does it differ from the processors we're using?

migrated from stackoverflow.com Jun 25 '10 at 14:21
This question came from our site for professional and enthusiast programmers.
First read Introduction to quantum mechanics, and then Quantum mechanics. After that read Quantum computing, QIS, and Quantum Processing unit. 


In a nutshell: processors right now run on electrons, and so are limited by the speed of light and various other nuances. Quantum processors take advantage of the properties of subatomic particles (e.g quantum entanglement, or Einstein's "Spooky action at a distance") to overcome some of these limits and offer a potentially exponential increase in power. In an even smaller nutshell: they're much, much faster. 


Josh K has linked to some good resources which wouldn't be a bad idea for you to read. I believe most of Wikipedia's information on these topics is reasonably accurate. But in case you couldn't tell from the link titles, quantum computing is not exactly a trivial subject. You have to be familiar with some background material (i.e. quantum physics) in order to make sense of it. For an somewhat less technical explanation (coming from someone who has studied quantum computing in some detail), try this: in quantum mechanics, the properties of particles are described by "quantum states" which consist of a combination of "basis states." For example, electrons have a spin (angular momentum), so they act like little magnets. Put them in a magnetic field and they point either up or down (well, either parallel to or antiparallel to the field). In normal computers (simplified model), you might choose up to be 1 and down to be 0, and you can do computations by adjusting the magnetic fields to flip the electrons up or down as you want. But in quantum mechanics, electrons aren't limited to pointing just up or just down; they can actually have some combination (superposition) of those two states, like half up and half down at the same time. That could represent a bit that acts as both 1 and 0. It's called a qubit. When you put multiple qubits (electrons) together, you can get more complicated superpositions, like 11/10/00 or 110/101/011/001/000 or whatever, and if you use those in the right kind of computer, it's like running an algorithm with 3 or 5 or however many inputs simultaneously. So any algorithm that requires you to perform the same operation on many different sets of bits can be enormously speeded up by quantum computing. In practice, it turns out that some exponentialtime algorithms turn into polynomialtime algorithms when you run them on a quantum computer. 

