Digital memcomputing: from logic to dynamics to topology

DOI10.1016/J.AOP.2019.167935MaRDI QIDQ2336003zbMATH OpenOpenAlexWikidataFDO

Authors Massimiliano Di Ventra, I. V. Ovchinnikov

Publication date 18 November 2019

Published in Annals of Physics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1903.08732

zbMATH Keywords

dynamical systemsmemorytopologyunconventional computing

Mathematics Subject Classification ID

Generation, random and stochastic difference and differential equations (37H10) Supersymmetric field theories in quantum mechanics (81T60)

Abstract: Digital memcomputing machines (DMMs) are a class of computational machines designed to solve combinatorial optimization problems. A practical realization of DMMs can be accomplished via electrical circuits of highly non-linear, point-dissipative dynamical systems engineered so that periodic orbits and chaos can be avoided. A given logic problem is first mapped into this type of dynamical system whose point attractors represent the solutions of the original problem. A DMM then finds the solution via a succession of elementary instantons whose role is to eliminate solitonic configurations of logical inconsistency ("logical defects") from the circuit. By employing a supersymmetric theory of dynamics, a DMM can be described by a cohomological field theory that allows for computation of certain topological matrix elements on instantons that have the mathematical meaning of intersection numbers on instantons. We discuss the "dynamical" meaning of these matrix elements, and argue that the number of elementary instantons needed to reach the solution cannot exceed the number of state variables of DMMs, which in turn can only grow at most polynomially with the size of the problem. These results shed further light on the relation between logic, dynamics and topology in digital memcomputing.

Recommendations

• scientific article; zbMATH DE number 1735638
• A computational complexity theory in membrane computing
• Impacts of membrane computing on theoretical computer science (extended abstract)
• Turing computability and membrane computing
• scientific article; zbMATH DE number 2155205
• Membrane Computing
• A dozen of research topics in membrane computing
• Logic and arithmetic operations with a constant number of steps in membrane computing
• Membrane Computing: Basics and Frontiers
• Theory and Applications of Models of Computation

Cites work

• Absence of chaos in digital memcomputing machines with solutions
• Absence of periodic orbits in digital memcomputing machines with solutions
• Ergodic theory of chaos and strange attractors
• Hamiltonian Systems and Transformation in Hilbert Space
• scientific article; zbMATH DE number 3776098 (Why is no real title available?)
• scientific article; zbMATH DE number 42047 (Why is no real title available?)
• scientific article; zbMATH DE number 193048 (Why is no real title available?)
• scientific article; zbMATH DE number 776267 (Why is no real title available?)
• Morse theory interpretation of topological quantum field theories
• Polynomial-time solution of prime factorization and NP-complete problems with digital memcomputing machines
• Pseudo-Hermiticity versus PT-symmetry III: Equivalence of pseudo-Hermiticity and the presence of antilinear symmetries
• Topological analysis of chaotic dynamical systems
• Topological field theory and physics
• Topological quantum field theory
• Topological sigma models

Cited in

(3)

• Absence of chaos in digital memcomputing machines with solutions
• Polynomial-time solution of prime factorization and NP-complete problems with digital memcomputing machines
• Absence of periodic orbits in digital memcomputing machines with solutions

This page was built for publication: Digital memcomputing: from logic to dynamics to topology

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2336003)