\documentstyle[jair,twoside,11pt,theapa]{article}
\usepackage{epsfig}

% some useful definitions
 %======================== CROSS-REFERENCING ==================
 \newcommand{\app}[1]{Appendix~\ref{sect.#1}}
 \newcommand{\sect}[1]{Section~\ref{sect.#1}}      % Ref. to section or subsection
                                        %   to appear as, say, $2.37
 \newcommand{\baresect}[1]{\ref{sect.#1}}      % Ref. to one more section or
                                 %    subsection to appear as, say, 2.37
 \newcommand{\eq}[1]{Eq.~(\ref{eq.#1})}	% Ref. to equation
 \newcommand{\bareeq}[1]{(\ref{eq.#1})}	% Ref. to equation
 \newcommand{\fig}[1]{Figure~\ref{fig.#1}}

 \newcommand{\sectlabel}[1]{\label{sect.#1}}
 \newcommand{\eqlabel}[1]{\label{eq.#1}}



%======================== FIGURES ========================

\newcommand{\figdef}[3]{% label, body, caption
\begin{figure}[!htb]
 \centering\leavevmode#2%
 \caption{#3}
 \label{fig.#1}
\end{figure}                 }


%======================== COMMON EXPRESSIONS ========================

% number of 1-bits in an assignment; inner braces required e.g. for a^\ones{x y}
\newcommand{\ones}[1]{{| #1 |}}

% bitwise and operation
\newcommand{\bitA}{\wedge}

% W matrix with hat: unnormalized version of the matrix
\newcommand{\W}{\hat{W}}

% floor
\newcommand{\floor}[1]{ { \left \lfloor #1 \right \rfloor } }

% conditional probabilities
\newcommand{\Pconf}{ {P_{\rm conf}} }
\newcommand{\Pbad}{ {P_{\rm bad}} }

% state vectors
\newcommand{\stateVec}[2]{ \pmatrix{ #1 \cr #2 \cr } }
\newcommand{\stateVecV}[2]{ \pmatrix{ #1 \cr \vdots \cr #2 \cr } }
\newcommand{\stateVecB}[4]{ \pmatrix{ #1 \cr #2 \cr #3 \cr #4 \cr } }

% ket
\newcommand{\ket}[1]{ { \left| #1 \right> }}

% effective number of conflicts
\newcommand{\cEff}{ {c_{\rm eff}} }



\jairheading{10}{1999}{39-66}{9/98}{2/99}
\ShortHeadings{Solving Highly Constrained Search Problems with Quantum Computers}
{Hogg}
\firstpageno{39}


\begin{document}
\title{Solving Highly Constrained Search Problems\\ with Quantum Computers}

\author{\name Tad Hogg \email hogg@parc.xerox.com \\
       \addr Xerox Palo Alto Research Center\\
       3333 Coyote Hill Road
       Palo Alto, CA  94304 USA
}

\maketitle

\begin{abstract}
  A previously developed quantum search algorithm for solving 1-SAT
  problems in a single step is generalized to apply to a range of
  highly constrained $k$-SAT problems. We identify a bound on the
  number of clauses in satisfiability problems for which the
  generalized algorithm can find a solution in a constant number of
  steps as the number of variables increases. This performance
  contrasts with the linear growth in the number of steps required
  by the best classical algorithms, and the exponential number
  required by classical and quantum methods that ignore the problem
  structure. In some cases, the algorithm can also guarantee that
  insoluble problems in fact have no solutions, unlike previously
  proposed quantum search algorithms.
\end{abstract}


\section{Introduction}

Quantum
computers~\cite{benioff82,bernstein92,deutsch85,deutsch89,divincenzo95,feynman86,lloyd93}
offer a new approach to combinatorial search problems~\cite{garey79}
with {\em quantum parallelism}, i.e., the ability to operate
simultaneously on many classical search states, and {\em interference}
among different paths through the search space. A quantum algorithm to
rapidly factor integers~\cite{shor94}, a problem thought to be
intractable for classical machines, offers a dramatic example of how
these features of quantum mechanics can be exploited.

While several additional algorithms have been
developed~\cite{boyer96,cerny93,grover96,grover97a,hogg95d,hogg97,terhal97},
the extent to which quantum searches can improve on heuristically
guided classical search methods remains an open question.  Quantum
algorithms can be based directly on classical heuristics, achieving a
search cost that is the square root of the corresponding classical
method~\cite{brassard98,cerf98}. Obtaining further improvement
requires uniquely quantum mechanical methods. Heuristics exploit the
structure of the search problems to greatly reduce the search cost in
many cases. The success of these heuristics raises the question of
whether the structure of search problems can form the basis of even
better quantum algorithms. A suggestion that this is possible has been
observed empirically for highly constrained problems~\cite{hogg97},
but the complexity of the algorithm precluded a definitive theoretical
analysis of its behavior.

This paper presents a new quantum search algorithm that is extremely
effective for some highly constrained search problems. These
constraints also allow for effective classical heuristics, i.e., these
problems are relatively easy. However, the new quantum algorithm
requires even fewer steps than the best classical methods, providing
another example of search problems for which quantum computers can
outperform classical ones. More significantly, this algorithm
illustrates how knowledge of the structure inherent in search problems
can be used to develop new algorithms. Finally, because of its
simplicity, the algorithm's behavior can be readily characterized
analytically in some cases, conclusively demonstrating its asymptotic
performance behavior in those cases.

Specifically the following two sections briefly review the ingredients
of quantum programs and the satisfiability problem.  The quantum
algorithm for a particularly simple case is described in \sect{1sat}
and generalized in \sect{app}.  The new algorithm is then evaluated
for a variety of highly constrained problems. Finally some open issues
are discussed, including a variety of ways this approach can be
extended.


\section{Quantum Computers}\sectlabel{quantum}

The state of a classical computer can be described by a string of
bits, each of which is implemented by some two-state device. Quantum
computers use physical devices whose full quantum state can be
controlled. For example~\cite{divincenzo95}, an atom in its ground
state could represent a bit set to 0, and an excited state for 1. The
atom can be switched between these states and also be placed in a
uniquely quantum mechanical {\em superposition} of these values, which
can be denoted as a vector $\stateVec{\psi_0}{\psi_1}$, with a
component (called an {\em amplitude}) for each of the corresponding
classical states for the system. These amplitudes are complex numbers.
A superposition should not be confused with a probabilistic
representation of ignorance about whether a classical bit is really 0
or 1. Nor is a superposition simply in between a 0 or 1, as could be
the case with a 3 volt value for classical bits implemented as 0 and
5 volts. Instead, a superposition has no complete classical analog.

In contrast to a classical machine which, at any given step of its
program, has a definite value for each bit, a quantum machine with $n$
quantum bits exists in a general superposition of the $2^n$ classical
states for $n$ bits, described by the vector
\begin{equation}\eqlabel{stateVector}
\psi = \stateVecV{\psi_0}{\psi_{2^n-1}}
\end{equation}
The amplitudes have a physical interpretation: when the computer's
state is measured, the superposition randomly changes to one of the
classical states with $|\psi_s|^2$ being the probability to obtain the
state $s$. Thus amplitudes satisfy the normalization condition $\sum_s
|\psi_s|^2 = 1$. This measurement operation is used to obtain definite
results from a quantum computation.

Using this rich set of states requires operations that can rapidly
manipulate the amplitudes in a superposition. Because quantum
mechanics is linear and the normalization condition must always be
satisfied, these operations are limited to unitary linear
operators~\cite{hogg95d}. That is, a state vector $\psi$ can only
change to a new vector $\psi^\prime$ related to the original one by a
unitary transformation, i.e., $\psi' = U \psi$ where $U$ is a
unitary matrix\footnote{A complex matrix $U$ is unitary when
$U^\dagger U = I$, where $U^\dagger$ is the transpose of $U$ with all
elements changed to their complex conjugates. Examples include
permutations, rotations and multiplication by phases (complex numbers
whose magnitude is one).} of dimension $2^n \times 2^n$. In
particular, this requires that the operations be reversible: each
output is the result of a single input. In spite of the exponential
size of the matrix, in many cases the operation can be performed in a
time that grows only as a polynomial in $n$ by quantum
computers~\cite{boyer96,hoyer97}. Importantly, the quantum computer
does not explicitly form, or store, the matrix $U$. Rather it performs
a series of elementary operations whose net effect is to produce the
new state vector $\psi'$. On the other hand, the components of the
new vector are not directly accessible: rather they determine the
probabilities of obtaining various results when the state is measured.

Important examples of such operations are reversible classical
programs~\cite{bennett85a,feynman96}. Let $P$ be such a program. Then
for each classical state $s$, i.e., a string of bit values, it
produces an output $s^\prime = P[s]$, and each output is produced by
only a single input. A simple example is a program operating with two
bits that replaces the first value with the exclusive-or of both bits
and leaves the second value unchanged, i.e., $P[00]=00$, $P[01]=11$,
$P[10]=10$ and $P[11]=01$. When used with a quantum superposition,
such classical programs operate independently and simultaneously on
each component to give a new superposition.  That is, a program
operating with $n$ bits gives
\begin{equation}\eqlabel{P}
P \left[
\stateVecV{\psi_0}{\psi_{2^n-1}} \right] \rightarrow
\stateVecV{\psi'_0}{\psi'_{2^n-1}}
\end{equation}
where $\psi_{s^\prime}^\prime =
\psi_s$ with $s^\prime = P[s]$.  This {\em quantum parallelism} allows
a machine with $n$ bits to operate simultaneously with $2^n$ different
classical states.

Unitary operations can also mix the amplitudes in a state vector.  An
example for $n=1$ is
\begin{equation}\eqlabel{Umix}
\frac{1}{\sqrt{2}}
\pmatrix{ 1 & 1 \cr 1 & -1 \cr }
\end{equation}
This converts $\stateVec{1}{0}$, which could correspond to an atom
prepared in its ground state, to $\frac{1}{\sqrt{2}}\stateVec{1}{1}$,
i.e., an equal superposition of the two states.  Since amplitudes are
complex numbers, such mixing can combine amplitudes to leave no
amplitude in some of the states. This capability for
interference~\cite{bernstein92,feynman85} distinguishes quantum
computers from probabilistic classical machines.





\section{The Satisfiability Problem}\sectlabel{sat}

NP search problems have exponentially many possible states and a
procedure that quickly checks whether a given state is a
solution~\cite{garey79}.  Constraint satisfaction problems
(CSPs)~\cite{mackworth92} are an example.  A CSP consists of
$n$ variables, $V_1,\ldots,V_n$, and the requirement to assign a
value to each variable to satisfy given constraints. An
{\em assignment} specifies a value for each
variable.

One important CSP is the satisfiability problem (SAT), which consists
of a logical propositional formula in $n$ variables and the
requirement to find a value (true or false) for each variable that
makes the formula true. This problem has $N=2^n$ assignments. For
$k$-SAT, the formula consists of a conjunction of clauses and each
clause is a disjunction of $k$ variables, any of which may be
negated. For $k \geq 3$ these problems are NP-complete. An example of
such a clause for $k=3$, with the third variable negated, is $V_1$ OR
$V_2$ OR (NOT $V_3$), which is false for exactly one assignment for
these variables: $\{V_1={\rm false}, V_2={\rm false}, V_3={\rm
true}\}$. A clause with $k$ variables is false for exactly one
assignment to those variables, and true for the other $2^k-1$ choices.
Since the formula is a conjunction of clauses, a solution must satisfy
every clause. We say an assignment conflicts with a particular clause
when the values the assignment gives to the variables in the clause
make the clause false.  For example, in a four variable problem, the
assignment $$\{V_1={\rm false}, V_2={\rm false}, V_3={\rm true},
V_4={\rm true}\}$$ conflicts with the $k=3$ clause given above, while
$$\{V_1={\rm false}, V_2={\rm false}, V_3={\rm false}, V_4={\rm
true}\}$$ does not. Thus each clause is a constraint that adds one
conflict to all assignments that conflict with it. The number of
distinct clauses $m$ is then the number of constraints in the problem.

The assignments for SAT can also be viewed as bit strings with the
correspondence that the $i^{th}$ bit is 0 or 1 according to whether
$V_i$ is assigned the value false or true, respectively. In turn,
these bit strings are the binary representation of integers, ranging
from 0 to $2^n-1$.  For definiteness, we arbitrarily order the bits so
that the values of $V_1$ and $V_n$ correspond, respectively, to the
least and most significant bits of the integer. For example, the
assignment $$\{V_1={\rm false}, V_2={\rm false}, V_3={\rm true},
V_4={\rm false}\}$$ corresponds to the integer whose binary
representation is 0100, i.e., the number 4.

For bit strings $r$ and $s$, let $\ones{s}$ be the number of 1-bits in
$s$ and $r \bitA s$ the bitwise AND operation on $r$ and $s$. Thus
$\ones{r \bitA s}$ counts the number of 1-bits both assignments have
in common. We also use $d(r,s)$ as the Hamming distance between $r$
and $s$, i.e., the number of positions at which they have different
values. These quantities are related by
\begin{equation}\eqlabel{hamming}
d(r,s) = \ones{r} + \ones{s} - 2 \ones{r \bitA s}
\end{equation}

An example 1-SAT problem with $n=2$ is the propositional formula (NOT
$V_1$) AND (NOT $V_2$).  This problem has a unique solution: $\{V_1={\rm
false}, V_2={\rm false}\}$, an assignment with the bit representation
00. The remaining assignments for this problem have bit
representations 01, 10, and 11.



\subsection{Highly Constrained SAT Problems}\sectlabel{problems}

In general, SAT problems are difficult to solve. However, in a few
simple cases the very regular structure of the search space allows
much more effective algorithms. One example is given by 1-SAT
problems.  In this case, each clause eliminates one value for a single
variable allowing classical algorithms to examine the variables
independently, giving an overall search cost of $O(n)$ in spite of the
exponentially large number of assignments. A 1-SAT problem has a
solution if and only if each of the $m$ clauses involves a distinct
variable. Otherwise, both values for some variable will be in
conflict, i.e., making a clause false, resulting in no solutions.

This simple structure allows for rapid search. SAT problems with
larger clauses have a more complicated structure. Nevertheless, when
the $k$-SAT problems are highly constrained, their structure is close
to that of 1-SAT. To see this, consider a soluble $k$-SAT problem.
With respect to a particular solution of that problem, define the {\em
good} value for each variable as the value (true or false) it is
assigned in that solution, while the opposite value is the {\em bad}
one for that variable.  For $k$-SAT problems with many constraints,
the {\em number} of bad values in an assignment can usually be
determined rapidly from its number of conflicts, even though
determining exactly {\em which} variables have incorrect assigned
values requires first finding the solution. In such cases, using the
number of bad values results in a tractable algorithm as long as {\it
a priori} knowledge of the solution is not assumed.

For example, consider soluble problems with the largest possible
number of constraints. For $k$-SAT, these maximally constrained
soluble problems have $m=m_{\rm max}$ where
\begin{equation}\eqlabel{mMax}
m_{\rm max} = {n \choose k} (2^k - 1)
\end{equation}
i.e., the  single solution precludes any clause that conflicts with it.

An assignment with $j$ bad values contains $n-j \choose k$ sets of $k$
variables all of which have the same values as the solution. Each of
the remaining sets conflicts with at least one clause in the
problem. Thus each assignment with $j$ bad values has
\begin{equation}\eqlabel{cMax}
c_{\rm max}(j) = {n \choose k} - {n-j \choose k}
\end{equation}
conflicts. This quantity grows strictly monotonically with $j$ for $j
\leq n-k$, so in these cases $j$ is directly determined by the number
of conflicts. Assignments with $n-k+1 \leq j \leq n$ are not
distinguishable.

Assignments with $j=n-k+1$ can also be corrrectly determined by
including neighborhood information. To see this, consider an
assignment $s$ with $j$ bad values, and its $n$ neighbors, i.e.,
assignments at Hamming distance one from $s$. Of these neighbors, $j$
have $j-1$ bad values, and the remaining $n-j$ have $j+1$ bad
values. For $j \leq n-k$, $s$ has $j$ neighbors with fewer conflicts
and $n-j$ with more. Thus for these assignments, examining the number
of conflicts in the neighbors readily determines the value of
$j$. When $j=n-k+1$, the assignment continues to have $j$ neighbors
with fewer conflicts, but now the remaining $k-1$ neighbors have the
same number of conflicts since the additional bad value does not
increase the number of conflicts. Finally, the neighbors of
assignments with $n-k+1 < j \leq n$ all have the same number of
conflicts. Thus examining the number of conflicts in an assignment's
neighbors determines the value of $j$, with the exception that
assignments with $n-k+1 < j \leq n$ are not distinguishable.

The value of $j$ is the number of conflicts that $s$ would have in the
maximally constrained 1-SAT problem with the same solution as the
given maximally constrained $k$-SAT problem. Thus for a maximally
constrained $k$-SAT problem let
\begin{equation}\eqlabel{cEff}
\cEff(s) = \left\{ \begin{array}{cl}
		j	& \mbox{if $j \leq n-k+1$} \\
		n-k+2	& \mbox{otherwise}
		\end{array}
	\right.
\end{equation}
The value of $\cEff(s)$ can be determined rapidly, in much the
same way that a classical local search method checks the number of
conflicts among neighbors of its current state to determine which
assignment to move to next~\cite{minton92,selman92}. Thus $c_{\rm
eff}$ is a computationally tractable approximation to the number of
conflicts each assignment would have in the corresponding 1-SAT
problem. Except for a few assignments with many conflicts, $c_{\rm
eff}$ gives the correct value. Specifically, only assignments with
at least $n-k+3$ bad values are given an incorrect value of $j$ by this
approximation. In particular, the approximation is completely correct
for $k=2$.

While classical searches use the number of conflicts in an assignment
and its neighbors, another possibility for maximally constrained
problems is to use the number of conflicts in the assignment and
its complement (i.e., the assignment with opposite values for all
the variables). If the assignment has $j$ bad values, its complement
will have $n-j$. As described above, the number of conflicts in an
assignment uniquely determines the corresponding value of $j$ provided
$j \le n-k$. On the other hand, the number of conflicts in the
complement assignment uniquely determines $j$ when $n-j \le n-k$, or 
$j \ge k$. Thus, as long as $n>2k$, at least one of these conditions
will be true for all $0 \le j \le n$ and the correct value of $j$
can be determined.




\subsection{Random SAT Problems}\sectlabel{random}


Theoretically, search algorithms are often evaluated for the worst
possible case. However, in practice, search problems are often found
to be considerably easier than suggested by these worst case
analyses~\cite{hogg95e}.  This observation leads to examining the
typical behavior of search algorithms with respect to a specified {\em
ensemble} of problems, i.e., a class of problems and a probability for
each to occur. For instance, the ensemble of random $k$-SAT is
specified by the number of variables $n$, the size of the clauses $k$
and the number of distinct\footnote{This ensemble differs slightly
from other studies where the clauses are not required to be distinct.}
clauses $m$. 

The quantum algorithm presented in this paper is effective for highly
constrained soluble $k$-SAT problems.  When there are many
constraints, soluble problems are very rare among randomly generated
instances. Thus to study the algorithm's behavior we generate random
problems with a prespecified solution.  That is, a random assignment
is selected to be a solution and used to restrict the selection of
clauses for the problem.  In the remainder of this section we describe
two methods for generating such problems, and how they can be related
to corresponding 1-SAT problems.

\subsubsection{Prespecified Solution}
 
The most common use of a prespecified solution is to simply avoid
selecting any clauses that conflict with it. Thus, we generate
problems by randomly selecting a set of $m$ distinct clauses from
among the $m_{\rm max}$, given by \eq{mMax}, available
clauses~\cite{nijenhuis78}.

Consider a given soluble $k$-SAT problem with $m$ clauses, and let
the assignment $r$ be one of its solutions. With respect to the
solution $r$, we can define the bad value for each variable.  For an
assignment with $j$ bad values, the probability it has $c$ conflicts
is
\begin{equation}\eqlabel{Pr(c,j)}
\Pconf(c | j) = \frac{ {c_{\rm max}(j) \choose c} {{m_{\rm max}-c_{\rm max}(j)} \choose {m-c}} }{{m_{\rm max} \choose m}}
\end{equation}
where $c_{\rm max}(j)$, given by \eq{cMax}, is the largest possible
number of conflicts for an assignment with $j$ bad values. The
probability that an assignment has $j$ bad values is
$$
\Pbad(j) = 2^{-n} {n \choose j}
$$ From these expressions and the definition of conditional
probability, the probability that an assignment with $c$ conflicts has
$j$ bad values is
\begin{equation}
\Pbad(j | c) \propto \Pconf(c | j) \Pbad(j)
\end{equation}
Hence, for a given assignment $s$ with $c$ conflicts, we can estimate
the number of bad values it has by picking $j$ that maximizes $\Pbad(j
| c)$. We use this maximum likelihood value for $j$ as $c_{\rm
eff}(s)$ instead of \eq{cEff} for random soluble $k$-SAT problems.
This estimate is readily computed from the number of conflicts.

\subsubsection{Balanced Clauses}

Generating problems with a prespecified solution as described above is
commonly used to study search problems. However, for each variable
there are more allowable clauses where the variable is assigned its
bad value than its good value. This makes highly constrained instances
particularly easy since the good value for each variable can often be
determined from its assigned value that appears most often in the
clauses~\cite{gent96b}.

This bias in clause selection can be removed by a slight change in the
generation method~\cite{vangelder93}. Specifically, instead of only
avoiding those clauses that conflict with the prespecified solution,
i.e., specify zero bad values, we also avoid any clauses that have an
even number of bad values with respect to the prespecified
solution. This selection method means both values for each variable
appear equally often among the clauses.  These balanced problems can
have at most
\begin{equation}\eqlabel{mMaxBalanced}
m_{\rm max}^{\rm bal} = {n \choose k} 2^{k - 1}
\end{equation}
clauses. Furthermore, an assignment with $j$ bad values can have at most
\begin{equation}\eqlabel{cMaxBalanced}
c_{\rm max}^{\rm bal}(j) =  {\sum_i}^\prime { j \choose i } { n-j \choose k-i }
\end{equation}
conflicts, where the sum is over odd values of $i$.  Using these
values in \eq{Pr(c,j)} instead of $m_{\rm max}$ and $c_{\rm max}(j)$
gives the maximum likelihood estimate for $j$ in this ``balanced
clause'' ensemble conditioned on the number of conflicts in the
assignment.




\section{Solving 1-SAT}\sectlabel{1sat}

A quantum computer, operating on superpositions of all assignments for
{\em any} 1-SAT problem, can find a solution in a single search
step~\cite{hogg98}. As a basis for solving highly constrained problems
with larger clause sizes, we focus on maximally constrained 1-SAT
which, from \eq{mMax}, has $m=n$ clauses and allows a simple
specification. Specifically, we first motivate and define the
algorithm for this case and illustrate it with small examples. Then we
show that it is guaranteed to find a solution if one exists, and
finally describe how the algorithm can be efficiently implemented on a
quantum computer. The remainder of the paper then shows how this
algorithm can form the basis for effectively solving highly
constrained $k$-SAT for $k>1$.

\subsection{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 {\it a priori}
knowledge of the solution, an unbiased initial state vector $\psi$ is
one with equal amplitude in each assignment: $\psi_s = 2^{-n/2}$.

We must then incorporate information about the particular problem to
be solved into this state vector. As in previous
algorithms~\cite{grover96,hogg95d,hogg97}, 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 $\rho(s) 2^{-n/2}$ where $|\rho(s)|=1$ and $\rho(s)$ 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 $|\rho(s)|^2 2^{-n} = 2^{-n}$, the same as random
selection.

This operation also illustrates how the unitarity requirement,
$|\rho(s)|=1$, prevents us from using a computationally more desirable
selection, i.e., $\rho(s)=0$ 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 {\em 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 $\phi_r = \sum_s U_{rs} \rho(s)
2^{-n/2}$. Suppose $t$ is the solution. The maximum possible
contribution to $\phi_t$ will be when all values in the sum combine
in-phase. This will be the case if $U_{ts}=\rho^*(s) 2^{-n/2}$ where
$\rho^*$ is the complex conjugate of $\rho$. In this case, $\phi_t =
\sum_s |\rho(s)|^2 2^{-n}$ 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.,
$|U_{rs}|=2^{-n/2}$. 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 $U_{rs}$
depend only on the Hamming distance between $r$ and $s$, i.e., $U_{rs}
= 2^{-n/2} \mu_{d(r,s)}$ where $|\mu_d|=1$.

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 $\rho(s)$ and
$\mu_d$ allow $2^{-n} \sum_s \mu_{d(t,s)} \rho(s) = 1$ for the
solution $t$.  This will be the case provided
$\mu_{d(t,s)}=\rho^*(s)$, where $\rho(s)=\rho_c$ 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 $\mu_d
= \rho_d^*$.

The final question is what choices for the $\mu_d$ values are
consistent with $U$ being a unitary matrix. This requirement restricts
the available choices, e.g., having all $\mu_d=1$ results in the
nonunitary matrix with all elements equal to $2^{-n/2}$. 

To examine the possible choices, consider the smallest possible case,
$n=1$. One maximally constrained, but still solvable, problem has the
single clause NOT $V_1$ and solution $V_1={\rm false}$. The two
assignments, 0 and 1, have, respectively, 0 and 1 conflicts. Since
overall phase factors are irrelevant, we can select $\rho_0=1$ leaving
a single remaining choice for $\rho_1$. For the matrix $U$, we have
pairs of assignments with Hamming distance 0 and 1. Requiring $\mu_d =
\rho_d^*$ then gives
\begin{displaymath}
 U
=\frac{1}{\sqrt{2}} \pmatrix{1 & \rho_1^* \cr \rho_1^* & 1 \cr}
\end{displaymath}
The unitarity condition, $U^\dagger U=I$, then requires that $\rho_1$
be purely imaginary, i.e., $\rho_1 = \pm i$.  We arbitrarily pick
$\rho_1 = i$. Starting from the initial state with
equal amplitude in both assignments we then have the results of
applying $R$ followed by $U$:
\begin{displaymath}
\frac{1}{\sqrt{2}} \stateVec{1}{1}  \rightarrow 
	\frac{1}{\sqrt{2}} \stateVec{1}{i} 
	 \rightarrow  \stateVec{1}{0}
\end{displaymath}
giving all the amplitude in the solution.  The overall operation
$L=UR$ is $$ L = \frac{1}{2} \pmatrix{1 & 1 \cr -i & i \cr} $$

It is important to note that the {\em same} operations also work if,
instead, the other assignment is the solution, i.e., the problem has
the clause $V_1$ and solution $V_1={\rm true}$. In this case, the
assignments 0 and 1 now have, respectively, 1 and 0 conflicts so the
$\rho_1 = i$ phase adjustment is now applied to assignment 0. The
operation then gives
\begin{displaymath}
\frac{1}{\sqrt{2}} \stateVec{1}{1}  \rightarrow 
	\frac{1}{\sqrt{2}} \stateVec{i}{1} 
	 \rightarrow  \stateVec{0}{1}
\end{displaymath}
Again, all amplitude is in the single solution, and the overall
operation is $$ L = \frac{1}{2} \pmatrix{i & -i \cr 1 & 1
\cr} $$ 

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 \sect{implement},
$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.


\subsection{The Algorithm for Maximally Constrained 1-SAT}\sectlabel{algorithm}

Briefly, the algorithm starts with an equal superposition of all the
assignments, adjusts the phases of the amplitudes based on the number
of conflicts in the assignments, and then mixes the amplitudes from
different assignments. This algorithm requires only a single testing
of the assignments, corresponding to a single classical search step.

Specifically, the initial state is $\psi_s=2^{-n/2}$ for each of the $2^n$
assignments $s$, and the final state vector is
\begin{equation}\eqlabel{map}
\phi = U R \psi
\end{equation}
where the matrices $R$ and $U$ are defined as follows.  The matrix $R$
is diagonal with $R_{ss} \equiv \rho(s)$ depending on the number of
conflicts $c$ in the assignment $s$, ranging from 0 to $n$:
\begin{equation}\eqlabel{rho}
\rho(s) = \rho_c = i^c
\end{equation}

The mixing matrix elements $U_{rs}=u_{d(r,s)}$ depend only on the
Hamming distance between the assignments $r$ and $s$, with
\begin{equation}\eqlabel{ud}
u_d = 2^{-n/2} (-i)^d
\end{equation}
and $d$ ranging from 0 to $n$.


\subsection{Examples}

To illustrate the algorithm, consider the example problem in
\sect{sat}. It has $n=m=2$. With the assignments ordered according to the
corresponding interger value, i.e., 00, 01, 10, and 11, $U=A^{(2)}/2$ where
\begin{equation}\eqlabel{A2}
A^{(2)} = \pmatrix{ 1 & -i & -i & -1 \cr -i & 1 & -1 & -i \cr -i & -1
 & 1 & -i \cr -1 & -i & -i & 1 \cr }
\end{equation}
The resulting behavior is:
\begin{center}
\begin{tabular}{l|cccc}
  assignment $s$      & 00  &  01  &  10  &  11 \\ \hline
  number of conflicts & 0   &   1  &   1  &   2 \\
  $\rho(s)$	      & 1     &   $i$ &   $i$ &  $-1$ \\ \hline
  $\psi$              & $1/2$ & $1/2$ & $1/2$ & $1/2$ \\
  $R \psi$            & $1/2$ & $i/2$ & $i/2$ & $-1/2$ \\
  $\phi = U R \psi$   & 1 & 0  &  0 & 0 \\
\end{tabular}
\end{center}
giving an amplitude of 1 in the solution assignment 00.

Another example, with $n=m=3$ is the propositional formula (NOT $V_1$)
AND (NOT $V_2$) AND $V_3$, with assignments $000,001,010,\ldots,110,111$,
represented as bit vectors, and solution $\{V_1={\rm false},
V_2={\rm false}, V_3={\rm true}\}$, i.e., the bit vector 100. In this case
$U$ can be expressed in terms of $A^{(2)}$ from \eq{A2} in block form:
\begin{equation}
U = \frac{1}{\sqrt{8}} \pmatrix{
A^{(2)} & -i A^{(2)} \cr
-i A^{(2)} & A^{(2)} \cr
}
\end{equation}
For this case, the algorithm's behavior is:
\begin{center}
\begin{tabular}{l|cccccccc}
  assignment $s$      & 000  &  001  &  010  &  011 & 100  &  101  &  110  &  111\\ \hline
  number of conflicts & 1   &   2  &   2  &   3  & 0   &   1  &  1  &   2 \\
  $\rho(s)$	      & $i$ & $-1$ & $-1$ & $-i$ & $1$ & $i$  & $i$ & $-1$ \\ \hline
  $\sqrt{8} \psi$     & 1 & 1  &  1 & 1 & 1 & 1  &  1 & 1 \\
  $\sqrt{8} R \psi$   & $i$ & $-1$ & $-1$ & $-i$ & $1$   & $i$  & $i$  &  $-1$ \\
  $\phi = U R \psi$   & 0 & 0  &  0 & 0 & 1 & 0  &  0 & 0 \\
\end{tabular}
\end{center}
Again, all the amplitude is in the solution.


\subsection{Performance of the Algorithm}\sectlabel{derivation}

Consider a maximally constrained soluble 1-SAT problem with $n$
variables.  As described in \sect{sat}, in such a problem each clause
involves a separate variable and there is exactly one solution. To show
that the algorithm works for all $n$, we evaluate \eq{map}.



For each assignment $s$, $(R \psi)_s = \rho(s) 2^{-n/2}$ from
\eq{rho}.  Then for each assignment $r$, $(U R \psi)_r =
2^{-n/2} \sum_s U_{rs} \rho(s)$.   
Each $s$ in this sum can be characterized by
\begin{itemize}
\item $x$: the number of conflicts $s$ shares with $r$
\item $y$: the number of conflicts of $s$ that are not conflicts of $r$
\end{itemize}
Let $h$ be the number of conflicts in the assignment $r$, i.e., the
number of the $n$ variables to which $r$ assigns an incorrect
value. In terms of these quantities, $s$ has $x+y$ conflicts and is at
Hamming distance $d(r,s) = (h-x)+y$ from $r$.  The number of such
assignments is ${h \choose x} {n-h \choose y}$, so the sum can be
written as
\begin{equation}\eqlabel{UR}
(U R \psi)_r = 2^{-n/2} \sum_x {h \choose x} 
	\sum_y {n-h \choose y} 
		u_{h-x+y} \rho_{x+y}
\end{equation}
Substituting the values from \eq{rho} and \bareeq{ud}, gives
\begin{eqnarray}
(U R \psi)_r &=& 2^{-n} \sum_x {h \choose x} 
	\sum_y {n-h \choose y} 
		(-i)^{h-x+y} i^{x+y} \\
%	&=& 2^{-n} (-i)^h \sum_x {h \choose x} i^{2x}
%	\sum_y {n-h \choose y}  \nonumber \\
	&=& 2^{-n} (-i)^h 2^{n-h} \sum_x {h \choose x} (-1)^{x} \nonumber
\end{eqnarray}
This gives $(U R \psi)_r = \delta_{h0}$ where $\delta_{xy}=1$ if $x=y$
and 0 otherwise by use of the identity
\begin{equation}\eqlabel{alternating}
\sum_{x=0}^h (-1)^x {h \choose x} = \delta_{h0}
\end{equation}
Thus, $\phi = U R \psi$ has all its amplitude in the state with no
conflicts, i.e., the unique solution. A measurement made on this final
state is guaranteed to produce a solution.


\subsection{Implementation}\sectlabel{implement}

Conceptually, the operation of \eq{map} can be performed classically
by matrix multiplication. However, since the matrices have $2^n$ rows
and columns, this is not be a practical algorithm. As described in
\sect{quantum}, quantum computers can rapidly perform many matrix
operations of this size. Here we show how this is possible for the
operations used by this algorithm.

For describing the implementation, it is useful to denote the
individual components in a superposition explicitly. Traditionally,
this is done using the ket notation introduced by
Dirac~\citeyear{dirac58}. For instance, the superposition described by the
state vector of \eq{stateVector} is equivalently
written as $\sum_s \psi_s \ket{s}$ where $\ket{s}$ just represents
a unit basis vector corresponding to the assignment $s$. An example of
these alternate, and equivalent, notations is:
\begin{displaymath}
\stateVec{\psi_0}{\psi_1} = \psi_0 \stateVec{1}{0} + \psi_1 \stateVec{0}{1} = \psi_0 \ket{0} + \psi_1 \ket{1}
\end{displaymath}

\subsubsection{Forming the Initial Superposition}

The initialization of $\psi$ can be performed rapidly
by applying the matrix of \eq{Umix} separately to each of the $n$
bits.  For instance, when $n=2$, starting from both bits set to 0,
the state vector is changed as:
\begin{eqnarray*}
\ket{00} & \rightarrow & \frac{1}{\sqrt{2}} \left( 
		\ket{00} + \ket{01} 
		\right) \\
	 & \rightarrow & \frac{1}{2} \left( 
		( \ket{00} + \ket{10}) + ( \ket{01} + \ket{11} )
		\right)
\end{eqnarray*}
Equivalently, in terms of state vectors, this is
$$
\stateVecB{1}{0}{0}{0} \rightarrow \frac{1}{\sqrt{2}} \stateVecB{1}{1}{0}{0} \rightarrow \frac{1}{2} \stateVecB{1}{1}{1}{1}
$$


\subsubsection{Adjusting Phases}

For the operation $R \psi$, note that each value in \eq{rho} has unit
magnitude so $R$ is a unitary diagonal matrix. Furthermore each
$\rho_c$ only requires using the efficient classical procedure $f(s)$
that counts the number of conflicts in an assignment $s$.  We require
a reversible version of this procedure, which can be made with an
additional program register. When the phases to be introduced are just
$\pm 1$, this additional register needs to take on only two values, 0
or 1, corresponding to whether the phase should be 1 or $-1$,
respectively. Thus it can be represented with a single additional
quantum bit, beyond those required to represent the assignment. Such
phases have been used in previous algorithms~\cite{hogg95d,grover96}
and can be implemented through a single evaluation of $f(s)$ by
setting the extra variable to be a superposition of its two
values~\cite{boyer96}.

In the algorithm presented here, \eq{rho} requires phases that are
powers of $i$, which can take on four different values: 1, $i$, $-1$
and $-i$.  The technique used with $\pm 1$ phases can be generalized
to work with these four values, again with a single evaluation of
$f(s)$.  The additional register must consist of two quantum bits, so
it can take on the values 0, 1, 2 or 3. For an assignment $s$ and
register $x$, we use the reversible operation
\begin{displaymath}
F : \ket{s,x} \rightarrow \ket{s, x+c \bmod 4}
\end{displaymath}
where $c=f(s)$ is the number of conflicts in assignment $s$. It then
remains to show how this operation can be used to perform the required
phase adjustments.  Just as we operate with a superposition of all
possible assignments, to implement the phase adjustment, we set
register $x$ to be a particular superposition of its four values:
$\Psi = \frac{1}{2} (\ket{0}-i\ket{1}-\ket{2}+i\ket{3})$. One way to
construct this superposition is to start with both bits of $x$ set to
1, operate on the most significant bit with \eq{Umix} and then operate
on the other bit with $$ \frac{1}{\sqrt{2}} \pmatrix{-i & 1 \cr 1 & -i
\cr} $$ to get
\begin{eqnarray*}
\ket{11} & \rightarrow & \frac{1}{\sqrt{2}} \left( 
		\ket{01} - \ket{11} 
		\right) \\
	 & \rightarrow & \frac{1}{2} \left( 
		( \ket{00} - i\ket{01}) - ( \ket{10} - i \ket{11} )
		\right)
\end{eqnarray*}
This is just the superposition $\Psi$ when we make the correspondence
between the 2-bit vectors $00,\ldots,11$ and the integers
$0,\ldots,3$, respectively.

We start with the equal superposition of amplitudes for the
assignments and this superposition for $x$:
\begin{displaymath}
2^{-n/2} \sum_s \ket{s} \Psi = 2^{-n/2-1} \sum_s
\sum_{x=0}^3 (-i)^x \ket{s,x}
\end{displaymath}
As illustrated with \eq{P}, the operation $F$ acts on each term in
this superposition separately, to produce
\begin{displaymath}
2^{-n/2-1} \sum_{sx} (-i)^x \ket{s,x+c \bmod 4}
\end{displaymath}
where $c$ is the number of conflicts in assignment $s$. Let $y=x+c
\bmod 4$. Then, for a given assignment $s$, as $x$ ranges from 0 to 3,
$y$ also takes on these values, but not necessarily in the same order.
Thus this resulting superposition can also be written as
\begin{displaymath}
2^{-n/2-1} \sum_s \sum_{y=0}^3 (-i)^{y-c} \ket{s,y}
\end{displaymath}
because $(-i)^4=1$. In this form, the sums separate to give finally
\begin{displaymath}
2^{-n/2} \sum_s i^c \ket{s} \sum_{y=0}^3 (-i)^y \ket{y} = 
2^{-n/2} \sum_s i^c \ket{s} \Psi
\end{displaymath}
The net result of applying $F$ using the superposition $\Psi$ for the
additional register is to change the phase of each assignment $s$ by
$i^c$, as required by \eq{rho}. Importantly, the final result
reproduces the original factored form in which the superposition of
assignments is not correlated with the superposition of the
register. This factored form means the register plays no role in the
subsequent mixing operation applied by the matrix $U$ to the
superposition of assignments. Thus this procedure produces the
required phase changes using only one evaluation of $f(s)$, showing
how the phases of a superposition of assignments can be adjusted
without requiring any prior explicit knowledge of the solution.

\subsubsection{The Mixing Matrix}

To implement $U$ specified by \eq{ud} we use two simpler matrices, $W$
and $\Gamma$ defined as follows.  For assignments $r$ and $s$,
\begin{equation}\eqlabel{W}
W_{rs} = 2^{-n/2} (-1)^\ones{r \bitA s}
\end{equation}
is the Walsh transform and $\Gamma$ is a diagonal matrix whose
elements $\Gamma_{rr} \equiv \gamma(r)$ depend only on the number of
1-bits in each assignment, namely,
\begin{equation}\eqlabel{D}
\gamma(r) = \gamma_h \equiv i^h e^{-i \pi n/4}
\end{equation}
where $h=\ones{r}$, ranging from 0 to $n$. The overall phase, $e^{-i
\pi n/4}$, is not essential for the algorithm. It merely serves to
make the final amplitude in the solution be one rather than $e^{i \pi
n/4}$. Whether or not this overall phase is used, the probability to
find a solution is one.

The matrix $W$ is unitary and can be implemented
efficiently~\cite{boyer96,grover96}. For $n=1$, $W$ is just the matrix
of \eq{Umix}. The phases in the matrix $\Gamma$ are powers of $i$ and
so can be computed rapidly using similar procedures to those described
above for the matrix $R$. In this case we use a procedure that counts
the number of 1-bits in each assignment rather than the number of
conflicts.

{% command for product matrix
\newcommand{\U}{ \hat{U} }
\renewcommand{\u}{ \hat{u} }

Finally we show that $U$ can be implemented by the product $W \Gamma W$.
To see this, let $\U \equiv W \Gamma W$. Then
\begin{equation}
\U_{rs} = 2^{-n} \sum_{h=0}^n \gamma_h S_h(r,s)
\end{equation}
where
\begin{equation}
S_h(r,s) = \sum_{t, \ones{t}=h} (-1)^{\ones{r \bitA t} + \ones{s \bitA t}}
\end{equation}
with the sum over all assignments $t$ with $h$ 1-bits.  Each 1-bit of
$t$ contributes 0, 1 or 2 to $\ones{r \bitA t} + \ones{s \bitA t}$
when the corresponding positions of $r$ and $s$ are both 0, have
exactly a single 1-bit, or are both 1, respectively.  Thus
$(-1)^{\ones{r \bitA t} + \ones{s \bitA t}}$ equals $(-1)^z$ where $z$
is the number of 1-bits in $t$ that are in exactly one of $r$ and
$s$. There are $(\ones{r}-\ones{r \bitA s})+(\ones{s}-\ones{r \bitA
s})$ positions from which such bits of $t$ can be selected, and by
\eq{hamming} this is just $d(r,s)$.  Thus the number of assignments
$t$ with $h$ 1-bits and $z$ of these bits in exactly one of $r$ and
$s$ is given by ${d \choose z} {n-d \choose h-z}$ where $d =
d(r,s)$. Thus $S_h(r,s) = S_{hd}^{(n)}$ where
\begin{equation}\eqlabel{Skm}
S_{hd}^{(n)} = \sum_z (-1)^z {d \choose z} {n-d \choose h-z}
\end{equation}
so that $\U_{rs}=\u_{d(r,s)}$ with $\u_d = 2^{-n} \sum_h \gamma_h
S_{hd}^{(n)}$.  Substituting the value of $\gamma_h$ from \eq{D} then
gives
\begin{eqnarray*}
\u_d &=& 2^{-n} e^{-i \pi n/4} \sum_{hz} i^h (-1)^z {d \choose z} {n-d \choose h-z} \\
%  &=& 2^{-n} e^{-i \pi n/4} \sum_{jz} i^{z+j} (-1)^z {d \choose z} {n-d \choose j} \\
%  &=& 2^{-n} e^{-i \pi n/4} \sum_z (-i)^z {d \choose z} \sum_j {n-d \choose j} i^j \\
  &=& 2^{-n} e^{-i \pi n/4} (1-i)^d (1+i)^{n-d}
\end{eqnarray*}
which equals $u_d$ as defined in \eq{ud}. Thus $U = W \Gamma W$,
allowing $U$ to be efficiently implemented. As a final note, except
for a different choice of the $\gamma_h$ phases, this is the same
implementation as used for the mixing matrix defined in an
unstructured quantum search algorithm~\cite{grover96}.


}% command for product matrix


\subsubsection{Required Search Time}

While search algorithm performances are often compared based on the
number of search {\em steps} required, i.e., the number of sequentially
examined assignments, it is also important to compare the number of
more elementary computational operations required. At the most fundamental
level, these operations are logic operators on one or two bits at a time
(e.g., the logical not or exclusive-or operations). As described above,
the matrix operations and forming the initial state can be done with
a series of $O(n)$ bit operations~\cite{boyer96}.

The time required to count the number of conflicts in an assignment
depends on data structures used to represent the problem. A single
evaluation will be comparable for both the quantum and classical
algorithms. For a SAT problem with $m$ clauses, examining each clause
to see if it conflicts with a given assignment uses $O(m)$ tests. Each
of these tests will, in turn, require comparing at least part of the
clause to the assignment. Because the clauses in $k$-SAT are of fixed
size, this gives an overall cost of $O(m)$ to evaluate the number of
conflicts.

For local classical search, the number of conflicts in neighboring
assignments will also be evaluated to determine which assignment
should be examined at the next step of the search. Since neighbors
differ by the value of only one variable, in fact it is only necessary
to examine clauses that involve that variable to determine the
difference in the number of conflicts between an assignment and one of
its neighbors. This evaluation will thus require only $O(m/n)$ tests.
Examining each, or a least a good portion, of the $n$ neighbors
results in a total of $O(m)$ tests to find the next assignment.
Selecting an initial assignment requires a value for each variable,
a cost of $O(n)$.

Thus we can expect both algorithms to involve costs of $O(n+m)$ to
evaluate a single search step. That is, the cost for a {\em single}
search step is about the same for the quantum algorithm and classical
searches when neighbors are examined. However, the quantum algorithm
is able to examine the characteristics of all assignments in
superposition while a classical search examines just one state,
allowing the quantum algorithm to complete in just one step while the
best classical methods for $k$-SAT require $O(n)$ steps.  For the
highly constrained $k$-SAT problems with $k>1$, discussed below, $m
\gg n$ so the dominant cost will be in the evaluation of the number of
conflicts.

This discussion indicates how a comparison of search steps gives a
reasonable comparison in terms of elementary operations as well.
However, a full comparison will also depend on details of actual
implementations, such as any additional operations required for
controlling errors that cannot themselves be performed in parallel
with the higher level steps of the algorithm. These remain significant
issues in the development of quantum
computation~\cite{landauer94a,unruh94,haroche96,monroe96a}, but at
this point seem unlikely to be fundamental
difficulties~\cite{berthiaume94,shor95,knill98}. In particular,
because the algorithm requires only a single step, decoherence is
likely to be less of a difficulty for it than search algorithms that
require multiple repeated steps to move significant amplitude to
solutions~\cite{grover96,hogg97}.

Finally, search algorithms can be compared based on elapsed execution
time. Current hardware
implementations~\cite{barenco95,bouwmeester97,chuang98,cirac95,cory96,gershenfeld96,sleator95} are quite limited in size, so
such a comparison will need to await the construction of quantum
machines with a sufficient number of bits to perform interesting
searches.




\section{Applying the Algorithm to $k$-SAT}\sectlabel{app}

The algorithm presented above is effective for 1-SAT by exploiting the
simple structure of such problems. As described in \sect{sat}, many
highly constrained $k$-SAT problems have a similar structure. This
observation allows the 1-SAT algorithm to be applied to more general
problems, although with a reduction in performance.  Specifically,
applying \eq{rho} requires knowing the number of conflicts the
assignments would have in the corresponding maximally constrained
1-SAT problem whose solution is equal to one of the solutions of the
original $k$-SAT problem. As described in \sect{problems}, for the
most part this can be computed efficiently using the neighborhood
relations for the problem. This suggests simply changing the 1-SAT
algorithm to use $\rho(s) = \rho_{\cEff(s)}$.

To see how this approximation changes the performance, consider an
assignment $s$ with $y$ bad values with respect to a specific solution
$r$ and let
\begin{equation}
\delta(s) = \rho_{\cEff(s)} - \rho_y
\end{equation}
The vector $v^{(k)} = R \psi$ used with the $k$-SAT problem is related
to the vector from the corresponding 1-SAT problem $v^{(1)}$ by
$v^{(k)}_s = v^{(1)}_s + \delta_s$. Except for this change, the
remaining transformations of the algorithm are the same as in the
1-SAT case.  Thus
\begin{displaymath}
 U R \psi = \phi^{(1)} + U \Delta \psi
\end{displaymath}
where $\phi^{(1)}$ is the result of the corresponding 1-SAT problem,
i.e., all amplitude in the solution, and $\Delta$ is a diagonal
matrix, with elements given by $\delta(s)$. It is convenient to define
the average value of $\delta(s)$ over all assignments with $y$ bad values:
\begin{equation}
\delta_y = \frac{1}{{n \choose y}} {\sum_s}' \delta(s)
\end{equation}
where the sum is restricted to just the $n \choose y$ assignments with
$y$ bad values.

The change in the amplitude in the solution state is determined by
$\eta \equiv (U \Delta \psi)_r$ when $r$ is the solution.  This change
can be expressed using \eq{UR} by recalling that $h=0$ for the
solution and replacing the phases $\rho_y$ by the error in the phases,
$\delta_y$:
\begin{equation}\eqlabel{error}
\eta= 2^{-n/2}  
	\sum_{y=0}^n {n \choose y} 
		u_y \delta_y
\end{equation}
Since all the $\rho_y$ have unit magnitude, $|\delta_y| \leq 2$.  If
the problem has only one solution, the probability the algorithm will
find it is $P_{\rm soln} = | 1 + \eta |^2$. If there are multiple
solutions, this is a lower bound on the probability.

The following sections use these observations to extend the range of problems
to which the 1-SAT algorithm can be effectively applied.


\section{Solving Maximally Constrained $k$-SAT}\sectlabel{ksat}

The regular structure of maximally constrained soluble $k$-SAT
problems allows them to be solved in $O(1)$ steps.  That is, the
probability to find a solution remains $O(1)$ as $n$ increases.  Thus
a solution is very likely to be found by repeating the algorithm
$O(1)$ times, and, as described above, each trial of the algorithm
involves only one evaluation of the conflicts. To see this, we use
$\cEff(s)$ from \eq{cEff}.  For $k>2$, this approximation
results in incorrect phase choices for only a few, high-conflict
assignments. Because the proportion of incorrect phases is small, we
can expect this approximation will introduce only small amplitudes in
nonsolution states. However, it will also make the algorithm
incomplete: it can find a solution if one exists but not prove no
solutions exist.

Specifically, $\delta(s)$ can be nonzero only for $y \ge n-k+3$, where
$y$ is the number of bad values in assignment $s$. Thus using
\eq{error}, $|\delta_y| \leq 2$ and \eq{ud},
\begin{displaymath}
|\eta| \leq 2^{-n} 2 \sum_{y=n-k+3}^n {n \choose y}
\end{displaymath}
When $n-k+3 \ge n/2$, the sum over binomial coefficients can be
bounded~\cite{palmer85} to give
\begin{equation}\eqlabel{bound}
|\eta| \leq 2^{-(n-1)} {n \choose k-3} \frac{n+1-(k-3)}{n+1-2(k-3)} \sim 2^{-(n-1)} \frac{n^{k-3}}{(k-3)!}
\end{equation}
Thus the probability to obtain a solution is
\begin{equation}\eqlabel{Psoln}
P_{\rm soln} = |1 + \eta| ^2 \ge (1 - |\eta|)^2 \sim 1-2^{-(n-2)} \frac{n^{k-3}}{(k-3)!} \rightarrow 1
\end{equation}
which rapidly approaches 1. Hence, this algorithm is able to find the
solution in $O(1)$ search steps as $n$ increases. This behavior is
illustrated in \fig{probSoln}.

\figdef{probSoln}{
\epsfig{file=figs/probSoln.eps}
}{Behavior of $1-P_{\rm soln}$ vs. $n$ for maximally constrained soluble
$k$-SAT for $k=3$ (black) and 4 (gray). For comparison, the bounds $(1
- |\eta|)^2$ from \eq{bound} are shown as the dashed lines.}

Similarly, soluble balanced $k$-SAT problems with the maximum possible
number of clauses, given by \eq{mMaxBalanced}, give good performance
as shown in \fig{probSolnBalanced}. The behavior in this case is
rather irregular and continues for larger values of $n$, 
but still gives a high probability to find a
solution. For odd $k$, the probability for a solution is exactly one
for many values of $n$. In fact, by including neighborhood
information, the errors in the remaining cases can also be eliminated,
giving a perfect algorithm for these problems.  For even $k$, the
balanced clauses force the problem to have two solutions with opposite
values. Even though this problem structure differs significantly from
that of a 1-SAT problem with a single solution, the algorithm is able
to find solutions for $k=4$ with probability of about 1/2, even as $n$
increases.

\figdef{probSolnBalanced}{
\epsfig{file=figs/probSolnUnbias.eps}
}{Behavior of $P_{\rm soln}$ vs. $n$ for maximally constrained balanced
soluble $k$-SAT for $k=3$ (black) and 4 (gray). For comparison, the
bounds $(1 - |\eta|)^2$ based on \eq{error} are shown as the dashed
lines, and is quite small for the $k=4$ case.}



\section{Solving Highly Constrained Random $k$-SAT}\sectlabel{high}

{
\newcommand{\expect}[1]{\overline{#1}}
\newcommand{\muCrit}{ {\mu_{\rm crit}} }
\newcommand{\erfI}{ {{\rm erf}^{-1}} }

The discussion of \sect{random} shows how a maximum likelihood
estimate for $\cEff$ can be computed for each assignment.
This value can then be used to extend the algorithm to arbitrary
$k$-SAT problems. To the extent that the errors introduced by this
approximation are small, the quantum algorithm will have a substantial
probability to find a solution in a single step.

When averaged over the problem ensemble, the error given by \eq{error}
becomes
$$
\expect{|\eta|} \leq B \equiv 2^{-n} 2 \sum_{y=0}^n {n \choose y} p_y
$$ where $p_y$ is the probability an assignment with $y$ bad values is
(incorrectly) determined to have a different number of bad values. In
terms of the conditional probabilities of \sect{random},
$$
p_y = 1 - \sum_c \Pconf(c | y) \chi_{cy}
$$ where $\chi_{cy} = 1$ when the maximum likelihood estimate for a
state with $c$ conflicts is $y$ (i.e., $\cEff=y)$, and 0
otherwise. 

For simplicity, these maximum likelihood estimates are determined
solely from the number of conflicts in each state. The $\cEff$
values could be made a bit more accurate by including neighborhood
information, as was used for maximally constrained random problems in
\sect{ksat}.

Because highly constrained random SAT problems are relatively easy,
they have not been well-studied with classical algorithms. Hence, to
provide comparison with the quantum search results presented below,
these problems were also solved with the classical GSAT
procedure~\cite{selman92}, limiting each trial to use no more than
$2n$ steps before a new random initial state was selected. For both
random and balanced ensembles, the median number of search steps
required to find a solution grows linearly over the range of sizes
considered here when $m = O(n^2)$.  In particular, while the balanced
ensemble has larger search costs, it still grows linearly when there
is such a large number of clauses.



\subsection{Random $k$-SAT}

For random $k$-SAT with prespecified solution, Stirling's asymptotic
expansion in \eq{Pr(c,j)} shows that $p_y=O(1)$ for $y=O(n)$ when $m$
grows as $O(n^2)$, which is much less that the maximum $m_{\rm max} =
O(n^k)$. In this case, the asymptotic behavior of the bound $B$ is
determined by the values near the maximum of the binomial coefficient,
i.e., near $y=n/2$. Thus if $m = \mu n^2$, we have $ B \sim 2
p_{n/2}$.  From \eq{Psoln}, $P_{\rm soln}=O(1)$ at least when $B < 1$.
This is the case for $\mu > \muCrit$ where
\begin{equation}
\muCrit = 
	\left\{ \begin{array}{cl}
	27 \zeta^2 /(2+18 \zeta^2)	   & \mbox{if $k=2$} \\
	2 (2^k-1)^3 \zeta^2 / k^2 	   & \mbox{if $k>2$}
		\end{array}
	\right.
\end{equation}
where $\zeta \equiv \erfI(\frac{1}{2}) \approx 0.477$. For instance,
$\muCrit$ is 1.01 and 17.3 for $k=2$ and 3, respectively. Thus, the
algorithm presented here is simple enough to allow an analytic bound
on its behavior for highly constrained problems, thus demonstrating
its asymptotic effectiveness in these cases. Other, more complex,
structured quantum algorithms have only been evaluated
empirically~\cite{hogg95d,hogg97}, which is limited to small problems.


The algorithm's behavior with fewer constraints, i.e., $\mu < \muCrit$,
is not easily evaluted analytically since the bound provided by $B$ 
is no longer useful. Instead, the behavior can be examined
empirically using a classical simulation~\cite{hogg97b}, which is
however limited to problems with a relatively small number of
variables. These empirical studies may eventually be extendable to
larger problems using approximate evaluation techniques~\cite{cerf97}.

An example is given in \fig{phase}. This shows good performance for
highly constrained problems, as expected from the behavior of the
lower bound. Performance is also good with few constraints; not
because the algorithm is capturing the problem structure particularly
well but rather because there are many solutions to weakly
constrained problems. As with other classical and quantum search
methods that use problem structure, the hardest cases are for problems
with an intermediate number of constraints~\cite{hogg95e}.

\figdef{phase}{ 
\epsfig{file=figs/phase.eps} 
}{Probability to find a solution for random 3-SAT for $n=10$ (solid) and
20 (dashed) vs. $m/n$, on a log-log scale. Each point is an average
over at least 100 problem instances, and includes error bars for the
standard deviation in this estimate of the averge. The error bars are
smaller than the size of the plotted points. The gray lines show the
corresponding lower bounds $(1-B)^2$.}

From \fig{scaling} we see that the nonzero asymptotic limit for the
probability of a solution appears to continue for somewhat fewer
constraints than expected from the value of $\muCrit$. Below this
value, the probability for finding a solution appears to decrease as a
power of $n$, indicated by linear scaling on the log-log plot of
\fig{scaling} for $m = n^2$. Similar empirical evaluations of the
scaling with an intermediate number of constraints where the hard
problems are concentrated, e.g., $m = 4 n$ for 3-SAT, shows linear
scaling on a log-plot, indicating exponential decrease in the
probability to find a solution. Moreover, the resulting search costs
in these cases are larger than those of other structured quantum
search algorithms~\cite{hogg95d,hogg97}. Thus the structure of these
harder cases differs enough from the simple 1-SAT problems that this
algorithm is not effective for them.

\figdef{scaling}{ 
\epsfig{file=figs/scaling.eps} 
}{Probability to find a solution for random soluble 3-SAT vs. $n$ with,
from top to bottom, $m = 18 n^2$, $8 n^2$ and $n^2$, respectively, on
a log-log plot. For each value of $n$, at least 100 problem instances
were used. Error bars showing the expected error in the estimate are
included but are smaller than the size of the plotted points.}

In summary, the algorithm solves highly constrained problems with
$m = \mu n^2$ in $O(1)$ steps for $\mu > \muCrit$, and possibly for
somewhat smaller values of $\mu$ as well. As the number of clauses
is further reduced, the required number of steps appears to grow
polynomially when $\mu >0 $ and exponentially when $m = O(n)$.



\subsection{Balanced Clauses}

In a similar way, the behavior of problems with balanced clauses can
be evaluated, as shown in \fig{phaseBalanced}. In this case the lower
bound is much looser than for random soluble problems. This is
because, unlike the previous case, significant errors are made in
assigning $\cEff$ for the large number of assignments with about
$n/2$ bad values. The bound assumes that any such mistake gives the
maximum possible contribution to \eq{error}, but in fact because of
the limited phase choices in \eq{rho}, some such mistakes will
nevertheless give the correct value of the phase. Again, the
intermediate problems are the most difficult for this algorithm.

\figdef{phaseBalanced}{ 
\epsfig{file=figs/phaseUnbias.eps} 
}{Probability to find a solution for random balanced 3-SAT for $n=10$
(solid) and 20 (dashed) vs. $m/n$, on a log-log scale. Each point
represents 100 problem instances and includes error bars which, in
most cases, are smaller than the size of the plotted points. The gray
lines show the corresponding lower bounds $(1-B)^2$}

Because the bound is so poor, its asymptotic behavior does not offer a
useful guide to the behavior of the algorithm for highly constrained
problems. Instead, the scaling for $m=O(n^2)$ is illustrated in
\fig{scalingBalanced}. The behavior is consistent with a polynomial
decrease in the probability to find a solution, but definitive
statements cannot be made from such small problem sizes.

\figdef{scalingBalanced}{ 
\epsfig{file=figs/scalingUnbias.eps} 
}{Probability to find a solution for random balanced 3-SAT vs. $n$ with,
from top to bottom, $m = 8 n^2$ and $n^2$, respectively, on a log-log
plot. For each value of $n$, 100 problem instances were used. Error
bars showing the expected error in the estimate are included but are
smaller than the size of the plotted points.}




} % end of grouping for commands in this section



\section{Discussion}

The algorithm presented in this paper provides an analytic
demonstration that quantum machines can significantly exploit the
structure of highly constrained $k$-SAT problems, thereby extending
the range of search problems that definitely have effective quantum
algorithms.  This contrasts with previous work on structured quantum
algorithms that could only be evaluated empirically.

In addition, for maximally constrained 2-SAT problems and many
maximally constrained balanced $k$-SAT problems, the algorithm finds a
solution with probability one. Thus in these cases, failure to find a
solution definitely indicates the problem is not soluble, i.e., the
search method is {\em complete}. As described in \sect{problems},
with the slight additional cost of evaluating the number of conflicts
in the complement of an assignment as well as the assignment itself
for maximally constrained $k$-SAT, the correct corresponding 1-SAT
problem can be determined. This additional information thus gives
a complete search algorithm for maximally constrained $k$-SAT.
This contrasts with previously proposed quantum algorithms that find 
solutions with probability less than one and hence cannot guarantee 
no solutions exist.

One direction for future work is generalizing this algorithm to other
types of combinatorial search. For instance, the algorithm is
restricted to CSPs with two values per variable, such as SAT. While
other CSPs can be recast as satisfiability problems, this mapping may
obscure structure inherent in the original formulation. Thus it would
be useful to find algorithms that apply directly to more general CSP
formulations. One possible approach would be based on search methods
that construct solutions incrementally from smaller parts, i.e.,
expanding the set of states to include assignments that give values to
only some of the variables in the problem. Such a representation can
apply readily to CSPs with any number of values for the
variables~\cite{hogg95d,hogg97}. Another approach would examine
replacing Walsh transforms with the approximate Fourier
transform~\cite{kitaev95} as has been proposed to extend an
unstructured search method to cases where the size of the search space
is not a power of two~\cite{boyer96}. Beyond CSPs, it would be
interesting to investigate optimization problems.

Search problems with an intermediate number of constraints are the
most difficult for classical heuristics as well as structure-based
quantum searches~\cite{hogg95d,hogg97} based on analogies with these
classical methods. For $k$-SAT, these hard cases occur when the number
of clauses grows linearly with the number of variables, which is much
smaller than the $O(n^2)$ used in \sect{high}.  The intermediate
number of clauses creates considerable variance in the detailed
structure of the search space from one problem instance to
another. Thus one cannot rely on precise {\it a priori} knowledge of
the structure in designing the algorithm. Nevertheless, the average or
typical structure of these harder search problems has been
characterized~\cite{cheeseman91,hogg95e,hogg94a,kirkpatrick94,monasson96,williams92}
and may be suitable as a basis for developing appropriate search
methods.  Instead of aiming for a single-step algorithm, the large
variation in structure is likely to require a series of smaller
changes to the amplitudes, along with repeated tests of the
consistency of all assignments, as with previous
proposals~\cite{grover96,hogg97}. However, since a quantum algorithm
can explore all search paths simultaneously, it can avoid some of the
variability encountered in classical methods: namely, that due to
random selection of initial states or random tie-breaking when
evaluating heuristics. Thus a quantum algorithm can focus on variation
due only to differences in problem instances rather than also to the
particular choices made in exploring a single search path. Ultimately,
this observation may allow quantum algorithms to more usefully exploit
improved understanding of typical problem structure than is feasible
for classical methods.

This discussion raises the general issue of optimally using the
information that can be readily extracted from CSP search states, as
commonly used in classical heuristics. Such information includes the
number of conflicts a state has and how it compares with its
neighbors. Additional information is available on partial assignments,
as used with incremental searches, but at the cost of involving a
greatly expanded search space.  The approach described in \sect{app}
suggests a useful technique is matching quantum algorithms to the
average structure of search problem ensembles.  

The most significant open question is the extent to which quantum
algorithms can solve problems in polynomial time that require
exponential time classically. Factoring provides one
example~\cite{shor94}, if, as commonly believed, it cannot be done in
polynomial time classically. By contrast, highly constrained searches
can be solved in polynomial time by both classical heuristics and, as
shown in this paper, quantum machines. At the other extreme, searches
that ignore problem structure are exponential, requiring $O(2^n)$
steps classically, and $O(2^{n/2})$ steps on quantum
computers~\cite{boyer96}.  These observations can be summarized as:
\begin{center}
\begin{tabular}{l|cc}
		      & \multicolumn{2}{c}{cost scaling} \\
  type of problem     & classical      & quantum  \\ \hline
  unstructured        & exponential    & exponential \\
  factoring           & exponential    & \bf polynomial  \\
  highly constrained  & \bf polynomial & \bf polynomial  \\
\end{tabular}
\end{center}
This comparison suggests some problems, including factoring, have
enough structure to allow quantum machines to operate in polynomial
time but not enough for classical machines to do so. Identifying the
class of such problems is an important research direction for quantum
computation. For example, an interesting open question is whether
there is a scaling regime for the number of clauses, $m$, as a
function of $n$ where the probability of finding a solution with a
quantum machine decreases only polynomially with $n$ while classical
searches require an exponential number of steps, even with the best
known heuristics. This question is difficult to treat empirically,
pointing to the need for further analytic investigation of quantum
algorithms and the structure of search problems.




\section*{Acknowledgments}

I have benefited from discussions with Ian Gent, Carlos Mochon, Wolf
Polak and Eleanor Rieffel.

% for submission insert result of bibtex directly into this file
%\bibliography{physrev,received}
%\bibliographystyle{theapa}
\begin{thebibliography}{}

\bibitem[\protect\BCAY{Barenco, Deutsch, \BBA\ Ekert}{Barenco
  et~al.}{1995}]{barenco95}
Barenco, A., Deutsch, D., \BBA\ Ekert, A. \BBOP1995\BBCP.
\newblock \BBOQ Conditional quantum dynamics and logic gates\BBCQ\
\newblock {\Bem Physical Review Letters}, {\Bem 74}, 4083--4086.

\bibitem[\protect\BCAY{Benioff}{Benioff}{1982}]{benioff82}
Benioff, P. \BBOP1982\BBCP.
\newblock \BBOQ Quantum mechanical hamiltonian models of {Turing}
  machines\BBCQ\
\newblock {\Bem J. Stat. Phys.}, {\Bem 29}, 515--546.

\bibitem[\protect\BCAY{Bennett \BBA\ Landauer}{Bennett \BBA\
  Landauer}{1985}]{bennett85a}
Bennett, C.~H.\BBACOMMA\  \BBA\ Landauer, R. \BBOP1985\BBCP.
\newblock \BBOQ The fundamental physical limits of computation\BBCQ\
\newblock {\Bem Scientific American}, July, 48--56.

\bibitem[\protect\BCAY{Bernstein \BBA\ Vazirani}{Bernstein \BBA\
  Vazirani}{1993}]{bernstein92}
Bernstein, E.\BBACOMMA\  \BBA\ Vazirani, U. \BBOP1993\BBCP.
\newblock \BBOQ Quantum complexity theory\BBCQ\
\newblock In {\Bem Proc. 25th ACM Symp. on Theory of Computation}, \BPGS\
  11--20.

\bibitem[\protect\BCAY{Berthiaume, Deutsch, \BBA\ Jozsa}{Berthiaume
  et~al.}{1994}]{berthiaume94}
Berthiaume, A., Deutsch, D., \BBA\ Jozsa, R. \BBOP1994\BBCP.
\newblock \BBOQ The stabilization of quantum computations\BBCQ\
\newblock In {\Bem Proc. of the Workshop on Physics and Computation
  (PhysComp94)}, \BPGS\ 60--62\ Los Alamitos, CA. IEEE Press.

\bibitem[\protect\BCAY{Bouwmeester et~al.}{Bouwmeester
  et~al.}{1997}]{bouwmeester97}
Bouwmeester, D.\BBACOMMA\  et~al. \BBOP1997\BBCP.
\newblock \BBOQ Experimental quantum teleportation\BBCQ\
\newblock {\Bem Nature}, {\Bem 390}, 575--579.

\bibitem[\protect\BCAY{Boyer, Brassard, Hoyer, \BBA\ Tapp}{Boyer
  et~al.}{1996}]{boyer96}
Boyer, M., Brassard, G., Hoyer, P., \BBA\ Tapp, A. \BBOP1996\BBCP.
\newblock \BBOQ Tight bounds on quantum searching\BBCQ\
\newblock In Toffoli, T.\BBACOMMA\  et~al.\BEDS, {\Bem Proc. of the Workshop on
  Physics and Computation (PhysComp96)}, \BPGS\ 36--43\ Cambridge, MA. New
  England Complex Systems Institute.

\bibitem[\protect\BCAY{Brassard, Hoyer, \BBA\ Tapp}{Brassard
  et~al.}{1998}]{brassard98}
Brassard, G., Hoyer, P., \BBA\ Tapp, A. \BBOP1998\BBCP.
\newblock \BBOQ Quantum counting\BBCQ\
\newblock {Los Alamos} preprint quant-ph/9805082.

\bibitem[\protect\BCAY{Cerf \BBA\ Koonin}{Cerf \BBA\ Koonin}{1997}]{cerf97}
Cerf, N.~J.\BBACOMMA\  \BBA\ Koonin, S.~E. \BBOP1997\BBCP.
\newblock \BBOQ {Monte Carlo} simulation of quantum computation\BBCQ\
\newblock In {\Bem Proc. of IMACS Conf. on Monte Carlo Methods}.
\newblock Los Alamos preprint quant-ph/9703050.

\bibitem[\protect\BCAY{Cerf, Grover, \BBA\ Williams}{Cerf
  et~al.}{1998}]{cerf98}
Cerf, N.~J., Grover, L.~K., \BBA\ Williams, C.~P. \BBOP1998\BBCP.
\newblock \BBOQ Nested quantum search and {NP}-complete problems\BBCQ\
\newblock {Los Alamos} preprint quant-ph/9806078.

\bibitem[\protect\BCAY{Cerny}{Cerny}{1993}]{cerny93}
Cerny, V. \BBOP1993\BBCP.
\newblock \BBOQ Quantum computers and intractable ({NP}-complete) computing
  problems\BBCQ\
\newblock {\Bem Physical Review A}, {\Bem 48}, 116--119.

\bibitem[\protect\BCAY{Cheeseman, Kanefsky, \BBA\ Taylor}{Cheeseman
  et~al.}{1991}]{cheeseman91}
Cheeseman, P., Kanefsky, B., \BBA\ Taylor, W.~M. \BBOP1991\BBCP.
\newblock \BBOQ Where the really hard problems are\BBCQ\
\newblock In Mylopoulos, J.\BBACOMMA\  \BBA\ Reiter, R.\BEDS, {\Bem Proceedings
  of IJCAI91}, \BPGS\ 331--337\ San Mateo, CA. Morgan Kaufmann.

\bibitem[\protect\BCAY{Chuang, Vandersypen, Zhou, Leung, \BBA\ Lloyd}{Chuang
  et~al.}{1998}]{chuang98}
Chuang, I.~L., Vandersypen, L. M.~K., Zhou, X., Leung, D.~W., \BBA\ Lloyd, S.
  \BBOP1998\BBCP.
\newblock \BBOQ Experimental realization of a quantum algorithm\BBCQ\
\newblock {\Bem Nature}, {\Bem 393}, 143--146.
\newblock Los Alamos preprint quant-ph/9801037.

\bibitem[\protect\BCAY{Cirac \BBA\ Zoller}{Cirac \BBA\ Zoller}{1995}]{cirac95}
Cirac, J.~I.\BBACOMMA\  \BBA\ Zoller, P. \BBOP1995\BBCP.
\newblock \BBOQ Quantum computations with cold trapped ions\BBCQ\
\newblock {\Bem Physical Review Letters}, {\Bem 74}, 4091--4094.

\bibitem[\protect\BCAY{Cory, Fahmy, \BBA\ Havel}{Cory et~al.}{1996}]{cory96}
Cory, D.~G., Fahmy, A.~F., \BBA\ Havel, T.~F. \BBOP1996\BBCP.
\newblock \BBOQ Nuclear magnetic resonance spectroscopy: An experimentally
  accessible paradigm for quantum computing\BBCQ\
\newblock In Toffoli, T.\BBACOMMA\  et~al.\BEDS, {\Bem Proc. of the Workshop on
  Physics and Computation (PhysComp96)}, \BPGS\ 87--91\ Cambridge, MA. New
  England Complex Systems Institute.

\bibitem[\protect\BCAY{Deutsch}{Deutsch}{1985}]{deutsch85}
Deutsch, D. \BBOP1985\BBCP.
\newblock \BBOQ Quantum theory, the {Church-Turing} principle and the universal
  quantum computer\BBCQ\
\newblock {\Bem Proc. R. Soc. London A}, {\Bem 400}, 97--117.

\bibitem[\protect\BCAY{Deutsch}{Deutsch}{1989}]{deutsch89}
Deutsch, D. \BBOP1989\BBCP.
\newblock \BBOQ Quantum computational networks\BBCQ\
\newblock {\Bem Proc. R. Soc. Lond.}, {\Bem A425}, 73--90.

\bibitem[\protect\BCAY{Dirac}{Dirac}{1958}]{dirac58}
Dirac, P. A.~M. \BBOP1958\BBCP.
\newblock {\Bem The Principles of Quantum Mechanics\/} (4th \BEd).
\newblock Oxford.

\bibitem[\protect\BCAY{DiVincenzo}{DiVincenzo}{1995}]{divincenzo95}
DiVincenzo, D.~P. \BBOP1995\BBCP.
\newblock \BBOQ Quantum computation\BBCQ\
\newblock {\Bem Science}, {\Bem 270}, 255--261.

\bibitem[\protect\BCAY{Feynman}{Feynman}{1986}]{feynman86}
Feynman, R.~P. \BBOP1986\BBCP.
\newblock \BBOQ Quantum mechanical computers\BBCQ\
\newblock {\Bem Foundations of Physics}, {\Bem 16}, 507--531.

\bibitem[\protect\BCAY{Feynman}{Feynman}{1985}]{feynman85}
Feynman, R.~P. \BBOP1985\BBCP.
\newblock {\Bem {QED}: The Strange Theory of Light and Matter}.
\newblock Princeton Univ. Press, NJ.

\bibitem[\protect\BCAY{Feynman}{Feynman}{1996}]{feynman96}
Feynman, R.~P. \BBOP1996\BBCP.
\newblock {\Bem Feynman Lectures on Computation}.
\newblock Addison-Wesley, Reading, MA.

\bibitem[\protect\BCAY{Garey \BBA\ Johnson}{Garey \BBA\
  Johnson}{1979}]{garey79}
Garey, M.~R.\BBACOMMA\  \BBA\ Johnson, D.~S. \BBOP1979\BBCP.
\newblock {\Bem Computers and Intractability: A Guide to the Theory of
  NP-Completeness}.
\newblock W. H. Freeman, San Francisco.

\bibitem[\protect\BCAY{Gent}{Gent}{1998}]{gent96b}
Gent, I. \BBOP1998\BBCP.
\newblock \BBOQ On the stupid algorithm for satisfiability\BBCQ\
\newblock \BTR\ APES-03-1998, Strathclyde University.
\newblock Available at www.cs.strath.ac.uk/$\sim$apes/apereports.html.

\bibitem[\protect\BCAY{Gershenfeld, Chuang, \BBA\ Lloyd}{Gershenfeld
  et~al.}{1996}]{gershenfeld96}
Gershenfeld, N., Chuang, I., \BBA\ Lloyd, S. \BBOP1996\BBCP.
\newblock \BBOQ Bulk quantum computation\BBCQ\
\newblock In Toffoli, T.\BBACOMMA\  et~al.\BEDS, {\Bem Proc. of the Workshop on
  Physics and Computation (PhysComp96)}, \BPG\ 134\ Cambridge, MA. New England
  Complex Systems Institute.

\bibitem[\protect\BCAY{Grover}{Grover}{1997a}]{grover97a}
Grover, L.~K. \BBOP1997a\BBCP.
\newblock \BBOQ Quantum computers can search arbitrarily large databases by a
  single query\BBCQ\
\newblock {Los Alamos} preprint quant-ph/9706005, Bell Labs.

\bibitem[\protect\BCAY{Grover}{Grover}{1997b}]{grover96}
Grover, L.~K. \BBOP1997b\BBCP.
\newblock \BBOQ Quantum mechanics helps in searching for a needle in a
  haystack\BBCQ\
\newblock {\Bem Physical Review Letters}, {\Bem 78}, 325--328.

\bibitem[\protect\BCAY{Haroche \BBA\ Raimond}{Haroche \BBA\
  Raimond}{1996}]{haroche96}
Haroche, S.\BBACOMMA\  \BBA\ Raimond, J.-M. \BBOP1996\BBCP.
\newblock \BBOQ Quantum computing: Dream or nightmare?\BBCQ\
\newblock {\Bem Physics Today}, {\Bem 49}, 51--52.

\bibitem[\protect\BCAY{Hogg}{Hogg}{1996}]{hogg95d}
Hogg, T. \BBOP1996\BBCP.
\newblock \BBOQ Quantum computing and phase transitions in combinatorial
  search\BBCQ\
\newblock {\Bem J. of Artificial Intelligence Research}, {\Bem 4}, 91--128.
\newblock Available at http://www.jair.org/ab\-stracts/hogg96a.html.

\bibitem[\protect\BCAY{Hogg}{Hogg}{1998a}]{hogg97}
Hogg, T. \BBOP1998a\BBCP.
\newblock \BBOQ A framework for structured quantum search\BBCQ\
\newblock {\Bem Physica D}, {\Bem 120}, 102--116.
\newblock Los Alamos preprint quant-ph/9701013.

\bibitem[\protect\BCAY{Hogg}{Hogg}{1998b}]{hogg98}
Hogg, T. \BBOP1998b\BBCP.
\newblock \BBOQ Highly structured searches with quantum computers\BBCQ\
\newblock {\Bem Physical Review Letters}, {\Bem 80}, 2473--2476.
\newblock Preprint at
  pub\-lish.aps.org/eprint/gate\-way/eplist/aps1997oct30\_002.

\bibitem[\protect\BCAY{Hogg, Huberman, \BBA\ Williams}{Hogg
  et~al.}{1996}]{hogg95e}
Hogg, T., Huberman, B.~A., \BBA\ Williams, C. \BBOP1996\BBCP.
\newblock \BBOQ Phase transitions and the search problem\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 81}, 1--15.

\bibitem[\protect\BCAY{Hogg \BBA\ Williams}{Hogg \BBA\
  Williams}{1994}]{hogg94a}
Hogg, T.\BBACOMMA\  \BBA\ Williams, C.~P. \BBOP1994\BBCP.
\newblock \BBOQ The hardest constraint problems: A double phase
  transition\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 69}, 359--377.

\bibitem[\protect\BCAY{Hogg \BBA\ Yanik}{Hogg \BBA\ Yanik}{1998}]{hogg97b}
Hogg, T.\BBACOMMA\  \BBA\ Yanik, M. \BBOP1998\BBCP.
\newblock \BBOQ Local search methods for quantum computers\BBCQ\
\newblock {Los Alamos} preprint quant-ph/9802043, Xerox.

\bibitem[\protect\BCAY{Hoyer}{Hoyer}{1997}]{hoyer97}
Hoyer, P. \BBOP1997\BBCP.
\newblock \BBOQ Efficient quantum transforms\BBCQ\
\newblock {Los Alamos} preprint quant-ph/9702028.

\bibitem[\protect\BCAY{Kirkpatrick \BBA\ Selman}{Kirkpatrick \BBA\
  Selman}{1994}]{kirkpatrick94}
Kirkpatrick, S.\BBACOMMA\  \BBA\ Selman, B. \BBOP1994\BBCP.
\newblock \BBOQ Critical behavior in the satisfiability of random boolean
  expressions\BBCQ\
\newblock {\Bem Science}, {\Bem 264}, 1297--1301.

\bibitem[\protect\BCAY{Kitaev}{Kitaev}{1995}]{kitaev95}
Kitaev, A.~Y. \BBOP1995\BBCP.
\newblock \BBOQ Quantum measurements and the {Abelian} stabilizer problem\BBCQ\
\newblock {Los Alamos} preprint quant-ph/9511026.

\bibitem[\protect\BCAY{Knill, Laflamme, \BBA\ Zurek}{Knill
  et~al.}{1998}]{knill98}
Knill, E., Laflamme, R., \BBA\ Zurek, W.~H. \BBOP1998\BBCP.
\newblock \BBOQ Resilient quantum computation\BBCQ\
\newblock {\Bem Science}, {\Bem 279}, 342--345.

\bibitem[\protect\BCAY{Landauer}{Landauer}{1994}]{landauer94a}
Landauer, R. \BBOP1994\BBCP.
\newblock \BBOQ Is quantum mechanically coherent computation useful?\BBCQ\
\newblock In Feng, D.~H.\BBACOMMA\  \BBA\ Hu, B.-L.\BEDS, {\Bem Proc. of the
  Drexel-4 Symposium on Quantum Nonintegrability}\ Boston. International Press.

\bibitem[\protect\BCAY{Lloyd}{Lloyd}{1993}]{lloyd93}
Lloyd, S. \BBOP1993\BBCP.
\newblock \BBOQ A potentially realizable quantum computer\BBCQ\
\newblock {\Bem Science}, {\Bem 261}, 1569--1571.

\bibitem[\protect\BCAY{Mackworth}{Mackworth}{1992}]{mackworth92}
Mackworth, A. \BBOP1992\BBCP.
\newblock \BBOQ Constraint satisfaction\BBCQ\
\newblock In Shapiro, S.\BED, {\Bem Encyclopedia of Artificial Intelligence},
  \BPGS\ 285--293. Wiley, NY.

\bibitem[\protect\BCAY{Minton, Johnston, Philips, \BBA\ Laird}{Minton
  et~al.}{1992}]{minton92}
Minton, S., Johnston, M.~D., Philips, A.~B., \BBA\ Laird, P. \BBOP1992\BBCP.
\newblock \BBOQ Minimizing conflicts: A heuristic repair method for constraint
  satisfaction and scheduling problems\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 58}, 161--205.

\bibitem[\protect\BCAY{Monasson \BBA\ Zecchina}{Monasson \BBA\
  Zecchina}{1996}]{monasson96}
Monasson, R.\BBACOMMA\  \BBA\ Zecchina, R. \BBOP1996\BBCP.
\newblock \BBOQ The entropy of the k-satisfiability problem\BBCQ\
\newblock {\Bem Phys. Rev. Lett.}, {\Bem 76}, 3881--3885.

\bibitem[\protect\BCAY{Monroe \BBA\ Wineland}{Monroe \BBA\
  Wineland}{1996}]{monroe96a}
Monroe, C.\BBACOMMA\  \BBA\ Wineland, D. \BBOP1996\BBCP.
\newblock \BBOQ Future of quantum computing proves to be debatable\BBCQ\
\newblock {\Bem Physics Today}, {\Bem 49}, 107--108.

\bibitem[\protect\BCAY{Nijenhuis \BBA\ Wilf}{Nijenhuis \BBA\
  Wilf}{1978}]{nijenhuis78}
Nijenhuis, A.\BBACOMMA\  \BBA\ Wilf, H.~S. \BBOP1978\BBCP.
\newblock {\Bem Combinatorial Algorithms for Computers and Calculators\/} (2nd
  \BEd).
\newblock Academic Press, New York.

\bibitem[\protect\BCAY{Palmer}{Palmer}{1985}]{palmer85}
Palmer, E.~M. \BBOP1985\BBCP.
\newblock {\Bem Graphical Evolution: An Introduction to the Theory of Random
  Graphs}.
\newblock Wiley Interscience, NY.

\bibitem[\protect\BCAY{Selman, Levesque, \BBA\ Mitchell}{Selman
  et~al.}{1992}]{selman92}
Selman, B., Levesque, H., \BBA\ Mitchell, D. \BBOP1992\BBCP.
\newblock \BBOQ A new method for solving hard satisfiability problems\BBCQ\
\newblock In {\Bem Proc. of the 10th Natl. Conf. on Artificial Intelligence
  (AAAI92)}, \BPGS\ 440--446\ Menlo Park, CA. AAAI Press.

\bibitem[\protect\BCAY{Shor}{Shor}{1995}]{shor95}
Shor, P. \BBOP1995\BBCP.
\newblock \BBOQ Scheme for reducing decoherence in quantum computer
  memory\BBCQ\
\newblock {\Bem Physical Review A}, {\Bem 52}, 2493--2496.

\bibitem[\protect\BCAY{Shor}{Shor}{1994}]{shor94}
Shor, P.~W. \BBOP1994\BBCP.
\newblock \BBOQ Algorithms for quantum computation: Discrete logarithms and
  factoring\BBCQ\
\newblock In Goldwasser, S.\BED, {\Bem Proc. of the 35th Symposium on
  Foundations of Computer Science}, \BPGS\ 124--134\ Los Alamitos, CA. IEEE
  Press.

\bibitem[\protect\BCAY{Sleator \BBA\ Weinfurter}{Sleator \BBA\
  Weinfurter}{1995}]{sleator95}
Sleator, T.\BBACOMMA\  \BBA\ Weinfurter, H. \BBOP1995\BBCP.
\newblock \BBOQ Realizable universal quantum logic gates\BBCQ\
\newblock {\Bem Physical Review Letters}, {\Bem 74}, 4087--4090.

\bibitem[\protect\BCAY{Terhal \BBA\ Smolin}{Terhal \BBA\
  Smolin}{1997}]{terhal97}
Terhal, B.~M.\BBACOMMA\  \BBA\ Smolin, J.~A. \BBOP1997\BBCP.
\newblock \BBOQ Single quantum querying of a database\BBCQ\
\newblock {Los Alamos} preprint quant-ph/9705041 v4, IBM.

\bibitem[\protect\BCAY{Unruh}{Unruh}{1995}]{unruh94}
Unruh, W.~G. \BBOP1995\BBCP.
\newblock \BBOQ Maintaining coherence in quantum computers\BBCQ\
\newblock {\Bem Physical Review A}, {\Bem 51}, 992--997.

\bibitem[\protect\BCAY{Van~Gelder \BBA\ Tsuji}{Van~Gelder \BBA\
  Tsuji}{1993}]{vangelder93}
Van~Gelder, A.\BBACOMMA\  \BBA\ Tsuji, Y.~K. \BBOP1993\BBCP.
\newblock \BBOQ Incomplete thoughts about incomplete satisfiability
  problems\BBCQ\
\newblock In {\Bem Proc. of 2nd DIMACS Challenge}.

\bibitem[\protect\BCAY{Williams \BBA\ Hogg}{Williams \BBA\
  Hogg}{1994}]{williams92}
Williams, C.~P.\BBACOMMA\  \BBA\ Hogg, T. \BBOP1994\BBCP.
\newblock \BBOQ Exploiting the deep structure of constraint problems\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 70}, 73--117.

\end{thebibliography}


\end{document}



