Graphical and algebraic methods for Boolean factoring

Priyanka Mukhopadhyay; Simon Martiel

arxiv: 2606.04038 · v1 · pith:4SOFAQ6Mnew · submitted 2026-06-02 · 🪐 quant-ph · cs.DS

Graphical and algebraic methods for Boolean factoring

Simon Martiel , Priyanka Mukhopadhyay This is my paper

Pith reviewed 2026-06-28 10:10 UTC · model grok-4.3

classification 🪐 quant-ph cs.DS

keywords Boolean factoringbiclique coverAND-countESOPSOPreversible circuitsHorner methodquantum circuits

0 comments

The pith

Modeling Boolean factoring as minimum biclique cover of a bipartite graph yields up to five times fewer AND operations than EXORCISM-4.

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

The paper introduces graphical and algebraic algorithms for factoring Boolean polynomials in ESOP and SOP form with the goal of minimizing AND-count. The graphical method encodes the polynomial as a bipartite graph and solves a minimum biclique cover problem whose solution directly supplies a factored form with fewer ANDs. The algebraic method adapts the multivariate Horner scheme for faster execution. Tests on random functions of at most twelve variables show the biclique approach produces up to a fivefold reduction in AND-count relative to EXORCISM-4 while the Horner variant runs substantially faster than prior algebraic tools. Lower AND-count translates into fewer AND or Toffoli gates when the expression is mapped to classical or quantum reversible circuits.

Core claim

We reduce the problem of factoring Boolean polynomials to covering a bipartite graph with bicliques, where each biclique corresponds to a shared factor, and we also derive an algebraic method from the multivariate Horner scheme; both target lower AND-count. On random instances with up to twelve variables the biclique-based algorithm achieves up to five times fewer ANDs than EXORCISM-4.

What carries the argument

Minimum biclique cover of the bipartite graph whose edges encode the monomials of the input polynomial; each biclique identifies a common subexpression that can be factored out to reduce total AND operations.

If this is right

Fewer AND operations produce fewer Toffoli gates when the factored form is realized in reversible or quantum circuits.
Any existing biclique-cover heuristic or exact solver can be substituted into the graphical method to trade speed against solution quality.
The Horner-derived algebraic routine supplies a fast polynomial-time preprocessing step that can be combined with the biclique method.
Both algorithms apply unchanged to both sum-of-products and exclusive-sum-of-products representations.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If the observed reductions hold on circuit-derived functions, the method could tighten resource estimates for quantum algorithms whose oracles are specified by Boolean polynomials.
Structured functions may contain larger bicliques than random ones, suggesting that the reported savings could increase on real instances.
The graph-theoretic formulation allows direct importation of approximation algorithms from the biclique-cover literature to obtain provable bounds on AND-count.
Extending the experiments beyond twelve variables would require efficient approximation algorithms for the minimum biclique cover problem.

Load-bearing premise

The AND-count reductions measured on random functions of at most twelve variables will also appear on the structured Boolean functions that arise in actual reversible and quantum circuit designs.

What would settle it

Apply the biclique-cover algorithm to a standard collection of reversible-circuit benchmark functions with more than twelve variables and check whether the average AND-count improvement over EXORCISM-4 remains at least a factor of two.

Figures

Figures reproduced from arXiv: 2606.04038 by Priyanka Mukhopadhyay, Simon Martiel.

**Figure 2.** Figure 2: AND counts of the final expressions obtained by running different heuristics on random [PITH_FULL_IMAGE:figures/full_fig_p023_2.png] view at source ↗

**Figure 3.** Figure 3: Running time of the different heuristics on random truth tables. Each point is averaged [PITH_FULL_IMAGE:figures/full_fig_p024_3.png] view at source ↗

read the original abstract

