Introduction #
In this article we will introduce superdense coding, a scheme which lets Alice send two bits of (classical) information to Bob by transmitting a single entangled qubit. This article will be mathematically rigorous, while hopefully also providing an intuitive explanation of what is really going on. We will assume an undergraduate understanding of quantum mechanics, including familiarity with Dirac notation and entanglement.
Suppose Alice has a qubit, whose state may be written as
[eqQubitGeneral]: $a0\rangle+b1\rangle,$
where $a$ and $b$ are complex numbers such that $a^2+b^2=1$. It would seem from [eqQubitGeneral] that if Alice wished to encode some information in her state and then send it to Bob, she has a lot of freedom in her choice of $a$ and $b$. In comparison to a classical bit, which can only take discrete values of $0$ or $1$, it seems like a qubit is infinitely more powerful! However, there's a big catch.
To access this information Bob needs to measure the qubit, and (assuming he measures in the ${0\rangle,1\rangle}$ basis) his result will be either $0$ or $1$, with probability $a^2$ and $b^2$ respectively. Once he does this the state is lost, and he can gain no more information. Thus the only way that Alice can deterministically transfer information is to send either the $0\rangle$ state or the $1\rangle$ state, in which case Bob can measure it to receive one bit of information. If Alice sends anything else, Bob won't be able to draw a conclusion from a single measurement, after which the original state will be lost. Despite all the extra freedom we have in a qubit, the probabilistic nature of quantum measurement seems imply we can't do any better than with a classical bit.
It turns out however that if Alice and Bob start off by sharing an entangled state, Alice can deterministically transfer two bits of information with a single qubit, by using a scheme called 'superdense coding'. We can think of this as them sharing one bit of entanglement, which together with the transfer of one qubit leads to two bits of information. This idea is relatively new, it was introduced in 1992 by Charles Bennet and Stephen Wiesner (see References for the paper link).
Some quantum gates #
We will begin by defining four operators which Alice and Bob will use. Firstly there is the Pauli $\sigma_x$, which flips a qubit:
$\sigma_x0\rangle=1\rangle, \; \sigma_x1\rangle=0\rangle.$
Next there is the Pauli $\sigma_z$ operator, which flips the phase of the $1\rangle$ bit:
$\sigma_z0\rangle = 0\rangle, \; \sigma_z1\rangle = 1\rangle.$
The Hadamard operator sends the qubits to two orthogonal superpositions:
$H0\rangle=\frac{1}{\sqrt{2}}\left(0\rangle+1\rangle\right), \; H1\rangle=\frac{1}{\sqrt{2}}\left(0\rangle1\rangle\right).$
We can see that this also reverses itself:
$H\frac{1}{\sqrt{2}}\left(0\rangle+1\rangle\right)=\frac{1}{\sqrt{2}}\left(H0\rangle+H1\rangle\right),$
$\phantom{H\frac{1}{\sqrt{2}}\left(0\rangle+1\rangle\right)}=\frac{1}{\sqrt{2}}\left(\frac{1}{\sqrt{2}}\left(0\rangle+1\rangle\right)+\frac{1}{\sqrt{2}}\left(0\rangle1\rangle\right)\right),$
$\phantom{H\frac{1}{\sqrt{2}}\left(0\rangle+1\rangle\right)}=\frac{1}{2}\left(20\rangle\right),$
$\phantom{H\frac{1}{\sqrt{2}}\left(0\rangle+1\rangle\right)}= 0\rangle.$
Similarly:
$H\frac{1}{\sqrt{2}}\left(0\rangle1\rangle\right)=1\rangle.$
Finally there is the only twoqubit gate we will need, the controlled not (CNOT) gate. This takes two qubits; if the first (the control) is $0\rangle$, it leaves the whole state unchanged:
$CNOT\left(0\rangle 0\rangle\right)=0\rangle 0\rangle,$
$CNOT\left(0\rangle 1\rangle\right)=0\rangle 1\rangle.$
If the control qubit is $1\rangle$ however then CNOT flips the target:
$CNOT\left(1\rangle 0\rangle\right)=1\rangle 1\rangle,$
$CNOT\left(1\rangle 1\rangle\right)=1\rangle 0\rangle.$
The superdense coding protocol #
Let's see how we can encode two bits of information in a single qubit. This time, Alice and Bob start off with a pair of entangled qubits:
[eqAliceBobBellPair]: $\Psi\rangle_{AB}=\frac{1}{\sqrt{2}}\left(0\rangle_A0\rangle_B+1\rangle_A1\rangle_B\right).$
In the equation above, $0\rangle_A$ represents Alice's qubit being $0\rangle$. Because this system is entangled, Alice's and Bob's states are intrinsically linked. This is best thought of as a single bipartite system rather than two individual qubits, and so local operations on Alice's state will affect the state $\Psi\rangle_{AB}$ of the system as a whole.
Suppose Alice has two classical bits to encode, $\alpha$ and $\beta$, each of which takes value either $0$ or $1$. She encodes the first bit in the parity of her's and Bob's states, i.e. whether they are the same or different. If $\alpha$ is $0$ she does nothing, and so from [eqAliceBobBellPair] Alice's and Bob's qubits will be the same. If $\alpha$ is $1$ she applies a $\sigma_x$ gate to her state, flipping it and resulting in the state
$\sigma_{x,A}\Psi\rangle_{AB}=\frac{1}{\sqrt{2}}\left(1\rangle_A0\rangle_B+0\rangle_A1\rangle_B\right).$
Thus her's and Bob's qubits will always be measured to be opposite.
Alice encodes her second bit $\beta$ in the phase between the two states in the superposition. If $\beta$ is $0$ she again does nothing, however if $\beta$ is $1$ she applies the $\sigma_z$ gate to her state, which will result in a minus sign between the two states.
As we mentioned before, even though Alice is applying these operators locally to her state, the system is an entangled bipartite state, and so we can think of her as applying global operators $\left(\sigma_{i,A}\otimes I_B\right)$, Pauli operators tensored with the identity, to the whole system. After Alice's operations, if $\alpha=0$ the global state will be
[eqFullStateAlphaZero]: $\Psi\rangle_{AB}=\frac{1}{\sqrt{2}}\left(0\rangle_A0\rangle_B\pm1\rangle_A1\rangle_B\right),$
and if $\alpha=1$ the global state will be
[eqGlobalStateAlphaOne]: $\Psi\rangle_{AB}=\frac{1}{\sqrt{2}}\left(0\rangle_A1\rangle_B\pm 1\rangle_A0\rangle_B\right),$
where in both cases the sign is positive if $\beta=0$, and negative if $\beta=1$. Again we note that $\alpha$ is encoded in the parity, whether Alice or Bob's quibts are the same or different, and $\beta$ in the phase between the two superpositions. This phase is the new degree of freedom which we get from entanglement.
Alice then sends her single qubit to Bob, who now possess both states of the bipartite system. Even though Alice has only transmitted a single qubit, because their states were entangled Bob may recover both of the operations that Alice performed. To do this Bob follows the following steps:

