The Improved Simulation Algorithm [2] and Two Strategies for Simulating Mixed States

[Fe-r-oz]

Hi, Stefan,

This flowchart is based on the improved simulation algorithm O(n^2) given in "Improved Simulation of Stabilizer Circuits" by Aaronson and Gottesman.

Assumption: Tableau is in form presented in the paper and the rowsum subroutine.

Is the improved algorithm mentioned in the paper implemented exactly here? I hope we can use it in the documentation somehow?

If there is any improvements needed in the flowchart, please let me know.

[Fe-r-oz]

In a similar vein, the paper mentions that "Mixed states could be simulated by simply purifying the state, and then simulating the purification, but we present an alternative and slightly more efficient strategy." They end up presenting two algorithms/strategies, the second algorithm is related [1] to the improved-algorithm that is presented above.

Which is these two strategies is implemented for simulating Mixed states?

We can provide one of these flowcharts for MixedDestabilizer representing the selected algorithm/strategy utilized here.

And what about non-stabilizer initial states, non-stabilizer gates? (slightly off topic question w.r.t this context)

Suggestion 3 was quite rough. It was about creating a schematic representing the 3 types of states when we go beyond stabilizer states. So, I explored and broken it down a bit further. Since, each of these 3 sections, mixed states, non-stabilizer gates, non-stabilizer initial states are covered in quite detail, I have first explored Mixed states first.

The paper presents 2 strategies for simulating Mixed States as follows:

Algorithm 1

Algorithm 2:

Comment from authors is that "We can keep track of this new kind of tableau in much the same way as the old kind. Unitary operations transform the new rows the same way as rows of the stabilizer or destabilizer [1] ."

Note: In dark mode, the arrows might not be visible for these two algorithms, but there is a way to make them vision!

I look forward to your insights!

[Fe-r-oz]

And what about non-stabilizer initial states, non-stabilizer gates?

In the non-stabilizer initial state section, it is said ""We do allow classical operations conditioned on the outcomes of measurements, so we also allow polynomial-time classical computation during the circuit."" This seems similar to the Gates conditioned on classical bits, right? https://quantumsavory.github.io/QuantumClifford.jl/stable/noisycircuits_ops/#Gates-Conditioned-on-Classical-Bits. I guess that at the moment, we have Mixed state (Section VII. A) implemented here, not the other two.

[Krastanov]

Is the improved algorithm mentioned in the paper implemented exactly here? I hope we can use it in the documentation somehow?

Yes, that exact algorithm is implemented. It is what is used when dispatching on (Mixed)Destabilizer.

Which is these two strategies is implemented for simulating Mixed states?

Mixed stabilizer states (either in MixedStabilizer or MixedDestabilizer) are represented by tableaux with fewer rows than columns, implicitly representing the equal mixture of all pure stabilizer states that obey the incomplete constraints of the tableau.

And what about non-stabilizer initial states, non-stabilizer gates? (slightly off topic question w.r.t this context)

They are implemented in a completely different manner, as a weighted list of pure stabilizer states (i.e. we need (a potentially exponentially long) list of Destabilizer objects).

This seems similar to the Gates conditioned on classical bits, right?

Yup.

[Fe-r-oz]

That's Cool!