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

ACM/IEEE Symposium on Logic in Computer Science (LICS)

Stochastic mechanics of graph rewriting

Nicolas Behr, Vincent Danos, Ilias Garnier

Published Jul 5, 2016• 29 citations
Publisher

Abstract

We propose an algebraic approach to stochastic graph-rewriting which extends the classical construction of the Heisenberg-Weyl algebra and its canonical representation on the Fock space. Rules are seen as particular elements of an algebra of "diagrams": the diagram algebra D. Diagrams can be thought of as formal computational traces represented in partial time. They can be evaluated to normal diagrams (each corresponding to a rule) and generate an associative unital non-commutative algebra of rules: the rule algebra R. Evaluation becomes a morphism of unital associative algebras which maps general diagrams in D to normal ones in R. In this algebraic reformulation, usual distinctions between graph observables (real-valued maps on the set of graphs defined by counting subgraphs) and rules disappear. Instead, natural algebraic substructures of R arise: formal observables are seen as rules with equal left and right hand sides and form a commutative subalgebra, the ones counting subgraphs forming a sub-subalgebra of identity rules. Actual graph-rewriting is recovered as a canonical representation of the rule algebra as linear operators over the vector space generated by (isomorphism classes of) finite graphs. The construction of the representation is in close analogy with and subsumes the classical (multi-type bosonic) Fock space representation of the Heisenberg-Weyl algebra.

DOI
10.1145/2933575.2934537

Related papers

Weyl quantization

Giampiero V. M. Esposito, Giuseppe Marmo, George Sudarshan

The commutator of position and momentum operators is first considered in the coordinate and momentum representations, and then in an abstract Hilbert space. The reader is then introduced to canonical operators with the associated canonical quantization of commutation rules, which consists of maps defined on a symplectic space and taking values in the set of unitary operators on a Hilbert space. If the symplectic space is finite-dimensional, all of its irreducible representations are unitarily equivalent. The Weyl exponentiated form of the commutation relations is described and investigated. One then arrives at the definition of Weyl systems, and it is shown how to recover from them the formulation in terms of self-adjoint operators which satisfy a generalized form of commutation relations.

Cambridge University Press eBooks•Mar 11, 2004•0 citations

CLIFFORD ALGEBRAS, RANDOM GRAPHS, AND QUANTUM RANDOM VARIABLES

René Schott, G. Stacey Staples

For fixed n > 0, the space of finite graphs on n vertices is canonically associated with an abelian, nilpotent-generated subalgebra of the Clifford algebra which is canonically isomorphic to the 2n-particle fermion algebra. Using the generators of the subalgebra, an algebraic probability space of “Clifford adjacency matrices” associated with finite graphs is defined. Each Clifford adjacency matrix is a quantum random variable whose m th moment corresponds to the number of m-cycles in the graph G. Each matrix admits a canonical “quantum decomposition” into a sum of three algebraic random variables: a = a Δ + a ϒ + a Λ , where a Δ is classical while a ϒ and a Λ are quantum. Moreover, within the Clifford algebra context the NP problem of cycle enumeration is reduced to matrix multiplication, requiring no more than n 4 Clifford (geo-metric) multiplications within the algebra.

Quantum Stochastics and Information•Aug 1, 2008•1 citation

Origin of the quantum observable operator algebra in the frame of stochastic mechanics

Francesco Guerra, R. Marra

In previous work the approach to stochastic quantization, originally proposed by Nelson, has been formulated in the frame of the stochastic variational principles of control theory. Then the Hamilton-Jacobi-Madelung equation is interpreted as the programming equation of the controlled problem, to be associated with the hydrodynamical continuity equation. Here we point out explicitly the canonical Hamiltonian structure of these equations, by introducing a suitable symplectic structure on the underlying phase space in various representations. One possible representation leads to the Schr\"odinger equation, which, together with its complex conjugate, can be recognized as a particular form of the Hamilton canonical equations in this frame. Then a suitably selected time-invariant subalgebra of the classical hydrodynamical algebra, closed under Poisson bracket pairing, is shown to be connected to the standard quantum observable operator algebra. In this correspondence Poisson brackets for hydrodynamical observables become averages of quantum observables in the given state. From this point of view stochastic quantization can be interpreted as giving an explanation for the standard quantization procedure of replacing the classical particle (or field) observables with operators, according to the scheme $p\ensuremath{\rightarrow}(\frac{h}{i})\frac{\ensuremath{\partial}}{\ensuremath{\partial}x}$, $l\ensuremath{\rightarrow}(\frac{h}{i})\frac{\ensuremath{\partial}}{\ensuremath{\partial}\ensuremath{\varphi}}$, etc. This discussion shows also the relevance of the canonical symplectic structure of the quantum state space, a feature which seems to have been overlooked in the axiomatic approaches to quantum mechanics.

