Quantum random walks - an introductory overview <s> The hypercube <s> Recently, it has been shown that one-dimensional quantum walks can mix more quickly than classical random walks, suggesting that quantum Monte Carlo algorithms can outperform their classical counterparts. We study two quantum walks on the n-dimensional hypercube, one in discrete time and one in continuous time. In both cases we show that the quantum walk mixes in (\pi/4)n steps, faster than the O(n log n) steps required by the classical walk. In the continuous-time case, the probability distribution is {\em exactly} uniform at this time. More importantly, these walks expose several subtleties in the definition of mixing time for quantum walks. Even though the continuous-time walk has an O(n) instantaneous mixing time at which it is precisely uniform, it never approaches the uniform distribution when the stopping time is chosen randomly as in [AharonovAKV2001]. Our analysis treats interference between terms of different phase more carefully than is necessary for the walk on the cycle; previous general bounds predict an exponential, rather than linear, mixing time for the hypercube. <s> BIB001 </s> Quantum random walks - an introductory overview <s> The hypercube <s> We show that the hitting time of the discrete time quantum random walk on the n-bit hypercube from one corner to its opposite is polynomial in n. This gives the first exponential quantum-classical gap in the hitting time of discrete quantum random walks. We provide the framework for quantum hitting time and give two alternative definitions to set the ground for its study on general graphs. We then give an application to random routing. <s> BIB002 </s> Quantum random walks - an introductory overview <s> The hypercube <s> We construct a black box graph traversal problem that can be solved exponentially faster on a quantum computer than on a classical computer. The quantum algorithm is based on a continuous time quantum walk, and thus employs a different technique from previous quantum algorithms based on quantum Fourier transforms. We show how to implement the quantum walk efficiently in our black box setting. We then show how this quantum walk solves our problem by rapidly traversing a graph. Finally, we prove that no classical algorithm can solve the problem in subexponential time. <s> BIB003
It is possible to calculate the eigenspectrum of several matrices U corresponding to a random walk on a graph with some coin C. Moore and Russell BIB001 analysed the mixing time of the walk on the hypercube (see Sec. III) along the lines of the previous paragraph, both in the discrete time case as well as in the continuous one. Their results for the mixing time are not very encouraging, though. The hypercube is one of the graphs that mixes fast to the uniform distribution in the classical case already (it belongs to a class of so called expander graphs which all share this property), namely The discrete time quantum walk turns out to do worse: Its mixing time M ǫ is at least d 3/2 /ǫ. Even more dramatically the continuous time quantum walk on the hypercube does not converge to the uniform distribution at all. We have mentioned another quantity of crucial interest in the study of random walks -the expected hitting time. We have shown the importance of fast hitting to solve some algorithmic problems in Sec. IV. Furthermore it is here that we may hope to achieve great quantum advantage: the classical random walk on the hypercube takes exponential time to hit its opposite corner. In the quantum world the notion of hitting can be made precise in several ways (see BIB002 for a systematic approach). In order to know whether a walk hits a certain point measurements need to be made, yet we do not wish to measure the position of the walk completely to not kill its quantum coherences and make it classical. In BIB002 two ways to define hitting time are presented: either we can wait for a certain time T (which we somehow determine in advance) and then measure the walk. If the probability to be in the node of interest is close to 1 we can call T a hitting time. To circumvent the problem of knowing T in advance we can alternatively use a definition similar to the absorbing wall described in Sec. III. At each step a measurement is performed which only determines if the walk is in the node of interest or not (M b in Eq. (18) of Sec. III). If it is found there the walk is stopped. We will call T a hitting time if the walk has stopped before time T with high probability. In the classical case all these notions of hitting time from one corner of the hypercube to its opposite are exponential in d. Kempe BIB002 shows that the quantum discrete time walk indeed behaves crucially different: The expected hitting time (both notions) from a corner to its opposite turns out to be polynomial in the dimension d! This is an exponential separation of the classical and quantum behavior, similar to what we have seen on the graph G n for the continuous time quantum walk (Sec. III B) [72] . It rests to see how this speed-up can be harnessed algorithmically. The modified graph of Fig. 11 . A big random cycle has been inserted between the two binary trees. This makes the classical task of penetrating the graph from root to root exponentially hard BIB003 .