Quantum Computing #4: Superdense Coding

Previously:

Introduction
Single Qubit Gates
Multiple Qubit Gates
Measurement & Review

Note: Last week's removal of Greek lettering and matrices has proved too popular to ignore, all feedback being either positive or neutral, so I'll continue using this "new" notation wherever possible.

Breaking News! A single qubit can transmit two full classical bits of information.

Not on its own, though. We can only ever encode one single classical bit of information into a solitary, unentangled qubit. But when we have access to an entangled pair, we can choose to send one unmodified to our intended recipient, and encode a full two classical bits into the other. To see how, we'll have to examine four quite similar quantum circuits. And we'll need the help of a new single-qubit gate we haven't met before:

The Z Gate

Like its partner the X gate, Z is a kind of inverter. It maps the input qubit state (a, b) to (a, -b). We say that it inverts the phase of the second basis vector. For the sake of completeness alone, here is its matrix representation:

Preparing the Bell State

The two qubits that we'll be using to perform the superdense coding trick have to be entangled, so first let's see how to achieve that. One way is to prepare them both initially in the 0 state. Next, we pass the first qubit of the pair through a Hadamard gate. Finally, we use the output of the H gate as the control input of a controlled-NOT gate, conditionally inverting the second qubit:

The H gate converts the first 0 into 0+1, where I'm going to use '+' and '-' to mean "normalized vector sum" and "normalized vector difference", just to get rid of all the visual noise generated in the calculations by incessant divisions by √2. Since the second qubit remains at 0, the combined state after the H gate is 00+10. Nothing strange about this so far; all it says is that a measurement on the first qubit will yield either 0 or 1, each with 50% probability, while a measurement on the second qubit will still yield 0, with 100% certainty.

Next, the qubits arrive at the cNOT gate. This has no effect upon the first part 00 of the superposition, since there the control (first) qubit is 0. However the second part, 10, has a 1 in the control bit position, causing the cNOT gate to invert the second qubit. The combined state at the output of the cNOT gate is therefore 00+11.

This is termed a Bell State, and it's actually a fairly remarkable state when you think about it. It says that the qubit pair is in a perfectly balanced superposition of the 00 and 11 states. Expressed as a sequence of renormalized amplitudes, it is

(a, b, c, d) = (1/√2, 0, 0, 1/√2)

Since |a|² = |d|² = ½, while |b|² = |c|² = 0, this says that a measurement is equally likely (50%) to yield 00 or 11, and to do so absolutely randomly; but it can never yield 01 or 10. Now if you measure just one of the qubits, whatever result you obtain, 0 or 1, you'll get exactly the same outcome when you measure the second qubit. Even if it's hours or years later, miles or light years away.

Encoding and Decoding

Remember that both Hadamard gates and inverters are their own inverses. If we were to make a mirror image of the above diagram and then join the two together, our final output state would be the same as the originally prepared 00, with probability 100%. This mirror image decoder is shown below, if we temporarily ignore the "?" gate (imagine it to be just a quantum wire, or an Identity gate I):

Suppose Alice is in charge of the "?" box, and Bob is performing the final measurements. Alice wants to send 2 classical bits of data to Bob, but she's only allowed to operate upon the first of the two qubits (the top one in the diagram) to do it. What should she put in the "?" box?

Well, if the bits she wants to send are 00, then she need apply nothing but a simple quantum wire, since we've just seen that this will result in Bob's measurements yielding the result 00 with 100% certainty. In the more general case, she needs to examine both of the classical bits that she wants to send. If the first is 1, then she should add our new friend the Z gate in place of the "?". If the second is 1, she adds an X. Note that if both bits are 1, she will now have added both a Z and a following X.

00 → I
01 → Z
10 → X
11 → Z followed by X

And that's all there is to the Superdense Coding Protocol. With those arrangements in place, Bob's measurements will always yield, with 100% certainty, the particular combined state 00, 01, 10, or 11 that Alice wanted to send him.

I Don't Believe You

No, you'd be mad to, unless you're already a QC expert! We'll go through the four cases individually in detail. Remember, the starting point for Alice is in each case the Bell State 00+11. It will also be useful to remember the reversibility of the H gate. Just as it converts basis states 0 and 1 respectively into their sum 0+1 and difference 0-1, so when presented with a sum 0+1 at its input, does it output 0; and with a difference 0-1, output 1.

Case 00: We already established, using an argument based on considerations of symmetry, the correct operation of the circuit for this first case. Still, it's worth running through the detailed sequence of decoding steps, since these are the same for all subsequent cases. So: Alice does nothing to the 00+11 state, which is then passed immediately into the second cNOT gate. This has no effect on the 00 portion of its input, but changes the 11 part (because the first, control bit is 1) into 10. The cNOT output is therefore 00+10. The first of these qubits, 0+1, is fed to the second Hadamard, which as mentioned above, converts it to 0. Therefore, the final 2-qubit output is 00, with probability 100%.

Case 01: Alice inserts an X gate in the path of the first qubit, converting the initial 00+11 to 10+01. The cNOT changes this to 11+01, feeding the first qubit 1+0 into H, which outputs 0. Therefore, the final 2-qubit output is 01, with probability 100%.

Case 10: Alice inserts a Z gate in the path of the first qubit, converting the initial 00+11 to 00-11. The cNOT changes this to 00-10, feeding the first qubit 0-1 into H, which outputs 1. Therefore, the final 2-qubit output is 10, with probability 100%.

Case 11: Alice inserts both a Z and a following X into the path of the first qubit, converting the initial 00+11 first to 00-11 as in the previous case, then to 10-01. The cNOT changes this to 11-01, feeding the first qubit 1-0 into H, which outputs 1. Therefore, the final 2-qubit output is 11, with probability 100%.

Quantum Erat Demonstrandum!

The second most surprising thing about Superdense Coding - other than the fact that in reality, it works exactly as advertised! - is the time it took to get itself discovered. The whole subject of Quantum Mechanics was kicked off by Werner Heisenberg in 1925, with Quantum Computing eventually appearing with Richard Feynman in 1982; yet it was a further ten years after that before the definitive Bennett & Wiesner paper appeared, noting that certain "EPR" (Einstein-Podolsky-Rosen) states "allow two bits to be encoded reliably in one spin-½ particle..."

Interactive Demo

The Wolfram Demonstrations Project contains a great interactive demo of the Superdense Coding protocol, one of several contributed by Brad Rubin. This varies a little from the our example, specifically in the order of the X and Z gates during the 11 case, but the difference vanishes during final measurement. You interact with it by downloading the Computable Document Format (CDF) Player, and optionally the Superdense Coding demo file itself, which looks like this:


As you can see, it displays all the intermediate states of the qubits during this quantum computation - and fully normalized, hence all the "1/√2"s.

Footnote

In this series I've been avoiding discussion about the physical realisation of qubits, but the day after I posted this comment on digital simulator Logicly's Facebook page...

Has anyone ever asked for a quantum circuit version? You seem to have all the component building and layout logic that would require. Qubit signals: rather than boolean, these would be pairs of complex numbers (or quadruples of floats), and there would be a "measurement" gate with a classical boolean 0 or 1 output. Now seems a good time to start training up on these!

... noted futurologist and SF author Charles Stross predicted room temperature quantum computing on integrated circuitry within 5 to 20 years, based on a fascinating discovery about silicon carbide. My guess is that many more suitable materials will be discovered quite soon, making available QC technologies that will have absolutely no trouble attracting capital investment at the left hand edge of that range.

Next time: Quantum Teleportation.