We identify a key difference between quantum search by discrete- andcontinuous-time quantum walks: a discrete-time walk typically performs one walkstep per oracle query, whereas a continuous-time walk can effectively performmultiple walk steps per query while only counting query time. As a result, weshow that continuous-time quantum walks can outperform their discrete-timecounterparts, even though both achieve quadratic speedups over theircorresponding classical random walks. To provide greater equity, we allow thediscrete-time quantum walk to also take multiple walk steps per oracle querywhile only counting queries. Then it matches the continuous-time algorithm'sruntime, but such that it is a cubic speedup over its corresponding classicalrandom walk. This yields the first example of a greater-than-quadratic speedupfor quantum search over its corresponding classical random walk.
展开▼
