A Search by Quantum Computation --- Good Introductions to Quantum Computation to Start with

• [A] G. W. Greenwood "Finding Solutions to NP Problems: Philosophical Differences Between Quantum and Evolutionary Search Algorithms" (8 pages)
  
  • "Besides, because no one has ever built a quantum computer, there is no way any direct comparison can be made at this time. It is up to the reader to decide which approach holds the most promise."
  • "Almost twenty years ago Richard Feynman observed that classical computers could not simulate certain quantum mechanical effects such as entanglement [3]."
    ------------------- 2nd time -------------------
    
  • "Classical computer systems represent a single bit of information deterministically: the value is either a logic 0 or a logic 1. Quantum computer systems represent a single bit of information as a qubit, which is a unit vector in a complex Hilbert space." (P. Dirac. The Principles of Quantum Mechanics. Oxford University Press, 4th edition, 1958.)
  • "The ideas are commonly expressed using the bra/ket notation introduced by Dirac [5]. The ket symbol is denoted by |x> and the corresponding bra is denoted by
  • "In computer science domains the ket (bra) can be thought of as a column (row) vector. That is, the orthonormal basis {0>, |1>} can be expressed as {(1,0)^T, (0,1_^T)} Any complex linear combination of two kets is also a ket. The inner product of two vectors is denoted by Note that since |0> and |1> are orthonormal, <0|1>=0 |x>

• [B] E. Rieffel and W. Polak (2000) "An Introduction to Quantum Computing for Non-Physicists" Los Alamos Physics preprint archive, http://xxx.lanl.gov/abs/quantph/ 9809016. (45 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.
  • "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)
    ------------------- 2nd time -------------------
    
  • "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."
    ------------------- 3rd time -------------------
    
  • "Even though a quantum bit can be put in infinitely many superposition states, it is only possible to extract a single classical bit�fs worth of information from a single quantum bit. The reason that no more information can be gained from a qubit than in a classical bit is that information can only be obtained by measurement. When a qubit is measured, the measurement changes the state to one of the basis states"
  • "Furthermore, quantum states cannot be cloned so it is not possible to measure a qubit in two ways, even indirectly by, say, copying the qubit and measuring the copy in a different basis from the original."

• [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."
  • "(like simulated annealing). instead of having the system in a specified state, it is in a distribution over various states with a certain probability of being in each state."

• [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

Quantum Comuptatin with photons --- to get a more clear image of quantum computation

• P. G. KWIAR, J. R. Mitchell, P. D. D. Schwindt and A. G. White (2000) "Grover's search algorithm: an optical approach." Journal of Modern Optics (10 pages)
  
  • "We present a simple all-optical implementation of Grover's algorithm for efficient searching, in which a database of four elements is searched with a single query."
    
    

• N. J. Cerf, C. Adami, and P. G. Kwiat (1998) "Optical simulation of quantum logic." Physical Review A, Vol. 57, No. 3 (4 pages)
  
  

• K. A. Brickman, P. C. Haljan, P. J. Lee, M. Acton, L. Deslauriers, and C. Monroe "Implementation of Grover's quantum search algorithm in a scalable system." Physical Review A 72, 050306(R) (2005) (4 pages)
  
  • "We report the implementation of Grover�fs quantum search algorithm in the scalable system of trapped atomic ion quantum bits. Any one of four possible states of a two-qubit memory is marked, and following a single query of the search space, the marked element is successfully recovered with an average probability of 60%."
  • "A common analogy ... N entries in the phonebook, this requires on the order of N queries. However, if the correlation between name and phone number is encoded with quantum bits, the name can be found after only about $\sqrt{N}$ queries."
  • "We implement the Grover search algorithm over a space of N=4 elements using two trapped atomic ion qubits. Grover's algorithm has been implemented with ensembles of molecules using nuclear magnetic resonance, with states of light using linear optical techniques, and with Rydberg states within individual atoms. None of these systems are scalable, however, as they require exponential resources as the number of qubits grows."
  • "At the heart of Grover's algorithm is the "oracle query," which quickly checks if a proposed input "x" is a solution to the search problem."
  • "The oracle marks a particular component of a quantum superposition by flipping the sign of its amplitude. Following the oracle, a number of quantum operations amplify the weighting of the marked state independent of which state is marked."
  • === Figure 1 best explains than I have ever seen in the litterature so far. ===
  • "The evolution of the four basis states is given by the following:"
    
    |0>|0> => |0>|0> - i|1>|1>
    |1>|1> => |1>|1> - i|0>|0>
    |0>|1> => |0>|1> - i|1>|0>
    |1>|0> => |1>|0> - i|0>|1>
  • "The classical counterpart is a simple shell game: suppose a marble is hidden under one of four shells, and after a single query the location of the marble is guessed. Under these conditions, the best classical approach gives an average probability of success (1/4)+(3/4)(1/3)=0.5, because 1/4 of the time the query will give the correct location of the marble while 3/4 of the time a guess must be made among the three remaining choices each with 1/3 probability of choosing the correct location."
    
    

• Arvind, Gurpreet Kaur, Geetu Narang "Optical implementations, oracle equivalence, and the Bernstein-Vazirani algorithm." (5 pages)
  
  • "The Bernstein-Vazirani algorithm (with a suitably modified oracle), wherein a hidden n bit vector is discovered by one oracle query as against n oracle queries required classically, belongs to this category."

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 H_CxH_S ... where H_C is the Hilbert space associated with a quantum coin and H_S 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 states."
  • "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 Symposium 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 |j>, 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)