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 phi of 3-SAT, a quantum Fredkin circuit that computes a superposition of all classical evaluations of phi 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 @f 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.

Leporati, A., Felloni, S. (2007). Three "quantum" algorithms to solve 3-SAT. THEORETICAL COMPUTER SCIENCE, 372(2-3), 218-241 [10.1016/j.tcs.2006.11.026].

Three "quantum" algorithms to solve 3-SAT

LEPORATI, ALBERTO OTTAVIO;
2007

Abstract

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 phi of 3-SAT, a quantum Fredkin circuit that computes a superposition of all classical evaluations of phi 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 @f 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.
Articolo in rivista - Articolo scientifico
Membrane computing; Quantum P systems; 3-SAT
English
2007
372
2-3
218
241
none
Leporati, A., Felloni, S. (2007). Three "quantum" algorithms to solve 3-SAT. THEORETICAL COMPUTER SCIENCE, 372(2-3), 218-241 [10.1016/j.tcs.2006.11.026].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/13111
Citazioni
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 7
Social impact