Title :
A quantum method to test the satisfiability of Boolean functions
Author :
Jin Wang ; Jialin Chen ; Chaofan Yu ; Linli Wang
Author_Institution :
State Key Lab. of ASIC & Syst., Fudan Univ., Shanghai, China
fDate :
Oct. 29 2012-Nov. 1 2012
Abstract :
Satisfiability (SAT) problem is one of the NP-hard problems. General SAT problem can be solved in polynomial time when the given formula contains only binary clauses (2-SAT). Quantum computation possesses some virtues that exceeding classical computation in speed, therefore it has the potential ability to solve NP-complete problems better than with classical methods. This paper introduces a new method to test the satisfiability of Boolean functions based on quantum ETOF gates.
Keywords :
Boolean functions; optimisation; polynomials; quantum gates; 2-SAT; Boolean function; NP-hard problem; binary clauses; polynomial time; quantum ETOF gate; quantum method; satisfiability problem; Boolean functions; Buildings; Computer science; Logic gates; Quantum computing; Time complexity; Transforms;
Conference_Titel :
Solid-State and Integrated Circuit Technology (ICSICT), 2012 IEEE 11th International Conference on
Conference_Location :
Xi´an
Print_ISBN :
978-1-4673-2474-8
DOI :
10.1109/ICSICT.2012.6467864
