Where Quantum Fourier Sampling Stops Short: A Three-Gate Audit Protocol for Delay-PUF Security Models

Owen Friedewald; Ali Shiri Sichani; Chi-Ren Shyu

quant-phOct 2, 2026

Where Quantum Fourier Sampling Stops Short: A Three-Gate Audit Protocol for Delay-PUF Security Models

Authors: Owen Friedewald, Ali Shiri Sichani, Chi-Ren Shyu

Organizations: Department of Electrical Engineering and Computer Science University of Missouri, Columbia, MO, USA

Abstract

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.

Figures & tables

Resource	Realizable holder	Required comparator
Observed CRPs	passive or protocol-level attacker	tuned supervised learner
Classical membership $f(c)$	chosen-challenge user or model holder	KM/Goldreich–Levin family
Coherent phase $O_{f}$	reversible designer-held model only	Fourier sampling with full oracle cost

Table 1: Access-matched comparison. Query counts are meaningful within a row, not across physically different resources.

Figure 1: Finite- $n$ concentration sweep with 30 deterministic seeded PUF instances per cell. Lines are medians and shaded bands are interquartile ranges across instances. Left: the fraction of all $2^{n}$ characters admitted by degree $\leq d_{f}(0.1)$ . Right: the fraction needed to accumulate $90\%$ Fourier mass. For higher XOR counts, both denominators remain large rather than shrinking toward a sparse audit target.

	$\|H_{.01}\|$	mass $(H_{.01})$	KM mass	QFS mass	$\|H_{.9}\|$	KM recall $H_{.9}$
APUF	11	.727	.735	.935	89	.157
2-XOR	15	.403	.445	.890	716	.032
4-XOR	4	.065	.123	.832	1,415	.0065

Table 2: Threshold and Fourier-mass recovery, medians over 15 rows per construction. “QFS mass” uses the fixed

2^{n}

ideal-call budget; Table 6 gives interquartile ranges.

H_{.01}

contains characters with power at least

0.01

;

H_{.9}

is the smallest set carrying

90\%

mass.

Gate	Evidence	Verdict
Structure	4-XOR at $n=14$ : median $d=9$ covers $91.02\%$ ; heavy set is $32.90\%$	No
Algorithmic: Fourier	$\|H_{.9}\|$ median 400; KM recall $4.1\%$ ; 4-XOR QFS never reaches $90\%$ mass	No cheap recovery
Algorithmic: kernel	$g_{CQ}$ tracks conditioning ( $r=.991$ ); 4-XOR permutation $p=.930$	No label-specific evidence
Implementation	exact oracle; estimated durations at certified precisions exceed median $T_{2}$	Snapshot warning; no QPU execution

Table 3: Decision-gate summary. “No” means unsupported in the measured regime, not a universal impossibility theorem.

$n$	$p$	qubits	arbitrary $R_{z}$	CNOT	$T$ , $\delta=10^{-3}$	$T$ , $\delta=10^{-6}$
8	7	20–21	806–1,074	985–1,177	79,550	113,948
10	5	20–21	630–814	769–925	69,768	101,048
12	6	24	1,046–1,072	1,165–1,185	94,514	136,434

Table 4: Logical resources at the least model-independently certified precisions, over three PUF instances.

T

columns are median constructive estimates for whole-oracle synthesis error

\delta

Figure 2: Precision and resource tradeoffs over three PUF instances and three transpiler seeds per point; accuracy is worst-instance and routed cost is the median. “Frozen gate” denotes a criterion fixed before the sweep. Dashed lines show these thresholds. Signal-preserving precision arrives only after median circuit duration reaches or exceeds mapped median

T_{2}

. Transpilation only; no backend execution.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Result	Generator	Evidence JSON
Concentration	sweep_concentration.py	phase0_concentration_sweep.json
KM versus QFS	benchmark_fourier_audits.py	phase1_findings.json
Kernel geometry	measure_geometric_difference.py	phase1_findings.json
Kernel labels	measure_label_kernel_complexity.py	phase1_findings.json
Oracle comparison	compare_e2_oracles.py	e2_oracle_comparison_findings.json
Weighted comparator	compare_e2_oracles.py	weighted_probe.json

Appendix

Table 5: Machine-readable evidence used in the paper.

	$\|H_{.01}\|$	mass $(H_{.01})$	KM mass	QFS mass	$\|H_{.9}\|$	KM recall $H_{.9}$
APUF	11–13	.687–.748	.715–.769	.928–.946	74.5–182	.069–.195
2-XOR	12–18.5	.385–.453	.414–.508	.876–.901	272–1,672.5	.011–.098
4-XOR	3.5–7.5	.044–.124	.076–.177	.825–.841	406.5–4,732	.0020–.038

Appendix

