Pauli Operator, Commutator, Bloch sphere, Binary Operation, and Cyclic Group

Sometimes a thing called "Commutator" is being used in Quantum Computing. In some particular algorithm that solve certain equation, Commutator is used extensively. However the problem is, how can we implement this function fast. The current implementation expecially in the quantum simulation package called OpenFermion is super slow, and I think maybe I can do a better job. 

• What is commute
• What is Binary Operation
• Commutator in 20 word
• Pauli Operator
• What is Bloch Sphere
• Pauli Operator form a Cyclic Group
• How to Make Fast Commutator

What is commute

"Commute" is a algebraic property in mathematics. Let say that you have some operation. Say "go to toilet" and "wash hand". And when you execute those operation, in different order, the outcome and meaning is completely different.

go to toilet then wash hand
wash hand then go to toilet

However the best option should be 

wash hand then go to toilet then wash hand

Then we say "go to toilet" and "wash hand" is NOT COMMUTE. We cannot change the their order arbitrarily. So this is "not commute". Then what is "commute"? 

Think of "walking front" and "walking left". No matter what order you walk, you must go to the same after position. Then we say walking front" and "walking left" is COMMUTE.

When two operation is COMMUTE, they are INDEPENDENT operation with respect to each other. Doing one operation do not affect anything in another operation. Like moving up and down will not have any affection on the horizontal position of that thing. 

So a commutator is a function that we use to check whether two operation is commute with each other or not. It is a binary operation.

What is Binary Operation

"Plus" and "Muliplication" is binary operation. They are used to make a relationship of two object. 

1 + 1 = 2
2 + 2 = 4
3 × 3 = 9

There is a machine called "PLUS" and you can only input two value into it. And then after that it produce a new value. 

PLUS(1,1) => 2

This machine/function can take only two number. Likewise, commutator is binary operation.

Commutator in 20 word

Let A, B be two operation.

Check AB - BA ?= 0

Explain: if A and B commute, then AB should have the same value as BA. And because of that, when you subtract them, you are subtracting the same value. So the result must be zero. 

State it inversely. If AB subtract BA is not equal to zero, A and B is not commute to each other. 

Pauli Operator

Pauli Operator a set of operation in quantum computing. They are denoted as

I, X, Y, Z

In their matrix form

I := [ 1  0 ]
     [ 0  1 ]

X := [ 0  1 ]
     [ 1  0 ]

Y := [ 0 -i ]
     [ i  0 ]

Z := [ 1  0 ]
     [ 0 -1 ]

The "i" in Y is the "i" of imaginary number.

Why is this name. Because they represented the rotation axis of Bloch Sphere. Each Pauli Operator mean that you rotate the Bloch Sphere in the same axis of its name. 

I = identity = do not rotate
X rotate 180 degree in X axis
Y rotate 180 degree in Y axis
Z rotate 180 degree in Z axis

What is Bloch Sphere

Bloch Sphere is used in vistualizing a quantum state. It is a ball, or a sphere, or a globe.

But in fact this thing is totally useless in everyday quantum computing. But I think it might help you understanding more about how the proterty of "commute" related to Pauli Operator. 

So a sphere has three axis namely X Y Z. 

To introduce those axis. I would not tell you to take out you hand and say "right hand rule" or something like that because some folks may not have right hand. So instead I will use your head. 

Think of you head. There is a arrow sticking through your right and left ears. That is the X axis. 

Another arrow sticking through your nose and back of your head. That is Y axis.

And the last arrow go through your neck and top of you head. That is Z axis.

So you try rotating X axis. Rotate you head with respect to ear axis. Doing so, you point your head to the groud. And you find that your nose will not be facing the front any more. Your nose is facing the back now. And of course your head is pointing at different direction. Therefore you know that rotating X axis is not independent from Y and Z axis. 

Likewise, try rotate the Z axis. Namely, facing front, then turn your body 180 degree and now you are facing the back. And you know that you cannot do this without changing the direction of your nose and ears. Again, Z axis is not independent from X and Y axis. 

Therefore the action of rotating X Y Z axis is complely NOT COMMUTE. Same for the Pauli Operator. 

XY != YX
YZ != ZY
ZX != XZ

But one thing is independent. Let say you and your friend is standing side by side. No matter how your friend's head rotate, that do not affect you. Your head and your friend's head is completely independent from each other. This is the principle of Pauli Operator's tensor product. It is internally independent. 

