Learning in Simulation in a Grid-world -- using memory

• [A] B. Srinivasan "Analysis of Memory-Based Learning Schemes for Robot Navigation in Discrete Grid-Worlds with Partial Observability" (6 pages)
  
  • "The problem of robot navigation dealt with in this paper, is essentially that of finding an optimal navigable path for the robot in a given environment, with certain constraints imposed on the robot, such as a time limit or limited availability of resources. Optimal path here refers to a path between the two points say the source and destination, which has the least path cost, or in other words the most profitable one among all the existing paths."
  • "The approach used in this paper involves an autonomous learning technique, namely Reinforcement Learning."
  • "A technique of short-term memory that is used in this paper is known as Nearest Sequence Memory (NSM) [4]"
    • [4] McCallum, Andrew K., Reinforcement �gLearning with Selective Perception and Hidden State�h, PhD. thesis. December, 1995.
• "The entire state space and actions taken by the agent are formalized as a finite Markov Decision Process (MDP)[8]"
  • [8] Parr, R. E. �gHierarchical control and learning for markov decision processes�h. Doctoral Thesis, 1998.
• "Further, we test different Temporal Difference learning algorithms [11] on the agent, with and without the use of shortterm memory"
• "For most animals, navigation of some form is an essential part of its behavioral repertoire, which is required to find food, avoid predators, find mates, etc."
• "One of the primary behaviors demonstrated by animals, is dead reckoning. The term is thought to be a corruption of deduced reckoning, and refers to the process of updating one's estimate of one's position on the basis of knowledge of how fast one has been moving, in what direction, and for how long."
• "We created random populations of 500 genetypes. Each genotype was evaluated by decoding it intyo a robot architecture and placing the robot at a random position in a 10 x 10 grid-world with 10 boxes and 2 power sorces located randomly."
• "... module constantly monitors the robot's battery level, and if it falls below LBT, it consults the spatial map to determine the location of the nearest power sourse."

• [B] K. Balakrishnan, and V Honavar "Spatial Memory Structures for Sensor-Guided Robot Navigation." GP-97 (9 pages)
  
  • "... ants, bees, rodents, doves, etc., demonstrate a surprising sense of space and are capable of locating thier homes even after pseudo-random movements in search of food."
  • The hippocampal formation has been known to play a crucial role in the spatial learning ability of animals... However, even after decades of research the exact nature of the spatial information encoded and the representation and use of the cognitive map remains unansered in its entirety."
  • "we develop a model of spatial learning and navigation"

• [B] D. Nikovski "Visual Memory-Based Learning for Mobile Robot Navigation" (4 pages) real robot "Moore Atkeson Schaal Memory-based-Learning-for-Control [3] [3] Moore, A.W., Atkeson, C.G., and Schaal, S. (1995). Memory-based Learning for Control, CMU Robotics Institute Technical Report CMU-RI-TR-95-18, April 1995."
  
  • The author of "Finding Solutions to NP Problems: Philosophical Differences Between Quantum and Evolutionary Search Algorithms" claims the best tutorial among othres which were writtne by physisits.
  • "Accessing the results is equivalent to making a measurement, which disturbs the quantum state."
  • "a register of n qubits can be in a superposition of all 2^n possible values."
  • "only one classical bit's worth of information can be extracted from a qubit."
  • "all quantum state transformations have to be reversible. While the classical NOT gate is reversible, AND, OR and NAND gates are not. Thus it is not obvious that quantum transformations can carry out all classical computations."
  • "Boyer et.al. [Boyer et al. 1996] provide a detailed analysis of the performance of Grover' algorithm."
    • BOYER, M., BRASSARD, G., HOYER, P., AND TAPP, A. 1996. Tight bounds on quantum search. In Proceedings of the Workshop on Physics of Computation: PhysComp '96 (Los Alamitos, CA, 1996). Institute of Electrical and Electronic Engineers Computer Society Press. Preprint at Los Alamos Physics reprint Archive, http://xxx.lanl.gov/abs/quant-ph/9605034. => OK
  • "Quantum error correction must reconstruct the exact encoded quantum state. Given the impossibility of cloning or copying the quantum state, this reconstruction appears harder than in the classical case. However, it turns out that classical techniques can be modified to work for quantum systems."
  • "Decoherence, the distortion of the quantum state due to interaction with the environment, is a key problem."
  • "Colin Williams and Scott Clearwater's book "Explorations in QuantumComputing" [Williams and Clearwater 1998] comes with software, in the form of Mathematica notebooks, that simulates some quantum algorithms like Shor's algorithm" (This is a book not a paper)
    -------------------
    
  • "The state space of a quantum system, consisting of the positions, momentums, polarizations, spins, etc. of the various particles, is modelled by a Hilbert space of wave functions. We will not look at the details of these wave functions. For quantum computing we need only deal with finite quantum systems and it suffices to consider finite dimensional complex vector spaces with an inner product that are spanned by abstract wave functions such as |�¨>."
  • "Quantum state spaces and the tranformations acting on them can be described in terms of vectors and matrices or in the more compact bra/ket notation invented by Dirac in 1958."
  • "Kets like |x> denote column vectors and are typically used to describe quantum states."

