An order-theoretic circuit syntax and characterisation of the concept lattice

Tein van der Lugt · 2025

Read An order-theoretic circuit syntax and characterisation of the concept lattice by Tein van der Lugt (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-05428.txt.

Introduction

Tein van der Lugt builds a math framework for circuits in a 2025 paper. Circuits are treated as partial orders with inputs and outputs, rather than as strings of symbols. Maps between circuits capture rewriting steps, and in finite cases the paper proves a factorization result for those maps.

Each circuit also has a connectivity pattern between its ports. The concept lattice from formal concept analysis turns out to be the smallest circuit matching any given pattern while receiving maps from all others. A dual construction follows. Readers in quantum causality get a tidy order-based syntax for circuit reasoning.

Catalog record

CREATORTein van der Lugt
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE291 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-05428

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An order-theoretic circuit syntax and characterisation of the concept lattice Tein van der Lugt Abstract We take an order-theoretic approach to circuit (string diagram) syntax, treating a circuit as a partial order with additional input-output structure. We define morphisms between circuits and prove a factorisation theorem showing that these can, in the finite case, be regarded as formalising a notion of syntactical circuit rewrites, with quotient maps in particular corresponding to gate composition. We then consider the connectivity of a circuit, expressed as a binary relation between its inputs and outputs, and characterise the concept lattice from formal concept analysis as the unique smallest circuit that admits morphisms from all other circuits with the same connectivity. This has significance for quantum causality, particularly to the study of causal decompositions of unitary transformations. We close by constructing the circuit characterised by the dual statement. \DeclareSortingNamekeyTemplate \keypart \keypart \keypart \keypart 1 Introduction This paper is about the syntax of circuits , or string diagrams , which describe parallel and sequential compositions of processes in symmetric monoidal categories (SMCs). A particular motivating application for this work, however, lies in causal inference and quantum foundations, where classical or quantum circuits may act as models of causal processes. In this context, the syntax of a circuit—i.e. its ‘shape’—alone implies relevant information about the process (morphism of the SMC) it implements: for example, the absence of a path between an input and an output of the circuit prohibits the flow of causal influence between those systems. Generally, one may wonder about the full class of morphisms in a specified SMC—be it classical probability theory, quantum theory, or any other—that can be expressed by a circuit with a given shape, a type of problem sometimes referred to as causal compatibility . 1 1 1 See e.g. [ 1 ] . In quantum and classical causal modelling, causal structures are often represented by directed acyclic graphs; however, string diagrams may equally well be used [ 2 ] . A circuit shape Q may then be considered ‘at least as expressive’ as a shape P if it can express at least as many morphisms of the SMC. Sometimes, this is the case simply because any circuit with shape P can be rewritten into one with shape Q using purely syntactical operations valid in any SMC, such as composing two or more gates, treating them as a single one; or adding trivial gates and trivial wires. Here, we propose an order-theoretic treatment of circuit syntax and such syntactical rewrites. We then consider the input-output connectivity of a circuit and characterise the concept lattice [ 3 , 4 , 5 ] as the most expressive circuit with a given connectivity. This result has particular relevance to the search for causal decompositions in quantum theory [ 6 , 7 , 8 ] . These are circuit decompositions of a unitary transformation where certain no-influence conditions satisfied by the unitary are reflected in the connectivity of the circuit. While the general existence of such circuit decompositions remains an open problem, the present result demonstrates the existence of a canonical shape for those that do exist—the concept lattice—thereby answering a question posed in [ 6 ] . In upcoming work [ 7 ] this syntactic result is combined with a semantic (operator-algebraic) proof to construct causal decompositions and characterise precisely when a particular type of them exists. This paper is structured as follows. In Section 2 , we propose a definition of a circuit as a partial order P supplemented by two maps {\lambda:A\to P} , \mu:B\to P into it. We also introduce the relevant structure-preserving maps, which we call circuit morphisms . In case A , B , and P are finite, the elements of P can be thought of as gates in a circuit diagram, the elements of A and B as the overall input and output wires, and \lambda,\mu as providing the locations of these wires in the circuit diagram. However, all results in this work, with the exception of Proposition 14 , hold in the infinite case, too. Section 3 examines the structure of circuit morphisms. We recall the theory of quotients of partially ordered sets by compatible congruences studied in [ 9 , 10 , 11 , 12 , 13 ] and show in Theorem 20 that each circuit morphism factorises into a quotient map and a number of other elementary types of morphisms. For the finite case, this section serves to show that circuit morphisms capture an appropriate notion of syntactical circuit rewrites, with quotient maps in particular corresponding to gate composition. Finally, Section 4 focusses on the connectivity of a circuit, which is a binary relation G\subseteq A\times B specifying which inputs can reach which outputs via directed paths through the circuit. We recall from [ 3 ] that out of any given binary relation G\subseteq A\times B one may construct a complete lattice, called the concept lattice in formal concept analysis [ 4 , 5 ] ; supplemented with the natural choice of maps \lambda,\mu into it, it defines a circuit {L_{G}} . Our main result, Theorem 29 , is a characterisation of {L_{G}} as the smallest circuit with connectivity G that admits morphisms from all other circuits with the same connectivity. In the sense described above, this shows in particular that {L_{G}} is most expressive, in terms of SMC morphism expressibility, among all circuits with connectivity G . 2 First definitions A preorder on a set P is a relation \leq\,\subseteq P\times P that is (i) reflexive : \forall p\in P:p\leq p and (ii) transitive : \forall p,q,r\in P:p\leq q\land q\leq r\implies p\leq r ; a (partial) order is one that is also (iii) antisymmetric : \forall p,q\in P:p\leq q\land q\leq p\implies p=q . We write p<q iff p\leq q and p\neq q ; p\mathrel{\#}q iff p\nleq q and q\nleq p ; and p\lessdot q iff p covers q from below, that is, if p<q and there is no r\in P so that p<r<q . Definition 1 . Let A and B be sets. A circuit from A to B is a tuple (P,\leq,\lambda,\mu) of a set P , a partial order \leq on P , and two functions \lambda:A\to P and \mu:B\to P called the input map and output map , respectively. We will often refer to elements of P as gates and to elements of A and B as inputs and outputs , respectively. P may also refer to a circuit itself, rather than only its underlying set; in this case we write \leq or \leq_{P} and \lambda_{P},\mu_{P} for the order and maps constituting the circuit on P . Definition 2 . We call a circuit P finite if the set P as well as the sets A and B are. Finite circuits may be conveniently depicted by diagrams. First of all, the Hasse diagram of the partial order (P,\leq) is the directed acyclic graph on P obtained by drawing an edge from p to q iff p\lessdot q . The elements of P are laid out on the page so that all edges point upward; the latter are then drawn as undirected edges. The circuit diagram of (P,\leq,\lambda,\mu) is obtained by supplementing

Read the complete text