(Z1 Z2) x (X1) == (Z1 X2) x (Z2) == (ZX1 Z2)

See that Z2 is unchanged. Because X1 only act on index 1. Although X1 is NON COMMUTE with Z1, it is COMMUTE with Z2.

Pauli Operator form a Cyclic Group

You do not need to know what mathematically a "Group" is. The only thing you need to know is this "Cyclic Group".

So the problem is, yup Pauli Operator is NON COMMUTATIVE. But how can we predict the outcome of it? Here I write all the combination out. Let see you can spot out the pattern.

XY ==  iZ
YX == -iZ
YZ ==  iX
ZY == -iX
ZX ==  iY
XZ == -iY

For the I, because it stand for Identity and do nothing, IX = X and XI = X, etc, so I omit it.

And you can see whatever you do, the result must be something within {X, Y, Z}. That "i" is imaginary number. Usually we ignore it because i is also independent with all Pauli Operator.

So the rule is, think of it as a circle of triangle. Counting XYZ clockwise and anticlockwise.

  X
Z   Y

X -> Y is clockwise, which is positive, and you got the next element Z. Hence iZ

Y -> X is anticlockwise, so you must have negative, and then the next element Z. Hence -iZ.

Same law apply to all others.

Or you can do this. List out all possible combination in a string.

X Y Z X Y Z X Y Z

Say, ZY, so you look for it and find the matching pattern

X Y Z X [Y <- Z] X Y Z

And follow the direction of the arrow, the next element is X. Thus ZY = -iX because the arrow is pointing at left.

This property is said to be the Cyclic Group.

But what about XX, or YY, or ZZ?

This is kind of simple. If the same thing happened twice, nothing happened after all. i.e

II == I
XX == I
YY == I
ZZ == I

Why is that. Because just as what I mention earlier,

X rotate 180 degree in X axis

So what happen if you do operation X twice?

rotate 180 degree, and rotate 180 degree in X axis

That is the same as

rotate 360 degree in X axis = Do not rotate at all

You can verify all these in the matrix form if you know how to do matrix multiplication. Or with some help of computer program, you should be able to get the same result.

How to Make Fast Commutator

So these knowledge lay the foundation for implementing Commutator in a faster way.

To avoid getting too theoretical, I will first show you how to work on real world example.

Here is a matrix generated from H2 molecule. Don't worry if this is your first time to do chemical calculation. It is just a bunch of number and stuffs. I don't even know what they mean exactly. Knowing how to deal with Pauli Operator is just enough for the task.

coefficient   Pauli Operator

-0.106        [I0 I1 I2   ]
+0.045        [X0 Z1 X2   ]
+0.045        [X0 Z1 X2 Z3]
+0.045        [Y0 Z1 Y2   ]
+0.045        [Y0 Z1 Y2 Z3]
+0.173        [Z0         ]
+0.173        [Z0 Z1      ]
+0.166        [Z0 Z1 Z2   ]
+0.166        [Z0 Z1 Z2 Z3]
+0.120        [Z0    Z2   ]
+0.120        [Z0    Z2 Z3]
+0.168        [   Z1      ]
-0.221        [   Z1 Z2 Z3]
+0.174        [   Z1    Z3]
-0.221        [      Z2   ]

The task is, we have to check that if this is commute with the thing below.

coefficient   Pauli Operator
+1.0          [Z0 Z2]

Let A be the first upper one, and B be the below one. We need to compute AB - BA ?= 0 .

As we can see, A is a sum of a bunch of Pauli Operator. For this kind of thing, we can use distribution law.

W * ( E + R ) == WE + WR   # distribution law

Therefor instead of doing the whole big thing at once, we can just do a single slice of it at a time. Like taking the first term out of A and check whether AB = BA.

A0 = -0.106 [I0 I1 I2] 
B  = +1.0   [Z0    Z2]

A0*B ?= B*A0

(-0.106 [I0 I1 I2] )(+1.0 [Z0 Z2] ) ?= (+1.0 [Z0 Z2] )(-0.106 [I0 I1 I2] )

We can just treat the coefficient as a coefficient, and Pauli Operator as a variable. We can split the task into two seperate part. Like 3y - 3y = 0, all we need to look at is

1. whether the coefficient is the same value.
2. whether the Pauli Operator is the exact same thing.

(-0.106 * +1.0) [I0 I1 I2][Z0 Z2] ?= (+1.0 * -0.106) [Z0 Z2][I0 I1 I2]