• [C] I. Carneiro, M. Loo, X. Xu, M. Girerd, V Kendon, and P. L. Knight (2005) "Entanglement in coined quantum walks on regular graphs" New Journal of Physics Vol. 7, pp 156--185 (29 pages)
  
  • The author of "Finding Solutions to NP Problems: Philosophical Differences Between Quantum and Evolutionary Search Algorithms" claims the best tutorial among othres which were writtne by physisits.
  • "For an overview of the development of quantum walks for quantum computing, see the recent reviews by Kempe [6] and Ambainis [7]." [C6] Kempe J 2003 Contemp. Phys. 44 302.27 (Preprint quant-ph/0303081) -> not-yet found [C7] Ambainis A 2003 Int. J. Quantum Inform. 1 507 (Preprint quant-ph/0403120)
  • "Like classical random walks, quantum walks come in both discrete time [C12]--[C15] and continuous time [C16] versions." [C12] Y. Aharonov, L. Davidovich and N. Zagury (1993) "Quantum Random Walks. hys. Rev. A 48(2) pp. 1687--1690 => OK [C13] Watrous J 2001 J. Comp. System Sci. 62 376 (Preprint cs.CC/9812012) => OK [C14] Aharanov D., Ambainis A., Kempe J. and Vazirani U2001 Proc. 33rd Annual ACMSymp. on Theory of Computing (STOC 2001) (NewYork: Assoc. for Comp. Machinery) pp 50.9 (Preprint quant-ph/0012090) => OK [C15] Andris Ambainis, Eric Bach, Ashwin Nayak, Ashvin Vishwanath, and John Watrous (2001) "One-Dimensional Quantum Walks." In Proceedings of the Thirty-Third Annual ACM Symposium on the Theory of Computing, pages 37--49, 2001. => OK [C16] Farhi E and Gutmann S 1998 Phys. Rev. A 58 915 (Preprint quant-ph/9706062) => OK
  • "The discrete and continuous time versions of classical random walks can be related in a straightforward manner by taking the limit of the discrete walk as the size of the time step goes to zero. In the quantum case, the discrete and continuous time walks have different sized Hilbert spaces so there is no simple limit that relates the two basic formulations."
  • "There is also an example of a problem where the algorithmic powers of discrete and continuous time walks differ. Spatial search, where there is a cost associated with moving from one data element to another, can be accomplished faster with a discrete time quantum walk, but a continuous time quantum walk only performs as well for spatial dimensions greater than four [17]. A continuous time walk with extra degrees of freedom has also been formulated by Childs and Goldstone [18] that does correspond to the limit of the discrete time walk and can perform equally well on spatial search." [17] Childs A and Goldstone J 2004 Phys. Rev. A 70 022314 (Preprint quant-ph/0306054) => OK [18] Childs A M and Goldstone J 2004 Phys. Rev. A 70 042312 (Preprint quant-ph/0405120) => OK "Our work in this paper investigates the properties of coins in discrete quantum walks. We follow on from prior work on quantum coins by Mackay et al [19] and Tregenna et al [20], broadening the types of graphs studied. "The question of what is particularly quantum in a quantum walk is an interesting one which has attracted much attention [21].[23]." [19] Mackay T D, Bartlett S D, Stephenson L T and Sanders B C 2002 J. Phys. A: Math. Gen. 35 2745 (Preprint quant-ph/0108004) => OK [20] Tregenna B, Flanagan W, Maile R and Kendon V 2003 New J. Phys. 5 83 (Preprint quant-ph/0304204) => OK [21] Kendon V M and Sanders B C 2004 Phys. Rev. A 71 022307 (Preprint quant-ph/0404043) => OK [22] Knight P L, Roldan E and Sipe J E 2003 Phys. Rev. A 68 020301(R) (Preprint quant-ph/0304201) => OK [23] Knight P L, Roldan E and Sipe J E 2003 Opt. Commun. 227 147 (Preprint quant-ph/0305165) => OK
  • "we address this issue by investigating the evolution of the quantum mechanical entanglement as the quantum walk progresses."
  • "Since the range of higher-dimensional coin operators is too large for systematic numerical study, for the remainder of this paper we concentrate on two natural choices" --- Grover's and DFT coins. "Equation (1) represents the most general expression [24] for a unitary coin operator with two degrees of freedom." [24] Bach E, Coppersmith S, Goldschen M P, Joynt R andWatrous J 2004 J. Comput. Syst. Sci. 69 562.92
  • "The Grover operator was first introduced by Moore and Russell [25] in their study of quantumwalks on the hypercube." [25] Moore C and Russell A 2002 Proc. 6th Int. Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM '02) ED. J. D. P. Rolim and S Vadhan (Berlin: Springer) pp 164.78 (Preprint quant-ph/0104137)
  • "We studied the entanglement for the walk on the glued trees graph, but it did not provide useful indications of the progress of the walk, so we do not present any of these results here."
  • "The DFT coin operator is unbiased for any degree, so the spreading depends only on the relative phases, which can be controlled by the coin labelling."

