We review here some recent work in the field of quantum annealing, alias adiabatic
quantum computation. The idea of quantum annealing is to perform optimization by a …

For many random constraint satisfaction problems, by now there exist asymptotically tight
estimates of the largest constraint density for which solutions exist. At the same time, for …

The path integral Monte Carlo simulated quantum annealing algorithm is applied to the
optimization of a large hard instance of the random satisfiability problem (N= 10 000). The …

We study the problem of preparing a quantum many-body system from an initial to a target
state by optimizing the fidelity over the family of bang-bang protocols. We present …

We propose a modified belief propagation algorithm, with over-relaxed dynamics. Such an
algorithm turns out to be generally more stable and faster than ordinary belief propagation …

Many real-life optimization problems can be formulated in Boolean logic as MaxSAT, a class
of problems where the task is finding Boolean assignments to variables satisfying the …

The bootstrap percolation (or threshold model) is a dynamic process modelling the
propagation of an epidemic on a graph, where inactive vertices become active if their …

The use of parity-check gates in information theory has proved to be very efficient. In
particular, error correcting codes based on parity checks over low-density graphs show …

Many natural optimization problems are NP-hard, which implies that they are probably hard
to solve exactly in the worst-case. However, it suffices to get reasonably good solutions for …

A new algorithm for solving maximum satisfiability (MAX-SAT) problems is introduced which
clusters good solutions, and restarts the search from the closest feasible solution to the …