Counterexamples to the fractional coloring conjecture for triply efficient shadow tomography

Introduction

Let $\mathcal{P}_n = \{I, X, Y, Z\}^{\otimes n}$ be the set of $n$-qubit Pauli strings. The task of Pauli shadow tomography asks for simultaneous estimates of $\operatorname{tr}(\varrho P)$ for the Pauli strings $P$ in a given set $S \subseteq\mathcal{P}_n$, using as few copies of the unknown state $\varrho$ as possible. A simple approach to tomography is to group the observables into disjoint sets of mutually commuting Pauli strings, which can then be measured in common Clifford bases. Clearly, a larger number of disjoint sets requires more samples. To understand more elaborate strategies, consider the anticommutation graph, whose vertices are connected if the corresponding Pauli strings anticommute. Fractional coloring then allows one to measure using distributions over commuting families instead of a single partition.

More precisely, the task of shadow tomography is:

AI statement: GPT Sol 5.6 was used to derive the main results (Theorem A and Theorem B) of this paper. The authors verified and contextualized all results.

Let us describe two results by King, Gosset, Kothari, and Babbush [1]. In both cases, one assumes that the fractional coloring of the corresponding anticommutation graph can be sampled with a classical randomized algorithm with runtime $T$.

The single-copy protocol learns a Pauli set $S\subseteq\mathcal{P}_n$ with Clifford measurements with high probability within error $\epsilon$ with complexity [1 Theorem 5]:

Here $\chi_f$ is the fractional chromatic number of the anticommutation graph of $S$. Note that the lower bound on sample complexity is $\Omega(\chi_f/\epsilon^2)$ samples [2].

The two-copy protocol first uses Bell measurements to identify the set $S_\epsilon$ of Pauli strings with large expectation values, after which partitions arising from a fractional coloring of the anticommutation graph $G(S_\epsilon)$ are used to measure them. The complexity to learn $S$ to high probability with error $\epsilon$ is [1 Lemma 20]:

In this case $\chi_f$ is the fractional chromatic number of the anticommutation graph induced by $S_\epsilon$ (not $S$).

One sees that for both the single- and two-copy protocols, the fractional chromatic number directly influences the sample and time complexities.

As one requires to learn Pauli expectations to within error $\epsilon$, define for any state $\varrho$ the set

A key question is whether a large $\epsilon$ forces the anticommutation graph of $B_\epsilon(\varrho)$ to have a small fractional chromatic number ². In particular, the following conjecture asserts that $\chi_f(B_\epsilon(\varrho))=O(1/\epsilon^2)$. If true, the sample complexity of the two-copy protocol would collapse to $O(\log|S|/\epsilon^4)$, termed sample-efficient in Ref. [1] ³.

We state the conjecture by King, Gosset, Kothari, and Babbush verbatim ⁴.

Rephrased as an inequality, Conjecture 2 asserts: there exists a constant $C$, such that for every state $\varrho$ and error $\epsilon$

where $\chi_{\mathrm{f}}$ is the fractional chromatic number of the anticommutation graph of $B_{\epsilon}(\varrho)$.

In this paper we provide both a specific construction and a generic graph property that shows that such $C$ does not exist.

Related works

The general task of shadow tomography, introduced by Aaronson [3], asks how many copies of an unknown state are required to estimate the outcome probabilities of any set of two-outcome observables (i.e., not only Paulis). Among subsequent developments in the general shadow tomography problem [4, 5], recent work has obtained dimension-independent bounds [6].

A related but slightly different framework is that of classical shadows [7]. Here randomized measurements are used to construct a classical description of the state, from which one is able to reconstruct the expectation values of many (typically low-weight) observables.

Shadow tomography has also been studied in more structured settings, including thermal states with an accessible Hamiltonian [8] and Pauli and fermionic observables [1, 2].

Note that our results concern the shadow tomography setting where one wants to measure a set of Pauli strings using few (i.e. a constant) number of copies.

Contributions

The aim of this paper is to show that Conjecture 2 is false, equivalently, that an inequality as in Eq. (4) cannot hold.

This is proven in Theorem 4 and Corollary 5 in § 5. It relies on the amplification [9] of certain graph properties through the lexicographic product.

A more general statement can be made using the machinery of $\beta$ numbers, a graph invariant that is related to quantum properties. It is compared against the independence number $\alpha$, that is the size of the largest subset of disconnected vertices.

