Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.10339

Binary Optimization of Measurement Groupings for Quantum Energy Estimation

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

quant-phSubmitted Oct 7, 2026• Announced Oct 8, 2026• 0 citations
arXivHTMLPDF

Abstract

Repeated measurements can dominate the resources required for quantum energy estimation, making the choice of which Pauli observables to measure together a central optimization problem for variational quantum algorithms. We formulate fully commuting measurement grouping as a classical binary optimization problem based on clique selection and construct non-overlapping groups using mixed-integer linear programming (MILP). For a benchmark of molecular Hamiltonians, groupings optimized with approximate covariances reduce the non-overlapping measurement requirement $\varepsilon^2M$ by $51.8\%$ on average relative to sorted insertion (SI). Using the MILP groups to initialize iterative coefficient splitting (ICS), denoted MILP-ICS, yields an average $24.3\%$ reduction relative to ICS initialized from SI (SI-ICS). The optimized groups also transfer across nearby molecular geometries while preserving substantial measurement savings. We further introduce O-clique, which directly optimizes overlapping commuting supports through candidate-clique selection and coefficient profiles. Although O-clique provides only modest additional reductions beyond MILP-ICS, it reduces the measurement requirement by $27.3\%$ on average relative to SI-ICS with 100 iterations, despite using only five final coefficient refinement iterations, indicating improved support quality. Finally, we extend the comparison to Fermi--Hubbard, Kitaev--Heisenberg--$Γ$, and XYZ lattice Hamiltonians, where MILP-based groupings substantially outperform the corresponding SI-based strategies. Together, these results show that variance-informed optimization of measurement-group structure can substantially reduce sampling costs across molecular and lattice Hamiltonians, with optimized non-overlapping groups providing strong, transferable initializations and direct overlapping optimization offering further gains.

AI Summary

The paper asks how covariance-informed selection of commuting Pauli measurement groups affects energy-estimation sampling costs, both directly and as initialization for overlapping coefficient splitting. It optimizes the shot-allocation objective $\varepsilon^2M=(\sum_\alpha\sqrt{\operatorname{Var}(H_\alpha)})^2$, rather than group count. For non-overlapping groups, candidate commuting cliques receive precomputed standard-deviation costs, converting restricted partition selection into a mixed-integer linear program (MILP), supplemented by greedy refinement. The resulting partitions initialize iterative coefficient splitting (MILP-ICS). A second method, O-clique, selects overlapping supports using fixed coefficient profiles and continuous profile multipliers. Its linear surrogate $U$ satisfies $S\leq U$ and $\varepsilon^2M\leq U^2$ for the covariance data used; fixed-support ICS subsequently refines the coefficients. Across eight small molecular Hamiltonians, optimization with approximate CISD covariances, followed by evaluation with exact FCI covariances, reduces measurement requirements by 51.8% on average relative to sorted insertion (SI). MILP-ICS reduces costs by about 24% relative to SI-ICS. O-clique achieves a 27.3% average reduction relative to SI-ICS with 100 iterations, using five final refinement iterations, but adds generally less than 10% beyond MILP-ICS, with a maximum of 13%. Geometry-transfer tests retain savings, and three lattice benchmarks also favor MILP-based groupings over SI-based counterparts. Optimality certificates apply only within finite candidate pools, not globally. Classical search costs vary substantially, reported timings exclude covariance construction, and transferred groupings can degrade when new terms appear. The lattice tests use exact ground-state covariances rather than demonstrating approximate-covariance performance.

Little sign of AI-generated textIncrementalMissing comparison

Error found: The claimed 0.5% measurement reduction from adding LNS is unreconciled with the displayed MILP and MILP-LNS tables, which show an aggregate worsening before ICS and different improvement percentages after ICS.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
18 pages, 4 figures, 6 tables

Related papers

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

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

The measurement cost for estimating expectation values of Hamiltonians is a central bottleneck in variational quantum algorithms. Grouping strategies significantly reduce this cost, with overlapping techniques being the state of the art in the field. Overlapping grouping methods require i) a non-overlapping grouping of the Hamiltonian, typically obtained from the Sorted Insertion (SI) algorithm as initialization, and ii) the construction of covariance dictionaries from approximate wavefunctions to guide the optimization. It was recently shown that different initializations can potentially reduce measurement costs for overlapping methods. Motivated by these findings, we introduce variance-aware SI (VarSI), a family of covariance-informed non-overlapping Pauli grouping heuristics to reduce measurement counts. VarSI grouping leverages the covariance dictionaries, already required by overlapping methods, to construct better non-overlapping groups. We propose three variants: a global greedy grouping insertion rule, a variance-informed SI analog, and a local refinement step initialized from SI or our variance-informed variant. We showcase the use of groupings generated by our VarSI heuristic algorithms to initialize overlapping methods using the iterative coefficient-splitting (ICS) algorithm. Molecular benchmarks with 130 Hamiltonians demonstrate consistent, non-overlapping measurement improvements over SI of 38\% and enhanced downstream ICS results when initialized from VarSI groups. We find that the initializations considered here achieve up to 70\% measurement reductions for ICS, compared to the standard SI initialization with mean reductions of 9--15.3\% depending on qubit mappings and covariance dictionaries used. These results show that non-overlapping grouping remains a consequential design step even when the final estimator uses overlapping fragments.

