PaperlayerView exact revision on arXiv

Source-linked AI summary

Factorized Boolean representations for efficient quantum synthesis

Mehul Shah, Robert Fiszer, Marek Perkowski

arXiv:2608.27430v1quant-phcs.LO

TL;DR

Boolean minimization can leave product-term structure unused in reversible synthesis, where expression width—not expression size—governs quantum cost. This paper factorizes minimized representations to exploit that structure, reporting median reductions of 42.7% in quantum cost and 28.6% in T-count across 64 functions without increasing either cost.

  • Problem

    Boolean minimization can leave product-term structure unused, while quantum cost is governed by expression width rather than minimized expression size.

    Source: OR, USA · p. 2, Discussion · p. 12

  • Method

    The paper factorizes minimized Boolean representations to exploit relationships among product terms before reversible mapping.

    Source: OR, USA · p. 2, Discussion · p. 12

  • Results

    42.7% median quantum-cost reduction and 28.6% median T-count reduction were reported, with no increase in either cost for any of 64 functions at either stage.

    Source: Results · p. 4

  • Takeaways & Limitations

    Factorized Boolean representation is an optimization layer between logic minimization and circuit-level optimization, complementary rather than competitive with circuit-level optimization.

    Source: Discussion · p. 12

    Individual cells can be too small to contain the structure factorization exploits, so that structure may span cell boundaries.

    Source: Scaling beyond truth-table synthesis · p. 11

Abstract

from arXiv · show

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.

OR, USA

The introduction argues that Boolean representations may contain exploitable structure beyond what expression minimization captures, and that this structure matters before quantum realization. The cost of synthesis can determine whether a computation is executable at all.

OR, USA

  • Factoring a 2,048-bit RSA modulus is estimated to require 2.6 billion Toffoli gates3, illustrating the practical stakes of reducing quantum resource costs.T gates consume a large fraction of projected surface-code qubits and execution time, so synthesis cost can determine executability, not merely runtime.Source: OR, USA · p. 2
  • Existing methods optimize reversible circuits after a Boolean representation is chosen, leaving its pre-realization structure underexplored.The open question is whether the logical representation itself contains structure that can be exploited before quantum realization.Source: OR, USA · p. 2
  • Reducing terms or literals does not necessarily reduce implementation complexity, because minimized expressions can conceal hierarchical relationships among product terms.Those relationships determine what reversible mapping can achieve, so conventional minimization captures only part of the available computational structure.Source: OR, USA · p. 2

Gate arity governs implementation cost

Execution cost is governed by gate arity, not simply gate count or expression size: a few wide gates can dominate because decomposing them requires superlinearly more elementary operations. Factorization can replace wide gates with more narrow ones, producing circuits that are structurally larger but cheaper to execute.

Gate arity governs implementation cost

  • A five-control Toffoli costs an order of magnitude more than a two-control gate because decomposition cost grows superlinearly with control count.The Maslov model charges an n-control gate 2n+1 - 3 elementary operations.Source: Gate arity governs implementation cost · p. 2
  • Conventional synthesis maps each product term to a multi-controlled gate, leaving the widest gate determined by the widest cube in the minimized expression.Reducing term or literal count cannot lower that width; minimization targets expression size, while cost depends on expression width.Source: Gate arity governs implementation cost · pp. 2–3
  • Factorization computes a shared factor once on an auxiliary line, replacing a wide cube with several narrow gates that are individually cheaper.Although the factorized circuit has more gates and is larger by conventional structural measures, superlinear arity costs make it cheaper to execute.Source: Gate arity governs implementation cost · p. 3

Factorized representation framework

The framework extracts shared computation from product terms through containment and complementary-polarity relationships, then realizes the resulting factors with Product-Sum-EXOR gates. In the con1f1 example, factorization lowers quantum cost, T-count, and maximum gate width despite using more gates.

