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

• URL: http://arxiv.org/abs/2507.05428v1
• Date: Mon, 07 Jul 2025 19:18:37 GMT
• Title: An order-theoretic circuit syntax and characterisation of the concept lattice
• Abstract summary: We take an order-theoretic approach to circuit (string diagram) syntax, treating a circuit as a partial order with additional input-output structure.<n>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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Many Circuits, One Mechanism: Input Variation and Evaluation Granularity in Circuit Discovery [49.50794188352666]
  We show that structural differences between circuits are not sufficient evidence for distinct mechanisms.<n>Standard evaluation practice obscures this pattern, while edge-level evaluation reveals the many-to-one mapping from structure to function.
  arXiv  Detail & Related papers  (2026-06-04T15:10:14Z)
• From Circuit Evidence to Mechanistic Theory: An Inductive Logic Approach [4.3997570047987775]
  This work provides a formal infrastructure for cumulative mechanistic science by treating circuit interpretation as inductive theory construction.<n>Each circuit is characterised at two levels: a Causal Functional Signature (CFS), which grounds component behaviour in causal attribution evidence, and an architectural signature $_mathrmarch$, learned by inductive logic programming (ILP) from scale-invariant structural predicates.
  arXiv  Detail & Related papers  (2026-05-20T15:33:14Z)
• From Tensor Networks to Tractable Circuits, and back [4.942278642834429]
  We show that some classes of tensor networks that are appealing in practice correspond to classes of circuits with specific properties.<n>In particular, we prove that matrix product states (tensor trains) coincide with nondeterministic edge-valued decision diagrams.
  arXiv  Detail & Related papers  (2026-04-30T18:01:40Z)
• A complete set of transformation rules for reversible circuits [4.640835690336652]
  We propose the first complete set of transformation rules for reversible circuits.<n>We show that every reversible function is computed by a unique reversible circuit in the canonical form.
  arXiv  Detail & Related papers  (2025-08-24T09:45:14Z)
• Generalized Linear Mode Connectivity for Transformers [87.32299363530996]
  A striking phenomenon is linear mode connectivity (LMC), where independently trained models can be connected by low- or zero-loss paths.<n>Prior work has predominantly focused on neuron re-ordering through permutations, but such approaches are limited in scope.<n>We introduce a unified framework that captures four symmetry classes: permutations, semi-permutations, transformations, and general invertible maps.<n>This generalization enables, for the first time, the discovery of low- and zero-barrier linear paths between independently trained Vision Transformers and GPT-2 models.
  arXiv  Detail & Related papers  (2025-06-28T01:46:36Z)
• Position-aware Automatic Circuit Discovery [59.64762573617173]
  We identify a gap in existing circuit discovery methods, treating model components as equally relevant across input positions.<n>We propose two improvements to incorporate positionality into circuits, even on tasks containing variable-length examples.<n>Our approach enables fully automated discovery of position-sensitive circuits, yielding better trade-offs between circuit size and faithfulness compared to prior work.
  arXiv  Detail & Related papers  (2025-02-07T00:18:20Z)
• Expressiveness of Commutative Quantum Circuits: A Probabilistic Approach [1.0864391406042209]
  This study investigates the frame potential and expressiveness of commutative quantum circuits.<n>We express quantum expectation and pairwise fidelity as characteristic functions of random variables, and expressiveness as the recurrence probability of a random walk on a lattice.
  arXiv  Detail & Related papers  (2024-04-30T17:22:33Z)
• Flux-charge symmetric theory of superconducting circuits [0.0]
  We present a theory of circuit quantization that treats charges and flux on a manifestly symmetric footing. For planar circuits, known circuit dualities are a natural canonical transformation on the classical phase space. We discuss the extent to which such circuit dualities generalize to non-planar circuits.
  arXiv  Detail & Related papers  (2024-01-16T18:18:52Z)
• Formal Verification of Zero-Knowledge Circuits [44.99833362998488]
  Zero-knowledge circuits are sets of equality constraints over arithmetic expressions interpreted in a prime field. We make contributions to the problem of ensuring that a circuit correctly encodes a computation.
  arXiv  Detail & Related papers  (2023-11-15T10:47:28Z)
• Causal Interpretation of Self-Attention in Pre-Trained Transformers [4.419843514606336]
  We propose a causal interpretation of self-attention in the Transformer neural network architecture. We use self-attention as a mechanism that estimates a structural equation model for a given input sequence of symbols. We demonstrate this method by providing causal explanations for the outcomes of Transformers in two tasks: sentiment classification (NLP) and recommendation.
  arXiv  Detail & Related papers  (2023-10-31T09:27:12Z)
• Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
  We discuss the problem of bounding partially identifiable queries, such as counterfactuals, in Pearlian structural causal models. A recently proposed iterated EM scheme yields an inner approximation of those bounds by sampling the initialisation parameters. We show how a single symbolic knowledge compilation allows us to obtain the circuit structure with symbolic parameters to be replaced by their actual values.
  arXiv  Detail & Related papers  (2023-10-05T07:10:40Z)
• Circuit complexity and functionality: a thermodynamic perspective [2.2988732018837177]
  We explore links between complexity and thermodynamics for functionally-equivalent circuits.<n>In particular, our framework provides a new perspective on the obfuscation of programs of arbitrary length.<n>We argue that fragmentation is unavoidable unless the complexity classes NP and coNP coincide.
  arXiv  Detail & Related papers  (2023-09-11T18:02:21Z)
• A Complete Equational Theory for Quantum Circuits [58.720142291102135]
  We introduce the first complete equational theory for quantum circuits. Two circuits represent the same unitary map if and only if they can be transformed one into the other using the equations.
  arXiv  Detail & Related papers  (2022-06-21T17:56:31Z)
• LOv-Calculus: A Graphical Language for Linear Optical Quantum Circuits [58.720142291102135]
  We introduce the LOv-calculus, a graphical language for reasoning about linear optical quantum circuits. Two LOv-circuits represent the same quantum process if and only if one can be transformed into the other with the rules of the LOv-calculus.
  arXiv  Detail & Related papers  (2022-04-25T16:59:26Z)
• A Compositional Atlas of Tractable Circuit Operations: From Simple Transformations to Complex Information-Theoretic Queries [44.36335714431731]
  We show how complex inference scenarios for machine learning can be represented in terms of tractable modular operations over circuits. We derive a unified framework for reasoning about tractable models that generalizes several results in the literature and opens up novel tractable inference scenarios.
  arXiv  Detail & Related papers  (2021-02-11T17:26:32Z)
• Hardware-Encoding Grid States in a Non-Reciprocal Superconducting Circuit [62.997667081978825]
  We present a circuit design composed of a non-reciprocal device and Josephson junctions whose ground space is doubly degenerate and the ground states are approximate codewords of the Gottesman-Kitaev-Preskill (GKP) code. We find that the circuit is naturally protected against the common noise channels in superconducting circuits, such as charge and flux noise, implying that it can be used for passive quantum error correction.
  arXiv  Detail & Related papers  (2020-02-18T16:45:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.