Institute of Information Science, Academia Sinica

The edge list model is arguably the simplest input model for graphs, where the graph is specified by a list of its edges. In this model, we study the quantum query complexity of three variants of the triangle finding problem. The first asks whether there exists a triangle containing a target edge and raises general questions about the hiding of a problem’s input among irrelevant data. The second asks whether there exists a triangle containing a target vertex and raises general questions about the shuffling of a problem’s input. The third asks whether there exists a triangle; this problem bridges the 3-distinctness and 3-sum problems, which have been extensively studied by both cryptographers and complexity theorists. We provide tight or nearly tight results for these problems as well as some first answers to the general questions they raise. Furthermore, given a graph with low maximum degree, such as a random sparse graph, we prove that the quantum query complexity of finding a length-k cycle in its length-m edge list is m3/4−1/(2k+2−4)±o(1). We prove the lower bound in Zhandry’s recording query framework [Zha19] as generalized by Hamoudi and Magniez [HM23], and the upper bound by adapting Belovs’s learning graph algorithm for k-distinctness [Bel12b].