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.

• On the top of the plot, the black bar shows the time, measured in units of the algorithm's steps, and the gray bar shows the total probability in the solution state.
• Initially, all of the probability is in the single set of size 0.
• After five steps, the solution state (shown as the gray point) has a significantly enhanced probability.

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:

• A weakly constrained problem with several solutions.
• A tightly constrained problem with one solution.

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.