We can test the hypothesis that replacing heuristic-based distance-pattern clustering with an exact O(k^2)-bounded facial distance algorithm in QUBO-mapped network routing problems significantly reduces the qubit overhead and compilation time for planar topologies.

This discovery has a Claude-generated validation package with a full experimental design.

Precise Hypothesis

Spine & Adversarial ReadReady for validation

“This hypothesis tests whether substituting an exact O(k²) facial-distance algorithm for heuristic distance-pattern clustering in QUBO-mapped planar quantum routing reduces qubit overhead and compilation time relative to the heuristic baseline.”

• highFacial-distance shortest-path computation via planar dual graphs is a well-known technique from VLSI routing and computational geometry (decades old); the claimed 'exact O(k²) facial distance algorithm' may not be novel at all — the only potentially novel element is its application inside a QUBO formulation for quantum routing, which is a much narrower and less impactful claim than presented.
  Not resolved in this EVP due to absent literature search results. A mandatory manual/library literature review (VLSI routing, planar graph algorithms, quantum compiler SWAP-minimization literature e.g. Sabre, tket, tket's Steiner-tree routing) must be completed before any novelty claim is finalized; NOVELTY_NARROWING_REQUIRED is set true precisely because this gap is unresolved.
• highWhy is simulated annealing / generic QUBO solving chosen as the evaluation backend rather than benchmarking directly against production quantum compilers (Qiskit transpiler, tket) that already use sophisticated non-heuristic-clustering SWAP routing (e.g., SABRE, lookahead algorithms)? The chosen baseline ('heuristic distance-pattern clustering') may be a weak strawman rather than the actual state-of-the-art in quantum circuit routing, inflating the apparent improvement.
  The methodology section does not justify why k-means/greedy clustering (rather than SABRE-style lookahead or A*-based routing, which are the current de facto standards in Qiskit/tket) is the correct baseline for comparison. This is a methodology justification gap: the EVP must be revised to include a comparison against at least one production-grade routing algorithm (SABRE) to make the claim credible to hardware compiler engineers, not just against a possibly outdated heuristic.
• mediumThe claimed effect sizes (15% qubit overhead reduction, 25% compilation time reduction) are asserted without any pilot data or prior simulation evidence in the discovery description — these numbers appear to be assumed targets rather than derived from preliminary experiments, raising concern about whether the hypothesis is falsifiable in a meaningful way versus post-hoc threshold-setting.
  Acknowledged gap: the EVP's success/failure thresholds are methodologically reasonable defaults for a first validation study but are not derived from pilot data. Recommend running the Day-10 pilot checkpoint explicitly to calibrate realistic effect-size expectations before committing to the full 45-day budget, and treat the 15%/25% thresholds as provisional pending pilot results.

Experimental Protocol

ROI Projection

Implementation Sketch

# Pseudocode: comparative routing benchmark harness

for instance in benchmark_suite(planar_graphs, k_range=[20,500]):
    dual_graph = build_planar_dual(instance.embedding)

    # Exact method
    t0 = now()
    dist_exact = all_pairs_bfs_facial_distance(dual_graph)  # O(k^2)
    qubo_exact = build_qubo(instance, dist_exact, penalty_weights)
    sol_exact = solve_qubo(qubo_exact, solver=SimulatedAnnealing, seeds=10)
    t_exact = now() - t0

    # Heuristic baseline
    t0 = now()
    dist_heur = heuristic_cluster_distance(instance.embedding, method='kmeans')
    qubo_heur = build_qubo(instance, dist_heur, penalty_weights)
    sol_heur = solve_qubo(qubo_heur, solver=SimulatedAnnealing, seeds=10)
    t_heur = now() - t0

    record_metrics(instance, sol_exact, sol_heur, t_exact, t_heur,
                    metrics=['ancilla_qubits','swap_count','circuit_depth','feasibility'])

analyze:
    paired_wilcoxon(overhead_exact, overhead_heur)
    paired_wilcoxon(time_exact, time_heur)
    fit_loglog_scaling(k_values, t_exact)  # verify O(k^2)
    stratify_by_topology_family(heavy_hex, grid, synthetic)