To examine the typical behavior of this quantum search algorithm with respect to problem structure, we need a suitable class of problems. This is particularly important for average case analyses since one could inadvertently select a class of search problems dominated by easy cases. Fortunately the observed concentration of hard cases near phase transitions provides a method to generate hard test cases.
The phase transition behavior has been seen in a variety of search problem classes. Here we select a particularly simple class of problems by supposing the constraints specify nogoods randomly at level 2 in the lattice. This corresponds to binary constraint satisfaction problems [44, 50], but ignores the detailed structure of the nogoods imposed by the requirement that variables have a unique assignment. By ignoring this additional structure, we are able to test a wider range of the number of specified nogoods for the problems than would be the case by considering only constraint satisfaction problems. This lack of additional structure is also likely to make the asymptotic behavior more readily apparent at the small problem sizes that are feasible with a classical simulation.
Furthermore, since the quantum search algorithm is appropriate only for soluble problems, we restrict attention to random problems with a solution. These could be obtained by randomly generating problems and rejecting any that have no solution (as determined using a complete classical search method). However, for overconstrained problems the soluble ones become quite rare and difficult to find by this method. Instead, we generate problems with a prespecified solution. That is, when randomly selecting nogoods to add to a problem, we do not pick any nogoods that are subsets of a prespecified solution set. This always produces problems with at least one solution. Although these problems tend to be a bit easier than randomly selected soluble problems, they nevertheless exhibit the same concentration of hard problems and at about the same location as general random problems [7, 53]. The quantum search is started at level 2 in the lattice.