Problem 268771 · medium · Quantum Computing · Level 02 Qubits and Gates

Rewinding the Pulse Schedule

inverse gates · conjugate transpose · quantum circuits · rotation gates

A lab notebook records a pulse schedule and the qubit's state after it, but the page with the starting state is lost. Because every gate U is unitary, its inverse is its conjugate transpose U^\dagger (swap rows and columns and conjugate every entry), and a schedule can be rewound.

A schedule is a list of gates applied left to right. Each gate is either a name or a rotation pair (i is 1j):

  • "i", "x", "y", "z", "h": I=\begin{pmatrix}1&0\\0&1\end{pmatrix}, 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", "sdg", "t", "tdg": S=\mathrm{diag}(1, i), S^\dagger=\mathrm{diag}(1, -i), T=\mathrm{diag}(1, e^{i\pi/4}), T^\dagger=\mathrm{diag}(1, e^{-i\pi/4})
  • ("rx", theta), ("ry", theta), ("rz", theta): 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}

A matrix is a list of rows, and a gate turns [a, b] into [U[0][0]*a + U[0][1]*b, U[1][0]*a + U[1][1]*b].

Write rewind(gates, final) that returns a pair (undo, start):

  1. undo, the schedule that takes the final state back to the starting state: one entry per gate of gates, each entry being the gate whose matrix is exactly U^\dagger of the gate it undoes, written in the same format. For a rotation use the negated angle -theta (not -theta + 4 * math.pi or any other angle with the same matrix). Keep "i" entries.
  2. start, the state you get by running undo on final. Any global phase of start is accepted: [1j, 0] is the same state as [1, 0].

Examples

Input:  gates = ["h", "s"], final = [0.7071067811865475, 0.7071067811865475j]
Output: (["sdg", "h"], [1, 0])

Input:  gates = [("ry", 0.5), "t", "x"], final = [0, 1]
Output: (["x", "tdg", ("ry", -0.5)], [0.9689124217106447, -0.24740395925452294])

Input:  gates = [], final = [0.6, 0.8]
Output: ([], [0.6, 0.8])

Constraints

  • 0 <= len(gates) <= 200; rotation angles satisfy -20 <= theta <= 20
  • final is normalised; amplitudes and angles are compared with a tolerance of 1e-6

Goals

  • Undo a circuit by applying the inverse gates in reverse order
  • Use the conjugate transpose (dagger) as the inverse of a unitary gate
  • Recover the starting state from the final state
Starting Python…