[Feature Request] Better QFT Compilation in the Pauli formalism

[gwwatkin]

Issue Description

Our implementation of the Pauli Formalism is very slow - see the benchmark in #258. Additionally it also generates 4x more ls instructions, but there is a chance to generate even fewer.

Proposed Solution

Compilation speed

The slowness, compared to the gate based pipeline, is due to the fact that QFT circuits are dominated by very long single qubit Clifford+T approximations and our pipeline pads single qubit rotations with identities to span the whole width of the circuit. Switching to a sparse format (like in the gate based pipeline) is likeley to speed up this step and drastically reduce memory footprint.

Computation depth

The bottle neck is approximations of arbitrary rotations, where we are going to gates and back, Increasing the length at the computation at every step:

Now, our pipeline is:

rotations -> approximation with gates -> rotations -> instructions

We have the opportunity of using directly Pauli rotations to approximate rotations:

goes rotations -> approximation with rotations -> instructions.

The approximation with rotations translates directly to LS instructions. With this pipeline, we should generate fewer ls instructions than with the gate based pipeline, which still does the Hadamards and separates groups like ZST which are a single Z_7pi/8 rotation

To do that, we reinterpret the Gridsynth approximations, which are in a normal form (as shown below), and cache them directly as rotations. We do so by grouping Zs, Ss and Ts and "sandwiching" them between Hadamard gates, and seeing that as a basis change:
Some gate -> TSHTHTHSTHZSTHTH...
-> TS HTH T HSTH ZST HTH ...
-> Z_3pi/8 HZ_pi/8H Z_pi/8 HZ_3pi/6H Z_5pi/8 HZ_pi/8H...
-> Z_3pi/8 X_pi/8 Z_pi/8 X_3pi/6 Z_7pi/8 X_pi/8 ...

Then these translate directly to ls instructions.

Additional References

If applicable, provide some references that will help us better understand the request.

[isolatedinformation]

What is the status of this issue?

[gwwatkin]

@isolatedinformation No work has been done yet. As by our conversation on Slack, passing it over to you.

CC: @alexnguyenn

[isolatedinformation]

Partly solved by #269! But as mentioned by @gwwatkin LLOPS edge case testing must done for rotations angles like 5pi/8.. raised in issue #271

[gwwatkin]

Also this issue has a part about sparse representation for rotations #269 doesn't address that. Perhaps this is best split it a different issue @isolatedinformation ?

[gwwatkin]

We won't be able to compile the 128 QFT without sparse representation