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

Area of Science:

• Quantum Computing
• Theoretical Computer Science
• Algorithm Design

Background:

• Boolean satisfiability problems (SAT) are computationally challenging.
• Finding satisfying assignments for hard K-SAT instances is a significant problem in computer science.
• Existing methods may struggle with the complexity of large K-SAT instances.

Purpose of the Study:

• To develop a new quantum heuristic algorithm for solving hard K-SAT instances.
• To leverage quantum tunneling for efficient solution finding.
• To iteratively reduce the distance to a satisfying assignment state.

Main Methods:

• The algorithm employs a continuous time quantum walk.
• A specifically constructed Hamiltonian guides the quantum walk.
• Iterative steps involve quantum evolution, measurement, and state updates.
• Potential barriers are engineered into the Hamiltonian without prior knowledge of solutions.

Main Results:

• Numerical simulations demonstrate a success rate of 0.66 on the first run for 3-SAT instances.
• The algorithm was tested on thousands of 3-SAT instances with varying numbers of variables.
• The quantum walk exploits tunneling paths to approach satisfying assignments.
• Periodic measurements and tunneling help escape local minima.

Conclusions:

• The proposed quantum heuristic algorithm shows promise for solving hard K-SAT problems.
• Quantum tunneling is an effective property to exploit for SAT problem-solving.
• The algorithm's design allows for efficient exploration of the solution space.