# Expected Minimum Clique Coverage?

I'm curious if there is literature on this and, if there is, where to find it. Here I'm using clique" to mean a set of observables which all commute with each other. I also include the identity matrix as the zeroth Pauli.

Problem: Say I randomly generate a list of $$P$$ different Pauli observables on $$M$$ qubits. They can be any tensor product of $$M$$ Paulis. Is there an approximate function of $$P,M$$ which can give me the expected number of cliques in a minimal clique covering? I'd also be happy with just big-$$O$$ notation.

Clearly the number of cliques must scale as less than $$O(M)$$. It also can't just be $$1$$ or you'd have a very, very simple Hamiltonian... non-contextual is the word I think? Regardless, I feel that the crux of this problem lies in the fact that Paulis either commute or anti-commute.

If anyone has any hints on how to approach this problem, if it's been done before or whether it's folly to try, I'd appreciate a hint. A solution for it would be important for VQE, I think.

EDIT: I think I have a better upper bound now. I think that the worst-case scenario for a commutativity graph is a line for the Paulis. In that case we'll still be able to make $$\lceil M / 2\rceil$$ cliques.

• Do you mean single qubit Pauli’s or any tensor product of Pauli’s on M qubits? May 20, 2022 at 17:56
• Very good point I meant any tensor product. I'll amend it. May 20, 2022 at 19:17
• Also, I find this paper by Gokhale et al (arxiv.org/abs/1907.13623) to be both an extremely interesting project, but also a very well explained one. They go through the theory of how to efficiently produce circuits for the sets of commuting Pauli operators and some clever tricks they use to make the graph algorithm efficient. May 20, 2022 at 19:49

The question you ask is an interesting one, and the general answer I don't know. But I find numerics to be a useful generator of conjectures. I wrote a little python code using pennylane for this, the code is attached below.

If you decide to play around in here, there's definitely space for optimization. But at the moment <7 qubits works fine, but you would probably have to do some work to get the program to deal with larger n.

Anyways, the plots show that the number of cliques anecdotally falls somewhere between $$\mathcal{O}(n^2)$$ and $$\mathcal{O}(n^3)$$. Assuming Pennylane's implementation is finding the maximum cliques, this is an equivalent definition of minimum clique cover. In addition to commutativity, there's degeneracy in the pauli group, meaning you can form other pauli strings by taking products of a subset of pauli matrices, this helps a lot in getting the $$4^n$$ scaling for the Pauli group down to something polynomially scaling in the number of unique measurements. For qubit-wise commuting Pauli operators, we observe slighty worse scaling (closer to $$\mathcal{O}(n^3)$$) number of individual measurements.

#%%
#DOCUMENTATION:
import pennylane as qml
from pennylane import grouping
import matplotlib.pyplot as plt

pauli_n = lambda n: list(grouping.pauli_group(n))
grouped_terms = lambda n: grouping.group_observables(pauli_n(n), grouping_type="commuting")

num_terms = lambda n: len(grouped_terms(n))
N = 5
sizes = [num_terms(n) for n in range(1,N+1)]
nk = lambda k : [n**k for n in range(1,N+1)]
plt.plot(range(1,N+1), sizes, label ='Number of commuting subgroups of P^n')
plt.plot(range(1, N+1), nk(2), label = "$$n^2$$")
plt.plot(range(1, N+1), nk(3), label = "$$n^3$$")
plt.legend()
plt.show()
#%%
#QW Commutator
grouped_terms = lambda n: grouping.group_observables(pauli_n(n))
num_terms = lambda n: len(grouped_terms(n))
sizes = [num_terms(n) for n in range(1,N+1)]
nk = lambda k : [n**k for n in range(1,N+1)]
plt.plot(range(1,N+1), sizes, label ='Number of commuting subgroups of P^n (QWC)')
plt.plot(range(1,N+1), nk(2), label = "$$n^2$$")
plt.plot(range(1,N+1), nk(3), label = "$$n^3$$")
plt.legend()
plt.show()
# %%


• Thank you! Very interesting. May 20, 2022 at 20:09
• You're welcome! If you haven't already, check out the link on the comment in the question, i think it will help answer some of the questions you may have. May 20, 2022 at 20:10

There are already some papers that investigate the idea of converting the problem of VQE measurement optimization to minimum clique cover problem:

• Thank you. I've skimmed these in the past but never found an answer to this exact question. Guess I'll need to really check them again! May 20, 2022 at 20:17