Physical review. D. Particles, fields, gravitation, and cosmology/Physical review. D. Particles and fields•Oct 15, 1983•36 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

Alternative Hamiltonians and Wigner quantization

Pawe B asiak, A. Horzela, Edward Kapu cik

The Wigner problem, i.e. the investigation of general quantum mechanical commutation relations consistent with the Heisenberg evolution equations of a given shape, is studied. We follow a recently proposed generalization of this idea within which the classical analogy is postulated only for the shape of the time evolution equations and not for a Hamiltonian itself. This links our investigation to the problem of alternative Hamiltonians of classical mechanics and to canonically inequivalent phase-space descriptions of physical systems governed by the same Newton equations of motion. Warned that the time evolution and the other symmetry generators may be given ambiguously even in the formalism of classical mechanics, we do not a priori assume the shape of their quantum analogues. Instead we only require that the set of basic algebraic relations, which quantum mechanical observables are to obey, has a Lie algebra structure. Such a requirement appears to be sufficient to find solutions for simple oscillator-like dynamics. New algebras of quantum mechanical observables are not constructed as a linear envelope of the Heisenberg algebra, and their representations reflect physical results unexpected in the framework of the canonical approach. We illustrate our approach in detail for the example of the one-dimensional harmonic oscillator using the representation of the generalized coherent states.

Journal of Optics B Quantum and Semiclassical Optics•Jun 1, 2003•10 citations

No More Than Mechanics. I

Vladimir V. Kisil

One can introduce so-called {\em Plain Mechanics} having an {\bf operator realization}. Then the set of one-dimension representations of this operator realization may be identified with the Classical Mechanics. Different irreducible infinite-dimension representations may be recognized as Quantum Mechanics for different $\hbar$ (the Planck constant). It can be done in the such manner that the following diagram will be commutative. Plain Mechanics / \ / \ / \ Quantum Mechanics --> Classical Mechanics h->0 Here the horizontal arrow is well known correspondence between Quantum and Classical Mechanics if Planck constant tensing to zero. A {\em realization} of this scheme for a particle in $n$-dimensional space by two-sided convolutions on the Heisenberg group is constructed. We also introduce the {\em motion equations} for observables in this realization. The left arrow of the given diagram carries this equation to the Heisenberg one and the right arrow maps it to the Hamilton equation.