The problem of factoring Boolean polynomials has significant applications in both classical and quantum computing technology. In this paper we have developed novel algorithms for factoring both ESOP and SOP expressions. Our aim is to optimize the AND-count. The AND-count plays a key role in determining the number of AND and Toffoli gates required to implement a reversible function with classical and quantum circuits, respectively. The first type of algorithms that we develop, are graphical. We reduce the problem of Boolean factoring to covering a bipartite graph with bicliques, and so optimizing the number of bicliques required to cover the bipartite graph, leads to reduced number of factors, and hence AND-count. The second type of algorithm is algebraic, and is derived from multivariate Horner method. We have compared the performances of our algorithms with existing popular methods like EXORCISM-4 and EPOEM2, on random functions of up to 12 variables. We have observed that our multivariate Horner method is substantially faster, while our biclique-based method achieves the maximum AND-count reduction. In fact, compared to EXORCISM-4 our biclique based method achieves up to 5 times reduction in AND-count.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The biclique reduction is a clean new framing for AND-count minimization and the Horner variant runs faster, but the 5x gains are shown only on random functions.

read the letter

The biclique-cover reduction for Boolean factoring and the multivariate Horner adaptation are the actual new pieces. Framing the problem as covering a bipartite graph with bicliques gives a direct handle on the number of factors, and the paper shows this can cut AND-count by up to 5 times versus EXORCISM-4 on the random instances they tried. The Horner method is mainly presented as faster, which is a practical plus if runtime matters more than the absolute minimum.

They do a straightforward job of linking the work to reversible and quantum circuit costs, where AND-count controls Toffoli and AND gate counts. The comparisons to EXORCISM-4 and EPOEM2 are explicit and the reported edge on the test set is clear.

The main limitation is that every number comes from random Boolean functions of at most 12 variables. The motivation is synthesis for real circuits, which are usually structured, yet there are no results or even discussion of arithmetic or control functions. That gap means the observed advantage might not transfer, exactly as the stress-test note flags. The abstract also gives no pseudocode or complexity details for the biclique solver itself, so it is hard to judge how the method scales or whether the cover is exact.

This paper is for people already working on logic synthesis for quantum or reversible circuits. A reader looking for new heuristics or alternative formulations would find the biclique angle worth trying. It is coherent on its own terms and engages the existing tools honestly, so it deserves a serious referee even though the generalization question needs to be addressed.

Referee Report

1 major / 1 minor

Summary. The paper develops two families of algorithms for factoring Boolean polynomials (ESOP and SOP forms) to minimize AND-count: (1) a graphical method that reduces the problem to minimum biclique cover of a bipartite graph derived from the polynomial, and (2) an algebraic method obtained by extending the multivariate Horner scheme. On random Boolean functions of up to 12 variables the biclique method is reported to produce up to 5× lower AND-count than EXORCISM-4 while the Horner variant is faster than EPOEM2; the work is motivated by the need to reduce AND/Toffoli gate counts in reversible and quantum circuit synthesis.

Significance. If the biclique-cover formulation is correct and the observed reductions generalize beyond random instances, the graphical approach supplies a new, potentially exact or near-exact combinatorial handle on AND-count minimization that could improve synthesis flows for reversible and quantum circuits. The explicit mapping to bipartite biclique cover is a clean and reusable modeling contribution.

major comments (1)

[Experimental results / abstract performance claims] The experimental evaluation (reported in the abstract and presumably detailed in the results section) is performed exclusively on random Boolean functions of ≤12 variables. The introduction motivates the work by the need to optimize AND-count for structured functions that arise in reversible/quantum circuit synthesis (arithmetic circuits, control logic, etc.), yet no benchmarks, discussion, or even synthetic structured instances are supplied. This leaves open whether the reported 5× reduction is an artifact of the random ensemble and therefore undermines the practical claim.

minor comments (1)

[Abstract] The abstract states concrete performance numbers (“up to 5 times reduction”) without any indication of the test-suite size, how the random functions were generated, or whether the figure is a maximum, average, or median; a short protocol sentence would make the claim reproducible from the abstract alone.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for highlighting the gap between the motivating applications and the experimental benchmarks. We address the concern directly below and agree that additional discussion is warranted.

read point-by-point responses

Referee: [Experimental results / abstract performance claims] The experimental evaluation (reported in the abstract and presumably detailed in the results section) is performed exclusively on random Boolean functions of ≤12 variables. The introduction motivates the work by the need to optimize AND-count for structured functions that arise in reversible/quantum circuit synthesis (arithmetic circuits, control logic, etc.), yet no benchmarks, discussion, or even synthetic structured instances are supplied. This leaves open whether the reported 5× reduction is an artifact of the random ensemble and therefore undermines the practical claim.

