The controlled-NOT gate, CNOT(control c, target t), works on two qubits of a register: in every basis state where qubit c reads 1 it flips qubit t, and where qubit c reads 0 it does nothing. On a state of 2^n amplitudes that means: for every basis index whose bit for qubit c is 1, the amplitude moves to the index with qubit t's bit flipped (and the amplitudes of indices with qubit c reading 0 stay where they are). The two qubits need not be neighbours, and c may be larger or smaller than t.
Bit order: basis state |b_0 b_1 \dots b_{n-1}\rangle has index int("b0b1...", 2), so qubit 0 is the leftmost bit, the most significant. In 3 qubits, |011\rangle is index 3.
Write apply_cnot(state, control, target) that returns the new state (a list or a numpy array). Any global phase is accepted: [1j, 0] is the same state as [1, 0].
The larger tests use two helpers that you can also call: test_state(n, seed) returns a normalised state of n qubits, and peek(state) returns 8 of its amplitudes, [state[(j * 40503) % len(state)] for j in range(1, 9)], so that the expected answer stays short.
Examples
Input: state = [0, 0, 1, 0], control = 0, target = 1
Output: [0, 0, 0, 1]
Explanation: the register is in |10>: qubit 0 reads 1, so qubit 1 flips, giving |11>.
Input: state = [0, 0, 1, 0], control = 1, target = 0
Output: [0, 0, 1, 0]
Explanation: in |10> qubit 1 reads 0, so nothing happens.
Input: state = [0.6, 0, 0, 0, 0, 0.8, 0, 0], control = 2, target = 0
Output: [0.6, 0.8, 0, 0, 0, 0, 0, 0]
Explanation: index 5 is |101>; qubit 2 reads 1, so qubit 0 flips: |001>, index 1.
Constraints
- the register has 2 to 16 qubits, and
control != target - amplitudes are compared with a tolerance of
1e-6
Goals
- Apply a controlled-NOT between any two qubits of a register, adjacent or not
- Treat control and target in either order
- Move amplitudes between basis states by flipping one bit of the index