Counterexamples to the fractional colouring conjecture for Pauli shadow tomography
The fractional chromatic number of the anticommutation graph of large-expectation Pauli observables is not bounded by a constant over epsilon squared, removing a proposed route to triply efficient shadow tomography.
- Lab
- Independent
- Model
- GPT-5.6 Sol
- Field
- Physics
- Date
- 2026-08-20
- Human collaborators
- Jędrzej Stempin, Santiago Llorens, Felix Huber
- Problem posed
- 2025 · open 1 yr
What was found
Fractional graph colourings are used in shadow tomography of Pauli observables, and it is desirable that any experimentally interesting set of Pauli operators have a small fractional chromatic number for its anticommutation graph. Conjecture 13 of King, Gosset, Kothari and Babbush states that for the set of Pauli observables whose expectation value in a given state has magnitude at least epsilon, the fractional chromatic number of the induced anticommutation graph is order epsilon to the minus two. The paper gives counterexamples, so no such constant exists; had the conjecture held it would have implied a triply efficient Pauli shadow tomography algorithm for any subset of Pauli observables given an efficient fractional colouring algorithm.
Novelty check
The conjecture is pinned to a specific numbered statement in a specific published paper, Conjecture 13 of King, Gosset, Kothari and Babbush in PRX Quantum 6, 010336 (2025), which leaves no ambiguity about what is being refuted or when it was posed. The consequence that fails with it, a triply efficient algorithm for arbitrary Pauli subsets, is stated in the same source. No prior counterexample appears.
Caveats and known objections
A preprint, unrefereed, not formalized, with no independent check on record, and vibemathed lists it as a candidate pending review. Autonomy is graded collaborative rather than ai-led because the disclosure is a single sentence with no account of the division of labour between the model and the three authors, and the weaker grade wins when the reading is arguable. The sentence, in full, is: GPT Sol 5.6 was used to derive the main results (Theorem A and Theorem B) of this paper.
Also recorded at
vibemathedfractional-colouring-pauli-shadow-tomography
Nothing mechanically. It is a parallel listing of the same result, carrying its own verification label rather than an independent check.
Nobody outside the lab has checked this yet.
Reading the primary source closely enough to say whether it supports the claim counts as a check, and you are credited on the entry.
Or on GitHub: submit a check challenge the grade send a correction or send a pull request
Flag this for triage
Signals order the review queue and nothing else. They are never published, and they never move a grade: that takes a citation.
Entry history (1 event)
- AddedEntered the registry graded Author verified and Collaborative.
Entries are never deleted. A grade that does not hold up is downgraded on the record, with the reason beside it.
Graded author verified for verification and collaborative for autonomy. What these mean.
Cite this entry
whataifound.org. (2026). Counterexamples to the fractional colouring conjecture for Pauli shadow tomography. whataifound.org: A Registry of AI Scientific and Mathematical Discoveries. https://whataifound.org/finding/2026-08-20-pauli-fractional-colouringBibTeX
@misc{whataifound-independent-2026-colouring,
title = {Counterexamples to the fractional colouring conjecture for Pauli shadow tomography},
author = {{whataifound.org}},
year = {2026},
howpublished = {whataifound.org: A Registry of AI Scientific and Mathematical Discoveries},
note = {Result by Independent. Verification: Author verified. Autonomy: Collaborative.},
url = {https://whataifound.org/finding/2026-08-20-pauli-fractional-colouring}
}