This is part one of a series on quantum programming. Part two discusses what quantum programming languages will look like.
How do quantum computers work? They rely on quantum bits, or qubits. Classical bits have two possible states: off and on, or 0 and 1 (written 
and 
in quantum mechanics). Qubits, on the other hand, have an infinite range of states. A single qubit can be in any state 
, where 
and 
are complex numbers and 
. [1]
is called a superposition of and . In some sense, superpositions let a qubit be off and on at the same time. The coefficients and represent how off and how on the qubit is. Two qubits occupy a superposition over the possible states of two classical bits: 
. In general, 
qubits occupy a superposition over the 
possible states of an -bit classical system, described by the coefficients 
. [2]
Why is this useful? The popular explanation is that qubits let one quantum operation do the work of classical operations. Unfortunately, that's too good to be true. [3]
A quantum operation does affect all classical states of a superposition. However, quantum mechanics prevents us from directly observing an operation's result: we can't read the numbers 
. We can only get information about qubits by measuring them. [4]
Measuring a qubit returns 0 or 1, nondeterministically. When we measure a qubit in the state , we'll see with probability 
and with probability 
. If we measure it a second time, we're guaranteed to get the exact same result. In other words, measurement destroys a qubit's quantum state, resetting it to or . [5]
In some ways, this means that quantum operations are like classical operations running on random input. The difference between a superposition and a classic random number generator is interference: the states of a superposition interact. Numerically, this means the coefficients of different states impact each other when we manipulate qubits.
Interference is the key to quantum computing's power. For any problem (say, finding a prime factor of an n-bit composite number), most possible guesses (all n/2-bit numbers) are wrong, and a very few are right. Trying random states (guessing random numbers) until we find the right one is a terrible strategy. With superpositions, however, we can more or less try all our guesses at once. Specifically, if we apply clever transformations to our qubits we can cancel out the coefficients of the wrong states, ensuring that measurement gives us back the right answer. [6][7]
What does this mean, physically? That's less clearcut. Both a quantum operation and a classical random operation could give you the output corresponding to any possible input state. Ultimately, both only run once, giving one output corresponding to a single input. The difference is that with quantum mechanics, the calculations we don't perform have some say over the one we do. [8]
This doesn't always work. Some problems can be solved by manipulating qubits; many cannot. We usually hear that quantum computers are better than classical ones. It's more accurate to say that they're a different approach to computation than what we're used to, with fundamentally different properties. As a result, we can use them to solve some hard problems dramatically faster than with classical computers. [9]
How do quantum algorithms work? At a low level, we first set our qubits to a starting state. We then manipulate them using quantum transformations, a rough analogue to classical logical operations.
Quantum transformations are another departure from classical computing. For example, all quantum transformations are reversible. That means there's no quantum 'and' operation: any operator taking two inputs must have two outputs to avoid losing information. It also means you can't copy or delete qubits [10]. This sort of thing underscores how different working with quantum algorithms will be. [11]
At a high level, we know much less about quantum algorithms than classical ones. Discovering what they're good for is an ongoing area of research. The best-known algorithm is Shor's algorithm, which can factor integers in polynomial time. (The best classical algorithm we have runs in sub-exponential time, and integer factorization is not known to be NP-hard.) This can crack RSA encryption, which gets a lot of press. However, it's not a big deal. There are a number of quantum-proof encryption schemes, and we'll just switch to one of them when we need to.
Grover's algorithm is the next best-known: it can search an unsorted list in 
time. This will speed up an enormous class of practical applications, including un-indexed database queries. It also halves the time needed to find a hash collision, effectively doubling the key sizes we need for secure symmetric cryptography. [12]
The most promising application of quantum computing is a more natural one, though: efficient simulation of quantum mechanical systems. A better understanding of quantum mechanics will impact everything from materials science and manufacturing, to genetics and medicine, to the design of classical and quantum computers.
[1] The math behind quantum mechanics is an extension of probability to the complex numbers. The difference is using complex coefficients 
with magnitude ≤ 1 instead of nonnegative real numbers 
with value ≤ 1, and requiring the 2-norm (the sum of the squares of the magnitudes, 
) to equal 1 instead of the 1-norm (the sum of the magnitudes, 
).
There's a ton of physics on top of this basic structure, but we need surprisingly little of it to reason about quantum computers. (Or maybe it's not surprising: you don't need to know the physics behind transistors to use a classical computer.)
[2] Superpositions are weird, and it's natural to ask what they physically represent. The answer is: they represent themselves. Superpositions are a fundamental part of the physical universe. They're only apparent at very small scales, though, so we're not familiar with them from everyday life.
[3] It doesn't seem like quantum computers can solve NP-hard problems in polynomial time unless P=NP, so we don't get an indirect exponential speedup either.
[4] Measurement is also called collapsing the quantum state, collapsing the wavefunction, and quantum decoherence.
[5] This extends to multiple qubits: measuring qubits will return the i-th state with probability 
, and reset the qubits to that state.
[6] Mathematically, qubits are more powerful than random classical bits because they use complex numbers. This lets us associate two values with each state (the magnitude and phase of a complex number) instead of just one, literally adding a dimension to the manipulations we can perform.
The most basic example of this is the "square root of not": a transformation on one bit that returns or with equal probability when applied once, and negates the bit when applied twice. This transformation is 
. If we start with , applying it once gives 
, and applying it again gives .
There's no way to do this classically. If a random circuit takes in or and returns a random output, that output's state must be 
. There's no other way, classically, to represent a 50-50 split.
This means we can't recover the original bit (or negate it) from that output. Qubits let us put the extra information in the phase of the coefficients.
[7] Some quantum algorithms are nondeterministic, which means the coefficients of the wrong states only nearly cancel out, and we measure a correct solution with high probability. These algorithms can usually give arbitrary precision with constant overhead.
[8] This is a widespread quantum mechanical phenomenon. For example, it's the reason why light always take the shortest path between two points: photons are subject to quantum mechanical effects, and would normally have some probability of taking any path between two given points. However, the coefficients of every path but the shortest one cancel out. The double slit experiment is another canonical example of interference.
If you find this difficult to picture, you're not alone. Quantum mechanics is notoriously counterintuitive. There's no substitute for working through a lot of equations if you want a deeper understanding. For a more technical discussion, see https://en.wikipedia.org/wiki/Path_integral_formulation.
[9] In addition to speed, qubits have promising cryptographic properties. Entanglement is the quantum version of correlation, and entangling qubits gives you control over the joint distribution of their measurements. This allows cryptographic protocols that are invulnerable to man-in-the-middle attacks. Measurement and no-cloning can create programs that can only be run once and neither saved nor reproduced.
To paraphrase Scott Aaronson: Bits want to be free. Qubits, in some sense, want to be private.
[10] This is the no-cloning theorem and the no-deletion theorem, which are time-reversals of each other.
[11] In general, the set of possible transformations of input bits is the group of 
unitary matrices. This is analogous to the group of stochastic for classical probability.
[12] Working through a quantum algorithm in detail is beyond the scope of this post, but doing so is the best way to understand quantum computing. This is a great step-by-step explanation of Grover's algorithm and the associated quantum weirdness.
Thanks to Jenna Kefeli, Michael Flaxman, and Ken Brooks for reading drafts of this post.