Factorized representation framework

  • Containment lets a smaller product term factor a larger one: b'd ⊕ a'b'cd = b'd(a'c), so the shared factor is evaluated once and the residual is computed onto an auxiliary line.The identity used is X ⊕ XY = X·Y'.Source: Factorized representation framework · p. 3
  • Complementary-polarity terms sharing be' combine as abcde' ⊕ a'be'f = be'(acd ⊕ a'f), replacing five- and four-control gates with gates of three, two, and three controls.The shared factor is be', and the terms differ in the polarity of a.Source: Factorized representation framework · p. 3
  • Product-Sum-EXOR gates compute shared products once and reuse them across related XOR contributions [23-24].Extracted factors are computed onto auxiliary lines that serve as additional controls, and that control is charged in both quantum cost and T-count.Source: Factorized representation framework · p. 3
  • Across all 64 functions evaluated, at most two auxiliary qubits are live at any point, from three-variable functions to hundred-variable functions with six hundred product terms.Auxiliary lines are returned to |0⟩ by measurement-based uncomputation requiring no non-Clifford resources, and are reused across factor groups.Source: Factorized representation framework · p. 3
  • The factorized con1f1 circuit has six gates rather than five, yet quantum cost falls from 141 to 59, T-count from 48 to 36, and the widest gate from five controls to three.The factorized circuit uses two auxiliary qubits.Source: Figure 1 · p. 4

Results

Across 64 Boolean functions, factorization reduced quantum cost and T-count without increasing either at the representation level. The reductions came from exploiting structure to lower gate arity, and the T-count guarantee applies to the stated cost model rather than an executed circuit.

Results

  • All 64 functions passed equivalence checks, exhaustive for functions of at most 20 variables and by random sampling above that.The suite comprised 37 structured benchmarks, 14 randomly generated 100-variable functions with 200–600 product terms, and 13 quantum-algorithm oracles; quantum cost used the Maslov model and T-count used an AND-tree decomposition.Source: Results · p. 4
  • Quantum cost fell for 56 of 64 functions and was unchanged for 8; median quantum-cost reduction was 42.7% and median T-count reduction was 28.6%.No function increased in quantum cost or T-count at either stage. Figure 2b compares T-count for 59 functions with non-zero conventional T-count; five affine functions require no non-Clifford resources in either representation.Source: Results · p. 4, Figure 2 · p. 5
  • Total gate count rose for 51 of 64 functions, while the widest gate decreased for 38 and increased for none; the widest gate fell from 86 controls to 48.This reflects exchanging a few wide gates for many narrow ones rather than eliminating gates, unlike conventional optimization that targets gate or term count.Source: Figure 2 · p. 5, Results · p. 6
  • Median quantum-cost reduction was 61.9% for algorithm oracles, 49.7% for structured benchmarks, and 32.9% for random functions, showing reductions depend on structure rather than size.Random 100-variable functions had essentially no containment relationships, so the containment stage found no merges; the eight unchanged functions were XOR-dominated or single-term and had little multi-controlled logic to factor.Source: Results · p. 5, Figure 2 · p. 5
  • By construction, containment and polarity merges cannot increase T-count under the representation-level cost model, and merges with shared factors longer than one literal strictly lower it.This guarantee is specific to the model: uncomputing auxiliary lines and decomposing multi-controlled gates into Clifford+T changes the accounting for executed circuits.Source: Results · p. 6

Comparison with circuit optimization

After translation and uncomputation, factorization’s T-count advantage shrinks, but PyZX more often yields a lower T-count on factorized circuits than on conventional circuits. Factorization also reduces qubit counts and speeds optimization on the largest completed comparisons.

