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

Ernesto Campos; Salvador E Venegas-Andraca; Marco Lanzagorta

doi:10.1038/s41598-021-95801-1

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

Sci Rep. 2021 Aug 19;11(1):16845. doi: 10.1038/s41598-021-95801-1.

Authors

Ernesto Campos^{1

2}, Salvador E Venegas-Andraca³, Marco Lanzagorta⁴

Affiliations

¹ Tecnologico de Monterrey, Escuela de Ingenieria y Ciencias, Av Eugenio Garza Sada 2501, Mty, NL, Mexico.
² Skolkovo Institute of Science and Technology, 3 Nobel Street, Skolkovo, 121205, Moscow, Russia.
³ Tecnologico de Monterrey, Escuela de Ingenieria y Ciencias, Av Eugenio Garza Sada 2501, Mty, NL, Mexico. svenegas@tec.mx.
⁴ US Naval Research Laboratory, 4555 Overlook Ave., SW Washington, DC, 20375, USA.

Abstract

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

Abstract

Grants and funding