2026-09-10T09:45:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27789 2026-09-09T12:19:39Z ddc:004 open_access

Quantum Algorithms for Path and Cycle Containment Problems Cornelissen, Arjan Gilani, Amin Shiraz Patro, Subhasree Quantum algorithms query complexity graph problems fine-grained reductions 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. This interest stems not only from the natural and well-motivated formulation of these problems, but also from a flurry of novel quantum algorithmic techniques that were developed specifically to solve them. Notably, 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 ∈ O(1). We compare the settings where the graphs are directed or undirected, where the goal is to detect or find the existence of a path/cycle, and where the path/cycle we're looking for has length exactly k, or at most k. We also consider several promise versions of these problems, where we know beforehand that the input graph has a certain structure. We characterize the relative difficulty of these variants of the path- and cycle-containment problems, by relating them to one another using randomized reductions, and grouping them into several equivalence classes. When we restrict our attention to path-containment problems, this implies a dichotomy result. Some of the path-containment problems can be solved using a linear number of queries, and all the others are equivalent to one another (and additionally to several cycle-containment problems as well) under randomized reductions and up to constant multiplicative overhead. For the latter equivalence class, we prove a novel quantum-walk-based algorithm that achieves query complexity Õ(n^{3/2-α_k}), where α_k ∈ Θ(c^{-k}) and c = √{3+√17}/2 ≈ 1.33, beating the previous best upper bound O(n^{3/2}) on its query complexity. We also provide a conditional lower bound based on the graph-collision problem, which implies that this equivalence class does not admit linear-query quantum algorithms unless graph collision admits an O(√n) query algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arjan Cornelissen and Amin Shiraz Gilani and Subhasree Patro 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.72 urn:nbn:de:0030-drops-277892 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.72 eng https://creativecommons.org/licenses/by/4.0/legalcode