In particular, graphs with this property exist. For example, $\overline{C}_7$ satisfies the hypothesis $\alpha< \beta$ of Theorem B, so the counterexample of § 5 can be seen as an instance of Theorem 6 but with a simpler proof.

Theorem B is proven via Theorem 6 in Section 6. It also relies on an amplification trick, together with an inequality for partial sums.

Proof sketch

We sketch the proof of Theorem A. Our second main result, Theorem B, has a similar flavour; however, it requires the introduction of slightly more machinery. In what follows we drop $\varrho$ from $B_{\delta}(\varrho)$ when the state in question is clear, and likewise for other sets defined by a state.

We provide a counterexample that violates Inequality (4) via the following construction: Consider the anti-heptagon $\overline{C}_{7}$, and denote by $\mathcal{A}=\{A_{1},\ldots,A_{7}\}$ seven Pauli strings which realize it as an anticommutation graph. Consider $H=\sum_{A\in\mathcal{A}}A$ and denote its ground state by $\varrho$. One can check that every operator $A\in\mathcal{A}$ has the same expectation value, namely

Since the fractional chromatic number of the anti-heptagon is $\chi_{\mathrm{f}}(\overline{C}_{7})=7/2$, it follows that

The key idea is to amplify this inequality through lexicographic graph products (illustrated in Figure 1), so that the right hand side of Eq. (6) becomes unbounded. To this end, take the $m$-fold product of $\overline{C}_{7}$, yielding the graph $\overline{C}_{7}^{\operatorname{lex} m}$. Corresponding to it are a state $\varrho_{m}$ and a set $\mathcal{A}^{m}$ containing $7^{m}$ Pauli observables, which are constructed in more detail in § 5.

The amplification trick uses that

The first property follows from the well-known fact $\chi_{\mathrm{f}}(G\operatorname{lex}H)=\chi_{\mathrm{f}}(G)\cdot\chi_{\mathrm{f}}(H)$ [10 Corollary 3.4.5]. We show the second property in § 5.

Now write $G(S)$ for the anticommutation graph induced by the set $S$. Also, from now on use a shorthand $\chi_{\mathrm{f}}(S)=\chi_{\mathrm{f}}(G(S))$ for any observable set $S$. Set $\epsilon_{m}=a^{m}$. Note that for the state $\varrho_{m}$, $G(\mathcal{A}^{m})$ is an induced subgraph of $G(B_{\epsilon_{m}})$.

The fractional chromatic number is monotone under induced subgraphs, and $\chi_{\mathrm{f}}(\mathcal{A}^{m})\leq\chi_{\mathrm{f}}(B_{\epsilon_{m}})$ holds.

This yields the following inequality

The right hand side is unbounded under repeated lexicographic graph products, i.e. when $m\to\infty$. Hence the inequality (4) cannot hold, and Conjecture 2 is false.

Concepts

Anticommutation graphs

Consider a set $S\subset\mathcal{P}_{n}$ of Pauli strings. Its anticommutation graph $G(S)$ has as vertices the elements of $S$, with edges between them if the corresponding Pauli strings anticommute,

Naturally, an independent set in $G(S)$ corresponds to a pairwise commuting family of Paulis.

We call a set of ($\pm$ signed) Pauli strings $S$ a realization of graph $G$, if the anticommutation graph of $S$ equals $G$. Every graph $G$ allows for a realization in terms of Pauli strings [11].

Independence, chromatic, and $\beta$ numbers

Denote the maximum size of an independent set, the independence number, as $\alpha(G)$. Let $\mathcal{I}(G)$ denote the set of independent sets of a graph $G$. Denote its independence number by

The chromatic number $\chi(G)$ is the minimum number of colors that can be assigned to the vertices such that no two adjacent vertices share a color.

The fractional chromatic number is a linear-programming relaxation of the chromatic number,

Here each independent set receives a nonnegative weight and every vertex must receive total weight at least one.

Finally, for $\mathcal{A}$ a realization of $G$, define the $\beta$ number as

In particular, $\beta$ is independent of the particular Pauli string realization [12 Section IV, Theorem 3].

We will use the following four facts. These are all standard (see e.g. [10, 13]) apart from the monotonicity and multiplicativity of $\beta$ [12] and Item (d) [14].

(a) Let $H$ be an induced subgraph of $G$. Then

(b) $\alpha$, $\chi_{\mathrm{f}}$, $\beta$ are multiplicative under the lexicographic product (cf. the next section),

(c) For all graphs,

