Source-linked AI summary
Factorized Boolean representations for efficient quantum synthesis
Mehul Shah, Robert Fiszer, Marek Perkowski
TL;DR
Quantum synthesis traditionally assumes that minimizing a Boolean expression produces the best representation, although minimized expressions can retain exploitable structure. This paper factors that structure using containment and complementary-polarity relationships, reducing wide-gate resources despite increasing operation counts. Across benchmarks and algorithmic oracles, the transformation never increased representation-level cost measures, while executed circuits retained an advantage after uncomputation and optimization.
Problem
Boolean minimization does not determine the ultimate representation for quantum realization, because minimized expressions can retain algebraic structure relevant to implementation cost.
Method
The paper extracts containment and complementary-polarity structure from minimized expressions and factorizes it before reversible-circuit compilation.
Results
Representation-level factorization never increased the measured cost, and circuit-level optimization reached lower final counts when applied to the factorized representation.
Takeaways & Limitations
A computation’s representation is itself an optimizable resource, distinct from logic minimization and circuit-level optimization.
Takeaways & Limitations
Benefits are bounded by the algebraic structure present and are smaller in executed circuits than in the representation-level model.
Abstract
from arXiv · showhide
Quantum algorithms promise advantages beyond classical reach, but running them on error-corrected hardware requires translating Boolean specifications into reversible circuits, and the resources that translation demands determine what is executable. Established methods minimize a Boolean expression and map it to a circuit, assuming the minimized form is best. Here we show that minimized expressions retain algebraic structure minimization cannot reach, arising from containment and complementary-polarity relationships among their terms, and that extracting it yields circuits cheaper to execute despite having more operations. The decisive quantity is not a circuit's operation count but the control count of its widest operation, a superlinear cost; extracting shared factors trades a few wide operations for many narrow ones and reduces qubit count. Across benchmarks and oracles from quantum search and factoring algorithms, at the representation level the transformation never increases either cost measure, a guarantee from its construction. Translation to an executable circuit returns part of that advantage, since auxiliary lines must be uncomputed, yet the factorized circuit still left a leading circuit-level optimizer reaching lower final counts, and faster, than unaided. The representation of a computation is therefore itself a resource, optimizable before compilation and distinct from both logic minimization and circuit-level optimization.
Gate arity governs implementation cost
Quantum implementation cost is governed by gate arity, especially the widest gates, rather than by expression or gate count alone. Factorization exploits this mismatch by replacing wide operations with several narrower ones.
- An n-control Toffoli cannot execute directly and must be decomposed into elementary operations.
- Under the Maslov model, an n-control gate costs 2n+1 - 3 elementary operations, making wide gates disproportionately expensive.A five-control gate costs an order of magnitude more than a two-control gate.
- Conventional synthesis maps each product term independently to a multi-controlled gate, fixing the widest gate by the widest cube.Reducing term count or literal count cannot lower that arity.
- Factorization computes shared factors onto auxiliary lines and uses them as controls, replacing one wide cube with several narrow gates.
- Although the factorized circuit has more gates, superlinear arity costs make the exchange strongly favourable.The decisive cost is dominated by a few widest gates rather than the total number of gates.
Factorized representation framework
The framework extracts shared structure from minimized Boolean expressions using containment and complementary-polarity relationships. Extracted factors are computed on auxiliary lines and reused as controls in the resulting circuit.
- The framework identifies containment and complementary-polarity relationships among product terms and extracts shared factors.
- Containment: Containment occurs when one term’s literals form a subset of another’s, allowing the smaller term to serve as a common factor.
- Containment: For b'd and a'b'cd, factor extraction evaluates the shared factor once and computes residual a'c onto an auxiliary line.
- Complementary polarity: Complementary-polarity factorization combines terms sharing a factor while differing in one or more literal polarities, reducing control structure.
- Each extracted factor is computed onto an auxiliary line that acts as an additional control, with that control included in quantum cost and T-count.
- Measurement-based uncomputation returns auxiliary lines to |0⟩ without non-Clifford resources, and at most two auxiliary qubits are live at once.This bound holds from three-variable functions through hundred-variable functions with 600 product terms.
- For con1f1, factorization increases the gate count from five to six while reducing quantum cost from 141 to 59 and the widest gate from five controls to three.The factorized realization uses two auxiliary qubits.
Results
Across 64 Boolean functions, factorization reduced or preserved representation-level resources, with benefits driven by arity reduction and existing algebraic structure. Executed-circuit accounting recovers some of the advantage after uncomputation and decomposition.
- 64 functions were evaluated across structured benchmarks, randomly generated 100-variable functions, and quantum-algorithm oracles.Quantum cost used the Maslov model, while T-count used an AND-tree decomposition.
- Every factorized representation was functionally equivalent to its originating expression under exhaustive verification up to 20 variables and random sampling above that.
- 42.7% was the median quantum-cost reduction, while 28.6% was the median T-count reduction.
- 49.7% was the median reduction for structured benchmarks, 61.9% for algorithm oracles, and 32.9% for random 100-variable functions.
- 51 of 64 functions gained gates, while the widest gate decreased for 38 and increased for none, falling from 86 controls to 48 at the suite maximum.
- T-count monotonicity is guaranteed by construction under the representation-level model, but executed-circuit accounting changes after auxiliary uncomputation and gate decomposition.
Comparison with circuit optimization
Factorization preserves an advantage after translation into executable circuits, although uncomputation reduces the representation-level savings. It also gives PyZX a better starting representation, improving final counts, qubit usage, and optimization time.
- Across 34 completed benchmarks, factorization reduced T-count by a median of 16.7%, versus 25% predicted at the representation level.Uncomputation accounts for the difference between the executed-circuit and representation-level reductions.
- PyZX reduced T-count by a median of 42.3% on conventional circuits and 53.4% on factorized circuits.The factorized representation produced the lower T-count for 24 of 34 benchmarks, compared with 5 for the conventional representation, with 5 ties.
- After optimization, factorization provided a median additional T-count reduction of 17.8%, functioning as preprocessing rather than competing with circuit optimization.The paper reports this as evidence that the two transformations act on different aspects of the circuit and combine.
- On seven largest completed comparisons, the factorized circuit had lower optimized T-count in every case, while PyZX reduced T-count by medians of 42.8% and 51.0% for conventional and factorized circuits.These comparisons involved instances whose PyZX optimization required more than ten minutes.
- Factorization reduced qubit count in every largest completed comparison by a median of 32.2%, a reduction PyZX did not produce.Across 46 benchmarks, the factorized realization used fewer qubits in 33 cases, was unchanged in 10, and used more in 3.
Application to algorithm oracles
The method was tested on Boolean oracles arising from quantum algorithms, including search- and factoring-related constructions. These algorithmically derived functions showed substantial resource reductions, while the oracle experiments remain small and are not full algorithm implementations.
- Across 13 quantum-algorithm oracle instances, median quantum-cost reduction was 61.9% and median T-count reduction was 38.5%.These reductions exceeded those of the structured benchmark group.
- For four non-degenerate modular-exponentiation output bits, median reductions were 73.2% in quantum cost and 37.9% in T-count.Two additional ax mod 15 bits were degenerate and excluded from the factoring medians.
- Adder output bits yielded a 48.4% median reduction and majority functions a 68.6% median reduction.The reductions are reported relative to conventional synthesis of the same function.
- For two measured ax mod 33 output bits, magic-state consumption fell from 5,876 to 3,680 states, a 37% reduction for identical exhaustively verified functions.Under the synthesis model used, each T gate consumes one distilled magic state, so T-count reductions correspond proportionally to magic-state savings.
- The oracle results show exploitable structure in algorithmically derived functions rather than only curated benchmarks.The experiments synthesize Boolean functions arising in quantum algorithms, not the algorithms themselves.
- The evaluated oracle instances are small and do not establish behavior at cryptographically relevant scales.The paper distinguishes these truth-table-synthesized oracles from hierarchically composed modular arithmetic implementations.
Scaling beyond truth-table synthesis
To extend beyond truth-table synthesis, the method factorizes bounded arithmetic cells and reuses the resulting inventory across larger modular-exponentiation circuits. This establishes scalable construction and width-independent per-cell reductions, but not unrestricted circuit-scale factorization.
- Truth-table synthesis is limited to functions of roughly a dozen variables because the representation requires a table with 2^n rows.At 20 variables, exhaustive evaluation already requires 1,048,576 assignments, and larger oracle widths exceed direct enumeration.
- Measured T-count grew as the 2.79 power of modulus width across the tested range, while compositional generation passed the width beyond which truth-table synthesis was not tractable.The compositional route therefore avoids enumeration at circuit scale.
- The distinct cell inventory remained fixed while cell instances grew with modulus width, producing flat complete-circuit reductions across the tested widths.This supports a scaling property of the compositional construction rather than a larger reduction at increasing width.
- Reductions were concentrated in three-term cells: 45 of 46 improved cells had three product terms, and no two-term cell improved.The transformation needs pairs of terms sharing exploitable structure, which two-term cells rarely provide.
- The compositional route predicts a width-independent 6.7% per-cell reduction at larger widths under the observed invariant inventory, rather than directly measuring those circuits.The paper presents this as a lower bound on what factorization of the composed circuit can deliver.
Discussion
Boolean minimization does not determine the best representation for quantum realization because minimized expressions can retain exploitable algebraic structure. Factorization forms an intermediate optimization layer, complements circuit-level optimization, and yields bounded benefits that depend on the available structure.
- Minimization reduces expression size, whereas quantum cost is governed by expression width, so minimized expressions can retain exploitable structure.
- The transformation reduces costs without altering the minimizer or changing the realized function.
- Factorized Boolean representation consumes a conventional minimizer's output and produces input for a conventional reversible mapper.
- ZX-calculus optimization is complementary rather than competitive: it achieves a larger T-count reduction while factorization still lowers the final count.
- Factorization's benefit is bounded by algebraic structure, substantial in arithmetic and symmetric functions but negligible in random functions, and smaller after circuit execution.
Methods
The method postprocesses minimized exclusive-sum-of-products expressions in two stages: cost-aware containment merging followed by weighted matching of complementary-polarity pairs. Bit-vector representations make the tests efficient, while the construction guarantees that T-count does not increase.
- Baseline exclusive-sum-of-products expressions are generated with EXORCISM-4 and reused as both comparison baselines and factorization inputs.
- Product terms use paired 128-bit value and mask words to encode one-fixed literals and don't-care positions.
- Containment: Stage one repeatedly selects the strictly positive-cost containment merge with greatest reduction, accepting at most m-1 merges.
- Complementary polarity: Stage two builds a weighted graph of valid complementary-polarity pairs and greedily accepts descending-weight edges without reused endpoints.
- Cost guarantee: Containment and polarity substitutions reduce T-count by exactly 4(|L|-1) and 4|L|, respectively, and neither can increase it.
- Complexity: Stage one takes O(m3) word operations and stage two O(m2 log m), with measured stage-one time reaching 112 ms at 600 terms while stage two stays below 5 ms.
Resource models
The evaluation uses identical resource models for conventional and factorized representations, adds an auxiliary-qubit-aware model, verifies equivalence, and measures auxiliary usage and circuit-level optimization across benchmarks and oracles.
- Cost models: Quantum cost is evaluated with the Maslov model, while an auxiliary-qubit-aware model charges an n-control gate as 2(n-2) Toffoli gates with O(n) cost.
- Cost models: Under the auxiliary-qubit-aware model, the median suite reduction is 27.7%, compared with 35.7% under the ancilla-free model.
- Auxiliary usage: The factorized realization uses measurement-based uncomputation to reuse auxiliary lines, requiring a peak of two simultaneous lines across all 64 functions.
- Verification: All 64 functions passed equivalence checks, using exhaustive assignments for functions with at most 20 variables and 20,000 random assignments above that threshold.
- Verification: For 100-variable functions, random sampling covers a negligible fraction of the input space, so a pass is strong evidence rather than proof.
- Evaluation suite: The suite contains 37 structured benchmarks, 14 randomly generated 100-variable functions, and 13 Boolean oracles.
Compositional oracle generation
Compositional oracle generation constructs arithmetic and majority circuits, extracts Boolean expressions from circuit blocks, factorizes repeated cells, and verifies both original and factorized realizations.
- Oracle construction: Modular exponentiation is generated as controlled modular multiplications, while adders use Cuccaro ripple-carry majority and unmajority cells.
- Oracle construction: Registers are one bit wider than the modulus to record subtraction signs, and incompatible moduli are rejected rather than silently mis-synthesized.
- Oracle construction: In-place multiplication uses multiply, controlled-swap, and inverse-multiply, requiring a multiplier coprime to the modulus.
- Verification: Adder verification is exhaustive through eight bits and sampled at larger widths, confirming sums, carry-out, addend preservation, and carry-ancilla restoration.
- Verification: Seven injected fault classes were all detected while the unmodified circuit passed verification.
- Expression extraction: Expressions are extracted from block truth tables with a Mobius transform, and majority/unmajority cells are factorized individually after identical-cell merging.
- Verification: Extracted expressions and factorized cells are checked against direct block simulation and the benchmark-suite equivalence procedure.
- Reproducibility: Benchmark specifications, generated expressions, resource tables, circuit comparisons, and implementation tools are deposited in the cited project repositories.
Funding
The paper reports no specific grant funding from public, commercial, or other agencies.
- The research received no specific grant from any funding agency in the public, commercial, or other sectors.