quant-pharXiv:2607.02794•Jul 6, 2026•2 citations

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

Jeremiah Rowland, Rahul Sarkar, Nicolas PD Sawaya +2 more

Grouping-based measurement strategies are widely used to reduce measurement complexity in near-term quantum algorithms. While these schemes have typically produced disjoint groups, recently this has been relaxed in what is known as overlapped grouping or coefficient splitting where operators may appear in more than one compatible group. In recent work, it has been numerically shown that this strategy can reduce the variance of energy estimates on small benchmark problems, motivating both the application and further analysis of the method. Here we prove that overlapped grouping for energy estimation can lead to a maximal variance reduction that is linear in the number of Hamiltonian terms. We introduce a new algorithm which we call repacking to transform existing groups into overlapped groups, and we show this repacking procedure iteratively reduces variance under mild assumptions. We also perform numerical simulations with Hamiltonians up to $44$ qubits and $575 \cdot 10^{3}$ terms, assessing overlapped grouping at scale on problems of practical importance. Our numerics show that the variance reduction relative to state-of-the-art (disjoint) grouping increases linearly with the problem size, suggesting that overlapped grouping methods can be a powerful strategy for quantum energy estimation at the scale of Megaquop computers and beyond.

quant-pharXiv:2604.07156•Apr 9, 2026•3 citations

From optimization to construction: Expanding quantum measurement designs

Taotao Zhao, Qianjun Yao, Mengdi Sun +1 more

Estimating molecular energies on quantum computers requires repeated measurements of many Pauli terms, making sampling a major resource cost. Measurement design chooses which compatible terms are measured together and allocates a finite shot budget among bases to minimize the variance of an energy estimator. We introduce variance-guided measurement group construction (VGMC), which reduces variance beyond optimization on existing measurement bases by changing which Hamiltonian terms share measurement shots. After including every Hamiltonian term measurable in each existing basis, we jointly optimize estimator coefficients and shot allocations to separate inefficient use of these measurements from limitations of their measurement combinations. We compare a candidate's benefit with the cost of withdrawing shots from existing bases, and use the resulting scores to guide greedy construction of qubit-wise commuting groups followed by joint re-optimization. With exact covariances, VGMC outperformed the state-of-the-art measurement design methods across the molecular benchmarks where it introduced additional measurement bases, achieving variance reductions of 18.19%-23.38%. The gains persisted with approximate covariances, and simulations with finite shots indicated lower estimated shot requirements near chemical accuracy. These results show that optimizing how measurements are combined can also guide which terms are measured together, offering a route to reducing the sampling overhead of variational quantum simulation while retaining local measurements on current and near-term devices.

arXiv:2611.14986•Nov 11, 2026•0 citations

Measurement optimization in the variational quantum eigensolver using a minimum clique cover

Vladyslav Verteletskyi, Tzu-Ching Yen, Artur F. Izmaylov

Solving the electronic structure problem using the Variational Quantum Eigensolver (VQE) technique involves the measurement of the Hamiltonian expectation value. The current hardware can perform only projective single-qubit measurements, and thus, the Hamiltonian expectation value is obtained by measuring parts of the Hamiltonian rather than the full Hamiltonian. This restriction makes the measurement process inefficient because the number of terms in the Hamiltonian grows as O(N4) with the size of the system, N. To optimize the VQE measurement, one can try to group as many Hamiltonian terms as possible for their simultaneous measurement. Single-qubit measurements allow one to group only the terms commuting within the corresponding single-qubit subspaces or qubit-wise commuting. We found that the qubit-wise commutativity between the Hamiltonian terms can be expressed as a graph and the problem of the optimal grouping is equivalent to finding a minimum clique cover (MCC) for the Hamiltonian graph. The MCC problem is NP-hard, but there exist several polynomial heuristic algorithms to solve it approximately. Several of these heuristics were tested in this work for a set of molecular electronic Hamiltonians. On average, grouping qubit-wise commuting terms reduced the number of operators to measure three times less compared to the total number of terms in the considered Hamiltonians.

