pith. sign in

arxiv: 2605.09017 · v1 · submitted 2026-05-09 · 🪐 quant-ph · cs.CC

Quantum algorithms for path and cycle containment problems

Arjan Cornelissen , Amin Shiraz Gilani , Subhasree Patro This is my paper

Pith reviewed 2026-05-12 02:15 UTC · model grok-4.3

classification 🪐 quant-ph cs.CC
keywords problemsquerypathcomplexitycyclecycle-containmentequivalencegraph
0
0 comments X

The pith

A dichotomy for path-containment problems shows some are solvable with linear queries while others are equivalent to cycle problems and admit a quantum-walk algorithm with query complexity Õ(n^{3/2 - α_k}) where α_k decays exponentially in k, plus a conditional lower bound.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Quantum query complexity counts how many times a quantum algorithm must inspect entries of the input graph's adjacency matrix to answer a question. The authors study several versions of the problem of finding a path or cycle of length exactly k or at most k, in directed or undirected graphs, with or without promises on the input. Using randomized reductions they prove that many of these variants have essentially the same complexity. For path problems they obtain a clean split: some versions need only a linear number of queries while the remaining ones collapse into a single equivalence class that also contains several cycle problems. For this hard class they construct a quantum-walk algorithm whose query cost is Õ(n^{3/2 - α_k}) with α_k roughly (1.33)^{-k}. This beats the previous O(n^{3/2}) bound by a factor that grows with k. They also prove that no linear-query quantum algorithm exists for the hard class unless the graph-collision problem itself admits an O(√n)-query algorithm.

Core claim

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}).

Load-bearing premise

The randomized reductions between problem variants preserve quantum query complexity up to constant factors; if this fails for any of the listed variants, the claimed equivalence classes and the transfer of the new upper bound would collapse.

Figures

Figures reproduced from arXiv: 2605.09017 by Amin Shiraz Gilani, Arjan Cornelissen, Subhasree Patro.

