{"id":"8b5a0d45-9814-4bda-a597-2ae99f914d29","arxiv_id":"2608.03188","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A rectangle-covering method for factoring ESOP expressions reports reductions of 20-95% in quantum circuit gate costs on benchmark circuits.","lead":"Researchers present two algorithms, called D and EO, that factor Exclusive-Sum-Of-Products logic expressions using a rectangle-covering trick over a matrix of product terms. On standard benchmarks they report 20-95% reductions in literal count and in Maslov quantum circuit cost.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Even-odd covering criterion (Def. 4) is self-contradictory: it requires both symmetric cells of every degree-2 cube to be covered oddly, forcing cancellation; paper's own Example 10 violates it, and Algorithm 2's cell-wise toggle has no correctness invariant.","rationale":"The reader's weakest assumption targeted the density-bound restriction and the unverified Maslov cost model, treating the algebraic core as correct. My review shows the core itself is internally inconsistent: the formal even-odd condition (Definition 4) cannot hold for any ESOP with degree-2 cubes because the two symmetric filled cells contribute even parity, forcing cancellation. The paper's own successful examples violate the stated condition, and Algorithm 2's cell-wise toggling lacks an invariant linking the matrix state to the remaining Boolean function. This is the single most load-bearing concern because the central claim is about producing equivalent factored AND/EXOR circuits; if equivalence fails, all cost reductions are for wrong functions. The proposed concrete test would quickly settle the matter by checking whether the described algorithm produces truth-table-equivalent outputs on small ESOPs. Until such a check is done, the paper cannot be conditionally accepted as a sound synthesis method. The reader's verdict should therefore move from CONDITIONAL to REJECT, not because of the optimality or cost-model gaps, but because the correctness of the core even-odd covering construction is unsupported and contradicted by the paper's own definitions.","tokens_in":17719,"tokens_out":17717,"duration_ms":191330,"concrete_test":"Implement the matrix representation exactly as described in §3.1–§3.4 (storing both symmetric entries) and Algorithm 2 as pseudocoded in §4.2 (cell-wise toggling with F=0.9 and F=0.75). Run it on all ESOPs over ≤4 variables that contain degree-2 cubes (e.g., E=ab, E=ab⊕ac⊕bc, and the rd53 benchmark) and compare the truth table of the returned factored form against the input. Any mismatch refutes correctness. If the implementation instead silently performs cube-level parity toggling (toggling both symmetric cells together), the paper's stated algorithm and proof need substantial revision to match what is actually computed.","verdict_should_be":"REJECT","load_bearing_attack":"The central claim that the factored forms are equivalent to the input ESOP rests on Section 3.4's even-odd correctness criterion and Algorithm 2's recursive update. This foundation is unsound. Section 3.1 stores every degree-2 cube ab in two symmetric cells, M_{a,b}=M_{b,a}=k. Definition 4 declares a cover valid if every filled cell is covered an odd number of times and every empty cell an even number of times. But the EXOR expansion of a rectangle R=(A,B) contributes each product a·b once per ordered pair (a,b) ∈ A×B; since a·b = b·a, the net parity of cube ab is [cov(a,b) + cov(b,a)] mod 2. Definition 4 forces both cov(a,b) and cov(b,a) to be odd, so every degree-2 cube present in E cancels. Hence no cover satisfying Definition 4 can realize any non-trivial ESOP with degree-2 cubes. Indeed, the paper's own Example 10 (Fig. 9b) violates the definition: the empty cells (a,c) and (c,a) are each covered once (odd). The correctness argument (Eqs. 13–14) conflates a 'filled cell' with a 'cube' and ignores the symmetric duplicate. Moreover, Algorithm 2's update step toggles only the directed cells in the chosen rectangle; it does not implement XOR of F_R into the remaining function, because the cube ab is not removed unless both orientations are toggled. The recursive search is therefore not over ESOP-equivalence classes, and the output can be a different function. This is more fundamental than the density-bound or cost-model issues: if the factored circuits are not functionally equivalent, the reported 20–95% reductions are meaningless.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes two rectangle-covering algorithms for factoring Exclusive-Sum-of-Products (ESOP) expressions into multi-level AND/EXOR forms, with the stated goal of reducing quantum circuit cost as measured by literal count and Maslov cost. ESOP expression cubes are stored in a symmetric matrix; a rectangle cover is then translated into a factored expression. Algorithm D uses a greedy disjoint rectangle covering, while Algorithm EO performs a recursive search over rectangles satisfying a density bound, allowing even/odd cell coverage. The authors claim 20--95% reductions in literal count and Maslov cost on a set of MCNC benchmarks, and assert that Algorithm EO finds the most optimal even-odd covering solution. The central novel ingredient is the even-odd covering criterion in Section 3.4 and its implementation in Algorithm 2.","tokens_in":18244,"tokens_out":7376,"duration_ms":86698,"significance":"If correct, a systematic factorization method for AND/EXOR expressions with a validated cost model would be useful for quantum circuit synthesis, particularly for reducing large Toffoli gates. The paper also provides a potentially reusable recursive Maslov-cost estimation framework and benchmarks against standard PLA circuits. However, the core correctness foundation of the even-odd method is flawed: the validity criterion is stated on directed matrix cells while cubes are stored symmetrically, and Algorithm 2 does not preserve ESOP equivalence. As presented, the reported cost reductions cannot be attributed to functionally equivalent circuits, so the main contribution is not established.","major_comments":[{"comment":"The even-odd validity criterion is stated on directed cells, but the matrix stores each degree-2 cube twice (Section 3.1: M_{a,b}=M_{b,a}=k). For a fixed cube ab, a cover contributes cov(M_{a,b})+cov(M_{b,a}) modulo 2 because ab=ba. Imposing that every filled directed cell has odd coverage therefore makes every degree-2 cube appear an even number of times, so no nontrivial degree-2 ESOP is representable under Definition 4. Conversely, the paper's own Example 10/Fig. 9b gives F2=(a⊕b)(c⊕d)⊕(c⊕f)(a⊕e), which is equal to the stated ESOP, yet the empty cells M_{a,c} and M_{c,a} are each covered exactly once. Thus Definition 4 is neither necessary nor sufficient for functional equivalence. Equations (13)-(14) equate a filled cell with a cube and ignore the symmetric duplicate.","section":"§3.4, Definition 4 and Example 10"},{"comment":"The recursive update is not an ESOP-equivalence operation. Toggling a cell from filled to empty on only the directed cells covered by the chosen rectangle leaves the opposite orientation M_{b,a} of the same cube untouched, so the cube is not removed from the function. When an empty cell is toggled to filled, Algorithm 2 assigns a fresh number C' per cell; if both orientations of a new cube are later covered, they receive different indices, breaking the matrix invariant M_{a,b}=M_{b,a} and hence the correspondence between matrices and ESOPs. The recursion therefore searches over matrices that do not necessarily represent the same Boolean function as the input. This invalidates the claim that the final factored expression is equivalent to the input ESOP.","section":"§4.2, Algorithm 2"},{"comment":"Algorithm EO is not an exhaustive search over all even-odd coverings. It restricts to rectangles with at least two cells and density at least F, then constructs solutions by repeatedly choosing one rectangle, toggling the matrix, and recursing until empty. No completeness theorem is given: a globally optimal factored form need not be reachable within this restricted space, and F is an arbitrary feasibility parameter rather than a derived bound. The phrase 'most optimal' should be replaced by 'best within the enumerated rectangle set.' Table 3 tests only F=0.75 vs 0.9 on a subset of benchmarks and cannot support global optimality.","section":"§4.2, 'most optimal' claim"},{"comment":"All reported Maslov-cost reductions are computed with the paper's own recursive model; no independent compiler or actual circuit realization is used to check the model. The model's internal arithmetic is inconsistent: in Example 12 the text identifies a single cube factor, then uses an ancilla to store a different multi-cube expression, and applies the special-case formula inconsistently. Since every percentage reduction in Tables 2-3 depends on this model, the quantitative claims (20-95%) are not validated. The model should be proven equivalent to the Section 2.4 gate count or compared against a concrete synthesis tool.","section":"§4.4 and Example 12"}],"minor_comments":[{"comment":"The computed automata cost is arithmetically wrong: the enumerated sum M(3)+M(1)+M(2)+M(3)+M(1)+M(3)+M(3) equals 23, not 19, and the displayed formula 2·1 + 1·2 + 3·5 = 19 does not match the number of listed gates.","section":"Example 6"},{"comment":"For DP/EO, LE=12 and LF=9 imply ∆L=25.0%, but the table reports 16.7%. Please re-check all percentage entries for consistency.","section":"Table 2, eosops1 row"},{"comment":"The figure has overlapping and illegible labels, especially for benchmarks with similar names, and omits some rows from Table 2 (e.g., rd84 and 9sym). This makes the visual cost comparison difficult to verify.","section":"Figure 10"},{"comment":"In the degree-1 case, the text says 'M_{x,x} gets numbered i' but the cube index is k; the notation should be unified with Eq. (1) and the surrounding text.","section":"§3.1"}],"recommendation":"reject","confidential_remarks":"The even-odd rectangle method is the paper's main novelty, but the correctness criterion and the recursive algorithm are internally inconsistent. The reported experiments cannot rescue the paper because the factorization outputs are not shown to implement the input ESOP. The authors would need to redefine the parity criterion at the cube level, repair Algorithm 2's toggle operation, provide a completeness proof for the search, and re-run the benchmark evaluation with an independently validated cost model. This is a substantial rewrite rather than a local fix. I recommend rejection in the current form, while noting that a corrected version could be a useful contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"I read this paper against the stress-test, and I think the stress-test lands. The core problem is that the matrix stores every degree-2 cube twice, in symmetric cells, and the even-odd correctness criterion (Def. 4) doesn't account for that. If every filled cell must be covered oddly, then both M_{a,b} and M_{b,a} are covered oddly for cube ab, so the two copies cancel and the cube vanishes. Example 10 is the tell: the shown cover is invalid under Definition 4 because the empty cells (a,c) and (c,a) are each covered once, odd; the cover only works if you treat the two orientations together as one cube with total even coverage. Equations (13)-(14) treat a filled cell as a cube and ignore the symmetric duplicate. Algorithm 2 toggles directed cells one by one, which is not XORing F_R into the remaining expression at cube level. So the factored output is not demonstrated to be equivalent to the input, and the reported 20-95% reductions are not meaningful as stated.\n\nThat is a shame, because the underlying intuition is decent and worth keeping: covering the matrix with rectangles, using odd/even parity to allow overlap, is a natural extension of Kalay's overlap idea, and applying it to quantum synthesis cost is new. The paper also has clear worked examples, a reasonable benchmark set, and the greedy Algorithm D is simple and easy to reproduce. The density-bound and 'optimal' issues are real but secondary; the unverified Maslov cost model is also secondary. First fix the equivalence bug.\n\nWould I send this to peer review? Yes, a serious referee could help the authors repair the definition—for instance, by treating each cube as an unordered pair and toggling both orientations together—and then re-run the benchmarks. But as it stands I would not cite it as a reliable result. It could still be a useful reading-group case study in how a symmetry error can invalidate an otherwise plausible synthesis method.","headline":"A novel rectangle-covering idea for ESOP factoring, but the equivalence proof is broken as written; benchmark savings are not trustworthy until that is fixed.","tokens_in":18666,"tokens_out":8785,"would_cite":false,"duration_ms":103019,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Rectangle-cover factoring of ESOP logic reduces quantum circuit cost by 20% to 95%.","keywords":["ESOP","factorization","rectangle covering","quantum circuit cost","Maslov cost","Toffoli gates","AND/EXOR circuits","reversible logic"],"falsifier":"Run the benchmarks with the density threshold removed and all rectangles (including those with one cell) considered, and check whether a lower-cost factoring exists outside the paper's search space; separately, compile a factored expression with a quantum circuit tool and compare the realized gate count against the Maslov model's prediction. A single counterexample in either test would invalidate the 'most optimal' or the exact 20–95% claims.","tokens_in":17652,"feed_emoji":"⚛️","tokens_out":7202,"duration_ms":63335,"temperature":0.7,"pith_summary":"The paper tries to establish that factorizing two-level EXOR-sum-of-products (ESOP) expressions into multi-level AND/EXOR forms, by covering a matrix of product terms with rectangles, can sharply reduce the cost of the resulting circuits. Two algorithms are proposed: a greedy disjoint rectangle covering and a recursive even-odd covering that exploits EXOR cancellation. On standard benchmark expressions, both algorithms reduce literal counts by roughly 20–80% and quantum circuit costs by 20–95%, with the largest percentage reductions on the largest expressions. If correct, the method gives a practical pre-synthesis step for quantum circuits composed of multi-controlled Toffoli gates.","feed_headline":"Factoring logic with rectangle covers cuts quantum costs up to 95%","feed_subtitle":"Two covering algorithms rewrite two-level AND/EXOR expressions into cheaper multi-level forms, with the biggest gains on large circuits.","key_machinery":"The rectangle cover of a cube-index matrix: an ESOP with degree-2 cubes is mapped to a $d\\times d$ matrix with rows and columns labelled by the support variables; each cube occupies one or two symmetric cells. A rectangle $(A,B)$ is the factored expression $(\\oplus_{a\\in A} a)(\\oplus_{b\\in B} b)$, and a valid cover decomposes the ESOP into an EXOR sum of such rectangles. Disjoint covering demands exactly one cover per filled cell; even-odd covering demands odd coverage of filled cells and even coverage of empty cells, which is sound because of EXOR idempotency. Higher-degree cubes are reduced to degree 2 by substituting frequent subcubes with new variables that become ancilla qubits.","core_discovery":"The central claim is that every degree-2 ESOP expression can be written as a matrix of product terms, and that rectangles in this matrix correspond to factored subexpressions of the form $(\\oplus_{a\\in A} a)(\\oplus_{b\\in B} b)$. Covering all filled cells with rectangles produces an equivalent factored expression; the paper proposes two covering rules. The disjoint rule covers each filled cell exactly once using 100%-density rectangles, found greedily. The even-odd rule allows filled cells to be covered an odd number of times and empty cells an even number of times, using the EXOR identity $x\\oplus x=0$ to cancel extra copies, and searches recursively over all rectangles with density at least","pith_inferences":["The paper's 'most optimal' wording applies only within the set of rectangles it searches; the search excludes rectangles of density below 0.9 (or 0.75) with fewer than two cells, so the global optimum could lie outside that set. A stricter claim would be 'best among all rectangles above the density bound.'","If the Maslov-based cost model is replaced by a concrete compilation and gate counting, the 20–95% figures might shift, since the model is never checked against an actual compiler in the paper.","The even-odd covering trick is specific to EXOR logic; an analogous idempotency-based overlap does not exist for AND/OR, so the method is unlikely to transfer directly to classical SOP factorization without modification.","Because the reported percentage gains grow with expression size, the approach is most promising for large quantum oracles, but the recursive EO algorithm's runtime may need heuristic pruning before it scales to such inputs."],"forward_implications":["Factored AND/EXOR forms produced by the two algorithms reduce literal count, quantum automata cost, and quantum oracle cost on all tested benchmarks, with bigger relative reductions on bigger expressions.","The greedy disjoint algorithm obtains solutions close to those of the more expensive exhaustive even-odd algorithm, so it is a practical choice when runtime matters.","The feasibility bound of 0.9 versus 0.75 makes almost no difference in cost, indicating the method is robust to that parameter.","The cost reductions hold under both the automata model (no mirroring) and oracle model (with mirroring), so the factoring is useful for reversible and oracle-based quantum circuits."],"supporting_citations":[{"why":"Supplies the EXORCISM-4 tool that minimizes raw benchmark PLA files into the ESOP expressions used as inputs.","marker":"[1]"},{"why":"Establishes the rectangle covering factorization method for ESOPs that this paper extends to disjoint and even-odd covers.","marker":"[14]"},{"why":"Origin of the rectangle-covering factorization technique for SOP expressions, adapted here to ESOPs.","marker":"[11,12,13]"},{"why":"Defines the Maslov quantum cost table for n-bit Toffoli gates used to compute all quantum automata and oracle costs.","marker":"[18]"},{"why":"Defines the PLA format in which the benchmarks are expressed.","marker":"[19]"},{"why":"Provides the MCNC benchmark suite from which the test expressions are drawn.","marker":"[20]"}],"fun_headline_variants":["Rectangle covering reduces quantum circuit cost by 20–95%","ESOP factoring via rectangle covers lowers quantum cost up to 95%","Two rectangle-cover algorithms cut quantum circuit cost up to 95%","Rectangle covers shrink ESOP quantum costs by up to 95%"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"The reported reductions and the 'optimal' label both depend on the untested assumption that the restricted set of high-density rectangles contains the best factoring and that the Maslov-based cost formulas match the cost of actually realized circuits.","fun_headline_variants_meta":{"raw":{"variants":["Rectangle covering reduces quantum circuit cost by 20–95%","ESOP factoring via rectangle covers lowers quantum cost up to 95%","Two rectangle-cover algorithms cut quantum circuit cost up to 95%","Rectangle covers shrink ESOP quantum costs by up to 95%"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001565,"raw_usage":{"total_tokens":6041,"prompt_tokens":656,"completion_tokens":5385,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":400,"completion_tokens_details":{"reasoning_tokens":5309}},"tokens_in":400,"tokens_out":5385,"duration_ms":32886,"temperature":1.0,"reasoning_tokens":5309,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T23:58:36.106895+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the benchmarks with the density threshold removed and all rectangles (including those with one cell) considered, and check whether a lower-cost factoring exists outside the paper's search space; separately, compile a factored expression with a quantum circuit tool and compare the realized gate count against the Maslov model's prediction. A single counterexample in either test would invalidate the 'most optimal' or the exact 20–95% claims.","supporting_citations":[{"cited_title":"Yang (1991),Logic Synthesis and Optimization Benchmarks User Guide Version 3.0, Micro- electronics Center of North Carolina (MCNC)","cited_arxiv_id":null,"evidence_quote":"Provides the MCNC benchmark suite from which the test expressions are drawn."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the PLA format in which the benchmarks are expressed."},{"cited_title":"Mishchenko and M","cited_arxiv_id":null,"evidence_quote":"Supplies the EXORCISM-4 tool that minimizes raw benchmark PLA files into the ESOP expressions used as inputs."},{"cited_title":"Kalay, M","cited_arxiv_id":null,"evidence_quote":"Establishes the rectangle covering factorization method for ESOPs that this paper extends to disjoint and even-odd covers."},{"cited_title":"Maslov, G","cited_arxiv_id":null,"evidence_quote":"Defines the Maslov quantum cost table for n-bit Toffoli gates used to compute all quantum automata and oracle costs."}],"review_version":1}