Clifford group¶
This note explain how Clifford circuit can be simulated efficiently on classical computers.
- link
- wiki/symplectic-group
- How to efficiently select an arbitrary clifford group element doi-link
- 2004 Improved simulation of stabilizer circuits doi-link
- Stabilizer Codes and Quantum Error Correction arxiv-link
- Quantum Error Correction via Codes over GF(4) arxiv-link
- Fast simulation of stabilizer circuits using a graph state representation arxiv-link
- python-quaec documentation github-link
- github/hongyehu/pyclifford
- github/abp Fast simulation of Clifford circuits
- quantumclifford.jl documentation github-link
- the canonical name of Clifford group: Involutions on the the Barnes-Wall lattices and their fixed point sublattices arxiv-link
- the canonical name of Pauli group: extra special group with $p=2$ wiki-link the Heisenberg group over a finite field stackexchange-link
- 6-qubit optimal Clifford circuits doi-link
- notation
- $\mathbb{F}_n$: finite field
- $\mathbb{R}$: real field
- $\mathbb{C}$: complex field
- $U(n)=\lbrace x\in\mathbb{C}^{n\times n}:x^\dagger x=I_n \rbrace$: unitary group
- $\Lambda_n=\sigma_x\otimes I_n$
import numpy as np
try:
import numqi
except ImportError:
%pip install numqi
import numqi
Clifford group¶
Previous notebook (TODO-link) discuss the Pauli groups $P_n$ ($4^{n+1}$ Pauli strings). The Clifford group $C_n$ are those matrices mapping Pauli groups to Pauli groups, i.e. $x\cdot P_n\cdot x^\dagger=P_n$ for $U\in C_n$. In other words, the Clifford group is the normalizer of the Pauli group in the unitary group $U(2^n)$.
$$C_{n}=\lbrace x\in U\left(2^{n}\right):xP_{n}x^{\dagger}=P_{n}\rbrace /U\left(1\right)$$
We quotient by $U(1)$ because the global phase is not observable.
Some quick facts about the Clifford group:
- $C_n$ is a finite group.
- $P_n\in C_n$: the Pauli group is a subset of the Clifford group.
- CNOT,S gate is in the Clifford group.
Below, Let's check CNOT gate.
# remove the sign factor (1,-1,i,-i) of Pauli group for easy print
pauli_group_str = numqi.gate.get_pauli_group(2, kind='str')
print('2-qubit Pauli group:', ' '.join(pauli_group_str))
clifford = numqi.gate.CNOT
for pauli_str in pauli_group_str:
tmp0 = clifford @ numqi.gate.PauliOperator.from_str(pauli_str).full_matrix @ clifford.T.conj()
pauli_str_after = numqi.gate.PauliOperator.from_full_matrix(tmp0).str_
print(f'{pauli_str}->{pauli_str_after}')
2-qubit Pauli group: II IX IY IZ XI XX XY XZ YI YX YY YZ ZI ZX ZY ZZ II->II IX->IX IY->ZY IZ->ZZ XI->XX XX->XI XY->YZ XZ->YY YI->YX YX->YI YY->XZ YZ->XY ZI->ZI ZX->ZX ZY->IY ZZ->IZ
Group isomorphism¶
Matrix representation of Clifford is not most efficient. Instead, we can use the symplectic representation like Pauli group discussed previously. There is a group isomorphism
$$C_{n}\cong\mathbb{F}_{2}^{2n}\times Sp\left(2n,\mathbb{F}_{2}\right)$$
where $Sp(2n,\mathbb{F}_{2})$ is the symplectic group over finite field $\mathbb{F}_2$.
$$ Sp\left(2n,\mathbb{F}_{2}\right)=\lbrace x\in\mathbb{F}_{2}^{2n\times 2n}:x\Lambda_{n}x^{T}=\Lambda_{n}\rbrace $$
Some quick facts about the symplectic group:
$x\in Sp\left(2n,\mathbb{F}_{2}\right)\Rightarrow x^{T}\in Sp\left(2n,\mathbb{F}_{2}\right)$
$x,y\in Sp\left(2n,\mathbb{F}_{2}\right)\Rightarrow xy\in Sp\left(2n,\mathbb{F}_{2}\right)$
$x\in Sp\left(2n,\mathbb{F}_{2}\right)\Rightarrow x^{-1}=\Lambda_{n}x^{T}\Lambda_{n}$
order of the group
$$ \left|Sp\left(2n,\mathbb{F}_{2}\right)\right|=\prod_{i=1}^{n}(4^{i}-1)2^{2n-1} $$
About the group isomorphism, denotes $x\in C_n \;\mapsto\; (r^{(x)}, S^{(x)})\in \mathbb{F}_{2}^{2n}\times Sp\left(2n,\mathbb{F}_{2}\right)$
identity $I_{2^n}\in C_n$ is mapped to $0^{2n}\times I_{2n}$
inverse TODO
multiplication: for any $x,y\in C_n$ with their images $(r^{(x)}, S^{(x)})$ and $(r^{(y)}, S^{(y)})$. Let $z=y\circ x$, then $z$'s image $(r^{(z)}, S^{(z)})$ is given by
$$ S_{ij}^{(z)}=\sum_{k=1}^{2n}S_{ik}^{(y)}S_{kj}^{(x)} $$
$$ \Delta_{\alpha}=\sum_{k=1}^{n}S_{k\alpha}^{(x)}S_{k+n,\alpha}^{(x)}+\sum_{i=1}^{n}\sum_{j=1}^{2n}S_{j\alpha}^{(x)}S_{ij}^{(y)}S_{i+n,j}^{(y)}-\sum_{k=1}^{n}S_{k\alpha}^{(z)}S_{k+n,\alpha}^{(z)} $$
$$ r_{\alpha}^{(z)}=r_{\alpha}^{(x)}+\sum_{i=1}^{2n}r_{i}^{(y)}S_{i\alpha}^{(x)}+\sum_{i=1}^{n}\sum_{j=1}^{2n}\sum_{k=j+1}^{2n}S_{j\alpha}^{(x)}S_{k\alpha}^{(x)}S_{i+n,j}^{(y)}S_{ik}^{(y)}+\left\lfloor \frac{\Delta\%4}{2}\right\rfloor $$
Action of Clifford group on Pauli group¶
Denote Clifford matrix $U\in C_n$ with its symplectic form $(r,S)\in \mathbb{F}_{2}^{2n}\times Sp\left(2n,\mathbb{F}_{2}\right)$. For basis elements in the Pauli group (Pauli X and Pauli Z), the action of the Clifford group is given by
$$ UX_{j}U^{\dagger}=\left(-1\right)^{r_{j}}\left(i\right)^{\sum_{k}S_{kj}S_{k+n,j}}\prod_{k=1}^{n}X_{k}^{S_{kj}}Z_{k}^{S_{k+n,j}} $$
$$ UZ_{j}U^{\dagger}=\left(-1\right)^{r_{j+n}}\left(i\right)^{\sum_{k}S_{k,j+n}S_{k+n,j+n}}\prod_{k=1}^{n}X_{k}^{S_{k,j+n}}Z_{k}^{S_{k+n,j+n}} $$
One should notice that the right side is the Symplectic form of the Pauli group. For a general element in Pauli group $x\in P_n$,
$$ x \in P_{n},x=\left(-1\right)^{x_0}\left(i\right)^{x_{0}^{\prime}}\prod_{i=1}^{n}X_{i}^{x_{i}}Z_{i}^{x_{i+n}} $$
the action of the Clifford group is given by
$$ y=UxU^{\dagger} =\left(-1\right)^{y_0}\left(i\right)^{y_{0}^{\prime}}\prod_{i=1}^{n}X_{i}^{y_{i}}Z_{i}^{y_{i+n}} $$
where
$$ \Delta=x_{0}^{\prime}+\sum_{i=1}^{n}\sum_{j=1}^{2n}x_{j}S_{ij}S_{i+n,j} $$
$$ y_{0}=x_{0}+\sum_{i=1}^{2n}x_{i}r_{i}+\sum_{i=1}^{n}\sum_{j=1}^{2n}\sum_{k=j+1}^{2n}x_{j}x_{k}S_{i+n,j}S_{ik}+\left\lfloor \frac{\Delta\%4}{2}\right\rfloor $$
$$ y_{0}^{\prime}=\Delta\%2 $$
$$ y_{i}=\sum_{j=1}^{2n}S_{ij}x_{j} $$
Below are some examples
$$ HXH=Z,HYH=-Y,HZH=X,H\simeq 00\times\begin{bmatrix}0 & 1\\1 & 0\end{bmatrix} $$
$$ XXX=X,XYX=-Y,XZX=-Z,X\simeq 01\times\begin{bmatrix}1 & 0\\0 & 1\end{bmatrix} $$
$$ YXY=-X,YYY=Y,YZY=-Z,Y\simeq 11\times\begin{bmatrix}1 & 0\\0 & 1\end{bmatrix} $$
$$ ZXZ=-X,ZYZ=-Y,ZZZ=Z,Z\simeq 01\times\begin{bmatrix}1 & 0\\0 & 1\end{bmatrix} $$
$$ SXS^\dagger=Y,SYS^\dagger=-X,SZS^\dagger=Z,S\simeq 00\times\begin{bmatrix}1 & 0\\1 & 1\end{bmatrix} $$
$$ \mathrm{CNOT}\simeq 0000\times\begin{bmatrix}1&0&0&0\\ 1&1&0&0\\0&0&1&1\\0&0&0&1\end{bmatrix} $$
numqi.sim.Clifford provides some utilities to convert between matrix representation and symplectic representation.
gate_dict = {
'Hadamard': numqi.gate.H,
'PauliX': numqi.gate.X,
'S': numqi.gate.S,
'CNOT': numqi.gate.CNOT,
}
for name,matrix in gate_dict.items():
cli_r,cli_S = numqi.sim.clifford.clifford_array_to_F2(matrix)
print(name, cli_r, cli_S, sep='\n')
print()
Hadamard [0 0] [[0 1] [1 0]] PauliX [0 1] [[1 0] [0 1]] S [0 0] [[1 0] [1 1]] CNOT [0 0 0 0] [[1 0 0 0] [1 1 0 0] [0 0 1 1] [0 0 0 1]]
And we can verify the action of the Clifford group on Pauli group in Symlectic representation.
clifford = numqi.gate.CNOT
tmp0 = numqi.gate.get_pauli_group(2, kind='str')
pauli = np.random.default_rng().choice(tmp0, 1)[0] #randomly choose a Pauli operator
print('pauli:', pauli)
# calculation via matrix form
result_matrix = clifford @ numqi.gate.PauliOperator.from_str(pauli).full_matrix @ clifford.T.conj()
print('result_matrix:', result_matrix, sep='\n')
# calculation via symplectic form
pauli_F2 = numqi.gate.PauliOperator.from_str(pauli).F2
cli_r,cli_S = numqi.sim.clifford.clifford_array_to_F2(clifford)
result_F2 = numqi.sim.clifford.apply_clifford_on_pauli(pauli_F2, cli_r, cli_S)
print('result_F2:', result_F2)
result_F2_matrix = numqi.gate.PauliOperator.from_F2(result_F2).full_matrix
print('result_F2_matrix:', result_F2_matrix, sep='\n')
pauli: XY result_matrix: [[0.+0.j 0.+0.j 0.-1.j 0.+0.j] [0.+0.j 0.+0.j 0.+0.j 0.+1.j] [0.+1.j 0.+0.j 0.+0.j 0.+0.j] [0.+0.j 0.-1.j 0.+0.j 0.+0.j]] result_F2: [0 1 1 0 1 1] result_F2_matrix: [[ 0.+0.j 0.+0.j 0.-1.j 0.+0.j] [ 0.+0.j -0.+0.j 0.+0.j 0.+1.j] [ 0.+1.j 0.+0.j 0.+0.j 0.+0.j] [ 0.+0.j 0.-1.j 0.+0.j -0.+0.j]]
The advantages of Symplectic representation are that quantum circuits with hundreds of qubits can be simulated efficiently on classical computers (the cost is that: only those circuits with Clifford gates). The following operation can be finished in less than seconds (TODO Clifford circuit)
num_qubit = 100
pauli_input = numqi.random.rand_pauli(num_qubit).F2
print('input:', numqi.gate.PauliOperator.from_F2(pauli_input).str_)
cli_r,cli_S = numqi.random.rand_Clifford_group(num_qubit)
pauli_output = numqi.sim.clifford.apply_clifford_on_pauli(pauli_input, cli_r, cli_S)
print('output:', numqi.gate.PauliOperator.from_F2(pauli_output).str_)
input: XIXIXYYXXZZZYYZXZXIZYIIYXXXYZYYXZZIZXYXZIZYXZXZXIIYXXZIXXXZYZYXIYIXZYYXIYZZZZIXZXXIZXYZIIIYYYIZYZZZX output: XIZZXXYIZIYXZZIIZXIYZXIXXZXZYIYXIZIIZZZXYZIYIXZZIXYYXIIZXYIIYYIXXXZZYZZZYXIZZYZYIYZXXYIIYXXXZZZZYZXX