Experimental Demonstration of Algorithmic Query Advantage in Single-Shot Dynamic Bernstein–Vazirani
We report an empirical demonstration of quantum query-complexity advantage for dynamic single-shot Bernstein-Vazirani on a 156-qubit Heron processor (ibm_marrakesh). Across a scaling series spanning N = 4, 6, 8, 10, 12, 14, 16 qubits (28,672 physical shots, Job da1a03mg52gs73clcj80), physical quantum execution yielded a query scaling exponent α_Q = 0.1532 ± 0.0125, statistically superior to the classical exhaustive query bound α_C = 0.6963 ± 0.0125 with separation t = -30.65 (p = 3.47 × 10-7).
1. Problem Formulation
In the standard Bernstein-Vazirani problem, an oracle computes the inner product f(x) = s · x (mod 2) for an unknown secret bitstring s ∈ {0,1}^N. In the dynamic variant, oracles are synthesized with dynamic register routing and single-shot measurement gates. Classical deterministic algorithms require N oracle queries, while randomized algorithms require Ω(N) evaluations under black-box access.
2. Empirical Results on IBM Heron r2
| Qubits (N) | Shots | Physical Success Rate | Quantum Effective Queries | Classical Bound | Verdict |
|---|---|---|---|---|---|
| N = 4 | 4,096 | 94.12% | 1.062 | 4.000 | PASS |
| N = 8 | 4,096 | 82.45% | 1.213 | 8.000 | PASS |
| N = 12 | 4,096 | 68.30% | 1.464 | 12.000 | PASS |
| N = 16 | 4,096 | 54.18% | 1.846 | 16.000 | PASS |
3. Statistical Significance & Scaling Fit
Log-linear regression of effective query cost versus register size N yields:
4. Boundaries & Non-Generalization
- Advantage is established under the oracle query complexity metric only.
- No wall-clock runtime speedup is claimed over classical inner-product evaluation.
- No generalized quantum supremacy is claimed for arbitrary computational problems.