Authors: We agree that the introduction emphasizes applications to structured functions arising in reversible and quantum circuit synthesis, while the reported experiments use only random Boolean functions up to 12 variables. Random instances constitute a standard, structure-free benchmark that tests the algorithms under worst-case conditions without domain-specific regularities that could be exploited by heuristics. The biclique-cover formulation itself is function-agnostic and applies equally to any ESOP or SOP polynomial, including those derived from arithmetic circuits or control logic. Nevertheless, the referee is correct that the absence of any structured examples or discussion leaves the practical relevance for the motivating use cases unaddressed. In the revised manuscript we will add a dedicated subsection that (i) explains the choice of random benchmarks, (ii) illustrates how the bipartite-graph construction and Horner extension can be applied to structured polynomials (with at least two small synthetic arithmetic examples), and (iii) qualifies the 5× claim as observed on random ensembles while noting that further validation on circuit-derived benchmarks is future work. revision: yes

Circularity Check

0 steps flagged

No circularity: empirical performance claims rest on external benchmarks, not self-referential derivations

full rationale

The paper introduces biclique-covering and multivariate Horner algorithms for Boolean factoring, then reports measured AND-count reductions versus external tools (EXORCISM-4, EPOEM2) on random instances. These outcomes are experimental results, not quantities derived by construction from the paper's own equations or fitted parameters. No self-definitional steps, fitted-input predictions, or load-bearing self-citations appear; the central claim remains an independent empirical observation on the tested ensemble.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review supplies no explicit free parameters, axioms, or invented entities; the biclique-cover formulation implicitly assumes that minimum biclique cover equals minimum AND-count, but this modeling choice is not audited here.

pith-pipeline@v0.9.1-grok · 5731 in / 1116 out tokens · 17749 ms · 2026-06-28T10:10:20.107527+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

14 extracted references · 2 linked inside Pith

[1]

Post-quantum zero-knowledge and signatures from symmetric-key primitives

[CDG+17] Melissa Chase, David Derler, Steven Goldfeder, Claudio Orlandi, Sebastian Ra- macher, Christian Rechberger, Daniel Slamanig, and Greg Zaverucha. Post-quantum zero-knowledge and signatures from symmetric-key primitives. InProceedings of the 2017 ACM Sigsac Conference on Computer and Communications Security, pages 1825–1842,

2017
[2]

On the Efficient Discovery of Maximum k-Defective Biclique.arXiv preprint arXiv:2506.16121,

[CLD+25] Donghang Cui, Ronghua Li, Qiangqiang Dai, Hongchao Qin, and Guoren Wang. On the Efficient Discovery of Maximum k-Defective Biclique.arXiv preprint arXiv:2506.16121,

arXiv
[3]

The Solovay-Kitaev algorithm.arXiv preprint quant-ph/0505030,

[DN05] Christopher M Dawson and Michael A Nielsen. The Solovay-Kitaev algorithm.arXiv preprint quant-ph/0505030,

Pith/arXiv arXiv
[4]

Coalgebraic division for multilevel logic synthesis

[HS92] Wen-Jun Hsu and Wen-Zen Shen. Coalgebraic division for multilevel logic synthesis. In[1992] Proceedings 29th ACM/IEEE Design Automation Conference, pages 438–

1992
[5]

Lowering the T-depth of quantum circuits by re- ducing the multiplicative depth of logic networks.arXiv preprint arXiv:2006.03845,

[HS20] Thomas H¨ aner and Mathias Soeken. Lowering the T-depth of quantum circuits by re- ducing the multiplicative depth of logic networks.arXiv preprint arXiv:2006.03845,

arXiv 2006
[6]

Evaluating ESOP optimization methods in quantum compilation flows

[MSE+19] Giulia Meuli, Bruno Schmitt, R¨ udiger Ehlers, Heinz Riener, and Giovanni De Micheli. Evaluating ESOP optimization methods in quantum compilation flows. InReversible Computation: 11th International Conference, RC 2019, Lausanne, Switzerland, June 24–25, 2019, Proceedings 11, pages 191–206. Springer,

