Quantum random walks - an introductory overview <s> 2-SAT <s> Once we have developed an algorithm (q.v.) for solving a computational problem and analyzed its worst-case time requirements as a function of the size of its input (most usefully, in terms of the O-notation; see ALGORITHMS, ANALYSIS OF), it is inevitable to ask the question: "Can we do better?" In a typical problem, we may be able to devise new algorithms for the problem that are more and more efficient. But eventually, this line of research often seems to hit an invisible barrier, a level beyond whch improvements are very difficult, seemingly impossible, to come by. After many unsuccessful attempts, algorithm designers inevitably start to wonder if there is something inherent in the problem that makes it impossible to devise algorithms that are faster than the current one. They may try to develop mathematical techniques for proving formally that there can be no algorithm for the given problem which runs faster than the current one. Such a proof would be valuable, as it would suggest that it is futile to keep working on improved algorithms for this problem, that further improvements are certainly impossible. The realm of mathematical models and techniques for establishing such impossibility proofs is called computational complexity. <s> BIB001 </s> Quantum random walks - an introductory overview <s> 2-SAT <s> We present a simple probabilistic algorithm for solving k-SAT and more generally, for solving constraint satisfaction problems (CSP). The algorithm follows a simple local search paradigm (S. Minton et al., 1992): randomly guess an initial assignment and then, guided by those clauses (constraints) that are not satisfied, by successively choosing a random literal from such a clause and flipping the corresponding bit, try to find a satisfying assignment. If no satisfying assignment is found after O(n) steps, start over again. Our analysis shows that for any satisfiable k-CNF-formula with n variables this process has to be repeated only t times, on the average, to find a satisfying assignment, where t is within a polynomial factor of (2(1-1/k))/sup n/. This is the fastest (and also the simplest) algorithm for 3-SAT known up to date. We consider also the more general case of a CSP with n variables, each variable taking at most d values, and constraints of order l, and analyze the complexity of the corresponding (generalized) algorith m. It turns out that any CSP can be solved with complexity at most (d/spl middot/(1-1/l)+/spl epsiv/)/sup n/. <s> BIB002 </s> Quantum random walks - an introductory overview <s> 2-SAT <s> We present a fully-polynomial randomized approximation scheme for computing the permanent of an arbitrary matrix with non-negative entries. <s> BIB003
Let us give another computational problem that can be solved by random walks on graphs, 2-SAT. Let us define more generally the class of decision problems called SAT. In an instance of SAT we are given a set of logical clauses C 1 , . . . C m . The Boolean inputs are the variables X 1 , X 2 , . . . X n which can take the values 0 or 1. They can appear in either uncomplemented (X i ) or complemented (¬X i ) form in the clauses. A clause is said to be satisfied if at least one of the variables in it is true (an unnegated variable X i is true if X i = 0, a negated variable ¬X i is true if X i = 1). For example the clause C = X 1 ∨ ¬X 2 ∨ X 3 is not satisfied only if X 1 X 2 X 3 = 101. We want to know if all the clauses can be satisfied simultaneously by some assignment of 0 and 1 for X 1 , . . . X n (then we say that the formula C 1 ∧ C 2 ∧ . . . ∧ C m is satisfiable and output YES). The class 2-SAT is the class of all SAT decision problems where each clause contains only two variables. For example take the following instance of 2-SAT on X 1 , X 2 , X 3 : The underlying decision problem has the answer YES and a satisfying assignment is X 1 X 2 X 3 = 110. The class of satisfiability problems is very important in theoretical computer science BIB001 . For instance in a famous piece of work (the Cook-Levin theorem) it has been shown that 3-SAT is as hard as any problem in the class NP. This class contains all problems that can be solved in so called non-deterministic polynomial time. That means that if we guess a solution then we can verify that it is indeed a solution in polynomial time. For instance if we were presented with a guess for the satisfying assignment of a formula in 3-SAT we are able to verify this with a machine running in time polynomial in the number of variables n by checking all the clauses C 1 , . . . C m . A plethora of decision and optimization problems are in the class NP. The Cook-Levin theorem states that if we had an efficient algorithm to solve 3-SAT (i.e. to find an answer YES/NO to the decision problem) we can change this into an algorithm to solve any other problem in NP with only polynomial overhead in time. Among the variety of problems known to be in NP we can find Shortest Common Superstring (relevant for gene-reconstruction from sequencing in biology), the Traveling Salesman Problem (important for tour-optimization), Bin Packing problems, the Minesweeper game and Protein Folding, to name just a few. It is not known if a polynomial time (in n) algorithm to solve 3-SAT exists (the famous P ? = N P problem). Let us now give a random walk algorithm that solves 2-SAT in time proportional to n 2 . To simplify things imagine that our formula is satisfiable and that it has a single truth assignment (in the example of Eq. BIB003 this is 110). The algorithm picks a random assignment of 0, 1 for the variables X 1 , . . . , X n . It checks the clauses one by one if they are satisfied until it either runs out of clauses (this means the assignment was satisfying, the algorithm stops and outputs YES) or it finds a clause C that is not satisfied. Say the two variables in the clause are X i and X j . In the true assignment one of these two variables must be flipped (0 ↔ 1). Now the algorithm choses one of the two variables X i or X j randomly and flips it. This is the new assignment and the algorithm restarts anew checking the clauses one by one etc. Let us look what happens to the Hamming distance between the true assignment (110 in the example of Eq. (34)) and the current assignment of the algorithm when we come to flipping X i or X j . In the true assignment one of the variables X i , X j must be flipped (since it satisfies the clause C). So with probability 1/2 the algorithm flips the right variable. In this case the Hamming distance between the new assignment and the true assignment has decreased by 1. Or the algorithm flips the wrong variable, in which case the Hamming distance increases by 1  . So we are faced with a random walk on the Hamming distances with transition probabilities 1/2. It is well known that such a walk on the line of length n will hit the corner with high probability after T ∼ n 2 steps. Figure 14 illustrates the algorithm for the example of Eq. BIB003 . Although this random walk algorithm is not the optimal one to solve 2-SAT it is very instructive. Many randomized algorithms can be viewed as random walks. The efficiency of these random algorithms is then closely related to the expected hitting time from a vertex (the initial state) to another (the solution). In fact the best known algorithm for 3-SAT BIB002 relies on a sophisticated version of this random walk idea. If a quantum random walk could improve the hitting time on certain graphs this could give rise to efficient quantum algorithms for problems that cannot be solved efficiently on a classical computer. It is yet another incentive to study the behavior of quantum random walks.