We describe an algorithm to solve the problem of Boolean CNFSatisfiability when the input formula is chosen randomly. We build upon the algorithms of Schöning 1999 and Dantsin et al. in 2002. The Schöning algorithm works by trying many possible random assignments, and for each one searching systematically in the neighborhood of that assignment for a satisfying solution. Previous algorithms for this problem run in time O(2^(n (1 Ω(1)/k))). Our improvement is simple: we count how many clauses are satisfied by each randomly sampled assignment, and only search in the neighborhoods of assignments with abnormally many satisfied clauses. We show that assignments like these are significantly more likely to be near a satisfying assignment. This improvement saves a factor of 2^(n Ω(lg² k)/k), resulting in an overall runtime of O(2^(n (1 Ω(lg² k)/k))) for random kSAT.
Estimating the Density of States of Boolean Satisfiability Problems on Classical and Quantum Computing Platforms
Given a Boolean formula ϕ(x) in conjunctive normal form (CNF), the density of states counts the number of variable assignments that violate exactly e clauses, for all values of e. Thus, the density of states is a histogram of the number of unsatisfied clauses over all possible assignments. This computation generalizes both maximumsatisfiability (MAXSAT) and model counting problems and not only provides insight into the entire solution space, but also yields a measure for the hardness of the problem instance. Consequently, in realworld scenarios, this problem is typically infeasible even when using stateoftheart algorithms. While finding an exact answer to this problem is a computationally intensive task, we propose a novel approach for estimating density of states based on the concentration of measure inequalities. The methodology results in a quadratic unconstrained binary optimization (QUBO), which is particularly amenable to quantum annealingbased solutions. We present the overall approach and compare results from the DWave quantum annealer against the bestknown classical algorithms such as the Hamzede FreitasSelby (HFS) algorithm and satisfiability modulo theory (SMT) solvers.
 Publication Date:
 NSFPAR ID:
 10181036
 Journal Name:
 Proceedings of the AAAI Conference on Artificial Intelligence
 Volume:
 34
 Issue:
 02
 Page Range or eLocationID:
 1627 to 1635
 ISSN:
 21595399
 Sponsoring Org:
 National Science Foundation
More Like this


The constraint satisfaction problems kSAT and Quantum kSAT (kQSAT) are canonical NPcomplete and QMA_1complete problems (for k >= 3), respectively, where QMA_1 is a quantum generalization of NP with onesided error. Whereas kSAT has been wellstudied for special tractable cases, as well as from a parameterized complexity perspective, much less is known in similar settings for kQSAT. Here, we study the open problem of computing satisfying assignments to kQSAT instances which have a "matching" or "dimer covering"; this is an NP problem whose decision variant is trivial, but whose search complexity remains open. Our results fall into three directions, all of which relate to the "matching" setting: (1) We give a polynomialtime classical algorithm for kQSAT when all qubits occur in at most two clauses. (2) We give a parameterized algorithm for kQSAT instances from a certain nontrivial class, which allows us to obtain exponential speedups over brute force methods in some cases by reducing the problem to solving for a single root of a single univariate polynomial. (3) We conduct a structural graph theoretic study of 3QSAT interaction graphs which have a "matching". We remark that the results of (2), in particular, introduce a number of new tools tomore »

The Boolean constraint satisfaction problem 3SAT is arguably the canonical NPcomplete problem. In contrast, 2SAT can not only be decided in polynomial time, but in fact in deterministic linear time. In 2006, Bravyi proposed a physically motivated generalization of kSAT to the quantum setting, defining the problem "quantum kSAT". He showed that quantum 2SAT is also solvable in polynomial time on a classical computer, in particular in deterministic time O(n^4), assuming unitcost arithmetic over a field extension of the rational numbers, where n is number of variables. In this paper, we present an algorithm for quantum 2SAT which runs in linear time, i.e. deterministic time O(n+m) for n and m the number of variables and clauses, respectively. Our approach exploits the transfer matrix techniques of Laumann et al. [QIC, 2010] used in the study of phase transitions for random quantum 2SAT, and bears similarities with both the linear time 2SAT algorithms of Even, Itai, and Shamir (based on backtracking) [SICOMP, 1976] and Aspvall, Plass, and Tarjan (based on strongly connected components) [IPL, 1979].

Using IBM's publicly accessible quantum computers, we have analyzed the entropies of Schrödinger's cat states, which have the form Ψ = (1/2) 1/2 [0 0 0⋯0〉 + 1 1 1⋯1〉]. We have obtained the average Shannon entropy S So of the distribution over measurement outcomes from 75 runs of 8192 shots, for each of the numbers of entangled qubits, on each of the quantum computers tested. For the distribution over N faultfree measurements on pure cat states, S So would approach one as N → ∞, independent of the number of qubits; but we have found that S So varies nearly linearly with the number of qubits n . The slope of S So versus the number of qubits differs among computers with the same quantum volumes. We have developed a twoparameter model that reproduces the nearlinear dependence of the entropy on the number of qubits, based on the probabilities of observing the output 0 when a qubit is set to 0〉 and 1 when it is set to 1〉. The slope increases as the error rate increases. The slope provides a sensitive measure of the accuracy of a quantum computer, so it serves as a quickly determinable index of performance. We have usedmore »

Multiple known algorithmic paradigms (backtracking, local search and the polynomial method) only yield a 2n(1−1/O(k)) time algorithm for kSAT in the worst case. For this reason, it has been hypothesized that the worstcase kSAT problem cannot be solved in 2n(1−f(k)/k) time for any unbounded function f. This hypothesis has been called the “SuperStrong ETH”, modeled after the ETH and the Strong ETH. We give two results on the SuperStrong ETH: 1. It has also been hypothesized that kSAT is hard to solve for randomly chosen instances near the “critical threshold”, where the clausetovariable ratio is 2^kln2−Θ(1). We give a randomized algorithm which refutes the SuperStrong ETH for the case of random kSAT and planted kSAT for any clausetovariable ratio. For example, given any random kSAT instance F with n variables and m clauses, our algorithm decides satisfiability for F in 2^n(1−Ω(logk)/k) time, with high probability (over the choice of the formula and the randomness of the algorithm). It turns out that a wellknown algorithm from the literature on SAT algorithms does the job: the PPZ algorithm of Paturi, Pudlák and Zane [17]. 2. The Unique kSAT problem is the special case where there is at most one satisfying assignment. Improvingmore »