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, respectively, and they are believed to be intractable for both classical and quantum computers. 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 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.

Figure 1

The phase boundary in the $\alpha \text{−}\beta$ plane that separates the SAT and the UNSAT regimes for the mixed classical-quantum problem. The dashed line indicates the emergence of a giant component in the ER graph (the percolation phase transition). $\beta =0$ corresponds to the 2-SAT problem and $\beta =1$ corresponds to the 2-QSAT problem.

Figure 2

(a) An unsnippable loop that contains both classical and quantum edges. (b) A loop with two cross-links. If all the strings are unsnippable and the cross-links penalize the loop's two linearly independent satisfying states, this motif becomes UNSAT. (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).