Classical simulation complexity of extended Clifford circuits

Understand

Clifford gates are a winsome class of quantum operations combining mathematical elegance with physical significance.

• The Gottesman-Knill theorem asserts that Clifford computations can be classically efficiently simulated but this is true only in a suitably restricted setting.
• Here we consider Clifford computations with a variety of additional ingredients: (a) strong vs.
• weak simulation, (b) inputs being computational basis states vs.