Quantum Walks and Quantum Resetting
A dissertation submitted for the partial fulfilment of BS-MS dual degree in Science
While quantum walks are faster than their classical counterparts in searching a node, the transient nature of quantum walks leads to a non-zero failure rate. By classically resetting the walk, it has been shown that the walk can be made recurrent, and thus the asymptotic failure rate goes to 0 without sacrificing the quantum speedup. In this work, we attempt to define a quantum resetting mechanism, and probe its effect on the mean hit time of the walk. Such a protocol is necessary for many quantum algorithms, where classical resetting may not be possible. We define two resetting protocols, a non-unitary quantum reset motivated by the coined walk formalism, and a unitary reset via the Szegedy walk.
First we propose a controlled reset-evolve operation, drawing inspiration from the coined quantum walk formalism. We show computationally, that for a range of parameters, there is no apparent speed up gained by this protocol. Furthermore, an additional coin and non-unitary operation set renders the protocol difficult to analyse. Thus, we require a quantum reset mechanism which remains unitary. This brings us to our second resetting proposal based on Szegedy walks. We can quantise the stochastic reset classical walk, thereby achieving a unitary quantum reset protocol. We further show computationally that a speedup for the Grover-like search protocol is achieved by the unitary reset walk for a range of parameters. Finally, we also use eigenvalue analysis to analyse the space and time complexity of protocol, and show a clear advantage in running the protocol.
