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.
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.
The available algorithms include
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.
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.
The display tabs select the type of information to show about the algorithm behavior:
The bottom of the display shows how much the normalization of the amplitudes differs from one (as an indication of numerical precision), the probability in all solution states and, if appropriate, the expected value of the selected property.
A popup menu adjusts the plot, e.g., showing normalized amplitudes instead of relative to the plot area, and including a global phase factor for the amplitudes to keep the amplitude of the first solution state along the positive real axis (this solution's amplitude is shown in gray instead of black).
A popup menu toggles the plot x-axis between the actual number of steps and the fraction relative to the maximum taken for each algorithm.
The values correspond to the behavior that would be seen if the algorithm were terminated at the corresponding number of steps by observing the state of the quantum computation. The available behaviors are:
The available state properties are:
The values somewhat arbitrarily group states based on whether local search will, may, or won't lead to a solution:
|The image schematically shows the main types for a one-dimensional search problem. The plateau types, 2, 4, 6, 8, are analogous to types 1, 3, 5, 7, respectively. These groups do not take into account the difficulty of local search on plateaus (where neighbor costs give no guide, so the difficulty depends on the number of states in a plateau).|