{"id":"arxiv/2605.09017","url":"https://arxiv.org/abs/2605.09017","tags":["quant-ph","cs.CC"],"score":0,"title":"Quantum algorithms for path and cycle containment problems","domain":"quant-ph","source":"arxiv","authors":["Arjan Cornelissen","Amin Shiraz Gilani","Subhasree Patro"],"reviews":0,"subject":"quant-ph","summary":"The quantum query complexity of subgraph-containment problems, which ask whether a given subgraph $H$ is present in an input graph $G$, has been the subject of considerable study. However, even for relatively simple subgraphs, such as paths and cycles, a complete understanding of their query complexities remains elusive. In this work, we consider several variants of path- and cycle-containment problems in the adjacency matrix model, where we search for paths or cycles of constant length $k$. We compare the settings where the graphs are directed or undirected, where the goal is to detect or…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-05-09","reactions":{}}