# Understanding efficient classical simulation of quantum computing

I want to understand the Gottesman-Knill theorem, which basically says that using some subclass of unitary transformations (from the Clifford group) there is no quantum speed-up ie. we can simulate the system efficiently on a classical computer.

I want to understand the claims presented in http://core.ac.uk/download/pdf/11923581.pdf . The author says that the reason that using only Clifford group brings efficient classical simulation is because the transformations in Clifford group inlcude only rotations of the Bloch sphere by multiples of $\pi/2$. He then goes on to explain that these transformations don't violate Bell's inequalities (specifically CHSH inequalities):

In an entangled quantum system, no amount of $k\pi/2$ transformations of one of the constituent systems will cause it to take on an orientation with respect to the other subsystems that is not a multiple of $\pi/2$ (unless it was so oriented initially).And as we have seen above, the statistics of compound states for which the difference in orientation between subsystems is a multiple of $\pi/2$ are capable in general of being reproduced by a classical hidden variables theory.

I wan't to know if this claim is correct and first of all, I would be happy if someone explained this to me on an example. I heard that stabilizer formalism can violate Bell's inequalities so this is all weird to me.

PS. My basic intention is to have a clearer picture of why some subclass of transformations can be efficiently simulated classicaly and I thought this would be a nice way to understand it (if of course it is true). If anyone has any other ideas as to how to explain the Gottesman-Knill (besides stabilizer formalism), I would be very happy.

• "As we have seen above, the statistics of compound states for which the difference in orientation between subsystems is a multiple of π/2 are capable in general of being reproduced by a classical hidden variables theory." How does that text treat EPR pairs, which may be prepared by Clifford group operations? – Niel de Beaudrap May 14 '15 at 13:22
• @Niel: I think the idea is that you need to measure Bell pairs in bases which differ from each other by rotations of $\pi/2$. – Peter Shor May 14 '15 at 19:00
• @Niel: As Peter Shor has pointed out, measuring Bell pairs at angles of experimental devices which differ by $k\pi/2$ doesn't violate Bell inequalities. For example, for the singlet two-qubit state QM predicts $- \cos (\theta)$, whereas LHV model predicts $2\theta/\pi - 1$. You can see that they agree at angles $\theta = 0, \pi/2$ and $\pi$. – angliru May 16 '15 at 9:08
• And how does one simulate the transformation of those hidden variables under entangling (and disentangling) operations? What means ought one to use to determine what correlations the hidden variable model ought to represent for the final state? – Niel de Beaudrap May 16 '15 at 16:25
• @PeterShor : I understand the argument the same way. To violate CHSH, you need non-Clifford gates in the measurement (or in the preparation). I know this intuition has been widely held, at least in the French quantum optics community. However, this argument is wrong with 3 qubits or more, since the GHZ paradox is a Bell inequality using only Pauli operators. – Frédéric Grosshans Jul 29 '15 at 15:02

The point is that the Gottesman-Knill theorem does not care about locality, but on simplicity. The Gottesmann-Knill theorem (wiki, arXiv) gives a polynomial hidden variable theory for a state constructed with Clifford gates. Nothing prevents this theory to be nonlocal, as the GHZ state shows, but its complexity is bounded : a $n$-qubit state is described by $2n²$ binary hidden variables.
The paradox can be explained by the following game, with 3 cooperating players and a referee. the referee asks a question, either $X$ or $Y$ to each player, which answers ±1 without communicating with the other players. The referee either asks $X$ to all the players or asks $X$ to one of them and $Y$ to the others. The players win if the product of their answers obeys the equality below corresponding to the question asked: \begin{align} XXX&=+1\\XYY&=-1\\YXY&=-1 \\YYX&=-1 \end{align} It is easy to see that the above set of equation is not consistent, and tha no local hidden variable theory allows to win the game with a probabiliyt greater than 3/4.
On the other hand, if each of the player has a qubit of a GHZ state $|\mathrm{GHZ}\rangle:=(|000\rangle+|111\rangle)/\sqrt2$, they can win with certainty. Indeed, $|\mathrm{GHZ}\rangle$ is stabilized by the following Pauli operators : \begin{align} S_0&=+XXX\\S_1&=-XYY\\S_2&=-YXY \\S_3&=-YYX. \end{align} Therefore, measuring the Pauli operators corresponding to the referee’s question allows the players to always win the game, and therefore violate a Bell inequality with certainty. Furthermore, this state can be prepared from Clifford operations, which invalidates the idea expressed in the paragraph you cite.