Noisy Random Boolean Formulae - a Statistical Physics Perspective

Conventional computing architectures have no known efficient algorithms for combinatorial optimization tasks, which are encountered in fundamental areas and real-world practical problems including logistics, social networks, and cryptography. Physical machines have recently been proposed and implemented as an alternative to conventional exact and heuristic solvers for the Ising problem, one such optimization task that requires finding the ground state spin configuration of an...

We investigate the ground-state probabilistic logic based on a binary energy landscape (GSPL-BEL) model, implementing the many-body interactions within Ising model cells. The GSPL-BEL model offers a simplified binary energy landscape, enabling the conversion of traditional CMOS-based logic into a probabilistic graphical representation based on desired truth tables. Stochastic Ising cells, coupled with generic probabilistic devices exhibiting sigmoidal electrical responses, se...

We present protocols for implementation of universal quantum gates on an arbitrary superposition of quantum states in a scalable solid-state Ising spin quantum computer. The spin chain is composed of identical spins 1/2 with the Ising interaction between the neighboring spins. The selective excitations of the spins are provided by the gradient of the external magnetic field. The protocols are built of rectangular radio-frequency pulses. The phase and probability errors caused...

Noise-based logic is a practically deterministic logic scheme inspired by the randomness of neural spikes and uses a system of uncorrelated stochastic processes and their superposition to represent the logic state. We briefly discuss various questions such as (i) What does practical determinism mean? (ii) Is noise-based logic a Turing machine? (iii) Is there hope to beat (the dreams of) quantum computation by a classical physical noise-based processor, and what are the minimu...

A short survey is provided about our recent explorations of the young topic of noise-based logic. After outlining the motivation behind noise-based computation schemes, we present a short summary of our ongoing efforts in the introduction, development and design of several noise-based deterministic multivalued logic schemes and elements. In particular, we describe classical, instantaneous, continuum, spike and random-telegraph-signal based schemes with applications such as ci...

In this paper, we show recent results indicating that using electrical noise as information carrier offers outstanding potentials reminding of quantum informatics. One example is noise-based computing and logic that shows certain similarities to quantum logic. However, due to the lack of the collapse of wavefunction and due to the immediate accessibility of superposition components, the use of noise-based and quantum computers will probably be different. Another example is se...

Determining properties of ground states of spin Hamiltonians remains a topic of central relevance connecting disciplines of mathematical, theoretical and applied physics. In the last few decades, ground state properties of physical systems have been increasingly considered as computational resources. This thesis develops parts of the mathematical apparatus to create (program) ground states relevant for quantum and classical computation. The core findings presented in this the...

In modern transistor based logic gates, the impact of noise on computation has become increasingly relevant since the voltage scaling strategy, aimed at decreasing the dissipated power, has increased the probability of error due to the reduced switching threshold voltages. In this paper we discuss the role of noise in a two state model that mimic the dynamics of standard logic gates and show that the presence of the noise sets a fundamental limit to the computing speed. An op...

Digital computers implement computations using circuits, as do many naturally occurring systems (e.g., gene regulatory networks). The topology of any such circuit restricts which variables may be physically coupled during the operation of a circuit. We investigate how such restrictions on the physical coupling affects the thermodynamic costs of running the circuit. To do this we first calculate the minimal additional entropy production that arises when we run a given gate in ...

We characterize the set of ground states that can be synthesized by classical 2-body Ising Hamiltonians. We then construct simple Ising planar blocks that simulates efficiently a universal set of logic gates and connections, and hence any boolean function. We therefore provide a new method of encoding universal computation in the ground states of Ising lattices, and a simpler alternative demonstration of the known fact that finding the ground state of a finite Ising spin glas...