CS Paper Radar

Computons for Control-Driven Boolean Circuits

Damian Arellanes

cs.LO ·submitted 2026-11-01 12:14 UTC · v2

Abstract

Boolean circuits abstract away from hardware aspects to capture the logical structure and computational behaviour of digital components. Despite their long history of study, their compositional foundations have received comparatively little attention. Building on the theoretical foundations of computons introduced in previous work, we develop a concrete and operationally defined model of high-level computation for control-driven Boolean circuits. We describe colimit-based operators for composing such circuits into sequential, parallel, branching and iterative structures, supported by concrete operational semantics grounded in abstract computing devices. The framework refines the semantics of composition, establishes the algebraic properties of its operators and introduces atomic circuits to support more expressive computation units. We demonstrate the applicability of the proposed framework through examples from propositional logic, biomedicine and electronics, and establish an operational equivalence with respect to classical Boolean circuits through a systematic transformation that accommodates gates of arbitrary arity. By this equivalence, we show that control-driven Boolean circuits are at least as powerful as their classical counterpart. That is, they are capable of non-uniformly computing any Boolean function over inputs of arbitrary length. Implementations in Idris and Java validate the practical realisability of the framework.

Comment
Extended version of the paper "Compositional Control-Driven Boolean Circuits". DOI: 10.1007/978-3-032-22469-9_2

Closest papers

Nearest neighbours by meaning across the whole index.

TRACE: Traversal and Reasoning Algebraic Computing Engine for Formal Hardware Verification

cs.AR ·2026-08-17 ·Jan Kleinekathöfer, Lennart Weingarten, Kamalika Datta, Rolf Drechsler
hot direction similarity 0.65
Abstract

Modern hardware verification of complex circuits relies heavily on the efficiency of formal methods. For complex arithmetic circuits in particular Symbolic Computer Algebra (SCA) engines which represent pseudo-boolean functions using polynomials are crucial. As circuit complexity grows in the age of AI, verification of arithmetic primitives, including Multiplication, Addition, Multiply-Accumulate (MAC), becomes a computational bottleneck. To address this, we introduce TRACE (Traversal and Reasoning Algebraic Computing Engine), a highly efficient framework designed to investigate the intersection of traversal strategies and proof efficiency. Unlike existing SCA tools which are mainly limited to multipliers, TRACE offers a flexible framework for researchers to analyze memory usage and verification time across a wide range of arithmetic circuits (adder, multiplier and MAC). To overcome the state-explosion problem inherent in polynomial expansion, the engine incorporates advanced reduction techniques, including optimized traversal strategies, conflict removal, and polarity-based optimization for compact symbolic representations. Our experimental results show that for optimized MAC, for the first time, TRACE was able to verify previously unverifiable circuits

0.35

A proof-carrying architecture for synthetic genetic logic circuits under stochastic temporal contracts

cs.LO q-bio.MN ·2026-09-27 ·Arman Ferdowsi, Laura Kovacs
similarity 0.62
Abstract

Genetic design automation maps Boolean specifications to regulatory networks and DNA sequences, but a successful mapping does not establish the probability that every output remains correct over time. This paper presents Proof-Carrying Synthetic Biology (PCS-Bio), a formal architecture for acyclic genetic logic circuits operated under fixed inputs. An ideal checker connects Boolean equivalence, sequence and model provenance, local stochastic contracts, and any surrogate-to-target discrepancy bounds. Under explicit semantic and checker assumptions, these obligations imply a joint temporal refinement guarantee without assuming independence among molecular events. Assignment-specific sufficient cubes select the branches needed to prove each output value. This can reduce risk and delay accounting provided that the retained local contracts remain uniform over the physically present but logically masked inputs. The reported evaluation exercises three separate interfaces: an archived Cello execution with sequence reconstruction, a restricted exact rational checker for a synthetic finite-state instance, and diagnostic IEEE~754 binary64 replay. Across 60 deterministic Boolean formula graphs, slicing reduced the worst-assignment risk-charge sum in 55 cases and the maximum accounting delay in 54. These results concern proof accounting and selected implementation components. They do not establish an integrated sequence-bound temporal certificate or physical validation.

0.23

pfoqcompiler: Efficient Compilation of Quantum Control in Recursive First-Order Quantum Programs

cs.PL cs.LOquant-ph ·2026-09-08 ·Mário Silva, Alexandre Guernut, Marco Lewis
similarity 0.61
Abstract

Recursive quantum control allows for simple and concise descriptions of algorithms. However, a naive circuit compilation sequentializes the different branches of the quantum if-statement and results in an exponential increase in circuit depth. Existing techniques can parallelize these branches, but do so at the cost of an exponential number of ancillary qubits. We present pfoqcompiler, a compiler targeting Qiskit for the first-order quantum programming language FOQ that exploits program structure to merge compatible recursive procedure calls across quantum branches. We introduce weaker syntactically-checkable conditions for well-foundedness, recursive halving, and uniformity, while preserving previously demonstrated complexity characterizations. For weakly well-founded bounded-width programs, the compiler produces polynomial-size circuits; weakly recursively halving programs additionally yield polylogarithmic depth, while weak uniformity removes the asymptotic overhead of branch sequentialization.

0.16

Applicative theories can count

cs.LO ·2026-11-07 ·Melissa Antonelli, Marcel Ertel, Eduardo Skapinakis
hot direction similarity 0.60
Abstract

