Cost-Function and Measurement Estimation in Variational Algorithms

Measurement estimation is the live bottleneck of the noisy intermediate-scale quantum (NISQ) era, the frontier where variational algorithms are made or broken. Every major software stack — Qiskit Nature, PennyLane, OpenFermion — ships the grouping machinery of this article as a primitive: qubit-wise cliques found by graph coloring, general commuting cliques diagonalized by Clifford circuits, and weighted shot allocation. On top of these sit newer estimators: classical shadows and their derandomized variants predict many observables from randomized measurements with logarithmic sample complexity, now standard for energies, fidelities, and entropies; low-rank and double-factorization decompositions reorganize the $\mathcal{O}(N^4)$ molecular terms into a handful of measurable fragments, cutting the shot-budget constant by orders of magnitude. These were essential to real experiments — Google's 2020 Hartree–Fock demonstration on twelve Sycamore qubits and IBM's hardware-efficient VQE runs on LiH and BeH₂ leaned on grouping and heavy error mitigation to survive. The open problem is quantitative: chemical accuracy beyond classical reach still implies shot counts current devices cannot deliver in reasonable wall-clock time, which is why measurement-estimation research is as central to quantum advantage as the qubits themselves.

Think of the Hamiltonian as a shopping list of Pauli observables, each with a price $c_k$. You can only buy an estimate one coin-flip at a time — every measurement returns $\pm1$ — and pinning one item's expectation to accuracy $\epsilon$ takes about $1/\epsilon^2$ flips. Measurement estimation is the discipline of bundling items you can buy together (commuting Paulis, which share an eigenbasis) and spending your finite shot budget where the price-times-uncertainty $|c_k|\sigma_k$ is highest. The first figure follows one energy through that pipeline: decompose, group, sample, sum.

Commutation is the geometry behind the bundling. Two observables commute if and only if they share an eigenbasis, so one measurement reveals both eigenvalues at once. Qubit-wise commuting strings such as $Z_0Z_1$ and $Z_0$ share a product basis — you only relabel single-qubit axes, essentially free. Generally commuting strings such as $X_0X_1$ and $Y_0Y_1$ share an entangled basis (here the Bell basis), so a Clifford circuit runs before measuring: you pay in two-qubit gates but harvest several terms from one setting. Yet grouping is only half the story — the variance, not the number of settings, is the true cost. A diagonal QAOA Hamiltonian needs a single basis yet still demands many shots because its cost-function variance can be large; a chemistry Hamiltonian with millions of terms may have modest variance if its coefficients are small. The second figure shows the quantity that decides feasibility: how the error shrinks with shot count, and exactly how many measurements chemical accuracy costs for a real molecule.

The cost is linear in $H$, and $H$ expands in the Pauli basis — the natural operator alphabet of qubits. So the energy is a weighted sum of Pauli averages, each readable directly on hardware. This one line is where the labor splits: the device supplies each $\langle P_k\rangle$, the classical computer supplies the coefficients and the sum.

where: $E(\boldsymbol\theta)$ — the variational cost to be minimized; $|\psi(\boldsymbol\theta)\rangle$ — ansatz state from a parameterized circuit; $H=\sum_k c_k P_k$ — Hamiltonian as a real-weighted sum of Pauli strings; $c_k\in\mathbb{R}$ — coefficient (real because $H=H^\dagger$); $P_k$ — tensor product of $\{I,X,Y,Z\}$, a Hermitian unitary with $P_k^2=I$. Read it as a division of labor: measure the parts, combine them classically. Each $\langle P_k\rangle$ is estimated the only way hardware allows — rotate into the Pauli's eigenbasis, sample, and average the $\pm1$ eigenvalues. Because $P_k^2=I$ the eigenvalues are exactly $\pm1$, which fixes both unbiasedness and variance at once.

where: $\hat e_k$ — empirical estimate of $\langle P_k\rangle$; $M_k$ — shots allocated to term $k$; $\lambda_s^{(k)}$ — the $\pm1$ eigenvalue measured on shot $s$; $1-\langle P_k\rangle^2$ — the single-shot variance, maximal ($=1$) when $\langle P_k\rangle=0$ and zero when the state is a $\pm1$ eigenstate. The per-shot variance is bounded by unity because the outcomes are. Averaging $M_k$ independent shots divides the single-shot variance by $M_k$, and summing coefficient-weighted term estimates adds their variances. This is the master cost formula: the total variance is a coefficient-weighted sum of per-term variances, each inversely proportional to the shots spent on it.

where: $\hat E=\sum_k c_k\hat e_k$ — the full cost estimator; $\sigma_k=\sqrt{1-\langle P_k\rangle^2}$ — standard deviation of term $k$; $M_k$ — shots per term, summing to the total budget $M=\sum_k M_k$. The formula assumes the terms are measured in independent shot pools; sharing shots within a commuting group replaces the term-by-term sum with a group variance (equation 5). Given a fixed budget, how should the shots be split? Minimizing equation (3) under $\sum_k M_k=M$ by a Lagrange multiplier gives a clean weighted rule, and substituting it back yields the smallest variance any allocation can reach — the irreducible floor set by the weighted $\ell_1$ norm of the coefficients.

