Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2512.20587

Quantum Gates from Wolfram Model Multiway Rewriting Systems

Furkan Semih Dündar, Xerxes D. Arsiwalla, Hatem Elshatlawy

quant-phcs.DMmath-phmath.QASubmitted Dec 23, 2025• Announced Dec 24, 2025• 1 citation
arXivHTMLPDF

Abstract

We show how representations of finite-dimensional quantum operators can be constructed using nondeterministic rewriting systems. In particular, we investigate Wolfram model multiway rewriting systems based on string substitutions. Multiway systems were proposed by S. Wolfram as generic model systems for multicomputational processes, emphasizing their significance as a foundation for modeling complexity, nondeterminism, and branching structures of measurement outcomes. Here, we investigate a specific class of multiway systems based on cyclic character strings with a neighborhood constraint - the latter called Leibnizian strings. We show that such strings exhibit a Fermi-Dirac distribution for expectation values of occupation numbers of character neighborhoods. A Leibnizian string serves as an abstraction of a $N$-fermion system. A multiway system of these strings encodes causal relations between rewriting events in a nondeterministic manner. The collection of character strings realizes a $\mathbb{Z}$-module with a symmetric $\mathbb{Z}$-bilinear form. For discrete spaces, this generalizes the notion of an inner product over a vector field. This admits a discrete analogue of the path integral and a $S$-matrix for multiway systems of Leibnizian strings. The elements of this $S$-matrix yield transition amplitudes between states of the multiway system based on an action defined over a sequence of Leibnizian strings. We then show that these $S$-matrices give explicit representations of quantum gates for qubits and qudits, and also circuits composed of such gates. We find that, as formal models of nondeterministic computation, rewriting systems of Leibnizian strings with causal structure encode representations of the CNOT, $π/8$, and Hadamard gates. Hence, using multiway systems one can represent quantum circuits for qubits.

Comments
39 pages, 15 figures

Related papers

ZX-Calculus and Extended Hypergraph Rewriting Systems I: A Multiway Approach to Categorical Quantum Information Theory

Jonathan Gorard, Manojna Namuduri, Xerxes D. Arsiwalla

Categorical quantum mechanics and the Wolfram model offer distinct but complementary approaches to studying the relationship between diagrammatic rewriting systems over combinatorial structures and the foundations of physics; the objective of the present article is to begin elucidating the formal correspondence between the two methodologies in the context of the ZX-calculus formalism of Coecke and Duncan for reasoning diagrammatically about linear maps between qubits. After briefly summarizing the relevant formalisms, and presenting a categorical formulation of the Wolfram model in terms of adhesive categories and double-pushout rewriting systems, we illustrate how the diagrammatic rewritings of the ZX-calculus can be embedded and realized within the broader context of Wolfram model multiway systems, and illustrate some of the capabilities of the software framework (ZXMultiwaySystem) that we have developed specifically for this purpose. Finally, we present a proof (along with an explicitly computed example) based on the methods of Dixon and Kissinger that the multiway evolution graphs and branchial graphs of the Wolfram model are naturally endowed with a monoidal structure based on rulial composition that is, furthermore, compatible with the monoidal product of ZX-diagrams.

arXiv:2010.02752•Oct 5, 2020•30 citations

ZX-Calculus and Extended Wolfram Model Systems II: Fast Diagrammatic Reasoning with an Application to Quantum Circuit Simplification

Jonathan Gorard, Manojna Namuduri, Xerxes D. Arsiwalla

This article presents a novel algorithmic methodology for performing automated diagrammatic deductions over combinatorial structures, using a combination of modified equational theorem-proving techniques and the extended Wolfram model hypergraph rewriting formalism developed by the authors in previous work. We focus especially upon the application of this new algorithm to the problem of automated circuit simplification in quantum information theory, using Wolfram model multiway operator systems combined with the ZX-calculus formalism for enacting fast diagrammatic reasoning over linear transformations between qubits. We show how to construct a generalization of the deductive inference rules for Knuth-Bendix completion in which equation matches are selected on the basis of causal edge density in the associated multiway system, before proceeding to demonstrate how to embed the higher-order logic of the ZX-calculus rules within this first-order equational framework. After showing explicitly how the (hyper)graph rewritings of both Wolfram model systems and the ZX-calculus can be effectively realized within this formalism, we proceed to exhibit comparisons of time complexity vs. proof complexity for this new algorithmic approach when simplifying randomly-generated Clifford circuits down to pseudo-normal form, as well as when reducing the number of T-gates in randomly-generated non-Clifford circuits, with circuit sizes ranging up to 3000 gates, illustrating that the method performs favorably in comparison with existing circuit simplification frameworks, and also exhibiting the approximately quadratic speedup obtained by employing the causal edge density optimization. Finally, we present a worked example of an automated proof of correctness for a simple quantum teleportation protocol, in order to demonstrate more clearly the internal operations of the theorem-proving procedure.

