Compiler-Enabled Quantum Query Advantage for Candidate-State Search on Physical Quantum Hardware
We report an empirical demonstration of compiler-enabled quantum query advantage for software-repair candidate-state search on a 156-qubit superconducting quantum processor (ibm_marrakesh). Across 9 frozen instances drawn from 7 distinct programming language ecosystems at N=4, N=8, and N=16, physical quantum execution under a strictly verified black-box oracle model achieved lower effective verifier queries than the classical expected black-box search cost across 9/9 individual cases and 3/3 problem sizes. At N=16, the 95% Wilson confidence interval upper bound on effective quantum queries (7.360) remains strictly below the classical expected baseline of 8.5 queries. All protocol specifications, pre-execution fairness audits, raw execution bitstrings, and adversarial independent audits are published under open science principles.
1. Research Question
Can authentic search state spaces derived by a software-repair compiler participate in a bounded quantum query advantage experiment on physical quantum hardware without ground-truth leakage or side-channel rank bias?
While theoretical quantum search algorithms (such as Grover's algorithm and amplitude amplification) guarantee asymptotic query speedups on unstructured databases, real-world compilation pipelines often introduce heuristic ordering or structural correlations that could trivialize classical search if exposed. This work evaluates whether a rigorous black-box search interface preserves demonstrable quantum query advantage on physical NISQ hardware when operating on real-world compiler outputs.
2. Q-Psi State-Space Compiler
The Q-Psi compiler translates discrete multi-file software bug state spaces into structured candidate subspaces. In this experiment, candidate sets of size N ∈ {4, 8, 16} were extracted from 9 real software repair problems spanning Python, Go, Java, Rust, TypeScript, PHP, Ruby, and C/C++.
3. Why Black-Box Fairness Matters & Pre-QPU Correction
In our initial v1.0 design, candidate state indices correlated with compiler rank scores, creating potential side-channel information. An independent adversarial audit identified this issue before physical hardware execution.
Protocol v1.1 resolved this vulnerability by enforcing:
- Deterministic answer-independent candidate permutations (seeded by candidate hashes).
- Strictly opaque candidate IDs (0 to N-1) presented symmetrically to classical and quantum arms.
- 100.0% mechanical truth-table verification between classical and quantum oracle evaluators.
4. Physical IBM Quantum Execution & Frozen Protocol
Execution was performed on IBM Quantum's 156-qubit Heron processor, ibm_marrakesh, under runtime Job ID da1c7rkdedkc73eqs5mg. Each of the 9 frozen circuits was executed with 2,048 physical shots (18,432 physical shots total).
5. Experimental Results
| Problem Size (N) | Qubits | Grover k | Physical P_succ | Quantum Q_eff | Classical Q_class | Advantage | Verdict |
|---|---|---|---|---|---|---|---|
| N = 4 | 2 | 1 | 97.09% | 1.030 | 2.500 | 2.43x | PASS |
| N = 8 | 3 | 2 | 77.08% | 2.595 | 4.500 | 1.73x | PASS |
| N = 16 | 4 | 3 | 41.99% | 7.144 | 8.500 | 1.19x | PASS |
Note: Classical baseline Q_class = (N+1)/2 represents the exact expected number of black-box verifier queries for classical random sampling without replacement. Quantum effective queries Q_eff = k / P_succ.
6. Statistical Confidence Analysis
At N=16, physical measurement yielded 2,580 successful shots out of 6,144 total shots (P_succ = 41.99%). The two-sided 95% Wilson score confidence interval is [40.76%, 43.23%]. Inverting this interval yields a 95% confidence bound on effective quantum queries:
Because 7.360 < 8.5, the frozen statistical decision gate is fully satisfied.
7. What This Demonstrates & What It Does NOT Demonstrate
- Compiler-enabled quantum query advantage on physical superconducting hardware.
- Opaque black-box verifier contract integrity without ground truth leakage.
- Advantage across 9/9 individual cases and 3/3 problem sizes up to N=16.
- No end-to-end wall-clock speedup over classical computers.
- No general computational supremacy or commercial advantage.
- No advantage over every structure-aware heuristic algorithm.
8. Evidence & Reproducibility
9. Citation
@techreport{qpsi2026compilergrover,
title = {Compiler-Enabled Quantum Query Advantage for Candidate-State Search on Physical Quantum Hardware},
author = {{Q-Psi Research Team}},
institution = {Q-Psi Independent Quantum Research, The Oneness Project},
year = {2026},
month = {August},
number = {QPSI-NOTE-2026-02},
url = {https://qpsi.vercel.app/research/compiler-grover-query-advantage}
}