Quantum random walks - an introductory overview <s> particles. <s> The usual general-purpose computing automaton (e.g.. a Turing machine) is logically irreversible- its transition function lacks a single-valued inverse. Here it is shown that such machines may he made logically reversible at every step, while retainillg their simplicity and their ability to do general computations. This result is of great physical interest because it makes plausible the existence of thermodynamically reversible computers which could perform useful computations at useful speed while dissipating considerably less than kT of energy per logical step. In the first stage of its computation the logically reversible automaton parallels the corresponding irreversible automaton, except that it saves all intermediate results, there by avoiding the irreversible operation of erasure. The second stage consists of printing out the desired output. The third stage then reversibly disposes of all the undesired intermediate results by retracing the steps of the first stage in backward order (a process which is only possible because the first stage has been carried out reversibly), there by restoring the machine (except for the now-written output tape) to its original condition. The final machine configuration thus contains the desired output and a reconstructed copy of the input, but no other undesired data. The foregoing results are demonstrated explicitly using a type of three-tape Turing machine. The biosynthesis of messenger RNA is discussed as a physical example of reversible computation. <s> BIB001 </s> Quantum random walks - an introductory overview <s> particles. <s> The design of new quantum algorithms has proven to be an extremely difficult task. This paper considers a different approach to the problem, by studying the problem of 'quantum state generation'.We first show that any problem in Statistical Zero Knowledge (including eg. discrete log, quadratic residuosity and gap closest vector in a lattice) can be reduced to an instance of the quantum state generation problem. Having shown the generality of the state generation problem, we set the foundations for a new paradigm for quantum state generation. We define 'Adiabatic State Generation' (ASG), which is based on Hamiltonians instead of unitary gates. We develop tools for ASG including a very general method for implementing Hamiltonians (The sparse Hamiltonian lemma), and ways to guarantee non negligible spectral gaps (The jagged adiabatic path lemma). We also prove that ASG is equivalent in power to state generation in the standard quantum model. After setting the foundations for ASG, we show how to apply our techniques to generate interesting superpositions related to Markov chains.The ASG approach to quantum algorithms provides intriguing links between quantum computation and many different areas: the analysis of spectral gaps and groundstates of Hamiltonians in physics, rapidly mixing Markov chains, statistical zero knowledge, and quantum random walks. We hope that these links will bring new insights and methods into quantum algorithms. <s> BIB002
Gates: The computation of a classical computer can be described by a circuit consisting of gates (like AND or NOT) that act on one or two bits. The computer is initialized in some input state and computes some Boolean function of it. Similarly a quantum computer can be modeled by a circuit consisting of unitary gates that act on one or two qubits only. The goal is to compute some unitary transformation on the initial state. It is well known that every Boolean function can be decomposed into a succession of gates from a universal set (like AND and NOT). In other words any computation on a classical computer can be written as a succession of AND and NOT. One of the achievements of quantum computing theory has been the insight that any unitary computation on qubits can be decomposed into a succession of quantum gates that act on one or two qubits only. One such universal quantum gate set is given by single qubit unitary matrices U single (these are 2 by 2 matrices giving all the generalized rotations of a single spin-  To build a quantum computer then means to build a device that can implement single qubit unitaries together with a two-body transformation that implements the CNOT  . The question is whether such a quantum computer with its unitaries can even perform the computations of a classical computer. After all, unitary transformations are reversible, so all the quantum computations are reversible and the class of these reversible computations might not contain some classical circuits. It has been shown by Bennett BIB001 that this is not a serious problem: Any classical circuit can be made reversible by replacing its gates by a reversible three bit gate and adding some more scratch space. Furthermore these reversible gates can be implemented unitarily by a quantum computer. In particular this implies that a quantum computer can emulate any classical computation efficiently: quantum computers are at least as strong as their classical brothers. The added bonus of using the laws of quantum mechanics is that the unitary power might be strictly larger than the classical one. The quest for quantum algorithms is exactly to explore this added power. Returning to random walks we can see that a quantum computer can efficiently implement any discrete time quantum random walk whenever a classical computer can implement the underlying classical random walk. This is because we can take the classical circuit that implements the classical random walk, turn it into a quantum circuit (after making it reversible) and replacing the classical coin-flip by a quantum coin-flip, which can be done efficiently on the small space of coin-qubits. That means that if we take a classical random walk at the basis of some classical algorithm and show that the quantum random walk improves its behavior, we will immediately have a quantum algorithm with some speed-up over the classical. The situation is not quite as easy for the model of continuous time quantum random walks. It is not a priori clear how to adapt its continuous evolution to the discrete quantum circuit model. However it has been shown recently [39, BIB002 that simulation of continuous time random walks can be done efficiently on a quantum computer. With this in place we are now set to explore some more differences between classical and quantum random walks.