Equality holds if $G$ is vertex-transitive.

(d) For all graphs, $\alpha(G) \le\beta(G)$.

Hereafter, we simply use $|V|$ for $|V(G)|$ when the context is clear.

Lexicographic graph products

Let $G=(V,E)$ and $H=(W,F)$. The lexicographic product $G$ lex $H$ has vertex set $V \times W$ and edges

The idea is simple: at each vertex of $G$ (branch) place a copy of $H$ (a leaf). Then connect the vertices among different leaves if and only if their branches are connected. This is illustrated in Figure 1. We write $G^{\operatorname{lex} 1}=G$ and $G^{\operatorname{lex} m+1}=(G^{\operatorname{lex} m}\operatorname{lex}G)$ for the lexicographic powers.

Realizing observables for lex products

Given two observable sets $S$ and $T$ with anticommutativity graphs $G$ and $H$, how can the $G$ lex $H$ be realized? We give a small example:

Example 3. Let $G=L_3$ and $H=C_3$. The graph $G$ is realized by $T=\{XI,ZZ,IX\}$, and $H$ is realized by $R=\{X,Y,Z\}$. A set realizing $(G\operatorname{lex}H)$ is

Here the first register is occupied by the observables $T$ of $G$. The second register hosts the observables $R$ of $H$, with a separate tensor factor (three of them in total) reserved for each copy of $H$.

We now follow with a generic construction [12]. Let $T=\{T_1,\ldots,T_t\}$ and $R=\{R_1,\ldots,R_r\}$ realize $G$ and $H$ respectively. Then the following set realizes $G$ lex $H$ as anticommutation graph,

Here $T_i$ is placed on the first register, and $R_j$ placed onto the $i$-th tensor factor of the second register, where the second register contains $|V(G)|$ internal tensor factors. In the following we denote by $T^{\operatorname{lex} m}=(T\operatorname{lex}\cdots\operatorname{lex}T)$ ($m$ times) the $m$-fold lex product of the observable set $T$.

Anti-heptagon as a counterexample

We now construct the set of states and Pauli strings that serve as counterexample to Conjecture 2. Consider the following set that realizes the anti-heptagon $\overline{C}_7$ (see Figure 2),

Consider the Hamiltonian $H=\sum_{A\in\mathcal{A}} A$ and let $\varrho_{\min}$ be its ground state (see Appendix § 8). One can check that the expectation values are equal for all observables $A\in\mathcal{A}$

We also note that $\chi_f(\overline{C}_7)=\frac{7}{2}$, which follows from the fact that $\overline{C}_7$ is vertex transitive and $\alpha(\overline{C}_7)=2$.

Amplified observables and state

As amplified set of observables, we take the observables that realize the $m$-fold lex product $\overline{C}_7^{\operatorname{lex}m}$, namely

As amplified state, we take

where $K$ is the total number of tensor factors required for the construction of $\mathcal{A}^m$. Due to the fact that on each register there is only one non-trivial tensor factor in the state, it follows that

Counterexample

We are ready to state the counterexample.

Proof. Let $\mathcal{A}^{m}$ and $\varrho_m$ be as given in Eq. (21) and Eq. (22). Then consider the set

where $n$ is chosen large enough to host the state $\varrho_m$. From now on write $B_{\epsilon_m}$ for $B_{\epsilon_m}(\varrho_m)$.

Set $\epsilon_m=a^m$. Clearly, the set $\mathcal{A}^m$ is a subset of $B_{\epsilon_m}$, because every element in $\mathcal{A}^m$ has expectation value magnitude of exactly $\epsilon_m$. It follows that $G(\mathcal{A}^m)$ is an induced subgraph of $G(B_{\epsilon_m})$. By Fact (a) on fractional chromatic numbers Eq. (13), one has $\chi_f(\mathcal{A}^m)\leq\chi_f(B_{\epsilon_m})$. Then

Here we have used the value of $a=\frac{1+2\sqrt{2}}{7}$ from Eq. (20) and the multiplicativity of $\chi_f$ Eq. (14). Letting $m\longrightarrow\infty$, one can see that the right hand sied in above inequality is unbounded.

Thus there does not exist a finite constant $C$ such that $\chi_f(B_{\epsilon}(\varrho))\epsilon^2\leq C$ holds for all graphs, states, and errors.

This ends the proof. □

Scaling

Let us now consider the scaling of the fractional chromatic number in the case of the anti-heptagon.

