Quantum Search Demo: Instructions


First select one of the available problem instances and algorithms (or use the default initial selections). Then perform one or more steps. The various displays show different aspects of the algorithm's behavior, and allow comparing different algorithms on a single instance.

screen image of demo applet

select problem instance

These search problems involve n Boolean variables, so an assignment to all variables corresponds to a string of n bits. Such problems have 2n assignments, or search states. A problem instance is defined by associating a cost with each state; solutions are those states with zero cost. The distance between two states is the number of variables they assign different values, and equals the Hamming distance between the corresponding bit strings.

The available problem instances include examples of the NP-complete satisfiability problem. Specifically instances of 3-SAT problems with m clauses. The examples include both relatively easy and hard instances, and instances with various numbers of solutions. The descriptions of these instances are read from data files located on the web server. If the files are not available, e.g., because the server is down, attempting to create the instance gives an error message.

The "Hamming" instances are problems with high symmetry, illustrating the extremes of very easy and very hard cases. For the easy case, the cost of each state is just the number of 1-bits it contains. In the hard case, the cost is one more than the number of 1-bits, except that the state with all 1's is given cost 0.

select algorithm

Selecting an algorithm requires picking one from the list of available options and, optionally, setting a value for the parameter j. These choices are described below.

The available algorithms include

For small problems, the unstructured search is quite effective. However, for larger sizes, the other techniques perform better. For further discussion on these algorithm choices and performance comparison on many more instances, see T. Hogg, Adiabatic Quantum Computing for Random Satisfiability Problems.

Quantum search involves superpositions of all search states, specified by a vector associating a complex number (called an amplitude) with each state. Algorithms change this vector through a series of steps, each corresponding to multiplication by a unitary matrix.

Most of the algorithms use a different matrix for each step. These matrices are defined in terms of an initial and final matrix, and the number of steps required to change between these forms. This number, denoted as j, is specified in the text field next to the algorithm selection. Different values of j produce different matrices for the steps, and hence different algorithms.

Generally the matrix choices are meant for an algorithm that will be run for j steps. The simulation allows the algorithm to run for any number of steps, not necessarily equal to j. This can illustrate the possible benefit of stopping the algorithm early (e.g., to minimize expected search cost over repeated trials rather than maximizing the probability to find a solution with a single trial of the algorithm).

The algorithms used here are not optimal for these instances. For any particular instance, it is possible to design an algorithm that can solve it in just one step. However, in practice, there will not be sufficient prior knowledge about the instance to make this computationally feasible.

run algorithm

Press the "step" button to run the algorithm.

By default, each press performs one step. To perform multiple steps, enter the number of steps in the field below the "step" button before pressing it.

While running multiple steps, the "step" button changes to "STOP": another press stops the evaluation. For larger problems, displaying the amplitudes for all states can be slow, in which case it may take a while to stop. The other display choices update more rapidly.

The "back" button reverses the algorithm by one step.

behavior displays

The display tabs select the type of information to show about the algorithm behavior:

The available state properties are:

Tad Hogg