Source-linked AI summary
Efficient estimation of Pauli observables by derandomization
Hsin-Yuan Huang, Richard Kueng, John Preskill
TL;DR
The paper addresses joint estimation of many Pauli expectation values from few state copies, a key task in variational quantum algorithms. It derandomizes randomized single-qubit Pauli measurements by fixing assignments sequentially while controlling the confidence bound. The resulting deterministic protocol is guaranteed to perform at least as well as the randomized baseline and improves molecular ground-state-energy estimation in numerical experiments.
Problem
The task is to estimate many Pauli expectation values within a specified error using as few copies of a repeatedly prepared quantum state as possible.
Method
The procedure replaces randomized single-qubit Pauli assignments sequentially with deterministic choices that minimize the conditional expected confidence bound.
Results
The resulting deterministic measurements have confidence bound no larger than the randomized protocol's average confidence bound and outperform several methods for BeH2 ground-state-energy estimation.
Takeaways & Limitations
For low-weight Pauli observables, deterministic measurements retain an order-log(L) copy requirement, while numerical molecular experiments show advantages over several existing techniques.
Abstract
from arXiv · showhide
We consider the problem of jointly estimating expectation values of many Pauli observables, a crucial subroutine in variational quantum algorithms. Starting with randomized measurements, we propose an efficient derandomization procedure that iteratively replaces random single-qubit measurements with fixed Pauli measurements; the resulting deterministic measurement procedure is guaranteed to perform at least as well as the randomized one. In particular, for estimating any $L$ low-weight Pauli observables, a deterministic measurement on only of order $\log(L)$ copies of a quantum state suffices. In some cases, for example when some of the Pauli observables have a high weight, the derandomized procedure is substantially better than the randomized one. Specifically, numerical experiments highlight the advantages of our derandomized protocol over various previous methods for estimating the ground-state energies of small molecules.
I. INTRODUCTION
The paper targets efficient joint estimation of many Pauli expectation values on repeatedly prepared quantum states, especially for near-term variational algorithms. It derandomizes randomized single-qubit measurements into a deterministic protocol that is never worse under the stated confidence-bound criterion.
- Motivation: NISQ variational algorithms motivate estimating many operator expectation values for applications including chemistry, materials science, and optimization.The paper focuses on Pauli operators, which are particularly relevant to near-term applications.
- Problem setting: The task is to estimate L n-qubit Pauli expectations within error ε while using as few copies of the quantum state ρ as possible.Each copy permits independent X, Y, or Z measurements on every qubit.
- Randomized baseline: For operators of weight at most w, randomized measurements achieve the target accuracy with high probability using M = O(3^w log L/ε^2) copies.The randomized protocol becomes unlikely to succeed with modest M when the list contains high-weight operators.
- Derandomization: The proposed deterministic protocol is obtained by replacing randomized single-qubit measurements one at a time while preserving or increasing the success probability.The procedure evaluates partially deterministic, partially randomized protocols during this replacement process.
- Practical scope: The protocol uses only single-qubit Pauli measurements, making it more amenable to near-term devices than approaches requiring deep quantum circuits.The paper reports substantially better performance than randomized protocols in numerical experiments.
II. STATISTICAL BACKGROUND
The statistical framework defines when a measurement string can inform a target Pauli observable and averages compatible outcomes to estimate its expectation value. Accuracy improves with the number of compatible measurements, and a confidence bound summarizes joint reliability across targets.
- Measurement model: Each full-weight Pauli measurement produces one outcome-sign string from independently measured copies of the n-qubit state.There are 3^n possible measurement strings, each using X, Y, or Z on every qubit.
- Compatibility: A measurement hits a target observable when the target is a marginal of the measurement string after replacing some local non-identity Paulis with I.For example, [X, X] is hit by [X, I], [I, X], and [X, X], but not by strings using Z.
- Compatibility: The hit count h(oℓ; P) records how many measurements provide actionable information about target observable oℓ.When h(oℓ; P) = 0, the procedure sets the estimate to zero because no measurement is compatible with that target.
- Estimation guarantees: The estimator exactly reproduces each target expectation in expectation when h(oℓ; P) ≥ 1, while large-deviation probability decreases exponentially with the number of hits.The estimator averages appropriately marginalized outcomes from measurements that hit the target.
- Joint guarantee: The confidence bound is a statistically sound summary of whether a measurement set predicts all target observables within accuracy ε and confidence 1 − δ.A smaller confidence bound indicates a better Pauli estimation protocol.
III. RANDOMIZED PAULI MEASUREMENTS
Randomized Pauli measurements provide a logarithmic-in-L baseline for low-weight observables, but their hit probability decreases exponentially with observable weight. The paper motivates derandomization as a way to retain the randomized framework while selecting measurements more deliberately.
- Randomized measurements: A randomized measurement hits an observable oℓ with probability 1/3^w(oℓ), yielding an expected M/3^w(oℓ) hits over M measurements.The weight w(oℓ) counts the non-identity qubits in the observable.
- Randomized measurements: Each confidence-bound contribution is exponentially suppressed in ε^2M/3^w(oℓ), linking measurement budget to observable weight.This suppression underlies the randomized error bound.
- Randomized guarantee: M ∝ log(L) maxℓ 3^w(oℓ)/ε^2 randomized measurements suffice to estimate L Pauli expectations to additive error ε.For low-weight observables, this is an order-log(L) measurement requirement.
- Derandomization: The derandomization algorithm represents measurements as an n × M label array and progressively fixes random labels using conditional confidence-bound expectations.At each step it chooses among X, Y, and Z assignments to minimize the conditional expectation over remaining random assignments.
- Scope: Information-theoretic lower bounds show that M ∝ log(L) maxℓ 3^w(oℓ)/ε^2 is asymptotically optimal in some scenarios.High-weight observables remain challenging because random measurements are unlikely to hit them by chance.
IV. DERANDOMIZED PAULI MEASUREMENTS
The paper constructs deterministic Pauli measurements by iteratively fixing randomized single-qubit choices while preserving a confidence-bound guarantee. The resulting procedure is at least as good as average randomized measurements and can reduce the measurement budget substantially.
- The procedure interpolates between randomized measurements for many local observables and deterministic measurements for fewer global observables.
- The confidence bound can be computed for partially deterministic and partially randomized measurement lists, enabling label-by-label construction.
- Each single-qubit setting is fixed by choosing the Pauli label that minimizes the conditional expected confidence bound over remaining random assignments.
- Algorithm 1 guarantees a deterministic measurement set with confidence bound no larger than the average confidence bound of randomized measurements.
- Derandomization reduces the measurement budget by at least an order of magnitude in the reported examples, although the greedy procedure is not guaranteed to be globally optimal.
V. NUMERICAL EXPERIMENTS
The numerical studies evaluate derandomized Pauli measurements for molecular ground-state energy estimation. Across benchmark comparisons, derandomization achieves smaller estimation errors than randomized and other state-of-the-art measurement methods at fixed budgets.
- Randomized Pauli measurements are a simple, efficient approach for estimating many observables required by variational quantum eigensolvers.
- Derandomization refines classical shadows through efficient classical preprocessing without extra quantum-hardware or classical-post-processing cost.
- Numerical experiments report an unconditional improvement of about one order of magnitude for a particular variational quantum eigensolver experiment.
- For BeH2 with Bravyi–Kitaev encoding, derandomization outperforms classical shadows, locally-biased classical shadows, and largest-degree-first grouping in ground-state energy estimation error.
- Across other benchmark molecules and encoding schemes, derandomization consistently gives smaller estimation error than other state-of-the-art techniques at fixed measurement budgets.
VI. CONCLUSION AND OUTLOOK
The paper presents derandomization as a deterministic way to estimate many Pauli expectation values from few measurements, while preserving randomized protocols’ advantages and adapting to observable structure. It reports favorable molecular-energy scaling and identifies broader extensions as future work.
- Conclusion: Derandomization replaces randomized single-qubit Pauli measurements with specific deterministic assignments while retaining the advantages of fully randomized protocols.The procedure is designed to capture fine-grained structure in the target observables.
- Conclusion: The approach improves molecular ground-state energy estimation over many existing techniques.The paper specifically connects this improvement to favorable scaling for molecular ground-state energies.
- Outlook: Randomized measurements support applications including entanglement entropy, topological invariants, device benchmarking, and prediction of physical experiments.The conclusion places derandomization within this broader family of randomized-measurement applications.
- Outlook: Derandomized measurements provide a principled way to adapt randomized procedures to the fine-grained structure of the observables.The method is related to multiplicative weight update and is proposed as a basis for broader measurement-design extensions.
- Outlook: The paper identifies non-Pauli observables, entanglement entropies, and improved cost functions as directions for extending derandomization.These are presented as prospective extensions rather than established results.
2. Few global Pauli observables.
A pair of complete global Pauli strings exposes why randomized measurements can fail for high-weight observables, while derandomization discovers a balanced deterministic schedule. A contrived larger family also demonstrates a limitation of the greedy rule.
- Few global Pauli observables: Randomized measurements are exponentially unlikely to hit either of two complete global strings consisting entirely of Y or entirely of Z.The example targets o1 = [Y, ..., Y] and o2 = [Z, ..., Z].
- Few global Pauli observables: The derandomization algorithm first selects Y for the first target and then Z for the second, tracking each complete string.The assignments emerge from comparing conditional expectations at each step.
- Few global Pauli observables: The resulting deterministic schedule alternates the two global observables, measuring both equally often.The paper describes this protocol as statistically optimal for the example.
- Very many global Pauli observables: For a large incompatible family, the greedy rule can repeatedly favor the majority Z-prefix and completely neglect the lone X-prefix observable.The construction contains L = 3^(n−1) + 1 global target observables, with 3^(n−1) beginning with Z.
- Very many global Pauli observables: This imbalance yields a non-minimal confidence bound, showing that the greedy derandomization is not guaranteed to be globally optimal.The failure occurs in a highly stylized collection of incompatible global observables.
1. Proof of Lemma 1
The proof establishes concentration for empirical estimates built from measurement outcomes that hit each target Pauli observable. A union bound then controls all L estimation errors simultaneously.
- Proof of Lemma 1: A Pauli measurement provides information about a target observable when the target can be obtained by marginalizing compatible measurement outcomes.The resulting empirical averages estimate the target expectation values from hit measurements.
- Proof of Lemma 1: The hitting count h(oℓ; P) records how many measurements provide meaningful information about observable oℓ.If the hitting count is zero, the estimator is set to zero because no actionable measurement information is available.
- Proof of Lemma 1: The reconstruction error is exponentially suppressed as the number of hits for each target Pauli observable increases.This behavior follows from concentration of empirical averages of independent signed outcomes.
- Proof of Lemma 1: The union bound combines the individual deviation probabilities to control simultaneous errors across the collection of target observables.This concentration inequality directly yields Lemma 1 in the main text.
- Proof of Lemma 1: Hoeffding’s inequality bounds the deviation probability for each empirical estimate, including the zero-hit case.The zero-hit bound is handled by the trivial probability upper bound of one.
2. Derivation of Eq. (6)
The derivation computes conditional expectations for partially assigned measurement protocols by decomposing hit indicators into independent single-qubit factors. The remaining Pauli labels contribute according to the reduced observable weights.
- Derivation of Eq. (6): The confidence-bound expression is rewritten using sums of indicator functions that record whether each measurement hits a target observable.This exposes the structure needed for conditional-expectation calculations.
- Derivation of Eq. (6): Each remaining hit indicator is decomposed into products of elementary single-qubit indicator functions.The decomposition separates the contributions of individual qubit labels.
- Derivation of Eq. (6): A random single-qubit Pauli label hits a non-identity target label with probability 1/3.This probability supplies the local factor in the expected confidence-bound calculation.
- Derivation of Eq. (6): For a partially assigned protocol, the already fixed measurements and labels are separated from independently uniform remaining labels.Independence makes the conditional expectation factorize into individual components.
- Derivation of Eq. (6): The exponent uses the weight of the reduced Pauli string consisting of the unassigned qubit labels.The reduced weight is denoted w¬k(oℓ), with w¬0(oℓ) equal to the full Pauli weight.
Appendix C: Details regarding numerical experiments
The numerical experiments evaluate derandomized Pauli measurements for molecular Hamiltonians using exact ground states, several encodings, and competing measurement procedures. The appendix also describes cost-function variants that incorporate measurement counts and Hamiltonian coefficients, while noting that the greedy cost function is not necessarily optimal.
- Experimental setup: Molecular electronic Hamiltonians are mapped to qubit Hamiltonians using Jordan-Wigner, Bravyi-Kitaev, and Parity encodings.The benchmark molecules range from 4 to 16 spin orbitals, with specified qubit sizes including H2, LiH, BeH2, H2O, and NH3.
- Experimental setup: The experiments apply each measurement procedure to exact ground states obtained by Lanczos diagonalization.Measurement error is quantified using RMSE over independent repetitions, relative to the exact ground-state electronic energy.
- Compared procedures: The comparison includes LDF grouping, classical shadows, and locally-biased classical shadows.LDF is described as a generally recommended heuristic, while locally-biased shadows bias single-qubit Pauli-basis distributions to reduce Hamiltonian-estimation variance.
- Derandomization cost functions: The derandomization cost function tracks how often each target observable is measured and penalizes incompatible remaining Pauli assignments.Its conditional-expectation formulation assumes a fixed measurement count M, while a modified formulation supports continuing until measurement criteria are met.
- Derandomization cost functions: Coefficient-weighted costs promote measuring Hamiltonian observables proportionally to their coefficient magnitudes |α_oℓ|.The authors state that alternative application-tailored cost functions might perform better and leave their exploration for future work.