Discrete quantum walks hit exponentially faster (Q2571012)

It is well-known that a simple random walk on the \(n\)-bit hypercube \(\{0,1\}^ n\) needs an exponential expected time until it hits the corner opposite to its initial corner for the first time. The paper contrasts this to the discrete quantum walk on the hypercube, which needs only a polynomial time for this. This result may be seen as one of the first rigorous examples of a process that takes much shorter time on a quantum computer than on a classical computer. The notion of a discrete quantum walk is motivated and introduced, and two alternate definitions of the hitting time for such a walk are given. An application to sequential packet routing is provided as well.