{"id":"aa941105-3923-4a2d-bb33-0c6e29b810b7","arxiv_id":"2507.21937","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":2.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"A Grover-based maze solver whose fitness function ignores wall constraints, so the algorithm does not actually solve mazes.","lead":"A quantum algorithm is proposed that encodes all possible maze paths as superpositions and uses Grover search to amplify paths with high fitness, where fitness is based only on endpoint distance. The paper claims efficient, provably convergent maze solving, but its circuit never reads the maze's walls, so it solves a wall-free grid instead of the stated perfect maze.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The algorithm never consults the maze's wall layout: Eq. (26) updates coordinates unconditionally and the Section XV validity check tests only grid bounds, so fitness and oracle are wall-independent. The claimed solution to perfect mazes is actually a solution to a wall-free grid.","rationale":"The reader's weakest_assumption is exactly the load-bearing concern: the algorithm's transition rule and validity check omit maze walls. The paper's own formalization in Section II requires a wall-aware δ, but Sections IV and XV implement a wall-free version. This is an internal inconsistency, not merely a disagreement with current consensus. The central claim—a complete quantum algorithm for solving perfect mazes—requires that the oracle mark legal goal-reaching paths; because the fitness value depends only on final coordinates under unconditional moves, illegal paths through walls are marked. The 2x2 example makes this concrete: S,E and E,S both end at (1,1), but a wall can make one illegal. The Grover analysis in Sections VI and VII is textbook and would be correct on a wall-free grid, but it is applied to the wrong predicate. The adaptive cutoff proof in Theorem 4 has additional gaps—it assumes knowledge of k_t for choosing r_t and is inconsistent about strict versus non-strict cutoff—but these are secondary. I found no independent support that would rescue the central claim: there is no machine-checked proof, no code, and no comparison with classical solvers. The reversible arithmetic components are standard, but they do not address wall legality. Therefore the reader's REJECT verdict is appropriate and unchanged.","tokens_in":13302,"tokens_out":3231,"duration_ms":43843,"concrete_test":"Construct a 2x2 perfect maze with start (0,0), goal (1,1), and a wall blocking the S move from (0,0), so the only legal path is E,S. Enumerate all 16 bitstrings under the paper's transition rule (Eq. (26) plus the Section XV bounds check): the path S,E (|1001⟩) terminates at (1,1) with fitness 4 and is marked by the oracle, yet δ in Eq. (3) declares it invalid because it crosses the wall. Simulate the full algorithm (or its classical probability distribution) for this maze; if it returns S,E as the solution, the central claim fails. Alternatively, instrument the validity operator to return valid(x)=0 for any path crossing an internal wall; doing so requires encoding the wall layout, and the paper provides no such circuit or operator.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim requires that the fitness operator and oracle identify valid maze paths, but the implementation never uses the maze's walls. Section II defines the transition function δ with a wall-aware legality condition (δ returns ⊥ for a wall hit), but Section IV, Eq. (26), replaces δ with unconditional coordinate updates (N: i-1, E: j+1, S: i+1, W: j-1). The only validity check, in Section XV, tests whether coordinates remain within [0,m-1]^2; it does not check whether a move crosses a wall. Consequently, end(P), distance, and fitness in Eq. (24) are computed on a wall-free grid, not on the maze M. The oracle's marked set M is therefore determined solely by final coordinates and the cutoff; paths that walk through internal walls are marked as high-fitness if they end at or near the goal. This is not a minor omission: the marked set is the input to the Grover amplification analysis, so all success-probability statements are about the wrong search problem. For example, in the paper's own 2x2 example, both S,E and E,S reach (1,1) from (0,0), but a perfect maze may have exactly one of these moves blocked; the algorithm would mark the illegal path as optimal. The proof of Theorem 2 establishes unitarity of an arithmetic circuit, not correctness of the fitness function. Separately, the adaptive-cutoff analysis is also fragile: Eq. (33) marks states with f(x) > cutoff, but Corollary 2 and Theorem 4 assume equality marks states, and the iteration count r_t requires knowledge of k_t, the number of marked states, which is unknown. The wall-independence issue is the load-bearing defect: without wall-aware simulation, the algorithm does not solve the stated problem.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a Grover-based quantum algorithm for solving perfect mazes. It encodes all length-n direction strings as 2n-qubit states, simulates their motion from a start cell, computes a fitness value C - squared Euclidean distance to the goal, marks states with fitness above an adaptive cutoff, and iterates Grover amplification. The paper claims formal proofs of correctness, unitarity, and convergence, together with resource estimates. The central thesis is that this pipeline solves a perfect maze by amplifying high-fitness paths.","tokens_in":13601,"tokens_out":6216,"duration_ms":72035,"significance":"The Grover geometry portion (Sections VI–VII) is a correct re-derivation of standard amplitude-amplification facts, and the reversible arithmetic circuit sketches are based on recognized primitives. However, the algorithm as specified never consults the maze's wall layout: Eq. (26) updates coordinates unconditionally, and the validity check in Section XV only tests grid bounds. Fitness values, the oracle's marked set, and all subsequent success-probability statements are therefore computed on a wall-free grid, not on the perfect maze M defined by the transition function δ in Eq. (3). This is a load-bearing defect that invalidates the central claim. The adaptive-cutoff analysis is also unsupported: Theorem 4 requires knowledge of k_t, the number of marked states, and the oracle's strict inequality in Eq. (33) is inconsistent with Corollary 2's equality-based marking. The paper provides no machine-checked proofs or reproducible code; its solid content is a textbook-level account of Grover search.","major_comments":[{"comment":"The fitness operator never checks maze walls. Eq. (26) defines unconditional coordinate updates (i-1, j+1, i+1, j-1), and Section XV's validity flag is defined as valid(x)=1 iff every intermediate cell lies in [0,m-1]^2, with no wall test. Consequently end(P), the distance in Eq. (24), and the oracle's marked set are determined by a wall-free grid, not by the perfect maze M. For example, in the paper's own 2x2 setting, the path S,E reaches (1,1) from (0,0), but a perfect maze may have a wall blocking one of those moves; the algorithm would mark the illegal path as optimal. Since the marked set is the input to the Grover success-probability analysis in Sections VI and VII, all correctness statements in the paper are about a different search problem than the one claimed.","section":"IV, Eq. (26); XV"},{"comment":"The proof requires choosing r_t so that (2r_t+1)θ_t ≈ π/2, where θ_t = arcsin(sqrt(k_t/N)) and k_t = |{x : f(x) > C_t}| is the number of marked states at threshold C_t. This requires knowing k_t, which is precisely the unknown quantity that Grover search is intended to find. No procedure for estimating or avoiding k_t is given, so the asserted per-round success probability P_t ≥ 1−δ is unjustified. Additionally, at C_t = fmax the strict inequality in Eq. (33) marks no states at all, so Corollary 2's statement that the oracle 'permanently marks all global optima' is false; the claimed final amplification step with k=1 is not achieved by the specified oracle.","section":"IX, Theorem 4; Eq. (83)"},{"comment":"The convergence proof conflates the monotonicity of a classical cutoff sequence with the probabilistic behavior of quantum measurements. Theorem 3 shows only that if a sequence of observed fitness values with f_t* > C_t occurs, then the cutoff increases; it does not show that each Grover round produces such a value with any nontrivial probability. Before C_t reaches fmax, the marked set can be large, and without knowledge of k_t the algorithm has no way to ensure that the measured state has f(x) > C_t. The claimed halting within T ≤ 2m rounds with success probability at least 1−ε is therefore not established. The proof also assumes fmax ≤ 2m, which is inconsistent with Eq. (24), where C ≥ 2(m−1)^2 and fitness is C − distance, so fmax can be much larger than 2m.","section":"VIII, IX; Theorem 3 and Theorem 4"}],"minor_comments":[{"comment":"The statement that perfect mazes (loop-free, acyclic grids) make the problem 'computationally intractable and NP-complete' is incorrect; finding a path in a tree is solvable in linear time by DFS or BFS. NP-completeness holds for general grid mazes with cycles, not for perfect mazes as defined here.","section":"Introduction and Section II"},{"comment":"The search-space size N is written as '4n' in Section VI and Eq. (83), but the number of direction strings of length n is 4^n (as stated in Section II). Since the Grover angle θ depends on N, the notation should be corrected to 4^n throughout.","section":"VI and Eq. (83)"},{"comment":"The fitness register size is defined as r = ceil(log2 C) with C = 2^r ≥ 2(m−1)^2, but Appendix XII describes a '(log m)-qubit fitness output register' and the worked example uses C = 2m; these presentations should be reconciled.","section":"IV and Appendix XII"},{"comment":"Reference [13] (Duchi et al., projections onto the l1-ball) is unrelated to the comparison or search circuits discussed in the paper and should be removed or replaced with a relevant reversible-comparator reference.","section":"References"}],"recommendation":"reject","confidential_remarks":"The manuscript's central algorithm solves a wall-free grid rather than a perfect maze, and the convergence proof requires knowledge of k_t, the very quantity Grover search is meant to discover. Both are load-bearing defects that cannot be fixed by local edits; the path-simulation, oracle, and convergence analysis would all need to be reworked. The framing as a 'complete quantum algorithm' with 'formal proofs' overstates what is actually established. If the author wishes to pursue a correct version, the wall-dependence of the transition function must be built into the fitness and oracle, and the k_t dependence must be eliminated or explicitly estimated."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe short version: the paper's central claim is false. The algorithm never consults the maze's walls. Equation (26) updates the walker's coordinates unconditionally for each direction, and the validity check in Section XV only tests whether coordinates stay within the grid. So the fitness function and oracle are defined on a wall-free grid, not on the maze. A path that walks straight through an internal wall gets the same score as one that follows the actual corridor. The 2x2 example makes this concrete: both S,E and E,S reach (1,1) from (0,0), but a perfect maze may block one of them. The algorithm marks the illegal one.\n\nThe motivation is also off. Perfect mazes are trees; the unique path between start and goal is found by classical BFS in linear time. Claiming the problem is NP-complete and that Grover gives a speedup is backwards. Even if the algorithm worked as intended, searching over all 4^n direction strings with O(2^n) Grover iterations is exponentially worse than the classical baseline.\n\nWhat is good: the paper is a clear, self-contained review of Grover's algorithm, reversible adders, and a greater-than comparator. The Grover geometry derivation is correct, and the circuit constructions are standard. If you want a refresher on how to wire Grover around an arithmetic oracle, this is readable. But there is no new primitive, no new theorem, and no code. The adaptive cutoff is just a running maximum; Theorem 3 is a tautology about a monotone integer sequence. Theorem 4 assumes you know k_t, the number of marked states, to set the iteration count—exactly the quantity you don't know.\n\nThe wall problem is not a minor gap. It is load-bearing. The definitions in Section II include a wall-aware transition function δ, but the implementation in Section IV replaces δ with unconditional coordinate updates. That is an internal contradiction between the formalism and the circuit. The proof of Theorem 2 establishes unitarity of arithmetic, not correctness of the fitness function.\n\nBottom line: this should be desk-rejected, not sent to referees. It does not solve the stated problem, and the error is visible at the level of Eq. (26). I would not cite it. It might be worth a skim as a cautionary example of checking whether the implemented circuit matches the problem definition, but I wouldn't spend a reading group session on it.","headline":"The algorithm never uses the maze's walls, so it solves a wall-free grid; the paper's central claim is unsupported.","tokens_in":14217,"tokens_out":2150,"would_cite":false,"duration_ms":22751,"reading_group":"no","serious_thinker":"no","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims a complete quantum algorithm that solves perfect mazes through a reversible fitness-guided Grover search.","keywords":["quantum algorithm","Grover search","maze solving","perfect maze","amplitude amplification","reversible arithmetic","adaptive cutoff","fitness-guided search"],"falsifier":"Take a 2x2 perfect maze in which the only legal route from (0,0) to (1,1) is S,E, with a wall blocking every other interior crossing; implement the path-simulation and oracle exactly as specified (updates from Eq. 26 plus the Section XV bounds check) and list the fitness values of all 16 direction strings. If any wall-crossing string receives fitness above a cutoff that also holds for the true path, the circuit is amplifying wall-free grid strings, not maze paths—settling that the claimed maze-solving correctness depends on an added wall-consulting test.","tokens_in":13014,"feed_emoji":"🧭","tokens_out":9546,"duration_ms":114122,"temperature":0.7,"pith_summary":"This paper claims to give a full quantum pipeline that solves perfect mazes: it encodes every length-$n$ direction string in superposition, simulates each string to an endpoint in reversible arithmetic, scores the endpoint by squared Euclidean distance to the goal, and uses a Grover-compatible oracle to amplify the highest-scoring strings. The strongest stated result is that an adaptive cutoff, raised monotonically whenever a better fitness is observed, converges to an optimal path within a bounded number of rounds and with success probability at least $1-\\varepsilon$. If the construction is correct, maze solving becomes a structured Grover search with per-iteration circuit depth $O(n\\log m)$ and qubit count $O(n\\log m)$, and the same fitness-oracle template extends to navigation over tree-like or acyclic graphs. A reader should care because this is an end-to-end specification—encoding, oracle, amplification, convergence—for a search problem with an unknown number of marked states.","feed_headline":"Perfect mazes solved by fitness-guided Grover search","feed_subtitle":"A fully specified reversible pipeline, from path encoding to amplitude amplification, with bounded convergence.","key_machinery":"The carrying mechanism is the two-dimensional Grover subspace spanned by the normalized marked state $|\\psi_T\\rangle$ and unmarked state $|\\psi_\\perp\\rangle$, together with the fitness oracle that defines the marked set. The initial state sits at angle $\\theta=\\arcsin\\sqrt{k/N}$ from the unmarked subspace, so after $r$ iterations the success probability is $\\sin^2((2r+1)\\theta)$ and the optimal iteration count is $r^*\\approx \\pi/(4\\theta)-1/2$. The fitness operator is built from direction-controlled coordinate updates, reversible subtraction and squaring, and uncomputation; the oracle is a reversible greater-than comparator followed by a controlled phase flip. The adaptive cutoff is the third piece: it converts an unknown number of marked states into a shrinking sequence of Grover problems whose final marked set contains only globally optimal strings.","core_discovery":"The central claim, in the paper's own terms, is that a perfect maze can be solved by a complete Grover-based algorithm rather than by classical backtracking. The paper defines a uniform superposition $|\\Omega\\rangle$ over all $4^n$ direction strings of length $n$, a reversible fitness operator $F:|x\\rangle|0\\rangle_f \\mapsto |x\\rangle|f(x)\\rangle$ with $f(x)=C-((i-i_f)^2+(j-j_f)^2)$, and a phase oracle $O=C^{-1}ZC$ that flips the sign of strings whose fitness exceeds a cutoff. Grover iteration $G=DO$ rotates the state in the two-dimensional marked/unmarked subspace, and the monotonic cutoff rule $C_{t+1}=\\max(C_t,f^*_t)$ is proved to reach the maximum fitness in at most $f_{\\max}-C_1$ steps with high probability. The paper also presents formal arguments that the superposition is uniform over valid encodings, that both $F$ and $O$ are unitary, and that one round of search costs $O(n\\log m)$ gates and qubits.","pith_inferences":["I read the validity condition in Section XV—staying inside the $m\\times m$ bounds—as the intended hook for enforcing the maze's actual walls; as written, the simulation updates coordinates without consulting the wall layout, so a wall-aware legality test would need to be added to the oracle for the claimed 'perfect maze' result to hold.","A concrete extension would be to compile the circuit for a 2x2 or 3x3 maze with known internal walls and check whether the amplified distribution assigns high probability to wall-crossing strings; that experiment separates the endpoint-optimality claim from true maze-path validity.","Because the number and identity of marked states is unknown, the practical speedup of the adaptive strategy depends on how quickly observed fitness rises as the cutoff climbs; the paper proves convergence but does not model that random-walk behavior, which is the natural next analysis.","The direction-string representation treats the maze as a complete $4$-ary tree of walks; for a perfect maze the legal paths form a much smaller tree, so comparing this encoding with search over the actual spanning tree is a testable route to reducing $N$."],"forward_implications":["A perfect maze can be compiled into a Clifford+T circuit whose depth per Grover round is $O(n\\log m)$ and whose width is $O(n\\log m)$, with $n$ path length and $m$ grid width.","The same oracle can accept a classical constant or a quantum register as the cutoff, so the adaptive scheme can run with thresholds supplied by another quantum subsystem.","The cutoff sequence reaches the maximum fitness in at most $f_{\\max}-C_1\\le 2m$ rounds; once there, the optimal strings are permanently marked and remain amplifiable.","Grover amplification provides the standard quadratic speedup: the number of oracle calls per round scales as $O(\\sqrt{N/k})$ with $N=4^n$, whenever the marked set has size $k$.","The encoding-and-fitness pipeline transfers directly to navigation on tree-like or acyclic graphs, since those can be represented by direction strings with a distance-based fitness function."],"supporting_citations":[{"why":"Supplies the underlying amplitude-amplification mechanism that the whole pipeline is built on.","marker":"[3]"},{"why":"Provides the ripple-carry adder used for reversible path simulation, subtraction, and the oracle comparator.","marker":"[1]"},{"why":"Provides the reversible addition primitive that the distance and fitness arithmetic rely on.","marker":"[2]"},{"why":"Supplies tight bounds on quantum searching with an unknown number of marked states, supporting the adaptive iteration strategy.","marker":"[12]"},{"why":"Provides the uncomputation and ancilla-reuse argument that keeps the fitness operator reversible and resource-efficient.","marker":"[6]"}],"fun_headline_variants":["Grover's algorithm cracks perfect mazes","Quantum pathfinding via fitness-guided Grover","Fitness-guided Grover search for perfect mazes","Solving perfect mazes with Grover's amplitude amplification","Quantum algorithm for perfect mazes via Grover search"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that a path is legal whenever its coordinates stay inside the grid; the maze's internal wall layout is never consulted in the simulation, so if walls block any boundary-respecting move, the algorithm can mark and amplify strings that walk through walls.","fun_headline_variants_meta":{"raw":{"variants":["Grover's algorithm cracks perfect mazes","Quantum pathfinding via fitness-guided Grover","Fitness-guided Grover search for perfect mazes","Solving perfect mazes with Grover's amplitude amplification","Quantum algorithm for perfect mazes via Grover search"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000694,"raw_usage":{"total_tokens":3120,"prompt_tokens":906,"completion_tokens":2214,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":522,"completion_tokens_details":{"reasoning_tokens":2142}},"tokens_in":522,"tokens_out":2214,"duration_ms":18379,"temperature":1.0,"reasoning_tokens":2142,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T12:12:53.510000+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a 2x2 perfect maze in which the only legal route from (0,0) to (1,1) is S,E, with a wall blocking every other interior crossing; implement the path-simulation and oracle exactly as specified (updates from Eq. 26 plus the Section XV bounds check) and list the fitness values of all 16 direction strings. If any wall-crossing string receives fitness above a cutoff that also holds for the true path, the circuit is amplifying wall-free grid strings, not maze paths—settling that the claimed maze-solving correctness depends on an added wall-consulting test.","supporting_citations":[{"cited_title":"A fast quantum mechanical algorithm for database search,","cited_arxiv_id":null,"evidence_quote":"Supplies the underlying amplitude-amplification mechanism that the whole pipeline is built on."},{"cited_title":"Tight bounds on quan- tum searching,","cited_arxiv_id":null,"evidence_quote":"Supplies tight bounds on quantum searching with an unknown number of marked states, supporting the adaptive iteration strategy."},{"cited_title":"Time/space trade-offs for reversible computation,","cited_arxiv_id":null,"evidence_quote":"Provides the uncomputation and ancilla-reuse argument that keeps the fitness operator reversible and resource-efficient."}],"review_version":1}