Quantum tunneling and quantum walks as algorithmic resources to solve hard K-SAT instances

We present a new quantum heuristic algorithm aimed at finding satisfying assignments for hard K-SAT instances using a continuous time quantum walk that explicitly exploits the properties of quantum tunneling. Our algorithm uses a Hamiltonian \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$H_A(F)$$\end{document}HA(F) which is specifically constructed to solve a K-SAT instance F. The heuristic algorithm aims at iteratively reducing the Hamming distance between an evolving state \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${|{\psi _j}\rangle }$$\end{document}|ψj⟩ and a state that represents a satisfying assignment for F. Each iteration consists on the evolution of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${|{\psi _j}\rangle }$$\end{document}|ψj⟩ (where j is the iteration number) under \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$e^{-iH_At}$$\end{document}e-iHAt, a measurement that collapses the superposition, a check to see if the post-measurement state satisfies F and in the case it does not, an update to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$H_A$$\end{document}HA for the next iteration. Operator \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$H_A$$\end{document}HA describes a continuous time quantum walk over a hypercube graph with potential barriers that makes an evolving state to scatter and mostly follow the shortest tunneling paths with the smaller potentials that lead to a state \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${|{s}\rangle }$$\end{document}|s⟩ that represents a satisfying assignment for F. The potential barriers in the Hamiltonian \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$H_A$$\end{document}HA are constructed through a process that does not require any previous knowledge on the satisfying assignments for the instance F. Due to the topology of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$H_A$$\end{document}HA each iteration is expected to reduce the Hamming distance between each post measurement state and a state \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${|{s}\rangle }$$\end{document}|s⟩. If the state \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${|{s}\rangle }$$\end{document}|s⟩ is not measured after n iterations (the number n of logical variables in the instance F being solved), the algorithm is restarted. Periodic measurements and quantum tunneling also give the possibility of getting out of local minima. Our numerical simulations show a success rate of 0.66 on measuring \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${|{s}\rangle }$$\end{document}|s⟩ on the first run of the algorithm (i.e., without restarting after n iterations) on thousands of 3-SAT instances of 4, 6, and 10 variables with unique satisfying assignments.

Self-Induced Glassy Phase in Multimodal Cavity Quantum Electrodynamics

We provide strong evidence that the effective spin-spin interaction in a multimodal confocal optical cavity gives rise to a self-induced glassy phase, which emerges exclusively from the peculiar Euclidean correlations and is not related to the presence of disorder as in standard spin glasses. As recently shown, this spin-spin effective interaction is both nonlocal and nontranslational invariant, and randomness in the atoms' positions produces a spin glass phase. Here we consider the simplest feasible disorder-free setting, where atoms form a one-dimensional regular chain and we study the thermodynamics of the resulting effective Ising model. We present extensive results showing that the system has a low-temperature glassy phase. The model depends on the adimensional parameter α=(a/w_{0})^{2}, a being a lattice spacing and w_{0} an interaction length scale. Notably, for rational values of α=p/q, the number of metastable states at low temperature grows exponentially with q and the problem of finding the ground state rapidly becomes computationally intractable, suggesting that the system develops high-energy barriers and ergodicity breaking occurs.

Replica symmetry and replica symmetry breaking for the traveling salesperson problem

We study the energy landscape of the traveling salesperson problem (TSP) using exact ground states and a novel linear programming approach to generate excited states with closely defined properties. We look at four different ensembles, notably the classic finite dimensional Euclidean TSP and the mean-field-like (1,2)-TSP, which has its origin directly in the mapping of the Hamiltonian circuit problem on the TSP. Our data supports previous conjectures that the Euclidean TSP does not show signatures of replica symmetry breaking neither in two nor in higher dimension. On the other hand the (1,2)-TSP exhibits some signature which does not exclude broken replica symmetry, making it a candidate for further studies in the future.

On the Representational Power of Restricted Boltzmann Machines for Symmetric Functions and Boolean Functions

Restricted Boltzmann machines (RBMs) are used to build deep-belief networks that are widely thought to be one of the first effective deep learning neural networks. This paper studies the ability of RBMs to represent distributions over {0,1}ⁿ via softplus/hardplus RBM networks. It is shown that any distribution whose density depends on the number of 1's in their input can be approximated with arbitrarily high accuracy by an RBM of size 2n+1 , which improves the result of a previous study by reducing the size from n² to 2n+1 . A theorem for representing partially symmetric Boolean functions by softplus RBM networks is established. Accordingly, the representational power of RBMs for distributions whose mass represents the Boolean functions is investigated in comparison with that of threshold circuits and polynomial threshold functions. It is shown that a distribution over {0,1}ⁿ whose mass represents a Boolean function can be computed with a given margin δ by an RBM of size and parameters bounded by polynomials in n , if and only if it can be computed by a depth-2 threshold circuit with size and parameters bounded by polynomials in n .

Numerical solution-space analysis of satisfiability problems

