Quantum algorithm for a set of quantum 2SAT problems

We present a quantum adiabatic algorithm for a set of quantum 2-satisfiability (Q2SAT) problem, which is a generalization of 2-satisfiability (2SAT) problem. For a Q2SAT problem, we construct the Hamiltonian which is similar to that of a Heisenberg chain. All the solutions of the given Q2SAT problem span the subspace of the degenerate ground states. The Hamiltonian is adiabatically evolved so that the system stays in the degenerate subspace. Our numerical results suggest that the time complexity of our algorithm is O(n(3.9)) for yielding non-trivial solutions for problems with the number of clauses m = dn(n - 1)/2 (d less than or similar to 0.1). We discuss the advantages of our algorithm over the known quantum and classical algorithms.

Automated summary

The study introduces a quantum adiabatic algorithm for solving Q2SAT problems by constructing a Hamiltonian similar to a Heisenberg chain, evolving the system to stay in the degenerate subspace, and obtaining non-trivial solutions. Numerical results suggest a time complexity of O(n^(3.9)), and advantages over known quantum and classical algorithms are discussed.