⚛️ quantum physics

Reducing quantum measurements in qubit-based overlapping grouping methods for quantum energy estimation through better initializations

This paper introduces VarSI, a family of covariance-informed non-overlapping Pauli grouping heuristics that significantly reduces measurement costs in quantum energy estimation by providing superior initializations for state-of-the-art overlapping grouping methods.

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

Published 2026-07-07

📖 5 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

Imagine you are trying to calculate the total energy of a complex molecule, like a tiny, intricate machine made of atoms. In the world of quantum computing, this is done by breaking the machine down into thousands of tiny parts (called "Pauli words") and measuring each one.

The problem? Measuring every single part individually is incredibly slow and expensive. It's like trying to weigh a massive pile of mixed coins by picking them up one by one, counting them, and putting them back down. If you have a million coins, this process will take forever.

The Current Solution: Grouping Coins

To speed things up, scientists use a strategy called grouping. Instead of measuring coins one by one, they try to find piles of coins that can be measured together in a single step.

The Old Way (Sorted Insertion): Imagine you have a bag of coins sorted by size. You grab the biggest coin and put it in a pile. Then you grab the next biggest. If it fits in the same pile (meaning it doesn't clash with the others), you add it. If not, you start a new pile. This is the standard method, known as Sorted Insertion (SI). It's a decent way to organize, but it's a bit rigid. It just looks at the "size" (coefficient) of the coin and doesn't care much about how the coins interact with each other.
The Advanced Way (Overlapping): Scientists recently discovered a trick: some coins can belong to multiple piles at the same time. This is called "overlapping." It's like a coin that is both a penny and a token for a game; you can count it for both groups simultaneously. This saves even more time. However, to make this work, you first need a good starting arrangement (a "seed") of non-overlapping piles.

The New Idea: VarSI (Variance-Aware Sorting)

The authors of this paper realized that the "seed" piles created by the old method (SI) weren't the best possible starting point. They asked: What if we organized the coins not just by size, but by how much they "wobble" (variance) and how they interact with their neighbors?

They introduced a new family of methods called VarSI (Variance-Aware Sorted Insertion).

Here is the analogy for how VarSI works:

The Old Method (SI): "I'll put the biggest coin in the first empty box I find."
The New Method (VarSI): "I'll look at the biggest coin, but before I put it in a box, I'll check: 'If I put this coin here, will it make the whole box shake violently? Or will it settle down nicely with the other coins?' I'll choose the box where it causes the least amount of chaos."

They use a "dictionary" of how the coins interact (covariance) to make these smart decisions. This dictionary is something the advanced "overlapping" methods already need, so VarSI gets this superpower for free without needing extra data.

Three New Strategies

The paper proposes three specific ways to build these better piles:

VarSI-O (Ordered): A smarter version of the old sorting method. It sorts coins by how much they "wobble" and places them in the best possible box based on that wobble.
VarSI-G (Global Greedy): This is the "picky" one. It looks at every remaining coin and every possible box to find the single best move to make right now. It's very thorough but takes more computer time to plan.
VarSI-R (Refinement): This is the "polisher." It takes an existing pile of coins (even one made by the old method) and starts shuffling them around. It moves a coin from one box to another only if it makes the whole system more stable. It keeps doing this until no more improvements can be found.

The Results: Saving Time and Money

The researchers tested these new methods on 130 different molecular "machines" (Hamiltonians). Here is what they found:

Better Starting Points: Even before using the advanced "overlapping" tricks, the new VarSI methods created better initial piles than the old standard. This reduced the number of measurements needed by about 38% on average.
Boosting the Advanced Methods: When they used these better piles to start the "overlapping" methods (specifically a technique called ICS), the savings were huge.
- Depending on the specific setup, they reduced the total measurements by 9% to 15% on average.
- In the best cases, they cut the measurements by up to 70%.
Real-World Impact: For a specific task involving the Nitrogen molecule ( $N_2$ ), using the best new method (VarSI-OR) saved about 1 hour of actual time on a quantum computer compared to the old way. For other tasks, it saved 20 to 40 minutes.

The Bottom Line

The paper proves that even if you plan to use fancy, overlapping measurement tricks later, how you start the process matters immensely. By using a smarter, "wobble-aware" way to organize the initial groups (VarSI), you can significantly reduce the time and resources needed to calculate molecular energies. It's a simple but powerful upgrade to the starting line that makes the whole race faster.

Technical Summary: Reducing Quantum Measurements in Qubit-Based Overlapping Grouping Methods through Better Initializations

Problem Statement
Estimating the expectation values of Hamiltonians is a central bottleneck in variational quantum algorithms (VQAs) for electronic structure and quantum machine learning. The number of Pauli words in molecular Hamiltonians scales as $O(N_q^4)$ , making direct measurement of each term impractical. While grouping strategies (partitioning Pauli words into compatible sets) reduce this cost, state-of-the-art overlapping methods, such as Iterative Coefficient Splitting (ICS) and Shared Pauli Products (SPP), rely on an initial set of non-overlapping "seed" fragments. These seeds are typically generated using the Sorted Insertion (SI) algorithm, which orders terms by coefficient magnitude. Recent findings suggest that the quality of this initial non-overlapping grouping significantly impacts the final measurement cost of overlapping methods, yet the optimization of these initializations remains an underexplored area.

Methodology
The authors introduce Variance-Aware Sorted Insertion (VarSI), a family of covariance-informed heuristic algorithms designed to generate superior non-overlapping Pauli groupings. Unlike standard SI, which sorts by coefficient magnitude ( $|c_i|$ ), VarSI utilizes a dictionary of Pauli covariances (already required by overlapping methods like ICS) to score candidate insertions based on their impact on the total measurement variance.

The paper defines three primary variants:

VarSI-O (Ordered): An analog to SI that sorts terms by their single-term variance contribution ( $v_i = c_i^2 C_{ii}$ ) and inserts them into the compatible group that minimizes the total measurement objective $\epsilon^2_M$ .
VarSI-G (Global Greedy): A more computationally expensive approach that dynamically selects the next term and its destination group to minimize the immediate variance, rather than following a fixed sorted order.
VarSI-R (Refinement): A local refinement step applied to groupings generated by SI or VarSI-O. It performs a sweep of one-term relocations between compatible groups, accepting moves only if they strictly reduce the measurement objective.

The measurement objective is defined as $\epsilon^2_M(G) = (\sum_{\alpha} \sqrt{\text{Var}_\psi(H_\alpha)})^2$ . The algorithms leverage the covariance update rule (Eq. 9 in the text) to efficiently calculate the variance change when a term is added to or removed from a group. The computational cost of VarSI-O is comparable to SI ( $O(N^2 n_q)$ ), while VarSI-G scales cubically ( $O(N^3)$ ).

Key Contributions

Derivation of Covariance Updates: The authors derive a specific covariance update rule that allows for the efficient scoring of candidate insertions without recalculating full group variances from scratch.
Algorithmic Framework: The proposal of VarSI-O, VarSI-G, and their refinement variants (VarSI-R, VarSI-OR) as a systematic way to improve non-overlapping groupings using covariance data.
Integration with Overlapping Methods: Demonstrating that these improved non-overlapping groupings serve as effective initializations for the ICS algorithm, creating a pipeline where better seeds lead to better final estimators.

Results
The methods were benchmarked on 130 molecular Hamiltonians (including LiH, BeH $_2$ , H $_2$ O, NH $_3$ , and hydrogen chains H $_4$ –H $_8$ ) using Jordan-Wigner (JW), Bravyi-Kitaev (BK), and Parity mappings. Covariance dictionaries were constructed using either exact ground-state wavefunctions or approximate Coupled Cluster with Single and Double excitations (CISD) wavefunctions.

Non-Overlapping Performance: The refinement variants (VarSI-R and VarSI-OR) consistently reduced measurement requirements compared to standard SI by 35–39% across the dataset, regardless of the covariance source or qubit mapping. VarSI-G generally failed to outperform SI in non-overlapping settings.
Overlapping (ICS) Performance: When used to initialize ICS, the VarSI-based groupings achieved significant measurement reductions relative to standard SI-ICS:
- With exact ground-state covariances: Average reductions of 9.2–10.1% (JW) and 7.1–13.1% (BK), with maximum reductions up to 70%.
- With CISD covariances: Average reductions of 11.1–15.3%, with maximum reductions up to 70.7%.
Strongly Correlated Systems: In tasks involving the Potential Energy Surface (PES) of N $_2$ and hydrogen chains, the VarSI-OR-ICS initialization reduced the total number of measurements required to reach 1 mEh accuracy by millions compared to SI-ICS. For the N $_2$ dissociation curve, this translated to approximately 1 hour less of QPU runtime for the VarSI-OR-ICS method.
Robustness: Across 418 test instances, the standard SI initialization was strictly better than the proposed VarSI initializations in only 5 cases (all using approximate CISD variances), demonstrating the consistency of the improvement.

Significance
The paper establishes that the initial non-overlapping grouping remains a "consequential design step" even when the final estimator utilizes overlapping fragments. By leveraging covariance dictionaries already necessary for overlapping methods, VarSI provides a low-overhead pathway to reduce measurement costs. The authors claim that these improved initializations allow the computationally cheaper ICS method to compete with more expensive frameworks like SPP. Furthermore, the results suggest that resource savings of up to 1 hour of QPU time are achievable in common quantum chemistry applications, highlighting the practical value of optimizing the "seed" of the measurement allocation process. The work also notes that the classical overhead of generating covariance dictionaries can be mitigated using machine learning techniques or pre-trained wavefunctions, though this extension is beyond the current scope.