arXiv:2103.15820•Mar 29, 2021•27 citations

Completeness of the ZH-calculus

Miriam Backens, Aleks Kissinger, Hector Miller-Bakewell +2 more

There are various gate sets used for describing quantum computation. A particularly popular one consists of Clifford gates and arbitrary single-qubit phase gates. Computations in this gate set can be elegantly described by the ZX-calculus, a graphical language for a class of string diagrams describing linear maps between qubits. The ZX-calculus has proven useful in a variety of areas of quantum information, but is less suitable for reasoning about operations outside its natural gate set such as multi-linear Boolean operations like the Toffoli gate. In this paper we study the ZH-calculus, an alternative graphical language of string diagrams that does allow straightforward encoding of Toffoli gates and other more complicated Boolean logic circuits. We find a set of simple rewrite rules for this calculus and show it is complete with respect to matrices over Z[12] , which correspond to the approximately universal Toffoli+Hadamard gateset. Furthermore, we construct an extended version of the ZH-calculus that is complete with respect to matrices over any ring R where 1+1 is not a zero-divisor.

arXiv:2103.06610•Compositionality•Jul 12, 2023•22 citations

A diagrammatic calculus of fermionic quantum circuits

Giovanni de Felice, Amar Hadzihasanovic, Kang Feng Ng

We introduce the fermionic ZW calculus, a string-diagrammatic language for fermionic quantum computing (FQC). After defining a fermionic circuit model, we present the basic components of the calculus, together with their interpretation, and show how the main physical gates of interest in FQC can be represented in our language. We then list our axioms, and derive some additional equations. We prove that the axioms provide a complete equational axiomatisation of the monoidal category whose objects are systems of finitely many local fermionic modes (LFMs), with maps that preserve or reverse the parity of states, and the tensor product as monoidal product. We achieve this through a procedure that rewrites any diagram in a normal form. As an example, we show how the statistics of a fermionic Mach-Zehnder interferometer can be calculated in the diagrammatic language. We conclude by giving a diagrammatic treatment of the dual-rail encoding, a standard method in optical quantum computing used to perform universal quantum computation.

arXiv:1801.01231•Logical Methods in Computer Science•Sep 2, 2019•20 citations

Pictures of Processes: Automated Graph Rewriting for Monoidal Categories and Applications to Quantum Computing

Aleks Kissinger

This work is about diagrammatic languages, how they can be represented, and what they in turn can be used to represent. More specifically, it focuses on representations and applications of string diagrams. String diagrams are used to represent a collection of processes, depicted as "boxes" with multiple (typed) inputs and outputs, depicted as "wires". If we allow plugging input and output wires together, we can intuitively represent complex compositions of processes, formalised as morphisms in a monoidal category. [...] The first major contribution of this dissertation is the introduction of a discretised version of a string diagram called a string graph. String graphs form a partial adhesive category, so they can be manipulated using double-pushout graph rewriting. Furthermore, we show how string graphs modulo a rewrite system can be used to construct free symmetric traced and compact closed categories on a monoidal signature. The second contribution is in the application of graphical languages to quantum information theory. We use a mixture of diagrammatic and algebraic techniques to prove a new classification result for strongly complementary observables. [...] We also introduce a graphical language for multipartite entanglement and illustrate a simple graphical axiom that distinguishes the two maximally-entangled tripartite qubit states: GHZ and W. [...] The third contribution is a description of two software tools developed in part by the author to implement much of the theoretical content described here. The first tool is Quantomatic, a desktop application for building string graphs and graphical theories, as well as performing automated graph rewriting visually. The second is QuantoCoSy, which performs fully automated, model-driven theory creation using a procedure called conjecture synthesis.

arXiv:1203.0202•Mar 1, 2012•68 citations

Unitary States and Gates of Three-Qubit Quantum Systems

Mars B. Gabbassov, Tolybay Z. Kuanov, Berik I. Tuleuov +1 more

