Check if a constraint is already implicit fulfilled

Question

$\sigma_i$ is the Pauli-Z matrix acting on the $i$th qubit, hence it commutes with $\sigma_j$ if $j \neq i$. It has the eigenvalues -1 and 1.

Having a list of constraints (directly fulfilled) for example

$\sigma_1 \sigma_2 \sigma_3 \sigma_4 = 1$

$\sigma_3 \sigma_4 \sigma_5 \sigma_6 = 1$

$\sigma_1 \sigma_2 \sigma_7 \sigma_8 = 1$

$\sigma_7 \sigma_8 \sigma_9 \sigma_{10} = 1$

$\sigma_3 \sigma_9 \sigma_{10} = 1$

I want to list all constraints which are implicitly fulfilled. Meaning, that since $\sigma_i^2 = \mathbb{1}$, we have for example

$\sigma_1 \sigma_2 \sigma_3 \sigma_4 \cdot \sigma_3 \sigma_4 \sigma_5 \sigma_6 = \sigma_1 \sigma_2\sigma_5 \sigma_6 = 1.$

This one was easy to see, but there are still more difficult ones as

$\sigma_1 \sigma_2 \sigma_3 \sigma_4 \cdot \sigma_1 \sigma_2 \sigma_7 \sigma_8 \cdot \sigma_7 \sigma_8 \sigma_9 \sigma_{10} = \sigma_3 \sigma_4 \sigma_9 \sigma_{10} = 1$

The list of directly fulfilled constraints contains only constraints of length 3 or 4. I want to find all constraints of lengths 3 and 4 which are implicitly fulfilled.

This problem seems quite hard to me, but I don't think I am the first one who comes up with it, so anyone knows what I have to search for? For sure I can loop over the list of constraints, get new implicit constraints, add them to the initial list, and loop again and so on, but that's a pain in the ass in terms of run time.

If listing all implicit constraints is too hard, maybe it is easier to check whether a given constraint is implicitly fulfilled? For example: Is $\sigma_3 \sigma_4 \sigma_9 \sigma_{10}$ fulfilled given the list of directly fulfilled constraints?

Answer 1

I'm going to assume every constraint is of the form. $$\sigma_x\sigma_y\cdots\sigma_z=1$$

We are going to convert each constraint to an $n$ dimensional vector, where $n$ is the number of qbits.

Let's say we only have $6$ qbits, for brevity. The constraints would translate as:

$\sigma_1 \sigma_2 \sigma_3 \sigma_4 = 1 \;\;\;\; \Rightarrow \; (1,1,1,1,0,0)$
$\sigma_1 \sigma_3 \sigma_5 = 1 \;\;\;\;\;\;\;\; \Rightarrow \; (1,0,1,0,1,0)$
$\sigma_4 \sigma_6 = 1 \;\;\;\;\;\;\;\;\;\;\;\; \Rightarrow \; (0,0,0,1,0,1)$
$\sigma_1 \sigma_3 \sigma_4 \sigma_5 \sigma_6 = 1\;\; \Rightarrow (1,0,1,1,1,1)$

Composition/multiplication of constraints corresponds to the addition of vectors. Note that $1 + 1 = 0 $ (since $\sigma_i^2=1$) . The next step is to order the constraints (vectors) lexicographically (ie. vectors in which the $a_1$ member is $1$ go first), place them as rows of a matrix, and perform Gaussian elimination on the matrix.

This ensures that the redundant constraints are eliminated. We are left with $m$ "generator" constraints such that not one of them can be written as a combination of the others. The number of all possible constraints is $2^m$, with each being a unique combination of the generator constraints. Then you can check whether or not a given constraint can be written in terms of the generator ones by applying reduction to it.

Let's take your given example.

$\sigma_1 \sigma_2 \sigma_3 \sigma_4 = 1$
$\sigma_3 \sigma_4 \sigma_5 \sigma_6 = 1$
$\sigma_1 \sigma_2 \sigma_7 \sigma_8 = 1$
$\sigma_7 \sigma_8 \sigma_9 \sigma_{10} = 1$
$\sigma_3 \sigma_9 \sigma_{10} = 1$

Applying Gaussian elimination we eliminate the first constraint from the second (as they both start with $a_1$) and get:

$\sigma_1 \sigma_2 \sigma_3 \sigma_4 = 1$
$\sigma_3 \sigma_4 \sigma_5 \sigma_6 = 1$
$\sigma_3 \sigma_4 \sigma_7 \sigma_8 = 1$
$\sigma_7 \sigma_8 \sigma_9 \sigma_{10} = 1$
$\sigma_3 \sigma_9 \sigma_{10} = 1$

