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.