<Abstract>In this paper we present a classical parallel quantum algorithm for the satisfiability problem.We have exploited the classical parallelism of quantum algorithms developed in [G.L.Long and L.Xiao,Phys.R...<Abstract>In this paper we present a classical parallel quantum algorithm for the satisfiability problem.We have exploited the classical parallelism of quantum algorithms developed in [G.L.Long and L.Xiao,Phys.Rev.A 69 (2004) 052303],so that additional acceleration can be gained by using classical parallelism.The quantum algorithm first estimates the number of solutions using the quantum counting algorithm,and then by using the quantum searching algorithm,the explicit solutions are found.展开更多
DNA computation （DNAC） has been proposed to solve the satisfiability （SAT） problem due to operations in parallel on extremely large numbers of strands. This paper attempts to treat the DNA-based bio-molecular solu...DNA computation （DNAC） has been proposed to solve the satisfiability （SAT） problem due to operations in parallel on extremely large numbers of strands. This paper attempts to treat the DNA-based bio-molecular solution for the SAT problem from the quantum mechanical perspective with a purpose to explore the relationship between DNAC and quantum computation （QC）. To achieve this goal, it first builds up the correspondence of operations between QC and DNAC. Then it gives an example for the case of two variables and three clauses for details of this theory. It also demonstrates a three-qubit experiment for solving the simplest SAT problem with a single variable on a liquid-state nuclear magnetic resonance ensemble to verify this theory. Some discussions are made for the potential application and for further exploration of the present work.展开更多
The maximum satisfiability problem (MAX-SAT) refers to the task of finding a variable assignment that satisfies the maximum number of clauses (or the sum of weight of satisfied clauses) in a Boolean Formula. Most loca...The maximum satisfiability problem (MAX-SAT) refers to the task of finding a variable assignment that satisfies the maximum number of clauses (or the sum of weight of satisfied clauses) in a Boolean Formula. Most local search algorithms including tabu search rely on the 1-flip neighbourhood structure. In this work, we introduce a tabu search algorithm that makes use of the multilevel paradigm for solving MAX-SAT problems. The multilevel paradigm refers to the process of dividing large and difficult problems into smaller ones, which are hopefully much easier to solve, and then work backward towards the solution of the original problem, using a solution from a previous level as a starting solution at the next level. This process aims at looking at the search as a multilevel process operating in a coarse-to-fine strategy evolving from k-flip neighbourhood to 1-flip neighbourhood-based structure. Experimental results comparing the multilevel tabu search against its single level variant are presented.展开更多
As a complementary technology to Binary Decision Diagram-based(BDD-based) symbolic model checking, the verification techniques on Boolean satisfiability problem have gained an increasing wide of applications over the ...As a complementary technology to Binary Decision Diagram-based(BDD-based) symbolic model checking, the verification techniques on Boolean satisfiability problem have gained an increasing wide of applications over the last few decades, which brings a dramatic improvement for automatic verification. In this paper, we firstly introduce the theory about the Boolean satisfiability verification, including the description on the problem of Boolean satisfiability verification, Davis-Putnam-Logemann-Loveland(DPLL) based complete verification algorithm, and all kinds of solvers generated and the logic languages used by those solvers. Moreover, we formulate a large number optimizations of technique revolutions based on Boolean SATisfiability(SAT) and Satisfiability Modulo Theories(SMT) solving in detail, including incomplete methods such as bounded model checking, and other methods for concurrent programs model checking. Finally, we point out the major challenge pervasively in industrial practice and prospect directions for future research in the field of formal verification.展开更多
We present a quantum adiabatic algorithm for a set of quantum 2-satisfiability(Q2SAT)problem,which is a generalization of 2-satisfiability(2SAT)problem.For a Q2SAT problem,we construct the Hamiltonian which is similar...We present a quantum adiabatic algorithm for a set of quantum 2-satisfiability(Q2SAT)problem,which is a generalization of 2-satisfiability(2SAT)problem.For a Q2SAT problem,we construct the Hamiltonian which is similar to that of a Heisenberg chain.All the solutions of the given Q2SAT problem span the subspace of the degenerate ground states.The Hamiltonian is adiabatically evolved so that the system stays in the degenerate subspace.Our numerical results suggest that the time complexity of our algorithm is O(n^(3.9))for yielding non-trivial solutions for problems with the number of clauses m=dn(n-1)/2(d■0.1).We discuss the advantages of our algorithm over the known quantum and classical algorithms.展开更多
This paper reviews the recent literature on solving the Boolean satisfiability problem(SAT),an archetypal N P-complete problem,with the aid of machine learning(ML)techniques.Over the last decade,the machine learning s...This paper reviews the recent literature on solving the Boolean satisfiability problem(SAT),an archetypal N P-complete problem,with the aid of machine learning(ML)techniques.Over the last decade,the machine learning society advances rapidly and surpasses human performance on several tasks.This trend also inspires a number of works that apply machine learning methods for SAT solving.In this survey,we examine the evolving ML SAT solvers from naive classifiers with handcrafted features to emerging end-to-end SAT solvers,as well as recent progress on combinations of existing conflict-driven clause learning(CDCL)and local search solvers with machine learning methods.Overall,solving SAT with machine learning is a promising yet challenging research topic.We conclude the limitations of current works and suggest possible future directions.The collected paper list is available at https://github.com/ThinklabSJTU/awesome-ml4co.Keywords:Machine learning(ML),Boolean satisfiability(SAT),deep learning,graph neural networks(GNNs),combinatorial optimization.展开更多
基金supported by 973 Program under Grant No.2006CB921106National Natural Science Foundation of China under Grant No.60635040the Key Grant Project of the Ministry of Education under Grant No.306020
文摘<Abstract>In this paper we present a classical parallel quantum algorithm for the satisfiability problem.We have exploited the classical parallelism of quantum algorithms developed in [G.L.Long and L.Xiao,Phys.Rev.A 69 (2004) 052303],so that additional acceleration can be gained by using classical parallelism.The quantum algorithm first estimates the number of solutions using the quantum counting algorithm,and then by using the quantum searching algorithm,the explicit solutions are found.
基金Project supported by the National Natural Science Foundation of China (Grant Nos 10774163 and 10574143)the National Basic Research Program of China (Grant No 2006CB921203)
文摘DNA computation （DNAC） has been proposed to solve the satisfiability （SAT） problem due to operations in parallel on extremely large numbers of strands. This paper attempts to treat the DNA-based bio-molecular solution for the SAT problem from the quantum mechanical perspective with a purpose to explore the relationship between DNAC and quantum computation （QC）. To achieve this goal, it first builds up the correspondence of operations between QC and DNAC. Then it gives an example for the case of two variables and three clauses for details of this theory. It also demonstrates a three-qubit experiment for solving the simplest SAT problem with a single variable on a liquid-state nuclear magnetic resonance ensemble to verify this theory. Some discussions are made for the potential application and for further exploration of the present work.
文摘The maximum satisfiability problem (MAX-SAT) refers to the task of finding a variable assignment that satisfies the maximum number of clauses (or the sum of weight of satisfied clauses) in a Boolean Formula. Most local search algorithms including tabu search rely on the 1-flip neighbourhood structure. In this work, we introduce a tabu search algorithm that makes use of the multilevel paradigm for solving MAX-SAT problems. The multilevel paradigm refers to the process of dividing large and difficult problems into smaller ones, which are hopefully much easier to solve, and then work backward towards the solution of the original problem, using a solution from a previous level as a starting solution at the next level. This process aims at looking at the search as a multilevel process operating in a coarse-to-fine strategy evolving from k-flip neighbourhood to 1-flip neighbourhood-based structure. Experimental results comparing the multilevel tabu search against its single level variant are presented.
基金Supported by the National Natural Science Foundation of China(Nos.61063002,61100186,61262008)Guangxi Natural Science Foundation of China(2011GXNSFA018164,2011GXNSFA018166,2012GXNSFAA053220)the Key Project of Education Department of Guangxi
文摘As a complementary technology to Binary Decision Diagram-based(BDD-based) symbolic model checking, the verification techniques on Boolean satisfiability problem have gained an increasing wide of applications over the last few decades, which brings a dramatic improvement for automatic verification. In this paper, we firstly introduce the theory about the Boolean satisfiability verification, including the description on the problem of Boolean satisfiability verification, Davis-Putnam-Logemann-Loveland(DPLL) based complete verification algorithm, and all kinds of solvers generated and the logic languages used by those solvers. Moreover, we formulate a large number optimizations of technique revolutions based on Boolean SATisfiability(SAT) and Satisfiability Modulo Theories(SMT) solving in detail, including incomplete methods such as bounded model checking, and other methods for concurrent programs model checking. Finally, we point out the major challenge pervasively in industrial practice and prospect directions for future research in the field of formal verification.
基金Project supported by the National Key R&D Program of China(Grant Nos.2017YFA0303302 and 2018YFA0305602)the National Natural Science Foundation of China(Grant No.11921005)Shanghai Municipal Science and Technology Major Project,China(Grant No.2019SHZDZX01)。
文摘We present a quantum adiabatic algorithm for a set of quantum 2-satisfiability(Q2SAT)problem,which is a generalization of 2-satisfiability(2SAT)problem.For a Q2SAT problem,we construct the Hamiltonian which is similar to that of a Heisenberg chain.All the solutions of the given Q2SAT problem span the subspace of the degenerate ground states.The Hamiltonian is adiabatically evolved so that the system stays in the degenerate subspace.Our numerical results suggest that the time complexity of our algorithm is O(n^(3.9))for yielding non-trivial solutions for problems with the number of clauses m=dn(n-1)/2(d■0.1).We discuss the advantages of our algorithm over the known quantum and classical algorithms.
基金supported by National Key Research and Development Program of China(No.2020AAA0107600)National Science Foundation of China(No.62102258)+2 种基金Shanghai Pujiang Program,China(No.21PJ1407300)Shanghai Municipal Science and Technology Major Project,China(No.2021SHZDZX0102)Science and Technology Commission of Shanghai Municipality Project,China(No.22511105100),and also sponsored by Huawei Ltd,China.
文摘This paper reviews the recent literature on solving the Boolean satisfiability problem(SAT),an archetypal N P-complete problem,with the aid of machine learning(ML)techniques.Over the last decade,the machine learning society advances rapidly and surpasses human performance on several tasks.This trend also inspires a number of works that apply machine learning methods for SAT solving.In this survey,we examine the evolving ML SAT solvers from naive classifiers with handcrafted features to emerging end-to-end SAT solvers,as well as recent progress on combinations of existing conflict-driven clause learning(CDCL)and local search solvers with machine learning methods.Overall,solving SAT with machine learning is a promising yet challenging research topic.We conclude the limitations of current works and suggest possible future directions.The collected paper list is available at https://github.com/ThinklabSJTU/awesome-ml4co.Keywords:Machine learning(ML),Boolean satisfiability(SAT),deep learning,graph neural networks(GNNs),combinatorial optimization.
