Case Study 1: The Algorithm That Answered a Question Nobody Asked

The setup

A team is evaluating quantum computing for a classification problem. They have a function — a scoring rule, several hundred lines of ordinary code — and a question about it: is this function biased? Specifically, does it return positive on roughly half its inputs, or is it lopsided?

Someone recognizes the shape. Constant or balanced. That is Deutsch–Jozsa, exactly, and Deutsch–Jozsa solves it in one query against a classical worst case of $2^{n-1}+1$.

For their 24-bit input space that is one query against 8,388,609.

They build it. The oracle is substantial work — Chapter 19's reversibility problem, ancillas, uncomputation — but it compiles, it runs, and it returns an answer:

   P(all zeros) = 0.0000  ->  BALANCED

Their function is balanced. Clean, deterministic, one query. Exactly as advertised.

The problem

Their function is not balanced. They check classically, on a sample, and it returns positive about 61% of the time.

The algorithm did not malfunction. The circuit was correct, the oracle was correct, the measurement was correct. Deutsch–Jozsa answered the question it was asked, and the question it was asked was "given that this function is constant or balanced, which is it?"

Their function is neither. That case is not in the algorithm's domain, and its behaviour there is undefined — not "wrong," not "approximate," but outside the specification entirely.

What the output actually looked like

Reproducing the failure at a size that fits in a simulator — $n = 4$, an oracle that returns 1 on exactly one input of sixteen:

   oracle                              P(all zeros)    standard rule
   constant (promise holds)                  1.0000         CONSTANT
   balanced (promise holds)                  0.0000         BALANCED
   marks ONE input (promise BROKEN)          0.7590         BALANCED   <- wrong

0.7590 is neither 1 nor 0, and the standard two-way decision rule — all zeros means constant, anything else means balanced — resolves it to "balanced" because the only alternative it knows about is "constant."

The information was in the output the whole time. Count distinct outcomes over 2000 shots:

   constant           1 outcome     {'0000': 2000}
   balanced           1 outcome     {'0110': 2000}
   promise broken    16 outcomes    {'0000': 1518, '0110': 40, '1111': 37, ...}

Both valid promises produce exactly one outcome. A constant function gives all-zeros with probability 1. A balanced function gives the single mask that defines it, also with probability 1.

A violated promise produces a spread, and at $n = 4$ that means all sixteen outcomes — 76% on all-zeros and a long thin tail across everything else.

The team collapsed a sixteen-outcome histogram into one scalar, applied a two-branch rule to it, and got a confident answer.

The missing branch

if   p_all_zeros > 0.99:    verdict = "constant"
elif p_all_zeros < 0.01:    verdict = "balanced"
else:                       verdict = "PROMISE VIOLATED"      # <- this one

Three lines instead of two. vqelab/algorithms.py implements this, and one of its tests asserts that the honest rule disagrees with the naive one on a broken oracle — which is the whole content of this case study, encoded so it cannot be lost.

There is a second, stronger check available in a test harness:

check_promise(truth_table, "deutsch-jozsa")
# -> (False, "neither: f is 1 on 1 of 16 inputs (need 0, 8, or 16)")

Brute force, exponential, and exactly the work the algorithm exists to avoid. A test harness can afford it at small $n$; the algorithm cannot afford it ever. That asymmetry is the point.

Why this was an easy mistake

The pattern-match was correct. "Constant or balanced" really is Deutsch–Jozsa's problem, stated in its own words. Recognizing it was good work.

The promise is stated as a premise, not a requirement. Textbook presentations open with "suppose $f$ is either constant or balanced" — which reads as scene-setting rather than as a precondition the caller must establish. It is easy to absorb the algorithm without absorbing that the supposition is load-bearing.

And nothing enforced it. No error, no warning, no flag. Chapter 19's oracle construction happily implements any predicate you hand it; the algorithm happily runs on any oracle.

The general shape: an algorithm with a precondition that cannot be checked from inside it. Deutsch–Jozsa cannot verify its promise because verification requires examining $f$ on exponentially many inputs — precisely the cost the algorithm exists to avoid. The precondition is imported from outside, and its correctness is the caller's responsibility.

What they should have done

Check the promise at small $n$ before scaling. Their function was available classically. Brute force at $n = 8$ or $n = 12$ costs nothing and would have shown a 61/39 split immediately.

Look at the distribution, not the scalar. One outcome versus sixteen is unmistakable, requires no extra runs, and was already in the data they had.

And ask whether the promise is a property of the problem or an artifact of the algorithm. "Is my function biased?" is a real question. "Is my function constant or balanced, given that it is one of those?" is a different question that happens to have a fast quantum answer. They are not the same question, and the second one is rarely the one anyone has.

The lessons

A promise problem's promise is a precondition, not a description. "Suppose $f$ is constant or balanced" is a requirement on the input, and violating it puts you outside the specification — where behaviour is undefined rather than merely inaccurate.

Algorithms with unverifiable preconditions need external verification. If the check is exponential and the algorithm is not, the check has to happen somewhere else: in a test harness, at small scale, or in an argument about why the promise holds structurally.

Add the third branch. A two-way decision rule on a three-way world will always answer, and will be wrong exactly when the third case occurs.

Read the distribution, not the scalar you reduced it to. This is Chapter 12 §12.6's lesson in a new setting — there, four missing outcomes named a stuck qubit; here, a long tail names a broken assumption. In both cases the scalar summary discarded the diagnosis.

And check whether the problem you have is the problem the algorithm solves. Pattern-matching a problem onto an algorithm's statement is not the same as matching it onto the algorithm's domain, and the gap between them is where the promise lives.

Reproduce it: code/example-03-broken-promise.py runs all three oracles and both decision rules; check_promise() in code/project-checkpoint.py is the brute-force verification.