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.

  • $\begingroup$ "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? $\endgroup$ May 14, 2015 at 13:22
  • $\begingroup$ @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$. $\endgroup$ May 14, 2015 at 19:00
  • $\begingroup$ @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$. $\endgroup$
    – angliru
    May 16, 2015 at 9:08
  • $\begingroup$ 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? $\endgroup$ May 16, 2015 at 16:25
  • 1
    $\begingroup$ @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. $\endgroup$ Jul 29, 2015 at 15:02

1 Answer 1


Brief (negative) answer

This claim is incorrect as soon as you have three (or more) qubits, as shown by the GHZ paradox, briefly described below, which shows a 3-partite Bell inequality which is beaten by a state stabilized by Pauli operators, which can be prepared and measured by Clifford operations. This paradox is named after Greenberger, Horne and Zeilinger, who found it in 1989 (2007 arXiv reprint here).

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.

On the other hand Bell inequalities characterize local hidden variable theories, without taking care of their complexity. The violation of a Bell inequality by the GHZ states means that it cannot be described by a model where each player has access to a different local hidden variable.

Details of the GHZ paradox

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.