<h1>Brief (negative) answer</h1>

<p>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 (<a href="http://arxiv.org/abs/0712.0921" rel="nofollow">2007 arXiv reprint here</a>).</p>

<p>The point is that the Gottesman-Knill theorem does not care about locality, but on simplicity. The Gottesmann-Knill theorem (<a href="https://en.wikipedia.org/wiki/Gottesman%E2%80%93Knill_theorem" rel="nofollow">wiki</a>, <a href="http://arxiv.org/abs/quant-ph/9807006v1" rel="nofollow">arXiv</a>) 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.</p>

<p>On the other hand Bell inequalities characterize <em>local</em> 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.</p>

<h1>Details of the GHZ paradox</h1>

<p>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&amp;=+1\\XYY&amp;=-1\\YXY&amp;=-1 \\YYX&amp;=-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.</p>

<p>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&amp;=+XXX\\S_1&amp;=-XYY\\S_2&amp;=-YXY \\S_3&amp;=-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.</p>

CC BY-SA 3.0
2015-07-29T12:03:39.333Z
2015-07-29T14:56:46.870Z
2015-07-29T14:56:46.870Z
Frédéric Grosshans
<p>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.</p>

<p>I want to understand the claims presented in <a href="http://core.ac.uk/download/pdf/11923581.pdf" rel="nofollow">http://core.ac.uk/download/pdf/11923581.pdf</a> .
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): </p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2015-05-14T13:22:56.290Z
"*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
CC BY-SA 3.0
2015-05-14T19:00:19.980Z
@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 
CC BY-SA 3.0
2015-05-16T09:08:37.067Z
@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
CC BY-SA 3.0
2015-05-16T16:25:59.747Z
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
CC BY-SA 3.0
2015-07-29T15:02:42.093Z
@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
<quantum-computing>
Understanding efficient classical simulation of quantum computing
angliru
# Understanding efficient classical simulation of quantum computing

(Asked by: username_0 on 2015-05-14)

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.

**Tags:** quantum-computing
> **Comments:**
> **username_1**: "*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?  
> **username_2**: @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$.  
> **username_0**: @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$.  
> **username_1**: 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?  
> **username_3**: @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.  

---

## 1 answers

### Answer by username_3 on 2015-07-29. Score: 2

# 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](http://arxiv.org/abs/0712.0921)).

The point is that the Gottesman-Knill theorem does not care about locality, but on simplicity. The Gottesmann-Knill theorem ([wiki](https://en.wikipedia.org/wiki/Gottesman%E2%80%93Knill_theorem), [arXiv](http://arxiv.org/abs/quant-ph/9807006v1)) 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.


---

