Superdense Coding

Superdense Coding

Superdense coding is the quantum-classical dual of teleportation: where teleportation sends 1 qubit using 2 classical bits, superdense coding sends 2 classical bits using only 1 qubit — provided Alice and Bob share a pre-established Bell pair.

This result is remarkable: no classical protocol can transmit 2 bits of information by sending a single bit. Entanglement is the resource that makes it possible.

The Bell Pair

Alice and Bob start by sharing the Bell state:

$|\Phi^+\rangle = \frac{|00\rangle + |11\rangle}{\sqrt{2}}$

Alice holds qubit 0 (the first qubit); Bob holds qubit 1.

Encoding

Alice encodes two classical bits $(b_0, b_1)$ by applying a gate to her qubit only:

The four resulting states are the four Bell states — an orthonormal basis.

Decoding

Bob receives Alice's qubit and applies:

1. CNOT (Alice's qubit as control, Bob's as target)
2. Hadamard on Alice's qubit

This uncomputes the Bell circuit and leaves the two qubits in one of $|00\rangle$, $|01\rangle$, $|10\rangle$, $|11\rangle$, which Bob measures directly.

State-Vector Convention

Index the 2-qubit computational basis as: $[|00\rangle,\; |01\rangle,\; |10\rangle,\; |11\rangle]$

so state[i] is the amplitude of the basis state whose binary representation is $i$.

Verifying the Decode Circuit

For each encoded Bell state, CNOT maps $|10\rangle \to |11\rangle$ and $|11\rangle \to |10\rangle$ (swaps entries 2 and 3), then $H$ on qubit 0 maps: $\frac{|0x\rangle \pm |1x\rangle}{\sqrt{2}} \to |0x\rangle \text{ or } |1x\rangle$

You can verify all four cases in the solution walkthrough above.

Your Task

Implement two functions:

1. encode_superdense(b0, b1) — return the 4-element complex state vector after Alice applies her encoding gate to $|\Phi^+\rangle$.
2. decode_superdense(state) — apply the CNOT + H decode circuit and return the recovered bits as a tuple (b0, b1).