Proof. Note that the proof in Theorem 4 still provides a counterexample to $\chi_f$ scaling as $O(\epsilon^{-s})$, if

due to the amplification occurring in Eq. (25). Taking a logarithm of the condition,

Thus

Thus necessarily, $\chi_f(B_{\epsilon_m})$ must scale at least as $\Omega(\epsilon^{-2.07598})$. □

Amplification through the $\beta$ number

Let $G$ be realized as an anticommutation graph by a set of Pauli strings $\mathcal{A}$. Consider the $\beta$-number (or commutativity index),

Here the maximization is taken over all quantum states $\varrho$. The $\beta$ number was introduced in Ref. [12, 14] and since then appeared in many different contexts in quantum information theory [12, 15, 16, 17, 18, 19, 20].

Denote by $\alpha$ and $\vartheta$ the independence number and the Lovász number of a graph. It holds that [14, 15],

Ref. [12] showed that the left-hand side of the Eq. (30) is not tight. In particular, the anti-heptagon has $2=\alpha(\overline{C_7})<\frac{9+4\sqrt{2}}{7}\le\beta(\overline{C_7})$.

Now note that the proof in § 5 uses the fact that the expectation values of all $A\in\mathcal{A}$ on $\varrho$ are both constant and sufficiently high. Thus it is tempting to think that a high $\beta$ number alone will be sufficient for constructing a counterexample to Conjecture 2.

This is indeed the case.

Note that if $\alpha(G)<\beta(G)$, then the expression on the right-hand side of the Eq. (31) is unbounded as $m\to\infty$: the denominator $1+m\log N$ grows linearly while $\left(\frac{\beta(G)}{\alpha(G)}\right)^m$ grows exponentially. Thus, there does not exist a constant $C$ for which $\chi_{\mathrm{f}}\cdot\epsilon^2\le C$.

In particular, graphs with $\alpha(G)<\beta(G)$ exist [12]. It follows that:

We state the proof of Theorem 6 in § 6.2 and for now proceed with a rather standard auxiliary Lemma.

Threshold Lemma

Given a high value of $\beta$, we need to select those observables in $\mathcal{A}$ that show a sufficiently high squared expectation value. While the following proof is standard we reproduce it here for the reader. For this denote by $h_N$ a partial sum of the harmonic series,

Proof. Consider

Denote by $\ell^*$ the index such that $M=\ell^*y_{\ell^*}$.⁵ By definition, for any $1\le i\le N$ it holds that

Summing Eq. (36) over the values of $Y$ and using the partial harmonic series [Eq. (32)],

Now set $t=y_{\ell^*}$. Since the sequence $Y$ is non-increasing, the number of its elements that are greater or equal $y_{\ell^*}$ is at least $\ell^*$, that is, $|Y_t| \ge\ell^*$. With $M=\ell^*y_{\ell^*}$ we have

Last we show that $t \le y_1$. To see this, assume otherwise $t>y_1$. Then $|Y_t|=0$ and Ineq. (34) cannot hold, leading to a contradiction. Thus $t \le y_1$. This ends the proof. $\square$

Clearly, any sequence of non-negative numbers can be sorted so that Lemma 7 applies.

Proof of Theorem 6

Proof. Given a graph $G$, let $\mathcal{A}$ be its Pauli realization. Then by the construction in § 4.4, $\mathcal{A}^m=\mathcal{A}^{\operatorname{lex} m}$ is a Pauli realization of $G^{\operatorname{lex} m}$. Recall that if $\mathcal{A}$ has $N$ elements, then $\mathcal{A}^m$ contains $N^m$ elements.

Now let $\sigma$ be the state that achieves the value $\beta(G)$. Likewise, let $\sigma_m$ be the state that achieves the value $\beta(G^{\operatorname{lex} m})=\beta(G)^m$. Here we have used that the $\beta$ number is multiplicative under the lexicographic graph product [Eq. (14)]. Note that given $\sigma$ it is not obvious how to construct $\sigma_m$ explicitly, but this will not matter for the proof.

From now on, fix $m$ and consider the sequence

Order the set $\{y_A\}_{A\in\mathcal{A}^m}$ non-increasingly,

Note that $Y$ contains at least one non-zero element due to the fact that $\sigma_m$ is the maximizer of $\beta(G^{\operatorname{lex} m})$, it can only vanish for empty graphs.

