Quantum circuit consisting only of CNOT, H, S, measurement on computational basis can be simulated efficiently on a classical computer
up to complex phases.
more specifically
\[ \forall p \in P_n, \forall c \in C_n, cpc^{\dagger} \in P_n \]up to complex phases.
Intuitive example:
\[ HXH^{\dagger} = Z \] \[ CNOT(X \otimes I) CNOT^{\dagger} = X \otimes X \]Given an n-qubits state \(\ket{\psi}\), the following are equivalent:
\(\ket{\psi}\) can be obtained from \(\ket{0}^{\otimes n}\) by CNOT, H, S only
\(\ket{\psi}\) can be obtained from \(\ket{0}^{\otimes n}\) by CNOT, H, S and measurement gates only
\(\ket{\psi}\) is stabilized by exactly \(2^n\) Pauli operators
\(\ket{\psi}\) is uniquely determined by \(\text{Stab}(\ket{\psi}) \cap P_n\), i.e. the group of Pauli operators that stabilize \(\ket{\psi}\)
Any finite group \(G\) has a generating set of size at most \(log_2|G|\)
if \(\ket{\psi}\) is a stabilizer states on n qubits, then the group \(\mathcal{S}_{P_n} := \text{Stab}(\ket{\psi}) \cap P_n\) of Pauli operators that stabilize \(\ket{\psi}\) has a generating set of size \(log_2 2^n = n\)
if \(U\ket{\psi} = \ket{\psi}\), \(V\ket{\psi} = \ket{\psi}\) then \(U^{\dagger}\ket{\psi} = \ket{\psi}\), \(UV\ket{\psi} = \ket{\psi}\)
indeed:
\[ \text{Stab}(\ket{\psi}) \subset P_n \]so
\[ \text{Stab}(\ket{\psi}) \cap P_n = \text{Stab}(\ket{\psi}) \]which is a group
recall
\[ C_n : C_n P_n C_n^{\dagger} = P_n \]up to complex phases.
So \(\mathcal{S}_{P_n}\) is our stabilizer groups (which is a subgroup of Pauli group), \(C_n\) is the set of circuits that builds up clifford group (i.e. clifford circuits)
this tells us that clifford circuits transform a state stabilized by \(\mathcal{S}_{P_n}^{(i)} \sub P_n\) into another state stabilized by \(\mathcal{S}_{P_n}^{(j)} \sub P_n\), such states form a closed algebra structure.
It can be easily shown that there is one-one corespondence between \(C_n\) and the states.
Example:
| \(\ket{\psi}\) | \(P_n\) | | – | – | | \(\ket{0}^{\otimes n}\) | \(Z^{\otimes n}\) | | \(C_n \ket{0}^{\otimes n}\) | \(C_n Z^{\otimes n} C_n^{\dagger}\) |
To show why:
\[ \begin{aligned} S\ket{\psi} &= \ket{\psi} \\ C_n S C_n^{\dagger} C_n \ket{\psi} &= C_n \ket{\psi} \end{aligned} \]i.e.
\[ \frac {\vdash S \in \mathcal{S}_{P_n}(\ket{\psi})} {\vdash C_n S C_n^{\dagger} \in \mathcal{S}_{P_n}(C_n\ket{\psi})} \]To show Why:
if we do not add the restriction, then:
\[ \mathcal{S}_{P_n} \mathcal{S}_{P_n}^{\dagger} := (\pm i)^2 \{\}\{\}^{\dagger} = -I^{\otimes n} \]is not unitary, which is forbidden.
Example:
\[ \begin{aligned} Y &= i X Z \\ SYS^{\dagger} &= iYZ = -X \end{aligned} \]Representing state generated by clifford circuits using its set of stabilizer generators: \(\mathcal{S}_{P_n}\)
Example:
\[ \begin{aligned} S :& X \to Y & Z \to Z \\ H : & X \to Z & Z \to X \\ CNOT : & X_1 \to X_1 X_2 & X_2 \to X_2 \\ & Z_1 \to Z_1 & Z_2 \to Z_1 Z_2 \\ X : & X \to X & Z \to -Z \\ Y : & X \to -X & Z \to -Z \end{aligned} \]For \(n\) qubits states, \(\mathcal{S}_{P_n}\) contains \(n\) Pauli strings, each Pauli string can be represented using \(2n\) bits.
\[ \begin{pmatrix} X_{11} & \cdots & X_{1n} & | & Z_{11} & \cdots & Z_{1n} & | & r_1 \\ \vdots & & \vdots & | & \vdots & & \vdots & | & \vdots \\ X_{n1} & \cdots & X_{nn} & | & Z_{n1} & \cdots & Z_{nn} & | & r_n \\ \end{pmatrix} \begin{matrix} R_1 \\ \vdots \\ R_n \end{matrix} \]each row represents a stabilizer.
Example:
2-qubit \(\ket{00}\):
\[ \begin{pmatrix} 0 & 0 & | & 1 & 0 & | & 0 \\ 0 & 0 & | & 0 & 1 & | & 0 \\ \end{pmatrix} \begin{matrix} R_1 \\ R_2 \end{matrix} \]the group multiply operation can be done with XOR:
\[ [g_{R_1} * g_{R_2}]_{rep} := R_1 \oplus R_2 \] \[\begin{aligned} \oplus: & 0 \oplus 0 = 0 & & I I = I \\ & 0 \oplus 1 = 1 & & I P = P \\ & 1 \oplus 0 = 1 & & P I = P\\ & 1 \oplus 1 = 0 & & P P = I \end{aligned} \]two row operation can be safely applied without disturbing the state(i.e. the symmetry introduced with this algebra structure)
row sum with XOR
row swap
to be continue
suppose we have a single measurement on computational basis onto qubit \(a\): \(Z_a\)
check if \(\exist k, X_{ka}=1\) in the tablue:
the measurement is random.
if there is another \(p\) s.t. \(X_{pa}=1\), we can:
do \(R_p = R_k \oplus R_p\) so that \(X_{pa}\) is canceled out.
\(\frac{1}{2}\) probability, \(m=0 \to r_k=0\)
\(\frac{1}{2}\) probability, \(m=1 \to r_k=1\)
set:
\(Z_{ka}:=1\)
\(X_{ka}:=0\)
the measurement is determinant.
\[ \forall k, R_k Z_a = Z_a R_k \]\(\pm Z_a\) is also a stabilizer of \(\ket{\psi}\)
but \(+1\) or \(-1\)?
\[ \exist \{i, j, k .. l\} s.t. \prod_{p \in \{i, j, k .. l\}} R_p = Z_a \text{or} -Z_a \]how to get this?
\[ R'_i = (X_{i1} \cdots X_{in} | Z_{i1} \cdots Z_{in}) \]we need to solve:
\[ R' B = Z_a \]solving this equation using Gaussian elimination requires \(\mathcal{O}(n^3)\)
let \(R_1 \cdots R_n\) s.t. \(R_i\) \(R_j\) commute
let \(R_{n+1} \cdots R_{2n}\) is the stabilizer group
let \(R_i, i \in \{1 ... n\}\) anticommutes with \(R_{n+i}\) and commutes with all others
recall
\[ \exist \{i, j, k .. l\} s.t. \prod_{p \in \{i, j, k .. l\}} R_p = Z_a \text{or} -Z_a \]\(Z_a\) will anticommute with \(R_i, i \in \{1 .. n\}\) iff \({i+n}\) is in the generator list of \(\{i, j, k .. l\}\) to produce \(\pm Z_a\)
Demo:
\[ \begin{aligned} & R_i R_{i+n} = (-1) R_{i+n} R_{i} \\ & \text{suppose:} Z_a = R_i R_j R_k ... R_l \\ \end{aligned} \] \[ \begin{aligned} Z_a R_{i+n} & = R_i R_j R_k ... R_l R_{i+n} \\ &= R_i R_{i+n} R_j R_k ... R_l \\ &= (-1) R_{i+n} R_i R_j R_k ... R_l \end{aligned} \]the procedure is simple
scan all the destabilizer generators, to see if it is anticommute with \(Z_a\)
if so, then the corresponding stabilizer generator is in the generator list
if not, it is not in the generator list
using all the generator in the generator list to produce \(Z_a\), the corresponding phase is what we need
This algorithm is of order \(\mathcal{O}(n^2)\)
[1] S. Aaronson and D. Gottesman, “Improved Simulation of Stabilizer Circuits”.
[2] "An Introduction to Stabilizer Circuit Simulation"
[3] V. Gheorghiu, “Efficient simulation of quantum computers: the Gottesman-Knill theorem or an application of group theory to quantum information (part 2),” . . ..