PaperlayerView exact revision on arXiv

Source-linked AI summary

Overlapped grouping measurement: A unified framework for measuring quantum states

Bujiao Wu, Jinzhao Sun, Qi Huang, Xiao Yuan

arXiv:2105.13091v2quant-ph

TL;DR

Estimating Hamiltonian expectations can require many measurements, while existing cost-reduction strategies exploit different features and lack a unified optimization framework. This paper unifies those strategies and proposes overlapped grouping measurement (OGM), which combines their advantages. The authors report significant improvements over existing methods in molecular-Hamiltonian benchmarks.

  • Problem

    Hamiltonian estimation can require many measurements, while existing schemes exploit distinct features and how to systematically optimize across them remains an open challenge.

    Source: §1 · pp. 1–2

  • Method

    The authors unify advanced measurement schemes in a framework and propose OGM, which combines importance sampling, observable compatibility, and classical-shadow features through overlapped groups.

    Source: §1 · p. 2, §3 · p. 6

  • Results

    The authors report significant improvements over existing advanced measurement methods, including higher accuracy than alternatives when measurement counts are limited.

    Source: §5 · p. 11, §6 · p. 13

  • Takeaways & Limitations

    The framework provides a common account of advanced measurement strategies, and OGM is presented as applicable to current and near-future quantum experiments.

    Source: §1 · p. 2

    Extending OGM to generalized measurements, including entangled measurements, remains a future direction.

    Source: §6 · p. 14

Abstract

from arXiv · show

Quantum algorithms designed for realistic quantum many-body systems, such as chemistry and materials, usually require a large number of measurements of the Hamiltonian. Exploiting different ideas, such as {importance sampling,} observable compatibility, or classical shadows of quantum states, different advanced measurement schemes have been proposed to greatly reduce the large measurement cost. Yet, the underline cost reduction mechanisms seem distinct from each other, and how to systematically find the optimal scheme remains a critical challenge. Here, we address this challenge by proposing a unified framework of quantum measurements, incorporating advanced measurement methods as special cases. Our framework allows us to introduce a general scheme~ -- ~overlapped grouping measurement, which simultaneously exploits the advantages of most existing methods. An intuitive understanding of the scheme is to partition the measurements into overlapped groups with each one consisting of compatible measurements. We provide explicit grouping strategies and numerically verify its performance for different molecular Hamiltonians with up to 16 qubits. Our numerical result shows significant improvements over existing schemes. Our work paves the way for efficient quantum measurement and fast quantum processing with current and near-term quantum devices.

1 Introduction

Hamiltonian estimation can require many measurements, and the cost grows alongside the number of terms and error-mitigation overhead. The paper unifies existing measurement strategies and introduces OGM, reporting prominent improvements over prior methods.

1 Introduction

  • Hamiltonians can contain many local terms, and error-mitigation techniques add sample overhead that grows with problem size.An electronic Hamiltonian with Coulomb interaction generally has O(M^4) terms for M fermionic modes.Source: §1 · pp. 1–2
  • Existing approaches reduce measurement cost through importance sampling, compatibility-based grouping, or classical shadows, but their relationships and systematic joint optimization remain open questions.The original uniform classical-shadow scheme scales exponentially with the number of qubits on which an observable acts; LBCS and derandomized classical shadows were proposed to reduce the cost.Source: §1 · p. 2
  • The paper introduces a unified measurement framework and OGM, then reports prominent improvements over advanced methods in molecular-Hamiltonian benchmarks.The proposed method is described as immediately applicable to current and near-future quantum experiments.Source: §1 · p. 2

2 A unified framework

The framework measures an observable by sampling Pauli bases and post-processing outcomes with an estimator designed to be unbiased. It expresses established strategies within a common scheme and motivates OGM by the limitations of locally selected measurements.

2 A unified framework

  • A measurement scheme selects Pauli bases and their probabilities so each target observable is measurable; sampled outcomes are post-processed into an unbiased expectation estimator.The framework represents observables as local Pauli strings and defines compatibility through whether a basis can measure an observable.Source: §2 · p. 3
  • Importance sampling measures each observable independently, while grouping partitions observables into disjoint compatible sets and can allocate samples according to each set's total weight.Finding the exact minimum number of groups is NP-hard; largest degree first is one heuristic for approximate grouping.Source: §2 · pp. 3–5
  • For the illustrated three-qubit instance, the reported variances are 0.90 for l1-sampling, 0.56 for LDF-grouping, 0.74 for LBCS, and 0.50 for OGM.The accompanying schematic depicts choosing Pauli bases according to a distribution, measuring the state, and post-processing outcomes to estimate the observable.Source: §2 · p. 4, Figure 1 · p. 4
  • Classical shadows fit the framework as random Pauli-basis measurements, including uniform sampling and LBCS's product distribution; derandomized shadows can also be represented through a sampling distribution.The framework presents LBCS as another view of observable compatibility.Source: §2 · p. 5
  • Because LBCS selects measurements locally, it can spend samples on redundant observables absent from the objective, potentially making it costly as system size increases.The passage gives X1Z2X3 as an example of a redundant observable in the illustrated instance.Source: §2 · p. 6