Comparison with circuit optimization

  • Across 34 completed benchmarks with non-zero T-count, factorization alone reduced executed-circuit T-count by a median of 16.7%, versus 25% at the representation level.Uncomputation accounts for the difference; in 3 of 34 cases, the factorized circuit had higher T-count before further optimization.Source: Comparison with circuit optimization · p. 6
  • PyZX-optimized factorized circuits had lower T-count in 24 of 34 benchmarks versus 5 for conventional circuits, with 5 ties; median reductions were 53.4% versus 42.3%.The median additional reduction attributable to factorization after optimization was 17.8%.Source: Comparison with circuit optimization · pp. 6–7
  • Among seven largest completed comparisons, factorized circuits had lower optimized T-count in every case; median reductions were 51.0% versus PyZX’s 42.8% on conventional circuits.Factorization contributed an additional 247–1,021 T gates of reduction per instance.Source: Comparison with circuit optimization · p. 7, Figure 3 · p. 7
  • For those seven comparisons, factorization reduced qubit count by a median of 32.2% (26.3–46.6%) and made PyZX 1.9- to 8.4-fold faster, exceeding size-based speed predictions in six cases.The optimized-to-unoptimized T-count ratios were nearly constant across representations, consistent with fixed local rewrites rather than circuit-specific exploitation; the reductions therefore combine.Source: Figure 3 · p. 7, Comparison with circuit optimization · p. 8
  • For the widest attempted instance, factorization cut pre-optimization T-count from 10,129 to 8,764 (13.5%) and qubits from 663 to 464 (30.0%); conventional optimization failed within 24 hours.Factorized optimization finished in 13.3 hours at 5,110 T-count, so this instance was excluded from paired comparisons and medians.Source: Comparison with circuit optimization · p. 8
  • Across 46 benchmarks, factorized circuits used fewer qubits in 33, the same number in 10, and more in 3; among improvements, the median reduction was 22.5%.PyZX does not reduce qubit count; examples include rd84f4_100 (138 to 88), mux_185 (88 to 56), and majority7 (67 to 37).Source: Comparison with circuit optimization · p. 8

Application to algorithm oracles

On 13 quantum algorithm oracle instances, factorized representations reduced median quantum cost and T-count relative to conventional synthesis; the evaluated oracles were small Boolean functions, not full algorithm implementations.

Application to algorithm oracles

  • The tested oracles were modular-exponentiation bits, ripple-carry adder output bits, and majority functions, synthesized from their truth tables.These functions were chosen as algorithm-derived oracles rather than curated benchmark functions.Source: Application to algorithm oracles · p. 9
  • Across 13 oracle instances, median reductions were 61.9% in quantum cost and 38.5% in T-count, exceeding the structured benchmark group.Table 1 reports resource reductions relative to conventional synthesis of the same function.Source: Application to algorithm oracles · p. 9, Table 1 · p. 9
  • For two measured output bits of ax mod 33, factorization reduced magic-state consumption from 5,876 to 3,680, a 37% reduction, while exhaustive verification confirmed identical functions.The proportional reduction in magic-state consumption follows because each T gate consumes one distilled magic state under the assumed synthesis model.Source: Application to algorithm oracles · p. 9
  • The instances were small truth-table syntheses, not implementations of algorithms that compose modular arithmetic hierarchically, so the results do not establish behavior at cryptographically relevant scales.The results show exploitable structure in algorithmically derived functions, not only in curated benchmarks.Source: Application to algorithm oracles · pp. 9–10

Scaling beyond truth-table synthesis

The section applies factorization to compositionally generated modular-exponentiation circuits, avoiding truth-table enumeration at circuit scale. Cellwise factorization reduces both measured resource costs across tested widths, while the fixed cell inventory supports a width-independent projection for the same construction.