where: $M_k^\star$ — variance-minimizing shots for term (or group) $k$; $\sum_k|c_k|\sigma_k$ — the weighted $\ell_1$ norm, the single quantity that controls the shot budget. Uniform allocation is strictly worse; the optimum funds the terms with large coefficient and large uncertainty. The lever that beats term-by-term measurement is commutation. Two Pauli strings can be read from the same measurement record exactly when they commute, and the variance of that shared estimator is not the sum of the pieces but the full quantum variance of the group's partial Hamiltonian in the trial state.

where: $G$ — a group of mutually commuting Paulis; $H_G$ — the partial Hamiltonian of that group; $M_G$ — shots spent on the group's single measurement setting. Two strings commute iff they differ in an even number of anticommuting single-qubit factors; the covariances that sharing shots induces are already inside $\langle H_G^2\rangle$. For a worst-case guarantee independent of the state, treat each shot as a bounded draw of $H$ in $[-\Lambda,\Lambda]$ with $\Lambda=\sum_k|c_k|$ and apply Hoeffding's inequality — a distribution-free confidence bound with the same $\Lambda^2/\epsilon^2$ scaling.

where: $\epsilon$ — target additive error on $E$; $\delta$ — failure probability, $\mathrm{Pr}(|\hat E-E|>\epsilon)\le\delta$; $\Lambda$ — the (unweighted) $\ell_1$ norm bounding the range of $H$. Because $\sigma_k\le1$, the variance floor $(\sum_k|c_k|\sigma_k)^2$ is never larger than $\Lambda^2$, so equation (6) is the conservative sibling of equation (4). Finally, the same estimator supplies gradients. The parameter-shift rule (owned by aq-qci-parameter-shift-rules-gradients, recalled here) writes each partial derivative as a difference of two energies, so gradient descent is built entirely from cost evaluations already analyzed.

where: $\theta_j$ — a circuit parameter entering through a Pauli-rotation gate $e^{-i\theta_j G/2}$ with $G^2=I$; $\mathbf{e}_j$ — unit vector shifting only $\theta_j$. Each shifted energy carries the full measurement cost of equation (4), so a $p$-parameter gradient multiplies the shot budget by roughly $2p$.

The shot cost changes character sharply across regimes; the table names the four that dominate practice.

1 · A single Pauli expectation, fully worked

A trial state has $\langle P\rangle=0.6$ for some Pauli string $P$. How many shots estimate $\langle P\rangle$ to a standard error $\epsilon=0.01$, and how does this change in the worst case $\langle P\rangle=0$?

Step 1. Compute the single-shot variance from the $\pm1$ statistics. Since $P^2=I$, the eigenvalues are $\pm1$ and $\mathrm{Var}(\lambda)=1-\langle P\rangle^2=1-0.6^2=\mathbf{0.64}$, so the single-shot standard deviation is $\sigma=\sqrt{0.64}=\mathbf{0.8}$.

Step 2. The sample mean of $M$ i.i.d. shots has variance $\sigma^2/M$, so demanding $\sqrt{\sigma^2/M}\le\epsilon$ gives $M\ge\sigma^2/\epsilon^2=0.64/(0.01)^2=\mathbf{6400\ \text{shots}}$. Doubling the precision to $\epsilon=0.005$ would quadruple this to $25\,600$ — the hallmark $1/\epsilon^2$ scaling.

Step 3. In the worst case $\langle P\rangle=0$ the single-shot variance saturates at $\sigma^2=1$, so $M=1/\epsilon^2=1/(0.01)^2=\mathbf{10\,000\ \text{shots}}$. Conversely, if the state were a $\pm1$ eigenstate of $P$ then $\sigma=0$ and a single shot suffices — the estimate is deterministic. The cost scales entirely with how uncertain the observable is in the state, not with the circuit that prepared it.

2 · Grouping and the shot budget of the hydrogen molecule

The two-qubit H₂ Hamiltonian (STO-3G, symmetry-tapered near equilibrium) is $H=g_0 I+g_1 Z_0+g_2 Z_1+g_3 Z_0Z_1+g_4 X_0X_1+g_5 Y_0Y_1$ with $g_1=0.3435$, $g_2=-0.4347$, $g_3=0.5716$, $g_4=g_5=0.0910$ Ha. Find the naive shot budget for chemical accuracy, then group the terms and count measurement settings.

Step 1. Sum the magnitudes of the non-identity terms — the weighted $\ell_1$ norm that controls the budget (conservatively taking $\sigma_k\le1$): $\sum_k|g_k|=0.3435+0.4347+0.5716+0.0910+0.0910=\mathbf{1.5318\ \text{Ha}}$. The identity term $g_0$ only shifts the energy and carries no variance, so it needs no shots.