arXiv:funct-an/9405002•May 2, 1994•21 citations
We propose an algebraic approach to stochastic graph-rewriting which extends the classical construction of the Heisenberg-Weyl algebra and its canonical representation on the Fock space. Rules are seen as particular elements of an algebra of "diagrams": the diagram algebra D. Diagrams can be thought of as formal computational traces represented in partial time. They can be evaluated to normal diagrams (each corresponding to a rule) and generate an associative unital non-commutative algebra of rules: the rule algebra R. Evaluation becomes a morphism of unital associative algebras which maps general diagrams in D to normal ones in R. In this algebraic reformulation, usual distinctions between graph observables (real-valued maps on the set of graphs defined by counting subgraphs) and rules disappear. Instead, natural algebraic substructures of R arise: formal observables are seen as rules with equal left and right hand sides and form a commutative subalgebra, the ones counting subgraphs forming a sub-subalgebra of identity rules. Actual graph-rewriting is recovered as a canonical representation of the rule algebra as linear operators over the vector space generated by (isomorphism classes of) finite graphs. The construction of the representation is in close analogy with and subsumes the classical (multi-type bosonic) Fock space representation of the Heisenberg-Weyl algebra.
The commutator of position and momentum operators is first considered in the coordinate and momentum representations, and then in an abstract Hilbert space. The reader is then introduced to canonical operators with the associated canonical quantization of commutation rules, which consists of maps defined on a symplectic space and taking values in the set of unitary operators on a Hilbert space. If the symplectic space is finite-dimensional, all of its irreducible representations are unitarily equivalent. The Weyl exponentiated form of the commutation relations is described and investigated. One then arrives at the definition of Weyl systems, and it is shown how to recover from them the formulation in terms of self-adjoint operators which satisfy a generalized form of commutation relations.
For fixed n > 0, the space of finite graphs on n vertices is canonically associated with an abelian, nilpotent-generated subalgebra of the Clifford algebra which is canonically isomorphic to the 2n-particle fermion algebra. Using the generators of the subalgebra, an algebraic probability space of “Clifford adjacency matrices” associated with finite graphs is defined. Each Clifford adjacency matrix is a quantum random variable whose m th moment corresponds to the number of m-cycles in the graph G. Each matrix admits a canonical “quantum decomposition” into a sum of three algebraic random variables: a = a Δ + a ϒ + a Λ , where a Δ is classical while a ϒ and a Λ are quantum. Moreover, within the Clifford algebra context the NP problem of cycle enumeration is reduced to matrix multiplication, requiring no more than n 4 Clifford (geo-metric) multiplications within the algebra.
In previous work the approach to stochastic quantization, originally proposed by Nelson, has been formulated in the frame of the stochastic variational principles of control theory. Then the Hamilton-Jacobi-Madelung equation is interpreted as the programming equation of the controlled problem, to be associated with the hydrodynamical continuity equation. Here we point out explicitly the canonical Hamiltonian structure of these equations, by introducing a suitable symplectic structure on the underlying phase space in various representations. One possible representation leads to the Schr\"odinger equation, which, together with its complex conjugate, can be recognized as a particular form of the Hamilton canonical equations in this frame. Then a suitably selected time-invariant subalgebra of the classical hydrodynamical algebra, closed under Poisson bracket pairing, is shown to be connected to the standard quantum observable operator algebra. In this correspondence Poisson brackets for hydrodynamical observables become averages of quantum observables in the given state. From this point of view stochastic quantization can be interpreted as giving an explanation for the standard quantization procedure of replacing the classical particle (or field) observables with operators, according to the scheme $p\ensuremath{\rightarrow}(\frac{h}{i})\frac{\ensuremath{\partial}}{\ensuremath{\partial}x}$, $l\ensuremath{\rightarrow}(\frac{h}{i})\frac{\ensuremath{\partial}}{\ensuremath{\partial}\ensuremath{\varphi}}$, etc. This discussion shows also the relevance of the canonical symplectic structure of the quantum state space, a feature which seems to have been overlooked in the axiomatic approaches to quantum mechanics.
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.
The Wigner problem, i.e. the investigation of general quantum mechanical commutation relations consistent with the Heisenberg evolution equations of a given shape, is studied. We follow a recently proposed generalization of this idea within which the classical analogy is postulated only for the shape of the time evolution equations and not for a Hamiltonian itself. This links our investigation to the problem of alternative Hamiltonians of classical mechanics and to canonically inequivalent phase-space descriptions of physical systems governed by the same Newton equations of motion. Warned that the time evolution and the other symmetry generators may be given ambiguously even in the formalism of classical mechanics, we do not a priori assume the shape of their quantum analogues. Instead we only require that the set of basic algebraic relations, which quantum mechanical observables are to obey, has a Lie algebra structure. Such a requirement appears to be sufficient to find solutions for simple oscillator-like dynamics. New algebras of quantum mechanical observables are not constructed as a linear envelope of the Heisenberg algebra, and their representations reflect physical results unexpected in the framework of the canonical approach. We illustrate our approach in detail for the example of the one-dimensional harmonic oscillator using the representation of the generalized coherent states.
One can introduce so-called {\em Plain Mechanics} having an {\bf operator realization}. Then the set of one-dimension representations of this operator realization may be identified with the Classical Mechanics. Different irreducible infinite-dimension representations may be recognized as Quantum Mechanics for different ℏ\hbarℏ (the Planck constant). It can be done in the such manner that the following diagram will be commutative. Plain Mechanics / \ / \ / \ Quantum Mechanics --> Classical Mechanics h->0 Here the horizontal arrow is well known correspondence between Quantum and Classical Mechanics if Planck constant tensing to zero. A {\em realization} of this scheme for a particle in nnn-dimensional space by two-sided convolutions on the Heisenberg group is constructed. We also introduce the {\em motion equations} for observables in this realization. The left arrow of the given diagram carries this equation to the Heisenberg one and the right arrow maps it to the Hamilton equation.