Digital Memcomputing: from Logic to Dynamics to Topology
arXiv:1903.08732 · doi:10.1016/j.aop.2019.167935
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.
References in corpus (9)
- Circuit elements with memory: memristors, memcapacitors and meminductors
- Pseudo-Hermiticity versus PT-Symmetry III: Equivalence of pseudo-Her miticity and the presence of antilinear symmetries
- Memcomputing: a computing paradigm to store and process information on the same physical platform
- Universal Memcomputing Machines
- Polynomial-time solution of prime factorization and NP-hard problems with digital memcomputing machines
- Introduction to Supersymmetric Theory of Stochastics
- Notes on instantons in topological field theory and beyond
- Absence of chaos in Digital Memcomputing Machines with solutions
- Topological field theory and physics
Cited by in corpus (9)
- Efficient Solution of Boolean Satisfiability Problems with Digital MemComputing
- Directed percolation and numerical stability of simulations of digital memcomputing machines
- Taming a non-convex landscape with dynamical long-range order: memcomputing Ising benchmarks
- Ubiquitous order known as chaos
- Hardware implementation of digital memcomputing on small-size FPGAs
- MemComputing vs. Quantum Computing: some analogies and major differences
- The Supersymmetric Origin of Chaos and its Hidden Topological Order
- On the solvable-unsolvable transition due to noise-induced chaos in digital memcomputing
- Brain-like features of MemComputing machines