# Recovering phases in $2n$-bit binary representation of n-qubit Paulis

I am currently going through a paper discussing Pauli sampling strategies for VQE: https://arxiv.org/abs/1908.06942

I want to code and test their strategy.

They explain how to create a circuit allowing to measure a set of commuting Paulis at once. To do so, they use stabilizer formalism and a representation of $$n$$-qbits Paulis as $$2n$$ binary vectors. If we denote the vector as $$(z_1,...,z_n,x_1,...,x_n)$$, the $$i$$-th operator in the product is a $$Z$$ if $$z_i = 1, x_i = 0$$, $$X$$ if this is the other way around, $$Y$$ if $$z_i = 1 = x_i$$ and $$I$$ if $$z_i = 0 = x_i$$. Addition on vectors correspond to multiplication, and operation on rows to $$H$$, $$S$$ and $$CZ$$ gates.

Linear algebra on said vectors is then used to create an appropriate circuit, and to see what classical post-processing will allow to measure all the commuting Paulis from a single measure.

However, this vector representation is incomplete as it does not keep track of the phase : for instance, both $$XY$$ and $$YX$$ will be represented as $$Z$$, forgetting the minus sign (because addition in $$\mathbb{Z}_2$$, unlike Paulis multiplication, is commutative), and same goes for $$H$$, $$S$$ and $$CZ$$ gates that will sometimes yield a minus sign.

The authors claim it is easy to recover the phases by looking at the operations we have made on the binary vectors. In appendix D, they give a full example of the algorithm but still do not explain how they get the phases back ("we can work out that the phases for the six original operators are ...")

How to compute said phases ? The authors suggest this is easy but I could not find a way to do that in the general case. Looking at the example in the appendix D, does someone see how to do it ?

You do have to keep track of the phase for each stabilizer generator separately.

## Phases as $$Z_n$$

There are only four phases possible in these circuits, $$\pm 1, \pm i$$. Note the following relationships.

$$(-i)^0$$ $$1$$
$$(-i)^1$$ $$-i$$
$$(-i)^2$$ $$-1$$
$$(-i)^3$$ $$i$$

This tells us that the four phases form the additive mod 4 group, i.e. instead of multiplying the phases, you can just add the powers. For instance, $$-i \times -1 \equiv 1 + 2 = 3 \equiv i$$.

## Add phases to the binary representation

Instead of setting $$X \equiv (0|1)$$ etc, let us track the phase $$p$$ with the notation $$[p](0|1)$$ etc. So for instance, $$iX = [3](0|1)$$.

## Binary representation of the Pauli group with non-commutative addition

The paper or other introductions to the topic assume the addition of vectors (multiplication of operators) is commutative. Meaning $$XY \equiv (1|0) + (1|1) \equiv YX$$. But if you want to track phases, you have to turn the addition non-commutative. At the same time we want to track the phases.

For instance, we want $$XY \equiv [0](0|1) + [0](1|1) = [3](1|0) \equiv iZ,$$ but $$YX \equiv [0](1|1) + [0](0|1) = [1](1|0) \equiv -iZ.$$

Note the addition on the phase is additive with existing phases. So $$-XY \equiv [2+3](1|0) = [1](1|0) = -iZ$$ as expected. It is also additive over tensor products. Eg. $$X_1X_2 Y_1Y_2 \equiv [3+3](00|11) = -Z_1Z_2$$.

You can create a 4x4 table of all 16 possible multiplications between the four single-qubit Pauli operators, with the table entries the phases due to the multiplication.

Then for any operation on $$n$$ qubits, you can keep track of the phases using this table.

I haven't discussed the operations of $$H, S, CZ$$, but it should not be too much work to incorporate them into this picture.