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.
Given copies of a quantum state ρ, a shadow tomography protocol aims to learn all expectation values from a fixed set of observables, to within a given precision ε. We say that a shadow tomography protocol is triply efficient if it is sample- and time-efficient, and only employs measurements that entangle a constant number of copies of ρ at a time. The classical shadows protocol based on random single-copy measurements is triply efficient for the set of local Pauli observables. This and other protocols based on random singlecopy Clifford measurements can be understood as arising from fractional colorings of a graph G that encodes the commutation structure of the set of observables. Here we describe a framework for two-copy shadow tomography that uses an initial round of Bell measurements to reduce to a fractional coloring problem in an induced subgraph of G with bounded clique number. This coloring problem can be addressed using techniques from graph theory known as chi-boundedness. Using this framework we give the first triply efficient shadow tomography scheme for the set of local fermionic observables, which arise in a broad class of interacting fermionic systems in physics and chemistry. We also give a triply efficient scheme for the set of all n-qubit Pauli observables. Our protocols for these tasks use two-copy measurements, which is necessary: sample- efficient schemes are provably impossible using only single-copy measurements. Finally, we give a shadow tomography protocol that compresses an n-qubit quantum state into a poly(n )-sized classical representation, from which one can extract the expected value of any of the 4n Pauli observables in poly(n ) time, up to a small constant error.
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.
A set of Pauli stings is well characterized by the graph that encodes its commutatitivity structure, i.e., by its frustration graph. This graph provides a natural interface between graph theory and quantum information, which we explore in this work. We investigate all aspects of this interface for a special class of graphs that bears tight connections between the groundstate structures of a spin systems and topological structure of a graph. We call this class
ℏ-perfect, as it extends the class of perfect and
h-perfect graphs.
Having an
ℏ-perfect graph opens up several applications: we find efficient schemes for entanglement detection, a connection to the complexity of shadow tomography, tight uncertainty relations and a construction for computing good lower on bounds ground state energies. Conversely this also induces quantum algorithms for computing the independence number. Albeit those algorithms do not immediately promise an advantage in runtime, we show that an approximate Hamilton encoding of the independence number can be achieved with an amount of qubits that typically scales logarithmically in the number of vertices. We also we also determine the behavior of
ℏ-perfectness under basic graph operations and evaluate their prevalence among all graphs.
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.