Case Study: Grover on a Real Scheduling Problem

Executive Summary

A logistics company wants to assign 20 deliveries to 4 vehicles subject to capacity and time-window constraints. The search space is $4^{20} \approx 1.1\times10^{12}$. Grover promises $\sqrt{N} \approx 10^{6}$ iterations against a trillion classical checks — a million-fold improvement.

This case study builds the oracle honestly, discovers the constraint checker costs ~2,400 two-qubit gates, and finds that the resulting circuit needs $2.4\times10^{9}$ coherent operations. Then it does the comparison that actually decides the question: against a classical constraint solver, which does not enumerate the space at all.

The conclusion is negative, and the reasoning is the transferable part — it generalizes to nearly every combinatorial-optimization proposal.

Skills applied

• Encoding a constraint-satisfaction problem for a quantum oracle (§13.16).
• Estimating oracle gate cost from constraint structure.
• Comparing against the correct classical baseline, not brute force.
• Recognizing when structure defeats the premise of unstructured search.

Phase 1: Encode the problem

20 deliveries, 4 vehicles → 2 bits per delivery → 40 qubits for the assignment register.

Constraints: - Capacity: each vehicle's total load ≤ 1,000 kg (4 constraints) - Time windows: each delivery within its vehicle's shift (20 constraints) - Route feasibility: each vehicle's total driving time ≤ 8 hours (4 constraints)

The oracle must compute all 28 constraints reversibly and flip the phase iff all are satisfied.

Phase 2: Cost the oracle

Plus roughly 120 ancilla qubits for accumulators and flags, bringing the register to ~160 qubits.

Phase 3: The full circuit

Assume 5,000 satisfying schedules exist among $1.1\times10^{12}$ — a plausible density for a lightly constrained instance. Then

$$k_{\text{opt}} = \frac{\pi}{4}\sqrt{\frac{1.1\times10^{12}}{5{,}000}} \approx \frac{\pi}{4}\times 14{,}832 \approx 11{,}650 \text{ iterations}$$

Each iteration costs the oracle plus diffusion (~500 gates on 40 qubits):

$$11{,}650 \times 6{,}260 \approx 7.3\times10^{7} \text{ two-qubit gates}$$

All sequential, all coherent.

On NISQ hardware: fidelity $\approx (1-0.007)^{7.3\times10^7} \approx e^{-511000}$. Zero, by an unimaginable margin.

With error correction: 160 logical qubits at ~1,000 physical each is 160,000 physical qubits — plausible for the 2040s. At $10^{-6}$ s per logical two-qubit gate, runtime is $7.3\times10^{7}\times10^{-6} \approx 73$ seconds. That is genuinely fast.

So on a mature fault-tolerant machine, the quantum approach solves it in about a minute.

Phase 4: The comparison that matters

Now the classical baseline — and this is where the analysis turns.

Nobody solves vehicle routing by enumerating $4^{20}$ assignments. A modern constraint solver or MIP solver (OR-Tools, Gurobi) exploits the structure: constraint propagation prunes the space, branch-and-bound eliminates whole subtrees, and problem-specific heuristics find good solutions immediately.

Measured on this instance class: 0.3 seconds on a laptop for a feasible solution, a few seconds for a proven optimum.

The quantum approach is 240× slower than a laptop, and requires hardware that does not exist.

The error in the original framing. The million-fold speedup was measured against brute force. But brute force is not the classical algorithm — it is the classical strawman. Grover's $\sqrt N$ is over the unstructured search space, and the whole reason classical solvers are fast is that the space is highly structured.

Phase 5: Why the structure argument is fundamental

This is not a matter of constant factors that better engineering will fix.

Grover treats the oracle as a black box. It cannot exploit the fact that violating a capacity constraint on vehicle 2 tells you something about millions of related assignments — a classical solver propagates that inference immediately and prunes them all. Grover must still amplitude-amplify through them.

BBBV proves no quantum algorithm beats $\sqrt N$ given only black-box access. But the classical solver does not have black-box access — it can see inside the problem. Grover's optimality is a statement about a weaker model than the one classical algorithms actually use.

The corollary: Grover's quadratic advantage is real only where classical algorithms are also reduced to brute force — genuinely unstructured problems. For structured combinatorial optimization, decades of classical algorithm engineering already beat brute force by many orders of magnitude, and that head start is far larger than quadratic.

Phase 6: What to tell the company

Do not pursue this. The quantum formulation is correct and would work on hardware two decades away, at which point it would still lose to a laptop running software available today.

If quantum is strategically interesting, look elsewhere: quantum simulation for materials or chemistry (Chapter 17), where the classical baseline is genuinely exponential and there is no structure to exploit classically, is the area with a defensible long-term case.

And check the classical solver first, always. In this instance the fastest path to value was a better classical formulation — the team had not tried a commercial solver before proposing a quantum computer.

Discussion Questions

1. The original pitch compared Grover against brute force. Name three other quantum claims you have seen that use a strawman baseline.
2. Grover is provably optimal for black-box search yet loses to a classical solver here. Explain why both statements are true.
3. Under what conditions on constraint density would Grover become competitive? Is that regime realistic?
4. The oracle cost 5,760 gates, dominated by arithmetic. What would make an oracle cheap, and which problems have such oracles?

Your Turn: Extensions

• Build a toy version — 6 deliveries, 2 vehicles, one capacity constraint — and run Grover in simulation.
• Implement the same instance in OR-Tools and time it.
• Estimate the gate cost of a reversible 10-bit adder and verify the oracle's cost breakdown.
• Find the crossover: at what problem size does Grover's $\sqrt N$ overtake a solver whose runtime grows as $1.05^n$?

Key Takeaways

• Grover's speedup is quadratic over unstructured search; the correct classical baseline is the best structured solver, not brute force.
• Realistic constraint oracles cost thousands of two-qubit gates, and the cost is dominated by reversible arithmetic.
• The full circuit here needs $7\times10^{7}$ sequential coherent operations — fault-tolerant only, and even then slower than a laptop.
• BBBV's optimality applies to black-box access; classical solvers see inside the problem, which is a strictly stronger model.
• Combinatorial optimization is the most over-proposed quantum application. Simulation, where the classical baseline is genuinely exponential, is the defensible one.