Back to search

University of Waterloo

Efficient Composition of Discrete Time Quantum Walks

Abstract

dc:description.abstract

It 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 × 3

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/11231

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Lou, Xingliang. Efficient Composition of Discrete Time Quantum Walks. University of Waterloo, 2017. http://hdl.handle.net/10012/11231