Efficient implementation of the Clifford group for $n$ qubits

Question

I'm looking for an efficient implementation of the Clifford group $\mathcal{C}_n$ of $n$ qubits. The Clifford group $\mathcal{C}_n$ has stucture $(2_+^{1+2n} \circ C_8).Sp(2,n)$, where $2_+^{1+2n}$ denotes an extraspecial 2 group of $+$ type, $C_8$ the cyclic group of order 8, and $Sp(2n,2)$ a symplectic group over the binary field. Here "$\circ$" means the central product.

The Clifford group $\mathcal{C}_n$ can be used for the simulation of quantum computing with $n$ qubits and a restricted set of qubit gates in polynomial time, see e.g. [1]. It has a unitary complex representation of dimension $2^n$, see e.g. [2]. Quantum theorists use an explicit construction $\rho$ of that representation of $\mathcal{C}_n$ based on Pauli matrices, see [1]. Vectors in $\rho$ are called state vectors. In [1] the group $\mathcal{C}_n$ is generated by the qubit gates CNOT, Phase, and Hadamard. These gates operate (repeatedly) on the state vectors starting at a certain unit vector $e_0 = |0 \ldots 0 \rangle$. Let $V_0$ be the image of $e_0$ under the operation of $\mathcal{C}_n$ in the state vector space. The states in $V_0$ are also called stabilizer states.

I need an implementation of representation $\rho$ that supports the following operations:

• Multiplication, inversion, and test for equality in $\mathcal{C}_n$.

• Operation of an element of $\mathcal{C}_n$ on a state vector in $V_0$.

• Output of an entry of the matrix representing an element of $\mathcal{C}_n$.

• Output of an entry of a state vector in $V_0$.

• Some kind of qubit measurement applied to a state vector in $V_0$, as in [1].

Entries of matrices and vectors are with respect to the representation $\rho$ in [1]. Runtime should be polynomial in $n$.

I have some concrete ideas for such an implementation.

My question is:

Has anybody implemented a similar representation of $\mathcal{C}_n$ before?

Note that the representation in [1] implements state vectors in $V_0$ (up to a scalar multiple), and operation of $\mathcal{C}_n$ on $V_0$, but not the computation of entries of group elements or state vectors. In [1] elements of
$\mathcal{C}_n$ cannot easily be tested for equality. I also need to distingiush between scalar multiples of a state vector, which is irrelevant in quantum theory.

[1] https://arxiv.org/abs/quant-ph/0406196

[2] https://arxiv.org/abs/math/0001038

^{Cross-posted from MathOverflow}

Answer 1

I think data structures based on ZX-calculus (see [1] for an introduction) are able to do all the operations you require. ZX-calculus is a diagrammatic calculus that is complete for all unitaries [2] (that is to say, every unitary can be represented as a ZX-diagram, and every pair of diagrams that represent the same unitary can be proven equal using just the rules of ZX-calculus). First note that:

• Since all Clifford operations are unitary, the inverse is just the conjugate transpose.
• Finding the entry in a matrix or vector can be done as a dot product with a 'one-hot' state.

Therefore, you just need to be able to multiply, take conjugate transposes, compare diagrams, and produce one-hot states. In ZX-calculus:

• Multiplication is done by composing the diagrams sequentially.
• The conjugate transpose of a diagram is the same diagram flipped horizontally with all the phases negated.
• A one-hot state that is non-zero at position $n$ is encoded by translating each of the binary digits of $n$ into either an $X[0]$ spider or an $X[\pi]$ spider and taking the tensor product (which composes diagrams in parallel).

Then to compare diagrams and extract the value of a diagram representing a dot product, you can use a procedure that simplifies any Clifford diagram to a normal form (see [3]). Comparing these normal forms lets you test for equality between diagrams (and also produce a proof that they are equal using the ZX-calculus rules). For scalar diagrams (like a dot product) this normal form is just a scalar that you can easily read off into a complex number.

All of these operations are implemented in a Python package called PyZX which contains tools for working with ZX-diagrams (see for instance pyzx.clifford_simp for simplifying Clifford circuits to a normal form). PyZX also contains implementations of some of the best known algorithms for optimizing and synthesizing quantum circuits.

It is possible to sample from measurements applied to some Clifford circuit (i.e do weak simulation) in polynomial time using ZX-calculus (put the diagram into affine-with-phases form and sample uniformly from the solutions to the equation $Ax = b$ where $A$ is the biadjacency matrix and $b$ is phases of the X-spiders - this is $O(q^3 + kq^2)$ for $k$ samples and $q$ qubits), but honestly the easiest way might be to synthesise an optimized circuit using PyZX and then use something like Qiskit to simulate it using the stabilizer option of their AerSimulator class.

However, if you want to do strong simulation (i.e find probabilities of measurement outcomes) this is actually very easy with ZX-calculus, since by the Born rule, such a probability is just a dot product (note also that you can marginalize over some qubits with no loss in runtime this way).

Finally, all these operations run in polynomial time. For the simplification algorithm, it takes $O(Nq^2)$ time for $N$ gates and $q$ qubits and produces a normal with $O(q)$ spiders and $O(q^2)$ edges, so comparisons between normal forms are $O(q^2)$. All the other operations are clearly polynomial time.

[1]: Coecke B, Kissinger A. Picturing Quantum Processes: A First Course in Quantum Theory and Diagrammatic Reasoning. Cambridge: Cambridge University Press; 2017.

[2]: Vilmart R. ZX-Calculi for Quantum Computing and their Completeness (Doctoral dissertation, Université de Lorraine).

[3]: van de Wetering J. ZX-calculus for the working quantum computer scientist. arXiv preprint arXiv:2012.13966. 2020 Dec 27.

Answer 2

I have written a collection of C programs together with a python interface that satisfies most of the requiremets listed above. Documentation see section

https://mmgroup.readthedocs.io/en/latest/api.html#the-subgroup-2-1-24-co-1-of-the-monster-and-the-clifford-group

in https://mmgroup.readthedocs.io/en/latest/ .

My motivation for doing so was that high-speed computation in the Clifford group $\mathcal{C}_{12}$ of 12 qubits is useful for computations in the monster group.