We can then invoke Lemma 7: For this, recall that $Y_t=\{y_i\in Y\mid y_i\ge t\}$ is the set of elements from $Y$ that are greater or equal $t$. The Lemma states that there exists $0<t\le y_1$, such that

For given $m$, denote it as $t_m$. Rewriting the right hand side in terms of expectation values and using the fact that all $y_A$ arise from measuring observables of $\mathcal{A}^m$ on $\sigma_m$, this reads

Now set $\epsilon_m = \sqrt{0.99t_m}$. Then $\epsilon_m^2 < t_m \le\max_{A \in\mathcal{A}^m} y_A \le1$, as all $A$ are Pauli strings. This guarantees $\epsilon_m < 1$, thereby satisfying the requirement in Conjecture 2.

Consider a set of observables from $\mathcal{A}^m$ and some threshold $\delta$. Define

Recall the analogously defined quantity

where $\mathcal{P}$ is the set of all Pauli strings on the space of $\sigma_m$.

Let us observe two relevant graph inclusions: First, by $\epsilon_m \le\sqrt{t_m}$ and $\mathcal{A}^m \subseteq\mathcal{P}$, one gets the graphs inclusions,

For $H$ an induced subgraph of $G$ write $H \subseteq_i G$. From Eq. (45) then follows

Second, from $\mathcal{A}^m_{\sqrt{t_m}} \subseteq\mathcal{A}^m$ follows

Recalling that $Y$ is the set of squared expectation values $|\operatorname{tr}(A\sigma_m)|^2$,

Let us restate the necessary graph facts from § 4.2:

(a) Let $H$ be an induced subgraph of $G$. Then $\alpha(H) \le\alpha(G)$ and $\chi_f(H) \le\chi_f(G)$.

(b) For all $G$, $H$: $\alpha(G \operatorname{lex} H) = \alpha(G) \cdot\alpha(H)$ and $\beta(G \operatorname{lex} H) = \beta(G) \cdot\beta(H)$.

(c) For all $G$, $\chi_f(G) \ge\frac{|V(G)|}{\alpha(G)}$.

We are ready for the final chain of inequalities.

A standard integral bound on the partial sum of a harmonic sequence is (see e.g. the derivation of the Integral Test in [21 Theorem 9 in Section 10.3])

One can then lower bound the expression on the left hand side of Eq. (49) by:

This ends the proof of Theorem 6.

Conclusion

We have shown that any graph with $\alpha<\beta$ provides a counterexample to Conjecture 2. The key idea is that $\left(\frac{\beta}{\alpha}\right)$ can be amplified under the lexicographic graph product so that $\chi_{\mathrm{f}}(B_{\epsilon})\cdot\epsilon^2$ is unbounded.

We note that, while Conjecture 2 does not hold, it does not rule out the existence of a triply efficient shadow tomography protocol for arbitrary Pauli sets, for example a sample-efficient protocol with $\chi_{\mathrm{f}}$ scaling as $\operatorname{poly}(1/\epsilon)$. In particular, Conjecture 2 is stronger than required for sample-efficient tomography alone: any upper bound on $\chi_{\mathrm{f}}$ of the form $O(\epsilon^{-\kappa})$ yields a sample-efficient two-copy Clifford measurement protocol for any set of Paulis. Thus, a natural question is:

Question 8. Let $\varrho$ be an $n$-qubit state, $\epsilon\in(0,1)$, and let $B_{\epsilon}\subseteq\mathcal{P}_n$ be the set of all Paulis $P$ such that $\lvert\operatorname{tr}(\varrho P)\rvert\geq\epsilon$. Does there exist a number $\kappa>0$, so that every anticommutation graph $G(B_{\epsilon})$ has a fractional coloring of size $O(\epsilon^{-\kappa})$?

We leave this question open.

An explicit seed eigenvector

Let us recall that the state which was used to construct a counterexample to Conjecture 2 in § 5, was chosen as an eigenstate of the Hamiltonian $H=\sum_{A\in\mathcal{A}}A$, where $\mathcal{A}$ is a set of Pauli observables from Eq. (19). By direct calculation, one can verify that the smallest eigenvalue of $H$ equals

The corresponding ground state is

References

JĘDRZEJ STEMPIŃ¹, SANTIAGO LLORENS¹, AND FELIX HUBER¹

¹ Division of Quantum Information, Institute of Informatics, Faculty of Mathematics, Physics and Informatics, University of Gdańsk, Wita Stwosza 57, 80-308 Gdańsk, Poland

Email address: [email protected]