next up previous
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 tex2html_wrap_inline1638 is one with equal amplitude in each assignment: tex2html_wrap_inline1954 .

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 tex2html_wrap_inline1962 where tex2html_wrap_inline1964 and tex2html_wrap_inline1966 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 tex2html_wrap_inline1972 , the same as random selection.

This operation also illustrates how the unitarity requirement, tex2html_wrap_inline1964 , prevents us from using a computationally more desirable selection, i.e., tex2html_wrap_inline1976 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 tex2html_wrap_inline1984 . Suppose t is the solution. The maximum possible contribution to tex2html_wrap_inline1988 will be when all values in the sum combine in-phase. This will be the case if tex2html_wrap_inline1990 where tex2html_wrap_inline1992 is the complex conjugate of tex2html_wrap_inline1994 . In this case, tex2html_wrap_inline1996 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., tex2html_wrap_inline2002 . 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 tex2html_wrap_inline2004 depend only on the Hamming distance between r and s, i.e., tex2html_wrap_inline2010 where tex2html_wrap_inline2012 .

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 tex2html_wrap_inline1966 and tex2html_wrap_inline2018 allow tex2html_wrap_inline2020 for the solution t. This will be the case provided tex2html_wrap_inline2024 , where tex2html_wrap_inline2026 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 tex2html_wrap_inline2040 .

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

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


The unitarity condition, tex2html_wrap_inline1648 , then requires that tex2html_wrap_inline2058 be purely imaginary, i.e., tex2html_wrap_inline2068 . We arbitrarily pick tex2html_wrap_inline2070 . 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 tex2html_wrap_inline1708 and solution tex2html_wrap_inline2082 . In this case, the assignments 0 and 1 now have, respectively, 1 and 0 conflicts so the tex2html_wrap_inline2070 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 up previous
Next: 4.2 The Algorithm for Up: 4 Solving 1-SAT Previous: 4 Solving 1-SAT

Tad Hogg
Feb. 1999