Quantum Search: Weakly Constrained

This plot is an example of the quantum search algorithm described in Tad Hogg, A Framework for Structured Quantum Search, 1997:

This plot shows the evolution of the probability associated with each state in the search space over a time interval equal to 5 steps of the algorithm. The probabilities are shown on a logarithmic scale, which does not show the many states whose probabilities are below 0.001.

The simple constraint satisfaction problem shown here has six variables, each of which can take on two values (0 and 1). There are 6 binary constraints and 14 solutions.

The search states for this problem consist of all possible sets of assumptions, each of which consists of a single variable assigned to a single value. This problem has 12 assumptions and so has 4096 search states. In the plot, these sets are shown grouped by size as indicated by the label on the horizontal axis (e.g., there are 66 sets of size two). Although there are different numbers of sets of different sizes, in the plot sets of each size are given an equal portion of the plot. Within each size, the sets are sorted by the number of constraints they violate. This ordering shows that after 5 steps, the algorithm tends to concentrate probability among states with at most a few constraint violations.

The solutions to this problem are shown as the first sets of size 6 in the plot. The paper gives a complete description of this representation of search states.

Other examples are also available: