A register of n qubits holds a state of 2^n amplitudes, and a gate on the whole register is a 2^n\times 2^n matrix (a list of rows, m[row][col]) that acts as new = M @ state. A single-qubit gate G (a 2\times 2 matrix) applied to qubit k only, with every other qubit left alone, has the full matrix
a Kronecker product of n factors in the order of the qubits, qubit 0 first: factor number k is G and all others are the 2\times 2 identity I. (The Kronecker product A\otimes B replaces each entry A_{ij} by the block A_{ij}B.)
The order matches the bit order of this path: 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 embed_gate(gate, k, n) that returns M as a list of 2^n rows (a numpy array is fine too).
Examples
Input: gate = [[0, 1], [1, 0]], k = 0, n = 2
Output: [[0, 0, 1, 0], [0, 0, 0, 1], [1, 0, 0, 0], [0, 1, 0, 0]]
Explanation: X on qubit 0 flips the leftmost bit: |00> <-> |10> (0 <-> 2) and |01> <-> |11> (1 <-> 3).
Input: gate = [[0, 1], [1, 0]], k = 1, n = 2
Output: [[0, 1, 0, 0], [1, 0, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0]]
Input: gate = [[1, 0], [0, 1j]], k = 0, n = 1
Output: [[1, 0], [0, 1j]]
Constraints
- entries are compared with a tolerance of
1e-6
Goals
- Build the full 2^n x 2^n matrix of a gate that acts on one qubit of a register
- Place the gate among identity matrices in the order of the qubits, qubit 0 first