Quantum Search: A Small Example

This plot is a small 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 simple constraint satisfaction problem shown here has two variables (x and y), each of which can take on two values (0 and 1). There are two constraints: x is not equal to 1, and y is not equal to 1.

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 four assumptions and so has 16 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 6 sets of size two). Within each size, the sets are sorted by the number of constraints they violate (i.e., sets of a given size with the fewest violations are on the left, those with the most are on the right). The single solution to this problem is the set {x=0,y=0}, shown as the first set of size 2 in the plot. The paper gives a complete description of this representation of search states.

Somewhat larger examples are also available:

The size of the search space grows exponentially with the size of the problem. Thus the examples shown here are limited to small problems that can also be readily solved with classical search methods and unstructured quantum search.