DocumentCode
3420775
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
fYear
2012
fDate
Oct. 29 2012-Nov. 1 2012
Firstpage
1
Lastpage
5
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;
fLanguage
English
Publisher
ieee
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
Type
conf
DOI
10.1109/ICSICT.2012.6467864
Filename
6467864
Link To Document