Decoherence in Search Algorithms
arXiv:0912.1523
Abstract
Recently several quantum search algorithms based on quantum walks were proposed. Those algorithms differ from Grover's algorithm in many aspects. The goal is to find a marked vertex in a graph faster than classical algorithms. Since the implementation of those new algorithms in quantum computers or in other quantum devices is error-prone, it is important to analyze their robustness under decoherence. In this work we analyze the impact of decoherence on quantum search algorithms implemented on two-dimensional grids and on hypercubes.
14 pages, presented at 36th Seminar on Software and Hardware (SEMISH), XXIX Brazilian Computer Society Congress, Bento Concalves, Brazil
References in corpus (7)
- A Quantum Random Walk Search Algorithm
- Decoherence can be useful in quantum walks
- Faster quantum walk algorithm for the two dimensional spatial search
- Decoherence in the quantum walk on the line
- Effects of Noisy Oracle on Search Algorithm Complexity
- Decoherence in Quantum Walks on the Hypercube
- Mixing Times in Quantum Walks on the Hypercube