To measure the parity Bob applies the CNOT gate on the system, using Alice's bit as the control. If $\alpha=0$, this will send [eqFullStateAlphaZero] to
$CNOT_A\Psi\rangle_{AB} =\frac{1}{\sqrt{2}}\left(0\rangle_A0\rangle_B\pm1\rangle_A0\rangle_B\right),$
$=\frac{1}{\sqrt{2}}\left(0\rangle_A\pm1\rangle_A\right)0\rangle_B,$and if $\alpha=1$ this will send [eqGlobalStateAlphaOne] to
$CNOT_A\Psi\rangle_{AB}=\frac{1}{\sqrt{2}}\left(0\rangle_A\pm1\rangle_A\right)1\rangle_B,$
Bob could now deterministically read out the value of $\alpha$ simply by performing a measurement on his qubit!

To measure the phase, Bob applies the Hadamard gate to Alice's qubit. Looking at the two equations above, we see that regardless of Bob's qubit, Alice's is in the superposition
$\frac{1}{\sqrt{2}}\left(0\rangle_A\pm1\rangle_A\right),$
where the sign is positive if $\beta=0$ and negative if $\beta=1$. In the former case the Hadamard gate will send this to $0\rangle_A$, and in the latter to $1\rangle_A$.
We can see then that after this protocol, Bob has the state: $\alpha\beta\rangle$. He may therefore perform a single measurement on the two qubits he possess, and in doing so learn the value of both bits $\alpha$ and $\beta$! Alice thus used one qubit, and one bit of entanglement, to transmit two bits of information to Bob.
Follow @ruvi_l on Twitter for more posts like this, or join the discussion on Reddit:
Notes and further reading #
u/RRumpleTeazzer pointed out that this protocol still involves the transmission of two qubits. We could imagine this as Alice first prepares the entangled state superposition ${\Psi\rangle_{AB}}$, sends one of the qubits to Bob, and then performs the superdense coding protocol on her remaining qubit before sending this to him as well. So really, this is Alice sending two classical bits via two qubits.
What I think still makes this process surprising from a classical point of view is that all of Alice's encoding happens after Bob already has the first qubit. They begin by sharing the resource of an entangled state, Alice encodes two classical bits on her qubit, and then sends this to Bob who can decode them both. Of course from the quantum point of view this is perfectly natural; since this is a bipartite entangled state, it is better to think of Alice performing operations on the global state ${\Psi\rangle_{AB}}$, rather than on 'her qubit'. As u/RRumpleTeazzer's says, 'delayed choice coding' is perhaps an equally good name.
u/NidStyles and u/gabeff asked about experimental implementations of superdense coding. The first implementation was in 1996 (see References) and used photons as qubits, where ${0\rangle}$ and ${1\rangle}$ were the Horizontal and Vertical polarisation states ${H\rangle}$ and ${V\rangle}$. The initial superposition was created using a process called 'spontaneous parameteric downconversion', where a nonlinear crystal creates pairs of photons whose polarisations are entangled with each other:
$\Psi\rangle=\frac{1}{2}\left(H\rangleH\rangle+V\rangleV\rangle\right).$
The problem with this experiment however was that Bob could only measure three of Alice's four possible messages. These four messages were:
$\Psi^+\rangle=\frac{1}{2}\left(H\rangleV\rangle+V\rangleH\rangle\right),$
$\Psi^\rangle=\frac{1}{2}\left(H\rangleV\rangleV\rangleH\rangle\right),$
$\Phi^+\rangle=\frac{1}{2}\left(H\rangleH\rangle+V\rangleV\rangle\right),$
$\Phi^\rangle=\frac{1}{2}\left(H\rangleH\rangleV\rangleV\rangle\right).$
The experimenters interfered these in such a way that you could distinguish states which were symmetric in interchanging the photons from states which were antisymemtric. We can see above that ${\Psi^\rangle}$ is the only antisymmetric state (if you swap the two photons this is the only one which picks up a minus sign), and so this one could be immediately read out. For the other three, they passed them through a scheme which could determine if the photons had the same or different polarisations. If they were different, this corresponded to ${\Psi^+\rangle}$. If they were the same however it could be either of ${\Phi^+\rangle}$ or ${\Phi^\rangle}$, with no way of distinguishing them further.
These difficulties were resolved in a later experiment in 2008 (again see References). In this, each qubit was composed two photons rather than one, with the first of each pair entangled in polarisation, and the second in angular momentum. This extra degree of freedom allowed the experimenters to distinguish the four possible messages.
Because of the intricacies of the setups, both of these should be seen as more 'proof of principle' than scalable methods for quantum communication.
References #
John Watrous's Lecture Notes 'Introduction to Quantum Computing (Winter 2006)'. See Lecture 3: 'Superdense coding; quantum circuits; and partial measurements'  https://cs.uwaterloo.ca/~watrous/LectureNotes.html.
Also check out the original paper:
Bennett, C. H., & Wiesner, S. J. (1992). Communication via one and twoparticle operators on EinsteinPodolsky Rosen states. Physical Review Letters, 69(20), 2881–2884. http://doi.org/10.1103/PhysRevLett.69.2881
The first experimental implementation was in 1996 using photons as qubits, however in this one Bob could only recover three out of the four possible messages:
Mattle, K., Weinfurter, H., Kwiat, P. G., & Zeilinger, A. (1996). Dense coding in experimental quantum communication. Physical Review Letters, 76(25), 4656–4659. http://doi.org/10.1103/PhysRevLett.76.4656
A newer implementation in 2008 allowed Bob to decode all four messages. This was done by composing each qubit of two photons, rather than one:
Barreiro, J. T., Wei, T. C., & Kwiat, P. G. (2008). Beating the channel capacity limit for linear photonic superdense coding. Nature Physics, 4(4), 282–286. http://doi.org/10.1038/nphys919