Scaling beyond truth-table synthesis

  • A 16-bit modular-exponentiation circuit with 619,792 gates on 120 qubits and T-count 955,968 was generated in under one second; measured T-count scaled as modulus width^2.79.At 16 bits, a truth table would require 65,536 rows for one output bit, and at 32 bits more than four billion.Source: Scaling beyond truth-table synthesis · p. 10, Figure 4 · p. 11
  • T-count fell by 6.5%, 7.0%, 7.0%, and 6.7%, while quantum cost fell by 3.3%, 3.0%, 3.0%, and 2.9% at the four tested widths.Each distinct cell was factorized once and weighted by its multiplicity; no cell increased in either measure.Source: Scaling beyond truth-table synthesis · p. 10, Figure 4 · p. 11
  • Only 46 of 541 distinct cells improved, 45 of them three-term cells, because two-term cells offered no improving pair; crossing cell boundaries was not attempted because conversion cost grows exponentially with block width.The authors attribute the smaller reduction relative to the benchmark suite to applying factorization to blocks too small to contain the structure it exploits.Source: Scaling beyond truth-table synthesis · p. 11
  • The invariant per-cell inventory supports projecting the 6.7% T-count reduction measured at eight bits to the same construction at 2,048 bits, not a measurement of a factorized circuit at that width.The compositionally generated circuit contains more cell instances as modulus width grows, while the distinct cell inventory does not.Source: Scaling beyond truth-table synthesis · pp. 11–12, Figure 4 · p. 11

Discussion

Factorized Boolean representations expose exploitable structure that minimization leaves behind, because expression size and quantum cost depend on different properties. Factorization complements circuit-level optimization, though its benefits depend on the function and are smaller in executed circuits than in the representations.

Discussion

  • Minimization reduces expression size, but quantum cost depends on expression width, so minimized expressions can retain exploitable structure.The reported reductions preserve the function and do not alter the minimizer.Source: Discussion · p. 12
  • Factorized Boolean representation is an optimization layer between logic minimization and reversible mapping, taking a conventional minimizer’s output and producing input for a conventional mapper.Source: Discussion · p. 12
  • ZX-calculus optimization achieves a larger T-count reduction on its own than factorization, but a lower final count when applied to factorized representations, without reducing qubit count.The two optimization layers are complementary rather than competitive.Source: Discussion · p. 12
  • Factorization’s algebraic structure is substantial in arithmetic and symmetric functions but negligible in random functions, and its measured benefit is smaller in executed circuits than in their representations.Source: Discussion · p. 12

Methods … Auxiliary qubit accounting

The method factors minimized exclusive-sum-of-products expressions by extracting containment and complementary-polarity relationships, using explicit cost evaluation and matching. It evaluates representation costs under multiple gate models and measures auxiliary-qubit use after uncomputation.

Baseline expression generation

  • EXORCISM-4 version 4.7 with default settings (-q 0, -v 0) produced the baseline expression used both for cost comparison and as factorization input.This shared baseline isolates reductions attributable to the representation change.Source: Baseline expression generation · p. 15

Cube representation

  • Each cube uses two 128-bit words: a value word marks inputs fixed to one, and a mask word marks don't-care positions; containment, overlap, literal counts, and distance use bitwise tests and population counts.Source: Cube representation · p. 15

Factorization procedure

  • Complementary-polarity factorization forms valid pairs from a shared factor and non-empty residuals, then greedily accepts highest-weight edges without reusing a term.Edge weight is the shared-factor literal count; this stage is introduced in this work.Source: Factorization procedure · pp. 15–16
  • Containment merges are chosen by scoring every candidate pair and taking the greatest strictly positive quantum-cost reduction, with ties resolved by smaller cube distance then residual literal count.A containment merge replaces two terms with one, so at most m-1 merges occur.Source: Factorization procedure · p. 15
  • 4(|L|-1) and 4|L| T-count units are saved by containment and polarity merges, respectively; containment saves zero at |L|=1 and is then accepted only if quantum cost falls.For an n-control gate, T-count is 4(n-1); neither substitution increases T-count for any shared factor or residuals.Source: Factorization procedure · p. 16
  • O(m^3) word operations bound containment and O(m^2 log m) bound polarity matching; on 100-variable functions, containment took 4.6 ms at 200 terms, 29 ms at 400, and 112 ms at 600.Polarity matching stayed below 5 ms, keeping total synthesis time for the largest instance well under a second.Source: Factorization procedure · pp. 16–17

