Counterexamples to the fractional coloring conjecture for triply efficient shadow tomography

Abstract: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 $\chi_{f}$ for its anticommutation graph. Conjecture 13 in King, Gosset, Kothari, and Babbush [PRX Quantum 6, 010336 (2025)] states that if $B_\epsilon(\varrho)$ is the set of Pauli observables having expectation value magnitude at least $\epsilon$ in some given quantum state $\varrho$, then the fractional chromatic number of the anticommutation graph $G$ induced by $B_\epsilon(\varrho)$ is $O(\epsilon^{-2})$. In other words, it asserts that there exists a constant $C$ such that $\chi_{f} \cdot \epsilon^2 \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_\epsilon$. 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 $\beta$ number of a graph. The key ingredient in the proofs can be seen as an instance of the amplification trick, where fractional chromatic numbers, $\beta$ numbers, and expectation values are amplified through lexicographic graph products.

14 pages. Found with GPT Sol 5.6. Comments welcome!

arXiv:2608.20113 [quant-ph]

(or arXiv:2608.20113v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2608.20113 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.