Counterexamples to the fractional coloring conjecture for triply efficient shadow tomography

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_ε\(varrho\) is the set of Pauli observables having expectation value magnitude at least ε in some given quantum state varrho, then the fractional chromatic number of the anticommutation graph G induced by B_ε\(varrho\) is O\(ε^-2\). In other words, it asserts that there exists a constant C such that χ_f cdot ε² leq 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.