next up previous
Next: The Problem-Independent Mapping Up: Quantum Search Methods Previous: Motivation

A Search Algorithm

The general idea of the mapping introduced here is to move as much amplitude as possible to supersets (just as in classical breadth-first search, increments to partial sets give supersets). This is combined with a problem specific adjustment of phases based on testing partial states for consistency (this corresponds to a diagonal matrix and thus is particularly simple in that it does not require any mixing of the amplitudes of different states). The specific methods used are described in this section.

Tad Hogg
Wed Mar 20 16:29:17 PST 1996