Certified Bounds on the Measurement Cost of Molecular Hamiltonians

The gist The problem, plainly. A quantum computer returns samples, not an energy. Estimating ⟨H⟩ therefore requires many state preparations and measurements, and for chemically relevant Hamiltonians this shot cost can dominate the calculation<ref:2607.16866#pg2>

Measurement Problem and Certificates

The paper introduces a certificate-centered formulation to address the bottleneck in estimating expectation values of observables that cannot be measured directly, where existing strategies lack a matching lower bound over the same allowed measurements<ref:2607.16866#pg2> The core idea is to compute the minimum leading cost among unbiased linear stratified estimators induced by declared single-shot scores and attach a verifiable lower-bound witness<ref:2607.16866#pg2> This certificate governs the sampling route to expectation values for variational algorithms, analog simulators, and any protocol that estimates ⟨H⟩ by repeated preparation and measurement of contexts<ref:2607.16866#pg2> The conic dual supplies an independently checkable lower-bound witness which allows an external verifier to recompute L ≤ Φ ≤ U from stored data without trusting the optimizer<ref:2607.16866#pg2>

Exact Optimum over a Finite Landscape

The optimization core is a quantum-context specialization of multiresponse c-optimal experimental design, where the SOCP reduction and its dual geometry are classical<ref:2607.16866#pg2> Theorem 1 states that for any finite dictionary of measurement settings, covariance model, and per-setting costs, the minimum leading shot constant required to achieve mean-square error at most ε2 is given by a second-order cone program<ref:2607.16866#pg2> The conic dual supplies a witness y whose value lowerbounds every schedule in the landscape<ref:2607.16866#pg2> The primal solution gives an explicit schedule and an upper bound U, while the dual feasible vector gives a lower bound L on the value of every schedule in the same dictionary<ref:2607.16866#pg2>

Data-Driven Robust Certificates

When pilot measurements yield simultaneous high-confidence brackets [Lrob, Urob] on the true landscape via covariance sandwiches, Theorem 4 provides a robust upper and lower value that is conditional only on the declared confidence level<ref:2607.16866#pg2> The robust upper value Urob and lower value Lrob satisfy Lrob ≤ Φ Dρ,c(h) ≤ Urob with probability at least 1 − δ<ref:2607.16866#pg2> This upgrades an oracle-covariance certificate to a datadriven one by using pilot data to account for covariance uncertainty<ref:2607.16866#pg2>

Landscape Expansion via Column Generation

The dual witness acts as a pricing oracle, and column generation can be used to find missing contexts that provably help or terminate with optimality certified over a landscape larger than the dictionary actually solved<ref:2607.16866#pg2> If a missing context V violates the full-landscape dual constraint, adding it and reoptimizing allows for an anytime algorithm where every iteration has a valid schedule, a valid lower bound, and a diagnostic for what kind of context is missing<ref:2607.16866#pg2>

Production-Scale Benchmarks

The work provides production-scale benchmarks for f-element Hamiltonians from an exascale pipeline using Hartree–Fock-proxy covariance models<ref:2607.16866#pg2> The study shows that adding fully commuting contexts lowers the certified optimum by as much as 56% with exact depolarized-ground-state covariances<ref:2607.16866#pg2> Furthermore, transformations reducing block-encoding cost need not reduce sampling cost, leading to a common standard of global exploration by RANGE where the landscape is nonconvex and schedules, dual witnesses, and certified gaps where it is convex<ref:2607.16866#pg2>

Dictionary Compression

The framework allows for certified compression of dictionaries; column generation can find compressed dictionaries that retain nearly all certified quality, beating greedy set cover given substantially more contexts<ref:2607.16866#pg2> The trade-off exhibits a knee where running the same search with a Pareto archive returns the trade-off front rather than a single point, indicating where certified quality degrades sharply<ref:2607.16866#pg2>

Conclusion

The central claim is that landscape geometry + convex gauge optimization + duality = certified measurement reduction<ref:2607.16866#pg2> The value of the formulation is that after a finite measurement landscape is declared, the best stratified unbiased estimator is exactly computable, and its optimality is certifiable<ref:2607.16866#pg2> The division of labor between the two optimization layers is enforced, not assumed<ref:2607.16866#pg2> The certificate framework creates a common standard for measurement-reduction claims: publish the schedule, publish the dual witness, and publish the gap<ref:2607.

1. Improved measurement-reduction systems can achieve globally optimal shot allocation by solving the inner layer globally and certifiably as a second-order cone program (SOCP) for any declared set of contexts, per-shot costs, score functions, and covariance model. This provides a minimum leading shot cost among unbiased linear stratified estimators and an independently checkable lower-bound witness.

2. AI systems can now perform robust uncertainty quantification by utilizing simultaneous finite-sample covariance brackets [Lrob, Urob] derived from pilot measurements to provide a high-confidence robust certificate, where the dual witness certifies that Lrob ≤ Φ Dρ,c(h) ≤ Urob with probability at least 1 − δ.

3. Measurement strategies can be dynamically optimized by employing column generation as an anytime algorithm, allowing the system to iteratively search for missing contexts based on a pricing oracle, which determines if a context violates the full-landscape dual constraint by checking if the pricing residual is greater than one ("If ν∗y > 1, a maximizing or approximately maximizing context is added to D").

4. The system can perform certified dictionary compression by utilizing global search (like the RANGE optimizer) on combinatorial choices such as which measurement contexts to include in a compressed set, ensuring that the resulting schedule retains nearly all certified quality and exposing the sharp dictionary-size-versus-cost knee.

5. AI systems can distinguish between heuristic performance and true optimality by using the certificate as a grading instrument, allowing them to answer if a strategy is already optimal in its own landscape, a heuristic that leaves gauge freedom on the table, or a landscape that must itself be enlarged.

Quantum estimates of molecular energy require repeated state preparation and measurement. We bound the minimum repetition count for given measurements and processing rules from above with a practical schedule and from below with independently verified inequalities. For an H 4 chain at H-H distances of 0.90 and 1.80 Åwith 2 per cent uniform noise in the ground state, entangling Clifford measurements, which map Pauli products onto one another, cut leading-order repetitions by at least 65.9 and 61.0 per cent, respectively, relative to any schedule using only single-qubit Pauli measurements and Hamiltonian terms. With 69 unaltered measurement settings, each a basis change followed by qubit readout, processing further observables saves at least 12.04 and 6.70 per cent. For four lanthanide and actinide Hamiltonians with depolarized Hartree-Fock covariances, reducing the sum of absolute Hamiltonian coefficients does not proportionally reduce sampling. The bounds cover linear unbiased estimates from independent batches at small error.