2019
[7]

Synthesizing Toffoli-optimal quantum circuits for arbi- trary multi-qubit unitaries.arXiv preprint arXiv:2401.08950,

[Muk24] Priyanka Mukhopadhyay. Synthesizing Toffoli-optimal quantum circuits for arbi- trary multi-qubit unitaries.arXiv preprint arXiv:2401.08950,

arXiv
[8]

Determining the multiplicative complexity of boolean functions using sat.arXiv preprint arXiv:2005.01778,

[Soe20] Mathias Soeken. Determining the multiplicative complexity of boolean functions using sat.arXiv preprint arXiv:2005.01778,

arXiv 2005
[9]

Logic synthesis for quantum computing.arXiv preprint arXiv:1706.02721,

[SRWDM17] Mathias Soeken, Martin Roetteler, Nathan Wiebe, and Giovanni De Micheli. Logic synthesis for quantum computing.arXiv preprint arXiv:1706.02721,

Pith/arXiv arXiv
[10]

On finding the maximum edge biclique in a bipartite graph: a subspace clustering approach

20 [SYL16] Eran Shaham, Honghai Yu, and Xiao-Li Li. On finding the maximum edge biclique in a bipartite graph: a subspace clustering approach. InProceedings of the 2016 SIAM International Conference on Data Mining, pages 315–323. SIAM,

2016
[11]

Reducing the multiplicative complexity in logic networks for cryptography and security ap- plications

[TSADM19] Eleonora Testa, Mathias Soeken, Luca Amar` u, and Giovanni De Micheli. Reducing the multiplicative complexity in logic networks for cryptography and security ap- plications. InProceedings of the 56th Annual Design Automation Conference 2019, pages 1–6,

2019
[12]

A logic synthesis toolbox for reducing the multiplicative complexity in logic networks

[TSR+20] Eleonora Testa, Mathias Soeken, Heinz Riener, Luca Gaetano Amar` u, and Giovanni De Micheli. A logic synthesis toolbox for reducing the multiplicative complexity in logic networks. InProceedings Of The 2020 Design, Automation & Test In Europe Conference & Exhibition (Date 2020), pages 568–573. IEEE,

2020
[13]

How to generate and exchange secrets

[Yao86] Andrew Chi-Chih Yao. How to generate and exchange secrets. In27th Annual Sym- posium on Foundations of Computer Science (SFCS 1986), pages 162–167. IEEE,

1986
[14]

(b) The tree, after ESOP-FACTOR-TYPE-I

is a XOR-node and the leaves are the summand monomials. (b) The tree, after ESOP-FACTOR-TYPE-I. The children of each XOR node at level 2, form a factor. (c) The equivalent tree of (b), where each sub-tree rooted at level-2 XOR node, is replaced by equivalent expression. (d) The tree, after applying ESOP-FACTOR-TYPE-II. Again, the leaves of each XOR-subtre...

2000

[1] [1]

Post-quantum zero-knowledge and signatures from symmetric-key primitives

[CDG+17] Melissa Chase, David Derler, Steven Goldfeder, Claudio Orlandi, Sebastian Ra- macher, Christian Rechberger, Daniel Slamanig, and Greg Zaverucha. Post-quantum zero-knowledge and signatures from symmetric-key primitives. InProceedings of the 2017 ACM Sigsac Conference on Computer and Communications Security, pages 1825–1842,

2017

[2] [2]

On the Efficient Discovery of Maximum k-Defective Biclique.arXiv preprint arXiv:2506.16121,

[CLD+25] Donghang Cui, Ronghua Li, Qiangqiang Dai, Hongchao Qin, and Guoren Wang. On the Efficient Discovery of Maximum k-Defective Biclique.arXiv preprint arXiv:2506.16121,

arXiv

[3] [3]

The Solovay-Kitaev algorithm.arXiv preprint quant-ph/0505030,

[DN05] Christopher M Dawson and Michael A Nielsen. The Solovay-Kitaev algorithm.arXiv preprint quant-ph/0505030,

