forgot password?
register here
Research articles
  search articles
  reviews guidelines
  articles index
My Pages
my alerts
  my messages
  my reviews
  my favorites
Members: 3652
Articles: 2'545'386
Articles rated: 2609

24 June 2024
  » arxiv » 1812.5846

 Article overview

Efficient Quantum Algorithm for a Class of 2-SAT Problems
Biao Wu ; Hongye Yu ; Frank Wilczek ;
Date 14 Dec 2018
AbstractWe present an efficient quantum algorithm for a class of 2-satisfiability (2-SAT) problems. For a given 2-SAT problem, a Hamiltonian is constructed so that the solutions of the 2-SAT problem are its degenerate ground states. The key step in our algorithm is to evolve adiabatically in the subspace of the degenerate ground states. Numerically we focus on a special case that the number of Boolean variables is equal to the number of clauses. Our numerical results indicate that the time complexity of our quantum algorithm is $O(1)$ whereas its classical counterpart is $O(n)$. In the end, we point out that the adiabatic evolution in the degenerate subspace can be viewed equivalently as a quantum diffusion process in a rather randomly connected $n$-dimensional cube.
Source arXiv, 1812.5846
Services Forum | Review | PDF | Favorites   
Visitor rating: did you like this article? no 1   2   3   4   5   yes

No review found.
 Did you like this article?

This article or document is ...
of broad interest:
Global appreciation:

  Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.

browser CCBot/2.0 (
» my Online CV
» Free

home  |  contact  |  terms of use  |  sitemap
Copyright © 2005-2024 - Scimetrica