Next: 4.2 The Algorithm for Up: 4 Solving 1-SAT Previous: 4 Solving 1-SAT

4.1 Motivation

Solving a search problem with a quantum computer requires finding a unitary operator L that transforms an easily constructed initial state vector to a new state with large amplitude in those components of the state vector corresponding to solutions. Furthermore, determining this operator and evaluating it with the quantum computer must be tractable operations. This restriction means that any information used for a particular assignment must itself be easily computed, and the algorithm only uses readily computable unitary operations.

To design a single-step quantum algorithm, we consider superpositions of all assignments for the problem. Since we have no a priori knowledge of the solution, an unbiased initial state vector is one with equal amplitude in each assignment: .

We must then incorporate information about the particular problem to be solved into this state vector. As in previous algorithms [27, 29, 30], we do this by adjusting the phases in parallel, based on a readily computed property of each assignment: its number of conflicts with the constraints of the problem. This amounts to multiplication by a diagonal matrix R, with the entries on the diagonal having unit magnitude so that R is unitary. The resulting amplitude for assignment s is then of the form where and depends only on the number of conflicts in s. While this operation adds problem specific information to the state vector, in itself it does not solve the problem: at this point a measurement would return assignment s with probability , the same as random selection.

This operation also illustrates how the unitarity requirement, , prevents us from using a computationally more desirable selection, i.e., if s is not a solution, and nonzero otherwise. Such a choice, if possible, would immediately give a state vector with all amplitude in the solution. While determining whether a given assignment is a solution can be done rapidly for any NP problem, that information can not be directly used to set amplitudes of the nonsolutions to zero. Thus, while quantum parallelism allows rapid testing of all assignments, the restriction to unitary operators severely limits the use that can be made of this information.

For a single-step search algorithm, the remaining operations must not require any additional evaluation of the problem constraints, i.e., these operations will be the same for all problems of a given size. One the other hand, this restriction has the advantage of allowing more general unitary matrices than just phase adjustments. Specifically, this allows operations that mix the various components of the state vector. We need to identify a mixing operator U that makes all contributions to the solution add together in phase, but with U independent of the particular problem.

The final result of the algorithm is . Suppose t is the solution. The maximum possible contribution to will be when all values in the sum combine in-phase. This will be the case if where is the complex conjugate of . In this case, which is just equal to 1. However, the mixing matrix itself is to be independent of any particular problem. Thus the issue is whether it is possible to create a U whose values will have the required phases no matter where the solution is. One approach is to note that the mixing should have no bias as to the amount of amplitude that will need to be moved from one assignment to another in the state vector. This means that the magnitude of each element in U will be the same, i.e., . For the phase of each element, we can consider using the feature of assignments used in classical local searches, namely the neighbors of each assignment. This suggests having depend only on the Hamming distance between r and s, i.e., where .

With the elements of U depending only on the Hamming distance, the matrix is independent of any particular problem's constraints. The question is then whether some feasible choices of and allow for the solution t. This will be the case provided , where depends only on the number of conflicts c in assignment s. This relation does not hold for all search problems. However, for the maximally constrained 1-SAT considered here, the Hamming distance of assignment s from the solution, d(t,s), which is the number of bad values in s, is precisely equal to the number of conflicts in s. Thus, to ensure all amplitude is combined into the solution, we merely need to have .

The final question is what choices for the values are consistent with U being a unitary matrix. This requirement restricts the available choices, e.g., having all results in the nonunitary matrix with all elements equal to .

To examine the possible choices, consider the smallest possible case, n=1. One maximally constrained, but still solvable, problem has the single clause NOT and solution . The two assignments, 0 and 1, have, respectively, 0 and 1 conflicts. Since overall phase factors are irrelevant, we can select leaving a single remaining choice for . For the matrix U, we have pairs of assignments with Hamming distance 0 and 1. Requiring then gives

The unitarity condition, , then requires that be purely imaginary, i.e., . We arbitrarily pick . Starting from the initial state with equal amplitude in both assignments we then have the results of applying R followed by U:

giving all the amplitude in the solution. The overall operation L=UR is

It is important to note that the same operations also work if, instead, the other assignment is the solution, i.e., the problem has the clause and solution . In this case, the assignments 0 and 1 now have, respectively, 1 and 0 conflicts so the phase adjustment is now applied to assignment 0. The operation then gives

Again, all amplitude is in the single solution, and the overall operation is

While the overall operation L depends on the location of the solution, for these problems it can be implemented by composing operators U and R that do not require knowledge of the solution. Instead, as described more generally in §4.5, R is implemented by using the classical function for evaluating the number of conflicts in a given assignment, but applied to a superposition of all assignments.

With these motivating arguments for the form of the operations, examining a few larger values of n establishes the simple pattern of phases used in the algorithm described in the remainder of this section.

Next: 4.2 The Algorithm for Up: 4 Solving 1-SAT Previous: 4 Solving 1-SAT