We present an efficient method for construction of a fully anticommutative set of Pauli generators (elements of the Pauli group) from a commutative set of operators that are composed exclusively from Pauli x̂ operators (purely X generators) and sorted by an associated numerical measure, such as absolute energy gradients. Our approach uses the Gauss–Jordan elimination applied to a binary matrix that encodes the set of X generators to bring it to the reduced row-echelon form, followed by the construction of an anticommutative system in a standard basis by means of a modified Jordan–Wigner transformation and returning to the original basis. The algorithm complexity is linear in the size of the X set and quadratic in the number of qubits. The resulting anticommutative sets are used to construct the qubit coupled cluster Ansatz with involutory linear combinations of anticommuting Paulis (QCC-ILCAP) proposed in J. Chem. Theory Comput. 2021, 17 (1), 66–78. We applied the iterative qubit coupled cluster method with the QCC-ILCAP Ansatz to calculations of ground-state potential energy curves for symmetric stretching of the water molecule (36 qubits) and dissociation of N 2 (56 qubits).
The cost of measuring quantum expectation values of an operator can be reduced by grouping the Pauli string (SU(2) tensor product) decomposition of the operator into maximally commuting sets. We detail an algorithm, presented in [1], to partition the full set of m-qubit Pauli strings into the minimal number of commuting families, and benchmark the performance with dense Hamiltonians on IBM hardware. Here we also compare how our method scales compared to graph-theoretic techniques for the generally commuting case.
Fractional graph colorings are useful for the Shadow tomography of Pauli observables. In practice, it is desirable that any experimentally interesting set of Pauli operators has a small fractional chromatic number
χf for its anticommutation graph. Conjecture 13 in King, Gosset, Kothari, and Babbush [PRX Quantum 6, 010336 (2025)] states that if
Bε(ϱ) is the set of Pauli observables having expectation value magnitude at least
ε in some given quantum state
ϱ, then the fractional chromatic number of the anticommutation graph
G induced by
Bε(ϱ) is
O(ε−2). In other words, it asserts that there exists a constant
C such that
χf⋅ε2≤C on all states and graphs. If the conjecture were true, it would imply that there exists a triply efficient Pauli shadow tomography algorithm for {\it any} subset
S of Pauli observables, provided that there is also an efficient fractional coloring algorithm for the set
Bε. Here we show that the conjecture is false by constructing a family of states and observables for which no finite
C satisfying the bound exists. We also give a more general construction relying on the commutation index or
β number of a graph. The key ingredient in the proofs can be seen as an instance of the amplification trick, where fractional chromatic numbers,
β numbers, and expectation values are amplified through lexicographic graph products.