Now the second constraint is the smallest (lexicographically) that starts with $a_3$, and we can eliminate it from the third and fifth (also start with $a_3$), getting:

$\sigma_1 \sigma_2 \sigma_3 \sigma_4 = 1$
$\sigma_3 \sigma_4 \sigma_5 \sigma_6 = 1$
$\sigma_5 \sigma_6 \sigma_7 \sigma_8 = 1$
$\sigma_7 \sigma_8 \sigma_9 \sigma_{10} = 1$
$\sigma_4 \sigma_5 \sigma_9 \sigma_{10} = 1$

After a final ordering we have:

$\sigma_1 \sigma_2 \sigma_3 \sigma_4 = 1$
$\sigma_3 \sigma_4 \sigma_5 \sigma_6 = 1$
$\sigma_4 \sigma_5 \sigma_9 \sigma_{10} = 1$
$\sigma_5 \sigma_6 \sigma_7 \sigma_8 = 1$
$\sigma_7 \sigma_8 \sigma_9 \sigma_{10} = 1$

Gausian elimination has been applied: each constraint starts with a different $\sigma_n$, and they are arranged in order. We're left with $5$ generating constraints (none of them was redundant), so the total number of all possible constraints would be $2^5 = 32$ . This corresponds to the possible combinations of the generating constraints (ie. a given generating constraint is either included, or not).

Finally, let's check whether:

$\sigma_3 \sigma_4 \sigma_9 \sigma_{10} = 1$

could be fulfilled from our generating constraints (also called basis). It starts with $a_3$ so it can be reduced by our second generating constraint (as it also starts with $a_3$). The second one is $\sigma_3 \sigma_4 \sigma_5 \sigma_6 = 1$, and the reduction is $\sigma_5 \sigma_6 \sigma_9 \sigma_{10} = 1$ . This now starts with $a_5$, and can be reduced by our fourth generating constraint, giving: $\sigma_7 \sigma_8 \sigma_9 \sigma_{10} = 1$. This can be reduced by (and coincides with) our fifth generating constraint, giving $1=1$ (true). So the relationship $\sigma_3 \sigma_4 \sigma_9 \sigma_{10} = 1$ can indeed be deduced from our generating constraints, by composing the second , the fourth and the fifth.

To give an example of something that can not be deduced from our generating constants, take:

$\sigma_7 \sigma_{10} = 1$

We reduce it with the fifth constrain to get:

$\sigma_8 \sigma_{9} = 1$ . However, notice that the starting term of this constraint, $\sigma_8$, is not among the stating terms of our generating constraints. Therefore, it is irreducible. So, $\sigma_7 \sigma_{10} = 1$ can not be deduced from our given generating constraints.

---

Edit: more detail on how the number of implicitly fulfilled constraints is equal to $2$ to the power of the number of generating constraints:

Given that in our example we have $5$ generating constraints, we shall map a constraint to each number from $0$ to $2^5-1$, giving a total of $2^5$ constraints. The key is that the numbers going from $0$ to $2^5-1$ are the binary numbers of up to $5$ digits:

Take the number $19$ for example. Written in binary it is $10011_2$. We see that the first, second, and fifth digits are $1$ (indexing the digits from right to left). Therefore the constraint corresponding to to the number $19$ is obtained by composing the first, second, and fifth of our generating constraints:

$(\sigma_1 \sigma_2 \sigma_3 \sigma_4)(\sigma_3 \sigma_4 \sigma_5 \sigma_6 )(\sigma_7 \sigma_8 \sigma_9 \sigma_{10}) = 1$

This simplifies to: $\sigma_1 \sigma_2\sigma_5 \sigma_6 \sigma_7 \sigma_8 \sigma_9 \sigma_{10}= 1$

This is the constraint associated to the number $19$. We can do this for any number going from $0$ to $2^5-1$, to generate all implicitly fulfilled constraints (as written in canonical from):
The number $0$ corresponds to the constraint $1 = 1$.
The number $3$ (ie. $11_2$) corresponds to $(\sigma_1 \sigma_2 \sigma_3 \sigma_4)(\sigma_3 \sigma_4 \sigma_5 \sigma_6 ) = 1$, which gives: $\sigma_1 \sigma_2 \sigma_5 \sigma_6 = 1$.