Overlapped groupings for quantum energy estimation: Maximal variance reduction and deterministic algorithms for reducing variance

1. Problem Statement

In near-term quantum algorithms, particularly Variational Quantum Eigensolvers (VQE), measurement complexity is a dominant bottleneck. Estimating the energy of a Hamiltonian $H = \sum c_i P_i$ requires measuring many Pauli terms. To reduce the number of required measurement shots, standard strategies group mutually commuting Pauli operators into disjoint sets (groups) that can be measured simultaneously in a shared basis.

However, standard disjoint grouping forces each Pauli term to appear in exactly one group. The paper addresses the potential of overlapped grouping (or coefficient splitting), where a single Pauli operator may appear in multiple compatible groups. While previous works suggested this could reduce variance, the theoretical limits of this reduction and the existence of deterministic algorithms to achieve it were open questions. The authors aim to:

1. Determine the maximal variance reduction possible via overlapped grouping compared to optimal disjoint grouping.
2. Develop deterministic algorithms to transform existing disjoint groupings into overlapped ones that strictly reduce variance.
3. Validate these methods on large-scale practical problems (up to 44 qubits and $5.75 \times 10^5$ terms), far exceeding previous numerical benchmarks.

2. Methodology

A. Overlapped Grouping and Estimators

The authors define an overlapped grouping as a collection of commuting sets whose union covers all Hamiltonian terms, allowing overlaps.

• Estimator Construction: For a Pauli operator $P_i$ appearing in multiple groups, the expectation value is estimated using a shot-weighted average of the empirical estimates from each group.
• Variance Model: The analysis assumes a state-independent variance model with zero covariance between distinct Pauli operators measured simultaneously. This is a standard heuristic assumption that simplifies the allocation problem and is shown to be valid for many electronic structure problems.

B. Repacking Algorithms

The core methodological contribution is the introduction of Repacking, a procedure to transform a disjoint grouping $\mathcal{G}$ into an overlapped grouping $\mathcal{R}$ without creating new groups (i.e., the number of measurement circuits remains constant). Two specific algorithms are proposed:

1. Post-hoc Repacking:

   • Mechanism: Takes an existing disjoint grouping and its associated measurement bases (diagonalizing unitaries). It checks if any other Pauli terms in the Hamiltonian are also diagonal in these existing bases. If so, it adds them to the group.
   • Advantage: Requires no new quantum circuits. It extracts additional information from data already collected, effectively providing a "free lunch" in terms of variance reduction.
   • Complexity: $O(m|V|)$, where $m$ is the number of groups and $|V|$ is the number of terms.

2. Ad-hoc Repacking:

   • Mechanism: A greedy algorithm that modifies the grouping before circuit synthesis. It iteratively inserts compatible Pauli operators into existing groups based on a scoring function $C(P_i) = c_i^2 / \mu_i$, where $c_i$ is the coefficient and $\mu_i$ is the current number of groups the term appears in.
   • Advantage: Allows for changing the measurement basis to maximize the overlap of compatible terms, potentially yielding greater variance reduction than post-hoc methods.
   • Constraint: It never deletes terms or creates new groups, ensuring the number of circuits remains fixed.

C. Theoretical Framework

The authors prove that repacking creates a partial order on groupings. If $\mathcal{R}$ is a repacking of $\mathcal{G}$, then $\mathcal{G} \subseteq \mathcal{R}$ (in terms of operator inclusion). Under the zero-covariance assumption, this inclusion guarantees that the variance of the energy estimator for $\mathcal{R}$ is less than or equal to that of $\mathcal{G}$.

3. Key Contributions and Theoretical Results

Theorem 1: Maximal Variance Reduction

The authors construct a family of Hamiltonians (based on interconnected complete graphs) to prove that the variance reduction of overlapped grouping relative to the best disjoint grouping (found via the "sorted insertion" heuristic) can be linear in the number of groups ($m$).

• Result: $\text{Var}_{\text{disjoint}} / \text{Var}_{\text{overlapped}} = \Theta(m)$.
• Significance: This establishes the theoretical upper bound of the benefit, showing that overlapped grouping is not just a minor optimization but can scale linearly with problem complexity.

Theorem 2: Deterministic Variance Reduction

The paper proves that repacking always reduces variance (or keeps it equal) under the assumption of zero covariance and shot-weighted averaging.

• Result: If at least one refinement step adds a Pauli operator with non-zero variance, the variance strictly decreases: $\text{Var}(\mathcal{R}) < \text{Var}(\mathcal{G})$.
• Significance: This provides a deterministic guarantee that the proposed algorithms will not degrade performance, unlike some heuristic methods that might fail on pathological instances.

4. Numerical Results

The authors performed extensive simulations on:

1. Molecular Hamiltonians: Including $H_2$, $LiH$, $BeH_2$, $NH_3$, $CH_4$, $H_6$, $H_2O$, and a large metaphosphate (OWP) model (44 qubits, $575 \times 10^3$ terms).
2. Random Hamiltonians: Scaled up to 12 qubits to study scaling behavior.

Key Findings:

• Variance Reduction: Overlapped grouping consistently reduced variance compared to standard sorted insertion.
• Magnitude: For the largest molecular benchmark (OWP), variance was reduced by a factor of $\sim 2.35\times$.
• Scaling: The variance reduction factor increases linearly (or super-linearly for random models) with the problem size (number of qubits/groups).
• Post-hoc vs. Ad-hoc: While ad-hoc repacking (changing bases) generally yielded higher reductions, post-hoc repacking (reusing existing data) still provided strict variance reduction, validating its utility for "free" improvement.
• Covariance Assumption: Numerical checks on a Fermi-Hubbard model confirmed that for typical electronic structure problems, the diagonal variance term dominates the covariance term, justifying the zero-covariance assumption used in the theory.

5. Significance and Impact

• Scalability for Megaquop Computers: The results suggest that overlapped grouping is a critical strategy for future quantum computers (Megaquop scale, $10^2$–$10^3$ qubits). As problem sizes grow, the linear variance reduction implies that the total measurement cost (shots) can be significantly lowered, making large-scale energy estimation feasible.
• Deterministic Improvement: Unlike many quantum algorithm optimizations that rely on probabilistic gains or specific state properties, repacking offers a deterministic path to lower variance for any Hamiltonian, provided the zero-covariance assumption holds (which is empirically true for chemistry).
• Retroactive Optimization: The post-hoc repacking method is particularly significant for near-term experiments. It allows researchers to re-analyze data collected from disjoint grouping experiments to extract more information without running new circuits, effectively increasing the utility of existing experimental resources.
• Theoretical Closure: The paper resolves open questions regarding the theoretical limits of overlapped grouping, proving that the potential gain is not bounded by a constant but scales with the problem size.

In summary, this work provides both the theoretical proof and practical algorithms to demonstrate that overlapped grouping via repacking is a powerful, scalable, and deterministic method for reducing measurement complexity in quantum energy estimation.