Approaches to A-Needle-in-a-Haystack

• [D] Grover "Quantum Mechanics helps in searching for a needle in a haystack" (4 pages)
  • "Quantum mechanical systems can be in a superposition of states and simultaneously examine multiple names."
  • "See [D1] & [D3] for a more detailed introduction to quantum computers."

Search for a Needle in Conputer Science

• [D3] Lov K. Grover (1996) "A fast quantum mechanical algorithm for database search" Proceedings, STOC, pp. 212-219. (8 pages) --- An updated version of this paper can be found in a world-wide-web page.
  
  Not found a concret example of aneedle-in-a-haystack but found a next interesting phrase.
  • "quantum mechanical systems can simultaneously be in multiple Schrodinger cat states and carry out multiple tasks at the same time."

• [D5] M. Boyer, G. Brassard, P. Hoyer, and A. Tapp (1998) "Tight Bounds on Quantum Searching" Fortschritte der Physik, Vol. 46, No. 4-5, pp. 493--505 (17 pages) Strengths and weaknesses of quantum computing
  Authors briefly showed "three simple applications for Grover's algorithm" as (1) Database searching problem; (2) Cryptographic application; and (3) Boolean formula on n variables. "More precisely, you wish to find an integer i such that 0<=i
  

• [D9] G. Brassard (1997) "Searching a quantum phone book" Science, pp. 627-628. ...
  
  No concrete example of searching for needle except for criptography problem, either

