|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
20 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.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER