Abstract
dc:description.abstractIt is well known that certain search problems are efficiently solved by quantum walk algorithms. Of particular interest are those problems whose efficient solutions involve nesting of search algorithms. The nesting of search algorithms generally incurs an extra logarithmic factor in query and time complexity, due to the use of majority voting as an error reduction technique. We study whether composition of search algorithms can be achieved without the said logarithmic factor in complexity. Two methods of composition have been proposed in this thesis. The first is a slight simplification of the quantum walk algorithm due to Magniez, Nayak, Roland, and Santha. The second is a method for composition of Markov chains. Neither approach appear to be generally applicable to all cases of quantum walk composition. Further work is required to determine the circumstances under which these approaches provide the logarithmic factor of increase in efficiency that we desire.
Degree
thesis:*- Grantor dc:publisher
- University of Waterloo
- Year dc:date.issued
- 2017
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Lou, Xingliang
- Advisor dc:contributor.advisor
-
- Nayak, Ashwin
Subjects
dc:subject × 3Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/10012/11231