A row of n qubits starts in the basis state |b_0 b_1 \dots b_{n-1}\rangle given by the string bits. Then this circuit runs:
- H on qubit 0, where H = \tfrac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix} (it maps |0\rangle \to (|0\rangle+|1\rangle)/\sqrt2 and |1\rangle \to (|0\rangle-|1\rangle)/\sqrt2),
- then CNOT(0, 1), CNOT(1, 2), ..., CNOT(n-2, n-1), in this order. CNOT(c, t) flips bit t of every basis state whose bit c is 1.
From bits = "000" this makes the GHZ state (|000\rangle + |111\rangle)/\sqrt2: three qubits that, when measured, all show the same random bit.
A state of n qubits is a list of 2^n amplitudes; basis state |b_0 \dots b_{n-1}\rangle has index int("b0...", 2), so qubit 0 is the leftmost bit: in 3 qubits, |011\rangle is index 3.
Write chain_state(bits) that returns the final state as a dict: each bit string whose amplitude has size greater than 1e-9 maps to that amplitude (a real number here). Bit strings with amplitude 0 are not in the dict.
Examples
Input: bits = "000"
Output: {'000': 0.7071067811865475, '111': 0.7071067811865475}
Input: bits = "100"
Output: {'000': 0.7071067811865475, '111': -0.7071067811865475}
Explanation: H turns |1> into (|0> - |1>) / sqrt(2), so |111> gets the minus sign.
Input: bits = "010"
Output: {'011': 0.7071067811865475, '100': 0.7071067811865475}
Explanation: after H: |010> and |110>. CNOT(0, 1) turns |110> into |100>.
CNOT(1, 2) then turns |010> into |011> and leaves |100> alone.
The order of the keys does not matter.
Constraints
1 <= len(bits) <= 10- amplitudes are compared with a tolerance of
1e-6
Goals
- Apply a Hadamard and a chain of CNOTs to an n-qubit basis state
- See that a chain of CNOTs copies one qubit's superposition along the register
- Report a state by its nonzero amplitudes, labelled by bit strings