|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'585
Articles rated: 2609
24 April 2024 |
|
| | | | |
|
Article forum
| |
|
|
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 message found in this article forum.
You have a question or message about this article?
Ask the community and write a message in the forum.
If you want to rate this article, please use the review section..
To add a message in the forum, you need to login or register first. (free): registration page
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER