Back to search

University of Waterloo

Quantum Query Complexity of Hypergraph Search Problems

Abstract

dc:description.abstract

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.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Yu, Zhiying
Advisor dc:contributor.advisor
  • Ben-David, Shalev

Subjects

dc:subject × 7

Rights

Language dc:language.iso
en

Identifiers

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

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

Yu, Zhiying. Quantum Query Complexity of Hypergraph Search Problems. University of Waterloo, 2024. http://hdl.handle.net/10012/20712