Pith. sign in

REVIEW 4 major objections 4 minor 20 references

Factorization of Exclusive-Sum-Of-Products Expressions with Rectangle Covering to Reduce Quantum Circuit Cost

T0 review · 4 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Rectangle-cover factoring of ESOP logic reduces quantum circuit cost by 20% to 95%.

desk verdict 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. read the letter →

arxiv 2608.03188 v1 pith:TVVOXWE6 submitted 2026-08-04 quant-ph

Audrey Hou , Lucia Zhang , Ali Al-Bayaty , Marek Perkowski This is my paper · ORCID
classification quant-ph
keywords ESOPfactorizationrectanglecoveringquantumcircuitcostMaslovToffoligatesAND/EXORcircuitsreversiblelogic
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

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.

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 (4)
  1. [§3.4, Definition 4 and Example 10] 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.
  2. [§4.2, Algorithm 2] 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.
  3. [§4.2, 'most optimal' claim] 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.
  4. [§4.4 and Example 12] 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.
minor comments (4)
  1. [Example 6] 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.
  2. [Table 2, eosops1 row] 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.
  3. [Figure 10] 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.
  4. [§3.1] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the factorization pipeline and cost reductions are self-contained, though a non-circular soundness gap exists in the even-odd equivalence proof.

full rationale

I examined the derivation chain: input ESOP -> FPRM/degree-2 conversion -> matrix representation -> rectangle coverings (Algorithm D and Algorithm EO) -> factored expression -> literal and Maslov cost reductions. The central equality F = XOR_{R in S} F_R = E (Eq. 12) is stated as a consequence of the rectangle-covering definitions and the XOR idempotence law, not as a restatement of the input or a fitted parameter. The cost reductions are computed with the same Maslov-based model used to guide the search, but this is standard optimization under a fixed evaluation metric; no benchmark-derived parameter is fit and then reported as a prediction. The baseline ESOPs come from EXORCISM-4 [1], a published external minimization tool co-authored by an author of this paper, but using it as a benchmark source is not circular; it is independently checkable. The rectangle-covering precursor [14] is by the same group, but this paper re-defines the coverings and algorithms in Sections 3 and 4, so the self-citation is not load-bearing for the correctness or optimality of the new algorithms. The cost table is from Maslov and Dueck [18], an external reference. There is a serious non-circular soundness issue: Section 3.1 stores each degree-2 cube in two symmetric cells (M_{a,b}=M_{b,a}=k), while Definition 4 defines validity per cell; the proof of F=E in Eqs. 13-14 does not account for this duplication, and rectangles with overlapping factor sets introduce diagonal or repeated terms. This undermines the equivalence claim, but it is a mathematical correctness bug, not a circular reduction of the result to its inputs. Therefore the circularity score is 0.

Assumptions & free parameters 3 free parameters · 5 assumptions · 2 invented entities

The central claim does not rest on fitted physical constants; the adjustable parts are algorithmic knobs (F, substitution scoring, inverter counting). The most consequential axiom is that rectangle-derived forms are exhaustive over useful factorizations, which is assumed without proof, and that the self-defined cost model faithfully represents real quantum costs.

free parameters (3)
  • Feasibility bound F = 0.9 default, 0.75 in comparison
    Density threshold for adding rectangles in Algorithm EO; hand-chosen; Table 3 shows it changes the result for rd53f2.
  • Cube substitution score = frequency * degree = heuristic rule
    Used in Section 4.3 to rank which cubes to replace by a new variable when reducing degree; no optimality argument is offered.
  • Negation cost multiplier = 2 inverters per negated literal
    Section 4.4 counts two inverters for every negated variable in a gate; an arbitrary simplification that affects all reported costs.
assumptions (5)
  • standard math Standard Boolean identities (a XOR 1 = NOT a, a XOR a = 0, a AND a = a, a AND NOT a = 0)
    Used in Section 2.2 for algebraic reductions and in Section 3.4 to justify odd/even coverage cancellation.
  • domain assumption Maslov cost table for n-bit Toffoli gates (Ref 18)
    Section 2.4 defines quantum costs by this table; the entire cost comparison rests on this external model.
  • domain assumption The Section 4.4 cost model (ancilla per factor, mirror doubling for oracle) is a faithful representation of realizable quantum costs
    Used for all final cost numbers; not verified by compilation or comparison with other tools.
  • ad hoc to paper Every useful factorization of a degree-2 ESOP corresponds to a set of rectangles in the Section 3.1 matrix
    The method searches only rectangle-derived factored forms (Eq. 10); no completeness proof is given.
  • domain assumption EXORCISM-4 output is the correct initial baseline
    Section 5.1 uses EXORCISM-4 minimized ESOPs as input; reference 1 is co-authored by a paper co-author, so the baseline is partly self-supplied though standard.