arXiv:1907.03358•The Journal of Chemical Physics•Mar 27, 2020•317 citations

Variance reduction methods in the estimation of Pauli sums

Søren Fuglede Jørgensen, Rafael Emilio Barfknecht, Patrick Ettenhuber +1 more

Accurately estimating expectation values of quantum observables with as few measurements as possible is crucial to many quantum computing applications. We introduce a framework that covers many of existing measurement strategies and introduce heuristics that can be used to enhance randomized schemes, including those based on Pauli grouping with inverse probability weighting and variants of the classical shadow algorithm. We show how to maximize information gain from such schemes, while carefully optimizing the distribution of possible measurements, and show that simple grouping algorithms can get close to, and in some cases exceed, state-of-the-art accuracy for unbiased estimation of expectation values on a standard quantum chemistry benchmark. We show how these randomized methods may be compared to more recent measurement schemes, such as shadow grouping, derandomized shadow, and overlapped grouping measurement, we show how the same strategies can be used to augment these schemes, and we demonstrate that we can reduce measurement costs by up to a factor of two by allowing Clifford measurement circuits for otherwise Clifford-less methods.

quant-pharXiv:2603.20029•Mar 23, 2026•0 citations

Pauli-string grouping for VQE measurement reduction on a sparse-connectivity quantum annealer

Raul Martinez, Miguel Sanchez-Beato, Mario Calonge

The Variational Quantum Eigensolver (VQE) requires a large number of measurements to evaluate molecular Hamiltonians. Expressing a molecular Hamiltonian as a linear combination of Pauli strings creates a measurement bottleneck: non-commuting Pauli strings cannot be measured simultaneously. Consequently, mutually commuting Pauli strings must be grouped and measured together to minimise the number of quantum-state preparations. This task maps to the minimum clique cover problem on a commutativity graph, an NP-hard problem typically addressed using classical heuristics. Although an Ising-model formulation has recently been explored on fully connected CMOS Ising machines and demonstrated on physical quantum annealers only at small scale, the embedding cost that governs its behaviour on hardware with sparse connectivity, where each logical variable must be represented by a chain of physical qubits, has not been characterised. In this work, we formulate the Pauli-grouping problem as a standard QUBO colouring model and study its scalability on a D-Wave quantum annealer. Across a series of molecular systems and for both qubit-wise and full commutativity, we quantify the growth in the number of logical variables and the QUBO interaction density, characterise the physical-qubit and chain-length overhead required for embedding on the Zephyr topology, and compare the annealer's time-to-solution and solution quality with those of heuristic classical baselines. This analysis identifies the threshold of molecular complexity beyond which hardware connectivity prevents viable embedding, and shows that a second, practical limit is reached earlier. The threshold therefore measures how far current annealers are from the regime in which pre-optimising a VQE measurement scheme on hardware would be worth considering.

