Quantum Fourier sampling may help audit the spectral learnability of delay-based physical unclonable functions (PUFs). We ask whether that promise survives access matching, a strong classical comparator, and oracle synthesis. Three gates structure the evaluation. Structure: low degree is not small support at reachable challenge lengths; for 4-XOR at $n=14$, degree $\le d_f(0.1)$ admits $91\%$ of all $2^n$ characters and the median $90\%$-mass set spans a third of the spectrum. Algorithmics: constructing the phase oracle logically implies classical membership access, making Kushilevitz--Mansour the correct baseline; across 45 tasks it exhausts each finite domain, and no 4-XOR ideal-sampling case reaches $90\%$ mass within $2^n$ calls. A quantum-kernel diagnostic appears more favorable, with geometric difference rising to $2.151$ at $N=512$ challenges, but it correlates $0.991$ with $1/\sqrt{λ_{\min}(K_C)}$ for the classical Gram matrix $K_C$, and the 4-XOR label-complexity ratio does not exceed a balance-preserving permutation null ($p=0.930$). Trace-normalized geometric difference can therefore grow through classical ill-conditioning alone, without task-label alignment. Implementation: a simulator-validated fixed-point phase oracle based on the quantum Fourier transform admits an $18.9\%$ routed-depth reduction, yet the least certified precisions have estimated durations of $1.18$--$1.55\times$ the median dephasing time $T_2$ of the mapped qubits on a static backend snapshot, without hardware execution. We find no end-to-end advantage in the evaluated regime, although ideal sampling does use fewer coherent calls on the thresholded task. The contribution is the Three-Gate Quantum Audit Protocol: a reproducible procedure separating an ideal query advantage from a realizable security benefit. This is not a claim about deployed silicon and not an impossibility result.
Comments
Accepted for presentation as a long oral at the NeurIPS 2026 SaTQuML Workshop, December 12-13, 2026, Atlanta, GA. arXiv version includes minor formatting revisions to meet submission requirements
Quantum Fourier sampling may help audit the spectral learnability of delay-based physical unclonable functions (PUFs). We ask whether that promise survives access matching, a strong classical comparator, and oracle synthesis. Three gates structure the evaluation. Structure: low degree is not small support at reachable challenge lengths; for 4-XOR at n=14, degree ≤df(0.1) admits 91% of all 2n characters and the median 90%-mass set spans a third of the spectrum. Algorithmics: constructing the phase oracle logically implies classical membership access, making Kushilevitz--Mansour the correct baseline; across 45 tasks it exhausts each finite domain, and no 4-XOR ideal-sampling case reaches 90% mass within 2n calls. A quantum-kernel diagnostic appears more favorable, with geometric difference rising to 2.151 at N=512 challenges, but it correlates 0.991 with 1/λmin(KC) for the classical Gram matrix KC, and the 4-XOR label-complexity ratio does not exceed a balance-preserving permutation null (p=0.930). Trace-normalized geometric difference can therefore grow through classical ill-conditioning alone, without task-label alignment. Implementation: a simulator-validated fixed-point phase oracle based on the quantum Fourier transform admits an 18.9% routed-depth reduction, yet the least certified precisions have estimated durations of 1.18--1.55× the median dephasing time T2 of the mapped qubits on a static backend snapshot, without hardware execution. We find no end-to-end advantage in the evaluated regime, although ideal sampling does use fewer coherent calls on the thresholded task. The contribution is the Three-Gate Quantum Audit Protocol: a reproducible procedure separating an ideal query advantage from a realizable security benefit. This is not a claim about deployed silicon and not an impossibility result.
We present ThylerSpectral-Audit-Q, a three-layer automated diagnostic framework for quantum kernel pathologies, validated across 124 configurations spanning 7 data domains plus a systematic six-family quantum kernel survey: tabular (digits, diabetes, California housing, covtype), clinical (Iris, Wine, Breast Cancer), quantum-native (V0/V1 ZZFeatureMap, V2 IQPFeatureMap), molecular graph (MUTAG, PTC_FM), industrial (semiconductor proxy, Steel Plates Faults, satellite proxy), time series (AR2, ECG5000 via ZZFeatureMap, QHMM, and TSHK kernels). The kernel survey applies six encoding families (PauliFeatureMap, AngleEncoding, AmplitudeEncoding, EfficientSU2, RandomCircuitKernel, QFTFeatureMap) to three tabular benchmark datasets at n ∈ {4, 6, 8}. Contribution 1 — Diagnostic framework. Three sequential layers — exponential concentration (EC) detection (Shannon effective rank ratio r_eff; five-tier spectral taxonomy), dequantization filter (Tang-Chia eigenvalue truncation), and kernel-target alignment evaluation (centered KTA) — combine into a composite PROCEED/CAUTION/ABORT Spectral Health Card. All four primary datasets (breast cancer, make_moons, Iris, Wine) yield ABORT or CAUTION verdicts under ZZFeatureMap. The framework generalizes: IQPFeatureMap reproduces EC_COLLAPSE at n=8 (r_eff=0.943) without recalibration. A data-kernel structural sensitivity is also detected: the same kernel yields LIKELY_DEQUANTIZABLE on molecular graph data (r_eff=0.153) versus CONFIRMED_DEQUANTIZABLE on tabular data (r_eff=0.095) — a distinction invisible to kernel architecture inspection alone. Contribution 2 — Advantage regime, retired at n_train=150 (v19). At n_train=50, Hamming Quantum Kernel (HQK) on quantum-native data produced the paper's only non-ABORT signal: large effect sizes over SVM-Linear on V2 (IQPFeatureMap) data (d=+0.949–1.015; under the corrected resampled t-test for repeated-CV dependence, p_NB=0.0605 for λ=0.5 and p_NB=0.0485 for λ=0.1 — marginal). Because the pre-registered robustness criterion required corrected significance in both λ configurations, a recovery experiment at n_train=150 was pre-registered (exploracion_010) and has now been executed (S052). Result: every V2 effect size reverses sign — λ=0.5: d=−0.215 (p_NB=0.6375, ns); λ=0.1: d=−1.243 (p_NB=0.0189 — a significant disadvantage, HQK now performing worse than SVM-Linear/RBF) — and the pre-registered effect-size-floor control (d≥0.5 in both λ, designed to distinguish gradual collapse from sign reversal) fails in both configurations. The secondary same-architecture V0/V1 arm also reverses sign (d=+0.27→−0.374 vs Linear, ns). Per the pre-registered decision rule, the cross-architecture advantage claim is retired, not restored. This converges with exploracion_012's finding that V6 — a circuit verified diagonal-unitary by construction but structurally distinct from V0/V1/V2's ZZ/IQP coupling — also shows significant disadvantage at n_train=150 (d=−1.10 to −1.13, p_NB<0.05 in both λ): at the matched n_train=150 standard, no HQK configuration tested in this paper shows a robust advantage over classical baselines. The dual concentration bottleneck — global EC (fidelity collapse) and local EC (Pauli-Z observables ⟨Z_i⟩→0 as n increases) — disables both fidelity kernels and projected quantum kernels simultaneously, and this negative result is now the paper's consistent empirical picture rather than a partial exception to it. A complementary negative structural result: exhaustive hyperparameter optimization over ZZFeatureMap (63 grid configurations: γ × reps × entanglement, plus 100-step continuous variational search) on classical time series data (AR2_n4, r_eff=0.2975) finds zero configurations with Δ_kta > 0 in full audit, confirming that quantum-native data is a necessary but not sufficient structural condition for any advantage signal under the full three-layer audit within the ZZFeatureMap family. The D6 kernel survey further shows that K2 (AngleEncoding) achieves Δ_kta>0 on classical tabular data, but is blocked from PROCEED by the dequantization filter, confirming that Layers 1–2 are essential to prevent false PROCEED verdicts. Contribution 3 — Quantum kernel phase diagram. The 124 audited configurations form a quantum kernel phase diagram in (r_eff × Δ_acc × n_qubits) space with two robustly confirmed empirical phases (ABORT, CAUTION) and measurable phase boundaries, plus a third, provisional phase (PROCEED, 7/124 configs) that has not been re-verified at the n_train=150 standard that retired Contribution 2 above. Seven geometric patterns are observable, including a cross-domain discovery: the STRUCTURED_LOW_RANK regime (0.10 < r_eff ≤ 0.35) appears independently in molecular graph data (r_eff ∈ [0.036, 0.312]) and industrial quality-control data (r_eff=0.22), despite no domain relationship — a finding invisible to kernel architecture inspection alone. Contribution 4 — Domain-agnostic spectral classification. A k-nearest-neighbor classifier trained exclusively on spectral audit features achieves F1-macro=1.000 and MCC=1.000 on an external test set of 20 configurations from three entirely unseen domains: molecular graphs, industrial QC, and time series. Random Forest feature importance reveals dataset_type_code=0% — the framework's diagnostic accuracy is domain-invariant by construction. To the best of our knowledge, ThylerSpectral-Audit-Q is the only pre-execution diagnostic tool integrating EC detection, dequantization filtering, and structural alignment evaluation into a single automated pipeline with an empirical multi-domain phase diagram, validated across 124 configurations spanning 7 data domains and a systematic six-family quantum kernel survey.
The Quantum Fourier Transform (QFT) uses O(n2) gates against the O(NlogN) operations of the Fast Fourier Transform, but this advantage is contingent on state preparation, readout, connectivity, decoherence, and on the classical algorithm chosen for comparison. We introduce the Quantum Fourier Advantage Index (QFAI), a task-, data- and reference-aware resource metric combining state preparation, task-dependent readout, native transpiled gate counts on real coupling maps, and a two-term calibrated noise model with relaxation. The QFAI is a conditional estimate of accessible advantage under stated input-access, task, reference-algorithm and stochastic-noise assumptions, not an intrinsic property of the QFT, and we separate asymptotic, resource-accounting and wall-clock advantage throughout. Across 9 datasets and 7 processors, the conventional dense-FFT reference yields broad windows on all-to-all hardware (peak QFAI 37.68, Quantinuum H2). Two findings qualify this. First, under a common synthetic noise convention and once SWAP-routing permutations are excluded from the measured infidelity, the gate-error amplification constant is modality-independent ( κg=0.786 , 0.778, 0.770); against per-qubit calibration snapshots of 4 real IBM processors it spans 0.349 to 0.769 and must be refitted per device. Second, replacing the dense FFT by the task-matched classical algorithm, a sublinear sparse FFT for dominant-mode extraction, reduces the peak to a near-break-even 0.17, whose sign reverses within a factor-of-two change of the unmeasured sparse-FFT constant; we prove this ratio is bounded by a constant, so no asymptotic separation exists, and we propagate fit, calibration and reference uncertainties into explicit bands. A 6G OFDM channel-estimation case study, an end-to-end model of the quantum processing pipeline rather than a measured receiver, shows the framework as a design tool: the quantum route recovers delay taps with precision up to 1.00 yet misses the 125.00μs slot deadline by five to eleven orders of magnitude, with the per-shot cost of state loading, reset and readout, not gate fidelity, the binding constraint, while a measured single-core dense FFT meets it at N≤4096 . All results are simulation-based, with stated evidence tiers and a released hardware-validation campaign.
Quantum predictive advantage under shift usually requires known target labels. We derive the assumption-free sharp identified interval for the finite-batch advantage of a fixed candidate over the best member of a prespecified fixed classical-kernel family under any bounded loss and unrestricted completions of the unaudited labels; zero-one accuracy has exact closed-form partial-label updates. Across eight security shifts, zero-label upper endpoints against 115 classical kernels span 0.002-0.088. Retrospective auditing reduces every endpoint to 0.010 with 0-33 of 500 labels, including entangling-ZZ models. Prospective corroboration on two eligible tasks met predefined criteria: four task-classifier medians require 0-3 labels (overall median 0; maximum 76), and all 20 realized effects are negative; a third task fails its feature gate. Protocol controls reverse an apparent advantage, while finite-shot noise can increase predictive distinctness without useful advantage. The framework separates protocol validity, target predictive indispensability, and quantum relevance.
Hardware noise and finite sampling perturb the fidelity estimates forming a quantum-kernel Gram matrix. We measured how far three hardware-reconstructed Gram matrices depart from an exact statevector reference for one frozen four-qubit ZZ feature map on N=24 indoor air-quality windows, executed on ibm_fez at 1024 shots per circuit in three single, non-interleaved jobs: baseline, dynamical decoupling alone, and gate twirling alone. All were complete, finite, and positive-semidefinite. Off-diagonal root-mean-squared error (RMSE) against the reference was 0.0878, 0.0864, and 0.0427; full-matrix centered kernel alignment (CKA) ranged 0.933-0.989 and the post hoc diagonal-excluded (U-centered) CKA 0.816-0.986. The gate-twirled job deviated least on every reported geometry axis; its baseline contrasts are deletion-stable for the Spearman, mean-absolute-error, RMSE, and full-matrix CKA diagnostics, while the Pearson and diagonal-excluded contrasts fall just below that convention. Dynamical decoupling was not separated from the baseline. The observed error exceeded both finite-shot reference scales, so, under those sampling-only models, sampling does not explain it. Centered kernel-target alignment did not track reconstruction fidelity and stayed at or below each label-permutation reference: implementation fidelity and task relevance are distinct diagnostic axes. All configuration-level statements describe three realized jobs on one backend; no mitigation-efficacy, classifier-superiority, forecasting, or quantum-advantage claim is made.
The Quantum Pi Benchmark (QPB) is a family of verification, search, counting, frequency-estimation, and collision tasks over the digits of Pi. It is designed as an architecture-neutral specification of mathematically fixed instances, classical comparators, resource boundaries, and admissible claims. The specification fixes zero-based indexing, binary and hexadecimal digit conventions, dense and sparse candidate domains, and task-specific payloads for target-bearing and collision problems. It separates three independent properties that benchmark descriptions can conflate: digit access (lookup or direct), oracle-construction provenance (P0–P4), and controller blindness (B0 or B1). A non-total capability grid retains codes R0–R12 as stable claim labels while stating their named dependencies; a higher-numbered code does not automatically inherit every lower-numbered capability. The evidence protocol requires pre-execution validation, routed-resource accounting, preservation of raw outcomes, outcome-independent eligibility, visible conditioning, uncertainty estimates, protocol separation, and formal record freezing. Collision scaling is stated as a heuristic candidate-domain model: birthday behavior gives D_h = Θ(16^(h/2)), while element distinctness gives O(D_h^(2/3)) coherent queries only under declared access and memory assumptions. These query bounds do not establish the earliest repeat, a quantum frontier, or end-to-end advantage. Frontier status depends on a current classical post-hoc resource audit; advantage requires a predeclared matched cost comparison that includes preparation, oracle construction, error correction, sampling, readout, and verification. The resulting framework classifies future Pi-derived experiments without importing device-specific performance into the foundational definition.
We construct a classical oracle proving that, in a relativized setting, the set of languages decidable by an efficient quantum verifier with a quantum witness (QMA) is strictly bigger than those decidable with access only to a classical witness (QCMA). The separating classical oracle we construct is for a decision problem we coin spectral Forrelation -- the oracle describes two subsets of the boolean hypercube, and the computational task is to decide if there exists a quantum state whose standard basis measurement distribution is well supported on one subset while its Fourier basis measurement distribution is well supported on the other subset. This is equivalent to estimating the spectral norm of a "Forrelation" matrix between two sets that are accessible through membership queries.
Our lower bound derives from a simple observation that a query algorithm with a classical witness can be run multiple times to generate many samples from a distribution, while a quantum witness is a "use once" object. This observation allows us to reduce proving a QCMA lower bound to proving a sampling hardness result which does not simultaneously prove a QMA lower bound. To prove said sampling hardness result for QCMA, we observe that quantum access to the oracle can be compressed by expressing the problem in terms of bosons -- a novel "second quantization" perspective on compressed oracle techniques, which may be of independent interest. Using this compressed perspective on the sampling problem, we prove the sampling hardness result, completing the proof.