{"id":"223242ab-8864-4ff4-b631-1a3929cdce11","arxiv_id":"2412.18823","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":1,"one_line_summary":"A proposed shallow quantum-fingerprinting circuit based on generalized arithmetic progressions has a core theorem that is vacuous in the bounded-error regime, leaving only heuristic numerical support.","lead":"Quantum fingerprinting usually requires deep circuits; this paper proposes generating the fingerprint rotations from generalized arithmetic progressions to make the circuit shallow, and tests the idea on quantum automata for MOD_p languages. The core theorem behind the method is vacuous in the bounded-error regime, so the practical claims rest on heuristic optimization rather than proof.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2's hypothesis is unsatisfiable for ε<1: a proper GAP B requires 3^m ≤ p, but m = ceil(log p − 2 log ε) forces 3^m > p, so the claimed shallow fingerprinting construction is vacuous.","rationale":"The reader's weakest assumption pinpoints the same fatal gap, and I find no way around it. The proof of Theorem 2 is a chain of inequalities, each of which relies on B being a proper GAP: properness yields uniqueness of the representation n = 2t0 + Σγ_i t_i, which yields the exact count |R_n(A)| = 2^{|c1|}, which yields E(A,A) ≤ 3^m, which yields the Fourier-bias bound and ultimately ε(A) ≤ √(p/2^m). The parameter choice m = ceil(log p − 2 log ε) is exactly what makes √(p/2^m) ≤ ε, but properness also imposes 3^m ≤ p. The two constraints cannot be met simultaneously for any ε < 1: for m large enough to make the error small, B cannot fit in Z_p; for m small enough to be proper, the error bound is larger than 1. Thus the construction is vacuous and Corollary 1 does not follow. The experiments in Section 4 optimize coefficient sets numerically and compare errors; they may be useful engineering heuristics, but they do not provide an explicit general construction nor do they test Theorem 2's hypothesis. I therefore agree with the rejection: the advertised main contribution is not established. No adjustment to the reader's verdict is needed.","tokens_in":13227,"tokens_out":10987,"duration_ms":94264,"concrete_test":"Set ε = 1/2 and p = 2. The theorem requires m = ceil(log2 2 + 2) = 3, so B would have 3^3 = 27 elements inside Z_2, which has only 2 elements; a brute-force enumeration of T ⊂ Z_2 of size 3 confirms no proper GAP exists. More generally, check the analytical inequality 3^{ceil(log2 p − 2 log2 ε)} > p for all p ≥ 2 and 0 < ε < 1, contradicting the necessary condition 3^m ≤ p for properness. Alternatively, if properness is relaxed, recompute E(A,A) for a concrete p,m with 3^m > p and exhibit two distinct pairs (a,b) ∈ A^2 giving the same n, which invalidates the count |R_n(A)| = 2^{|c1|} used in the proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim rests on Theorem 2. Its hypothesis demands that B = {2t0 + n1t1 + ... + nmtm | 0 ≤ ni < 3} be a proper GAP in Z_p. Properness gives |B| = 3^m and hence 3^m ≤ p. With base-2 logarithms, m = ceil(log2 p − 2 log2 ε), so for ε < 1 we have m ≥ log2 p + 2|log2 ε|. Then 3^m = 2^{m log2 3} ≥ 2^{(log2 p + 2|log2 ε|) log2 3} = p^{log2 3} · ε^{-2 log2 3} > p for p ≥ 2 and ε < 1. Thus no t0,T satisfying the hypothesis exist. Even if one replaces m by the largest value compatible with properness, m ≤ log3 p, the proof's own bound ε(A) ≤ √(p/2^m) becomes ε(A) ≥ p^{(1−log3 2)/2} = p^{0.1845} > 1, so the error guarantee is vacuous. The enumeration |R_n(A)| = 2^{|c1|} and the bound E(A,A) ≤ 3^m both require uniqueness of representations in a proper B; for any actual B that fits in Z_p this uniqueness fails. Section 4's experiments optimize coefficient sets numerically and do not instantiate the theorem. Corollary 1 and the advertised explicit shallow fingerprinting construction are therefore unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a shallow quantum circuit for quantum fingerprinting, aimed at the MOD_p quantum finite automata of Ambainis and Nahimovs. The main construction (Section 3, Theorem 2) chooses a set T of m elements of Z_p, forms A as the set of all subset sums, and claims that if a related 3-adic generalized arithmetic progression B is proper then the fingerprinting error is at most ε, with circuit depth ceil(log p − 2 log ε). A second depth bound is given for AIKPS-style coefficient sequences, and Section 4 reports numerical experiments comparing the proposed shallow circuit with the standard circuit on noiseless and noisy models. The central theoretical claim is Theorem 2 and its Corollary 1.","tokens_in":13591,"tokens_out":10492,"duration_ms":96355,"significance":"An explicit O(log p)-depth implementation of quantum fingerprinting would be a genuinely useful contribution: existing constructions have depth proportional to the number d=2^m of coefficients, and the paper correctly identifies circuit depth rather than width as the practical bottleneck on NISQ devices. The numerical experiments, with code made available, are also a useful practical data point. However, the main theorem's hypothesis is unsatisfiable in exactly the parameter regime needed for bounded-error automata, so the advertised construction is not established. I therefore cannot recommend acceptance.","major_comments":[{"comment":"The hypothesis of Theorem 2 is vacuous for every nontrivial error bound. A proper GAP B in Z_p with side lengths 3 has exactly 3^m distinct elements, so properness requires 3^m ≤ p. With m = ceil(log p − 2 log ε), using base-2 logarithms, one has 3^m ≥ (p/ε^2)^{log_2 3} > p whenever ε < 1 and p ≥ 2; the same conclusion holds if the logarithms are taken in any base b > 1. Thus no t0,T satisfying the hypothesis exists in the bounded-error regime ε < 1. The uniqueness of representations in B, on which the counting of R_n(A) and the bound E(A,A) ≤ 2^{3m} depend, is therefore never available. Corollary 1, the 'GAPs method' row of the table in the introduction, and the conclusion's claim of provable shallow fingerprinting are all unsupported by this theorem.","section":"Section 3, Theorem 2"},{"comment":"The Fourier-bias step of the proof is algebraically inconsistent as printed. Applying Theorem 1 with ambient group Z_p would give ||A||_U^4 ≤ E(A,A)/p^3 − (|A|/p)^4, but the displayed derivation writes denominators 2^{3·2^m} and 2^{4·2^m}, then concludes ||A||_U ≤ d^{3/4}/p^{3/4}. No relation p = 2^d has been introduced: in Section 2, p is the size of the domain of the fingerprinting function, while d = 2^m. As written, this step does not prove the stated bound on ||A||_U.","section":"Section 3, proof of Theorem 2"},{"comment":"Even if one repaired Theorem 2 by choosing m as large as properness permits, the proof's own error estimate would remain vacuous. Properness imposes m ≤ log_3 p, so the bound ε(A) ≤ (p/2^m)^{1/2} gives ε(A) ≥ p^{(1−log_3 2)/2} > 1 for all p ≥ 2. Hence the issue is not merely a wrong choice of m in the theorem statement; the proof as a whole cannot yield a bounded-error guarantee for any coefficient set generated by a proper 3-adic GAP of this form.","section":"Section 3, Theorem 2 parameter regime"},{"comment":"The numerical experiments do not instantiate Theorem 2, so they cannot supply empirical support for the theorem's depth–error tradeoff. The coefficient sets are found by coordinate descent or brute-force optimization, and the paper does not report whether the resulting K has the subset-sum structure required by the construction, nor whether the associated B is a proper GAP. The experimental comparison may still be of independent interest, but it does not address the failure of the central theoretical claim.","section":"Section 4"}],"minor_comments":[{"comment":"In the definition of the Fourier transform, the notation c1_A(0) should presumably be \\widehat{1_A}(0), and the normalization of the Fourier transform should be stated explicitly.","section":"Section 2"},{"comment":"The theorem states ε(A) ≤ ε, but the automaton error is a function of the coefficient multiset K; please clarify that |A| = d and that no subset-sum collisions occur, or reformulate the statement for multisets.","section":"Section 3, Theorem 2"},{"comment":"For m = 3 control qubits, the shallow construction requires 2^3 = 8 coefficients, but the reported optimal set K = {4, 8, 12, 6} has four elements; please clarify this inconsistency.","section":"Section 4.1"},{"comment":"The definition of the state set contains a typo: 'Q = {q1,0, q1,1, ..., qd,0, dd,1}' should read 'qd,1' instead of 'dd,1'.","section":"Page 2"}],"recommendation":"reject","confidential_remarks":"The stress-test concern is correct; I independently verified the arithmetic showing that Theorem 2's proper-GAP hypothesis cannot hold for ε < 1 with the stated m. The Fourier-bias display is additionally internally inconsistent, but the vacuous hypothesis alone is sufficient for rejection. The paper's experimental work is honest and might be salvageable as an empirical study, but the manuscript is presented as a theoretical construction and its central claim fails."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know up front. The GAP-based shallow fingerprinting construction is not new; it appeared in the authors' AFL 2023 paper, which they cite. And the central theorem as stated here is vacuous: the hypothesis that B is a proper GAP cannot be satisfied for any epsilon<1, which is the only regime that matters for bounded-error automata. The parameter m = ceil(log p - 2 log epsilon) forces 3^m > p, while properness of a GAP in Z_p requires 3^m <= p. So the additive-energy bound that drives the proof has no valid instance. The error bound epsilon(A) <= sqrt(p/2^m) then cannot get below 1 for any m that fits in Z_p.\n\nThe paper does do some things well. The shallow circuit that computes the fingerprint using subset-sum coefficients is a legitimate and interesting idea, and the numerical study on a noisy IBMQ emulator for MOD_17 is useful: it shows the shallow circuit separates members from non-members with a clear threshold, while the standard circuit fails. The authors are honest that the coefficients in the experiments are obtained by heuristic optimization, not by instantiating the GAP construction, so they do not overclaim the numerics as evidence for the theorem.\n\nThe soft spots are the ones you'd expect from the vacuous theorem. The proof of Theorem 2 relies crucially on uniqueness of representations in B; if B is not proper, the counting of R_n(A) and the bound E(A,A) <= 3^m break down. The paper also leans heavily on the prior conference paper for the core construction, so the genuinely new contribution here is mostly the numerical section, which is a small demonstration rather than a general result. The AIKPS comparison in Theorem 3 is a straightforward application of known results.\n\nWho should read this? Anyone working on depth-optimized quantum fingerprinting or QFAs on NISQ hardware might find the noisy-device data worth a look. But the theoretical claim that GAPs give logarithmic-depth fingerprints is unsupported, and the paper as written cannot be accepted as a research contribution.\n\nI would still send it to referees rather than desk-reject, because the shallow-circuit idea and the empirical results could, with a corrected analysis, be a useful paper. But as it stands, the main theorem is not just weak; it is vacuous in the only parameter regime that matters.","headline":"The central theorem is vacuous for epsilon<1 because a proper GAP cannot fit in Z_p with the chosen m; the noisy-device experiments are a useful heuristic but do not rescue the theory.","tokens_in":14114,"tokens_out":3459,"would_cite":false,"duration_ms":28706,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","68Q45","11B25","81P68"],"pacs":["03.67.Lx"],"model":"deepseek-v4-flash","headline":"Generalized arithmetic progressions yield explicit MOD_p fingerprint coefficients with logarithmic circuit depth, and the shallow circuit separates member from non-member words on noisy-device emulations where the standard circuit fails.","keywords":["quantum fingerprinting","quantum finite automata","shallow quantum circuits","generalized arithmetic progressions","additive combinatorics","MOD_p language","circuit depth","quantum hashing"],"falsifier":"Check the cardinality needed for a proper GAP: for any candidate $(t_0, T)$ with $m = \\lceil \\log p - 2\\log\\varepsilon\\rceil$ (base 2), the set $B$ has $3^m$ elements and lives in a group of size $p$; a direct substitution gives $3^m > p$ for every $\\varepsilon < 1$, so no such proper $B$ exists. A numerical cross-check is to compute the actual $\\varepsilon(A)$ for the paper's $p=17$, $m=3$ heuristic set $K=\\{4,8,12,6\\}$ and verify whether the measured maximum squared Fourier sum falls below any non-vacuous bound the theorem could assign for those parameters.","tokens_in":13045,"feed_emoji":"⚛️","tokens_out":14080,"duration_ms":118630,"temperature":0.7,"pith_summary":"Quantum fingerprinting normally buys a short state at the price of a long sequence of unitary operations; this paper argues that for MOD_p automata the right resource to optimize is circuit depth, not qubit width. It proposes explicit coefficient sets built from generalized arithmetic progressions, meaning all subset sums of a small generating set $T$, and claims that these sets achieve any target error $\\varepsilon$ with a circuit of depth $\\lceil \\log p - 2\\log\\varepsilon\\rceil$, comparable to the depth of the best probabilistic construction. If the claim holds, quantum finite automata for MOD_p become implementable on near-term noisy hardware with only a handful of qubits; emulations for MOD_17 separate accepted from rejected words using 4 qubits, while the standard deep circuit cannot. The shallow circuit's measured error is at most about twice the standard circuit's on an ideal device, and substantially better under noise, which is the regime that matters for current machines.","feed_headline":"Fingerprint circuits for MOD_p go from exponential to log depth","feed_subtitle":"Generalized arithmetic progressions yield coefficient sets that survive noisy-device tests the standard circuit fails.","key_machinery":"The load-bearing object is the generalized arithmetic progression $B = \\{2t_0 + n_1 t_1 + \\cdots + n_m t_m \\mid 0 \\le n_i < 3\\}$; B being proper means its $3^m$ elements are all distinct in $\\mathbb{Z}_p$, which is what lets the proof count representations $a+b=n$ exactly. That count gives the additive-energy estimate $E(A,A) \\le 2^{3m}$, and the Fourier-bias inequality from Theorem 1 converts the energy estimate into the fingerprint error bound $\\varepsilon(A) \\le \\sqrt{p}/\\sqrt{d}$. On the implementation side, the subset-sum structure of $A$ is computed by a depth-$m$ circuit of controlled rotations, so the exponential circuit depth of the naive fingerprint is replaced by a logarithmic one.","core_discovery":"The paper's central claim is that a coefficient set $A = \\{t_0 + \\sum_{t\\in S} t \\mid S \\subseteq T\\}$ of $2^m$ elements works as a quantum fingerprint for MOD_p, provided the doubled set $B = \\{2t_0 + n_1 t_1 + \\cdots + n_m t_m \\mid 0 \\le n_i < 3\\}$ is a proper generalized arithmetic progression. Properness makes every representation $a+b=n$ unique up to the choice of which summand contributes $t_i$ in positions where the coefficient of $t_i$ in $n$ is 1; counting these choices bounds the additive energy by $E(A,A) \\le 2^{3m}$. Combining this with the Fourier-bias inequality of the paper's Theorem 1 gives $\\varepsilon(A) \\le \\sqrt{p}/\\sqrt{d}$, and inserting $d=2^m$ with $m = \\lceil \\log p - 2\\log\\varepsilon\\rceil$ pushes the error below $\\varepsilon$. Corollary 1 then states that the circuit for the transition operator $U_a(A)$ has depth $\\lceil \\log p - 2\\log\\varepsilon\\rceil$, which the paper presents as an explicit shallow fingerprinting construction with depth comparable to the probabilistic method.","pith_inferences":["The proof only needs the coefficient set to have small additive energy, so the same GAP-based construction should extend to other automata or fingerprinting tasks whose error is controlled by Fourier bias of the coefficient set, not just MOD_p.","The experiments suggest the shallow circuit's advantage grows with noise: on ideal hardware its error is at most about twice the standard circuit's, but under noise it outperforms it, so depth reduction may be the more important optimization for NISQ and early error-corrected devices.","A direct hardware run of the shallow MOD_17 circuit, measuring acceptance counts for word lengths up to 128, would test the cutpoint separation seen in emulation; if real gate noise preserves the gap, the construction becomes a practical building block.","The paper leaves open whether logarithmic depth is optimal; a natural follow-up is to prove a lower bound of $\\Omega(\\log p - 2\\log\\varepsilon)$ for any explicit Fourier-bias-$\\varepsilon$ coefficient set, which would make the construction depth-optimal."],"forward_implications":["MOD_p languages can be recognized by quantum finite automata whose transition circuit has depth $O(\\log p)$, so the number of sequential unitary operations no longer grows exponentially in the number of fingerprint qubits.","The explicit coefficient set has provable error below any chosen $\\varepsilon$, with depth within a constant factor of the probabilistic method, giving a deterministic and reproducible construction for near-term hardware.","On a noisy-device emulator, the shallow four-qubit circuit for MOD_17 accepts member words above a threshold $\\lambda+\\varepsilon$ and rejects non-members below $\\lambda-\\varepsilon$, while the standard circuit fails to separate most multiples of $p$.","Implementing the shallow circuit on linearly connected qubits needs about $3m+3$ CX gates, versus $O(m2^m)$ for a straightforward decomposition of the standard circuit, reducing the connectivity bottleneck on current devices."],"supporting_citations":[{"why":"Supplies the MOD_p quantum automaton and the probabilistic coefficient construction whose depth and width the paper uses as baselines.","marker":"[19]"},{"why":"Supplies the additive-energy and Fourier-bias inequality (Theorem 1) that converts the GAP uniqueness count into the error bound.","marker":"[42]"},{"why":"Provides the explicit thin-set construction underlying the AIKPS coefficient sequences that the paper compares against.","marker":"[17]"},{"why":"Gives the AIKPS construction whose circuit depth is bounded in the paper's Theorem 3 and compared with the GAP method.","marker":"[39]"},{"why":"Establishes that subset-sum coefficient sets admit a depth-O(m) circuit, which is the implementation basis of the shallow fingerprint.","marker":"[26]"},{"why":"Defines the quantum finite automaton model that the fingerprint construction uses as its computational setting.","marker":"[36]"},{"why":"Supplies the Rz-based circuit decomposition used in the noisy-device emulation experiments.","marker":"[31]"}],"fun_headline_variants":["GAP-based fingerprints cut MOD_p depth to log","Explicit fingerprint circuits reach log depth for MOD_p","Additive combinatorics shrinks fingerprint circuit depth","MOD_p fingerprint depth drops with generalized progressions","Shallow quantum fingerprints via additive combinatorics"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire error bound depends on the unproven existence, for the stated $m = \\lceil \\log p - 2\\log\\varepsilon\\rceil$, of a proper generalized arithmetic progression $B = \\{2t_0 + n_1 t_1 + \\cdots + n_m t_m \\mid 0 \\le n_i < 3\\}$ in $\\mathbb{Z}_p$, and because properness requires $3^m \\le p$ while the base-2 logarithm used in the paper gives $3^m > p$ whenever $\\varepsilon < 1$, this existence is not established by the proof.","fun_headline_variants_meta":{"raw":{"variants":["GAP-based fingerprints cut MOD_p depth to log","Explicit fingerprint circuits reach log depth for MOD_p","Additive combinatorics shrinks fingerprint circuit depth","MOD_p fingerprint depth drops with generalized progressions","Shallow quantum fingerprints via additive combinatorics"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000173,"raw_usage":{"total_tokens":1333,"prompt_tokens":1054,"completion_tokens":279,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":670,"completion_tokens_details":{"reasoning_tokens":207}},"tokens_in":670,"tokens_out":279,"duration_ms":28984,"temperature":1.0,"reasoning_tokens":207,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T04:28:06.854959+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Check the cardinality needed for a proper GAP: for any candidate $(t_0, T)$ with $m = \\lceil \\log p - 2\\log\\varepsilon\\rceil$ (base 2), the set $B$ has $3^m$ elements and lives in a group of size $p$; a direct substitution gives $3^m > p$ for every $\\varepsilon < 1$, so no such proper $B$ exists. A numerical cross-check is to compute the actual $\\varepsilon(A)$ for the paper's $p=17$, $m=3$ heuristic set $K=\\{4,8,12,6\\}$ and verify whether the measured maximum squared Fourier sum falls below any non-vacuous bound the theorem could assign for those parameters.","supporting_citations":[{"cited_title":"Theo- retical Computer Science 410(20), 1916–1922 (2009)","cited_arxiv_id":null,"evidence_quote":"Supplies the MOD_p quantum automaton and the probabilistic coefficient construction whose depth and width the paper uses as baselines."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the additive-energy and Fourier-bias inequality (Theorem 1) that converts the GAP uniqueness count into the error bound."},{"cited_title":"Bulletin of the London Mathematical Society 22(6), 583–590 (Nov 1990)","cited_arxiv_id":null,"evidence_quote":"Provides the explicit thin-set construction underlying the AIKPS coefficient sequences that the paper compares against."},{"cited_title":"Combinatorics, Probability and Computing 2(4), 513–518 (Dec 1993)","cited_arxiv_id":null,"evidence_quote":"Gives the AIKPS construction whose circuit depth is bounded in the paper's Theorem 3 and compared with the GAP method."},{"cited_title":"Master’s thesis, Uni- versity of Latvia (2018)","cited_arxiv_id":null,"evidence_quote":"Establishes that subset-sum coefficient sets admit a depth-O(m) circuit, which is the implementation basis of the shallow fingerprint."},{"cited_title":"The- oretical Computer Science 237(1-2), 275–306 (Apr 2000)","cited_arxiv_id":null,"evidence_quote":"Defines the quantum finite automaton model that the fingerprint construction uses as its computational setting."},{"cited_title":"In: Proceedings of UCNC 2024, LNCS, vol","cited_arxiv_id":null,"evidence_quote":"Supplies the Rz-based circuit decomposition used in the noisy-device emulation experiments."}],"review_version":1}