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.