{"id":"6356b82d-f0b3-413b-a148-15b047d73aff","arxiv_id":"2607.29453","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Given a divisor q of p-1 of intermediate size, a bounded-error quantum algorithm computes n! mod p in time O~(q^c + sqrt(p/q)), breaking the square-root barrier.","lead":"A quantum algorithm is proposed that computes n! modulo a prime p in time roughly q^c + sqrt(p/q), where q is a divisor of p-1, beating the square-root barrier when q is chosen well. The core trick is a quantum method to exactly reconstruct a Jacobi sum in compact algebraic form without expanding it.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Main result hinges on unverified Biasse–Song S-unit/PIP theorems and an inexplicit balancing constant c.","rationale":"I examined the paper's internal chain: the central congruence (Appendix A), the p^2 extension (Appendix D), the reduction lemma (Lemma 2.3), the interval products (Lemma 2.4), the relative-norm equation (Step 4), and the phase-identification (Step 5). Each step is internally consistent; the Stickelberger exponents, block expansions, and harmonic-sum identities all check out. The algorithm's main vulnerabilities are external: it depends on the exact statements of Theorems 2.5 and 2.6, which are recent black-box results from a detailed version [19] that is not reproduced, and on the existence of an absolute constant c that is never made explicit. The non-explicit c prevents an actual user from choosing the balanced divisor q in Proposition 1.4, though it does not contradict the logical existence claim. Because the headline sub-square-root speedup would collapse if the black-box theorems are misstated or conditional, the reader's CONDITIONAL verdict is appropriate. I find no reason to move to ACCEPT (the external dependencies are unresolved) or REJECT (the paper's internal reasoning is sound).","tokens_in":20981,"tokens_out":34617,"duration_ms":321493,"concrete_test":"Verify Theorems 2.5 and 2.6 against the cited detailed version [19] (arXiv:2510.02280) and the SODA paper [18]: check that the S-unit group algorithm and the principal ideal algorithm are unconditional and have running time polynomial in [F:Q] and log|Δ_F|, with no hidden GRH or heuristic assumptions. If [19] is unavailable or the stated theorems do not hold as quoted, the central claim is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Theorem 1.1) relies on Theorem 1.3, whose proof invokes Theorems 2.5 (Biasse–Song S-units) and 2.6 (Biasse–Song principal ideal problem) as black boxes. The paper asserts they are unconditional and polynomial in degree and log discriminant, but does not prove or reproduce them, citing only [18,19]. If either theorem is conditional (e.g., on GRH) or has a superpolynomial hidden dependence on [F:Q], the O~(q^c) Jacobi-sum bound collapses and the balancing q≈p^{1/(2c+1)} no longer gives exponent <1/2. The paper also never makes c explicit, so Proposition 1.4 cannot be used to select the balancing divisor as described in §1.3. These are external dependencies rather than internal contradictions, but they are load-bearing: the headline sub-square-root speedup stands or falls with them.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents a bounded-error quantum algorithm that, given a prime p, a divisor q | (p-1), and an integer 0 < n < p, computes n! mod p in expected time O~(q^c + sqrt(p/q)) for an absolute constant c >= 1. When p-1 has a divisor near p^{1/(2c+1)}, the running time is p^{c/(2c+1)+o(1)} with exponent below 1/2, breaking the square-root barrier under a divisor promise. The method reconstructs the Jacobi sum J_a(chi) in compact algebraic form using Stickelberger's factorization, the Biasse-Song principal-ideal and S-unit algorithms, and Van Dam-Seroussi Gauss-sum phase estimation. It then combines the Jacobi sum with Young's p-adic congruence relating (aK)! to Jacobi sums, and with two classical interval products. A second theorem extends the bound to n! mod p^2, with the Wilson quotient as a corollary.","tokens_in":21290,"tokens_out":10621,"duration_ms":118005,"significance":"If the quoted external algorithms are correct and unconditional as stated, this is a substantial technical contribution: it gives the first sub-square-root quantum algorithm for modular factorials in the divisor-promise regime, and the exact compact reconstruction of Jacobi sums of growing order is a useful new tool. The internal reduction is coherent: the central congruences and Stickelberger factorization are proved in the appendices, and the method avoids expanding algebraic integers of enormous height. The main caveats are that the proof leans on unproved black-box theorems for unit groups, S-units, and Gauss-sum phase estimation, and that the balancing constant c is never made explicit, so the claimed speedup is partly non-effective. These concerns are load-bearing for the headline result but appear addressable within the manuscript's scope.","major_comments":[{"comment":"The proof of Theorem 1.3 (and hence Theorems 1.1–1.2) treats the Biasse–Song PIP and S-unit algorithms and the Van Dam–Seroussi Gauss-sum phase estimation as unproved black boxes. The paper asserts they are unconditional and polynomial in degree and log discriminant, citing [18,19]. These results carry the entire q-polynomial dependence in the Jacobi-sum reconstruction; if any of them is conditional on GRH or has a superpolynomial hidden dependence on [F:Q], the O~(q^c) bound and the sub-square-root exponent collapse. Please include the precise statements and hypotheses of the cited theorems, or prove the needed special cases for cyclotomic fields.","section":"§2.7, Theorems 2.5–2.7"},{"comment":"The absolute constant c in Theorems 1.1–1.3 is never made explicit. In the proof of Theorem 1.3, c is chosen larger than the fixed degrees of the polynomial bounds, but those degrees are not stated, notably for the Biasse–Song black boxes. Consequently Proposition 1.4 cannot be applied with target T = p^{1/(2c+1)}: the target itself depends on the unknown c. The balancing discussion is therefore only an existential claim, not an effective algorithm for selecting q. Make c explicit, or reformulate the theorem so that the non-effectiveness of the speedup is stated clearly.","section":"§1.1, §1.3, §4.2"},{"comment":"The exact recovery of integer exponents from numerical approximations rests on the quoted lower bound from [19, Proposition 6] that the first minimum of the logarithmic unit lattice is at least log(d/2)/(6(d/2)^4). This is a strong polynomial-in-1/d bound, stated without proof or context. If it does not hold, the rounding step and hence the whole coordinate-recovery argument fail. Please provide a proof or a complete statement of the bound, or replace this dependency by a fully specified lemma for the cyclotomic fields used here.","section":"§4.1, Step 4"}],"minor_comments":[{"comment":"The definition of K is typeset ambiguously as “K = p−1 q”; write K = (p−1)/q for clarity.","section":"§1.2"},{"comment":"The sentence following the display ends with “Breaking the square-root bound again.” with a capital B; fix capitalization and punctuation.","section":"Theorem 1.2"},{"comment":"Reference [19] is an arXiv preprint; please update it with the publication status or give the exact DOI if it has appeared.","section":"References"},{"comment":"The same symbol p is used for the rational prime and for the distinguished prime ideal p = (p, ζ_q − η). Although the context is clear, using a Fraktur symbol for the prime ideal would improve readability.","section":"§2.1"}],"recommendation":"major_revision","confidential_remarks":"The central risk is the paper's dependence on [19] for the polynomial-time S-unit and PIP algorithms, and on the non-explicit constant c. If the editor is confident that the Biasse–Song theorems are correct, unconditional, and polynomial in degree and log discriminant, the technical core is coherent and the result is likely publishable after the requested revisions. The paper's claim that all used routines are unconditional should be checked carefully against the actual statements in [19]."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a genuinely new algorithmic idea — first quantum algorithm to break the exponent-1/2 barrier for n! mod p under a divisor promise, plus a clean extension to mod p^2 and Wilson quotients — and the internal reduction is coherent. But the headline bound is hostage to two black-box theorems from Biasse–Song and to an inexplicit constant c. These are external dependencies, not flaws in the reduction, yet they should be checked before anyone builds on it.\n\nWhat's new: the move from Young's congruence to Jacobi sums, then avoiding expansion by using compact representations and reconstructing J_a(χ) via Stickelberger factorization + principal-ideal recovery + unit-group computation + phase identification, is original. The appendices give real proofs for the central congruences and the Stickelberger factorization, not hand-waving. Theorem 1.3 is a genuine contribution if it stands: polynomial dependence on both q and log p for exact compact Jacobi-sum recovery. The p^2 treatment with the harmonic term is also neat and gives the Wilson quotient as a bonus.\n\nSoft spots: (1) Steps 2, 3, and 5 rely on Theorems 2.5–2.7 as black boxes. The author asserts they are unconditional and polynomial in degree and log discriminant, but does not prove or reproduce them. If Biasse–Song's S-unit/PIP algorithm has hidden GRH-type assumptions or a superpolynomial degree dependence, the O~(q^c) Jacobi-sum bound collapses, and with it the sub-square-root conclusion. This is the load-bearing point and deserves scrutiny from someone who knows [18,19]. (2) The absolute constant c is never made explicit. The theorem says \"some absolute constant c ≥ 1,\" but choosing the balancing divisor q ≈ p^{1/(2c+1)} requires knowing c. Existence is fine for a theoretical statement, but as written the algorithm cannot actually be instantiated. (3) The exact unit-coordinate recovery also depends on a first-minimum bound quoted from [19, Prop 6]; plausible, but again not verified here.\n\nNone of this is an internal contradiction. The reduction is careful and the dependencies are named. I would send this to a serious referee: it deserves a close check of the Biasse–Song prerequisites, and the author should be asked to make c explicit or at least show how it can be computed from the proofs. Not a desk reject.","headline":"Real sub-square-root algorithm under a divisor promise, but the speedup rests on Biasse–Song black boxes and a constant c the paper never makes explicit.","tokens_in":21664,"tokens_out":3763,"would_cite":true,"duration_ms":40183,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","81P68","11T24"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims a bounded-error quantum algorithm computes n! mod p in ~O(q^c + sqrt(p/q)) when q divides p−1, breaking the exponent-1/2 barrier for modular factorials by reconstructing Jacobi sums in compact algebraic form without expand","keywords":["quantum algorithm","modular factorial","sub-square-root time","Jacobi sums","compact representation","S-unit groups","principal ideal problem","p-adic congruence"],"falsifier":"Run the exact Jacobi-sum reconstruction for a family of pairs (p,q) with q growing, e.g., q ≈ p^{1/3}, and inspect the empirical gate count of the principal-ideal, unit-group, and phase-estimation subroutines: if the count in q exceeds q^C polylog(p) for every fixed C, Theorems 1.3 and 1.1 are false. Because the paper never fixes c, the same experiment is also the only way to select the balanced divisor the algorithm promises.","tokens_in":20828,"feed_emoji":"⚛️","tokens_out":8198,"duration_ms":86217,"temperature":0.7,"pith_summary":"The paper tries to show that modular factorials n! mod p and n! mod p^2 can be computed by a quantum computer in expected time ~O(q^c + sqrt(p/q)), where q is any promised divisor of p−1 and c is an absolute constant. Because the two terms balance at q ≈ p^{1/(2c+1)}, the running time is p^{c/(2c+1)}, an exponent strictly below 1/2, breaking the square-root barrier that limits classical baby-step/giant-step methods. The key is not to multiply the n factors individually, but to relate (aK)! to K! and a Jacobi sum attached to a character of order q, then reconstruct that Jacobi sum exactly in a compact form that can be reduced modulo p or p^2. At n = p−1 modulo p^2, the method also computes the quotient ((p−1)!+1)/p mod p, which detects primes whose factorial is congruent to −1 modulo p^2. If the central claim is right, a single-input worst-case quantum algorithm can compute modular factorials sub-square-root for a positive proportion of primes.","feed_headline":"Quantum algorithm breaks square-root barrier for n! mod p","feed_subtitle":"A promised divisor of p−1 unlocks sub-square-root time for n! mod p and n! mod p^2.","key_machinery":"The carrying object is the a-fold Jacobi sum J_a(χ), an algebraic integer in the cyclotomic field of degree φ(q). Its magnitude and prime-ideal factorization are known in advance, and a p-adic Jacobi-multinomial congruence expresses (aK)! mod p as (−1)^{a−1} ρ_p(J_a(χ)) (K!)^a, where K = (p−1)/q. The load-bearing device is the compact representation: a symbolic power product of field elements with polynomial description length that stands for an algebraic number of potentially exponential height. The proof chain computes the ideal of J_a(χ), converts it to a generator via a principal-ideal routine, adjusts that generator by units so it differs from J_a(χ) only by a root of unity, identifies","core_discovery":"The paper's central claim is that a bounded-error quantum algorithm, given a prime p, a divisor q of p−1, and 0 < n < p, computes n! mod p in expected time ~O(q^c + sqrt(p/q)) for some absolute constant c ≥ 1, and that the same bound holds for n! mod p^2 uniformly for 0 ≤ n < p^2. The engine is an exact reconstruction, in compact algebraic form, of the Jacobi sum J_a(χ) for a multiplicative character of order q. The algorithm determines the prime-ideal factorization of the ideal generated by J_a(χ), finds a generator of that ideal using a principal-ideal routine, adjusts it via unit-group and relative-norm computations so it differs from J_a(χ) only by a root of unity, identifies that root b","pith_inferences":["If the exact-divisibility condition can be relaxed as the author conjectures, the same compact-reconstruction strategy would likely give a uniform sub-square-root quantum algorithm for every prime, not only those whose p−1 has an intermediate divisor; a natural test is to try shifted characters or nearby q that do not divide p−1.","The compact-reconstruction pipeline is transferable: any algebraic integer whose ideal factorization is known in a field with polynomial-size descriptions could be reconstructed and evaluated by the same principal-ideal, unit-group, and phase-identification steps, so the method may apply beyond factorial computation.","A concrete near-term experiment is to implement the central congruence and the compact-reduction step classically for small primes with q | (p−1) and compare the Jacobi-sum residue with a direct computation of (aK)!; this would validate the number-theoretic core before quantum hardware is available.","The paper leaves the constant c unspecified; identifying a concrete c from the referenced algorithms would determine whether the balanced exponent is merely below 1/2 or practically significant, and would make the divisor-search step executable."],"forward_implications":["If the central claim is correct, modular factorials n! mod p for a single input no longer need roughly sqrt(p) work whenever p−1 has a divisor of suitable intermediate size; the time exponent becomes c/(2c+1) < 1/2.","The same running-time bound applies to n! mod p^2, and at n = p−1 it computes ((p−1)!+1)/p mod p, giving a single-input test for primes with (p−1)! ≡ −1 mod p^2.","The divisor q need not be supplied by the user: factoring p−1 on a quantum computer and applying the paper's trimming argument finds a near-optimal q in polynomial time.","A positive proportion of primes have a divisor in the required intermediate range, so the algorithm is not vacuous, though the proportion is not quantified.","The compact-representation technique decouples the huge height of an algebraic integer from the cost of evaluating it modulo p or p^2, so exact algebraic reconstruction can be polynomial even when expanded representations are prohibitive."],"fun_headline_variants":["Quantum algorithm cracks n! mod p under sqrt barrier","Sub-sqrt quantum time for n! mod p with divisor promise","Quantum speedup for modular factorials: breaks 1/2 exponent","Exact Jacobi sum method gives sub-sqrt quantum n! mod p","First quantum algorithm to break sqrt barrier for n! mod p"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The whole speedup rests on three cited quantum algorithms actually running in polynomial time in the field degree q and the bit size of p, with no unproved number-theoretic hypothesis; if any one of them is slower or conditional, the claimed exponent below 1/2 collapses.","fun_headline_variants_meta":{"raw":{"variants":["Quantum algorithm cracks n! mod p under sqrt barrier","Sub-sqrt quantum time for n! mod p with divisor promise","Quantum speedup for modular factorials: breaks 1/2 exponent","Exact Jacobi sum method gives sub-sqrt quantum n! mod p","First quantum algorithm to break sqrt barrier for n! mod p"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00046,"raw_usage":{"total_tokens":2165,"prompt_tokens":796,"completion_tokens":1369,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":540,"completion_tokens_details":{"reasoning_tokens":1293}},"tokens_in":540,"tokens_out":1369,"duration_ms":11153,"temperature":1.0,"reasoning_tokens":1293,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T06:42:35.517287+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the exact Jacobi-sum reconstruction for a family of pairs (p,q) with q growing, e.g., q ≈ p^{1/3}, and inspect the empirical gate count of the principal-ideal, unit-group, and phase-estimation subroutines: if the count in q exceeds q^C polylog(p) for every fixed C, Theorems 1.3 and 1.1 are false. Because the paper never fixes c, the same experiment is also the only way to select the balanced divisor the algorithm promises.","supporting_citations":[],"review_version":1}