The behavior of the algorithm as a function of the ratio of clauses to variables is shown in Fig. 11 using the phase inversion method. This shows the phase transition behavior. Comparing to Fig. 5, this also shows the class of random 3SAT problems is harder, on average, for the quantum algorithm than the class of unstructured problems.
Figure 11: Average number of tries to find a solution with the quantum search algorithm for random 3SAT as a function of c/n, using the phase inversion method. The curves correspond to n=5 (black) and n=10 (gray).