PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Owen Friedewald, Ali Shiri Sichani, Chi-Ren Shyu

arXiv:2610.02636v1quant-phcs.CRcs.LG

TL;DR

The paper asks whether quantum Fourier sampling can audit delay-PUF models once access is matched, a strong classical comparator is used, and phase-oracle implementation is accounted for. It evaluates those questions through structural, algorithmic, and implementation gates, finding no end-to-end advantage in the measured regime while identifying an ideal-query advantage in finite experiments.

  • Problem

    It is unclear whether quantum Fourier sampling’s promise for delay-PUF auditing survives access matching, strong classical comparison, and phase-oracle implementation.

    Source: §1 · p. 2

  • Method

    The Three-Gate Quantum Audit Protocol tests spectral support, compares Fourier sampling with an access-matched Kushilevitz–Mansour baseline, and evaluates reversible-oracle implementation.

    Source: §1 · p. 2, §3.2 · p. 4, §3.3 · p. 5

  • Results

    No end-to-end advantage is established in the evaluated regime, although ideal Fourier sampling uses fewer coherent calls in the finite experiments.

    Source: §5 · pp. 7–8, §7 · p. 9

  • Takeaways & Limitations

    The protocol separates an ideal query advantage from a realizable security benefit for the measured delay-PUF models and access assumptions.

    Source: §7 · p. 9

    The numerical conclusion is limited to the measured models and access assumptions; no QPU was executed and the result is not a general lower bound on quantum learning.

    Source: §6 · p. 9

Abstract

