Certified Optimal Measurement Reduction over Quantum Context Landscapes

Technical Summary: Certified Optimal Measurement Reduction over Quantum Context Landscapes

Problem Statement
Estimating the expectation value $\langle H \rangle$ of a quantum Hamiltonian on near-term quantum devices requires decomposing $H$ into measurable fragments (contexts) and allocating measurement shots to minimize variance. Existing strategies—ranging from qubit-wise commuting (QWC) grouping to classical shadows and fermionic fragments—often produce measurement schedules without a rigorous lower bound on the shot cost for a specific declared measurement model. Consequently, it is difficult to distinguish whether an observed improvement stems from a better point in a fixed landscape, an enlargement of the landscape (new contexts), or simply unoptimized coefficient splitting within an existing framework. The paper addresses the need for a "certificate" that answers: within a declared set of measurement contexts and a covariance model, what is the minimum unavoidable shot cost, and how close is a given schedule to this optimum?

Methodology
The authors propose a framework that divides the measurement reduction problem into two distinct optimization layers: a continuous inner layer and a non-convex outer layer.

1. Inner Layer (Convex Optimization): For a fixed dictionary of measurement contexts $\mathcal{D} = \{(V_\ell, c_\ell)\}$ and a declared covariance model $\Gamma_\ell$, the problem of finding the optimal linear stratified estimator (decomposing $H$ into fragments $F_\ell \in V_\ell$ and allocating shots $N_\ell$) is formulated as a Second-Order Cone Program (SOCP).

   • The objective minimizes the leading shot constant $\Phi = \min \sum \sqrt{c_\ell} \|F_\ell\|_\rho$ subject to the reconstruction constraint $\sum F_\ell = H$.
   • This formulation subsumes all coefficient-splitting freedoms (including overlapping splitting and state-aware covariance usage) into a single convex gauge.

2. Dual Certificates: The SOCP possesses a conic dual that provides a lower-bound witness ($L$).

   • A primal solution yields an upper bound ($U$) representing the cost of a specific schedule.
   • A dual feasible vector $y$ certifies that no unbiased linear stratified estimator over the same dictionary can achieve a cost lower than $L$.
   • The gap $U/L$ provides a machine-checkable certificate of optimality. If $U=L$, the schedule is globally optimal for the declared landscape.

3. Outer Layer (Combinatorial Search): The design of the dictionary itself (selecting which contexts to include) and the calibration of covariance models are non-convex problems. The authors employ RANGE, a robust adaptive nature-inspired global optimizer (hybridizing artificial bee colony and genetic algorithms), to:

   • Search for optimal sub-dictionaries (compression).
   • Perform column generation: using the dual witness as a "pricing oracle" to identify missing contexts that violate the dual constraint (i.e., contexts that would provably lower the cost).
   • Calibrate covariance-radius models using pilot data.

4. Robustness: To handle uncertainty in the covariance model (e.g., from pilot measurements or proxy states), the framework constructs simultaneous confidence intervals (sandwiches) for the covariance matrices. This yields data-driven robust certificates ($L_{rob} \le \Phi \le U_{rob}$) that hold with high probability without requiring knowledge of the true state $\rho$.

Key Contributions

1. Exact Optimum with Classical Pedigree: The paper establishes that the minimum leading shot constant for any finite dictionary is the value of an SOCP. This is a quantum-context specialization of multiresponse $c$-optimal experimental design, providing the global convex closure of the coefficient-splitting design space.
2. Independently Checkable Certificates: Unlike prior works that report schedules and estimated variances, this framework exports a dual witness. A verifier can repair feasibility residuals and recompute bounds without trusting the optimizer, ensuring the reported gap is conservative and valid.
3. Validity Under Covariance Uncertainty: Theorem 4 provides high-confidence robust certificates using pilot data, upgrading oracle-based certificates to data-driven ones.
4. Dictionary Certification via Column Generation: The dual witness acts as a pricing oracle. If a missing context violates the dual constraint, it is added to the dictionary. This allows the framework to certify optimality over a landscape larger than the one initially solved or to identify when a landscape must be enlarged.
5. Grading Instrument: The certificate distinguishes three regimes: heuristics that are already optimal in their own landscape, heuristics that leave "gauge freedom" (unoptimized splitting) on the table, and landscapes that are fundamentally suboptimal and require enlargement.

Numerical Results
The framework was validated across synthetic landscapes, molecular Hamiltonians (H$_2$, LiH, BeH$_2$, H$_2$O), and production-scale f-element Hamiltonians (CeO, NdO, UO$_2^+$, UO$_2^+$) with 29–35 qubits.

• Optimality Gaps: For small systems like H$_2$, standard strategies (e.g., sorted insertion) were found to be exactly optimal. However, for larger systems like H$_2$O, standard strategies left factors of 2.1–7.7 in shot costs unoptimized within their own settings.
• Dictionary Compression: Using global search, the authors compressed molecular context dictionaries by 4.3–6.1$\times$ while increasing the certified shot cost by only 0.2–2.1%. This revealed a sharp "knee" in the trade-off between dictionary size and cost.
• Impact of Entangled Settings: Adding fully commuting (FC) contexts (entangled settings) lowered the certified optimum by 25–56% for molecular systems. For production f-element Hamiltonians, this enlargement saved 31–70% of shots compared to QWC-only dictionaries.
• Compression vs. Sampling: The study demonstrated that compression techniques designed to reduce block-encoding norms (simulation cost) do not necessarily reduce sampling cost. For example, symmetry shifts reduced the block-encoding norm significantly but had minimal impact on the certified measurement constant, whereas qubit tapering significantly reduced the shot count.
• Production Scale: The method successfully generated certificates for Hamiltonians with $\sim 2 \times 10^4$ terms and $\sim 10^4$ contexts (approx. $2 \times 10^6$ cone variables) in 8–15 minutes on a single CPU node, with certified gaps below $10^{-1}\%$.

Significance and Claims
The paper claims to establish a common standard for measurement-reduction claims. By separating the non-convex design choices (dictionary selection) from the convex core (optimal allocation), the framework ensures that global search is reserved for genuine combinatorial problems, while convex optimization provides provable guarantees for the allocation.

The authors emphasize that the framework does not replace existing heuristics (like ShadowGrouping or minimum clique cover) but provides a certificate layer on top of them. Once a heuristic proposes a dictionary or schedule, the conic program optimizes the remaining freedom, and the dual witness certifies how close the result is to the theoretical limit. The paper concludes that measurement reduction should be viewed as "geometry plus optimization," where the landscape geometry is defined by the allowed contexts, and the certificate provides the rigorous bounds necessary to evaluate progress.

The authors explicitly note limitations: the certificate is conditional on the declared covariance model (garbage covariances yield rigorous statements about garbage), and the guarantee is relative to the declared landscape (exact pricing over all possible stabilizer contexts remains a hard combinatorial problem). The framework is designed for stratified unbiased estimators of known targets, not for adaptive or informationally complete protocols, though it can grade the estimators induced by such protocols.