{"id":"5c9cace2-c941-4e70-b41f-fd1b6d55770b","arxiv_id":"2608.11563","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A new reversible quantum circuit family for Crandall reduction of pseudo-Mersenne moduli achieves roughly 47% lower T-count and T-depth than optimized folding Barrett reduction at n=10.","lead":"The authors design a reversible quantum circuit for modular reduction that works only for moduli of the form 2^n minus a small constant, and report it needs far fewer of the expensive T gates than the standard Barrett method for those numbers. The result could lower the estimated cost of quantum algorithms that rely on modular arithmetic, such as cryptography-breaking algorithms.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Appendix B undercounts T-depth: no-carry adders are used where the final carry/borrow is required, so Table 1 formulas are not the true worst-case costs.","rationale":"The reader identified Appendix B's worst-case bound as the weak point, and I agree that the derivation of the T-depth formulas is the most load-bearing part of the central claim. However, the specific issue the reader flagged (the effective-range lemma for two-step normalization) appears to hold in hand checks for small n: admissible constants with a most significant bit above m have lower Hamming weight, and the shift-range increase is more than offset by the weight decrease, so the maximum cost is still attained by c = 2^k−1 within the m-bit range. The more concrete and demonstrable flaw is that Appendix B uses no-carry adder depths (L−1) for operations whose final carry or borrow is logically needed. This occurs in the first accumulation into the lower register, in each partial-product addition of the second multiplier, and in the normalization subtractor that produces the sign qubit. These are not just resource-accounting choices; omitting those carries would make the circuit compute incorrect values for valid inputs. Correcting them increases the reported T-depth and T-count by more than a small additive constant (about 7 T-depth layers at n=10), so the exact numbers in Table 1 and the associated percentage reductions are wrong. The qualitative advantage over Barrett reduction is likely preserved, so the paper should be revised rather than rejected, which matches the reader's CONDITIONAL verdict. The brute-force test for the effective-range lemma is still worth running, but the carry-omission issue is the decisive concern.","tokens_in":16464,"tokens_out":38741,"duration_ms":378055,"concrete_test":"Implement the n=4, c=3 circuit of Fig. 1 with the no-carry adders exactly as specified and simulate the input a1=15, a0=15 (a=255, q=13). The second folding requires the carry-out of 9+12 to form a(2)=21, and normalization requires the borrow-out to decide the conditional subtraction. If the no-carry adder is used, the circuit returns 5 instead of 8, showing that the no-carry adder cannot be used where Appendix B places it. Alternatively, count the carry-generation blocks in the corrected circuit; for n=10 this yields T_CR1^D = 128 and T-count = 512, not 121 and 484.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Appendix B derives the folding and normalization T-depths using no-carry adders that omit the final carry-out, but in three places that carry is logically required. (1) Eq. (42): the accumulation of c·a1 into a0 must produce the most significant bit of a(1), i.e., the top bit of a′1 = floor(a(1)/2^n). Since a(1) < (c+1)2^n can reach the (n+m)-th bit, a no-carry adder of effective length n+m−1 discards a needed bit. (2) Eq. (43): the second multiplier accumulates shifted m-bit partial products; each addition's carry into the next bit is part of the accumulating product, so each adder has depth m, not m−1. (3) Eq. (50): the normalization subtractor must output the borrow (sign) to control restoration, but p−1 is the no-carry depth. Correcting these for n=10 gives T_CR1^D = 128 instead of 121, and T-count = 512 instead of 484; the claimed 46.9% reduction over optimized folding Barrett drops to roughly 44%. The formulas in Eq. (20) and Table 1 are therefore not exact worst-case resource costs of the described circuit, and the paper's internal consistency is broken by using no-carry adders where the circuit needs the carry.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes two reversible quantum circuits, Crandall reduction-1 and Crandall reduction-2, for modular reduction modulo pseudo-Mersenne moduli q = 2^n − c. It fixes two classical folding steps in the quantum circuit, derives sufficient ranges on c for one-step and two-step normalization, and counts T gates and T-depth using temporary logical-AND-based adders combined with quantum-classical specialization for the constants c and q. It then extends the analysis to a surface-code setting, estimating required code distances via a KQ-style error model and runtimes through a magic-state factory latency model plus a decoder-backlog model, reporting a resource advantage over optimized folding Barrett reduction.","tokens_in":16746,"tokens_out":24054,"duration_ms":247301,"significance":"If the resource counts were correct, this would be a valuable modulus-specialized alternative to Barrett reduction: the derivation is parameter-free, the comparison against optimized folding Barrett reduction is systematic, and the fault-tolerant runtime model provides concrete quantitative predictions. The paper is generally clear, and the two-fold normalization-range analysis is mostly sound. However, the exactness of the reported T-count and T-depth formulas is the central contribution, and the carry-accounting errors identified below mean that the stated numbers are not yet reliable. The qualitative conclusion that Crandall reduction beats Barrett reduction appears robust to the corrections (the n=10 advantage drops from about 46.9% to about 43.9%), but all resource formulas and the derived code-distance expressions need to be re-derived and cross-checked.","major_comments":[{"comment":"The folding and normalization T-depth formulas omit carry or borrow outputs that the circuit logically requires. In Eq. (42), the accumulation of c·a1 into a0 must produce the top bit of a(1) at position n+m−1, since a(1) can reach 2^{n+m}−1; a no-carry adder of effective length n+m−1 produces only bits 0 through n+m−2, so the correct depth is n+m−1, not n+m−2. In Eq. (43), each of the k−1 partial-product accumulations in the second multiplier must propagate its carry into the next bit of the accumulating product, so each addition costs depth m, not m−1. In Eq. (44), the final accumulation of the second product into a'_0 can carry into bit n, so the n-bit no-carry adder of depth n−1 is insufficient and depth n is required. In Eq. (50), the normalization subtractor must output the borrow that controls the restoration addition, so the p=n+1-bit subtractor has depth p, not p−1. Applying these four corrections for n=10 raises T_CR1^D from 121 to 128 and T_CR1_count from 484 to 512, changing the claimed 46.9% reduction over optimized folding Barrett to about 43.9%. Thus Eq. (20) and Table 1 are not exact worst-case resource counts of the circuit as described.","section":"Appendix B, Eqs. (42)-(44), (50)"},{"comment":"The resource formulas are internally inconsistent for odd n. Eq. (17) and Eq. (20) use (n−1)ceil(n/2) in the folding depth, while the derivation in Appendix B, Eq. (45)-(48), yields (n−1)floor(n/2). For n=11, these differ by 10 in the folding T-depth (89 versus 99, or 136 versus 146 in T_CR1^D). In addition, substituting the Table 1 values of K and D_T into Eqs. (22)-(24) for odd n gives K·D_T = (18n^3 + 129n^2 + 66n + 3)/4 for Crandall-1, not the expression corresponding to Table 2's odd-n row, which contains (18n^3 + 93n^2 + 60n + 9)/4. Since Table 2's code-distance formulas are presented as derived from the logical resource estimates, this discrepancy must be resolved and the affected distance formulas rechecked.","section":"Section 4.1, Eq. (17)/(20) vs Appendix B Eq. (48); Table 2 odd-n rows"},{"comment":"The worst-case bound for two-step normalization is asserted without proof. The text claims that admissible constants whose most significant bit lies above the effective range m are offset by a smaller Hamming weight, but no inequality is provided. For n=10, the two-step range includes c=43, which has wt(c)=4 and a highest bit at position 5, while c=31 has wt(c)=5 within positions 0..4; the depth formula depends on both the shift range and the Hamming weight, and it is not shown that the smaller Hamming weight always dominates the larger shift range. Since Eq. (17) is presented as a worst-case bound over all admissible c, this step needs either a proof or a counterexample.","section":"Appendix B, paragraph after Eq. (39)"}],"minor_comments":[{"comment":"The algebraic simplifications in Eqs. (8) and (9) are incorrect: (c+1)2^n / (2^n−c) is not equal to c + c(c+1)/(2^n−c), and the correct expression involves a remainder of (2^n + c^2)/(2^n−c) for Eq. (8) and requires a ceiling rather than a floor. The subsequent conclusions about N_max1 and N_max2 happen to be correct under the stated conditions, but the displayed equations should be fixed.","section":"Section 2.2, Eqs. (8)-(9)"},{"comment":"The statement that 'the execution time was compared on the log10(talg[s]) scale' followed by values such as 1283.13, 932.19, 521.03, and 632.12 is inconsistent; if these are actual runtimes in seconds, the axis label and text should say so, and if they are log10 values, the numbers are implausibly large. Please clarify the units and the axis scaling.","section":"Section 5.4 and Figure 6(a)"},{"comment":"Eq. (24) as written does not contain a ceiling operation, but the entries in Table 2 use ceiling over a base-10 logarithm. The rounding convention should be stated explicitly so the formulas can be reproduced.","section":"Table 2 and Eq. (24)"},{"comment":"The phrase 'first exact reversible quantum circuit formulation' is stronger than what the manuscript currently supports, given the carry-accounting issues in Appendix B; after correcting the formulas, please re-evaluate this claim or qualify it as 'first formulation with exact resource counts' only once the counts are verified.","section":"Abstract and Section 4.1"}],"recommendation":"major_revision","confidential_remarks":"The conditional verdict from the review is well founded. The carry-accounting concern is confirmed by the manuscript's own adder definitions: no-carry adders are used in several places where the final carry or borrow is logically required, and the odd-n inconsistency between Section 4.1 and Table 2 indicates that the formulas were not numerically cross-validated. The qualitative resource advantage over Barrett reduction appears to survive the corrections, so the paper is fixable, but all resource formulas, the code-distance expressions, and the associated numeric examples need to be re-derived and rechecked. I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a genuinely new circuit family for modular reduction with pseudo-Mersenne moduli, and the resource advantage over Barrett reduction is probably real. But the paper's headline numbers are wrong. The T-depth/T-count formulas in Table 1 undercount because Appendix B uses no-carry adders in several places where the final carry (or borrow) is logically required: the first folding sum needs the top bit of a(1) to form a'_1, the second multiplier needs carries into the accumulating product, and the normalization subtractor needs the borrow to drive the conditional restoration. For n=10 I get T_CR1^D = 128 and T-count = 512, not 121 and 484; the claimed 46.9% reduction drops to about 44%. The advantage survives, but the exact worst-case claim does not.\n\nThe main new thing is the explicit reversible formulation of Crandall reduction: two fixed folding steps plus one or two conditional subtractions, with clean normalization conditions. That part is sound and useful. The building blocks are standard, and the normalization-range analysis (c^2 + 2c ≤ 2^n and c^2 + 3c ≤ 2^{n+1}) checks out. The paper is also honest in not fitting any parameter.\n\nThe other soft spots: Table 2's odd-n distance formulas don't match the K·D_T product from Table 1 (n=11 gives d=9, should be 7). The effective-range lemma in Appendix B, that constants with wider shifts have lower Hamming weight, is asserted but not proven, and it is load-bearing for the worst-case bound. The runtime model is a simplified backlog approximation; fine as an estimate, not a prediction.\n\nThe citation pattern looks fine, and the Barrett baselines are the right ones. No code or formal verification, but that is normal for this literature.\n\nThis deserves a serious referee: the idea is new, the error is in the cost accounting rather than the reduction logic, and a revision that fixes the carry treatment and re-derives the worst-case formulas would be a solid contribution. I would send it to review, with a request that the authors check every no-carry adder against the actual circuit, or provide code.","headline":"A useful idea with a real accounting flaw: the Crandall-reduction circuits likely beat Barrett, but the T-depth formulas are not worst-case because they drop carries that the circuit needs.","tokens_in":17259,"tokens_out":7151,"would_cite":false,"duration_ms":71016,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper shows how to make reversible quantum modular reduction for moduli $q=2^n-c$ using two folding steps plus conditional subtractions, beating optimized Barrett reduction in qubits, T-count, T-depth, and runtime.","keywords":["Crandall reduction","pseudo-Mersenne modulus","quantum modular reduction","reversible circuit","T-count","T-depth","surface code","fault-tolerant quantum computation"],"falsifier":"For a fixed $n$, enumerate every admissible $c$ (for the two-step variant, all $c$ with $c^2+3c\\le 2^{n+1}$); for each $c$, count the carry-generation blocks in the two folding multiplications and the accumulation adder under the paper's construction. If any admissible $c$ yields a folding T-depth greater than $\\lfloor n^2/4\\rfloor+(n-1)\\lceil n/2\\rceil+n-2$, the reported formulas are not worst-case; at $n=10$, checking the full range up to $c=43$ already tests this.","tokens_in":16219,"feed_emoji":"🧮","tokens_out":15450,"duration_ms":143314,"temperature":0.7,"pith_summary":"This paper aims to show that when the modulus has the special form $q=2^n-c$, quantum modular reduction can be built from two fixed folding steps and conditional subtractions, avoiding division and general multiplication. It derives explicit conditions for one-step and two-step normalization—$c^2+2c\\le 2^n$ and $c^2+3c\\le 2^{n+1}$—and turns them into two reversible circuit variants, Crandall reduction-1 and Crandall reduction-2. The reported worst-case resources are $T_{\\mathrm{CR1}}=4F(n)+20n+4$ T gates with depth $F(n)+5n+1$, where $F(n)=\\lfloor n^2/4\\rfloor+(n-1)\\lceil n/2\\rceil$; at $n=10$ this cuts both metrics by about 46.9% compared with optimized folding Barrett reduction. The authors further map both variants to the surface code and estimate that the lower T-depth reduces required code distance and total execution time, for example 30.05 ms versus 53.77 ms at $n=20$ under their fast-decoder setting. If correct, the result gives a concrete modulus-class-specific way to reduce the dominant non-Clifford cost in quantum arithmetic for cryptanalytic algorithms.","feed_headline":"Crandall reduction cuts quantum modular cost by ~47%","feed_subtitle":"Reversible folding circuits for pseudo-Mersenne moduli beat Barrett in T-count, T-depth, and runtime.","key_machinery":"The load-bearing mechanism is Crandall folding: the congruence $2^n\\equiv c\\pmod q$ lets the high half of a $2n$-bit input be multiplied by the small constant $c$ and added to the low half, replacing division by bit shifts plus constant multiplication. The circuit fixes exactly two folds and then normalizes by subtract-then-restore: subtract $q$ and conditionally add it back when the sign bit shows a negative result. Reversible components are specialized to the fixed classical bit patterns, so gates corresponding to zero bits of $c$ and $q$ are removed; carry and borrow logic uses the temporary logical-AND construction, which contributes T-count 4 and T-depth 1 per carry-generation block. The worst-case resource counts follow from bounding the Hamming weight of admissible $c$ by $\\lfloor n/2\\rfloor$ and the effective active-bit range by $\\lceil n/2\\rceil$.","core_discovery":"The paper's central claim is that Crandall reduction—classically a looped fold-and-subtract method for moduli $q=2^n-c$—can be made into a reversible quantum circuit with a fixed structure of two folding steps, followed by one or two conditional subtractions. It derives sufficient conditions: one-step normalization works when $c^2+2c\\le 2^n$, and two-step normalization works when $c^2+3c\\le 2^{n+1}$. Using a temporary logical-AND-based arithmetic primitive and quantum-classical specialization for the fixed constants, the worst-case T-depth formulas are $T^{\\mathrm{CR1}}_D=F(n)+5n+1$ and $T^{\\mathrm{CR2}}_D=F(n)+9n+4$, with T-counts four times those depths; here $F(n)=\\lfloor n^2/4\\rfloor+(n-1)\\lceil n/2\\rceil$. The paper reports that both variants use fewer qubits, fewer T gates, and less T-depth than optimized folding Barrett reduction, with a representative 46.9% reduction at $n=10$, and that the lower T-depth propagates to smaller surface-code distance and shorter estimated execution time.","pith_inferences":["The fold-then-normalize template should transfer to other special-form moduli with a small power-of-two offset, such as $2^n+c$ or multi-term generalized Mersenne forms; the paper's range analysis gives a recipe for deriving the admissible constants.","The reported worst-case costs are conservative in one direction: constants with sparse binary representations need fewer partial-product additions, so an implementation could tune $c$ (or $n$) to land on a sparse admissible constant and beat the tabulated numbers.","In complete algorithms such as Shor's factoring, modular reduction is invoked many times; if the per-call savings survive integration and uncomputation, the end-to-end reduction in T-count could exceed the single-call figure.","The runtime model is sensitive to the decoder throughput ratio: if that ratio is even slightly above one, the exponential backlog term amplifies any T-depth difference, so the gap between Crandall and Barrett reduction could widen in decoder-limited settings."],"forward_implications":["For pseudo-Mersenne moduli $q=2^n-c$ with $c^2+2c\\le 2^n$, the one-step variant achieves worst-case T-depth $F(n)+5n+1$ and T-count $4F(n)+20n+4$; both are lower than the optimized folding Barrett reduction circuits compared in the paper.","The two-step variant admits the larger range $c^2+3c\\le 2^{n+1}$ (at $n=10$, $1\\le c\\le43$ instead of $1\\le c\\le31$) while still beating Barrett reduction on T-count and T-depth.","Because the proposed formulas have smaller quadratic coefficients than Barrett reduction, the resource advantage grows with operand size $n$.","The lower T-depth also lowers the required surface-code distance for a fixed target failure probability and shortens estimated fault-tolerant execution time, including decoder backlog time."],"supporting_citations":[{"why":"It supplies the classical folding identity $2^\\ell\\equiv c\\pmod q$ that the circuit operationalizes.","marker":"[7]"},{"why":"It provides the optimized folding Barrett reduction circuit used as the comparison baseline.","marker":"[8]"},{"why":"It gives the temporary logical-AND construction that sets the T-count 4 and T-depth 1 per carry-generation block.","marker":"[15]"},{"why":"It supplies the surface-code logical error model and magic-state factory latency factor used in fault-tolerant estimates.","marker":"[10]"},{"why":"It provides the physical error rate and decoder throughput values used in the code-distance and runtime simulations.","marker":"[16]"},{"why":"It supplies the KQ formalism connecting qubit count and circuit size to logical error rate and code distance.","marker":"[18]"},{"why":"It supplies the failure-probability approximation that ties logical error rate to the T-depth and qubit count.","marker":"[12]"}],"fun_headline_variants":["Crandall reduction trims quantum modular cost by ~47%","First reversible Crandall circuit beats Barrett in T-count and T-depth","Crandall reduction lowers fault-tolerant resource needs","Pseudo-Mersenne moduli enable efficient quantum reduction","Crandall reduction cuts T-count and depth ~46.9% at n=10"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The worst-case T-depth and T-count formulas rest on an unproved bound: for every constant $c$ allowed by the normalization condition, the folding stage never needs more carry blocks than the maximum-Hamming-weight case within the assumed bit range, even when $c$ is large enough to extend beyond that range.","fun_headline_variants_meta":{"raw":{"variants":["Crandall reduction trims quantum modular cost by ~47%","First reversible Crandall circuit beats Barrett in T-count and T-depth","Crandall reduction lowers fault-tolerant resource needs","Pseudo-Mersenne moduli enable efficient quantum reduction","Crandall reduction cuts T-count and depth ~46.9% at n=10"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000554,"raw_usage":{"total_tokens":2709,"prompt_tokens":1084,"completion_tokens":1625,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":700,"completion_tokens_details":{"reasoning_tokens":1534}},"tokens_in":700,"tokens_out":1625,"duration_ms":14084,"temperature":1.0,"reasoning_tokens":1534,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T00:36:13.571091+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a fixed $n$, enumerate every admissible $c$ (for the two-step variant, all $c$ with $c^2+3c\\le 2^{n+1}$); for each $c$, count the carry-generation blocks in the two folding multiplications and the accumulation adder under the paper's construction. If any admissible $c$ yields a folding T-depth greater than $\\lfloor n^2/4\\rfloor+(n-1)\\lceil n/2\\rceil+n-2$, the reported formulas are not worst-case; at $n=10$, checking the full range up to $c=43$ already tests this.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It supplies the classical folding identity $2^\\ell\\equiv c\\pmod q$ that the circuit operationalizes."},{"cited_title":"Rep.1522808 (doi: 10.1038/s41598-025-04987-1)","cited_arxiv_id":null,"evidence_quote":"It provides the optimized folding Barrett reduction circuit used as the comparison baseline."},{"cited_title":"Process.2160 (doi: 10.1007/s11128-021-03398-1)","cited_arxiv_id":null,"evidence_quote":"It supplies the failure-probability approximation that ties logical error rate to the T-depth and qubit count."}],"review_version":1}