quant-pharXiv:2609.20861•Sep 11, 2026•0 citations
Repeated measurements can dominate the resources required for quantum energy estimation, making the choice of which Pauli observables to measure together a central optimization problem for variational quantum algorithms. We formulate fully commuting measurement grouping as a classical binary optimization problem based on clique selection and construct non-overlapping groups using mixed-integer linear programming (MILP). For a benchmark of molecular Hamiltonians, groupings optimized with approximate covariances reduce the non-overlapping measurement requirement ε2M\varepsilon^2Mε2M by 51.8%51.8\%51.8% on average relative to sorted insertion (SI). Using the MILP groups to initialize iterative coefficient splitting (ICS), denoted MILP-ICS, yields an average 24.3%24.3\%24.3% reduction relative to ICS initialized from SI (SI-ICS). The optimized groups also transfer across nearby molecular geometries while preserving substantial measurement savings. We further introduce O-clique, which directly optimizes overlapping commuting supports through candidate-clique selection and coefficient profiles. Although O-clique provides only modest additional reductions beyond MILP-ICS, it reduces the measurement requirement by 27.3%27.3\%27.3% on average relative to SI-ICS with 100 iterations, despite using only five final coefficient refinement iterations, indicating improved support quality. Finally, we extend the comparison to Fermi--Hubbard, Kitaev--Heisenberg--ΓΓΓ, and XYZ lattice Hamiltonians, where MILP-based groupings substantially outperform the corresponding SI-based strategies. Together, these results show that variance-informed optimization of measurement-group structure can substantially reduce sampling costs across molecular and lattice Hamiltonians, with optimized non-overlapping groups providing strong, transferable initializations and direct overlapping optimization offering further gains.
The paper asks how covariance-informed selection of commuting Pauli measurement groups affects energy-estimation sampling costs, both directly and as initialization for overlapping coefficient splitting. It optimizes the shot-allocation objective ε2M=(∑αVar⁡(Hα))2\varepsilon^2M=(\sum_\alpha\sqrt{\operatorname{Var}(H_\alpha)})^2ε2M=(∑α​Var(Hα​)​)2, rather than group count.
For non-overlapping groups, candidate commuting cliques receive precomputed standard-deviation costs, converting restricted partition selection into a mixed-integer linear program (MILP), supplemented by greedy refinement. The resulting partitions initialize iterative coefficient splitting (MILP-ICS). A second method, O-clique, selects overlapping supports using fixed coefficient profiles and continuous profile multipliers. Its linear surrogate UUU satisfies S≤US\leq US≤U and ε2M≤U2\varepsilon^2M\leq U^2ε2M≤U2 for the covariance data used; fixed-support ICS subsequently refines the coefficients.
Across eight small molecular Hamiltonians, optimization with approximate CISD covariances, followed by evaluation with exact FCI covariances, reduces measurement requirements by 51.8% on average relative to sorted insertion (SI). MILP-ICS reduces costs by about 24% relative to SI-ICS. O-clique achieves a 27.3% average reduction relative to SI-ICS with 100 iterations, using five final refinement iterations, but adds generally less than 10% beyond MILP-ICS, with a maximum of 13%. Geometry-transfer tests retain savings, and three lattice benchmarks also favor MILP-based groupings over SI-based counterparts.
Optimality certificates apply only within finite candidate pools, not globally. Classical search costs vary substantially, reported timings exclude covariance construction, and transferred groupings can degrade when new terms appear. The lattice tests use exact ground-state covariances rather than demonstrating approximate-covariance performance.
The measurement cost for estimating expectation values of Hamiltonians is a central bottleneck in variational quantum algorithms. Grouping strategies significantly reduce this cost, with overlapping techniques being the state of the art in the field. Overlapping grouping methods require i) a non-overlapping grouping of the Hamiltonian, typically obtained from the Sorted Insertion (SI) algorithm as initialization, and ii) the construction of covariance dictionaries from approximate wavefunctions to guide the optimization. It was recently shown that different initializations can potentially reduce measurement costs for overlapping methods. Motivated by these findings, we introduce variance-aware SI (VarSI), a family of covariance-informed non-overlapping Pauli grouping heuristics to reduce measurement counts. VarSI grouping leverages the covariance dictionaries, already required by overlapping methods, to construct better non-overlapping groups. We propose three variants: a global greedy grouping insertion rule, a variance-informed SI analog, and a local refinement step initialized from SI or our variance-informed variant. We showcase the use of groupings generated by our VarSI heuristic algorithms to initialize overlapping methods using the iterative coefficient-splitting (ICS) algorithm. Molecular benchmarks with 130 Hamiltonians demonstrate consistent, non-overlapping measurement improvements over SI of 38\% and enhanced downstream ICS results when initialized from VarSI groups. We find that the initializations considered here achieve up to 70\% measurement reductions for ICS, compared to the standard SI initialization with mean reductions of 9--15.3\% depending on qubit mappings and covariance dictionaries used. These results show that non-overlapping grouping remains a consequential design step even when the final estimator uses overlapping fragments.
Grouping-based measurement strategies are widely used to reduce measurement complexity in near-term quantum algorithms. While these schemes have typically produced disjoint groups, recently this has been relaxed in what is known as overlapped grouping or coefficient splitting where operators may appear in more than one compatible group. In recent work, it has been numerically shown that this strategy can reduce the variance of energy estimates on small benchmark problems, motivating both the application and further analysis of the method. Here we prove that overlapped grouping for energy estimation can lead to a maximal variance reduction that is linear in the number of Hamiltonian terms. We introduce a new algorithm which we call repacking to transform existing groups into overlapped groups, and we show this repacking procedure iteratively reduces variance under mild assumptions. We also perform numerical simulations with Hamiltonians up to 444444 qubits and 575⋅103575 \cdot 10^{3}575⋅103 terms, assessing overlapped grouping at scale on problems of practical importance. Our numerics show that the variance reduction relative to state-of-the-art (disjoint) grouping increases linearly with the problem size, suggesting that overlapped grouping methods can be a powerful strategy for quantum energy estimation at the scale of Megaquop computers and beyond.
Estimating molecular energies on quantum computers requires repeated measurements of many Pauli terms, making sampling a major resource cost. Measurement design chooses which compatible terms are measured together and allocates a finite shot budget among bases to minimize the variance of an energy estimator. We introduce variance-guided measurement group construction (VGMC), which reduces variance beyond optimization on existing measurement bases by changing which Hamiltonian terms share measurement shots. After including every Hamiltonian term measurable in each existing basis, we jointly optimize estimator coefficients and shot allocations to separate inefficient use of these measurements from limitations of their measurement combinations. We compare a candidate's benefit with the cost of withdrawing shots from existing bases, and use the resulting scores to guide greedy construction of qubit-wise commuting groups followed by joint re-optimization. With exact covariances, VGMC outperformed the state-of-the-art measurement design methods across the molecular benchmarks where it introduced additional measurement bases, achieving variance reductions of 18.19%-23.38%. The gains persisted with approximate covariances, and simulations with finite shots indicated lower estimated shot requirements near chemical accuracy. These results show that optimizing how measurements are combined can also guide which terms are measured together, offering a route to reducing the sampling overhead of variational quantum simulation while retaining local measurements on current and near-term devices.
Solving the electronic structure problem using the Variational Quantum Eigensolver (VQE) technique involves the measurement of the Hamiltonian expectation value. The current hardware can perform only projective single-qubit measurements, and thus, the Hamiltonian expectation value is obtained by measuring parts of the Hamiltonian rather than the full Hamiltonian. This restriction makes the measurement process inefficient because the number of terms in the Hamiltonian grows as O(N4) with the size of the system, N. To optimize the VQE measurement, one can try to group as many Hamiltonian terms as possible for their simultaneous measurement. Single-qubit measurements allow one to group only the terms commuting within the corresponding single-qubit subspaces or qubit-wise commuting. We found that the qubit-wise commutativity between the Hamiltonian terms can be expressed as a graph and the problem of the optimal grouping is equivalent to finding a minimum clique cover (MCC) for the Hamiltonian graph. The MCC problem is NP-hard, but there exist several polynomial heuristic algorithms to solve it approximately. Several of these heuristics were tested in this work for a set of molecular electronic Hamiltonians. On average, grouping qubit-wise commuting terms reduced the number of operators to measure three times less compared to the total number of terms in the considered Hamiltonians.
Accurately estimating expectation values of quantum observables with as few measurements as possible is crucial to many quantum computing applications. We introduce a framework that covers many of existing measurement strategies and introduce heuristics that can be used to enhance randomized schemes, including those based on Pauli grouping with inverse probability weighting and variants of the classical shadow algorithm. We show how to maximize information gain from such schemes, while carefully optimizing the distribution of possible measurements, and show that simple grouping algorithms can get close to, and in some cases exceed, state-of-the-art accuracy for unbiased estimation of expectation values on a standard quantum chemistry benchmark. We show how these randomized methods may be compared to more recent measurement schemes, such as shadow grouping, derandomized shadow, and overlapped grouping measurement, we show how the same strategies can be used to augment these schemes, and we demonstrate that we can reduce measurement costs by up to a factor of two by allowing Clifford measurement circuits for otherwise Clifford-less methods.
The Variational Quantum Eigensolver (VQE) requires a large number of measurements to evaluate molecular Hamiltonians. Expressing a molecular Hamiltonian as a linear combination of Pauli strings creates a measurement bottleneck: non-commuting Pauli strings cannot be measured simultaneously. Consequently, mutually commuting Pauli strings must be grouped and measured together to minimise the number of quantum-state preparations. This task maps to the minimum clique cover problem on a commutativity graph, an NP-hard problem typically addressed using classical heuristics. Although an Ising-model formulation has recently been explored on fully connected CMOS Ising machines and demonstrated on physical quantum annealers only at small scale, the embedding cost that governs its behaviour on hardware with sparse connectivity, where each logical variable must be represented by a chain of physical qubits, has not been characterised. In this work, we formulate the Pauli-grouping problem as a standard QUBO colouring model and study its scalability on a D-Wave quantum annealer. Across a series of molecular systems and for both qubit-wise and full commutativity, we quantify the growth in the number of logical variables and the QUBO interaction density, characterise the physical-qubit and chain-length overhead required for embedding on the Zephyr topology, and compare the annealer's time-to-solution and solution quality with those of heuristic classical baselines. This analysis identifies the threshold of molecular complexity beyond which hardware connectivity prevents viable embedding, and shows that a second, practical limit is reached earlier. The threshold therefore measures how far current annealers are from the regime in which pre-optimising a VQE measurement scheme on hardware would be worth considering.