Repositorio de producción científica de la Universidad de Sevilla

Three Quantum Algorithms to Solve 3-SAT


Advanced Search
Opened Access Three Quantum Algorithms to Solve 3-SAT
Show item statistics
Export to
Author: Leporati, Alberto
Felloni, Sara
Date: 2006
Published in: Proceedings of the Fourth Brainstorming Week on Membrane Computing, Vol.II, 137-159. Sevilla, E.T.S. de Ingeniería Informática, 30 de Enero-3 de Febrero, 2006
ISBN/ISSN: 8461106814
Document type: Presentation
Abstract: We propose three quantum algorithms to solve the 3-SAT NP-complete decision problem. The first algorithm builds, for any instance Á of 3-SAT, a quantum Fredkin circuit that computes a superposition of all classical evaluations of Á in a given output line. Similarly, the second and third algorithms compute the same superposition on a given register of a quantum register machine, and as the energy of a given membrane in a quantum P system, respectively. Assuming that a specific non-unitary operator, built using the well known creation and annihilation operators, can be realized as a quantum gate, as an instruction of the quantum register machine, and as a rule of the quantum P system, respectively, we show how to decide whether Á is a positive instance of 3-SAT. The construction relies also upon the assumption that an external observer is able to distinguish, as the result of a measurement, between a null and a non-null vector.
Size: 257.7Kb
Format: PDF


This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)