Quantum Random Walks Hit Exponentially Faster

Julia Kempe

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 q…