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ε(ϱ) is the set of Pauli observables having expectation value magnitude at least
ε in some given quantum state
ϱ, then the fractional chromatic number of the anticommutation graph
G induced by
Bε(ϱ) is
O(ε−2). In other words, it asserts that there exists a constant
C such that
χf⋅ε2≤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.
Godsil, Roberson, Šámal and Severini conjectured that the quantum chromatic number of the categorical product of two graphs equals the minimum of the quantum chromatic numbers of the factors. We disprove this conjecture: we construct explicit finite graphs
G,H with
χ(G×H)≤1538<1539=min(χq(G),χq(H)).The graphs are obtained from Zhu's counterexample to Hedetniemi's conjecture by using a base graph for which the Lovász theta number of the complement, and not only the fractional chromatic number, is large. The lower bound for the first factor is the theta bound. For the second factor we adapt Zhu's argument to projections that do not commute: the step that fixes the colors of a clique is replaced by identities between operators. Both lower bounds hold for colorings by projections in an arbitrary nonzero unital
C∗-algebra. Hence the conjecture also fails for the spatial, approximate, commuting-operator and
C∗-algebraic variants of the quantum chromatic number. We also give smaller counterexamples certified by exact integer data. The graph constructions, the certificates and the counterexample statements in the projective formulation are formalized in Lean~4.
Shadow tomography protocols have recently emerged as powerful tools for efficient quantum state learning, aiming to reconstruct expectation values of observables with considerably fewer resources than traditional quantum state tomography. For the particular case of estimating Pauli observables, entangling two-copy measurement schemes can offer an exponential improvement in sample complexity over any single-copy strategy conceivable [1, Huang, Kueng, Preskill, PRL (2021)]. A recent refinement of these ideas by King et al. [2, King, Gosset, Kothari, Babbush, SODA (2025)] does not only achieve polynomial sample complexity, but also maintains reasonable computational demands and utilizes joint measurements on only a small constant number of state copies. This 'triple efficiency' is achievable for any subset of
n-qubit Pauli observables, whereas single-copy strategies can only be efficient if the Pauli observables in question have advantageous structure. In this work, we complement existing theoretical performance guarantees with the empirical evaluation of triply efficient shadow tomography using classical, noise-free simulations. Our findings indicate that the empirical sample complexity aligns closely with theoretical predictions for stabilizer states and, notably, demonstrates slightly improved scaling for random Gibbs states compared to established theoretical bounds. In addition, we improve a central subroutine in the triply-efficient shadow protocol by leveraging insights from a refined quantum and quantum-inspired convex optimization algorithm [3, Henze et al. arXiv:2502.15426 (2025)] [Henze et al. arXiv:2502.15426 (2025)]. To summarize, our empirical sample complexity studies of triply efficient shadow tomography not only confirm existing theoretical scaling behavior, but also showcase that the actual constants involved are comparatively benign. Hence, this protocol has the potential to also be very sample-efficient in practice.
We characterize the magic of random fermionic Gaussian states through their Pauli spectrum and their stabilizer entropies. For the Haar ensemble of Majorana Gaussian states we derive closed finite-
N expressions for the average stabilizer purities and reconstruct the Pauli spectrum exactly, as a mixture of products of beta-distributed variables resolved by Majorana weight. The stabilizer entropies, and their filtered versions, freeze at Rényi index
qc=2: for
q>2 the magic density is
1/(q−1), controlled by rare weight-two Majorana strings. Resolving these contributions requires exponentially many characteristic samples, making direct sampling estimates of the stabilizer entropies inefficient in this frozen regime. For Haar-random Gaussian states at fixed filling, we express the averaged stabilizer purities at positive integer
q as coefficient integrals over
SU(2q), with dimension independent of
N, and evaluate the
q=2 case exactly. We establish that the frozen density describes typical states in the Majorana and half-filled number-conserving ensembles and relate these ensembles to the corresponding
SYK2 ground states. Finally, we show that typical fermionic Gaussian states retain certified magic after discarding any fixed fraction
κ<κ⋆G≃0.7613 of their modes in the thermodynamic limit, remaining magical even beyond the
2/3 threshold for Haar-random states in the full Hilbert space.
Godsil, Roberson, Šámal and Severini conjectured that the quantum chromatic number of the categorical product of two graphs equals the minimum of the quantum chromatic numbers of the factors. We disprove this conjecture: we construct explicit finite graphs
G,H with
χ(G×H)≤1538<1539=min(χq(G),χq(H)).The graphs are obtained from Zhu's counterexample to Hedetniemi's conjecture by using a base graph for which the Lovász theta number of the complement, and not only the fractional chromatic number, is large. The lower bound for the first factor is the theta bound. For the second factor we adapt Zhu's argument to projections that do not commute: the step that fixes the colors of a clique is replaced by identities between operators. Both lower bounds hold for colorings by projections in an arbitrary nonzero unital
C∗-algebra. Hence the conjecture also fails for the spatial, approximate, commuting-operator and
C∗-algebraic variants of the quantum chromatic number. Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
Classical shadows are an influential framework for compressing copies of a given quantum state
ρ into classical data
S, enabling many properties of
ρ to be predicted from relatively few copies. In this work, we study two natural questions involving shadows: (1) Given
S, when can one efficiently verify that
S came from a genuine
n-qubit state? This is called the Classical Shadow Validity (CSV) problem, introduced by Karaiskos, Rudolph, Meyer, Eisert, and Gharibian [ICALP 2026]. (2) Given
S that allows one to capture 2-local properties of
ρ, can one fake or spoof a shadow
S′ which predicts 3-local properties of some state? For (1), we show CSV is efficiently solvable for permutation-invariant shadows, QMA-hard for real, fermionic, and bosonic shadows, and both coNP-hard and QMA-hard when the observable family consists of all
n-qubit Pauli strings. A result of independent interest along the way is a new upper bound qc-
Σ2 ⊆ PPP, where qc-
Σ2 is a quantum analogue of the second level of the polynomial hierarchy in which the first proof is quantum. For (2), we show intractability: Given the 2-local marginals
S of a quantum state
ρ, estimating the 3-local marginals of
ρ is intractable unless QCMA
⊆ BPP, even if the state
ρ is the unique state consistent with
S.