<?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-22T07:44:06Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/20712" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/20712</identifier><datestamp>2025-03-26T23:32:30Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9930</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">Ben-David, Shalev</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="1d1e46f2-f132-493d-b0e8-efe076df74e9" confidence="600">Yu, Zhiying</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2024-07-09T14:47:40Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2024-07-09T14:47:40Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2024-07-09</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2024-07-03</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/20712</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">In the study of quantum query complexity, it is natural to study the problems of finding triangles and spanning trees in a simple graph. Over the past decades, many techniques are developed for finding the upper and lower quantum query bounds of these graph problems. We can generalize these problems to detecting certain properties of higher rank hypergraphs and ask whether these techniques are still available. In this thesis, we will see that when the rank increase, complexity bounds still holds for some problems, although less effectively. For some other problems, their nontrivial complexity bounds vanish. Moreover, we will focused on using the generalized adversary and learning graph techniques for finding nontrivial quantum query bounds for different hypergraph search problems. The following results are presented.

• Discover a general quantum query lower bound for subhypergraph-closed properties and monotone properties over r-partite r-uniform hypergraphs.
• Provide tight quantum query bounds for the connectivity and acyclicity problems over r-uniform hypergraphs.
• Present a nontrivial learning graph algorithm for the 3-simplex finding problem.
• Formulate nested quantum walk in the adaptive learning context and use it to present a nontrivial quantum query algorithm for the 4-simplex finding problem.
• Present a natural relationship of lower bounds for simplex finding of different ranks.
• Use the learning graph formalization of tetrahedron certificate structure to find a nontrivial quantum query lower bound of the 3-simplex sum problem.</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 complexity theory</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">quantum information theory</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">randomized algorithm</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">quantum walk</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">learning graph</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">data structure and algorithm</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">graph theory</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Quantum Query Complexity of Hypergraph Search Problems</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">David R. Cheriton School of Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="discipline" lang="en">Computer Science</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-etd" element="embargo" qualifier="terms" lang="en">0</dim:field>
   <dim:field mdschema="uws" element="contributor" qualifier="advisor">Ben-David, Shalev</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>