您的瀏覽器不支援JavaScript語法,網站的部份功能在JavaScript沒有啟用的狀態下無法正常使用。

中央研究院 資訊科學研究所

活動訊息

友善列印

列印可使用瀏覽器提供的(Ctrl+P)功能

學術演講

:::

Hiding, Shuffling, and Cycle Finding: Quantum Algorithms on Edge Lists

  • 講者Amin Shiraz Gilani 先生 (美國馬里蘭大學)
    邀請人:鐘楷閔
  • 時間2025-07-10 (Thu.) 10:15 ~ 12:15
  • 地點資訊所新館101演講廳
摘要
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].