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

• URL: http://arxiv.org/abs/2604.07156v1
• Date: Wed, 08 Apr 2026 14:47:26 GMT
• Title: Overlapped groupings for quantum energy estimation: Maximal variance reduction and deterministic algorithms for reducing variance
• Abstract summary: Grouping-based measurement strategies are widely used to reduce measurement complexity in near-term quantum algorithms.<n>In recent work, it has been numerically shown that this strategy can reduce the variance of energy estimates on small benchmark problems.<n>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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Efficient Learning and Symmetry Discovery under Exact Invariances [62.27019402162741]
  Learning with group invariances is central to many scientific and geometric learning problems.<n>It has been unclear whether one can efficiently compute a regression function that is exactly in subgroup to a given group action.<n>We present the first-time algorithm for learning with exact group invariants that applies uniformly to finite and infinite groups.
  arXiv  Detail & Related papers  (2026-09-07T04:35:19Z)
• Reducing quantum measurements in qubit-based overlapping grouping methods for quantum energy estimation through better initializations [0.8594140167290097]
  Grouping strategies significantly reduce the cost of estimating expectation values of Hamiltonians.<n>Overlapping methods require i) a non-overlapping grouping of the Hamiltonian, typically obtained from the Sorted Insertion (SI) algorithm as an initial.<n>VarSI grouping leverages the covariance-informed dictionaries, already required by overlapping methods, to construct better non-overlapping groups.
  arXiv  Detail & Related papers  (2026-07-02T22:12:00Z)
• Sample Complexity Bounds for Estimating Probability Divergences under Invariances [31.946304450935628]
  Group-invariant probability distributions appear in many data-generative models in machine learning. In this work, we study how the inherent invariances, with respect to any smooth action of a Lie group on a manifold, improve sample complexity. Results are completely new for groups of positive dimension and extend recent bounds for finite group actions.
  arXiv  Detail & Related papers  (2023-11-06T04:45:21Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks. The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions. We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
  arXiv  Detail & Related papers  (2023-09-30T15:57:14Z)
• Achieving Sample and Computational Efficient Reinforcement Learning by Action Space Reduction via Grouping [7.691755449724638]
  Reinforcement learning often needs to deal with the exponential growth of states and actions in high-dimensional spaces. We learn the inherent structure of action-wise similar MDP to appropriately balance the performance degradation versus sample/computational complexity.
  arXiv  Detail & Related papers  (2023-06-22T15:40:10Z)
• Guaranteed efficient energy estimation of quantum many-body Hamiltonians using ShadowGrouping [49.36226952764697]
  Estimation of the energy of quantum many-body systems is a paradigmatic task in various research fields.<n>We aim to find the optimal strategy with single-qubit measurements that yields the highest provable accuracy given a total measurement budget.<n>We develop a practical, efficient estimation strategy, which we call ShadowGrouping.
  arXiv  Detail & Related papers  (2023-01-09T14:41:07Z)
• Bregman divergence based em algorithm and its application to classical and quantum rate distortion theory [61.12008553173672]
  We address the minimization problem of the Bregman divergence between an exponential subfamily and a mixture subfamily in a Bregman divergence system. We apply this algorithm to rate distortion and its variants including the quantum setting.
  arXiv  Detail & Related papers  (2022-01-07T13:33:28Z)
• Deterministic improvements of quantum measurements with grouping of compatible operators, non-local transformations, and covariance estimates [0.0]
  We consider several partitioning schemes based on grouping of commuting multi-qubit Pauli products. We develop two new measurement schemes that achieve a severalfold reduction in the number of measurements.
  arXiv  Detail & Related papers  (2022-01-05T06:20:18Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  Clustering is a fundamental primitive in unsupervised learning. Recent work has established lower bounds against the class of low-degree methods. We show that, perhaps surprisingly, this particular clustering model textitdoes not exhibit a statistical-to-computational gap.
  arXiv  Detail & Related papers  (2021-12-07T18:50:17Z)
• Two-level Group Convolution [2.2344764434954256]
  Group convolution has been widely used in order to reduce the computation time of convolution. We propose a new convolution methodology called two-level'' group convolution that is robust with respect to the increase of the number of groups.
  arXiv  Detail & Related papers  (2021-10-11T07:54:49Z)
• Quantum algorithms for group convolution, cross-correlation, and equivariant transformations [9.134244356393665]
  Group convolutions and cross-correlations are commonly used in mathematics to analyze or take advantage of symmetries inherent in a given problem setting. Here, we provide efficient quantum algorithms for performing linear group convolutions and cross-correlations on data stored as quantum states.
  arXiv  Detail & Related papers  (2021-09-23T12:21:31Z)
• Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
  Joint network topology inference represents a canonical problem of learning multiple graph Laplacian matrices from heterogeneous graph signals. We propose a general graph estimator based on a novel structured fusion regularization. We show that the proposed graph estimator enjoys both high computational efficiency and rigorous theoretical guarantee.
  arXiv  Detail & Related papers  (2021-03-05T04:42:32Z)
• The role of boundary conditions in quantum computations of scattering observables [58.720142291102135]
  Quantum computing may offer the opportunity to simulate strongly-interacting field theories, such as quantum chromodynamics, with physical time evolution. As with present-day calculations, quantum computation strategies still require the restriction to a finite system size. We quantify the volume effects for various $1+1$D Minkowski-signature quantities and show that these can be a significant source of systematic uncertainty.
  arXiv  Detail & Related papers  (2020-07-01T17:43:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.