Applicative theories offer a proof-theoretic framework for studying complexity. In this paper, we introduce a family of applicative theories to characterize classes ranging from constant-depth circuits to polynomial space. Our approach relies on a simple axiom scheme, the small variations of which allows to capture various forms of counting and alternation. This leads to highly uniform results. When applied on notation, the scheme captures bit counting, yielding a characterization of the functions computable by constant-depth, polynomial-size threshold circuits ($\textbf{FTC}^0$); when applied lexicographically, it allows for the counting of accepting computations, yielding a characterization of the functions in the counting hierarchy ($\textbf{FCH}$). Increasing the logical complexity of the induction formulas allowed in the scheme, we obtain characterizations of the functions computable by bounded Boolean circuits of logarithmic-depth and polynomial-size ($\textbf{FNC}^1$) and of the functions computable in polynomial space ($\textbf{FPSPACE}$). The latter characterization solves an open problem in the field. Finally, we investigate separation results. While it is unknown whether $\textbf{FNC}^1$ and $\textbf{FCH}$ are different, there is an oracle relative to which (relativized) $\textbf{FNC}^1$ is strictly contained in (relativized) $\textbf{FCH}$. We use this fact to separate the theories characterizing them, by exploring their ability to represent higher-order functionals.

0.29

Certifiably Interpretable Training of ReLU-MLPs for Boolean Tasks with Guaranteed Truth-Table Generalization

cs.LG cs.AIstat.ML ·2026-09-11 ·Hrad Ghoukasian, Anastasis Kratsios
theory similarity 0.60
Abstract · 58 pages, 7 figures, 6 tables

As compute scales, models evolve, and training algorithms advance, our ability to explain the increasingly powerful AI systems they enable is eroding. To help safeguard interpretability, we introduce a specialized training algorithm (MACCHIATO) that jointly constructs (i) an explicitly structured $\operatorname{ReLU}$-MLP from partial truth-table observations and (ii) an explicit Boolean circuit over signed literals with $\{\operatorname{AND},\operatorname{OR},\operatorname{XOR}\}$ gates certifying what its subnetworks compute and how they compose. Intuitively, we iteratively project the residuals of a Boolean function onto low-dimensional $\{\operatorname{AND},\operatorname{OR},\operatorname{XOR}\}$-circuit classes and exactly compile the resulting circuit into a $\operatorname{ReLU}$-MLP; we combine $\operatorname{ReLU}$-MLP circuit compilation, ESPRESSO logic minimization, and influence-based variable selection. Roughly speaking, our interpretability certificate is complemented by a statistical guarantee: under the theorem's influence-recovery conditions, if each of the $m$ stage-wise residuals depends on at most $\log_2(B)$ bits, a sample-splitting variant of our algorithm trained on $T$ observations returns a six-layer $\operatorname{ReLU}$-MLP (counting the input layer) of width $\mathcal{O}(mB)$ with truth-table error $\mathcal{O}\bigl(\sqrt{m(B+\log(m/δ))/T}\bigr)$. On synthetic random-junta tasks, our networks outperform depth- and hidden-width-matched Adam-trained MLPs in several data-sparse or projection-aligned regimes, while the trained ReLU-MLPs are stronger in others. Moreover, in our explicit PyEDA truth-table implementation, the iterative procedure completes in regimes where flat ambient-dimensional ESPRESSO exceeds the three-hour computational budget.

0.49

Factorized Boolean representations for efficient quantum synthesis

cs.LO quant-ph ·2026-08-27 ·Mehul Shah, Robert Fiszer, Marek Perkowski
code/data similarity 0.59
Abstract · 20 pages, 4 figures. Code and data: https://github.com/mehulshah225/Research_Project

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.

0.25

Formulating Uncomputation Beyond Classical Ancilla Use

cs.PL quant-ph ·2026-11-13 ·Bonan Su, Shengyuan Yang
similarity 0.59
Abstract

Ancilla qubits are routinely used to simplify quantum circuit construction and reduce implementation costs, but their use introduces the burden of designing proper uncomputation afterward. To alleviate this, prior work has developed automated uncomputation synthesis based on a computational-basis formulation of ancilla use. However, this formulation is tailored to classically structured ancilla computations. For more general circuits, it may be undefined, yield unintended functionality, or fail to synthesize uncomputation. It therefore falls short of providing a precise and general formulation of uncomputation beyond classical ancilla use. To address these limitations, we propose a new formulation of ancilla use that specifies the operation of each gate through two complementary aspects: (1) the functionality it implements and (2) the transformation it induces on ancilla roles. Based on this specification, we define uncomputation as restoring the initial ancilla role while implementing the identity functionality. This perspective enables a simple Use-first strategy for automatically synthesizing uncomputation in cases both within and beyond the scope of prior approaches. We further develop a complete inference system for reasoning about specifications, together with a derivation-directed procedure for automatically synthesizing efficient uncomputation, enabling systematic uncomputation synthesis even in challenging cases beyond the scope of our automatic strategy.

0.10

Handling JAX

cs.PL ·2026-11-02 ·Oghenevwogaga Ebresafe, Daniel Zheng, Gordon Plotkin, Ningning Xie
similarity 0.59
Abstract

Languages that target hardware accelerators typically expose a restricted, first-order core without recursion or first-class functions, leaving programmers without a principled way to express computational effects. This paper presents a technique for compiling effect handlers to such a constrained target. We introduce a novel translation that statically eliminates effect handlers, and prove that it preserves both typing and semantics. Moreover, we address the challenges of integrating effect handlers with structured control flow, where continuations cannot be constructed statically. The calculus and all our results are fully mechanized in the Lean 4 proof assistant. Finally, we implement our design as a library for JAX, a Python domain-specific language for accelerator programming, and demonstrate its expressiveness through practical case studies.

0.23