3 Overlapped grouping measurement

Overlapped grouping measurement (OGM) combines importance sampling, observable compatibility, and classical-shadow ideas by allowing compatible measurement groups to overlap. The framework includes existing schemes as special cases and is described as strictly better than classical shadows.

3.1 Overlapped grouping

  • OGM covers all objective observables with potentially overlapping sets, each paired with a basis compatible with its members.Its estimator uses probability-corrected measurement outcomes to give an unbiased estimate of tr(ρO).Source: §3.1 · p. 6
  • The OGM variance determines sample complexity: T must be at least Var(ˆvG)/δε^2 to meet the stated error and failure-probability bounds.The bound targets estimation within ε of tr(ρO) with failure probability δ.Source: §3.1 · p. 7

3.2 Illustration and comparison with other measurement schemes

  • OGM encompasses importance sampling, LDF grouping, classical shadows, and a probabilistic version of derandomized classical shadows as restricted cases.Its estimator can use all compatibility properties within overlapped sets.Source: §3.2 · p. 7
  • OGM is strictly better than classical shadows and avoids the redundant observables measured by local-shadow methods.Classical shadows are recovered when OGM uses local product measurement probabilities.Source: §3.2 · p. 7
  • Finding optimal overlapped groups is NP-hard, so the paper develops a greedy approximate grouping strategy and optimizes the measurement probabilities.The probability search seeks to minimize estimator variance.Source: §3.2 · pp. 7–8

4 Explicit grouping strategies

The explicit strategy builds overlapped groups by prioritizing observables with larger weights, then optimizes measurement probabilities and partially derandomizes sampling for a fixed measurement budget.

4 Explicit grouping strategies

  • The grouping strategy sorts observables by absolute weight, then adds compatible observables to sets while ensuring all objective observables are covered.The ordering affects the resulting set structure and number of sets.Source: §4 · p. 8

4.1 Optimization process

  • Because the true variance depends on the potentially unknown state, the strategy optimizes a state-independent diagonal approximation that is fast to evaluate and includes dominant variance contributions.The cost is nonconvex, so the method searches for a local minimum.Source: §4 · pp. 8–9
  • The optimization prunes low-probability groups and adds a T-scaled penalty for omitted observables to account for their initial error.The revised cost function is also nonconvex and can be minimized locally.Source: §4.1 · p. 9

4.2 Sampling strategy

  • For a fixed measurement budget, partially derandomized sampling assigns each basis floor(TKj) measurements and probabilistically adds one more.The sample count may differ slightly from T; the numerical experiments add measurements when the selected list remains below T.Source: §4.2 · pp. 9–10

5 Numerical tests

Numerical tests compare OGM with LDF-grouping, LBCS, and derandomized classical shadows for molecular Hamiltonians and random-state expectations. The reported results show improved estimation accuracy at limited measurements, advantages at large sample counts, and faster convergence in experiments.

5 Numerical tests

  • The simulations cover molecular Hamiltonians from 4 to 16 qubits; the authors add a disturbance term to the cost function to address local-minimum trapping.They omit importance sampling from the comparison because its performance is worse than the other schemes.Source: §5 · p. 10
  • OGM achieves much higher accuracy than LDF-grouping, LBCS, and derandomized CS for molecular-energy estimates with limited measurements.The comparison uses 1,000 samples and initializes OGM probabilities directly from Algorithm 1.Source: Table 1 · p. 11, §5 · p. 11
  • At large T, OGM error scales linearly to 1/T and has clear advantages over existing algorithms for LiH and BeH2 under JW encoding.Figure 2 compares errors across measurement counts for the two molecules.Source: §5 · p. 11, Figure 2 · p. 12
  • The tests also compare estimation errors for H2 expectations across 10 random 8-qubit states at 1,000 and 10,000 samples.The authors use these comparisons to illustrate that OGM's advantage is independent of the quantum input state.Source: §5 · p. 12, Figure 3 · p. 12
  • Experimental results show faster OGM convergence with a few hundred measurements, which the authors describe as practically useful for current-generation quantum devices.Source: §5 · p. 12

6 Discussion and outlook

The paper presents OGM as a unified measurement framework and reports numerical advantages over existing advanced methods. It identifies broader measurement settings and improved grouping strategies as future directions.

6 Discussion and outlook

  • OGM integrates features of existing advanced measurement strategies, and numerical results suggest significant improvements over those methods.The authors identify variational algorithms and quantum many-body tasks involving energy estimation as possible applications.Source: §6 · p. 13
  • The authors expect OGM’s advantages to grow with system size and note its applicability to adaptive variational quantum simulation.They connect efficient measurement to reducing measurement cost and speeding quantum computation.Source: §6 · p. 13
  • Figure 4 concerns OGM estimation error for H2 with eight qubits under a randomly generated input state.The passage gives the figure’s scope, but no numerical outcome.Source: Figure 4 · p. 13
  • The current analysis assumes local Pauli measurements; arbitrary local or entangled measurements are proposed as future extensions.The authors also identify more advanced classical algorithms and neural-network sampling as possible improvements or extensions.Source: §6 · pp. 13–14