Resource models

  • Under auxiliary-aware costs, con1f1 quantum cost falls from 92 to 50 (46%), versus 141 to 59 (58%) under the ancilla-free model; suite median reductions are 27.7% and 35.7%, respectively.Both representations use the same cost function; the auxiliary-aware model grants the baseline auxiliary qubits and assigns an n-control gate cost of O(n).Source: Resource models · p. 17

Auxiliary qubit accounting

  • Two auxiliary lines suffice at peak across all 64 functions; measurement-based uncomputation returns lines to |0⟩ between factor groups so they can be reused.Auxiliary use was measured by recording the simultaneously held lines for each factored term and reporting the circuit peak.Source: Auxiliary qubit accounting · p. 17

Equivalence verification … Code availability

The section documents equivalence and oracle-generation checks, defines the benchmark inputs and bounded circuit-optimization comparison, and identifies the deposited data and synthesis tools.

Equivalence verification

  • All 64 factorized representations passed equivalence checks, using exhaustive evaluation through 20 variables and more than 20,000 random assignments above that.For 100-variable functions, sampling covers a negligible fraction of inputs, so a pass is evidence rather than proof; a failure is conclusive.Source: Equivalence verification · p. 17

Comparison with circuit optimization

  • Executable QASM 2.0 circuits required Clifford+T decomposition and auxiliary-line uncomputation; their T-counts exceeded representation-level model counts under identical PyZX treatment.PyZX 0.10.5 was used for graph reduction and circuit extraction; the 14 hundred-variable functions and six timed-out pairs were outside the reported completed-pair comparison.Source: Comparison with circuit optimization · p. 18
  • Median PyZX runtime was 1.4 s on completed pairs; 6 of 45 submitted pairs timed out on both realizations, while 14 hundred-variable functions were not submitted.Five further oracle instances were optimized under 8- to 24-hour limits and reported separately in Fig. 3.Source: Comparison with circuit optimization · p. 18

Benchmark suite and oracle construction

  • The suite combines 37 structured benchmarks, 14 synthetic 100-variable functions, and 13 oracles; synthetic terms were sampled uniformly across don't-care and both polarities.Synthetic instances used 200, 400, or 600 terms, with duplicates rejected; 560,000 positions had symbol frequencies of 33.40%, 33.23%, and 33.37% and chi-square 2.9 against a uniform null.Source: Benchmark suite and oracle construction · p. 18

Compositional oracle generation

  • Modular-exponentiation oracles were built from controlled modular multipliers and Cuccaro ripple-carry adders, then decomposed into reusable majority/unmajority cells for factorization.Expressions were recovered from blocks by evaluating their wires' assignments and applying a Möbius transform; identical cells were merged and weighted by multiplicity.Source: Compositional oracle generation · pp. 18–19
  • Generated adders, modular adders, and in-place multipliers were checked across exhaustive and randomized or edge-case tests; seven injected fault classes were detected, and ancillas returned to zero.Adder checks included widths up to 64 bits; modular adders and in-place multipliers were verified over every modulus and applicable operand or control value.Source: Compositional oracle generation · p. 19

Data availability

  • Benchmark and oracle specifications, generated expressions, per-function resource tables, and circuit-comparison results including timed-out attempts are available in the deposited repository.The structured benchmarks derive from the RevLib reversible-circuit collection and EPFL logic-synthesis suite.Source: Data availability · p. 19

Code availability

  • The code-availability section identifies the EXORCISM-5 implementation, resource-analysis tool, and equivalence checker.Source: Code availability · p. 20

Funding

The research received no specific grant from any funding agency.

Funding

  • The authors report no specific grant from any funding agency in the public, commercial, or not-for-profit sectors.Source: Funding · p. 20

Related papers

Loading 2608.27430v1…