<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T19:57:17Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/11231" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/11231</identifier><datestamp>2025-03-26T23:37:05Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9928</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="advisor">Nayak, Ashwin</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="9b90629b-a91f-4566-b0d6-e0874fed563c" confidence="600">Lou, Xingliang</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2017-01-20T17:00:48Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2017-01-20T17:00:48Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2017-01-20</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2017-01-18</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/11231</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">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.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">quantum walk</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">discrete time quantum walk</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">quantum algorithm</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Efficient Composition of Discrete Time Quantum Walks</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Master Thesis</dim:field>
   <dim:field mdschema="dc" element="pending">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">Combinatorics and Optimization</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="discipline" lang="en">Combinatorics and Optimization (Quantum Information)</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="grantor" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Master of Mathematics</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Nayak, Ashwin</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="affiliation1" lang="en">Faculty of Mathematics</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="city" lang="en">Waterloo</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="country" lang="en">Canada</dim:field>
   <dim:field mdschema="uws" element="published" qualifier="province" lang="en">Ontario</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>