The solution-space structure of the three-satisfiability problem (3-SAT) is studied as a function of the control parameter α (ratio of the number of clauses to the number of variables) using numerical simulations. For this purpose one has to sample the solution space with uniform weight. It is shown here that standard stochastic local-search (SLS) algorithms like average satisfiability (ASAT) exhibit a sampling bias, as does "Metropolis-coupled Markov chain Monte Carlo" (MCMCMC) (also known as "parallel tempering") when run for feasible times. Nevertheless, unbiased samples of solutions can be obtained using the "ballistic-networking approach," which is introduced here. It is a generalization of "ballistic search" methods and yields also a cluster structure of the solution space. As application, solutions of 3-SAT instances are generated using ASAT plus ballistic networking. The numerical results are compatible with a previous analytical prediction of a simple solution-space structure for small values of α and a transition to a clustered phase at α(c)≈3.86 , where the solution space breaks up into several non-negligible clusters. Furthermore, in the thermodynamic limit there are, even for α=4.25 close to the SAT-UNSAT transition α(s)≈4.267 , always clusters without any frozen variables. This may explain why some SLS algorithms are able to solve very large 3-SAT instances close to the SAT-UNSAT transition.

Genetic embedded matching approach to ground states in continuous-spin systems

Due to an extremely rugged structure of the free energy landscape, the determination of spin-glass ground states is among the hardest known optimization problems, found to be NP hard in the most general case. Owing to the specific structure of local (free) energy minima, general-purpose optimization strategies perform relatively poorly on these problems, and a number of specially tailored optimization techniques have been developed in particular for the Ising spin glass and similar discrete systems. Here, an efficient optimization heuristic for the much less discussed case of continuous spins is introduced, based on the combination of an embedding of Ising spins into the continuous rotators and an appropriate variant of a genetic algorithm. Statistical techniques for insuring high reliability in finding (numerically) exact ground states are discussed, and the method is benchmarked against the simulated annealing approach.

Monomer-dimer model in two-dimensional rectangular lattices with fixed dimer density

The classical monomer-dimer model in two-dimensional lattices has been shown to belong to the "#P-complete" class, which indicates the problem is computationally "intractable." We use exact computational method to investigate the number of ways to arrange dimers on mxn two-dimensional rectangular lattice strips with fixed dimer density rho . For any dimer density 0<rho<1 , we find a logarithmic correction term in the finite-size correction of the free energy per lattice site. The coefficient of the logarithmic correction term is exactly -12 . This logarithmic correction term is explained by the newly developed asymptotic theory of Pemantle and Wilson. The sequence of the free energy of lattice strips with cylinder boundary condition converges so fast that very accurate free energy f{2}(rho) for large lattices can be obtained. For example, for a half-filled lattice, f{2}(12)=0.633195588930 , while f{2}(14)=0.4413453753046 and f{2}(34)=0.64039026 . For rho<0.65 , f{2}(rho) is accurate at least to ten decimal digits. The function f{2}(rho) reaches the maximum value f{2}(rho{*})=0.662798972834 at rho{*}=0.6381231 , with 11 correct digits. This is also the monomer-dimer constant for two-dimensional rectangular lattices. The asymptotic expressions of free energy near close packing are investigated for finite and infinite lattice widths. For lattices with finite width, dependence on the parity of the lattice width is found. For infinite lattices, the data support the functional form obtained previously through series expansions.

The influence of oppositely classified examples on the generalization complexity of Boolean functions

In this paper, we analyze Boolean functions using a recently proposed measure of their complexity. This complexity measure, motivated by the aim of relating the complexity of the functions with the generalization ability that can be obtained when the functions are implemented in feed-forward neural networks, is the sum of a number of components. We concentrate on the case in which we use the first two of these components. The first is related to the "average sensitivity" of the function and the second is, in a sense, a measure of the "randomness" or lack of structure of the function. In this paper, we investigate the importance of using the second term in the complexity measure, and we consider to what extent these two terms suffice as an indicator of how difficult it is to learn a Boolean function. We also explore the existence of very complex Boolean functions, considering, in particular, the symmetric Boolean functions.

Logic backbone of a transcription network

A great part of the effort in the study of coarse-grained models of transcription networks concentrates on their dynamical features. In this Letter, we consider their equilibrium properties, showing that the backbone underlying the dynamic descriptions is an optimization problem. It involves N variables, the gene expression levels, and M constraints, the effects of transcriptional regulation. In the case of Boolean variables and constraints, we investigate the structure of the solutions and derive phase diagrams. Notably, the model exhibits a connectivity transition between a regime of simple gene control, where the input genes control O(1) other genes, and a regime of complex control, where some core input genes control O(N) others.

Near-optimal configurations in mean-field disordered systems

We present a general technique to compute how the energy of a configuration varies as a function of its overlap with the ground state in the case of optimization problems. Our approach is based on a generalization of the cavity method to a system interacting with its ground state. With this technique we study the random matching problem as well as the mean-field diluted spin glass. As a by-product of this approach we calculate the de Almeida-Thouless transition line of the spin glass on a fixed connectivity random graph.

Polynomial iterative algorithms for coloring and analyzing random graphs

We study the graph coloring problem over random graphs of finite average connectivity c. Given a number q of available colors, we find that graphs with low connectivity admit almost always a proper coloring whereas graphs with high connectivity are uncolorable. Depending on q, we find with a one-step replica-symmetry breaking approximation the precise value of the critical average connectivity c(q). Moreover, we show that below c(q) there exists a clustering phase c in [c(d),c(q)] in which ground states spontaneously divide into an exponential number of clusters. Furthermore, we extended our considerations to the case of single instances showing consistent results. This leads us to propose a different algorithm that is able to color in polynomial time random graphs in the hard but colorable region, i.e., when c in [c(d),c(q)].