Introduction to quantum computing

What is quantum physics?

You may have heard of "Schrödinger's cat": Schrödinger was a physicist who theorised that if you were to lock a cat in a chamber along with a small amount of radioactive substance, which may or may not begin to decay (and thus trigger a poison to kill the cat), you wouldn't know if the cat was dead or alive until you opened the chamber.  Therefore, until you do, the cat is in a sense both dead and alive.

This thought experiment (don't worry, we don't do this in real life!) is often used to illustrate the key principles of what we call "quantum physics", science's description of the world at the atomic and subatomic level.  The term is often opposed to "classical physics", the description of the world at the ordinary, macroscopic level.  Yet quantum physics and classical physics differ in more than just their scale, as quantum physics routinely seems to defy our common-sense understanding of how the world works. 

Whereas classical physics says that an object must be in just one determinate state at any given moment (e.g. a coin cannot land on both heads and tails), quantum physics says that a particle can be in multiple states at the same time - a phenomenon called "superposition".  This is what Schrödinger's cat analogy is intended to illustrate, although (as is often the case in science) theorists disagree on how we should interpret it.  A common interpretation is that we should express the superposition of states as a set of probabilities that only collapse into one value upon observation - thus why the cat is both dead and alive until we take a look.

Then there's the phenomenon of "entanglement": whereas classical physics says that two objects separated in space must have independent states or properties (e.g. one coin's landing on heads doesn't depend on another's landing on tails), quantum physics says that two particles can be "entangled" in such a way that you cannot describe the state of one independently of the other.  Performing an action on one will even affect the state of the other, regardless of how much space separates them.  Again, Schrödinger's cat analogy is sometimes used as an illustration of this, with some theorists interpreting the fate of the cat as entangled with the "observer state" i.e. whether or not we're looking.

How does this relate to quantum computing?

Just as classical computing is based on classical physics, quantum computing is based on quantum physics: it exploits the "weirdness" of quantum physics - its probabilistic nature, and the phenomena of superposition and entanglement - in order to create machines far more powerful than the ones we're used to using in everyday life.  Whereas in a classical computer, a "bit" (the most basic unit of information) must have the value of either 0 or 1, a quantum bit (or "qubit") can be 0, 1, or both 0 and 1 at the same time.  Likewise, qubits can be entangled in such a way that they behave together as a group instead of individual units.  What this means is that quantum computers are not just faster than even the most advanced of classical computers, but work in a fundamentally different way - and are therefore capable of tackling complex tasks that aren't even conceivable for existing machines.  To recall Schrödinger's cat, a quantum computer is like a kennel full of highly-trained, well-behaved (and incredibly small!) cats: you give them a problem, close the door, and when you open it again they will have worked out the answer.