A parallel spatial quantum search algorithm applied to the 3-SAT problem
This work presents a quantum search algorithm to solve the 3-SAT problem. An improvement over one of the best known classical algorithms for this problem is proposed, replacing the local search with a quantum search algorithm. The performance of the improved algorithm is assessed by simulating it us...
| Autores principales: | , , |
|---|---|
| Formato: | Objeto de conferencia |
| Lenguaje: | Español |
| Publicado: |
2011
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/125243 |
| Aporte de: |
| id |
I19-R120-10915-125243 |
|---|---|
| record_format |
dspace |
| institution |
Universidad Nacional de La Plata |
| institution_str |
I-19 |
| repository_str |
R-120 |
| collection |
SEDICI (UNLP) |
| language |
Español |
| topic |
Ciencias Informáticas 3-SAT algorithm |
| spellingShingle |
Ciencias Informáticas 3-SAT algorithm Hernández Barreto, Miguel A. Abal, G. Nesmachnow, Sergio A parallel spatial quantum search algorithm applied to the 3-SAT problem |
| topic_facet |
Ciencias Informáticas 3-SAT algorithm |
| description |
This work presents a quantum search algorithm to solve the 3-SAT problem. An improvement over one of the best known classical algorithms for this problem is proposed, replacing the local search with a quantum search algorithm. The performance of the improved algorithm is assessed by simulating it using parallel programming techniques with shared memory. The experimental analysis demonstrate that the parallel simulation of the algorithm takes advantage of the available computing resources to improve over the eficiency of the sequential version, thus allowing to perform realistic simulations in reduced execution times. |
| format |
Objeto de conferencia Objeto de conferencia |
| author |
Hernández Barreto, Miguel A. Abal, G. Nesmachnow, Sergio |
| author_facet |
Hernández Barreto, Miguel A. Abal, G. Nesmachnow, Sergio |
| author_sort |
Hernández Barreto, Miguel A. |
| title |
A parallel spatial quantum search algorithm applied to the 3-SAT problem |
| title_short |
A parallel spatial quantum search algorithm applied to the 3-SAT problem |
| title_full |
A parallel spatial quantum search algorithm applied to the 3-SAT problem |
| title_fullStr |
A parallel spatial quantum search algorithm applied to the 3-SAT problem |
| title_full_unstemmed |
A parallel spatial quantum search algorithm applied to the 3-SAT problem |
| title_sort |
parallel spatial quantum search algorithm applied to the 3-sat problem |
| publishDate |
2011 |
| url |
http://sedici.unlp.edu.ar/handle/10915/125243 |
| work_keys_str_mv |
AT hernandezbarretomiguela aparallelspatialquantumsearchalgorithmappliedtothe3satproblem AT abalg aparallelspatialquantumsearchalgorithmappliedtothe3satproblem AT nesmachnowsergio aparallelspatialquantumsearchalgorithmappliedtothe3satproblem AT hernandezbarretomiguela parallelspatialquantumsearchalgorithmappliedtothe3satproblem AT abalg parallelspatialquantumsearchalgorithmappliedtothe3satproblem AT nesmachnowsergio parallelspatialquantumsearchalgorithmappliedtothe3satproblem |
| bdutipo_str |
Repositorios |
| _version_ |
1764820451434954756 |