next up previous
Next: Motivation Up: Quantum Search Methods Previous: Example: A One-Bit

Some Approaches to Search

A device consisting of n quantum bits allows for operations on superpositions of tex2html_wrap2644 classical states. This ability to operate simultaneously on an exponentially large number of states with just a linear number of bits is the basis for quantum parallelism. In particular, repeating the operation of Eq. 7 n times, each on a different bit, gives a superposition with equal amplitudes in tex2html_wrap2644 states.

At first sight quantum computers would seem to be ideal for combinatorial search problems that are in the class NP. In such problems, there is an efficient procedure tex2html_wrap2646 that takes a potential solution set s and determines whether s is in fact a solution, but there are exponentially many potential solutions, very few of which are in fact solutions. If tex2html_wrap2647 are the potential sets to consider, we can quickly form the superposition tex2html_wrap2648 and then simultaneously evaluate tex2html_wrap2646 for all these states, resulting in a superposition of the sets and their evaluation, i.e., tex2html_wrap2650 . Here tex2html_wrap2651 represents a classical search state considering the set tex2html_wrap2652 along with a variable soln whose value is true or false according to the result of evaluating the consistency of the set with respect to the problem requirements. At this point the quantum computer has, in a sense, evaluated all possible sets and determined which are solutions. Unfortunately, if we make a measurement of the system, we get each set with equal probability tex2html_wrap2653 and so are very unlikely to observe a solution. This is thus no better than the slow classical search method of random generate-and-test where sets are randomly constructed and tested until a solution is found. Alternatively, we can obtain a solution with high probability by repeating this operation tex2html_wrap2654 times, either serially (taking a long time) or with multiple copies of the device (requiring a large amount of hardware or energy if, say, the computation is done by using multiple photons). This shows a trade-off between time and energy (or other physical resources), conjectured to apply more generally to solving these search problems [6], and also seen in the trade-off of time and number of processors in parallel computers.

To be useful for combinatorial search, we can't just evaluate the various sets but instead must arrange for amplitude to be concentrated into the solution sets so as to greatly increase the probability a solution will be observed. Ideally this would be done with a mapping that gives constructive interference of amplitude in solutions and destructive interference in nonsolutions. Designing such maps is complicated by the fact that they must be linear unitary operators as described above. Beyond this physical restriction, there is an algorithmic or computational requirement: the mapping should be efficiently computable [15]. For example, the map cannot require a priori knowledge of the solutions (otherwise constructing the map would require first doing the search). This computational requirement is analogous to the restriction on search heuristics: to be useful, the heuristic itself must not take a long time to compute. These requirements on the mapping trade off against each other. Ideally one would like to find a way to satisfy them all so the map can be computed in polynomial time and give, at worst, polynomially small probability to get a solution if the problem is soluble. One approach is to arrange for constructive interference in solutions while nonsolutions receive random contributions to their amplitude. While such random contributions are not as effective as a complete destructive interference, they are easier to construct and form the basis for a recent factoring algorithm [48] as well as the method presented here.

Classical search algorithms can suggest ways to combine the use of superpositions with interference. These include local repair styles of search where complete assignments are modified, and backtracking search, where solutions are built up incrementally. Using superpositions, many possibilities could be simultaneously considered. However these search methods have no a priori specification of the number of steps required to reach a solution so it is unclear how to determine when enough amplitude might be concentrated into solution states to make a measurement worthwhile. Since the measurement process destroys the superposition, it is not possible to resume the computation at the point where the measurement was made if it does not produce a solution. A more subtle problem arises because different search choices lead to solutions in differing numbers of steps. Thus one would also need to maintain any amplitude already in solution states while the search continues. This is difficult due to the requirement for reversible computations.

While it may be fruitful to investigate these approaches further, the quantum method proposed below is based instead on a breadth-first search that incrementally builds up all solutions. Classically, such methods maintain a list of goods of a given size. At each step, the list is updated to include all goods with one additional variable. Thus at step i, the list consists of sets of size i which are used to create the new list of sets of size tex2html_wrap2655 . For a CSP with n variables, i ranges from 0 to tex2html_wrap2656 , and after completing these n steps the list will contain all solutions to the problem. Classically, this is not a useful method for finding a single solution because the list of partial assignments grows exponentially with the number of steps taken. A quantum computer, on the other hand, can handle such lists readily as superpositions. In the method described below, the superposition at step i consists of all sets of size i, not just consistent ones, i.e., the sets at level i in the lattice. There is no question of when to make the final measurement because the computation requires exactly n steps. Moreover, there is an opportunity to use interference to concentrate amplitude toward goods. This is done by changing the phase of amplitudes corresponding to nogoods encountered while moving through the lattice.

As with the division of search methods into a general strategy (e.g., backtrack) and problem specific choices, the quantum mapping described below has a general matrix that corresponds to exploring all possible changes to the partial sets, and a separate, particularly simple, matrix that incorporates information on the problem specific constraints. More complex maps are certainly possible, but this simple decomposition is easier to design and describe. With this decomposition, the difficult part of the quantum mapping is independent of the details of the constraints in a particular problem. This suggests the possibility of implementing a special purpose quantum device to perform the general mapping. The constraints of a specific problem are used only to adjust phases as described below, a comparatively simple operation.

For constraint satisfaction problems, a simple alternative representation to the full lattice structure is to use partial assignments only, i.e., sets of variable-value pairs that have no variable more than once. At first sight this might seem better in that it removes from consideration the necessary nogoods and hence increases the proportion of complete sets that are solutions. However, in this case the number of sets as a function of level in the lattice decreases before reaching the solution level, precluding the simple form of a unitary mapping described below for the quantum search algorithm. Another representation that avoids this problem is to consider assignments in only a single order for the variables (selected randomly or through the use of heuristics). This version of the set lattice has been previously used in theoretical analyses of phase transitions in search [53]. This may be useful to explore further for the quantum search, but is unlikely to be as effective. This is because in a fixed ordering some sets will become nogood only at the last few steps, resulting is less opportunity for interference based on nogoods to focus on solutions.

next up previous
Next: Motivation Up: Quantum Search Methods Previous: Example: A One-Bit

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