Case Study 1: The Search That Returned Nothing

The situation

A team implements Grover to find satisfying assignments for a small constraint problem. Sixteen-bit input space, an oracle built from the constraint predicate, and the standard iteration count:

k = int(np.floor(np.pi / 4 * np.sqrt(N)))       # N = 2**16

They test it on a problem with one known solution. It works — high success probability, the right answer, exactly as advertised.

They run it on a real instance. It returns nothing. Not a low success rate — across thousands of shots, not a single measurement satisfies the constraints. The distribution looks uniform over non-solutions.

The debugging

Their reasoning is sound and it leads nowhere.

Is the oracle wrong? They verify it exhaustively on a small instance: it marks exactly the satisfying assignments and nothing else. Correct.

Is the diffuser wrong? They check it implements $2|s\rangle\langle s| - I$ by comparing against a hand-built matrix. Correct.

Is it noise? They are on a simulator. No.

Is the circuit too deep? They check — it is large but exact, and the state vector is available. No approximation anywhere.

Every component is correct, and the algorithm returns nothing.

What was actually wrong

The real instance had three solutions, not one.

The iteration count formula is

$$k_{\text{opt}} = \left\lfloor \frac{\pi}{4}\sqrt{\frac{N}{M}} \right\rfloor$$

and they had hard-coded $M = 1$ because their test case had one solution.

Reproducing at a size that fits on a page — $N = 16$, three solutions:

   assumption        k    P(any marked)
   M = 1 (WRONG)     3           0.0000
   M = 3 (correct)   1           0.9492

Exactly zero, and here is why it is exact rather than merely small:

   M=3, N=16:  θ = arcsin(√(3/16)) = 0.447832

     k   (2k+1)θ        in units of π     sin²
     1   1.343497            0.4276π   0.949219
     2   2.239162            0.7127π   0.615967
     3   3.134827            0.9978π   0.000046

At $k = 3$ the state has rotated through almost exactly $\pi$ — landing on the unmarked axis. Every solution's amplitude is essentially zero, and a non-solution is measured with certainty.

They ran the algorithm three times longer than they should have, and three times too long is exactly half a full rotation.

Why every component test passed

Because no component was broken. The oracle was right, the diffuser was right, the circuit was right, the formula was right.

The bug was in an input to the formula — a value that was correct for the test case and wrong for the real one, hard-coded because in the test case it was obviously 1.

The general shape: a parameter that is invisible in the easy case. With one solution, $M = 1$ is so obviously right that it does not look like an assumption. It becomes an assumption only when the input changes, and by then it is a literal buried in a formula.

This is a variation on Chapter 20's promise problem, and worth distinguishing from it. There, the algorithm required a structural precondition it could not check. Here, Grover has no promise — but it needs a numeric parameter it also cannot determine on its own, and getting it wrong is worse than getting it approximately right.

The symptom is diagnostic

This failure has a signature that distinguishes it from the other common Grover bug:

"Nothing at all" points at the iteration count, not at the oracle. A broken oracle still marks something, and Grover will still amplify whatever it marked — you get a confident wrong answer, not an empty one.

The check costs two runs:

     k   P(any marked)
     1        0.9492
     2        0.6160
     3        0.0000

A small $k$ works and the computed $k$ does not. That is conclusive: the oracle is fine and the iteration count is wrong. Ten seconds, and it eliminates the four hypotheses they spent a day on.

The fix

Estimate $M$ before committing to $k$. vqelab/grover.py does this:

estimated = estimate_marked_count(n, oracle)
result = run_grover(n, oracle, assumed_M=estimated)

and the result object flags the failure when it happens anyway:

if result.marked_count_looks_wrong:
    # "success probability 0.0000 is at or below the uniform 0.0625;
    #  you assumed M=1 and the true M is 3. A wrong M rotates onto
    #  the UNMARKED axis (section 21.5)"

Estimating $M$ is a real subroutine, not a workaround. Quantum counting — phase estimation applied to the Grover operator — determines $M$ in $\mathcal{O}(\sqrt N)$, the same order as the search. It is part of the algorithm as it is actually deployed, and it is routinely omitted from tutorials because tutorials use $M = 1$.

There is also a fallback when you cannot estimate $M$: exponential search. Try $k = 1, 2, 4, 8, \dots$, checking each result classically. It costs a constant factor and removes the dependence on $M$ entirely.

The lessons

Grover has no promise but it does have a parameter, and the parameter is one the algorithm cannot determine for itself. Dropping the promise (Chapter 20) did not make Grover assumption-free; it moved the assumption from the input's structure to the input's cardinality.

A hard-coded value that is obviously correct in the test case is an assumption. $M = 1$ did not look like a choice because with one solution there was no choice. The test case hid the parameter.

"Returns nothing" is diagnostic information, not just failure. No successes at all is a different symptom from a wrong answer, and it points at a different part of the system. A broken oracle marks something; a wrong iteration count marks nothing.

Component tests cannot catch a wrong parameter. Every piece was verified in isolation and every piece was correct — this book's sixth instance of correct components composing into an incorrect system (Chapters 8, 10, 11, 13, 14, 18, and now here).

And the cheapest diagnostic is often to run the thing wrong on purpose. Two runs at $k = 1$ and $k = 2$ settled a question that four careful component verifications could not.

Reproduce it: code/example-02-wrong-marked-count.py shows the zero-success failure and the two-run diagnostic; estimate_marked_count() in code/project-checkpoint.py is the fix.