Problem 666611 · medium · Quantum Computing · Level 06 Noise and Error Correction

Keep These Qubits, Forget the Rest

partial trace · reduced density matrix · bit order · bit manipulation

A register of n qubits is in the normalised state state (a list of 2^n complex amplitudes). Basis state |b_0 b_1 \dots b_{n-1}\rangle has index int("b0b1...", 2): qubit 0 is the leftmost bit (in 3 qubits, |011\rangle is index 3, and qubit 0 is 0 there while qubits 1 and 2 are 1).

You only get to look at the qubits in the list keep. Everything you can learn about them is in their reduced density matrix. Split every index i into two bit strings: k(i), the bits of the kept qubits, and r(i), the bits of all other qubits. Then

(\rho_{\text{keep}})_{k,k'} = \sum_{r} \psi_{(k,r)}\,\overline{\psi_{(k',r)}},

where \psi_{(k,r)} is the amplitude whose kept bits are k and other bits are r, the bar is the complex conjugate, and the sum runs over every value of the other bits. Rows and columns of the result are numbered by the kept bits in the order of keep, which is increasing: keep[0] is the leftmost (most significant) bit of a row number. If keep = [0, 2], row 1 of the result means qubit 0 is 0 and qubit 2 is 1.

Write reduced_state(state, keep) that returns the 2^m \times 2^m reduced density matrix (m = len(keep)) as a list of rows. If keep holds every qubit, the answer is the density matrix \rho_{ij} = \psi_i\overline{\psi_j} of the whole state.

Examples

Input:  state = [0.7071067811865476, 0, 0, 0, 0, 0, 0, 0.7071067811865476], keep = [0]
Output: [[0.5, 0], [0, 0.5]]
Explanation: (|000> + |111>)/sqrt(2): one qubit of it alone is I/2.

Input:  state = [0.7071067811865476, 0, 0, 0.7071067811865476, 0, 0, 0, 0], keep = [0]
Output: [[1, 0], [0, 0]]
Explanation: (|000> + |011>)/sqrt(2): qubit 0 is 0 in both terms.

Input:  state = [0.7071067811865476, 0, 0, 0.7071067811865476, 0, 0, 0, 0], keep = [0, 2]
Output: [[0.5, 0, 0, 0], [0, 0.5, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
Explanation: the kept bits (qubit 0, qubit 2) are 00 in |000> and 01 in |011>;
qubit 1 differs between the terms, so they do not interfere.

Constraints

  • 1 to 8 qubits; keep has 1 to 3 distinct qubits in increasing order.
  • Entries may be ints, floats or complex numbers; each is compared with a tolerance of 1e-6.

Goals

  • Compute the reduced density matrix of any set of qubits of an n-qubit state
  • Split each basis index into the bits of the kept qubits and the bits of the rest
Starting Python…