Can GP simulate Quantum Computation?

• [E] L. Spector H. Barnum, H. J. Bernstein, and N. Swamy (1996) "Finding a Better-than-Classical Quantum AND/OR Algorithm using Genetic Programming" Proceedings, of the 1999 Conhgress on Evolutionary computation. (8 pages)
  • "For those new to quantum computing Steane provides a good overview [E7], Braunstein provides an accessible on-line tutorial [E8], Williams and Clearwater provide a text with a CD ROM containing Mathematica code for simulating quantum computers [E9], and Milburn provides an introduction for the general reader [E10]." [E7] A. Steane, .Quantum computing,. Reports on Progress in Physics, vol. 61, pp. 117.173, 1998, http://xxx.lanl.gov/abs/quant-ph/9708022. [E8] S. L. Braunstein, .Quantum computation: a tutorial, . Available only electronically, on-line at URL http ://chemphys.weizmann.ac.il/ ~schmuel/comp/comp.html, 1995. [E9] C. P.Williams and S. H. Clearwater, Explorations in Quantum Computing, Springer-Verlag, TELOS, 1997. [E10] G. J. Milburn, Schr�Nodinger�fs Machines: The Quantum Technology Reshaping Everyday Life, W. H. Freeman & Co., 1997.
  • "Because practical quantum computer hardware is not yet available, we must test the tness of evolved quantum algorithms using a quantum computer simulator that runs on conventional computer hardware. This entails an exponential slowdown, so we must be content to simulate relatively small systems."
  • "The basic unit of information in a quantum computer is a qubit, which is like a classical bit except that a qubit can exist in a superposition of states and can become entangled with other qubits.that is, its value can be linked to the values of other qubits in non-classical ways." "We will give a fuller treatment of the quantum mechanics of these algorithms in a future article." (Now we can check what has happened via google search for example.)

Quantum Random Walks

• [C6] J. Kempe (2003) "Quantum Random Walks -- An Introductory Overview' Contemporary Physics, Vol. 44 Issue 4 (also preprint quant-ph/0303081), pp. 307-327. (20 pages)
  • "We will give a thorough introduction to the necessary terminology without overburdening the reader with unnecessary mathematics."
  • "An excellent comprehensive introduction to quantum information and computation can be found in [1]." [1] M.A. Nielsen and I.L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, Cambridge, UK, 2000."
  • "This example - which might be thought of as a precursor to later models - is taken from the work of three physicists in 1993, Y. Aharonov, L. Davidovich and N. Zagury [5]. Their work for the first time coins the term �fquantum random walk�f."

• [C7] A. Ambainis "Quantum Walks and Their Algorithmic Applications" International Journal of Quantum Information, Vol 1 (also preprint quant-ph/0403120), 2003, pp. 507--518. (11 pages)
  • Author refer 4 papers as recent work regarding Quantum Walk Search as [C7-10] N. Shenvi, J. Kempe, K. Whaley. Quantum random-walk search algorithm, Physical Review A, 67:052307, 2003. Also quant-ph/0210064. [C7-11] A. Childs, J. Goldstone. Spatial search by quantum walk, quant-ph/0306054. [C7-12] A. Ambainis. Quantum walk algorithm for element distinctness. quant-ph/0311001. [C7-13] A. Ambainis, J. Kempe, A. Rivosh. Coins make quantum walks faster, quant-ph/0402107.
  • "there is a clever reduction to the walk on line [7]." [7] A. Childs, E. Farhi, S. Gutmann. An example of the difference between quantum and classical random walks. Journal of Quantum Information Processing, 1:35, 2002. Also quant-ph/0103020.
  • "Thus, we have a variant of continous quantum walk on line, with matrix H slightly different from one described in section 2.2."
    
    ----------
    
    The first algorithm of this type (searching the Boolean hypercube) was discovered by Shenvi et al. [10].

