In this section, the behavior of the quantum algorithm is evaluated for two classes of combinatorial search problems. The first class, of unstructured problems, is used to examine the phase transition in a particularly simple context using both random and inverted phases for nogoods. The second class, random propositional satisfiability (SAT), evaluates the robustness of the algorithm for problems with particular structure.
For classical simulation of this algorithm we explicitly compute the amplitude of all sets in the lattice up to the solution level and the mapping between levels. Unfortunately, this results in an exponential slowdown compared to the quantum implementation and severely limits the feasible size of these classical simulations. Moreover, determining the expected behavior of the random phase method requires repeating the search a number of times on each problem (10 tries in the experiments reported here). This further limits the feasible problem size.
As a simple check on the numerical errors of the calculation, we recorded the total normalization in all sets at the solution level. With double precision calculations on a Sun Sparc10, for the experiments reported here typically the norm was 1 to within a few times . As an indication of the execution time with unoptimized C++ code, a single trial for a problem with and 16, with , required about 70 and 1000 seconds, respectively. This uses a direct evaluation of the map from one level to the next as given by Eq. 21. A substantial reduction in compute time is possible by exploiting the simple structure of this mapping to give a recursive evaluation. Some additional improvement is possible by exploiting the fact that all amplitudes are real when using the method that inverts phases of nogoods. This reduced the execution time to about 1 and 6 seconds per trial for N of 14 and 16, respectively.