{"id":"448ca948-1977-4ec6-a0c6-49f3fe20b908","arxiv_id":"2412.12558","paper_version":4,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A new quantum factoring circuit factors P^2 Q integers with near-linear gates and sublinear qubits and depth, for a class believed classically hard.","lead":"This paper presents a compact quantum circuit that factors numbers of the form P^2 Q using far fewer qubits and less depth than prior factoring algorithms. If correct, it provides a practical, classically verifiable proof of quantum power for a class of integers believed hard for classical computers.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Classical hardness of N = P^2 Q with Q small is an unproven premise: if a classical attack beats the NFS for log Q = Θ(n^{2/3}), the 'classically-hard factoring' and proof-of-quantumness claims collapse, though the circuit theorems remain valid.","rationale":"I read the full manuscript. The main theorems (Theorem 3.1, Theorem 4.1, Corollary 4.7) are internally consistent: the Gauss-sum analysis is detailed, the Jacobi circuit's streamed-block construction is reversible and its space/depth accounting is coherent, and the special-integer reduction in Section 5 is correct. The approximate QFT error and the external trace-distance lemma are minor unquantified gaps but do not threaten the Ω(1) success probability. The only load-bearing vulnerability is external: the classical hardness of the N = P^2 Q family with small Q is asserted on the basis of a literature survey and explicitly left as future work. The reader identified the same weakest assumption, and I agree. Since the paper transparently conditions its significance claims on this premise and the technical contribution is sound, the verdict remains ACCEPT (UNCHANGED).","tokens_in":35645,"tokens_out":19874,"duration_ms":164302,"concrete_test":"Run the lattice-based factoring algorithms of Boneh-Durfee-Howgrave-Graham (CRYPTO 1999) and Coron et al. (CT-RSA 2016), adapted to the regime r=2, q small, on N = P^2 Q with log Q = n^{2/3} for n = 512, 1024, 2048, and compare empirical scaling to the number field sieve baseline exp(Õ(n^{1/3})); if any attack's time grows as exp(o(n^{1/3})), the hardness premise is falsified.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that the Jacobi factoring circuit yields a sublinear-space proof of quantumness depends on the premise that factoring n-bit integers N = P^2 Q with log Q = Θ(n^a), a ∈ (2/3,1), is classically infeasible. The paper's support (Section 2.3 and the Introduction) is a survey of known algorithms: ECM and Mulder's squarefree-decomposition method run in exp(O(√(log Q))), which for a > 2/3 is asymptotically slower than the number field sieve, and lattice attacks in [BDH99, CFRZ16] are argued not to apply to the small-Q regime. Yet the paper concedes 'there has been little classical cryptanalysis for factoring integers of the specific form we consider,' and no lower bound rules out a specialized attack. If such an attack exists, the 'classically-hard factoring problem' and the proof-of-quantumness application collapse, although the circuit resource theorems (Corollary 4.7) would remain true as unconditional algorithmic results.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper gives a quantum circuit for factoring integers of the form N = P^2 Q with near-linear gate count and, when log Q is polynomially smaller than log N, sublinear space and depth. The authors first refine the LPDS squarefree-decomposition algorithm so that the initial superposition only needs to range up to poly(B_max), then build a space-efficient quantum circuit for computing Jacobi symbols when the modulus N is classical and much larger than the superposition input x, and finally give a black-box reduction showing that any squarefree-decomposition algorithm completely factors integers whose prime exponents are distinct. The paper also discusses applications to classically-verifiable proofs of quantumness.","tokens_in":35829,"tokens_out":28145,"duration_ms":252310,"significance":"If the results are correct, Corollary 4.7 is the first polynomial-time quantum factoring circuit with sublinear qubit count for a class of integers for which no faster classical algorithm is currently known. The Jacobi-symbol algorithm in Section 4 is of independent interest and is stated with explicit, parameterized resource bounds. The proof structure is largely rigorous: Theorem 3.1 carries out a careful trace-distance and Gauss-sum analysis, Lemmas 4.2--4.4 verify the blockwise reduction underlying the Jacobi circuit, and Theorem 5.3 is a clean black-box reduction. A particular strength is that the authors are explicit about the main unproven premise: the classical hardness of N=P^2Q with small Q is supported only by a survey of known algorithms and is flagged as an open direction.","major_comments":[{"comment":"The proof of Theorem 3.1 analyzes the state after an exact QFT, but the efficiency paragraph specifies that the circuit uses Coppersmith's o(1)-approximate QFT. Since the near-linear gate count depends on using the approximate QFT (an exact QFT would cost O(ell^2) gates and break the main claim), the proof must explicitly argue that the o(1) approximation error changes the final measurement distribution by o(1) in total variation distance, so the Omega(1) success probability is preserved. The argument is standard, but it is currently omitted.","section":"Section 3, Algorithm 3.1 / Theorem 3.1"},{"comment":"The claims that N=P^2Q with log Q = Theta(n^{2/3}) is a 'classically-hard factoring problem' and that the circuit yields the first factoring-based proof of quantumness with sublinear space rest on an unproven, nonstandard hardness assumption. The paper's own survey concedes that there has been little classical cryptanalysis of this specific form. Please state the required assumption explicitly as a conjecture (e.g., no classical polynomial-time algorithm factors such N with non-negligible success probability), and qualify the proof-of-quantumness statements as conditional on that conjecture. The unconditional circuit-resource theorems should be separated from the application claim.","section":"Abstract, Section 2.3, Corollary 4.8"},{"comment":"Lemma 4.4 notes that s can be negative, but Step 4 of Algorithm 4.1 feeds s to an m-bit Jacobi-symbol subroutine that is normally specified for nonnegative inputs. The text should clarify how negative s is represented in the quantum registers and reduced modulo x' before the subroutine is invoked, or the algorithm should be modified to guarantee s >= 0. The asymptotic resource claims survive if modular reduction is included, but the current description is ambiguous on a point that is central to the construction.","section":"Section 4, Algorithm 4.1 / Lemma 4.4"}],"minor_comments":[{"comment":"The displayed trace-distance bound has a confusing square-root/fourth-root expression. Please state the exact form of [Che24, Lemma 2.11] being used and show the chain of inequalities, since the current notation suggests sqrt(||u-v||^2/||u||^2) while the final bound is a fourth root of a ratio of squared norms.","section":"Section 3, proof of Lemma 3.3"},{"comment":"The algorithm requires m | n and its loop range presupposes n >= 2m. Please state how arbitrary m is handled via padding or restriction, so that the corollaries are unambiguously valid for all stated parameter ranges.","section":"Section 4, Theorem 4.1 / Algorithm 4.2"},{"comment":"The recursion formula m_i = m_{i-1}/d with m_1 = n/d appears inconsistent as written: after one step m_2 would already be smaller than d when d is, say, n^{2/3}. Please correct or clarify the recurrence and the stopping condition for the claimed depth/space tradeoff.","section":"Remark 5"}],"recommendation":"major_revision","confidential_remarks":"This is a solid algorithmic paper, and I do not see circularity in the use of [RV24, Lemma A.2] and [KMY24] as building blocks. The main risk is overclaiming the proof-of-quantumness application: the classical hardness of N=P^2Q with small Q is a genuine, largely unstudied assumption, and the paper should present it as a named conjecture rather than as an established fact. Please also ensure that the approximate-QFT error in Theorem 3.1 is addressed explicitly before the paper is accepted, since the near-linear gate count relies on that approximation."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The key thing to know: this is a real algorithmic advance, not hype. The Jacobi symbol circuit in Section 4 — reversed long division starting from the LSB, streaming through classical bits of N in blocks, tracking only O(m) qubits — is genuinely new and cleanly presented with correctness lemmas. The reduced-superposition analysis of LPDS12 (Theorem 3.1) is also new and necessary for the sublinear-space claim. Section 5's reduction from squarefree decomposition to complete factorization of 'special' integers is a neat observation, with proper credit to Yun's polynomial analogue. I came away convinced the circuit complexity claims are internally consistent: ~O(n) gates, ~O(n/m + m) depth, ~O(m) qubits for the Jacobi unitary, hence ~O(n^{2/3}) space and depth for N = P^2 Q with log Q = Θ(n^{2/3}). The pseudocode is concrete enough to implement, and the proofs go through.\n\nThe soft spots are real but proportionate. The biggest is one the authors themselves flag: the proof-of-quantumness framing depends on the assumption that no classical algorithm exploits small Q to beat NFS in the log Q = Θ(n^{2/3}) regime. That is an unproven premise, and the authors candidly admit 'there has been little classical cryptanalysis for integers of the specific form we consider.' If a specialized classical attack ever appears, the applications collapse — but the circuit theorems survive as unconditional statements. The paper would be just as valuable framed purely as a circuit-complexity result, and I'd encourage the authors to keep the caveat prominent.\n\nTwo minor technical gaps. First, the correctness proof of Theorem 3.1 uses an exact QFT while the circuit implements Coppersmith's approximate QFT; the approximation error is not tracked. This should be fixable with standard phase-estimation bounds, but it needs explicit handling. Second, Lemma 3.3 imports a trace-distance bound from [Che24, Lemma 2.11]; that's a legitimate external reference rather than a circular step, but a referee should verify the constants.\n\nBottom line: this deserves serious peer review. The central algorithmic contributions are solid, the assumptions are stated rather than hidden, and the sublinear-space factoring circuit is the first of its kind. I'd recommend accept after minor revisions, with the approximate-QFT gap closed or explicitly bounded. I'd cite the Jacobi circuit construction in my own work.","headline":"Real algorithmic advance in compact quantum factoring circuits; the proof-of-quantumness framing rests on an honest but unproven classical-hardness assumption.","tokens_in":36448,"tokens_out":2513,"would_cite":true,"duration_ms":20037,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","11Y05"],"pacs":["03.67.Lx"],"model":"deepseek-v4-flash","headline":"A quantum circuit factors n-bit integers N=P^2 Q with small Q using near-linear gates and sublinear qubits and depth","keywords":["quantum factoring","Jacobi symbol","squarefree decomposition","sublinear space","sublinear depth","proof of quantumness","Gauss sums","period finding"],"falsifier":"A classical factoring algorithm that handles $n$-bit $N=P^2Q$ with $\\log Q=\\Theta(n^{2/3})$ in time $\\exp(o(n^{1/3}))$ would falsify the claim that these integers are classically hard, and with it the proof-of-quantumness application; the circuit construction itself would remain valid.","tokens_in":35401,"feed_emoji":"⚛️","tokens_out":16185,"duration_ms":131811,"temperature":0.7,"pith_summary":"The paper claims that $n$-bit integers of the form $N=P^2Q$ with prime $P,Q$ and $Q<2^m$ can be factored by a quantum circuit using $\\tilde{O}(n)$ gates, $\\tilde{O}(m)$ qubits, and $\\tilde{O}(n/m+m)$ depth. When $\\log Q=\\tilde{\\Theta}(n^{2/3})$, both space and depth become $\\tilde{O}(n^{2/3})$, sublinear in $n$; the authors state this is the first polynomial-time factoring circuit with sublinear qubit count for a class of integers believed hard for classical computers. The result matters because no known classical algorithm exploits the small size of $Q$ to beat the general number field sieve in this regime, so such integers are a promising basis for a classically verifiable proof of quantumness. The same Jacobi-symbol machinery also completely factors any integer whose prime exponents are all distinct, using only $O(\\sqrt{\\log N})$ calls to the squarefree-decomposition circuit.","feed_headline":"Sublinear-space quantum circuit factors P^2 Q numbers","feed_subtitle":"Near-linear gates and n^(2/3) qubits recover both primes for a class believed classically hard.","key_machinery":"The central object is the Jacobi symbol $(a/b)$, a multiplicative character computable without factoring $b$; when $b$ is squarefree it is a primitive Dirichlet character, and for $N=P^2Q$ it collapses to $(x/Q)$ for $x$ coprime to $N$, making the symbol periodic with period $Q$. The argument is carried by two mechanisms. A Gauss-sum estimate for primitive characters gives $|G(\\chi)|=\\sqrt{m}$, which guarantees that after the quantum Fourier transform the superposition of periodic signals has $\\Omega(1)$ amplitude on frequencies close to multiples of $1/Q$, so a single Fourier sampling run succeeds with constant probability. A new reversed long division subroutine streams over the classical bits of $N$ in blocks of size $m$, constructing a multiple $kx$ that matches $N$ in its low $n-m$ bits while storing only the leading $O(m)$ bits of $kx$; by quadratic reciprocity this reduces $(x/N)$ to a Jacobi symbol between two $m$-bit inputs with near-linear gates and sublinear space and depth.","core_discovery":"The core discovery is that factoring $N=P^2Q$ reduces to period finding on a function periodic modulo the secret $Q$: the Jacobi symbol satisfies $(x/N)=(x/Q)$ whenever $\\gcd(x,N)=1$, because $(x/P)^2=1$. The paper proves a sharpened analysis of the squarefree-decomposition circuit showing that a uniform superposition over only $\\mathrm{poly}(B_{\\max})$ values, rather than $\\mathrm{poly}(N)$, suffices to recover the squarefree part $B$ with constant success probability. It then constructs a space-efficient quantum circuit computing the Jacobi symbol $(x/N)$ for classical $N<2^n$ and superposed $x<2^m$ using $\\tilde{O}(n)$ gates, $\\tilde{O}(m)$ qubits, and $\\tilde{O}(n/m+m)$ depth, which is the technical heart of the paper. For $N=P^2Q$ with $\\log Q=\\tilde{\\Theta}(n^{2/3})$, this yields $\\tilde{O}(n)$ gates, $\\tilde{O}(n^{2/3})$ qubits, and $\\tilde{O}(n^{2/3})$ depth.","pith_inferences":["The paper leaves implicit that the circuit theorems and the classical-hardness claim are separable: a future classical speedup for $P^2Q$ would end the proof-of-quantumness application without invalidating the circuit construction.","By analogy with the reversed-division subroutine, the same block-streaming idea should transfer to modular reduction and modular inversion with a large classical modulus and a small superposed operand, making the improvement a general template.","Theorem 3.1 in fact applies to every squarefull $N=A^2B$ with squarefree $B$, so the sublinear-resource claim covers a much larger class than the $P^2Q$ headline; the headline case is the one with a clean classical-hardness story.","A 2048-bit instantiation with $Q\\approx 2^{161}$ would be the natural next test of whether the asymptotic savings survive concrete constant factors; the paper leaves that resource estimation to future work."],"forward_implications":["For $N=P^2Q$ with $\\log Q=\\tilde{\\Theta}(n^{2/3})$, Corollary 4.8 gives a factoring circuit with $\\tilde{O}(n)$ gates, $\\tilde{O}(n^{2/3})$ qubits, and $\\tilde{O}(n^{2/3})$ depth.","This is the first polynomial-time quantum factoring circuit whose qubit count is sublinear in $n$ for a class of integers believed classically hard, and it yields a factoring-based, non-interactive proof of quantumness with sublinear space.","The Jacobi-symbol circuit generalizes to computing greatest common divisors and modular inverses with the same $\\tilde{O}(n)$-gate, $\\tilde{O}(m)$-space, $\\tilde{O}(n/m+m)$-depth profile.","Any integer whose prime factorization has distinct exponents can be completely factored with $O(\\sqrt{\\log N})$ calls to the squarefree-decomposition circuit, succeeding with probability $1-\\mathrm{negl}(\\log N)$.","The initial superposition needs only $\\mathrm{poly}(B_{\\max})$ values, so the quantum cost scales with the size of the squarefree part rather than with $N$ when that part is small."],"supporting_citations":[{"why":"Supplies the squarefree-decomposition circuit and the Jacobi-symbol period-finding idea that this paper sharpens.","marker":"[LPDS12]"},{"why":"Provides the period-finding analysis and continued-fraction post-processing that Theorem 3.1 adapts to a superposition of periodic signals.","marker":"[Sho97]"},{"why":"Supplies a near-linear-time Jacobi-symbol and GCD algorithm used as the equal-size subroutine.","marker":"[Sch71]"},{"why":"Specifies a near-linear divide-and-conquer GCD and Jacobi-symbol algorithm used in the same subroutine.","marker":"[Möl08]"},{"why":"Fast integer multiplication underlying the near-linear gate-count claims.","marker":"[SS71]"},{"why":"Quantum circuit for fast parallel multiplication used to parallelize the block arithmetic into polylogarithmic depth.","marker":"[NZLS23]"},{"why":"Provides the Gauss-sum bound for primitive Dirichlet characters that yields the constant success probability.","marker":"[Con]"},{"why":"Elliptic-curve factoring baseline used to argue no known special-purpose classical algorithm beats the general sieve in the target regime.","marker":"[Len87]"},{"why":"Classical squarefree-decomposition algorithm whose cost sets the state of the art the quantum circuit is compared against.","marker":"[Mul24]"},{"why":"General number field sieve baseline defining the $\\exp(\\tilde{O}(n^{1/3}))$ time that the classical-hardness assumption requires beating.","marker":"[BLP93]"}],"fun_headline_variants":["Quantum factoring of P^2 Q in near-linear gates and sublinear space","Jacobi-symbol circuit shrinks quantum factoring to sublinear space","Near-linear gates, sublinear qubits: factoring P^2 Q","Quantum factoring of P^2 Q gets sublinear qubit count","P^2 Q factoring with near-linear gates and sublinear depth"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that no classical algorithm can factor $N=P^2Q$ with $Q$ of size $n^a$ for $a\\in(2/3,1)$ asymptotically faster than the best known general-purpose factoring method, the number field sieve; the paper surveys known methods but does not prove such an algorithm cannot exist.","fun_headline_variants_meta":{"raw":{"variants":["Quantum factoring of P^2 Q in near-linear gates and sublinear space","Jacobi-symbol circuit shrinks quantum factoring to sublinear space","Near-linear gates, sublinear qubits: factoring P^2 Q","Quantum factoring of P^2 Q gets sublinear qubit count","P^2 Q factoring with near-linear gates and sublinear depth"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00115,"raw_usage":{"total_tokens":4819,"prompt_tokens":1046,"completion_tokens":3773,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":662,"completion_tokens_details":{"reasoning_tokens":3679}},"tokens_in":662,"tokens_out":3773,"duration_ms":27051,"temperature":1.0,"reasoning_tokens":3679,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T13:58:31.905960+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A classical factoring algorithm that handles $n$-bit $N=P^2Q$ with $\\log Q=\\Theta(n^{2/3})$ in time $\\exp(o(n^{1/3}))$ would falsify the claim that these integers are classically hard, and with it the proof-of-quantumness application; the circuit construction itself would remain valid.","supporting_citations":[],"review_version":1}