| | |
| | |
Stat |
Members: 3645 Articles: 2'506'133 Articles rated: 2609
27 April 2024 |
|
| | | |
|
Article overview
| |
|
Efficient Quantum Algorithm for a Class of 2-SAT Problems | Biao Wu
; Hongye Yu
; Frank Wilczek
; | Date: |
14 Dec 2018 | Abstract: | We 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 |
|
|
No review found.
Did you like this article?
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.
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |