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.

Feb. 1999