Quantum Walk Search

• [C7-10] N. Shenvi, J. Kempe, and B. Whaley (2003) "A Quantum Random Walk Search Algorithm" Physical Review A, Vol 67 pp. 052307--052318. (also preprint quant-ph/0210064). (13 pages)
  • "previous to a very recent paper by Childs et. al. [6], there had been no quantum algorithms based on the random walk model."
  • "Current research uses two distinct models for quantum random walks, based on either discrete time steps or on continuous time evolution. Discrete time quantum random walks were introduced as a possible new tool for quantum algorithms generalizing discrete classical Markov chains. ... In the continuous-time walk the adjacency matrix of the graph is used to construct a Hamiltonian which gives rise to a continuous time evolution."
  • "The discrete time random walk can be described by the repeated application of a unitary evolution operator U. This operator acts on a Hilbert space HCxHS ... where HC is the Hilbert space associated with a quantum coin and HS is the Hilbert space associated with the nodes of the graph."
  • "the coin is a quantum coin and can therefore exist in a superposition of sta"
  • "An important feature of the discrete time quantum random walk that has significance for its use in development of quantum algorithms, is that by virtue of its definition this walk will be efficiently implementable on a quantum computer whenever its classical counterpart is."
  • "We refer the reader to the recent papers [2], [3], [11] and [12] for some results obtained from discrete time quantum random walks." [2] D. Aharonov, A. Ambainis, J. Kempe, and U. Vazirani, in Proceedings of ACM Symposium on Theory of Computing (STOC) (ACM, New York, NY, 2001), pp. 50.59, LANL preprint quant-ph/0012090. [3] A. Ambainis, E. Back, A. Nayak, A. Vishwanath, and J. Watrous, in Proc. 33rd STOC (ACM, New York, NY, 2001), pp. 60.69. [11] C. Moore and A. Russell, Proc. RANDOM, to appear (2002), lanl-arXive quant-ph/0104137. [12] J. Kempe, quant-ph/0205083 (2002).
  • "Our random walk search algorithm will be based on a random walk on the n-cube, i.e. the hypercube of dimension n [11, 12]. The hypercube is a graph with N = 2n nodes, each of which can be labelled by an n-bit binary string."
  • "We define the search space of the algorithm to be the set of all n-bit binary strings, x = {0, 1}^n. We consider the function f(x) = {0,1}, such that f(x) = 1 for exactly one input x_target. Our goal is to find x_target."
  • "Each iteration in Grover's algorithm corresponds to a rotation in this subspace. In this paper, we have shown that the random walk search algorithm can also be viewed as a rotation in a two-dimensional subspace."
  • "The random walk search analyzed here was based on a discrete walk on the hypercube." "The probability distribution generated by running quantum walk for t steps and measuring it has been studied in more detail in refs. [5, 15, 16, 17, 18]." [5] A. Ambainis, E. Bach, A. Nayak, A. Vishwanath, and J. Watrous. One-dimensional quantum walks. Proceedings of STOC�f01, pp. 37-49. Proceedings of the thirty-third annual ACM symposium on Theory of computing table of contents Year of Publication: 2001 [15] A. Nayak, A. Vishvanath. Quantum walk on the line. quant-ph/0010117 [16] N. Konno. A New Type of Limit Theorems for the One-Dimensional Quantum Random Walk. quant-ph/0206103. [17] H. Carteret, M. Ismail, B. Richmond. Three routes to the exact asymptotics for the onedimensional quantum walk. Journal of Physics A, 36:8775-8795, 2003. Also quant-ph/0303105. [18] G. Grimmett, S. Janson, P. Scudo. Weak limits for quantum random walks. quant-ph/0309135
    
    

