Quantum Search Demo: Examples

Examples of quantum search demo.

Examples for a 3-SAT problem instance with 8 variables.

Each of the 256 possible assignments has an associated cost equal to the number of clauses conflicting with the state.

applet screen image: probability to find solution Probability of finding a solution vs. number of algorithm steps.

Black: unstructured search (i.e., Grover's algorithm).

Red: one of the heuristic methods.

In this case, unstructured search gives lower cost, but the heuristic (and adiabatic) methods perform better for larger problems. The adiabatic method requires many more steps to give solution probabilities close to one (not shown).

applet screen image: amplitudes for heuristic method Amplitudes for one of the heuristic methods. The amplitudes of states with different costs (represented by different colors) tend to cluster, with phases increasing clockwise as the costs increase.

Amplitudes for a discrete version of the adiabatic method. The system remains close to the ground state during the steps of the algorithm. One consequence is all amplitudes have nearly the same phase, shown here by the clustering of the amplitudes near the positive real axis. This clustering becomes more pronounced with a larger number of steps: the adiabatic limit corresponds to an increasing number of steps. Note the much larger number of steps for this example than used for the unstructured and heuristic methods.

Tad Hogg

	Probability of finding a solution vs. number of algorithm steps. Black: unstructured search (i.e., Grover's algorithm). Red: one of the heuristic methods. In this case, unstructured search gives lower cost, but the heuristic (and adiabatic) methods perform better for larger problems. The adiabatic method requires many more steps to give solution probabilities close to one (not shown).
	Amplitudes for one of the heuristic methods. The amplitudes of states with different costs (represented by different colors) tend to cluster, with phases increasing clockwise as the costs increase.
	Amplitudes for a discrete version of the adiabatic method. The system remains close to the ground state during the steps of the algorithm. One consequence is all amplitudes have nearly the same phase, shown here by the clustering of the amplitudes near the positive real axis. This clustering becomes more pronounced with a larger number of steps: the adiabatic limit corresponds to an increasing number of steps. Note the much larger number of steps for this example than used for the unstructured and heuristic methods.