Simple Algorithm
Quantum Computing · Rydberg State · 26 min

Measurement Cost & Ansatz Design

Shot budgets, Pauli grouping and hardware-efficient ansätze.

A VQE energy is a sum of up to thousands of Pauli expectation values, each estimated from shots. The bill for one energy evaluation, let alone a full optimization, can dwarf the cost of the circuit itself. This lesson derives the shot cost and the optimal allocation, shows how commuting groups and classical shadows cut it, and how the choice of ansatz feeds back into it.

What you’ll learn

  • Derive the variance of the term-by-term energy estimator and the optimal allocation Ni∝∣ci∣σiN_i\propto\abs{c_i}\sigma_i, giving N≤∥c∥12/ε2N\le\norm{c}_1^2/\varepsilon^2.
  • Prove the commutation criterion for Pauli strings, and explain qubit-wise and general commuting groups and their costs.
  • Derive the classical-shadow estimator for random Pauli measurements and its 3k3^k variance for weight-kk observables.
  • Compare hardware-efficient, chemically motivated and adaptive ansätze in expressibility, symmetry, depth and measurement cost.

The shot budget

Write H=∑i=1MciPiH=\sum_{i=1}^Mc_iP_i. The simplest strategy measures each term separately with NiN_i shots and adds the sample means: E^=∑iciP^i\hat E=\sum_ic_i\hat P_i.

DerivationOptimal shot allocation
  1. Var⁡(E^)=∑i=1Mci2σi2Ni\operatorname{Var}(\hat E)=\sum_{i=1}^M\frac{c_i^2\sigma_i^2}{N_i}

    Independent estimates add variances. With single-shot variances σi2=1−⟨Pi⟩2≤1\sigma_i^2=1-\expval{P_i}^2\le1:

  2. Ni⋆=N ∣ci∣σi∑j∣cj∣σj,Var⁡⋆=(∑i∣ci∣σi)2NN_i^\star=N\,\frac{\abs{c_i}\sigma_i}{\sum_j\abs{c_j}\sigma_j},\qquad\operatorname{Var}^\star=\frac{\big(\sum_i\abs{c_i}\sigma_i\big)^2}{N}

    Minimize subject to ∑iNi=N\sum_iN_i=N. By Cauchy–Schwarz, (∑i∣ci∣σi)2≤(∑ici2σi2Ni)(∑iNi)\big(\sum_i\abs{c_i}\sigma_i\big)^2\le\big(\sum_i\frac{c_i^2\sigma_i^2}{N_i}\big)\big(\sum_iN_i\big), with equality iff Ni∝∣ci∣σiN_i\propto\abs{c_i}\sigma_i:

  3. N  ≤  ∥c∥12ε2,∥c∥1=∑i∣ci∣N\;\le\;\frac{\norm{c}_1^2}{\varepsilon^2},\qquad\norm{c}_1=\sum_i\abs{c_i}

    With σi≤1\sigma_i\le1, a target standard error ε\varepsilon needs at most

  4. shots, independent of the number of terms MM (Wecker, Hastings & Troyer, 2015). Uniform allocation gives Var⁡≤M∑ici2/N\operatorname{Var}\le M\sum_ic_i^2/N instead, worse by up to a factor of MM when a few coefficients dominate.

An alternative with the same bound that needs no knowledge of the σi\sigma_i: on each shot, pick term ii with probability ∣ci∣/∥c∥1\abs{c_i}/\norm{c}_1, measure PiP_i, and record sign⁡(ci) ∥c∥1 x\operatorname{sign}(c_i)\,\norm{c}_1\,x for the outcome x=±1x=\pm1. Each record is an unbiased estimate of EE with second moment exactly ∥c∥12\norm{c}_1^2.

Predict before you look

Suppose a molecular Hamiltonian has ∥c∥1=10\norm{c}_1=10 hartree and you want chemical accuracy, ε=1.6×10−3\varepsilon=1.6\times10^{-3} hartree. Using N≈∥c∥12/ε2N\approx\norm{c}_1^2/\varepsilon^2, what is log⁡10N\log_{10}N for a single energy evaluation?

Show the answer

7.6

(10/0.0016)2=62502≈3.9×107(10/0.0016)^2=6250^2\approx3.9\times10^7 shots, so log⁡10N≈7.6\log_{10}N\approx7.6. An optimization needs hundreds to thousands of energy evaluations, and parameter-shift gradients multiply the cost by 2m2m: measurement, not circuit depth, becomes the bottleneck.

Measuring many terms at once

Commuting terms can share shots. For Pauli strings, commutation is a counting criterion:

