Computation is ultimately a physical process [33]. That is, in practice the range of physically realizable devices determines what is computable and the resources, such as computer time, required to solve a given problem. Computing machines can exploit a variety of physical processes and structures to provide distinct trade-offs in resource requirements. An example is the development of parallel computers with their trade-off of overall computation time against the number of processors employed. Effective use of this trade-off can require algorithms that would be very inefficient if implemented serially.
Another example is given by hypothetical quantum computers [14]. They offer the potential of exploiting quantum parallelism to trade computation time against the use of coherent interference among very many different computational paths. However, restrictions on physically realizable operations make this trade-off difficult to exploit for search problems, resulting in algorithms essentially equivalent to the inefficient method of generate-and-test. Fortunately, recent work on factoring [48] shows that better algorithms are possible. Here we continue this line of work by introducing a new quantum algorithm for some particularly difficult combinatorial search problems. While this algorithm represents a substantial improvement for quantum computers, it is particularly inefficient as a classical search method, both in memory and time requirements.
When evaluating algorithms, computational complexity theory usually focuses on the scaling behavior in the worst case. Of particular theoretical concern is whether the search cost grows exponentially or polynomially. However, in many practical situations, typical or average behavior is of more interest. This is especially true because many instances of search problems are much easier to solve than is suggested by worst case analyses. In fact, recent studies have revealed an important regularity in the class of search problems. Specifically, for a wide variety of search methods, the hard instances are not only rare but also concentrated near abrupt transitions in problem behavior analogous to physical phase transitions [27]. To exhibit this concentration of hard instances a search algorithm must exploit the problem constraints to prune unproductive search choices. Unfortunately, this is not easy to do within the range of allowable quantum computational operations. It is thus of interest to see if these results generalize to quantum search methods as well.
In this paper, the new algorithm is evaluated empirically to determine its average behavior. The algorithm is also shown to exhibit the phase transition, indicating it is indeed managing to, in effect, prune unproductive search. This leaves for future work the analysis of its worst case performance.
This paper is organized as follows. First we discuss combinatorial search problems and the phase transitions where hard problem instances are concentrated. Second, after a brief summary of quantum computing, the new quantum search algorithm is motivated and described. In fact, there are a number of natural variants of the general algorithm. Two of these are evaluated empirically to exhibit the generality of the phase transition and their performance. Finally, some important caveats for the implementation of quantum computers and open issues are presented.