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...

Full description

Saved in:
Bibliographic Details
Published in:Chinese physics B 2021-02, Vol.30 (2), p.20308-67
Main Authors: Hu, Yanglin, Zhang, Zhelun, Wu, Biao
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 ≲ 0.1). We discuss the advantages of our algorithm over the known quantum and classical algorithms.
ISSN:1674-1056
DOI:10.1088/1674-1056/abd741