This gives two levels of grouping:

  • Qubit-wise commuting (QWC) groups: on every qubit, all members act with the same Pauli or with I\id. One layer of single-qubit rotations measures the whole group; e.g. ZZIZZI, ZIZZIZ, IZZIZZ and ZZZZZZ share the ZZ basis.
  • General commuting groups: any set of pairwise commuting Pauli strings can be mapped by a Clifford circuit to ZZ-type strings, so one measurement setting suffices, at the cost of an entangling basis change with O(n2)O(n^2) gates in general. For example XXXX, YYYY and ZZZZ commute pairwise (two anticommuting positions each) but are not QWC; a Bell-basis measurement reads all three.

Choosing groups to minimize the number of settings is a minimum clique cover problem (equivalently, coloring the graph whose edges join non-commuting terms), NP-hard in general; greedy heuristics work well in practice (Verteletskyi, Yen & Izmaylov, 2020). Grouped terms share shots, so covariances enter: Var⁡(∑i∈GciP^i)=1NG∑i,j∈GcicjCov⁡(Pi,Pj)\operatorname{Var}\big(\sum_{i\in G}c_i\hat P_i\big)=\frac{1}{N_G}\sum_{i,j\in G}c_ic_j\operatorname{Cov}(P_i,P_j), which can help or hurt.

Classical shadows

Huang, Kueng & Preskill (2020) proposed measuring first and choosing the observables later. On each shot, measure every qubit in a uniformly random Pauli basis (XX, YY or ZZ) and store the outcomes: a classical shadow of the state.

DerivationThe random-Pauli shadow estimator
  1. M(ρ)=13∑W∑b=±⟨bW|ρ|bW⟩∣bW⟩ ⁣⟨bW∣=13∑WI+rWW2=13ρ+13Tr⁡(ρ) I\mathcal M(\rho)=\frac13\sum_W\sum_{b=\pm}\mel{b_W}{\rho}{b_W}\dyad{b_W}=\frac13\sum_W\frac{\id+r_WW}{2}=\frac13\rho+\frac13\Tr(\rho)\,\id

    Per qubit, average the post-measurement projector over the random basis W∈{X,Y,Z}W\in\{X,Y,Z\} and the outcome b=±b=\pm. For ρ=12(I+r⃗⋅σ⃗)\rho=\frac12(\id+\vec r\cdot\vec\sigma):

  2. ρ^=⨂j=1n(3∣bj⟩ ⁣⟨bj∣−I),E[ρ^]=ρ\hat\rho=\bigotimes_{j=1}^n\big(3\dyad{b_j}-\id\big),\qquad\mathbb E[\hat\rho]=\rho

    This is a depolarizing channel, inverted by M−1(Y)=3Y−Tr⁡(Y) I\mathcal M^{-1}(Y)=3Y-\Tr(Y)\,\id. Applied to the observed projectors it gives a single-shot snapshot, an unbiased estimator of ρ\rho:

  3. E[Tr⁡(Pρ^)]=Tr⁡(Pρ),Var⁡[Tr⁡(Pρ^)]=3k−Tr⁡(Pρ)2≤3k\mathbb E\big[\Tr(P\hat\rho)\big]=\Tr(P\rho),\qquad\operatorname{Var}\big[\Tr(P\hat\rho)\big]=3^k-\Tr(P\rho)^2\le3^k

    For a Pauli string PP of weight kk, Tr⁡(Pρ^)=∏j∈supp⁡P3⟨bj|Pj|bj⟩\Tr(P\hat\rho)=\prod_{j\in\supp P}3\mel{b_j}{P_j}{b_j}, since each qubit outside the support contributes Tr⁡(3∣bj⟩ ⁣⟨bj∣−I)=1\Tr(3\dyad{b_j}-\id)=1. It equals ±3k\pm3^k when all kk random bases match PP (probability 3−k3^{-k}) and 00 otherwise, so

Predict before you look

With random-Pauli shadows, what fraction of snapshots carry information about one particular weight-3 Pauli string? Answer in percent.

Show the answer

3.7 %

All three relevant qubits must have been measured in the matching basis: (1/3)3=1/27≈3.7%(1/3)^3=1/27\approx3.7\%. Each informative snapshot contributes ±27\pm27 and the rest contribute 00, hence the variance 3k3^k. Shadows shine when you need many low-weight observables at once (the log⁡M\log M); for a single Hamiltonian, good groupings, derandomized shadows or locally biased shadows usually do better.

Ansatz design and its measurement bill

AspectHardware-efficientChemically motivated (UCCSD, Givens)Adaptive (ADAPT-VQE)
Building blocksNative rotations and fixed native entanglersFermionic excitations eθ(τ−τ†)e^{\theta(\tau-\tau^\dagger)} on a Hartree–Fock referenceOperators added one at a time, chosen by energy gradient from a pool
SymmetriesGenerally broken (particle number, spin)Preserved by constructionPreserved if the pool preserves them
DepthMinimal per layerDeep after Jordan–Wigner compilationCompact, problem-tailored
ParametersO(nL)O(nL) for LL layersO(Nocc2Nvirt2)O(N_{\text{occ}}^2N_{\text{virt}}^2) double excitationsGrow as needed
TrainabilityBarren plateaus when deep and randomBetter near a good reference, not guaranteedGood in practice
Measurement bill2m2m energy evaluations per gradientSame, with more parametersPlus gradients of the whole pool at each growth step
Hardware-efficient ansätze were popularized by Kandala et al. (2017); ADAPT-VQE was introduced by Grimsley et al. (2019).