Step 2. Invert the variance floor at a standard error equal to chemical accuracy, $\epsilon=1.6\times10^{-3}$ Ha: $M=(\sum_k|g_k|/\epsilon)^2=(1.5318/1.6\times10^{-3})^2=(957)^2\approx\mathbf{9.2\times10^{5}\ \text{shots}}$ for a single energy on this two-qubit problem. Fold in an optimization of $\sim100$ iterations with parameter-shift gradients and the total climbs toward $10^{8}$–$10^{9}$ shots — the measurement, not the qubit count, is the bottleneck.

Step 3. Now group by qubit-wise commutation. The three diagonal strings $\{Z_0,Z_1,Z_0Z_1\}$ share the computational ($Z$) basis — one setting; $X_0X_1$ needs its own $X$-basis setting; $Y_0Y_1$ its own $Y$-basis setting. So five terms collapse to three measurement settings, each amortizing its shots across the terms it contains.

Step 4. Push to general commutation. Check that $X_0X_1$ and $Y_0Y_1$ commute: $X_0X_1\,Y_0Y_1=(iZ_0)(iZ_1)=-Z_0Z_1=(-iZ_0)(-iZ_1)=Y_0Y_1\,X_0X_1$, and $Z_0Z_1$ commutes with both. These three form a Bell-basis (stabilizer) group measurable with one Clifford setting, while $\{Z_0,Z_1\}$ stay diagonal (one setting), since $Z_0$ anticommutes with $X_0X_1$ and cannot join the Bell group. Result: 5 terms → 3 qubit-wise settings → 2 general-commuting settings, each grouping trading circuit count against Clifford depth and correlated variance.

Measurement estimation is where a mid-century concentration bound and a twenty-first-century idea about learning quantum systems meet — and its most modern face belongs to the researcher who showed you can predict a great many properties of a state from astonishingly few measurements.

Texts and reviews. Nielsen and Chuang, Quantum Computation and Quantum Information, §2.2 (measurement statistics) and §4.2 (Pauli operators) · Preskill, Lecture Notes on Quantum Computation, Ch. 3 · Watrous, The Theory of Quantum Information, Ch. 2 (measurements as POVMs) · Kitaev, Shen, and Vyalyi, Classical and Quantum Computation, §13 (Hamiltonian expectation) · McClean, Romero, Babbush, and Aspuru-Guzik, "The theory of variational hybrid quantum-classical algorithms," New J. Phys. 18, 023023 (2016) · Huang, Kueng, and Preskill, "Predicting many properties of a quantum system from very few measurements," Nature Physics 16, 1050 (2020) · Verteletskyi, Yen, and Izmaylov, "Measurement optimization in VQE by a minimum clique cover," J. Chem. Phys. 152, 124114 (2020) · Cerezo et al., "Variational Quantum Algorithms," Nature Reviews Physics 3, 625 (2021).

Provenance. The single-shot variance $1-\langle P\rangle^2$ follows from $\lambda^2=1$ and the Born rule (Nielsen and Chuang §2.2). The optimal allocation $M_k^\star\propto|c_k|\sigma_k$ and floor $(\sum_k|c_k|\sigma_k)^2/M$ are a standard Lagrange-multiplier (equivalently Cauchy–Schwarz) result — re-derive by stationarity of $\sum_k c_k^2\sigma_k^2/M_k$. The Hoeffding bound uses range $2\Lambda=2\sum_k|c_k|$, and the group variance is the operator identity $\langle H_G^2\rangle-\langle H_G\rangle^2$. The H₂ coefficients are representative STO-3G values (O'Malley et al., 2016) with weighted $\ell_1$ norm $\sum|g_k|=1.5318$ Ha, giving $M\approx9.2\times10^5$ shots at $\epsilon=1.6\times10^{-3}$ Ha; the $5\to3\to2$ grouping uses $X_0X_1Y_0Y_1=-Z_0Z_1=Y_0Y_1X_0X_1$. Chemical accuracy $1.6\times10^{-3}$ Ha $\approx1$ kcal/mol ($1$ Ha $=627.5$ kcal/mol). The $\mathcal{O}(N^4)$ Pauli scaling and barren-plateau $2^{-n}$ gradient variance are textbook (McClean et al., 2018).

Prerequisites. Variational Quantum Eigensolver · Parameterized Quantum Circuits and Ansatz Design · Quantum Approximate Optimization Algorithm. Leads to. Parameter-Shift Rules and Quantum Gradients · Barren Plateaus in Variational Landscapes · Classical Optimizers for Variational Quantum Algorithms.

Ask the tutor: Ask me to work a full shot budget from a Hamiltonian's Pauli coefficients, to group a set of Pauli strings into qubit-wise and general commuting cliques, or to contrast term-by-term measurement with classical shadows on the same observable.