Source-linked AI summary
Operator Sampling for Shot-frugal Optimization in Variational Algorithms
Andrew Arrasmith, Lukasz Cincio, Rolando D. Somma, Patrick J. Coles
TL;DR
VQCA optimization can require many shots to estimate gradients over large sets of operators. The paper combines weighted random operator sampling with adaptive shot allocation in Rosalin, which outperforms other approaches in the tested molecule problems, particularly as Hamiltonians grow more complex.
Problem
Method
Rosalin combines coefficient-weighted random operator sampling with iCANS-style adaptation of shots for individual gradient components.
Source: §I · p. 1, §III · p. 5Results
For Hamiltonians with more than a few terms, Rosalin outperforms the other optimizer and sampling-strategy combinations considered, with larger advantages reported for more complex molecules.
Source: §I · p. 2, §III · p. 6Takeaways & Limitations
Random and hybrid sampling extend unbiased estimation into few-shot regimes while retaining the standard 1/stot variance scaling.
Source: §3 · p. 3
Abstract
from arXiv · showhide
Quantum chemistry is a near-term application for quantum computers. This application may be facilitated by variational quantum-classical algorithms (VQCAs), although a concern for VQCAs is the large number of measurements needed for convergence, especially for chemical accuracy. Here we introduce a strategy for reducing the number of measurements (i.e., shots) by randomly sampling operators $h_i$ from the overall Hamiltonian $H = \sum_i c_i h_i$. In particular, we employ weighted sampling, which is important when the $c_i$'s are highly non-uniform, as is typical in chemistry. We integrate this strategy with an adaptive optimizer developed recently by our group to construct an improved optimizer called Rosalin (Random Operator Sampling for Adaptive Learning with Individual Number of shots). Rosalin implements stochastic gradient descent while adapting the shot noise for each partial derivative and randomly assigning the shots amongst the $h_i$ according to a weighted distribution. We implement this and other optimizers to find the ground states of molecules H$_2$, LiH, and BeH$_2$, without and with quantum hardware noise, and Rosalin outperforms other optimizers in most cases.
I. INTRODUCTION
VQCAs face shot costs from repeated circuit measurements, large noncommuting operator sets, and hardware-noise-flattened training landscapes. The paper combines random operator sampling with adaptive shot allocation in Rosalin and reports better performance than other approaches when Hamiltonians have more than a few terms.
I. INTRODUCTION
- VQCA optimization faces shot costs from repeated circuit runs, large non-commuting operator sets, and hardware-noise-flattened training landscapes.Gradient methods may also require estimating many partial derivatives over sums of expectation values.Source: §I · p. 1
- Sampling operators with probabilities proportional to |ci| gives an unbiased cost estimator even with a single shot and may help escape local minima.The paper distinguishes its sampling approach from the one in Ref. [47].Source: §I · p. 1
- For Hamiltonians with more than a few terms, Rosalin outperforms all other optimizer and sampling-strategy combinations considered.The reported advantage grows with Hamiltonian size and complexity.Source: §I · p. 2
- Rosalin combines random operator sampling with iCANS, which adapts shot noise for each partial derivative while maximizing expected gain per shot.The resulting optimizer is applied to VQE for H2, LiH, and BeH2.Source: §I · pp. 1–2
A. Variances of Estimation Strategies
- The estimator framework allocates a total shot budget across operators and is unbiased when each operator has positive expected allocation.If an operator receives zero expected shots, the estimator can become undefined or biased absent special symmetries or vanishing coefficients.Source: A. Variances of Estimation Strategies · p. 2
1. Uniform Deterministic Sampling
Uniform Deterministic Sampling (UDS) divides shots equally among Hamiltonian terms, subject to an integer-shot constraint. It is optimal in the special case where operator standard deviations scale inversely with coefficient magnitudes.
1. Uniform Deterministic Sampling
- UDS allocates an equal number of shots to each of the N Hamiltonian terms.For a total budget stot, it sets si = stot/N.Source: §1 · p. 2
- UDS requires a total shot budget divisible by N; otherwise it uses the largest multiple of N not exceeding the requested budget.Positive integer shot counts motivate this adjustment.Source: §1 · p. 2
- UDS is optimal in the special case where σi is proportional to 1/|ci|.Source: §1 · p. 2
2. Weighted Deterministic Sampling
Weighted Deterministic Sampling (WDS) allocates shots in proportion to coefficient magnitudes. For chemical Hamiltonians, it tends to outperform uniform allocation when coefficient magnitudes vary more than operator standard deviations.
2. Weighted Deterministic Sampling
- WDS deterministically allocates shots in proportion to |ci|, using integer shot counts.When the proportional allocation is non-integer, the method floors it and redefines the total shots used.Source: §2 · pp. 2–3
- For chemical Hamiltonians, WDS tends to outperform UDS because coefficient magnitudes vary more than operator standard deviations.The authors report this empirical pattern for both random states and low-energy states.Source: §2 · p. 3
- WDS reduces to UDS when all coefficient magnitudes are equal and is optimal when all σi magnitudes are equal.Source: §2 · p. 3
3. Weighted Random Sampling
Weighted random sampling assigns shots to Hamiltonian operators with probabilities proportional to coefficient magnitudes. It permits unbiased estimation below the deterministic shot floor, including with a single shot, while retaining 1/stot variance scaling at high shot counts.
3. Weighted Random Sampling
- Deterministic strategies require measuring every operator, so their shot floor for unbiased estimates increases with the number of operators N.Random sampling can produce an unbiased estimate with as little as one shot.Source: §3 · p. 3
- Weighted Random Sampling (WRS) draws operators with probabilities proportional to |ci| and allocates the total shots through a multinomial distribution.The expected number of shots for operator hi is pistot.Source: §3 · p. 3
- At high shot counts, WRS resembles Weighted Deterministic Sampling, but its additional nonnegative variance terms do not change the 1/stot scaling.The added terms are the price of extending weighted sampling to the few-shot, high-variance regime.Source: §3 · p. 3
4. Weighted Hybrid Sampling
Weighted Hybrid Sampling (WHS) combines deterministic and random weighted allocation. It uses deterministic allocation when the shot budget permits and random allocation for the remainder, with an all-random fallback below the floor.
4. Weighted Hybrid Sampling
- When stot ≥ sfloor, WHS first assigns shots according to WDS and then randomly assigns any leftover shots.When stot < sfloor, all shots are allocated randomly using WRS.Source: §4 · p. 3
- WHS variance is no smaller than WRS variance, and its added terms scale as 1/stot^2 because the randomly allocated shot count is bounded above.Those terms therefore do not contribute significantly at high shot counts, making WHS suited to both low- and high-shot regimes.Source: §4 · p. 3
- Figure 1 compares estimator variances across sampling strategies for low-energy states of H2 at D = 1 and LiH and BeH2 at D = 2.The caption identifies the molecular panels and ansatz depths.Source: Figure 1 · p. 4
5. Randomly Selecting Only One Term
Weighted Single Sampling (WSS) uses all shots to measure one randomly selected operator. It is unbiased, but its variance has a floor because its additional terms do not decrease as 1/stot.
5. Randomly Selecting Only One Term
- WSS randomly selects one operator and uses all shots to measure it, with selection probability pi; the weighted version uses probabilities proportional to |ci|.The paper contrasts this single-operator draw with strategies that distribute shots across operators.Source: §5 · p. 4
- Although WSS provides an unbiased estimator, measuring only one operator creates a variance floor because the additional terms no longer scale as 1/stot.Extending the method to a subset of operators improves the situation but recovers 1/stot scaling only when all operators are included.Source: §5 · p. 4
6. Numerical Comparison of Variances
The numerical comparison evaluates sampling-strategy variances for low-energy molecular states using the specified ansatzes. Across H2, LiH, and BeH2, weighted strategies generally have lower variance than UDS, with the strongest strategy depending on shot count.
6. Numerical Comparison of Variances
- The variance comparison is motivated by its dependence on both the state and the Hamiltonian.The reported molecular Hamiltonians are those used in.Source: §6 · p. 4
- The study numerically compares variance for low-energy states obtained at the end of VQE, using the Figure 2 ansatz and Hamiltonians for H2, LiH, and BeH2 used in.The ansatz gate block is repeated D times to provide ansatzes of different depths.Source: §6 · p. 4, Figure 2 · p. 4
- For all three molecular cases, WRS, WHS, and WDS when relevant have lower variance than UDS; WDS leads at high shot counts, while WRS and WHS perform best at small counts.WHS moves close to WDS once deterministic allocation becomes relevant, while WSS is typically uncompetitive because of its variance floor.Source: §6 · p. 4
- Algorithm 1 estimates the Hamiltonian using WRS or WHS, with operator probabilities proportional to |ci| and single-shot estimates weighted by ci/pi.The algorithm selects the hybrid option through a Boolean flag.Source: §6 · p. 5
B. The Rosalin Method
Rosalin combines iCANS with weighted random or hybrid operator sampling to make VQCA optimization more shot-frugal. Its advantage becomes more marked as Hamiltonians grow, including for BeH2 with commuting subsets.
B. The Rosalin Method
- Rosalin combines iCANS with weighted random sampling (WRS) or weighted hybrid sampling (WHS), retaining expected-gain-per-shot optimization.The WRS and WHS versions are called Rosalin1 and Rosalin2, respectively.Source: B. The Rosalin Method · p. 5, §III · p. 5
III. DISCUSSION
- For larger, more complicated Hamiltonians, Rosalin can use very few shots early and increase precision as optimization proceeds.Its random and hybrid sampling schemes retain the standard 1/stot variance scaling.Source: §III · pp. 5–6
- For LiH and BeH2, Rosalin shows a marked advantage over other strategies, including with BeH2’s 44 commuting subsets; H2’s four-term Hamiltonian shows little difference.The comparisons include noisy and noiseless optimization for H2 and LiH.Source: §III · p. 6, Figure 4 · p. 6, Figure 3 · p. 6
- Biased Hamiltonian truncation could be used when its total energy bias stays negligible relative to the target accuracy.The proposed random and hybrid sampling methods apply to a truncated Hamiltonian as well as the full Hamiltonian.Source: §III · p. 7
- Random and hybrid sampling could also lower the computational cost of expectation-value estimates in non-variational methods.The authors note potential relevance to traditional quantum algorithms, including in the fault-tolerant era.Source: §III · p. 7
IV. METHODS
The estimator for the Hamiltonian expectation is unbiased when each operator receives a positive expected number of shots. The proof establishes this condition for the shot allocation.
IV. METHODS
- The estimator uses measurement outcomes for each h_i and allocates s_i shots to that operator, with s_i allowed to be random.The setup assumes E[s_i] > 0 for all i.Source: A. Proof of Prop. 1 · p. 7
- The proof derives unbiasedness by taking the estimator’s expectation under the positive-expected-shot condition.The resulting expectation is ⟨H⟩.Source: A. Proof of Prop. 1 · p. 7
- The estimator’s expected value equals ⟨H⟩ when E[s_i] > 0 for every operator.This is the stated unbiasedness condition for the estimator.Source: A. Proof of Prop. 1 · p. 7
B. Proof of Prop. 2
The section derives the estimator’s variance and considers how prior operator-variance information could affect shot allocation. Prior information can help expectation estimation, but using previous-iteration variances during minimization performed poorly empirically.
C. Remark on Using Prior Variance Information
- Prior knowledge of operator variances can optimize deterministic shot allocation and reduce estimator variance, though integer shot counts may require flooring.The unbiased estimator must allocate at least one shot to each operator, requiring regularization when σ_i approaches zero.Source: C. Remark on Using Prior Variance… · p. 8
- Variance-informed random sampling becomes unstable when any σ_i is small, because its variance diverges without a lower-bound regularizer.This is the stated limitation of the random probability prescription using prior σ_i values.Source: C. Remark on Using Prior Variance… · p. 8
- Using previous-iteration σ_i values to guide minimization performed poorly empirically, so Rosalin does not incorporate that information.The authors suggest it may still help estimate an expectation value after optimization.Source: C. Remark on Using Prior Variance… · p. 8
D. The Rosalin Optimizer
Rosalin’s hyperparameters govern derivative bounds, learning rates, shot-count adaptation, and variance regularization. The text gives constraints and recommendations for setting them.
D. The Rosalin Optimizer
- The Lipschitz bound L is set by the Hamiltonian; the authors recommend L = M, with learning rates constrained by 0 < α < 2/L.Source: D. The Rosalin Optimizer · p. 8
- The running-average constant μ controls how quickly recommended shots per gradient component change, and can be near one for smoother shot increases.Unlike running averages in other methods, μ does not directly influence the parameter update step.Source: D. The Rosalin Optimizer · p. 8
- The minimum shot count s_min must be at least 2 for the variance estimate to be defined, while bias b should be positive and small relative to expected variances.The bias acts as a regularizer.Source: D. The Rosalin Optimizer · p. 8