from arXiv · show

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{\lambda_{\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.

1 Introduction

Quantum Fourier sampling offers a spectral audit for delay-PUF models, but its promise must survive access matching, a strong classical baseline, and oracle implementation. The paper organizes that test into structural, algorithmic, and implementation gates.

1 Introduction

  • The phase oracle provides stronger access than CRPs, while support enumeration is weaker than the best classical membership-query baseline.These mismatches motivate using a classical heavy-Fourier algorithm with membership access when assessing the quantum sampler.Source: §1 · p. 2
  • The central question is whether quantum Fourier sampling remains advantageous after matching access, comparing against a strong classical algorithm, and accounting for phase-oracle implementation.The three gates test spectral support, an access-matched classical comparator, and whether a reversible oracle preserves the audit signal at compatible routed cost.Source: §1 · p. 2
  • The paper packages its audit as the Three-Gate Quantum Audit Protocol, combining access-matched Kushilevitz–Mansour comparison, finite-n support analysis, kernel-conditioning controls, and fixed-point oracle costs.The introduction reports that no end-to-end advantage is supported in the evaluated regime, although ideal Fourier sampling uses fewer coherent calls in the finite experiments.Source: §1 · p. 2
  • Earlier work adapted the Linial–Mansour–Nisan low-degree algorithm to PUF attacks, while this paper tests whether its finite-regime support is small enough for a quantum audit.The related-work discussion also cites the LMN algorithm [14], XOR-arbiter learnability analysis, the LMN scale derived by Ganji et al. [7, Corollary 1], and PUFmeter.Source: §1 · p. 2

2 Setting and access model

The setting is uniform-challenge additive-delay APUFs and their XOR constructions, with simulator parity checked against pypuf. Access distinctions matter: the synthesized coherent oracle is available only from a designer-held model and implies classical membership access.

2.1 Additive-delay PUFs

  • An x-XOR PUF is the product of x halfspace-valued APUFs, analyzed under uniform challenges with Fourier coefficients satisfying Parseval’s identity.The challenge-to-suffix map is an invertible triangular linear map over F2, so it permutes Walsh characters and preserves coefficient magnitudes.Source: §2.1 · pp. 2–3
  • Matched APUF, 2-XOR, and 4-XOR simulator instances reproduce pypuf responses, quality metrics, and logistic-regression attack accuracy, validating implementation parity rather than silicon fidelity.The authors explicitly distinguish this cross-check from validation of the additive model as a complete model of silicon.Source: §2.1 · p. 3

2.2 Access is part of the problem

  • Synthesizing the coherent phase oracle from a known, simulatable delay model logically grants classical membership access, but does not equate classical and quantum query complexity or runtime.A fabricated arbiter chain has no coherent-challenge interface; the paper therefore frames its quantum object as a design-time model audit, not an attack speedup against deployed PUFs.Source: §2.2 · p. 3

3 Decision gates

The decision gates test whether spectral concentration is operationally sparse, whether quantum recovery beats an access-matched classical baseline, and whether a reversible oracle meets accuracy and device-resource criteria. The protocol treats gate outcomes separately: an upstream measurement can remain informative even when a later gate fails.

3.1 Concentration with its denominator

  • The structural gate evaluates the degree region and smallest target-mass set against the full subset lattice, rather than treating low degree alone as sparse support.The section numerically evaluates degree and mass-based support for multiple n and XOR sizes; a supplied passage notes the formal support bound is n^O(x^2/ε^2) when the degree is much smaller than n.Source: §3.1 · p. 3

3.2 Access-matched algorithms

  • The ideal Fourier sampler applies the phase oracle between Hadamard layers, sampling character S with probability equal to its squared Fourier coefficient.Its timing excludes oracle synthesis, fault-tolerant overhead, and state preparation.Source: §3.2 · p. 4
  • Kushilevitz–Mansour recursively estimates Fourier energy below prefixes and prunes low-energy prefixes using membership queries, providing the access-matched classical comparator.The study scores threshold-heavy characters and exact mass-carrying sets; the ideal sampler receives a deliberately generous 2^n-call budget, and model evaluations are not converted into coherent calls.Source: §3.2 · p. 4
  • The kernel diagnostic compares trace-normalized classical and quantum Gram matrices before fitting labels, then assesses label-specific complexity against a predeclared kernel suite and balance-preserving permutation control.The geometric-difference bound is label-independent; the label-complexity ratio is an in-sample diagnostic, not held-out accuracy.Source: §3.2 · p. 4

3.3 A reversible sign oracle and approximation criteria

  • The reversible sign oracle accumulates quantized delays with a QFT constant-adder chain, uses the most significant bit for phase kickback, and inverts workspace preparation to clean ancillas.The implementation is tested on basis states and compared with the exact Walsh spectrum; resource estimates use a fixed backend coupling and calibration snapshot without QPU execution.Source: §3.3 · p. 4
  • Implementation passes only when phase and uncomputation are exact on ground-truth tests and some precision meets both task-error and device budgets; duration/T2 is a warning, not a success probability.The audit separately specifies finite-distribution and model-independent precision criteria, and pre-registers mass targets, support limits, query budgets, claimed advantage, and device resources.Source: §3.3 · p. 5
  • A failed gate blocks an end-to-end advantage claim but does not invalidate measurements from earlier gates.The protocol applies structural and algorithmic tests before requiring implementation accuracy and a target-device resource budget.Source: §3.3 · p. 5

4 Results

Across the four results subsections, low-degree support remains broad at measured challenge lengths, and access-matched spectral recovery does not establish a quantum advantage. Kernel and oracle-implementation checks likewise leave practical advantage unsupported in the evaluated regime.

4.1 Low degree is not small support at reachable n

  • At n = 14, 4-XOR degree at most 9 admits 91.02% of characters, while its median 90%-mass set occupies 32.90% of the spectrum.At n = 18, median degree-support fraction is 88.11% for both 4-XOR and 8-XOR; the cited asymptotic scale supplies no useful finite-n sparsity certificate at these parameters.Source: §4.1 · p. 5

4.2 Access-matched threshold and mass recovery

  • Across 45 rows, KM recovers every threshold-heavy character in 44 nonempty rows, but every row queries all 2^n challenges at least once.The median thresholded set has four characters for 4-XOR and carries 6.5% of its spectrum.Source: §4.2 · p. 5, Table 2 · p. 6
  • No 4-XOR row reaches 90% Fourier mass within its 2^n ideal-call budget; the median 90%-mass set across 45 rows has 400 characters, with KM median recall of 4.1%.The median ideal first passage among rows that reach 90% mass is 2,041 calls; classical evaluations and coherent calls remain separate resources.Source: §4.2 · p. 5

4.3 Kernel diagnostics under conditioning and permutation controls

  • At n = 16, median best gCQ rises from 1.118 at N = 32 to 2.151 at N = 512, but the cited diagnostic is substantially conditioning-driven.Quantum Gram matrices remain close to identity at N = 512 while the selected classical suffix-RBF matrices do not.Source: §4.3 · p. 6
  • For 4-XOR, the observed median sC/sQ is 1.156, below the balance-preserving permutation-null median of 1.176 (upper-tail p = 0.930).Across 15 rows per construction, median sC/sQ is 0.608 for APUF and 0.995 for 2-XOR; degree-6 structured parity is the best classical kernel in every 4-XOR row.Source: §4.3 · p. 6

4.4 Oracle precision and cost on the target snapshot

  • Across 81 matched cases, exact line-QFT reduces median routed native-gate depth by 18.9% relative to full QFT, but the least certified precisions have estimated durations of 1.18–1.55T2.Only (n, p) = (8, 7) passes the finite audit gate; no tested precision passes at n = 10 or 12.Source: §4.4 · pp. 6–7
  • The smallest evaluated oracle requires about 7 × 10^4 constructive T gates at δ = 10^-3 before repeated Fourier samples are counted.These are per-oracle-call constructive logical estimates, not optimized lower bounds, physical gate counts, or a fault-tolerant runtime.Source: §4.4 · p. 7

5 Discussion

The three-gate audit finds no end-to-end advantage in the evaluated regime: favorable kernel diagnostics do not establish task-specific quantum alignment, and signal-preserving oracle precision reaches the snapshot’s coherence scale. The discussion frames the protocol as a way to distinguish ideal query advantages from realizable benefits.

Implementation gate

  • Signal-preserving precision arrives only when median circuit duration reaches or exceeds mapped median T2, and the sweep involved transpilation without backend execution.The tested signal-preserving oracle precisions exceed the snapshot’s coherence scale in estimated duration.Source: Figure 2 · p. 8, §5 · p. 8

Kernel gate

  • The kernel gate fails after controls: geometric difference grows with an ill-conditioned classical direction, while above-one 4-XOR label ratios are typical under balance-preserving permutations.The authors say these diagnostics do not isolate task-specific quantum alignment.Source: §5 · p. 8
  • When a trace-normalized quantum Gram matrix is near identity and a classical Gram matrix has a small eigenvalue, gCQ can grow without task-label alignment.The proposed diagnostics are to report λmin(KC), ridge sensitivity, and a label-permutation control rather than rely on gCQ alone.Source: §5 · p. 8

Scope

  • The ideal sampler uses fewer coherent calls than KM uses distinct model evaluations on the threshold-heavy task, but this does not establish that every classical algorithm matches Fourier sampling query for query.The authors note that fault-tolerant hardware, a lower-depth sign oracle, or a genuinely sparse spectrum could change the Fourier-audit conclusion.Source: §5 · p. 8

Protocol scope

  • Extending the audit to other Boolean PUFs requires a declared challenge distribution and representation, measured spectral support, access-matched baselines, and a separately validated reversible oracle.The XOR concentration argument does not automatically extend to other constructions, and the numerical verdicts do not transfer without evaluation.Source: §5 · p. 8

Security interpretation

  • The oracle is a designer-side diagnostic because synthesizing it requires the known model; the audit code can also assist classical modeling when that model is available.It does not create coherent access to silicon.Source: §5 · p. 8

6 Limitations

The experiments and conclusions are bounded by simulated models, finite evaluation settings, and a static hardware snapshot. The authors identify further validation needed before making claims about fabricated-device populations or broader quantum-learning settings.

Experimental scope

  • The experiments use additive-delay APUF and XOR-APUF simulations under uniform challenges, not measurements of inter-die process or environmental behavior.The simulator’s deterministic instances quantify seed-to-seed dispersion but do not estimate a fabricated-device population.Source: §6 · pp. 8–9

Kernel and label-complexity scope

  • The geometric diagnostic covers five pools and a declared classical suite, while the in-sample minimum-complexity comparison is not held-out accuracy or independent model selection.The permutation control tests label specificity conditional on the observed pools and suite, not population-level generalization.Source: §6 · p. 9

Algorithmic and implementation scope

  • KM exhausts finite domains, so the study makes no empirical claim about its asymptotic query efficiency.Ideal Fourier timing omits fault-tolerant and oracle costs; the snapshot duration/T2 ratio is not a noise simulation or fidelity prediction, and no QPU was executed.Source: §6 · p. 9

Future validation

  • Post-silicon validation would require measured CRPs with disjoint fitting and evaluation challenges, held-out devices for population claims, and repeated measurements across operating conditions.The study also calls for separating response noise from model mismatch and testing audit stability under measured uncertainty.Source: §6 · p. 9

Resource and diagnostic scope

  • The logical Clifford+T estimate uses uniform synthesis-error allocation without jointly optimizing rotations, and is not a surface-code resource estimate or forecast of fault-tolerant feasibility.The geometric difference is an upper bound sensitive to small eigenvalues; the 4-XOR median ratio provides no label-specific positive result against its balance-preserving null.Source: §6 · p. 9

7 Conclusion

For delay-PUF auditing, none of the three criteria establishes practical advantage in the measured regime. The authors present the protocol as a reusable evaluation tool and specify what future positive claims should report.

Conclusion

  • None of the three criteria establishes practical advantage in the measured regime: spectra are not sparse at reachable n, kernel diagnostics fail conditioning and permutation controls, and signal-preserving arithmetic exceeds the snapshot’s coherence scale.Coherent access remains designer-only, with KM as the access-matched classical baseline.Source: §7 · p. 9
  • The Three-Gate Quantum Audit Protocol is presented as a reusable evaluation tool for secure and trustworthy QML.The authors frame reporting the diagnosed negative outcome as part of that contribution.Source: §7 · p. 9
  • Future positive results should state their access class, include concentration denominators, connect kernel geometry to task labels, and budget for the oracle physically.Source: §7 · p. 9

A Proof of Proposition 1

The proof bounds high-degree Fourier mass by coupling inputs that differ through independent bit flips and applying a noise-stability bound. A choice of flip probability then yields a degree scale and a formal support bound.

Proof of Proposition 1

  • Couple u and uδ by independently flipping each input bit with probability δ; a product change implies that at least one factor changed.Source: A Proof of Proposition 1 · p. 11
  • Choosing δ = 1/(2d) for d ≥ 1 and applying the preceding equations gives the stated high-degree bound.The argument uses the noise-stability bound for weighted majority and a universal constant C.Source: A Proof of Proposition 1 · p. 11
  • Setting the bound to ε yields the stated degree scale and, for fixed d relative to n, the formal support bound n^O(d).No clipping operation is used, so the degree conclusion is preserved.Source: A Proof of Proposition 1 · p. 11

B Oracle derivation and validation

The oracle uses QFT addition and phase kickback to implement the suffix-parity sign, with an accumulator-width bound preventing modular overflow from changing that sign. Simulator tests validate challenge phases, clean ancillas, edge cases, and the resulting Walsh spectrum before hardware-facing code is admitted.

B Oracle derivation and validation

  • QFT addition applies a Fourier-basis phase, while controlled rotations encode the challenge-dependent arithmetic and a sign kickback marks negative suffix parity.Inverting the arithmetic returns the accumulator and kickback ancilla to zero.Source: B Oracle derivation and validation · p. 11
  • An accumulator-width bound prevents modular overflow from changing the sign encoded by the oracle.Source: B Oracle derivation and validation · p. 11
  • Simulator tests check every small-example basis state, quantized challenge phases, clean ancillas, constant-response and overflow cases, and the final exact Walsh spectrum.Source: B Oracle derivation and validation · p. 11
  • The weighted-comparator alternative receives statevector tests only through n=3; its n=8 result is transpilation-only because workspace grows rapidly.Source: B Oracle derivation and validation · p. 11

C Experimental protocol and provenance

The experimental record ties manuscript results to committed generators and records run provenance, while describing the construction-level IQRs as dispersion rather than population confidence intervals. The reported work used CPU-only runs and no GPU or QPU.

C Experimental protocol and provenance

  • Each result JSON records its arguments, Git SHA, worktree status, timestamp, seeds, and package versions; Table 5 maps results to committed generators.Source: C Experimental protocol and provenance · p. 12
  • Challenge pools are sampled without replacement, and sample-complexity runs enforce max(Ntrain)+Ntest ≤ 2^n/100, requiring n≥20 on the default grid.Source: C Experimental protocol and provenance · p. 12
  • Source code, evidence JSONs, pinned requirements, reproduction commands, and a deterministic hash manifest are available in an anonymous reproduction archive.Source: C Experimental protocol and provenance · p. 12
  • The Table 6 IQRs describe dispersion across 15 rows for n=10, 12, and 14 with five PUF instances per n, not population confidence intervals.Source: Table 6 · p. 12
  • The reported sweeps used CPU-only resources, and no GPU or QPU was used for the paper's results.The precision-frontier and mass-audit jobs completed within their stated allocations; peak memory was not retained for the precision-frontier job.Source: C Experimental protocol and provenance · p. 12
  • The released code is MIT-licensed; listed external software includes Qiskit and Qiskit IBM Runtime under Apache 2.0 and pypuf under GPLv3.Source: C Experimental protocol and provenance · p. 12
Loading 2610.02636v1…