Three “quantum” algorithms to solve 3-SAT

In this paper we borrow some ideas from quantum computing, and we propose three “quantum” brute force 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 a truncated version of 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 discriminate, as the result of a measurement, a null vector from a non-null vector.