Figure 1
Figure 1. Figure 1: Randomized reductions between problems for [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: A layered graph (left) and a layered cycle graph (right). These can be obtained from general [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Randomized reductions between path-containment problems. All the green problems can be [PITH_FULL_IMAGE:figures/full_fig_p016_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Pictorial representation of the randomized reductions we prove in this section, for [PITH_FULL_IMAGE:figures/full_fig_p020_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The layered-path problem. Every set Vj for j ∈ [k − 1] represents a set of Θ(n) vertices, and the first and last layer might have a different size, say |V0| = |Vk| = r. We are looking for a directed path that traverses all the layers from V0 to Vk. Lemma 4.2. Let k, n, r ∈ N, with 3 ≤ k ∈ O(1) and r ≤ n. Let n/2 ≥ s ∈ N, and suppose that we can solve the layered path-finding problem with length k − 2 and f… view at source ↗
Figure 6
Figure 6. Figure 6: The best-known upper bounds on the query complexity of the [PITH_FULL_IMAGE:figures/full_fig_p034_6.png] view at source ↗
read the original abstract

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 find the existence of a path/cycle, and where the path/cycle we are looking for has length exactly $k$, or at most $k$. We also consider several promise versions of these problems, where we suppose that the input graph has a certain structure. We characterize the relative difficulty of these variants of the path/cycle-containment problems, by relating them to one another using randomized reductions, and grouping them into equivalence classes. When we restrict our attention to path-containment problems, we get 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) under randomized reductions, up to constant overhead. For the latter equivalence class, we prove a novel quantum-walk-based algorithm that achieves query complexity $\widetilde{O}(n^{3/2-\alpha_k})$, where $\alpha_k \in \Theta(c^{-k})$ and $c = \sqrt{3+\sqrt{17}}/2 \approx 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(\sqrt{n})$ query algorithm.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript classifies quantum query complexities for path- and cycle-containment problems of constant length k in the adjacency-matrix model. Randomized reductions are used to group variants into equivalence classes, yielding a dichotomy for path problems (some linear-query solvable, others equivalent to each other and to certain cycle problems). For the non-trivial class, a new quantum-walk algorithm is given with query complexity Õ(n^{3/2-α_k}) where α_k ∈ Θ(c^{-k}) and c = √(3+√17)/2 ≈ 1.33, improving on the prior O(n^{3/2}) bound; a conditional lower bound is also derived from the graph-collision problem.

Significance. If the reductions and algorithm hold, the work meaningfully advances quantum query complexity for subgraph problems by supplying both an explicit improved upper bound via quantum walks and a structural dichotomy via reductions. The exponential-in-k improvement in the exponent for fixed k and the conditional lower bound are concrete contributions that help map the complexity landscape.

major comments (2)
  1. [Section 3] Section 3 (Randomized Reductions and Equivalence Classes): The assertion that randomized reductions preserve quantum query complexity up to constant factors is load-bearing for the equivalence classes and for transferring the Õ(n^{3/2-α_k}) upper bound to all members of the class. The manuscript must supply explicit bounds on error-probability amplification, the number of oracle calls in the reduction, and the overhead of simulating the adjacency-matrix oracle on the reduced instances; without these, the claimed constant-factor equivalence cannot be verified.
  2. [Section 4] Section 4 (Quantum Walk Algorithm): The derivation of the exponent α_k ∈ Θ(c^{-k}) with the specific constant c = √(3+√17)/2 is central to the claimed improvement over O(n^{3/2}). The recurrence or closed-form analysis that produces this exponent (and confirms it is strictly positive for each fixed k) should be stated with all intermediate steps so that the query-complexity bound can be checked independently.
minor comments (2)
  1. [Abstract] The abstract lists promise versions without enumerating them; a one-sentence clarification of the promise assumptions would improve readability.
  2. [Notation] Notation for the Õ symbol and the precise definition of α_k should be repeated at the first use in the main text for consistency.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their insightful comments on our manuscript. We address the two major comments below and will incorporate the necessary clarifications and details in the revised version.

read point-by-point responses

  1. Referee: [Section 3] Section 3 (Randomized Reductions and Equivalence Classes): The assertion that randomized reductions preserve quantum query complexity up to constant factors is load-bearing for the equivalence classes and for transferring the Õ(n^{3/2-α_k}) upper bound to all members of the class. The manuscript must supply explicit bounds on error-probability amplification, the number of oracle calls in the reduction, and the overhead of simulating the adjacency-matrix oracle on the reduced instances; without these, the claimed constant-factor equivalence cannot be verified.

    Authors: We agree that explicit bounds are required to rigorously establish constant-factor preservation of quantum query complexity. In the revised manuscript we will add a dedicated paragraph (or short appendix) that (i) specifies the error-amplification procedure, showing that O(1) independent repetitions suffice to boost success probability to 2/3 while incurring only constant overhead, (ii) bounds the number of reduction oracle calls by a k-dependent constant, and (iii) proves that each adjacency-matrix query on the reduced instance is simulated by at most a constant number of original-oracle calls. These additions will confirm the claimed equivalence classes. revision: yes

  2. Referee: [Section 4] Section 4 (Quantum Walk Algorithm): The derivation of the exponent α_k ∈ Θ(c^{-k}) with the specific constant c = √(3+√17)/2 is central to the claimed improvement over O(n^{3/2}). The recurrence or closed-form analysis that produces this exponent (and confirms it is strictly positive for each fixed k) should be stated with all intermediate steps so that the query-complexity bound can be checked independently.

    Authors: We thank the referee for this observation. The exponent α_k is obtained from the spectral analysis of a quantum walk on the Johnson graph whose marked set encodes paths of length k. In the revision we will expand the relevant subsection to include the full derivation: we first recall the general quantum-walk query bound, then derive the recurrence relating the improvement factor at step k to the eigenvalue gap and marked-set density at step k-1, solve the resulting linear recurrence to obtain the closed form α_k = Θ(c^{-k}) with the stated constant c, and verify that α_k > 0 for every finite k. All algebraic steps will be shown explicitly. revision: yes

Circularity Check

0 steps flagged

No significant circularity; upper bound from explicit new algorithm, reductions are external assumptions

full rationale

The paper derives its main upper bound Õ(n^{3/2-α_k}) from an explicit quantum-walk algorithm constructed in the adjacency-matrix model, with α_k obtained from the analysis of the walk's hitting time or eigenvalue gap rather than any fitted parameter or self-referential definition. Equivalence classes among problem variants are established by randomized reductions whose preservation of quantum query complexity (up to constants) is stated as a separate claim, not derived from the complexity bound itself. The conditional lower bound references the independent graph-collision problem. No step in the provided derivation chain reduces the claimed result to a quantity defined by the result, nor relies on load-bearing self-citations or smuggled ansatzes. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on the standard quantum query model and the assumption that randomized reductions preserve query complexity up to constants. No free parameters are fitted to data and no new entities are postulated.

axioms (2)
  • standard math Quantum query complexity is measured in the adjacency-matrix model
    All variants are defined and analyzed inside this standard model.
  • domain assumption Randomized reductions between problem variants preserve quantum query complexity up to constant factors
    Used to establish the equivalence classes and transfer the new upper bound.

pith-pipeline@v0.9.0 · 5664 in / 1387 out tokens · 55120 ms · 2026-05-12T02:15:46.902250+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages

  1. [1]

    SIAM Journal on Computing , volume=

    Quantum query complexity of minor-closed graph properties , author=. SIAM Journal on Computing , volume=. 2012 , publisher=

    work page 2012

  2. [2]

    Chicago Journal of Theoretical Computer Science , volume=

    Learning graph based quantum query algorithms for finding constant-size subgraphs , author=. Chicago Journal of Theoretical Computer Science , volume=

    work page

  3. [3]

    2014 IEEE 55th Annual Symposium on Foundations of Computer Science , pages=

    Improved quantum algorithm for triangle finding via combinatorial arguments , author=. 2014 IEEE 55th Annual Symposium on Foundations of Computer Science , pages=. 2014 , organization=

    work page 2014

  4. [4]

    Algorithmica , volume=

    Extended learning graphs for triangle finding , author=. Algorithmica , volume=. 2020 , publisher=

    work page 2020

  5. [5]

    Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms , pages=

    Nested quantum walks with quantum data structures , author=. Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms , pages=. 2013 , organization=

    work page 2013

  6. [6]

    arXiv preprint arXiv:2209.14146 , year=

    Quantum subroutine composition , author=. arXiv preprint arXiv:2209.14146 , year=

    work page arXiv

  7. [7]

    arXiv preprint arXiv:2510.04973 , year=

    Quantum walks through generalized graph composition , author=. arXiv preprint arXiv:2510.04973 , year=

    work page arXiv

  8. [8]

    1974 , author =

    Cycles of even length in graphs , journal =. 1974 , author =

    work page 1974

  9. [9]

    , author=

    Quantum Lower Bound for Graph Collision Implies Lower Bound for Triangle Detection. , author=. Baltic Journal of Modern Computing , volume=

    work page

  10. [10]

    SIAM Journal on Computing , volume=

    Quantum algorithms for the triangle problem , author=. SIAM Journal on Computing , volume=. 2007 , publisher=

    work page 2007

  11. [11]

    Quantum Amplitude Amplification and Estimation , volume =

    Brassard, Gilles and Hoyer, Peter and Mosca, Michele and Tapp, Alain , year =. Quantum Amplitude Amplification and Estimation , volume =

    work page

  12. [12]

    2011 , Bdsk-File-1 =

    Quantum query complexity of subgraph containment with constant-sized certificates , author=. arXiv preprint arXiv:1109.4165 , year=

    work page arXiv

  13. [13]

    European Symposium on Algorithms , pages=

    Span programs and quantum algorithms for st-connectivity and claw detection , author=. European Symposium on Algorithms , pages=. 2012 , organization=

    work page 2012

  14. [14]

    SIAM Journal on Computing , volume=

    Quantum walk algorithm for element distinctness , author=. SIAM Journal on Computing , volume=. 2007 , publisher=

    work page 2007

  15. [15]

    Theoretical Computer Science , volume=

    On the power of Ambainis lower bounds , author=. Theoretical Computer Science , volume=. 2005 , publisher=

    work page 2005

  16. [16]

    Theory of Computing , volume=

    All Quantum Adversary Methods are Equivalent , author=. Theory of Computing , volume=. 2006 , publisher=

    work page 2006

  17. [17]

    Quantum Information and Computation , volume=

    Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness , author=. Quantum Information and Computation , volume=. 2018 , publisher=

    work page 2018

  18. [18]

    Proceedings of the thirty-ninth annual ACM symposium on Theory of computing , pages=

    Search via quantum walk , author=. Proceedings of the thirty-ninth annual ACM symposium on Theory of computing , pages=

    work page

  19. [19]

    ACM SIGACT News , volume=

    A general method for solving divide-and-conquer recurrences , author=. ACM SIGACT News , volume=. 1980 , publisher=

    work page 1980

  20. [20]

    Quantum Query Complexity of Some Graph Problems , journal =

    D\". Quantum Query Complexity of Some Graph Problems , journal =

    work page

  21. [21]

    Quantum Algorithms for Element Distinctness , booktitle =

    Buhrman, Harry and de Wolf, Ronald and D\". Quantum Algorithms for Element Distinctness , booktitle =

    work page

  22. [22]

    2007 , booktitle =

    Hoyer, Peter and Lee, Troy and Spalek, Robert , title =. 2007 , booktitle =

    work page 2007

  23. [23]

    1998 , booktitle =

    Beals, Robert and Buhrman, Harry and Cleve, Richard and Mosca, Michele and de Wolf, Ronald , title =. 1998 , booktitle =

    work page 1998

  24. [24]

    and Cleve, Richard and Deotto, Enrico and Farhi, Edward and Gutmann, Sam and Spielman, Daniel A

    Childs, Andrew M. and Cleve, Richard and Deotto, Enrico and Farhi, Edward and Gutmann, Sam and Spielman, Daniel A. , title =. 2003 , booktitle =

    work page 2003

  25. [25]

    and Coudron, Matthew and Gilani, Amin Shiraz , title =

    Childs, Andrew M. and Coudron, Matthew and Gilani, Amin Shiraz , title =. 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) , year =

    work page 2023

  26. [26]

    2010 , publisher=

    Quantum computation and quantum information , author=. 2010 , publisher=

    work page 2010

  27. [27]

    Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Reflections for quantum query algorithms , author=. Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2011 , organization=

    work page 2011

  28. [28]

    Journal of the ACM (JACM) , volume=

    Color-coding , author=. Journal of the ACM (JACM) , volume=. 1995 , publisher=

    work page 1995

  29. [29]

    computational complexity , volume=

    On the power of non-adaptive learning graphs , author=. computational complexity , volume=. 2014 , publisher=

    work page 2014

  30. [30]

    Quantum , volume=

    Quantum speedup based on classical decision trees , author=. Quantum , volume=. 2020 , publisher=

    work page 2020

  31. [31]

    Proceedings of the 30th Conference on Computational Complexity , pages=

    Upper bounds on quantum query complexity inspired by the elitzur-vaidman bomb tester , author=. Proceedings of the 30th Conference on Computational Complexity , pages=

    work page