• [C7-11] A. M. Childs, and J. Goldstone "Spatial search by quantum walk" (12 pages)
  • "Suppose we had N items stored in a d-dimensional physical space, and that these items could be explored in superposition by a quantum computer making local moves (a 'quantum robot' [3])." [3] P. Benioff, Space searches with a quantum robot, quant-ph/0003006, in Quantum Computation and Information,eds. S. J. Lomonaco and H. E. Brandt (AMS, 2002). => OK 9 May
  • "Here we consider the continuous time quantum walk [5]. On certain graphs, this quantum walk can yield exponentially faster hitting times than its classical counterpart [5, 6]. Indeed, a recent result shows that the continuous time quantum walk can solve a certain black box problem exponentially faster than any classical algorithm [7]." [5] E. Farhi and S. Gutmann, Quantum computation and decision trees, quant-ph/9706062, Phys. Rev. A 58, 915 (1998). [6] A. M. Childs, E. Farhi, and S. Gutmann, An example of the difference between quantum and classical random walks, quant-ph/0103020, Quantum Information Processing 1, 35 (2002). => OK 9 May [7] A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, Exponential algorithmic speedup by quantum walk, quant-ph/0209131, Proc. 35th ACM Sym- posium on Theory of Computing, 59 (2003).
  • "The continuous time quantum walk on a graph takes place in an N-dimensional Hilbert space spanned by states |ji, where j is a vertex in G."
    
    

• [C7-11-3] P. Benioff (2002) "Space searches with a quantum robot" In Quantum Computation and Information, (eds.) S. J. Lomonaco and H. E. Brandt (AMS), also quant-ph/0003006. (13 pages)
  • "For this initial memory state all N^2 searches are carried out coherently. Since the path lengths range from 0 to 2^N, the quantum robot can search all sites of R and return to the origin in O(NlogN) steps. Since this is less than the number of steps, O(N^2logN), required by a classical robot, the question arises if Grover's algorithm can be used to process the final memory state to determine the location of s. If this is possible, the overall search and processing should require O(N logN) steps which is less than that required by a classical robot.

One-dimensional Quantum Random Walks cited by Shenvi et al. (2003) above.

