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 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 |psi j and a state that represents a satisfying assignment for F. Each iteration consists on the evolution of |psi j (where j is the iteration number) under 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 HA for the next iteration. Operator 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 |s that represents a satisfying assignment for F. The potential barriers in the Hamiltonian 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 HA each iteration is expected to reduce the Hamming distance between each post measurement state and a state |s. If the state |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 |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.

Automated summary

The algorithm utilizes continuous time quantum walk and quantum tunneling to iteratively reduce the Hamming distance between states for solving K-SAT instances, without prior knowledge about satisfying assignments. The Hamiltonian is designed to reduce Hamming distance in each iteration and escape local minima through periodic measurements and quantum tunneling. Numerical simulations show a success rate of 0.66 on the first run for thousands of 3-SAT instances with unique satisfying assignments.