  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.
