FELLONI , Sara

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...