Removing Measurements From Quantum Walks

Amer Physical Soc
Publication Type:
Journal Article
Physical Review A, 2013, 87 (1), pp. 1 - 9
Issue Date:
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2012004094OK.pdf1.29 MB
Adobe PDF
Quantum walks are very useful tools in designing quantum algorithms. Amplitude amplification is a key technique to increase the success probability of a quantum-walk-based algorithm, and it is quadratically faster than classical probabilistic amplification. However, amplitude amplification only applies to quantum walks with one-shot hitting time, where no measurements except a final one are performed, and not to quantum walks with concurrent hitting time, where measurements happen or absorbing boundaries exist at each step. In this paper, we propose a procedure to modify quantum walks with concurrent hitting time by removing measurements from them. This procedure enables us to use amplitude amplification to design algorithms based on the modified quantum walks which are faster than those based on the original walks with a concurrent hitting time and more robust than those based on the corresponding walks with a one-shot hitting time.
Please use this identifier to cite or link to this item: