Different Pulses, Same Gate? · Python problem 230591

Two engineers wrote different pulse schedules for the same qubit and want to know whether they do the same thing. A schedule is a list of gate names applied left to right; its matrix M is the product of the gate matrices in reverse order (the last gate on the left), the identity for an empty list. The names are (i is 1j):

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=\begin{pmatrix}1&0\\0&i\end{pmatrix},\ T=\begin{pmatrix}1&0\\0&e^{i\pi/4}\end{pmatrix}

written "i", "x", "y", "z", "h", "s", "t".

Two schedules have the same effect on every state, as far as any measurement can tell, exactly when their matrices are equal up to a global phase: there is one complex number c with |c| = 1 such that M_1 = c\,M_2, entry by entry. For example XZ is -ZX, so ["x", "z"] and ["z", "x"] have the same effect, with c=-1.

Write same_effect(first, second) that returns True if the matrices of the two schedules are equal up to a global phase, else False. Treat entries as equal when they differ by at most 1e-6; in the tests two schedules are either equal up to phase (to rounding error) or differ by more than 0.1 in some entry for every choice of c.

Examples

Input:  first = ["h", "z", "h"], second = ["x"]
Output: True
Explanation: HZH is exactly X.

Input:  first = ["s"], second = ["z"]
Output: False
Explanation: all entries have the same size, but S has i where Z has -1,
and the top-left entries (both 1) force c = 1.

Input:  first = ["x", "z"], second = ["z", "x"]
Output: True

Constraints

0 <= len(first), len(second) <= 500

Goals

Decide whether two circuits are equal up to a global phase
Find the phase factor from one reliable entry and check every other entry with it
Discover identities such as HZH = X and TT = S