Quantum tunneling and quantum walks as algorithmic resources to solve hard K-SAT instances

Abstract We present a new quantum heuristic algorithm aimed at finding satisfying assignments for hard K-SAT instances using a continuous time quantum walk that explicitly exploits the properties of quantum tunneling. Our algorithm uses a Hamiltonian $$H_A(F)$$ H A ( F ) which is specifically constr...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Ernesto Campos, Salvador E. Venegas-Andraca, Marco Lanzagorta
Formato:	article
Lenguaje:	EN
Publicado:	Nature Portfolio 2021
Materias:	Medicine R Science Q
Acceso en línea:	https://doaj.org/article/362d451aae42424eadb4a41e9adb6af9
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:362d451aae42424eadb4a41e9adb6af9
record_format	dspace
spelling	oai:doaj.org-article:362d451aae42424eadb4a41e9adb6af92021-12-02T15:10:54ZQuantum tunneling and quantum walks as algorithmic resources to solve hard K-SAT instances10.1038/s41598-021-95801-12045-2322https://doaj.org/article/362d451aae42424eadb4a41e9adb6af92021-08-01T00:00:00Zhttps://doi.org/10.1038/s41598-021-95801-1https://doaj.org/toc/2045-2322Abstract We present a new quantum heuristic algorithm aimed at finding satisfying assignments for hard K-SAT instances using a continuous time quantum walk that explicitly exploits the properties of quantum tunneling. Our algorithm uses a Hamiltonian $$H_A(F)$$ H A ( F ) which is specifically constructed to solve a K-SAT instance F. The heuristic algorithm aims at iteratively reducing the Hamming distance between an evolving state $${\|{\psi _j}\rangle }$$ \| ψ j ⟩ and a state that represents a satisfying assignment for F. Each iteration consists on the evolution of $${\|{\psi _j}\rangle }$$ \| ψ j ⟩ (where j is the iteration number) under $$e^{-iH_At}$$ e - i H A t , a measurement that collapses the superposition, a check to see if the post-measurement state satisfies F and in the case it does not, an update to $$H_A$$ H A for the next iteration. Operator $$H_A$$ H A describes a continuous time quantum walk over a hypercube graph with potential barriers that makes an evolving state to scatter and mostly follow the shortest tunneling paths with the smaller potentials that lead to a state $${\|{s}\rangle }$$ \| s ⟩ that represents a satisfying assignment for F. The potential barriers in the Hamiltonian $$H_A$$ H A are constructed through a process that does not require any previous knowledge on the satisfying assignments for the instance F. Due to the topology of $$H_A$$ H A each iteration is expected to reduce the Hamming distance between each post measurement state and a state $${\|{s}\rangle }$$ \| s ⟩ . If the state $${\|{s}\rangle }$$ \| s ⟩ is not measured after n iterations (the number n of logical variables in the instance F being solved), the algorithm is restarted. Periodic measurements and quantum tunneling also give the possibility of getting out of local minima. Our numerical simulations show a success rate of 0.66 on measuring $${\|{s}\rangle }$$ \| s ⟩ on the first run of the algorithm (i.e., without restarting after n iterations) on thousands of 3-SAT instances of 4, 6, and 10 variables with unique satisfying assignments.Ernesto CamposSalvador E. Venegas-AndracaMarco LanzagortaNature PortfolioarticleMedicineRScienceQENScientific Reports, Vol 11, Iss 1, Pp 1-18 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	Medicine R Science Q
spellingShingle	Medicine R Science Q Ernesto Campos Salvador E. Venegas-Andraca Marco Lanzagorta Quantum tunneling and quantum walks as algorithmic resources to solve hard K-SAT instances
description	Abstract We present a new quantum heuristic algorithm aimed at finding satisfying assignments for hard K-SAT instances using a continuous time quantum walk that explicitly exploits the properties of quantum tunneling. Our algorithm uses a Hamiltonian $$H_A(F)$$ H A ( F ) which is specifically constructed to solve a K-SAT instance F. The heuristic algorithm aims at iteratively reducing the Hamming distance between an evolving state $${\|{\psi _j}\rangle }$$ \| ψ j ⟩ and a state that represents a satisfying assignment for F. Each iteration consists on the evolution of $${\|{\psi _j}\rangle }$$ \| ψ j ⟩ (where j is the iteration number) under $$e^{-iH_At}$$ e - i H A t , a measurement that collapses the superposition, a check to see if the post-measurement state satisfies F and in the case it does not, an update to $$H_A$$ H A for the next iteration. Operator $$H_A$$ H A describes a continuous time quantum walk over a hypercube graph with potential barriers that makes an evolving state to scatter and mostly follow the shortest tunneling paths with the smaller potentials that lead to a state $${\|{s}\rangle }$$ \| s ⟩ that represents a satisfying assignment for F. The potential barriers in the Hamiltonian $$H_A$$ H A are constructed through a process that does not require any previous knowledge on the satisfying assignments for the instance F. Due to the topology of $$H_A$$ H A each iteration is expected to reduce the Hamming distance between each post measurement state and a state $${\|{s}\rangle }$$ \| s ⟩ . If the state $${\|{s}\rangle }$$ \| s ⟩ is not measured after n iterations (the number n of logical variables in the instance F being solved), the algorithm is restarted. Periodic measurements and quantum tunneling also give the possibility of getting out of local minima. Our numerical simulations show a success rate of 0.66 on measuring $${\|{s}\rangle }$$ \| s ⟩ on the first run of the algorithm (i.e., without restarting after n iterations) on thousands of 3-SAT instances of 4, 6, and 10 variables with unique satisfying assignments.
format	article
author	Ernesto Campos Salvador E. Venegas-Andraca Marco Lanzagorta
author_facet	Ernesto Campos Salvador E. Venegas-Andraca Marco Lanzagorta
author_sort	Ernesto Campos
title	Quantum tunneling and quantum walks as algorithmic resources to solve hard K-SAT instances
title_short	Quantum tunneling and quantum walks as algorithmic resources to solve hard K-SAT instances
title_full	Quantum tunneling and quantum walks as algorithmic resources to solve hard K-SAT instances
title_fullStr	Quantum tunneling and quantum walks as algorithmic resources to solve hard K-SAT instances
title_full_unstemmed	Quantum tunneling and quantum walks as algorithmic resources to solve hard K-SAT instances
title_sort	quantum tunneling and quantum walks as algorithmic resources to solve hard k-sat instances
publisher	Nature Portfolio
publishDate	2021
url	https://doaj.org/article/362d451aae42424eadb4a41e9adb6af9
work_keys_str_mv	AT ernestocampos quantumtunnelingandquantumwalksasalgorithmicresourcestosolvehardksatinstances AT salvadorevenegasandraca quantumtunnelingandquantumwalksasalgorithmicresourcestosolvehardksatinstances AT marcolanzagorta quantumtunnelingandquantumwalksasalgorithmicresourcestosolvehardksatinstances
_version_	1718387621882757120

Quantum tunneling and quantum walks as algorithmic resources to solve hard K-SAT instances

Ejemplares similares