For the coefficient, since they are all number, they obey all law from algebra. Namely, commutative law and associative law of multiplication.

Let a,b,c be arbitrary number.

a*b = b*a  # commutative law
a*b*c = a*(b*c)  # associative law

Therefore it do not matter you multiple two number left of right. Any order can produce the same value. Let say Ac is coefficient of A and Bc is of B,

Ac*Bc == Bc*Ac

hence,
Ac*Bc (AB) ?= Bc*Ac (BA)
Ac*Bc (AB) ?= Ac*Bc (BA)  # Ac*Bc = Bc*Ac
      (AB) ?= (BA)        # cancel out Ac*Bc

Absolutely we can ignore the coefficient, however, the only thing in coefficient that we have to worry about is the i produced after two non commute Pauli Operator multiplied together i.e. XY = iZ etc.

e.g. K = X, L = Y

KL ?= LK
XY ?= YX
iZ ?= -iZ
iZ != -iZ

So although both side got the same Pauli Z, the sign of i disagree. If you got more than one set of Pauli Operator multiplied, you have to count for how many i are produced and keep track of the sign.

e.g.
 XY0 XY1 ?= YZ0 YZ1
 iZ0 iZ1 ?= -iZ0 -iZ1

ii Z0 Z1 ?= --ii Z0 Z1
-1 Z0 Z1 ?= -1 Z0 Z1
-1 Z0 Z1 == -1 Z0 Z1

Almost the same configuration but this time commute. To conclue on issue among coefficient, only the i and their sign you should pay attention to. Other do not worth the effort because they are 100% sure to be the exact same value.

So, lets focus on the Pauli Operator.

A0 = [I0 I1 I2] 
B  = [Z0    Z2]

A0*B ?= B*A0

For A0*B
[I0 I1 I2][Z0    Z2]

= [IZ0 I1 IZ2]

You can see index 1 is not contained in B, so instead of doing the full length multiplication, we can just extract those index both A0 and B share. So the problem size is smaller.

[I0 I1 I2][Z0 Z2] = [I0 I2][Z0 Z2] = [IZ0 IZ2]

Those index both A0 and B share are the main target. Still we need to see what is outside of main target. Here we can use the property of Pauli Operator that different index COMMUTE. So we don't need to care where to put them. Front of back, do not matter.

[IZ0 IZ2] -> {IZ0 IZ2}[I1] or [I1]{IZ0 IZ2}
{}for target

As I mention earlier, I stand for Identity thus it do nothing, therefore

{IZ0 IZ2} = {Z0 Z2}

And since A0 contains only I, it is automatically known as commute. 100% sure. You don't even need to compute it.

because IZ = ZI, if only I is invlove, it must commute.

Let see what if it is non commute.

A1 = +0.045 [X0 Z1 X2]
B  = +1.0   [Z0    Z2]

A1*B ?= B*A1

Again, only need to check the targeted part.

A1 = +0.045 {X0 X2}
B  = +1.0   {Z0 Z2}

A1*B ?= B*A1

   XZ0 XZ2 ?= ZX0 ZX2
 -iY0 -iY2 ?= iY0 iY2
--ii Y0 Y2 ?= ii Y0 Y2
     Y0 Y2 == Y0 Y2

Appending the non targeted part,

     Y0 Y2 Z1 == Y0 Y2 Z1

In fact you don't even need to check for the non targeted part to see whether all term match. The real power of Cyclic Group property of Pauli Operator is that it ensured that all tensor product of Pauli Operator is unique.

We can seperate terms in such manner
{target}[non target]

The thing brother me is that target part will change accouding to what it is multiplied to.
Like

A3 = {target3}[non target3]
A4 = {target4}[non target4]

B  = {targetB}

A3*B != B*A3 by coefficient
but if {target4 * targetB} == {target3}
adding its coefficient to A3*B may lead to A3*B == B*A3

Will there be such situation?

Turn out there is no such situation.

Let say

A3 = {X}[non target3]
A4 = {Y}[non target4]

B  = {Z}

First of all, A3==A4 if and only if target3==target4, given they have exactly same [non target] term.

So target3 must not be target4.

Second, property from Cyclic Group ensure that A3*B != A4*B.

XY = YX = Z 
YZ = ZY = X

Third, since multiplying Pauli Operator is a binary operation, this make Cyclic Group 100% true.

So by this uniqueness, we can do all comparison separately.

---

Last update: 2023-06-28
Created: 2023-06-28