⚛️ quantum physics

Binary Optimization of Measurement Groupings for Quantum Energy Estimation

This paper demonstrates that formulating measurement grouping for quantum energy estimation as a classical binary optimization problem, specifically using mixed-integer linear programming and overlapping clique selection, significantly reduces sampling costs across molecular and lattice Hamiltonians compared to standard sorting-based strategies.

Original authors: Isaac L. Huidobro-Meezs, Rodrigo A. Vargas-Hernández

Published 2026-10-08

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Isaac L. Huidobro-Meezs, Rodrigo A. Vargas-Hernández

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

To understand the energy of a molecule, scientists often turn to quantum computers, devices that use the strange rules of the subatomic world to solve problems too complex for traditional machines. However, simply preparing a quantum state is not enough to know its energy; researchers must repeatedly measure that state to infer the answer. This process of repeated measurement is costly, consuming the vast majority of the computing resources available. The challenge lies in deciding which parts of the molecule's energy equation to measure together. Some parts can be measured simultaneously without interfering with one another, while others must be measured separately. If scientists group these parts inefficiently, they waste time and resources on unnecessary repetitions. The goal is to find the best way to bundle these measurements so that the total number of times the computer needs to run is as small as possible, making practical quantum chemistry a reality.

A team of researchers at McMaster University has developed a new method to solve this grouping problem, treating it as a puzzle of optimization rather than a simple list of rules. They approached the task by first looking at the molecule's energy equation as a collection of many different terms. Their strategy involves sorting these terms into groups where every item in a group can be measured at the same time. To do this effectively, they used a powerful mathematical tool called mixed-integer linear programming, which acts like a highly efficient sorter that tests millions of possible combinations to find the arrangement that requires the fewest measurements. They tested this approach on a variety of molecular systems, from simple hydrogen chains to more complex molecules like water and ammonia.

The results showed that their optimized groupings were significantly better than the standard methods currently in use. On average, their new approach reduced the number of required measurements by nearly 52 percent compared to the previous best technique. This means that for the same level of precision, a quantum computer would need to run roughly half as many times. The researchers also found that these optimized groups were robust; a grouping designed for one specific shape of a molecule worked very well for slightly different shapes of the same molecule, saving the need to recalculate the entire strategy for every tiny change in the molecule's geometry. This transferability is crucial because molecules in the real world are constantly vibrating and changing shape.

Beyond just grouping terms that do not overlap, the team also explored a more advanced strategy where a single term could be shared across multiple groups. They developed a method to select these overlapping groups directly, rather than just refining an initial non-overlapping list. While this direct search offered only a modest extra improvement over their already strong initial method, it proved that the quality of the group selection itself was more important than simply running more refinement steps. In fact, their direct search method achieved a 27 percent reduction in measurement requirements compared to the standard approach, even though it used far fewer refinement steps. This suggests that finding the right structure for the groups is the key to efficiency, rather than just tweaking the numbers afterward.

The study also extended beyond simple molecules to test these methods on complex lattice models used in physics, which represent different kinds of quantum interactions. In these cases, the new optimization methods substantially outperformed the standard strategies, confirming that the approach works across different types of quantum problems. The researchers concluded that by using variance-informed optimization—meaning they used estimates of how the measurements fluctuate to guide their choices—they could drastically cut the sampling costs for both molecular and lattice Hamiltonians. Their work demonstrates that a smart, mathematically rigorous way of organizing measurements can make quantum energy estimation much more feasible, providing a strong foundation for future applications in chemistry and physics without needing to change the underlying quantum hardware.

Technical Summary: Binary Optimization of Measurement Groupings for Quantum Energy Estimation

Problem Statement
In variational quantum algorithms, determining the energy of a quantum state requires repeated measurements to infer expectation values. This sampling cost often dominates the computational resources required, particularly for electronic structure problems where the qubit Hamiltonian comprises many Pauli terms. While compatible (commuting) Pauli terms can be measured simultaneously to reduce circuit executions, the statistical fluctuations within these groups determine the total number of shots required to achieve a target precision. Existing strategies, such as sorted insertion (SI), often rely on state-independent heuristics that do not fully account for state-dependent correlations. Furthermore, while overlapping measurement strategies (where a Pauli term contributes to multiple groups) can reduce variance beyond non-overlapping partitions, they typically rely on non-overlapping initializations that may not be optimal for subsequent coefficient splitting.

