Fractional-chromatic bounds for Pauli shadow tomography

For a quantum state ρ, form the anticommutation graph of Pauli observables whose expectation magnitude is at least ε. Is its fractional chromatic number bounded by a universal constant times ε⁻²?

Why it matters and what counts as progress

Why it matters: The proposed bound is an ingredient in a Pauli shadow-tomography approach; sampling a fractional coloring is a separate requirement.

What counts as progress: A universal bound or a state-and-observable family whose fractional chromatic number grows faster than ε⁻², with the graph construction explicit.

How the problem developed

2025 · Conjecture [1]
Robbie King, David Gosset, Robin Kothari and Ryan Babbush Conjectured an O(ε⁻²) fractional-chromatic bound for the anticommutation graph of Pauli observables with expectation magnitude at least ε in a state.
20 Aug 2026 · Reported counterexample [2]
Jędrzej Stempin, Santiago Llorens and Felix Huber Constructed states and Pauli observables for which no uniform O(ε⁻²) bound holds; the authors state that GPT Sol 5.6 derived the main results and that they verified them.

AI contribution

Counterexamples to the fractional coloring conjecture for triply efficient shadow tomography

Jędrzej Stempin, Santiago Llorens, Felix Huber

Stempin, Llorens and Huber refute the proposed universal bound χ_f(B_ε(ρ)) = O(ε⁻²). Their Theorem A constructs states and Pauli sets from lexicographic powers of the complement of a seven-cycle for which χ_f(B_ε(ρ)) grows faster. Theorem B gives a broader counterexample criterion using anticommutation graphs with α(G) < β(G).

AI involvementAI-led

ImportanceNotable

Technical verificationFormal (human)

Human understandingFull