Symmetry preservation is a concrete design principle. A gate e−iθGe^{-i\theta G} conserves the number of excitations (the Hamming weight) iff [G,∑jZj]=0[G,\sum_jZ_j]=0. The generator G=12(X1Y2−Y1X2)G=\tfrac12(X_1Y_2-Y_1X_2) satisfies this: it annihilates ∣00⟩\ket{00} and ∣11⟩\ket{11} and acts within span{∣01⟩,∣10⟩}\mathrm{span}\{\ket{01},\ket{10}\}, so e−iθGe^{-i\theta G} is a real Givens rotation there. Networks of Givens rotations implement any single-particle basis change (preparing Slater determinants) without ever leaving the right particle-number sector.

Key takeaways

  • Term-by-term estimation with optimal allocation Ni∝∣ci∣σiN_i\propto\abs{c_i}\sigma_i costs at most ∥c∥12/ε2\norm{c}_1^2/\varepsilon^2 shots per energy, independent of the number of terms.
  • Pauli strings commute iff they differ non-trivially on an even number of qubits; QWC groups need only local rotations, general commuting groups a Clifford basis change, and optimal grouping is NP-hard.
  • Random-Pauli classical shadows estimate MM weight-kk observables from O(3klog⁡M/ε2)O(3^k\log M/\varepsilon^2) snapshots.
  • The ansatz sets the measurement bill (parameters × 2 evaluations × shots per energy); symmetry-preserving and adaptive ansätze trade depth for structure.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

For H=3 Z1+X1H=3\,Z_1+X_1 with σ1=σ2=1\sigma_1=\sigma_2=1 and a fixed total budget, what fraction of the shots should optimal allocation give to the Z1Z_1 term?

  1. 12\tfrac12
  2. 34\tfrac34
  3. 910\tfrac{9}{10}
  4. 14\tfrac14
Show the answer

B. 34\tfrac34

Ni∝∣ci∣σiN_i\propto\abs{c_i}\sigma_i, so the Z1Z_1 term gets 3/(3+1)=3/43/(3+1)=3/4. Allocating in proportion to ci2c_i^2 (giving 9/109/10) over-invests in the large term.

Question 2

Which pair of Pauli strings commutes?

  1. XIXI and ZIZI
  2. XXXX and XZXZ
  3. XYZXYZ and ZYXZYX
  4. ZZZZZZ and XIIXII
Show the answer

C. XYZXYZ and ZYXZYX

Count positions holding different non-identity Paulis: X/ZX/Z at position 1 and Z/XZ/X at position 3 (position 2 has Y/YY/Y). Two is even, so they commute. They are not qubit-wise commuting, though, so measuring both on the same shots needs an entangling basis change.

Question 3

For random-Pauli classical shadows, the single-snapshot variance for a weight-kk Pauli observable is at most…

  1. kk
  2. 2k2^k
  3. 3k3^k
  4. 4k4^k
Show the answer

C. 3k3^k

A snapshot contributes ±3k\pm3^k with probability 3−k3^{-k} (all bases match) and 00 otherwise, so the second moment is 3−k⋅9k=3k3^{-k}\cdot9^k=3^k.

Question 4

Which is a disadvantage of hardware-efficient ansätze compared with chemically motivated ones?

  1. They require deep circuits after compilation
  2. They generally break physical symmetries such as particle number, and deep random instances suffer barren plateaus
  3. They cannot run on superconducting hardware
  4. They have no tunable parameters
Show the answer

B. They generally break physical symmetries such as particle number, and deep random instances suffer barren plateaus

Built from native gates, they are shallow, but nothing ties them to the physics: they wander out of the right symmetry sector and, when deep and randomly initialized, approach 2-designs.

Further reading

  • D. Wecker, M. B. Hastings & M. Troyer, "Progress towards practical quantum variational algorithms", Phys. Rev. A 92, 042303 (2015).
  • H.-Y. Huang, R. Kueng & J. Preskill, "Predicting many properties of a quantum system from very few measurements", Nature Physics 16, 1050 (2020).
  • V. Verteletskyi, T.-C. Yen & A. F. Izmaylov, "Measurement optimization in the variational quantum eigensolver using a minimum clique cover", J. Chem. Phys. 152, 124114 (2020).
  • A. Kandala et al., "Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets", Nature 549, 242 (2017).
  • H. R. Grimsley, S. E. Economou, E. Barnes & N. J. Mayhall, "An adaptive variational algorithm for exact molecular simulations on a quantum computer", Nature Communications 10, 3007 (2019).