{'fraction_non_alphanumeric': 0.03636972164890947, 'fraction_numerical': 0.009259775757237685, 'mean_word_length': 4.181502890173411, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Classical-Quantum Mixing in the Random 2-Satisfiability Problem

Classical satisfiability (SAT) and quantum satisfiability (QSAT) are complete problems for the complexity classes NP and QMA which are believed to be intractable for classical and quantum computers, respectively. Statistical ensembles of instances of these problems have been studied previously in an attempt to elucidate their typical, as opposed to worst case, behavior. In this paper we introduce a new statistical ensemble that interpolates between classical and quantum. For the simplest 2-SAT/2-QSAT ensemble we find the exact boundary that separates SAT and UNSAT instances. We do so by establishing coincident lower and upper bounds, in the limit of large instances, on the extent of the UNSAT and SAT regions, respectively.

In the second approach, the introduction of an appropriate measure on the instances of a problem generates a question in statistical Physics. Instead of worrying about worst case complexity, we attempt to understand the structure of problems which are typical with respect to the measure. For example, phase transitions which arise as functions of parameters controlling the measure often signal the regimes where the most complicated problems may be found [5]. This approach builds on the seminal insight of Fu and Anderson [6] that the intractability of NP-complete problems is a form, indeed an extreme one, of (spin) glassiness. Ensembles of both classical SAT [7,8] and, more recently, QSAT [9][10][11] have been studied in this fashion.
In this paper we build on the second approach and introduce new ensembles that interpolate between the SAT and QSAT ones. Specifically for the 2-SAT/2-QSAT interpolation, we show that there is a sharp phase boundary ( Fig. 1) which we determine rigorously by deriving coincident lower and upper bounds on the extent of the UNSAT and SAT regions, respectively. The interest in this interpolation flows considerably from a remarkable "geometrization" theorem that applies to the QSAT limit [9]. As this result is not widely known, we begin with a quick review of the relevant background which will also enable a proper definition of the problem studied herein. We then present our central technical results on the phase boundary and close with some remarks on the lessons learned and future directions. SAT, QSAT, and the mixed ensemble: An instance of k-QSAT is defined by a positive semi-definite Hamiltonian on N qubits given by the sum of M k-body interactions, H = M m=1 Π m . Here, each interaction Π m = |φ φ| m projects onto a particular state in the local Hilbert space of the k qubits associated with interaction m. The computational problem is to decide whether H has a ground state of energy zero. If so, the problem is SAT and if not, it is UNSAT [12]. If the states |φ m are computational basis states, we recover classical k-SAT as a special case. We can now summarize the statistical ensembles used in previous work. These involve the uniform Erdős-Rényi measure [13][14][15], parametrized by the 'clause density' α = M/N , over the set of k-hypergraphs representing the interactions in H. The interaction associated to each hyperedge is likewise uniformly chosen from the 2 k projectors in classical SAT or from the Haar measure over the rays in the 2 k dimensional Hilbert space for QSAT. We observe that the latter makes classical SAT instances highly non-generic within the QSAT ensemble and so these two can be expected to behave very differently, and indeed they do [7,8].
The classical ensemble has been studied intensively. The broad picture that has emerged is that for all k ≥ 2 there is a sharp SAT-UNSAT transition in the N → ∞ limit as a function of α. For k ≥ 3, there are additional transitions in the SAT regime wherein the structure of the solution space changes. For the quantum ensemble, it is known that there is a SAT-UNSAT transition for k ≥ 2 [9,10,16] and that there is at least one sharp transition involving the growth of entanglement in the satisfying states for k ≥ 12 [10,17]. But perhaps the most remarkable result to come out of the quantum generalization is a "geometrization theorem" [9] wherein uniformly chosen quantum projectors on any graph exhibit the same dimension of the satisfying manifold with probability 1. This reduces the generic QSAT decision problem to a purely graph theoretic question! The identification of this implicit graph theoretic property for k ≥ 3 and understanding its computational difficulty is an outstanding problem.
As advertised above, we initiate a new approach by introducing ensembles that interpolate between the fully classical and quantum regimes. We do this by constraining each realization to include a fraction β of uniformly chosen quantum projectors and 1 − β uniformly chosen classical ones. As β varies between 0 and 1, we pass from the classical ensemble to the quantum one. As the classical ensemble does not exhibit geometrization and typically has larger satisfying manifolds, the interpolation has the potential to shed light on the emergence of geometrization in the quantum limit and thence on precisely where in the ensemble one might look for genuinely difficult quantum cases.
As a first step in this program, we study the case of 2-SAT/QSAT. We generate the underlying 2-graphs by drawing edges between any two sites with probability αN/ N 2 . In the thermodynamic limit N → ∞ this generates an Erdős-Rényi (ER) random graph with M = αN expected edges. For each edge m = 1...M we label it 'quantum' with probability β and 'classical' with probability 1 − β: we write e m ∈ {Q, C} if the edge between sites (m, m + 1) is quantum or classical. The purely classical and quantum limits are very well understood. At β = 0 [18][19][20] there is a sharp SAT-UNSAT transition at α c = 1 while for β = 1, there is a SAT-UNSAT transition at α q = 1/2 [9]. The quantum transition coincides with the emergence of a giant component in the underlying random graph [14]. The snip-core: The primary tool in our analysis is snipping qubits out of an interaction graph G. Classically, a node i is snippable if all of the bonds connected to it agree about the bit arrangement they locally disfavor. All clauses attached to such a snippable node i can then be trivially satisfied by assigning the appropriate value to qubit i. Thus, these bonds can be snipped from the graph G to produce a smaller graph G which is SAT if and only if the original G is. This definition extends naturally to the mixed classical-quantum problem (β = 0): if a generic quantum edge attaches to a site i of degree greater than 1, it cannot be locally satisfied by the state on i without reference to the rest of the graph G (with probability 1). Thus, any site of degree at least 2 with a quantum edge attached is unsnippable.
For a random instance G of the mixed problem, we can iteratively remove snippable sites and the incident edges in a similar fashion to the "Leaf Removal" Algorithm [21]. When there are no snippable qubits left, this algorithm stops and we end up with a unique maximal snip-core. Clearly, G is SAT iff its snip-core is SAT. Moreover, if the snip-core is empty then G is SAT. Behind our considerations lies the result that when G is SAT we can always find a satisfying product state [3]. We will now analyze the structure and probability of non-empty snip-cores in order to determine the SAT-UNSAT boundary. Upper bound on SAT region: The basic idea in this part is to identify an UNSAT motif that must be present on all snip-cores for α > α c (β) thus establishing an upper bound on the extent of the SAT region. To this end, we first note that the simplest motif that is unsnippable is the unsnippable loop. A loop with classical and quantum edges is said to be unsnippable if all of its sites are unsnippable [see Fig. 2(a)]. We can find a simple example in the fully classical problem: a loop that dislikes 01 on each edge. While this loop is unsnippable, it is SAT: it has exactly two satisfying states comprised of all sites 0 or all sites 1. The same is true of the other 2 L such classical unsnippable loops of length L which are equivalent under "gauge" transformations. Laumann et al. [9] have shown that the fully quantum loop also has two SAT states. Moreover, based on their Geometrization Theorem we can conclude that the dimension of the kernel of the fully quantum problem is a lower bound for the mixed problem, whereas the fully classical one is an upper bound: we start from the classical unsnippable loop and slowly turn classical projectors into generic quantum ones; this can only decrease the degeneracy of satisfying states. But since both kernels have dimension two, we conclude that the mixed classical-quantum unsnippable loop always has exactly two linearly independent SAT states. Finally, an unsnippable but UNSAT motif can be constructed by decorating the unsnippable loop with two unsnippable cross-links-strings joining two different points on the loop whose interior sites are unsnippable [ Fig. 2(b)] that penalize the two SAT states.
We now turn to the probability of finding UNSAT unsnippable loops with cross-links. Quite generally, the expected number of subgraphs A in the ER ensemble on N nodes is where |A| and e(A) represent the number of vertices and edges of A, respectively; Aut(A) is the number of automorphisms of A and p = αN/ N 2 . For a loop of length L we have |L| = e(L) = L and Aut(L) = 2L. Introducing the probability that a given loop is unsnippable, we find the expected number of unsnippable loops # uns (L) is From this, one can show readily that # uns (L) for any fixed length L is independent of N as N → ∞. Furthermore, we see that the addition of cross-links of finite length causes the expected number of motifs to vanish in that limit. Indeed, this result holds irrespective of the form of p(L is unsnippable) since it is simply a property of the ER graphs. It follows that in order to get a nonvanishing number of our UNSAT motifs we must consider sizes that scale with N such as ones that contain giant loops L = lN (0 < l ≤ 1).
To calculate their number we need the last factor in Eq. (2). Note that for a collection {e i } of M edges, the probability that site i is unsnippable is 1−δ ei,C δ ei+1,C /2. If it is connected to a quantum edge then it is unsnippable with probability 1; otherwise it is unsnippable with probability 1/2. Also, from the definition of the random ensemble we have p(e i = Q) = β and p(e i = C) = 1 − β. Hence, we find that for a loop of length L (3) Using a standard transfer matrix and focusing solely on the dominant eigenvalue λ + which will control the result for large loops, we find that (4) With this in hand, we return to Eq. (2) and using Stirling's approximation for log(# uns ) we find that the extensive, O(N ), piece of the entropy is Observe that giant unsnippable loops proliferate exponentially in N if the entropy function is positive for some 1 ≥ l > 0. Since S uns (0) = 0 and S uns (l) = N [log(2αλ + ) + log(1 − l)] ≤ N log(2αλ + ), we see that S uns (l) is a negative and decreasing function on 0 < l ≤ 1 for 2αλ + < 1. However, for 2αλ + > 1, the entropy goes positive for small l and large numbers of giant unsnippable loops emerge. As we find O(e N ) loops on just N sites, the loops must intersect and overlap repeatedly. It follows that any given giant loop is covered by a finite density of cross-links and therefore the probability of finding an UNSAT unsnippable loop with cross-links approaches 1 as N → ∞ for α greater than α c (β) = 2 Hence, we conclude that that α c (β) is an upper bound on the extent of the SAT region at any fixed β. Lower bound on UNSAT region: We will now show that for α < α c (β) the snip-core is always SAT so that α c (β) is also a lower bound on the extent of the UNSAT region. We do this by showing that the snip-core must contain one of a finite list of motifs [22] and that all of these except SAT unsnippable loops are not present as N → ∞ for α < α c (β).
To show that there is a finite list of necessary motifs, we start from an arbitrary site in the snip-core which we label 1 and walk along any edge which we label e 1 that connects it to a site 2 [see Fig. 2(c)]. At step 2, we walk along an edge e 2 to site 3 such that 2 is unsnippable with respect to edges e 1 and e 2 . Thus, e 2 can either be quantum or, if it is classical, it has to disagree with e 1 on site 2. From this point onward, we take further steps as follows: • At step k: we move along an edge e k that connects it to k + 1 such that site k is unsnippable.
• Iterate until we pass through a site i twice.
Since the size of the snip-core is finite at any given N, then each such path must be self-intersecting. Therefore, the algorithm stops in either of the following scenarios: 1. The path returns to the starting point (i = 1) and we end up with a loop. There are two subcases: (a) If all sites on the loop have degree 2 then the loop must be unsnippable [ Fig. 2(a)].
(b) If there exists a site on the loop that has a degree of at least 3 then we walk one step away from the loop starting at that site as before and get a "lasso motif" [Fig. 2(c)].
2. The path crosses itself at a site i = 1 and we encounter the same lasso motif.
At this point, we continue from the open end of the lasso and generate unsnippable sites as before. Again, our path will necessarily return and touch the lasso. When this happens, we will end up with one of three motifs: an unsnippable loop with one cross-link [ Fig. 2(d) Fig. 2(a)], these constitute the set of structures of which at least one must be present on each non-empty disconnected component of a snip core. Strictly speaking, we should classify somewhat more finely by specifying the unsnippability of each loop passing through the degree 3 and 4 sites in these motifs. But that will only change our estimates below by constant factors as N → ∞ so we will refrain from exhibiting these details here. Now for the frequency of occurrence of these motifs. In the limit N → ∞ for any fixed number of sites L, the expected number of loops is O(N 0 ), while the expected numbers of the other three are O(1/N ) and hence vanish. As before, we are led to examine giant versions of these graphs. The most optimistic case assumes that all the individual legs of the motifs are large and diverge with N . In this case, the expected numbers take the form where a is the number of automorphisms (a = 4 for the figure eight and the dumbbell and a = 2 for the loop with a single cross-link) and c is an O(1) number (dependent on β) associated with the precise unsnippability of vertices that have degree at least 3 alluded to above. The reader can check that for α < α c (β) these expected numbers vanish also for large motifs where L = lN γ for any l and 0 < γ ≤ 1. Hence, the loop with cross-link, figure eight, and dumbbell are entirely absent for α < α c (β) and the snipcore is either empty or composed entirely of unsnippable loops. Such snip-cores are SAT so we can conclude that our starting graphs are SAT for α < α c (β) with probability 1 and thus α c (β) is a lower bound on the extent of the UNSAT region at fixed β. Putting together the upper and the lower bounds, we conclude that α c (β) from Eq. (6) represents the exact location of the phase boundary between SAT and UNSAT in the α−β plane as shown in Fig. 1. Concluding remarks: In the preceding we have introduced a new family of mixed classical-quantum ensembles for the k-SAT/QSAT problems and established the exact phase diagram for the simplest member of this family with k = 2. We note that the shape of the phase boundary is consistent with what is known about the limits. The quantum limit is insensitive to the choice of projectors and we find that the restriction of a dilute concentration of projectors to classical values barely shifts the phase boundary. The classical limit is sensitive to the choice of projectors and the phase boundary near it is maximally sensitive to the inclusion of a dilute set of quantum projectors. A problem that we leave open is c) The "lasso" motif. We start from a random site 1 and move along an unsnippable path until we pass through the same site i twice. The loop can either be unsnippable (x = 1) or snippable at site i (x = 0). d) The loop with a single cross-link. We encounter this motif if we traverse the dangling branch of the lasso and end up at a site located on the initial loop. e) The "figure eight". We encounter this motif if we traverse the dangling branch of the lasso and end up at the same starting point i. f) The "dumbbell". We encounter this motif if we traverse the dangling branch of the lasso and pass through the same point twice (located outside of the initial loop).
the nature of scaling near the phase boundary. One basic question concerns the scaling of the probability P SAT that a random instance is SAT. Work on the classical problem by Bollobás et al. [20] showed that this has the scaling form P SAT (N, α) = f ((α − α c )/N 1/3 ). Work on the ER ensemble by Bollobás [23] and Luczak [24] implies that the same scaling holds for the purely quantum problem. Qualitatively, our work makes sense of this apparent coincidence and implies that this scaling will hold everywhere along the phase boundary-that everywhere there exists a single transition involving the proliferation of unsnippable loops with the mix of projectors along such loops changing continuously with β. However, more work is required to show this rigorously and to try and extract more detailed information on the scaling functions near the transition. Finally, we intend to examine similar ensembles for k = 3. The current work suggests that perturbing about the classical limit by introducing a dilute set of quantum projectors into the Hamiltonian could be informative in quantum mechanical perturbation theory.