{"id":"b180583c-ee56-4235-a1ac-97ee1954b008","arxiv_id":"2506.21108","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A new QPE-based circuit implements the Grover diffusion operator exactly on Laplacian integral graphs, giving deterministic spatial search with O(1/√ε) cost on any connected such graph.","lead":"This paper gives a quantum algorithm that finds a marked vertex on a graph with 100% success probability whenever the graph's Laplacian has only integer eigenvalues and the fraction of marked vertices is known. It is the first deterministic search method that works on any such graph with any number of marked vertices, not just special symmetric graphs with one marked vertex.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1 omits the connectedness assumption used in its proof; for disconnected Laplacian integral graphs the QPE circuit implements e^{iβP_0}, not e^{iβ|π⟩⟨π|}, so the 'any' claim fails.","rationale":"I checked the QPE parameter choice t0 = π/2^{s-1}, the coherent uncomputation counted twice in Eq. (11), and Long's parameter conditions; all are consistent for connected graphs. The only load-bearing defect is the domain: the proof's explicit '0 = λ1 < λ2' assumption requires a simple zero eigenvalue, which is equivalent to connectedness. The reader's weakest_assumption identifies exactly this gap, and the two-isolated-vertices example makes it concrete. Since a one-word qualification ('connected') repairs Theorem 1 without changing the algorithm or complexity claims, the conditional verdict is appropriate rather than rejection; hence my read leaves the reader's verdict unchanged.","tokens_in":13218,"tokens_out":13022,"duration_ms":153139,"concrete_test":"Simulate Algorithm 1 on the disconnected Laplacian integral graph K_1 ∪ K_1 with M = {v1}. Replace the intended e^{iβ|π⟩⟨π|} by the operator actually produced by Fig. 5, e^{iβP_0} = e^{iβ}I, and run Long's iteration with ε = 1/2. If the squared overlap with |v1⟩ after k iterations is 1/2 for all k ≥ 1 instead of 1, the connectedness assumption is load-bearing. The same conclusion follows analytically: each iteration is a global phase times e^{iαΠ_M}, so the marked amplitude is never amplified.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central construction is sound for connected graphs, but the domain statement of Theorem 1 is not. Section III B assumes '0 = λ1 < λ2 ≤ ...' and '|ψ0⟩ = |π⟩', which is exactly the statement that the zero eigenspace is one-dimensional. The abstract and Theorem 1 say 'any Laplacian integral graph' without repeating the connectedness restriction stated in Section II. For a disconnected graph, the zero eigenspace has dimension equal to the number of components, so the circuit in Fig. 5 applies the phase e^{iβ} to every zero eigenvector, implementing e^{iβP_0} rather than e^{iβ|π⟩⟨π|}. Lemma 1 then no longer applies. Concretely, take G = K_1 ∪ K_1, so L = 0 and every vector is a zero eigenvector; with one marked vertex the effective diffusion is a global phase and the success probability stays 1/2 for every iteration. The fix is to state Theorem 1 for connected Laplacian integral graphs, or to restrict the abstract accordingly; with that qualification the rest of the proof is internally consistent.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a deterministic quantum spatial search algorithm for Laplacian integral graphs, based on the controlled intermittent quantum walk (CIQW) model. The key idea is to use exact quantum phase estimation on the unitary e^{i t0 L}, where L is the graph Laplacian, to implement the phase shift e^{i β |π⟩⟨π|} around the uniform state |π⟩. Since Laplacian integral graphs have integer eigenvalues, the phase estimation is exact. The paper then invokes Long's deterministic Grover iteration to search for any predetermined fraction ε of marked vertices with certainty, claiming total evolution time O(1/√ε) and query complexity O(1/√ε). It also compares its scope and costs with the earlier work of Wang et al. and gives gate-complexity estimates under different assumptions on simulating the continuous-time quantum walk.","tokens_in":13478,"tokens_out":9378,"duration_ms":96642,"significance":"For connected Laplacian integral graphs, the construction is elegant and conceptually clean: the exactness of QPE on an integer spectrum is used directly to turn the Laplacian evolution into a Grover diffusion operator, without fitting parameters to numerical data. This genuinely unifies and extends earlier deterministic search results to a large class of graphs, including non-vertex-transitive ones and multiple marked vertices, and the reduction to Long's deterministic Grover iteration is mathematically sound. The examples in Table I and Appendix A are useful concrete illustrations. However, the scope of the central claim as stated in the abstract and Theorem 1 is broader than what the proof supports, and there are several internal inconsistencies in the complexity accounting that need correction before the paper can be accepted.","major_comments":[{"comment":"The statement 'any Laplacian integral graph' is not supported by the proof. The proof in Section III B assumes the spectrum is 0 = λ1 < λ2 ≤ ... and that |ψ0⟩ = |π⟩, which is exactly the connectedness assumption that the zero eigenspace of L is one-dimensional. For a disconnected Laplacian integral graph, the zero eigenspace has dimension equal to the number of connected components, so the phase-estimation circuit of Fig. 5 applies the phase e^{iβ} to every zero eigenvector, implementing e^{iβ P0} rather than e^{iβ|π⟩⟨π|}. Lemma 1 then no longer applies. A concrete counterexample is G = K1 ∪ K1, for which L = 0, every state is a zero eigenvector, and the algorithm's effective diffusion is a global phase, leaving the success probability at 1/2. The theorem and abstract should be qualified to connected Laplacian integral graphs (or the proof extended to handle the degenerate zero eigenspace), and the standing assumption in Section II should be repeated in the theorem statement.","section":"Abstract and Theorem 1; Section III B"},{"comment":"The count of calls to the controlled continuous-time quantum walk is inconsistent. The text states that 'the controlled CTQW c-e^{iLt} is called for 2^s = 2^{⌈log(λN + 1)⌉} < 2⌈log(N + 1)⌉ times', but with s = ⌈log(λN + 1)⌉ the quantity 2^s can be Θ(N), not O(log N), and the displayed inequality is false already for N = 8 (where 2^s = 16 > 8). If the intended count is 2s calls (s for the controlled-U^{2^j} operations in the forward QPE and s for their inverses in the uncomputation), then Eq. (15) should read O(log(N)/√ε) calls, and the total evolution-time calculation T < 4π is consistent. As written, the call count in Eq. (15) and the gate-complexity conclusions in Section III C and Theorem 3 rest on an erroneous intermediate statement and need to be corrected.","section":"Section III B, Eq. (15); Section III C; Theorem 3"},{"comment":"The description of how the phase gate e^{iβ|π⟩⟨π|} is implemented is internally inconsistent. Algorithm 1 says to perform 'a CIQW (Fig. 3) with m = 2 intermittent steps and s = ⌈log(λN)⌉ ancillary qubits', but the actual circuit in Fig. 5 is a QPE circuit with s controlled evolutions e^{i 2^j t0 L} for j = 0, ..., s−1 and their inverses; this is not a CIQW with m = 2 intermittent steps. Moreover, s must satisfy 2^s > λN, which for integer λN is s = ⌈log(λN + 1)⌉, not ⌈log(λN)⌉; for example, λN = 4 requires s = 3, whereas ⌈log 4⌉ = 2. The pseudo-code should be rewritten to describe the QPE-based construction accurately, since a reader implementing Algorithm 1 from the pseudo-code alone would build the wrong circuit.","section":"Algorithm 1, Step 2(a); Section III B"}],"minor_comments":[{"comment":"The caption states t0 = π/2^{s+1}, but Eq. (10) in Section III B defines t0 = π/2^{s−1}; the latter is the value needed for the QPE eigenphases to be 2π λ_k / 2^s, so the caption should be corrected.","section":"Fig. 5 caption"},{"comment":"The symbol k is used both for the number of iterations of the outer loop and for the iteration-count parameter in Lemma 1, leading to statements such as 'Repeat ... for k = O(1/√ϵ) times, with parameters α, β, k set by Lemma 1.' Renaming one of these, for example using K for the loop count, would remove the ambiguity.","section":"Algorithm 1"},{"comment":"There is a typo in 'alternating quantum walks model [32] can be seen as a mixtuire' — 'mixtuire' should be 'mixture'.","section":"Section I A"},{"comment":"The phrase '2dL = O(N)' appears to be missing superscript formatting; it should read '2^{d_L} = O(N)', consistent with the complexity expression O(2^{d_L}√N) in the comparison with Wang et al.","section":"Introduction, paragraph after Theorem 1"}],"recommendation":"major_revision","confidential_remarks":"The core QPE construction is sound for connected graphs, and the paper is likely acceptable after the scope is corrected and the internal inconsistencies in the algorithm description and complexity accounting are fixed. The connectedness qualification is essential: as stated, the abstract and Theorem 1 overclaim. The call-count issue (2^s vs 2s) is also important because it propagates into Section III C and Theorem 3; this appears to be a fixable typo rather than a flaw in the main evolution-time bound. No circularity was found: the proof does not assume its own conclusion, and the use of the CIQW model from Ref. [42] is appropriate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is worth your time. The new idea is simple: for a Laplacian integral graph, the eigenvalues are integers, so a phase-estimation circuit on e^{iLt} recovers the eigenvalue exactly. That lets you apply a phase to the uniform-vector eigenspace and implement the Grover diffusion operator exactly, turning probabilistic spatial search into deterministic search with total evolution time O(1/sqrt(epsilon)) and query complexity O(1/sqrt(epsilon)) for any predetermined fraction epsilon of marked vertices. That genuinely extends the known deterministic results: Wang et al. needed vertex-transitivity and a single marked vertex; this works for all connected Laplacian integral graphs and any number of marked vertices. The comparison on antiregular graphs, Johnson graphs, and hypercubes is honest and well chosen.\n\nThe construction is clean and the proof is short. The QPE-based phase gate is exact because the spectrum is integral; there are no approximation parameters. The use of Long's deterministic Grover lemma is appropriate. I checked the circuit: the controlled evolutions sum to a constant total time below 4pi per iteration, so the O(1/sqrt(epsilon)) evolution time is real.\n\nThe soft spot is real but easy to fix. The abstract and Theorem 1 say 'any Laplacian integral graph', while the proof uses the fact that the zero eigenvalue is simple, i.e., the graph is connected. In disconnected graphs the QPE circuit applies the phase to the whole zero eigenspace, giving e^{i beta P_0}, not e^{i beta |pi><pi|}; the algorithm then fails. Since Section II says the paper only considers connected graphs, the fix is to add 'connected' wherever 'Laplacian integral' appears in the abstract and theorem, or to add a sentence that connectedness is assumed throughout. As written, the abstract overclaims.\n\nThere are also a few typos that should be caught in revision: '2^s = 2*lceil log(lambda_N+1) rceil' is garbled, the t_0 in Fig. 5's caption is wrong, and Algorithm 1's 'm=2' does not match the QPE circuit. None affect the argument.\n\nThis is a solid contribution. It deserves peer review and, after the connectedness fix, acceptance. I would bring it to a reading group if anyone cares about quantum walk search.","headline":"Clean QPE-based deterministic search that genuinely extends the known graph class; the only real fix is to state the connectedness assumption.","tokens_in":13970,"tokens_out":5228,"would_cite":true,"duration_ms":54750,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A quantum algorithm based on a controlled intermittent quantum walk finds a marked vertex with certainty on any Laplacian integral graph, in total evolution time and query complexity $O(1/\\sqrt{\\varepsilon})$ when the marked fraction is…","keywords":["quantum spatial search","deterministic quantum algorithm","Laplacian integral graphs","controlled intermittent quantum walk","quantum phase estimation","Grover search","quantum walk"],"falsifier":"Simulate Algorithm 1 on a disconnected Laplacian integral graph — the disjoint union of two complete graphs, say — with a known marked set; because the zero eigenspace has dimension two, the reflection built by phase estimation is not the reflection about the uniform state, and the measured success probability will be strictly below 1, contradicting the theorem as stated.","tokens_in":13046,"feed_emoji":"🎯","tokens_out":11891,"duration_ms":120589,"temperature":0.7,"pith_summary":"The paper claims that spatial search — finding an unknown marked vertex of a graph — can be made deterministic for every Laplacian integral graph, meaning every graph whose Laplacian eigenvalues are all integers. The proposed algorithm runs a controlled intermittent quantum walk (CIQW) in which quantum phase estimation is used to build the exact reflection around the uniform superposition state. Wrapping that reflection with the phase oracle in Long's deterministic Grover iteration yields the marked vertex with certainty whenever the proportion $\\varepsilon$ of marked vertices is known in advance, with total evolution time and query count both $O(1/\\sqrt{\\varepsilon})$. This would be the largest class of graphs known to admit deterministic quantum search, and it unifies earlier results that required vertex-transitivity or a single marked vertex.","feed_headline":"Search succeeds with certainty on every integer-spectrum graph","feed_subtitle":"A new quantum-walk algorithm runs in O(1/√ε) and removes old restrictions on marked vertices and graph symmetry.","key_machinery":"The central object is the controlled intermittent quantum walk (CIQW), a sequence of controlled continuous-time quantum walks $\\Lambda_s(e^{iLt_j})$ interleaved with unitaries on the control register. The load-bearing mechanism is exact quantum phase estimation of $e^{i t_0 L}$ with a time step chosen so that every integer Laplacian eigenvalue $\\lambda_k$ appears as the exactly representable $s$-bit phase $2\\pi\\lambda_k/2^s$. Flipping a phase on the $|0\\cdots0\\rangle$ outcome of that phase estimate therefore acts as $e^{i\\beta|\\pi\\rangle\\langle\\pi|}$ on the walk space, and inverting the phase estimation uncomputes the register at no extra cost. The per-reflection evolution time is bounded by $4\\pi$, independent of the number of vertices.","core_discovery":"The central discovery is Theorem 1: for any Laplacian integral graph, a CIQW-based algorithm finds a marked vertex with certainty in total evolution time $O(1/\\sqrt{\\varepsilon})$ and query complexity $O(1/\\sqrt{\\varepsilon})$, where $\\varepsilon = \\|\\Pi_M |\\pi\\rangle\\|^2$ is the fraction of marked vertices and is known in advance. The construction implements the generalized Grover operator $G(\\alpha,\\beta) = e^{i\\beta|\\pi\\rangle\\langle\\pi|} e^{i\\alpha\\Pi_M}$ exactly. The key step is that because every Laplacian eigenvalue is an integer, quantum phase estimation on the unitary $e^{i t_0 L}$ returns the eigenvalue exactly on an $s$-qubit register, so a single conditional phase gate can implement exactly the reflection $e^{i\\beta|\\pi\\rangle\\langle\\pi|}$; reversing the phase estimation restores the register. Long's lemma then gives the precise parameters $\\alpha = \\beta = 2\\arcsin(\\sin(\\pi/(4k+2))/\\sqrt{\\varepsilon})$ for which $k = O(1/\\sqrt{\\varepsilon})$ iterations succeed with probability one.","pith_inferences":["The exactness mechanism is not specific to Laplacians: any Hermitian matrix whose spectrum is exactly representable by phase estimation (for instance integer or dyadic-rational eigenvalues) should admit the same reflection-based deterministic search, so the scope may extend to other graph-associated matrices.","If the requirement that the marked fraction $\\varepsilon$ be known in advance is relaxed, combining the CIQW reflection with fixed-point or robust Grover iterations is a natural next step; whether certainty can be retained without exact $\\varepsilon$ is left open by the paper.","For disconnected integral graphs, a plausible repair is to decompose into connected components and run the search component-wise, or to replace the single reflection by a reflection about the entire zero-eigenspace projector; this would turn the literal claim for disconnected graphs into a testable extension."],"forward_implications":["A single unified algorithm now covers the known Laplacian integral graph families — complete, Johnson, Kneser, Hamming, hypercube, Grassmann, rook, star, cocktail-party, and complete $k$-partite graphs — with $O(1/\\sqrt{\\varepsilon})$ walk time and query count.","Multiple marked vertices are handled directly, as long as their fraction $\\varepsilon$ is known; previous deterministic schemes were limited to exactly one marked vertex.","When the continuous-time quantum walk has a poly-logarithmic gate circuit, the total gate complexity is $O(\\mathrm{poly}(\\log N)/\\sqrt{\\varepsilon})$, so deterministic search on those graphs is efficient in both time and gates.","The vertex-transitivity requirement disappears, so graphs such as the antiregular graphs, which the earlier alternating-walk algorithm could not address, are covered."],"supporting_citations":[{"why":"It defines the controlled intermittent quantum walk model that the algorithm uses to implement the reflection.","marker":"[42]"},{"why":"It supplies Long's deterministic Grover iteration and parameter choice that guarantee probability-one success once the reflection and oracle are exact.","marker":"[35]"},{"why":"It supplies the quantum phase estimation subroutine that reads out the integer eigenvalues exactly.","marker":"[46]"},{"why":"It is the previous alternating-quantum-walk deterministic search this work improves, removing vertex-transitivity and single-marked-vertex restrictions and the depth-dependent complexity.","marker":"[7]"},{"why":"It supplies the standard spectral fact that a connected graph's Laplacian has a simple zero eigenvalue with uniform eigenvector, which the phase-gate construction requires.","marker":"[45]"}],"fun_headline_variants":["Quantum search now always succeeds on integral graphs","Certain quantum search for any fraction of marked vertices","Zero-failure search on all Laplacian integral graphs","Deterministic quantum search: no failure on integral graphs","Perfect quantum search on any integer-spectrum graph"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof requires the graph to be connected so the zero Laplacian eigenspace is one-dimensional and spanned by the uniform state; on a disconnected Laplacian integral graph the phase-estimation gate no longer implements the reflection about $|\\pi\\rangle$, so the theorem's literal claim for 'any' such graph is stronger than what the construction demonstrates.","fun_headline_variants_meta":{"raw":{"variants":["Quantum search now always succeeds on integral graphs","Certain quantum search for any fraction of marked vertices","Zero-failure search on all Laplacian integral graphs","Deterministic quantum search: no failure on integral graphs","Perfect quantum search on any integer-spectrum graph"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000708,"raw_usage":{"total_tokens":3192,"prompt_tokens":954,"completion_tokens":2238,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":570,"completion_tokens_details":{"reasoning_tokens":2164}},"tokens_in":570,"tokens_out":2238,"duration_ms":17427,"temperature":1.0,"reasoning_tokens":2164,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T22:35:55.502455+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate Algorithm 1 on a disconnected Laplacian integral graph — the disjoint union of two complete graphs, say — with a known marked set; because the zero eigenspace has dimension two, the reflection built by phase estimation is not the reflection about the uniform state, and the measured success probability will be strictly below 1, contradicting the theorem as stated.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It defines the controlled intermittent quantum walk model that the algorithm uses to implement the reflection."},{"cited_title":"Krovi, F","cited_arxiv_id":null,"evidence_quote":"It supplies Long's deterministic Grover iteration and parameter choice that guarantee probability-one success once the reflection and oracle are exact."},{"cited_title":"Marsh and J","cited_arxiv_id":null,"evidence_quote":"It supplies the quantum phase estimation subroutine that reads out the integer eigenvalues exactly."},{"cited_title":"This graph has n vertices, and each vertex is connected to the other n − 1 vertices","cited_arxiv_id":null,"evidence_quote":"It is the previous alternating-quantum-walk deterministic search this work improves, removing vertex-transitivity and single-marked-vertex restrictions and the depth-dependent complexity."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It supplies the standard spectral fact that a connected graph's Laplacian has a simple zero eigenvalue with uniform eigenvector, which the phase-gate construction requires."}],"review_version":1}