• [C7-5] A. Ambainis, E. Bach, A. Nayak, A. Vishwanath, and J. Watrous (2001) "One-dimensional quantum walks." Proceedings of the 33rd annual ACM symposium on Theory of computing (STOC'01) pp. 37-49. (13 pages)
  • "In the classical case, it is wellknown that a random walk on a (two-way infinite) line has expected distance $\Theta(\sqrt t)$ from the origin at time t, and the probability of being at a distance $Omega(t)$ from the origin is exponentially small. In contrast, observation of a quantum particle doing a Hadamard walk on the line after t steps yields an expected distance $\Theta(t)$ from the origin. Moreover, the location of the particle is almost uniformly distributed over the interval $[-t/\sqrt 2, t/\sqrt 2]$, so that the quantum walk spreads quadratically faster than the classical random walk."
  • "Various quantum variants of random walks have previously been studied by a few authors [6, 12, 24, 32], but their results are, for the most part, unrelated to ours." --- [6] A. Childs, E. Farhi, S. Gutmann. An example of the difference between quantum and classical random walks. LANL preprint archive, quant-ph/0103020. [12] E. Farhi and S. Gutmann. Quantum computation and decision trees. Physical Review A, 58:915{928, 1998. [24] D. Meyer. From quantum cellular automata to quantum lattice gases. Journal of Statistical Physics, 85:551{574, 1996. Also available from the Los Alamos Preprint Archive, quant-ph/9604003. [32] J. Watrous. Quantum simulations of classical random walks and undirected graph connectivity. Journal of Computer and System Sciences, 62(2): 376-391, 2001.
  • "The (pure) quantum states of our systems may be identified with unit vectors in the Hilbert space $l_2(Z)\otimesl_2 (\Sigma)$, for which the set ${| n \in N, d \in \Sigma}$ forms an orthonormal basis. Each state |n>|d> is identified with the classical state (n,d)."
  • "It is yet unclear whether quantum walks are interesting from an algorithmic point of view. Any speed-up of a known classical algorithm based on random walks (such as those mentioned in Section 1) seems to involve the analysis of quantum walks on graphs much more complex than the line."
    -----
    
  • "To study the properties of quantum walks, we consider the wave function describing the position of the particle and analyze how it evolves with time. Let $\Psi(n,t) = (\psi_L (n,t), \psi_R (n,t))^T$ be the two component vector of amplitudes of the particle being at point n at time t, with the chirality being left (upper component) or right (lower component)."
    -----
    
  • "Similarly, let $P(n, t) = p_L(n, t) + p_R(n, t)$ be the probability of being at position n at time t."
    -----
    
    
    

• [C7-15] A. Nayak, A. Vishvanath. "Quantum walk on the line." quant-ph/0010117 (20 pages)
  • "As explained below (and also shown by [13]), it is still possible to construct a unitary walk if the particle has an extra degree of freedom that assists in its motion." [13] David A. Meyer. From quantum cellular automata to quantum lattice gases. Journal of Statistical Physics, 85:551.574, 1996. => OK (05/04)
  • "A walk on the line by such a particle may be described as follows. At every time step, its chirality undergoes a rotation (a unitary transformation in general) and then the particle moves according to its final chirality state."
  • "The problem of evaluating, or even approximating, path integrals to determine the time development of a wave function is well known to be notoriously hard. We circumvent this barrier by taking the Schrodinger approach, which takes advantage of the time and space homogeneity of the quantum walk."
  • "The Fourier transform of the wave function is thus easily analysed, and transformed back to the spatial domain. It is noteworthy that this technique is standard in the analysis of classical random walk [5]."
  • "Finally, we ask if it is possible to design quantum algorithms to generate certain desirable superpositions efficiently.those corresponding to distributions that are classically hard to sample from (much in the spirit of [15])." "We can calculate the probability of observing the particle doing the quantum walk at any given point $n = \alpha t$ from the wave function derived above. Below we give the asymptotic distribution for points $\alpha = n/t$ between $-1/\sqrt{2} + \epsilon$ and $-1/\sqrt{2} - \epsilon$ for an arbitrarily small constant $\epsilon> 0$."
    
    

• [C7-16] N. Konno. "A New Type of Limit Theorems for the One-Dimensional Quantum Random Walk." quant-ph/0206103. (14 pages)
  
  

• [C7-17] H. Carteret, M. Ismail, B. Richmond. Three routes to the exact asymptotics for the onedimensional quantum walk. Journal of Physics A, 36:8775-8795, 2003. Also quant-ph/0303105. (26 pages)
  • "Meyer therefore considered the wave function as a two component vector of amplitudes of the particle being at point n at time t."
  • "The first authors to discuss the quantum random walk were Y. Aharonov, Davidovich and Zagury, in [2] where they described a very simple realization of the quantum random walk in quantum optics." [2] Y. Aharonov, L. Davidovich, and N. Zagury, Quantum random walks, Phys. Rev. A 48 (1993), 1687.
  • "We refer to the paper by Ambainis, Bach, Nayak, Vishwanath and Watrous [3] for proper definitions and references." [3] A. Ambainis, E. Bach, A. Nayak, A. Vishwanath, and J. Watrous, One-Dimensional Quantum Walks, Proceedings of ACM Symposium on Theory of Computation (STOC�f01), July 2001, Association for Computing Machinery, New York, 2001, pp. 37.49.
    
    

• [C7-18] G. Grimmett, S. Janson, P. Scudo "Weak limits for quantum random walks." quant-ph/0309135 (9 pages)

Yet other citation by Shenvi et al. (2003) above.

• [C7-12] A. Ambainis "Quantum walk algorithm for element distinctness" (33 pages)

• [C7-13] A. Ambainis, and J. Kempe "Coins Make Quantum Walks Faster." (25 pages)