REVIEW 2 major objections 2 minor
Quantum algorithms for path and cycle containment problems
T0 review · 2 major / 2 minor · reviewed 2026-05-12 · grok-4.3
Pith's one-line read 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.
desk verdict The paper gives a concrete improvement to the quantum query bound for an equivalence class of path and cycle problems via a new quantum walk, plus a clean dichotomy, but the constant-factor claim on the randomized reductions is the part that needs the closest look. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
Extended reading notes
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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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)
- [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.
- [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)
- [Abstract] The abstract lists promise versions without enumerating them; a one-sentence clarification of the promise assumptions would improve readability.
- [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
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
-
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
-
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
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.
Assumptions & free parameters
assumptions (2)
- standard math Quantum query complexity is measured in the adjacency-matrix model
- domain assumption Randomized reductions between problem variants preserve quantum query complexity up to constant factors
Cite this review
Pith. "Pith review of Quantum algorithms for path and cycle containment problems." pith.science (2026). https://pith.science/paper/ZCXPIOJX
@misc{pith2026260509017,
author = {Pith},
title = {Pith review of: Quantum algorithms for path and cycle containment problems},
year = {2026},
howpublished = {\url{https://pith.science/paper/ZCXPIOJX}},
note = {Machine review of arXiv:2605.09017}
}
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.
Figures
Figures from the paper (3 more)
Reviewed May 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.