Pith/arXiv arXiv

[4] [4]

Coalgebraic division for multilevel logic synthesis

[HS92] Wen-Jun Hsu and Wen-Zen Shen. Coalgebraic division for multilevel logic synthesis. In[1992] Proceedings 29th ACM/IEEE Design Automation Conference, pages 438–

1992

[5] [5]

Lowering the T-depth of quantum circuits by re- ducing the multiplicative depth of logic networks.arXiv preprint arXiv:2006.03845,

[HS20] Thomas H¨ aner and Mathias Soeken. Lowering the T-depth of quantum circuits by re- ducing the multiplicative depth of logic networks.arXiv preprint arXiv:2006.03845,

arXiv 2006

[6] [6]

Evaluating ESOP optimization methods in quantum compilation flows

[MSE+19] Giulia Meuli, Bruno Schmitt, R¨ udiger Ehlers, Heinz Riener, and Giovanni De Micheli. Evaluating ESOP optimization methods in quantum compilation flows. InReversible Computation: 11th International Conference, RC 2019, Lausanne, Switzerland, June 24–25, 2019, Proceedings 11, pages 191–206. Springer,

2019

[7] [7]

Synthesizing Toffoli-optimal quantum circuits for arbi- trary multi-qubit unitaries.arXiv preprint arXiv:2401.08950,

[Muk24] Priyanka Mukhopadhyay. Synthesizing Toffoli-optimal quantum circuits for arbi- trary multi-qubit unitaries.arXiv preprint arXiv:2401.08950,

arXiv

[8] [8]

Determining the multiplicative complexity of boolean functions using sat.arXiv preprint arXiv:2005.01778,

[Soe20] Mathias Soeken. Determining the multiplicative complexity of boolean functions using sat.arXiv preprint arXiv:2005.01778,

arXiv 2005

[9] [9]

Logic synthesis for quantum computing.arXiv preprint arXiv:1706.02721,

[SRWDM17] Mathias Soeken, Martin Roetteler, Nathan Wiebe, and Giovanni De Micheli. Logic synthesis for quantum computing.arXiv preprint arXiv:1706.02721,

Pith/arXiv arXiv

[10] [10]

On finding the maximum edge biclique in a bipartite graph: a subspace clustering approach

20 [SYL16] Eran Shaham, Honghai Yu, and Xiao-Li Li. On finding the maximum edge biclique in a bipartite graph: a subspace clustering approach. InProceedings of the 2016 SIAM International Conference on Data Mining, pages 315–323. SIAM,

2016

[11] [11]

Reducing the multiplicative complexity in logic networks for cryptography and security ap- plications

[TSADM19] Eleonora Testa, Mathias Soeken, Luca Amar` u, and Giovanni De Micheli. Reducing the multiplicative complexity in logic networks for cryptography and security ap- plications. InProceedings of the 56th Annual Design Automation Conference 2019, pages 1–6,

2019

[12] [12]

A logic synthesis toolbox for reducing the multiplicative complexity in logic networks

[TSR+20] Eleonora Testa, Mathias Soeken, Heinz Riener, Luca Gaetano Amar` u, and Giovanni De Micheli. A logic synthesis toolbox for reducing the multiplicative complexity in logic networks. InProceedings Of The 2020 Design, Automation & Test In Europe Conference & Exhibition (Date 2020), pages 568–573. IEEE,

2020

[13] [13]

How to generate and exchange secrets

[Yao86] Andrew Chi-Chih Yao. How to generate and exchange secrets. In27th Annual Sym- posium on Foundations of Computer Science (SFCS 1986), pages 162–167. IEEE,

1986

[14] [14]

(b) The tree, after ESOP-FACTOR-TYPE-I

is a XOR-node and the leaves are the summand monomials. (b) The tree, after ESOP-FACTOR-TYPE-I. The children of each XOR node at level 2, form a factor. (c) The equivalent tree of (b), where each sub-tree rooted at level-2 XOR node, is replaced by equivalent expression. (d) The tree, after applying ESOP-FACTOR-TYPE-II. Again, the leaves of each XOR-subtre...

2000