A register of n qubits is in the state state, a list of 2^n complex amplitudes. A single-qubit gate gate (a 2\times 2 matrix as a list of rows, gate[row][col]) acts on qubit k and leaves the other qubits alone. Its full matrix is the Kronecker product I\otimes\dots\otimes G\otimes\dots\otimes I of n factors, qubit 0's factor first, with G in place k and the 2\times 2 identity I everywhere else; the new state is that matrix times state.
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.
The simulator you are building has to handle registers of up to 18 qubits, where the full matrix would have 2^{36}\approx 7\cdot 10^{10} entries: far too many to build. Write apply_on_qubit(state, gate, k) that returns the new state (a list or a numpy array) without building it. Any global phase is accepted: [1j, 0] is the same state as [1, 0].
The large 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 = [1, 0, 0, 0], gate = [[0.7071067811865475, 0.7071067811865475], [0.7071067811865475, -0.7071067811865475]], k = 0
Output: [0.7071067811865475, 0, 0.7071067811865475, 0]
Explanation: H on qubit 0 (the leftmost bit) mixes |00> (index 0) with |10> (index 2).
Input: state = [0, 0.6, 0, 0.8], gate = [[0, 1], [1, 0]], k = 1
Output: [0.6, 0, 0.8, 0]
Explanation: X on qubit 1 swaps index 0 with 1 and index 2 with 3.
Input: state = [0.6, 0.8j], gate = [[1, 0], [0, 1j]], k = 0
Output: [0.6, -0.8]
Constraints
- the register has 1 to 18 qubits; the hidden tests use 16 and 18 qubits, so do not build the 2^n\times 2^n matrix
- a plain-Python loop over the amplitudes is fast enough; numpy (
reshape) is faster still - amplitudes are compared with a tolerance of
1e-6
Goals
- Apply a single-qubit gate to one qubit of a large register without building the 2^n x 2^n matrix
- Pair up the basis states that differ only in qubit k's bit
- Find qubit k's bit with qubit 0 as the leftmost, most significant bit