invented entities (2)
  • Substitution variables g,h,i,j (e.g. g=acd)
    purpose: Reduce cubes of degree >2 to degree 2 so they fit the matrix; if used more than once, kept as ancilla variables.
    Introduced in Section 4.3, Example 11; they are internal algorithmic artifacts, and the ancilla-vs-substitute decision changes the computed cost.
  • Synthetic cubes filled into empty cells during even-odd covering (e.g. cube 7 = ac in Fig 9b)
    purpose: Allow larger rectangles in Algorithm EO; each synthetic cube appears an even number of times so XOR cancels it.
    Section 3.4, Example 10; these cubes do not exist in the original function but are used to make the covering work.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Factorization of Exclusive-Sum-Of-Products Expressions with Rectangle Covering to Reduce Quantum Circuit Cost." pith.science (2026). https://pith.science/paper/TVVOXWE6

@misc{pith2026260803188,
  author       = {Pith},
  title        = {Pith review of: Factorization of Exclusive-Sum-Of-Products Expressions with Rectangle Covering to Reduce Quantum Circuit Cost},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TVVOXWE6}},
  note         = {Machine review of arXiv:2608.03188}
}
read the original abstract

The implementation of quantum circuits is currently very expensive, especially due to the usage of large Toffoli gates. Therefore, it is critical to optimize circuit costs by factoring expressions as they become more complex. In the proposed algorithms to factor ESOP expressions, each product term is converted into a cell in a 2D matrix, and optimal factored AND/EXOR solutions are determined using Disjoint and Even-Odd Rectangle covering methods. Two Python programs implementing these algorithms were tested and evaluated using well-known benchmarks. The results showed that both the literal counts used in classical logic circuits as well as the Maslov cost used in quantum circuits was reduced by 20%-95% depending on expression size.

Figures

Figures reproduced from arXiv: 2608.03188 by the authors.

