Quantum circuits composed by Clifford gates can be simulated by classical computation in polynomial time. More precisely, this simulation should be a weak simulation, i.e. it is possible to sample the outcome of measurements of the output state of the circuit. This is stated, e.g., here

An explicit method for sampling the outcome of the measurement is given in the above mentioned paper and here. In both cases, the used formalism is different from the most traditional one, based on normalizer groups and stabilizers.

This latter formalism was used in the seminal paper of Gottesman (with Knill in references.). Very roughly, the original idea was to use the Heisenberg representation. Instead of having a vector $\left|\Psi\right>$ that evolves like $O\left|\Psi\right>$, there is an operator $N$ evolving as $O^{\dagger}NO$. When $N$ is chosen in the Pauli group, and $O$ is the evolution generated by a quantum circuit made of Clifford gates, then $O^{\dagger}NO$ remains in the Pauli group. The representation of $N$ and its evolution under the Clifford gates can be done quickly by classical calculation.

It is thus possible to efficiently compute the expectation values $\left<\Psi\right|O^{\dagger}NO\left|\Psi\right>$, but this should be a task for strong simulation.

To deal with states, it is noticed that a state $\left|\Psi\right>$ is uniquely defined by giving $n$ operators $N_n$ (belonging to the Pauli group), such that $N_n\left|\Psi\right>=\left|\Psi\right>$. If we want to use the Gottesman formalism for weak simulation, it should be possible to classically sample the outcome of the measurements of single qubits of the state $\left|\Psi\right>$, given the operators $N_n$. However, I do not see a proof of this. Is this true? If so, do you have references?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.