Bounding the Joint Numerical Range of Pauli Strings by Graph Parameters

The relations among a given set of observables on a quantum system are effectively captured by their so-called joint numerical range, which is the set of tuples of jointly attainable expectation values. Here we explore geometric properties of this construct for Pauli strings, whose pairwise commutation and anticommutation relations determine a graph $G$. We investigate the connection between the parameters of this graph and the structure of minimal ellipsoids encompassing the joint numerical range, and we develop this approach in different directions. As a consequence, we find counterexamples to a conjecture by de Gois et al. [Phys. Rev. A 107, 062211 (2023)], and answer an open question raised by Hastings and O’Donnell [STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 776–789], which implies a new graph parameter that we call “$\beta (G)$.” Furthermore, we provide new insights into the perennial problem of estimating the ground-state energy of a many-body Hamiltonian. Our methods give lower bounds on the ground-state energy, which are typically hard to come by, and might therefore be useful in a variety of related fields.

Popular Summary

A problem of most intense interest in physics and chemistry is the computation of ground-state energies in correlated many-body systems. This question plays a central role in condensed-matter physics and quantum chemistry. Because of the large size of typical systems and the complex interactions among the particles, the exact solution becomes impractical, and various numerical techniques have been developed since the early days of quantum mechanics. However, most of them provide upper bounds (by way of approximation of the ground state), and lower bounds (i.e., inaccessible regions) are rare. Here we show how to use tools from graph theory to lower-bound the ground-state energy of Hamiltonians made up of Pauli strings whose anticommutation and commutation relations are encoded in a graph—namely, the frustration graph.

A critical step in our approach is to convert the original problem into the estimation of the joint expectation values of Pauli strings. Previous studies either conjecture that the independence number of the frustration graph should be the squared radius of the joint expectation values or leave it as an open question. We show by explicit examples that this conjecture is false. As a consequence, we introduce a new graph parameter, which we call the “$\beta$ number,” and we embark on its exploration. Equivalent formulations of the $\beta$ number and numerical estimation tools are developed too. Interestingly, the $\beta$ number of any odd cycle coincides with its independence number, which is, however, not the case for odd anticycles with more than five nodes.

Since our study is closely related to multiple topics in quantum theory, graph theory, and algebra analysis, the present results might provide new insights in those fields as well.

Figure 1

Joint numerical ranges of three Pauli strings whose commutation and anticommutation relations are represented by the four possible graphs of three vertices. The real lines represent the anticommutation relations and the dashed lines stand for commutation relations.

Figure 2

Pentagon graph $C_5$.

Figure 3

A graph $G_{10}$ with ten vertices and one of its standard realizations, which contains a pentagon $C_5$ as an induced subgraph (thick green lines).

Figure 4

Graph of the counterexample and its SAUR. A pair of observables anticommute when the corresponding vertices are connected by an edge in the graph of an antiheptagon ${\overline{C}}_7$ (all blue lines) and commute when they are connected by an edge in the graph of a heptagon $C_7$ (thin green lines). The subgraph of ${\overline{C}}_7$ (solid blue lines) is named as “$G_7$.”

Figure 5

The estimation $\tilde{\beta }({\overline{C}}_{2n+1})$ of $\beta ({\overline{C}}_{2n+1})$ in comparison with $\vartheta ({\overline{C}}_{2n+1})$. For each estimation, we used the second see-saw method with 500 rounds of iteration.