Please note: This master’s thesis presentation will take place online.
Zhiying Yu, Master’s candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Shalev Ben-David
In the study of quantum query complexity, it is natural to study the problems of finding triangles and spanning trees in a simple graph. We can generalize these problems to detecting certain properties of higher-ranked hypergraphs and ask whether similar upper and lower quantum query bounds still hold. This thesis presents a broad investigation of the quantum query complexities for natural hypergraph finding problems. It also shows the difficulties we face when applying the usual complexity-bounding techniques for hypergraphs. This research contributes to our understanding of the capability of quantum algorithms and opens up a class of interesting new problems.
Over the past decades, many techniques have been developed for finding, or at least, for closing these complexity bounds. For upper bounds, learning graphs can used to construct nontrivial quantum query algorithms. For part of the thesis, we use learning graphs to build a nested quantum walk framework. This framework can be used to find nontrivial learning graph algorithms for the 3-simplex and 4-simplex finding problems without having to drown in the hassle of technicality. However, as the rank increases, these upper bounds may be closer to trivial and are difficult to generalize. For lower bounds, we focused on using the generalized adversary method and the randomized reduction. Using existing techniques, we present a nontrivial quantum query lower bound of the 3-simplex sum problem and a tight quantum query bound for the connectivity and acyclicity problems over r-uniform hypergraphs.