Pure states of three-qubit quantum systems are represented by eight-dimensional complex vectors, whereas their unitary transformations are described by $8 \times 8$ complex matrices. Motivated by this correspondence, we extend our algebraic model for two-qubit systems to eight-dimensional spaces endowed with commutative and associative multiplication. To each eight-dimensional number we assign a matrix and prove that the resulting correspondence is a homomorphic bijection. We derive conditions under which the associated matrix is unitary and hence represents a three-qubit quantum gate. This leads to a specific algebraic notion of a unitary state: a normalized state whose multiplication matrix is unitary. We construct 16,384 basis spaces; within each fixed space, multiplication generates a commuting family of quantum gates. For any two unitary states in the class considered, we give an explicit transition-gate construction within one of these algebraic families. For real components, the unitary states in a representative basis space form a union of thirty-two four-dimensional manifolds in \(\mathbb{R}^{8}\). The construction therefore yields new structured classes of three-qubit unitary operators and invariant state sets, while its extension to larger multiqubit systems remains open.

•Oct 20, 2026•0 citations
We show how representations of finite-dimensional quantum operators can be constructed using nondeterministic rewriting systems. In particular, we investigate Wolfram model multiway rewriting systems based on string substitutions. Multiway systems were proposed by S. Wolfram as generic model systems for multicomputational processes, emphasizing their significance as a foundation for modeling complexity, nondeterminism, and branching structures of measurement outcomes. Here, we investigate a specific class of multiway systems based on cyclic character strings with a neighborhood constraint - the latter called Leibnizian strings. We show that such strings exhibit a Fermi-Dirac distribution for expectation values of occupation numbers of character neighborhoods. A Leibnizian string serves as an abstraction of a NNN-fermion system. A multiway system of these strings encodes causal relations between rewriting events in a nondeterministic manner. The collection of character strings realizes a Z\mathbb{Z}Z-module with a symmetric Z\mathbb{Z}Z-bilinear form. For discrete spaces, this generalizes the notion of an inner product over a vector field. This admits a discrete analogue of the path integral and a SSS-matrix for multiway systems of Leibnizian strings. The elements of this SSS-matrix yield transition amplitudes between states of the multiway system based on an action defined over a sequence of Leibnizian strings. We then show that these SSS-matrices give explicit representations of quantum gates for qubits and qudits, and also circuits composed of such gates. We find that, as formal models of nondeterministic computation, rewriting systems of Leibnizian strings with causal structure encode representations of the CNOT, π/8π/8π/8, and Hadamard gates. Hence, using multiway systems one can represent quantum circuits for qubits.
Categorical quantum mechanics and the Wolfram model offer distinct but complementary approaches to studying the relationship between diagrammatic rewriting systems over combinatorial structures and the foundations of physics; the objective of the present article is to begin elucidating the formal correspondence between the two methodologies in the context of the ZX-calculus formalism of Coecke and Duncan for reasoning diagrammatically about linear maps between qubits. After briefly summarizing the relevant formalisms, and presenting a categorical formulation of the Wolfram model in terms of adhesive categories and double-pushout rewriting systems, we illustrate how the diagrammatic rewritings of the ZX-calculus can be embedded and realized within the broader context of Wolfram model multiway systems, and illustrate some of the capabilities of the software framework (ZXMultiwaySystem) that we have developed specifically for this purpose. Finally, we present a proof (along with an explicitly computed example) based on the methods of Dixon and Kissinger that the multiway evolution graphs and branchial graphs of the Wolfram model are naturally endowed with a monoidal structure based on rulial composition that is, furthermore, compatible with the monoidal product of ZX-diagrams.
This article presents a novel algorithmic methodology for performing automated diagrammatic deductions over combinatorial structures, using a combination of modified equational theorem-proving techniques and the extended Wolfram model hypergraph rewriting formalism developed by the authors in previous work. We focus especially upon the application of this new algorithm to the problem of automated circuit simplification in quantum information theory, using Wolfram model multiway operator systems combined with the ZX-calculus formalism for enacting fast diagrammatic reasoning over linear transformations between qubits. We show how to construct a generalization of the deductive inference rules for Knuth-Bendix completion in which equation matches are selected on the basis of causal edge density in the associated multiway system, before proceeding to demonstrate how to embed the higher-order logic of the ZX-calculus rules within this first-order equational framework. After showing explicitly how the (hyper)graph rewritings of both Wolfram model systems and the ZX-calculus can be effectively realized within this formalism, we proceed to exhibit comparisons of time complexity vs. proof complexity for this new algorithmic approach when simplifying randomly-generated Clifford circuits down to pseudo-normal form, as well as when reducing the number of T-gates in randomly-generated non-Clifford circuits, with circuit sizes ranging up to 3000 gates, illustrating that the method performs favorably in comparison with existing circuit simplification frameworks, and also exhibiting the approximately quadratic speedup obtained by employing the causal edge density optimization. Finally, we present a worked example of an automated proof of correctness for a simple quantum teleportation protocol, in order to demonstrate more clearly the internal operations of the theorem-proving procedure.
There are various gate sets used for describing quantum computation. A particularly popular one consists of Clifford gates and arbitrary single-qubit phase gates. Computations in this gate set can be elegantly described by the ZX-calculus, a graphical language for a class of string diagrams describing linear maps between qubits. The ZX-calculus has proven useful in a variety of areas of quantum information, but is less suitable for reasoning about operations outside its natural gate set such as multi-linear Boolean operations like the Toffoli gate. In this paper we study the ZH-calculus, an alternative graphical language of string diagrams that does allow straightforward encoding of Toffoli gates and other more complicated Boolean logic circuits. We find a set of simple rewrite rules for this calculus and show it is complete with respect to matrices over Z[12] , which correspond to the approximately universal Toffoli+Hadamard gateset. Furthermore, we construct an extended version of the ZH-calculus that is complete with respect to matrices over any ring R where 1+1 is not a zero-divisor.
We introduce the fermionic ZW calculus, a string-diagrammatic language for fermionic quantum computing (FQC). After defining a fermionic circuit model, we present the basic components of the calculus, together with their interpretation, and show how the main physical gates of interest in FQC can be represented in our language. We then list our axioms, and derive some additional equations. We prove that the axioms provide a complete equational axiomatisation of the monoidal category whose objects are systems of finitely many local fermionic modes (LFMs), with maps that preserve or reverse the parity of states, and the tensor product as monoidal product. We achieve this through a procedure that rewrites any diagram in a normal form. As an example, we show how the statistics of a fermionic Mach-Zehnder interferometer can be calculated in the diagrammatic language. We conclude by giving a diagrammatic treatment of the dual-rail encoding, a standard method in optical quantum computing used to perform universal quantum computation.
This work is about diagrammatic languages, how they can be represented, and what they in turn can be used to represent. More specifically, it focuses on representations and applications of string diagrams. String diagrams are used to represent a collection of processes, depicted as "boxes" with multiple (typed) inputs and outputs, depicted as "wires". If we allow plugging input and output wires together, we can intuitively represent complex compositions of processes, formalised as morphisms in a monoidal category. [...] The first major contribution of this dissertation is the introduction of a discretised version of a string diagram called a string graph. String graphs form a partial adhesive category, so they can be manipulated using double-pushout graph rewriting. Furthermore, we show how string graphs modulo a rewrite system can be used to construct free symmetric traced and compact closed categories on a monoidal signature. The second contribution is in the application of graphical languages to quantum information theory. We use a mixture of diagrammatic and algebraic techniques to prove a new classification result for strongly complementary observables. [...] We also introduce a graphical language for multipartite entanglement and illustrate a simple graphical axiom that distinguishes the two maximally-entangled tripartite qubit states: GHZ and W. [...] The third contribution is a description of two software tools developed in part by the author to implement much of the theoretical content described here. The first tool is Quantomatic, a desktop application for building string graphs and graphical theories, as well as performing automated graph rewriting visually. The second is QuantoCoSy, which performs fully automated, model-driven theory creation using a procedure called conjecture synthesis.
Pure states of three-qubit quantum systems are represented by eight-dimensional complex vectors, whereas their unitary transformations are described by 8×88 \times 88×8 complex matrices. Motivated by this correspondence, we extend our algebraic model for two-qubit systems to eight-dimensional spaces endowed with commutative and associative multiplication. To each eight-dimensional number we assign a matrix and prove that the resulting correspondence is a homomorphic bijection. We derive conditions under which the associated matrix is unitary and hence represents a three-qubit quantum gate. This leads to a specific algebraic notion of a unitary state: a normalized state whose multiplication matrix is unitary. We construct 16,384 basis spaces; within each fixed space, multiplication generates a commuting family of quantum gates. For any two unitary states in the class considered, we give an explicit transition-gate construction within one of these algebraic families. For real components, the unitary states in a representative basis space form a union of thirty-two four-dimensional manifolds in R8\mathbb{R}^{8}R8. The construction therefore yields new structured classes of three-qubit unitary operators and invariant state sets, while its extension to larger multiqubit systems remains open.