Problem 363943 · medium · Quantum Computing · Level 03 Entanglement

The Simulator Runs a Whole Schedule

state-vector simulation · quantum circuits · CNOT gate · rotation gates

This is the core of the simulator you are building. A register of n qubits starts in |0\dots0\rangle (amplitude 1 at index 0, all others 0), and a schedule ops is applied left to right, first ops[0]. Each operation is a tuple (or list) whose first entry is a lower-case name:

  • ("x", q), ("y", q), ("z", q), ("h", q), ("s", q), ("t", q): a named gate on qubit q, with X=\begin{pmatrix}0&1\\1&0\end{pmatrix}, Y=\begin{pmatrix}0&-i\\i&0\end{pmatrix}, Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix}, H=\tfrac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}, S=\begin{pmatrix}1&0\\0&i\end{pmatrix}, T=\begin{pmatrix}1&0\\0&e^{i\pi/4}\end{pmatrix};
  • ("rx", q, theta), ("ry", q, theta), ("rz", q, theta): a rotation by the angle theta (radians) on qubit q, with R_x(\theta)=\begin{pmatrix}\cos\frac\theta2&-i\sin\frac\theta2\\-i\sin\frac\theta2&\cos\frac\theta2\end{pmatrix}, R_y(\theta)=\begin{pmatrix}\cos\frac\theta2&-\sin\frac\theta2\\\sin\frac\theta2&\cos\frac\theta2\end{pmatrix}, R_z(\theta)=\begin{pmatrix}e^{-i\theta/2}&0\\0&e^{i\theta/2}\end{pmatrix};
  • ("cx", c, t): CNOT, which flips qubit t in every basis state where qubit c reads 1;
  • ("cz", a, b): multiplies the amplitude of every basis state where qubits a and b both read 1 by -1;
  • ("swap", a, b): exchanges qubits a and b (the amplitude of each basis state moves to the index with those two bits exchanged).

A single-qubit gate G on qubit q acts as the full matrix I\otimes\dots\otimes G\otimes\dots\otimes I (G in place q, qubit 0's factor first). In two-qubit operations the two qubits are different, and either may be the larger.

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 run_register(n, ops) that returns the final state, 2^n amplitudes (a list or a numpy array). Any global phase is accepted: [1j, 0] is the same state as [1, 0]. The larger tests use the helper peek(state), which returns 8 amplitudes, [state[(j * 40503) % len(state)] for j in range(1, 9)].

Examples

Input:  n = 2, ops = [("x", 0)]
Output: [0, 0, 1, 0]
Explanation: X on qubit 0 (the leftmost bit) gives |10>, index 2.

Input:  n = 2, ops = [("h", 0), ("cx", 0, 1)]
Output: [0.7071067811865475, 0, 0, 0.7071067811865475]

Input:  n = 3, ops = [("x", 2), ("ry", 0, 1.2), ("cx", 2, 1), ("rz", 1, 0.5)]
Output: [0, 0, 0, 0.8253356149096783, 0, 0, 0, 0.5646424733950354]
Explanation: |001>, then cos(0.6)|001> + sin(0.6)|101>; qubit 2 reads 1, so qubit 1 flips:
cos(0.6)|011> + sin(0.6)|111>. Qubit 1 reads 1 in both, so Rz only multiplies the whole state by e^{0.25i}.

Constraints

  • 1 <= n <= 11, 0 <= len(ops) <= 150
  • amplitudes are compared with a tolerance of 1e-6

Goals

  • Simulate a multi-qubit circuit from |0...0> by applying its operations in order
  • Dispatch single-qubit gates, rotations and two-qubit gates from one list
  • Keep every gate on the right qubits, with qubit 0 as the leftmost bit
Starting Python…