Methodology
The authors formulate the design of measurement groupings as a classical binary optimization problem, distinguishing three levels of optimization: (I) constructing non-overlapping groups, (II) optimizing overlapping coefficients from variance-informed initializations, and (III) directly searching for overlapping measurement supports.

Non-Overlapping Grouping (MILP): The authors model the commutativity graph of Pauli words, where vertices represent terms and edges represent commutativity. They define the measurement cost objective $\varepsilon^2 M$ based on the sum of standard deviations of group variances, which depends on state-dependent covariances. To solve this, they construct a pool of candidate cliques (compatible groups) derived from graph coloring and greedy partitions. They then employ Mixed-Integer Linear Programming (MILP) to select a set of non-overlapping cliques that minimizes the measurement cost. This approach uses approximate covariances (e.g., from CISD) during optimization but evaluates performance using exact covariances.
Iterative Coefficient Splitting (MILP-ICS): The optimized non-overlapping groups serve as an initialization for Iterative Coefficient Splitting (ICS). In this phase, coefficients are redistributed among the groups to minimize variance while preserving the Hamiltonian, allowing for overlapping supports.
Direct Overlapping Optimization (O-clique): The authors introduce "O-clique," a method that directly optimizes overlapping supports. Instead of optimizing the membership matrix directly, O-clique selects from a finite pool of candidate cliques (including those from MILP and SI) and simultaneously optimizes coefficient profiles. This is formulated as a linear MILP where continuous multipliers scale pre-defined coefficient profiles to satisfy Hamiltonian reconstruction. The method uses heuristics (Relative Standard Deviation, Relative Variance, or Softmax) to initialize these profiles before a final, brief ICS refinement.

Key Results
The study benchmarks these methods on molecular Hamiltonians (e.g., H4, LiH, MgO) and lattice models (Fermi–Hubbard, Kitaev–Heisenberg– $\Gamma$ , XYZ).

Non-Overlapping Optimization: The MILP-based grouping reduces the non-overlapping measurement requirement ( $\varepsilon^2 M$ ) by an average of 51.8% compared to Sorted Insertion (SI) across molecular benchmarks.
Initialization for Overlapping Methods: Using MILP groups to initialize ICS (MILP-ICS) yields a significant improvement over ICS initialized from SI (SI-ICS). The paper reports an average performance ratio of R = 3.79 (where $R = \varepsilon^2 M(\text{SI}) / \varepsilon^2 M(\text{Method})$ ), with a maximum ratio of 8.42 for MgO, indicating a substantial reduction in measurement cost compared to the SI initialization.
Transferability: Optimized groupings demonstrate robustness across nearby molecular geometries. When reused for potential energy surface scans, MILP groupings maintain significant savings (e.g., 39.7% reduction for H4) compared to SI, even without re-optimization. Simple heuristic refinements (MILP-R) further mitigate performance degradation at distant geometries.
Direct Overlapping Optimization (O-clique): O-clique reduces the measurement requirement relative to SI-ICS (after 100 iterations) by 16.0%–41.3% across the tested systems, despite using only five final coefficient refinement iterations. This suggests O-clique identifies higher-quality overlapping supports rather than merely benefiting from extended coefficient optimization. However, the incremental gain over the already optimized MILP-ICS baseline is modest (generally <10%), indicating diminishing returns for the additional classical search cost.
Lattice Hamiltonians: The superiority of MILP-based groupings over SI-based strategies extends to lattice models with qualitatively different interaction structures.

Significance and Claims
The paper claims that variance-informed optimization of measurement group structures can substantially reduce sampling costs across both molecular and lattice Hamiltonians. The authors posit that:

Optimized non-overlapping groups provide strong, transferable initializations for overlapping methods, outperforming standard heuristics.
Direct optimization of overlapping supports (O-clique) offers further gains by identifying superior support structures, though the marginal benefit over a well-initialized ICS (MILP-ICS) is limited.
The trade-off between classical optimization time and quantum measurement savings warrants the use of MILP for initialization, with O-clique serving as a secondary refinement step when additional classical resources are available.

The work establishes that moving beyond state-independent heuristics to variance-aware binary optimization is a viable strategy for mitigating the sampling bottleneck in variational quantum algorithms.

More like this