A Sample complexity

This section analyzes sample complexity for l1-sampling, grouping, and classical-shadow algorithms, and relates estimator variance to measurement cost.

A Sample complexity

  • The section theoretically analyzes upper bounds on copy counts for l1-sampling, grouping, and classical-shadow algorithms.The supplied passages do not provide the bounds’ complete formulas.Source: A Sample complexity · p. 20
  • Chebyshev’s inequality is used to relate estimator variance to the sample count needed for an error and success-probability guarantee.The passage states that the sample count scales with variance and the error and failure-probability parameters, but its formula is incomplete.Source: A Sample complexity · p. 21
  • The section gives variance analyses for l1-sampling, grouping, and classical shadows, then relates derandomization variance to OGM.The supplied passages do not preserve the full variance expressions.Source: A Sample complexity · p. 21

B LDF Grouping method

The appendices describe a graph-based LDF grouping heuristic, an alternative greedy overlapped-grouping strategy, and variance analyses for partially derandomized measurement. They also connect the OGM cost function to variance.

B LDF Grouping method

  • LDF grouping represents observables as graph vertices, connects incompatible pairs, and builds compatible sets by processing vertices in descending degree order.The resulting sets contain observables that are pairwise compatible.Source: B LDF Grouping method · p. 22

C Greedy overlapped grouping strategy

D Variance for the partially derandomized strategy

  • OGM’s variance was reported to be unbiased when every observable receives at least one measurement basis, with covariance among outcomes affecting the variance.The derivation assumes independent measurement bases; outcomes for different observables can be correlated.Source: D Variance for the partially… · p. 24

E Relationship between cost function and variance

F Variance comparison

OGM yielded lower estimation variance than the compared methods, with a more pronounced advantage for larger molecules. The table reports molecular ground-state variances under JW encoding across systems from 4 to 14 qubits.

F Variance comparison

  • OGM had much smaller variance than LDF-grouping and LBCS; for larger molecules, its improvement was approximately one order relative to classical-shadow methods.The comparison used a measurement distribution generated with T = 1000 and a negligible ε0.Source: Table 3 · p. 25, F Variance comparison · p. 25

G Numerical results and discussions

The numerical section compares OGM with l1-sampling, LDF Grouping, LBCS, and derandomized CS using variance and estimation error. It also examines encoding choices and a perturbed OGM cost function.

G Numerical results and discussions

  • The comparison evaluates OGM against l1-sampling, LDF Grouping, LBCS, and derandomized CS using variances and estimation errors.The section also compares performance under different fermionic-to-qubit encodings.Source: G Numerical results and discussions · p. 25
  • Table 4 compares variances across JW, BK, and parity encodings and reports OGM's deviation after a small cost-function perturbation.The perturbation is introduced in the main text.Source: G Numerical results and discussions · p. 25
  • Table 5 compares estimation errors for H2, LiH, BeH2, and H2O with 1000 measurements, using OGM probabilities from Algorithm 1.Source: G Numerical results and discussions · p. 25

H Error of the estimation

This section describes how estimation error is assessed across repetitions and reports simulation settings and comparisons for molecular ground states. It also specifies the averaging used for IBM hardware results.

H Error of the estimation

  • Estimation error is quantified by root mean squared error over N independent repetitions of T measurements.Each repetition produces an estimate from independently performed measurements of the initial state.Source: H Error of the estimation · p. 25
  • The average error fluctuates within a small range after more than 10 iterations.Figure 5 plots average errors for different repetition counts N on the 8-qubit H2 molecule.Source: H Error of the estimation · p. 25, Figure 5 · p. 27
  • The simulations use N = 100 for molecules below 14 qubits and N = 20 for NH3; IBM Q results average 12 rounds.Source: H Error of the estimation · pp. 25, 27
  • The reported comparisons include ground-state estimation variances across encodings and errors with 1000 samples.Table 4 covers variances for different molecular-Hamiltonian encodings; Table 5 reports errors for corresponding molecular ground states.Source: Table 4 · p. 26, Table 5 · p. 26

I Experimental results

The hardware experiment compares measurement schemes on an IBM quantum device and a classical simulator. It estimates a four-qubit H2 Hamiltonian with a GHZ state and uses OGM results from 49140 samples as the reference.

I Experimental results

  • The experiment estimates the four-qubit H2 Hamiltonian under JW encoding using a GHZ state, whose variance is much larger than the ground state's.The authors describe this as a suitable testbed for comparing measurement schemes.Source: I Experimental results · p. 27
  • Estimation errors are compared across sample counts for l1-sampling, LDF-grouping, LBCS, derandomized CS, and OGM, against an OGM reference from 49140 samples.Source: I Experimental results · p. 27
  • Figure 6 reports comparisons on the IBM classical simulator over 100 rounds and the ibmq athens cloud device over 12 rounds.Source: Figure 6 · p. 28
Loading 2105.13091v2…