Figure 1
Figure 1. Permutative Quantum Gates The Maslov costs of the first few gate sizes is given below in [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Realization of a(b ⊕ c) in Automata vs Oracle circuit The quantum cost of a final circuit is found by summing up the quantum cost of all gates used. To put it all together, we will use an example to summarize the different costs. Example 5 Let us look at ESOP expression E = ab ⊕ ac ⊕ ad ⊕ bc ⊕ bd, which can be algebraically factored as F = ab ⊕ (a ⊕ b)(c ⊕ d). By counting the number of literal instances, including r… view at source ↗
Figure 3
Figure 3. Realization of E and F The quantum circuit for E uses five 3-bit Toffolis, giving a Maslov cost of 5 · M(3) = 25, while the quantum circuit for F uses two 3-bit Toffolis and four CNOT gates, giving a Maslov cost of 2 · M(3) + 4 · M(2) = 14. In this example, the literal count improved by 4, and the Maslov cost improved by 11. As ESOP expressions grow larger, factorization will enable even greater cost improvements. E… view at source ↗
Figures from the paper (8 more)
Figure 4
Figure 4. Figure 4: Automata of After factoring 3.1 Matrix representation of an ESOP expression Given an ESOP expression E composed of n cubes as described in Eq. 1, define the cube index set to be C = {1, 2, . . . , n}, where each k ∈ C is the cube index of the cube ck. We can represent …
Figure 5
Figure 5. Figure 5: Matrix Representation of E 3.2 Rectangles and solution sets In our matrix, we can “cover” cells with rectangles that correspond to factored expressions. We define these rectangle covers below. Definition 2 Given two subsets A, B ⊆ V , a rectangle R is defined as the or…
Figure 6
Figure 6. Figure 6: Examples of Rectangles can see that R1 = ({a, c, d}, {a, b}) contains |CR1 | = 5 filled cells out of 3 · 2 = 6 total circled cells, giving a density of 5 6 = 83.3%. Notice that although cells (b, a) and (b, b) look like they are enclosed within the borders of R1, they …
Figure 7
Figure 7. Figure 7: Disjoint Rectangle Covering Example {1, 2, 3} and CR4 = {4, 5}. We obtain the factored form, F2 = a(b ⊕ c ⊕ d) ⊕ b(c ⊕ d), and we find that κ(F2) = (7, 13, 16), which is more expensive than F1. 3.4 Even-odd rectangle covering In disjoint rectangle covering, we are rest…
Figure 8
Figure 8. Figure 8: Odd Rectangle Covering vs. Disjoint Covering on the same matrix [PITH_FULL_IMAGE:figures/full_fig_p012_8.png]
Figure 9
Figure 9. Figure 9: Even Rectangle Covering vs. Disjoint Covering on the same matrix [PITH_FULL_IMAGE:figures/full_fig_p013_9.png]
Figure 10
Figure 10. Figure 10: Costs Before and After Factorization 21 [PITH_FULL_IMAGE:figures/full_fig_p021_10.png]
Figure 11
Figure 11. Figure 11: Percentage Reduction in Cost as Initial Cost Increases [PITH_FULL_IMAGE:figures/full_fig_p022_11.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

  1. [1]

    Mishchenko and M

    A. Mishchenko and M. Perkowski (2001),Fast Heuristic Minimization of Exclusive Sums-of- Products, RM’2001 Workshop

    work page 2001

  2. [2]

    De Vos (2011),Reversible computing: fundamentals, quantum computing, and applications, John Wiley & Sons

    A. De Vos (2011),Reversible computing: fundamentals, quantum computing, and applications, John Wiley & Sons

    work page 2011

  3. [3]

    J. M. Saul (1991),An Algorithm for the Multi-Level Minimization of Reed-Muller Representations, Proc. IEEE Int. Conf. on Computer Design, pp. 634–637

    work page 1991

  4. [4]

    J. M. Saul (1993),Towards a Mixed Exclusive-/Inclusive-OR Factored Form, Int. Workshop on Applications of the Reed-Muller Expansion in Circuit Design, pp. 1–5

    work page 1993

  5. [5]

    J. M. Saul (1995),Logic Synthesis Based on Exclusive-OR Sums, Proc. Reed-Muller Colloquium. University of Bristol

    work page 1995

  6. [6]

    Chattopadhyay, S

    S. Chattopadhyay, S. Roy, and P. P. Chaudhuri (1997),KGPMIN: An Efficient Multilevel Multi- output AND-OR-XOR Minimizer, IEEE Trans. Computer-Aided Design, Vol. 16, pp. 257–265

    work page 1997

  7. [7]

    L. Tran, A. Gronquist, M. Perkowski, J. Caughman (2016),An improved factorization approach to reversible circuit synthesis based on exors of products of exors, 2016 IEEE 46th International Symposium on Multiple-Valued Logic (ISMVL), pp. 37-43

    work page 2016

  8. [8]

    L. Tran, B. Schaeffer, A. Gronquist, M. Perkowski (2014),Synthesis of reversible circuits based on EXORs of products of EXORs, Transactions on Computational Science XXIV: Special Issue on Reversible Computing, pp. 111-128

    work page 2014

Show all 20 references
  1. [9]

    Rajski and J

    J. Rajski and J. Vesudevamurthy (1992),The Testability-Preserving Concurrent Decomposition and Factorization of Boolean Expressions, IEEE Trans. Computer-Aided Design, Vol 11., pp. 778–793

    1992

  2. [10]

    Tsai and M

    C. Tsai and M. Marek-Sadowska (1996),Multilevel Logic Synthesis for Arithmetic Functions, Proc. Design Automation Conf., pp. 242–247

    1996

  3. [11]

    R. K. Brayton (1987),Factoring Logic Functions, IBM J. Res. Develop., Vol. 31, pp. 187-198

    1987

  4. [12]

    R. K. Brayton and C. McMullen (1982),The Decomposition and Factorization of Boolean Expres- sions, Proc. Int. Symp. Circuits and Systems

    1982

  5. [13]

    R. K. Brayton, R. Rudell, A. Sangiovanni-Vincentelli, and A. Wang (1987),MIS: A Multiple-Level Logic Optimization System, IEEE Trans. Computer-Aided Design, Vol. 6, pp. 1062–1081

    1987

  6. [14]

    Kalay, M

    U. Kalay, M. Perkowski, D. Hall, B. Steinbach, and S. A. Shahjahan (2007),Rectangle Covering Factorization of ESOPs into Scan-Based Levelized Circuits with Universal Test Set, Proc. 4th Int. Workshop on Applications of the Reed-M¨ uller Expansion in Circuit Design

    2007

  7. [15]

    S. Yang, A. Al-Bayaty, M. Perkowski (2026),Minimization of AND-XOR expressions with decoders for quantum circuits, Phys. Rev. A, Vol. 113, pp. 052443

    2026

  8. [16]

    Kumar, M

    M. Kumar, M. Perkowski (2025),Realization of Deterministic Quantum Circuits for Non- Deterministic or Incompletely Specified Quantum State Machines, Quantum Information & Com- putation, Vol. 26, pp. 716

    2025

  9. [17]

    J. M. Henderson, E. R. Henderson, A. Sinha, M. A. Thornton, D. M. Miller (2023),Automated quantum oracle synthesis with a minimal number of qubits, Quantum Information Science, Sensing, and Computation XV, Vol. 12517, pp. 50-67

    2023

  10. [18]

    Maslov, G

    D. Maslov, G. W. Dueck (2003),Improved quantum cost for n-bit Toffoli gates, Electronics Letters, Vol. 39, pp.1790-1791

    2003

  11. [19]

    R. K. Brayton, G. D. Hachtel, C. McMullen, and A. Sangiovanni-Vincentelli (1984),Logic Mini- mization Algorithms for VLSI Synthesis, Kluwer Academic Publishers

    1984

  12. [20]

    Yang (1991),Logic Synthesis and Optimization Benchmarks User Guide Version 3.0, Micro- electronics Center of North Carolina (MCNC)

    S. Yang (1991),Logic Synthesis and Optimization Benchmarks User Guide Version 3.0, Micro- electronics Center of North Carolina (MCNC). 24

    1991

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.