Table 6: Interquartile ranges corresponding to the construction-level medians in Table 2 . Each range is descriptive dispersion over 15 rows spanning

n\in\{10,12,14\}

and five PUF instances per

n

, not a population confidence interval.

Algorithmic Auditing

Algorithmic auditing evaluates whether automated systems are fair, reliable, robust, compliant, and accountable in their intended settings.

See all 143 papers

Jul 13, 2026

Overcoming Fourier Locking in Quantum Data Re-uploading Classifiers via Spectral Homotopy

Data re-uploading parameterized quantum circuits (DRU-PQCs) are universal function approximators, yet their expressivity produces oscillatory, non-convex loss landscapes that resist gradient-based optimization. We show that the primary optimization bottleneck in DRU-PQCs is not insufficient capacity but a structural failure mode we term Fourier locking (FL): because encoding weights and entangling layers are nonlinearly coupled, random initialization on high-frequency targets collapses the encoding parameters into spurious local minima. Two Fisher diagnostics characterize FL. The input-space quantum Fisher information

F_x

measures the effective frequency content of the encoded state; the Fisher discriminant ratio of the measured features measures their alignment with the class labels. In two independent 50-seed experiments, the locking is literal: trapped circuits hold

F_x

frozen for the entire run, while escaping circuits migrate their frequency content (direct training:

r_{pb} = -0.48

; curriculum:

d = 1.34

; both

p < 0.001

). The replicated signature is this spectral mobility, not any endpoint value of

F_x

, and trapped circuits retain a fully non-degenerate parameter-space QFIM (

r_{pb} \approx 0

): the failure is spectral misalignment of a responsive state, not a loss of geometric sensitivity. A frequency-staged homotopy protocol that paces the target frequency (

f: 1.0 \to 3.0

) convexifies the early loss landscape; escaping circuits raise

F_x

in step with the curriculum, and the escape rate triples (18% vs. 6%). Fourier locking is a frequency-alignment problem, and its remedy is frequency pacing.

Spencer Topel

Moth, Brooklyn, New York

Quantum Machine Learning Variational Quantum Circuits Quantum Circuit Trainability Quantum Data Encoding

Ask PDF

Sep 29, 2026

Advantage of Sample Complexity in Quantum PAC Learning Requires Inverse Access to State-Preparation Unitaries

Whether quantum computation can reduce the amount of data required for conventional machine learning is a central problem in quantum machine learning. In probably approximately correct (PAC) learning, a learner receives training examples sampled from an unknown probability distribution. Quantum PAC learning extends this framework by allowing access to quantum examples, which are quantum states that coherently encode this distribution, or to unitaries that prepare quantum examples, with or without inverse access. When only copies of quantum examples are available, the optimal worst-case sample complexity asymptotically matches that of classical learning. In contrast, access to both a preparation unitary and its inverse can improve the accuracy dependence of query complexity. However, it has remained open whether access to the preparation unitary alone suffices for this improvement. In this work, we resolve this question by determining the optimal query complexity with forward-only access, taking the worst case over compatible preparation unitaries and their dimensions. In both realizable and agnostic PAC learning, this complexity matches, up to constant factors, the optimal sample complexity achievable with classical examples or copies of quantum examples. To prove these results, we construct, for any algorithm with forward-only access, a simulator that approximates the algorithm's Haar-averaged output state using as many copies of the prepared state as the algorithm makes queries. These results show that inverse access is essential for the known improvement in accuracy dependence in this worst-case setting. Beyond PAC learning, our reduction provides a general tool for transferring lower bounds for state copies to query lower bounds for forward-only access to the corresponding preparation unitaries.

Natsuto Isogai, Satoshi Yoshida, Mio Murao

Department of Physics, Graduate School of Science, The University of Tokyo, Tokyo, Japan

Sample Complexity Quantum Machine Learning

Ask PDF

Aug 12, 2026

A Quantum/Classical Example Oracle Separation for Making Things Up

Consider two PAC learning algorithms, both having access to quantum computation, but differing in the types of examples they obtain: one is provided with classical samples, while the other is given quantum samples. Are there any learning tasks that can be efficiently performed by the latter, but not by the former? This question, the focus of our work, is surprisingly still open. Our main result is to show that relative to an oracle, there are distributions that can be efficiently generated by a quantum learner with access to quantum samples, but not by a quantum learner with access to only classical samples, making progress to answering this question in the affirmative.

Kenny Chen

The University of Sydney

Quantum Machine Learning PAC Learning

Ask PDF

Abstract

Algorithmic Auditing

Explore similar work

Overcoming Fourier Locking in Quantum Data Re-uploading Classifiers via Spectral Homotopy

Advantage of Sample Complexity in Quantum PAC Learning Requires Inverse Access to State-Preparation Unitaries

A Quantum/Classical Example Oracle Separation for Making Things Up