The Qubit Returns

Represent the four states by $0,1,2,3$. The action of each gate is the following permutation.

• H: $(2,3,0,1)$
• X: $(1,0,2,3)$
• Z: $(0,1,3,2)$

Fix the left endpoint $l$ and move the right endpoint $r$ from $l$ to $N$. Initially, the four resulting states are $0,1,2,3$. When gate is added, apply its permutation to all four current results. If the results become again, add interval to the answer.

Repeat this for every $l$. The time complexity is $O(N^2)$, and the additional space complexity is $O(1)$.

Solution written by GPT6