Optimize clifford/non-clifford matching optimization by calculating qubit states

[Strilanc]

Currently, the optimization that removes non-Clifford operations and merges them does so by individually moving them through the circuit. If there are C cliffords and N non-cliffords, it takes N*C time.

What we should do instead is assign the k'th qubit an initial Pauli string of X_k for its X observable and Z_k for its Z observable. Then we iterate through the circuit, ignoring non-Cifford operations but modifying those Pauli strings with the Clifford operations, and keeping track of the string assigned to each qubit after each operation.

For example, start with a circuit:

-----@-----@-----
     |     |
--T--X--T--X--T--

Assign initial strings:

For example, start with a circuit:

(x0,z0)-----@-----@-----
            |     |
(x1,z1)--T--X--T--X--T--

Iterate through ignoring non-cliffords while tracking the strings:

(x0,z0)----(x0,z0)-@-----@-----
                   |     |
(x1,z1)--T-(x1,z1)-X--T--X--T--

But update based on Cliffords:

(x0,z0)----(x0,z0)-@-(x0,z0*x1)----@-----
                   |               |
(x1,z1)--T-(x1,z1)-X-(x1*z0,z1)-T--X--T--

Do the whole thing:

(x0,z0)----(x0,z0)-@-(x0,z0*x1)----@-(x0,z0)----
                   |                         |
(x1,z1)--T-(x1,z1)-X-(x1*z0,z1)-T-(x1*z0,z1)-X-(x1,z1)-T--

The non-clifford operations are now preceded by the Pauli string that they should be assigned. This took time O(C+N) instead of O(N*C). We also don't need to worry about finding where the Non-cliffords returns to, since they are still in place. All the commutes-or-not computations stay the same, and generally this should just make things faster.

[daxfohl]

I'd like to try this one, but @Strilanc can you flesh out the final step a bit more? Plugging your original circuit into the existing optimizer we get

0: ───Y^-0.5───@───[X]^-0.25───@───Y^0.5───
               │               │
1: ────────────@───────────────@───Z^0.5───

I'm not quite seeing how to get from your final step above to this final representation.

(Also, I see that the first step of the optimizer calls converted_gate_set, which does all the work--the final circuit comes directly out of that, and the remaining optimizations don't change anything else. So here are you talking about a strategy that skips the call to converted_gate_set?)

https://github.com/quantumlib/Cirq/blob/master/cirq-core/cirq/contrib/paulistring/clifford_optimize.py#L24

[daxfohl]

I'm trying but not entirely sure this is possible. IIUC, you can't arbitrarily jump non Cliffords. They have to be PSPhasors with a matching PS on the qubit of the gate you're moving. So if you're moving them in bulk I don't understand how those assumptions work out.

I think it's still plausible that there's an O(C+N) algorithm, but I'm not seeing how the proposal quite gets there. @Strilanc am I missing something?

[daxfohl]

Xref #2961

[tanujkhattar]

The optimizer lives in contrib and there are very few examples of people using it. We can close this issue for now and reopen if it becomes a bottleneck.