Case Study 2: Choosing the Primitive

"The Sampler and the Estimator both run. Both return plausible numbers. One of them costs you an exponential factor."

Executive Summary

A team implements a portfolio-optimization prototype. The problem is a cost function over 12 binary variables, encoded as a 12-qubit Ising Hamiltonian. They build the ansatz, run it with the Sampler, reconstruct the cost from the measured distribution, and hand the result to an optimizer.

It works, at 12 qubits, slowly. At 20 qubits it becomes unusable, and the team concludes that "quantum optimization does not scale."

Their conclusion is correct about their implementation and wrong about the cause. They chose the Sampler for a problem whose answer is a single number, and paid a factor that grows like $2^n$ for the privilege. This case study works the arithmetic, shows the fix, and then — because honesty requires it — establishes that the fix does not rescue the underlying claim about quantum optimization, for entirely different reasons that Chapter 37 takes up.

Skills applied: Sampler versus Estimator (§7.5, §7.6); shot-cost scaling (Ch. 5 §5.4, §5.5); Pauli expectation values from counts (Ch. 5 §5.6).

The Implementation

The cost function is an Ising Hamiltonian:

$$C = \sum_{i

with roughly 70 terms for 12 variables. The team's approach:

# What they did
counts = sampler.run([(ansatz_with_measurements, values)], shots=8192).result()[0]...

cost = 0.0
for bitstring, n in counts.items():
    z = [1 - 2 * int(b) for b in reversed(bitstring)]      # 0 -> +1, 1 -> -1
    energy = (sum(J[i][j] * z[i] * z[j] for i, j in pairs)
              + sum(h[i] * z[i] for i in range(n_vars)))
    cost += n * energy
cost /= sum(counts.values())

This is correct. It computes the right quantity, and at 12 qubits it works.

It is also asking the machine for a distribution over $2^{12} = 4096$ outcomes in order to extract one number.

The Arithmetic

The Sampler estimates a probability for each bitstring. To resolve the distribution well enough that the weighted sum is accurate, the number of outcomes carrying meaningful probability grows exponentially.

At 100 μs per shot, the 20-qubit row is about 17 minutes of QPU time per cost evaluation, and an optimizer needs hundreds of those.

The Estimator's cost does not depend on the qubit count at all:

$$N \approx \frac{0.96}{\epsilon^2} \quad \text{per measurement basis}$$

For $\epsilon = 0.01$ that is about 9,600 shots — regardless of whether there are 12 qubits or 120. What does grow is the number of distinct measurement bases, and for an Ising Hamiltonian that number is one: every term is a product of $Z$ operators, all of which commute qubit-wise, so a single computational-basis measurement supplies every term.

# What they should have done
from qiskit.quantum_info import SparsePauliOp

H = SparsePauliOp.from_list(ising_terms)          # 70 terms, all Z-type
prepared = prepare(ansatz, H, backend)            # the Ch. 7 checkpoint
result = estimator.run([prepared.as_pub(values)], precision=0.01).result()[0]
cost, error = float(result.data.evs), float(result.data.stds)

At 20 qubits the Estimator is roughly a thousand times cheaper. At 30, a million.

📐 Math Aside — Why the Estimator escapes the exponential.

Both approaches sample bitstrings, so where does the difference come from?

The Sampler approach estimates each $p_x$ and then computes $\sum_x p_x\, C(x)$. To get the sum right, each individual $p_x$ must be resolved, and there are $2^n$ of them. Every $p_x$ needs its own samples.

The Estimator estimates $\langle C\rangle$ directly, as the sample mean of $C(x)$ over measured bitstrings. The variance of that mean is $\mathrm{Var}(C)/N$, and $\mathrm{Var}(C)$ is bounded by the range of the cost function — which depends on the coefficients, not on the number of outcomes.

This is exactly the classical distinction between estimating a distribution and estimating a mean. Estimating the mean of a random variable never requires seeing every value it can take. The Sampler asks you to characterize the distribution; the Estimator asks the machine for the statistic you wanted.

Which also says when the Sampler is right: when you genuinely want the distribution, or when you want the mode rather than the mean. Grover and Shor return bitstrings, and a bitstring is not an average of anything.

When Each Primitive Is Correct

The decision is not about which is better; it is about what your algorithm's answer is.

The test that settles it: if you would summarize the result as a single real number, use the Estimator. If you would summarize it as "the answer is 01101," use the Sampler.

The portfolio team's answer was a cost, which is a number. They should have used the Estimator from the first line.

The Honest Postscript

Fixing the primitive rescued their implementation. It did not rescue their conclusion, and being clear about the difference is the point of this section — a team that fixes an obvious inefficiency and then declares victory has made a second mistake on top of the first.

🔬 Honest Assessment — What the fix does and does not buy.

What it buys: a cost evaluation that is affordable at 20 or 30 qubits instead of impossible. That is real and large, and it moves the bottleneck from measurement to everything else.

What it does not buy: any evidence that the quantum approach beats a classical one.

Once the measurement cost is fixed, the remaining obstacles are the ones Chapter 37 examines: the ansatz must be expressive enough to contain a good solution, the optimizer must find it through noise, the depth must fit inside the coherence budget, and — decisively — the whole thing must beat a classical solver on the same problem. For portfolio optimization at 20 variables, a classical branch-and-bound solver finds the exact optimum in well under a second.

So the correct summary is narrow and worth stating precisely: the team's implementation was needlessly expensive by a factor that grows exponentially, and fixing it makes the experiment feasible rather than successful. Feasible is a prerequisite for successful and is not the same thing.

Being able to make that distinction — "your implementation is wrong" versus "your approach does not work" — is much of what makes a quantum engineer useful rather than merely enthusiastic.

Lessons

1. Ask what your answer is. A number means Estimator; a bitstring means Sampler.
2. The Sampler's cost grows like $2^n$ when you are deriving a single quantity from a distribution. The Estimator's does not.
3. What grows for the Estimator is the measurement-basis count — and for an Ising Hamiltonian it is exactly one, because all $Z$-type terms commute qubit-wise.
4. Estimating a mean never requires resolving the whole distribution. That is the entire mathematical content of the difference.
5. The Estimator returns an error bar. Deriving one from counts is extra work you will sometimes skip, and skipping it is Chapter 5's Case Study 2.
6. Fixing an implementation is not validating an approach. Say which one you did.
7. Both primitives run and return plausible numbers. Nothing warns you; the choice has to be made deliberately, at design time.

Questions

1. Implement both approaches for a 6-qubit Ising Hamiltonian and verify they agree. Then measure the shots each needs for the same precision on the cost. What ratio do you get?

2. Extend to 10 and 14 qubits. Plot shots-to-fixed-precision against qubit count for both. Does the Sampler curve look exponential?

3. For a Hamiltonian with both $Z$ and $X$ terms, how many measurement bases does the Estimator need? Write a function that counts qubit-wise-commuting groups and apply it to a Hamiltonian of your construction.

4. Construct a problem where the Sampler is right even though the final answer is a number. (Hint: consider wanting the minimum over sampled bitstrings rather than the mean.)

5. The 📐 Math Aside claims $\mathrm{Var}(C)$ depends on the coefficient range, not the outcome count. Verify numerically: build Ising Hamiltonians at 6, 10, and 14 qubits with the same coefficient distribution and measure the variance of the sampled cost. Does it grow with $n$?

6. The team concluded "quantum optimization does not scale" from a measurement-cost problem. Write the paragraph you would send them, distinguishing what their experiment did and did not show, in a way that is useful rather than merely corrective.

7. Hardest. Suppose the cost is not a sum of Pauli terms but an arbitrary function of the bitstring — say, one with a hard constraint assigning infinite cost to invalid configurations. Can the Estimator still be used? What would you have to change about the encoding, and what does it cost? (This is a real and generally unsolved difficulty in quantum optimization; Chapter 37 §37.3 covers the standard workarounds.)