Fractional coloring conjecture for triply efficient shadow tomography

Let $\mathcal{P}_n$ denote the set of $n$ -qubit Pauli observables. For every $n$ -qubit quantum state $\varrho$ and every $\epsilon\in(0,1]$ , define $B_\epsilon(\varrho)=\{P\in\mathcal{P}_n:|\operatorname{Tr}(\varrho P)|\geq\epsilon\}$ . Let $G_{\epsilon,\varrho}$ be the graph with vertex set $B_\epsilon(\varrho)$ , in which two vertices are adjacent exactly when the corresponding Pauli observables anticommute. The conjecture asserts that there exists a universal constant $C<\infty$ such that, for all $n$ , all $n$ -qubit states $\varrho$ , and all $\epsilon\in(0,1]$ , $\chi_f(G_{\epsilon,\varrho})\leq C\epsilon^{-2}$ ; equivalently, $\chi_f(G_{\epsilon,\varrho})\epsilon^2\leq C$ .

Progress summary

Solved

A new preprint claims the conjecture is false and removes one proposed path to universally efficient shadow tomography, but the claim has not yet been independently confirmed.

The conjecture, posed by Chen et al. in 2024, asserts that the relevant Pauli commutation graph has fractional chromatic number $\chi_f=O(\delta^{-2})$ for every $n$ -qubit state. If true, this would enable triply efficient Pauli shadow tomography for arbitrary observable subsets.

Known results

Chen et al. (2024) formulated the conjecture as Conjecture 13 and identified it as open.
Chen et al. (2024) noted that an $O(\delta^{-2})$ bound on the fractional clique number would imply the conjecture by linear-programming duality.
Their related two-copy framework achieved only a coloring bound of $n^{O(1/\epsilon^2)}$ .

August 2026 counterexample

A preprint dated August 2026, “Counterexamples to the fractional coloring conjecture for triply efficient shadow tomography,” claims to disprove the universal $\chi_f=O(\epsilon^{-2})$ bound using lexicographic graph-product amplification. This would eliminate the proposed route to universally triply efficient Pauli shadow tomography, but the counterexample has not yet been independently verified.

Current status (as of August 2026): The conjecture has a claimed counterexample in a new preprint, but independent verification is absent, so its refutation is not yet confirmed.

Sources

Sources & referencesView supporting material

Primary source

arXiv

Additional references

Counterexamples to the fractional coloring conjecture for triply efficient shadow tomography — arXiv

graph-theory quantum-information

5 hours ago