{"id":"d4a9ecf6-f3ab-4005-bfce-dcc7edb61986","arxiv_id":"2608.09134","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A 1-covering path method reduces the CNOT cost of quantum hashing circuits on arbitrary qubit connectivity graphs.","lead":"This paper presents an algorithm for building CNOT-based quantum fingerprinting circuits on arbitrary qubit connectivity graphs, using a new graph problem called the shortest non-simple 1-covering path. The authors claim 16 to 17 percent lower CNOT counts on some grid architectures than an earlier method by the same group.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's CNOT-cost formula is inconsistent with Algorithm 4 as written: Step 3/Step 6 do not exclude path vertices from single-CR_y use, adding 2 CNOTs per such vertex (4-cycle example gives 11 vs the claimed 7).","rationale":"The reader's weakest assumption—parameter existence for the shallow circuit—is a real caveat, but it is inherited from prior work [46,47], explicitly acknowledged in Appendix A, and applies to any shallow-circuit construction. The more load-bearing concern is internal to this paper: the central Theorem 1 gives a precise CNOT-cost formula, but the counting proof in Appendix H silently assumes that path vertices are never used as single CR_y controls outside the paired CR_y+SWAP steps. The published Algorithm 4 does not enforce this: U tracks only controls already used, not all vertices already in the path, and the starting target is never placed in U. On a simple 4-cycle this changes the cost from the claimed 7 to 11, so the theorem is false for the algorithm as written. The fix is small—skip all path vertices in the neighbor loops and initialize U with the starting vertex—but it is essential and must be stated before the cost claims can be accepted. This is why the reader's conditional verdict remains appropriate, though for a different, more directly testable reason. I do not see a reason to move from CONDITIONAL to REJECT because the intended construction is plausible and the discrepancy is likely correctable; however, the current text contains a concrete counterexample to its headline bound.","tokens_in":18086,"tokens_out":30217,"duration_ms":291623,"concrete_test":"Implement Algorithm 4 verbatim on the 4-cycle graph C4 with ℓ=1 and the shortest 1-covering path P=(v1,v2) returned by Shortest1CP. Count CNOT gates: Theorem 1 predicts 7, while literal Algorithm 4 produces 11 because Step 6 adds cR(v1,v2) and cR(v3,v2). Then patch Step 3 and Step 6 to skip every vertex of P (not just the immediate next vertex) and initialize U with v_{i1}; if the count drops to 7 and each non-target qubit controls exactly one CR_y, the issue is an omitted condition in the pseudocode rather than a deeper flaw. This single check settles whether the published algorithm meets its claimed bound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Appendix H proves Theorem 1 by counting exactly n−k′ single CR_y gates (to vertices outside the 1-covering path P) plus k−1 SWAP/cancelled-pair steps. This counting is valid only if Step 3 and Step 6 never apply a CR_y to a vertex that already belongs to P. Algorithm 4 (Appendix F), however, checks only `v' ∉ U` and `v' ≠ v_{ij+1}`; U is initialized to ∅ and does not contain the starting target v_{i1} or previously traversed path vertices. On a 4-cycle v1–v2–v3–v4–v1, Shortest1CP returns P=(v1,v2). Literal execution of Algorithm 4 gives: Step 3 adds cR(v4,v1); Step 4 adds cR(v2,v1)+SWAP; Step 6 then adds both cR(v1,v2) and cR(v3,v2), because neither v1 nor v3 is in U. The total CNOT count is 4·2+1·3=11, whereas Theorem 1 predicts (3·2+2·2)−5+2=7. The extra cR(v1,v2) uses the initial target vertex as a control after the target has been swapped away; in the fixed-wire circuit this is a second use of the control qubit that was moved into v1, so the circuit also lacks the intended single-use-per-control form. If the intended rule is to skip all path vertices in Step 3, that condition is missing from Algorithm 4 and from the proof's counting; hence the theorem is not established for the algorithm as submitted.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a method for compiling a sequence of shallow quantum hashing (quantum fingerprinting) operators U_s onto an arbitrary qubit connectivity graph. The method is based on a shortest non-simple 1-covering path P: the target qubit moves along P, controlled rotations are applied to qubits outside P, and SWAP gates move the target. The main theoretical claim (Theorem 1) is a closed-form CNOT-cost formula, (3k+2(n-k'))ℓ-5ℓ+2, for ℓ applications of U_s, with corollary bounds between 2nℓ-4ℓ+2 and 6nℓ-7ℓ+2. The paper also gives an exact exponential-time algorithm and a polynomial-time approximation algorithm for the 1-SNSCP problem, and demonstrates the method on MOD_p and EQ_p automata, including a grid graph example with a reported 16%-17% CNOT reduction over the prior method [49].","tokens_in":18525,"tokens_out":8221,"duration_ms":72728,"significance":"If the CNOT-cost formula and its proof are correct, the paper offers a genuinely useful compilation heuristic for limited-connectivity quantum devices, and the 1-SNSCP formulation has independent algorithmic interest. The strength of the work is that it makes explicit, parameter-free cost formulas and compares them directly with a prior construction [49], rather than fitting constants to data. The exact and approximate algorithms for the 1-covering path problem are also presented in detail. However, the central formula is currently not established by the manuscript: the proof in Appendix H counts a structure that Algorithm 4 does not produce, and the paper itself flags a critical open limitation in Appendix A about whether the shallow circuit uses the same number of qubits for the required hash parameters.","major_comments":[{"comment":"The CNOT counting in Appendix H is inconsistent with Algorithm 4 as written. U is initialized to empty, and the conditions in Steps 3 and 6 only test membership in U (and, in Step 3, that v' is not the next path vertex); vertices of the covering path P are not excluded. On a 4-cycle v1-v2-v3-v4-v1 with shortest 1-covering path P=(v1,v2), literal execution gives: Step 3 adds cR(v4,v1); Step 4 adds cR(v2,v1) and U={v4,v2}; Step 5 swaps v1 and v2; Step 6 then adds both cR(v1,v2) and cR(v3,v2). The CNOT count is 4·2+3=11, whereas Theorem 1 predicts (3·2+2·2)-5+2=7. The extra cR(v1,v2) also breaks the single-use-per-control structure on which the proof's counting relies. To make the theorem correct, Steps 3 and 6 must explicitly skip every vertex of P (or U must be initialized with all path vertices), and the proof must count the resulting number of single CR_y gates accordingly.","section":"Appendix F, Algorithm 4; Section 3.2, Theorem 1"},{"comment":"The proof states that 'for two sequential applications of Us, one CR_y operator disappears' and uses this to derive the -5ℓ term. This cancellation is load-bearing and is not proven at the gate level. The manuscript should provide an explicit circuit identity or an induction showing that, for arbitrary P and arbitrary neighbor orderings, exactly one CR_y gate cancels at each boundary between consecutive U_s applications, including the role of the first and last neighbors of the path endpoints.","section":"Appendix H, proof of Theorem 1"},{"comment":"The algebra in the grid example contains an arithmetic error. The displayed expansion reads 3((t+1)(q-1)/2 - 2) + 2(qt - ((t+1)(q-1)/2 - 1)) = 2qt + (t+1)(q-1)/2 - 3, but the correct value is 2qt + (t+1)(q-1)/2 - 4. The numerical values 101 and 123 for q=7, t=6 are consistent with the corrected expression, so the qualitative 16%-17% improvement claim survives, but the displayed formula should be corrected.","section":"Section 3.2, grid example"},{"comment":"The proof says that after setting k=2n-2, 'the maximum possible number of distinct vertex in P is n-2.' This is not justified and appears to be the wrong direction: the number of distinct vertices in a walk of length 2n-2 is at most n, not at most n-2, and since the cost formula decreases as k' increases, the upper bound on CNOT cost requires a lower bound on k', not an upper bound. Please either prove the needed lower bound or revise the argument for the claimed range 2nℓ-4ℓ+2 to 6nℓ-7ℓ+2.","section":"Appendix I, proof of Corollary 1"},{"comment":"Appendix A explicitly states that 'it is not known whether we can keep the same number of qubits or should we increase the number of qubits exponentially' when using the shallow circuit from [46,47]. This is a load-bearing caveat for the paper's stated application: the constructed circuit implements U_s, and the claim that this is a circuit for the quantum hashing transformation assumes that 'good' angles exist at the same qubit count n. The paper should state prominently that the CNOT-cost guarantees apply to the U_s circuit, and that equivalence to the hashing transformation for fixed n is an empirical assumption inherited from [46,47].","section":"Appendix A, quantum fingerprinting caveat"}],"minor_comments":[{"comment":"The line 'sw ap(vj, vj+1)' uses vj and vj+1 while the path was defined as P=(v_i1,...,v_ik); the notation should be consistent, e.g., sw ap(v_{i_j}, v_{i_{j+1}}).","section":"Appendix F, Algorithm 4, Step 5"},{"comment":"The heading 'Implementation of the ProcedureShor testP a ths for Shortest Paths Searching' contains a corrupted word; it should read 'ShortestPaths'.","section":"Appendix C heading"},{"comment":"The reported improvement is described variously as '16%-17%' and 'more than 16%'; for the q=7, t=6 example the improvement is 22/123 ≈ 17.9%, so the percentages should be harmonized.","section":"Abstract and Section 3.2"},{"comment":"The phrase 'CNOT coast' should be 'CNOT cost'.","section":"Section 3.2, grid example"},{"comment":"Reference [54] is listed as 'Rigetti Computing. Quantum computing, 1987'; if this is a website reference, it should include the URL and an accessed date, and the year appears to be a typo.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The paper is within scope for a quantum information/computation journal and addresses a practically relevant compilation problem. The main issue is the mismatch between Algorithm 4 and the proof of Theorem 1; it appears fixable by modifying the algorithm's exclusion rule or the theorem's counting, but as submitted the central cost claim is not established. The Appendix A qubit-count caveat should also be discussed explicitly in the main text. I recommend major revision rather than rejection, since the core approach is promising and the identified problems are localizable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: the paper has a good idea but a load-bearing bug. The 1-covering-path formulation is a nice variant of the shortest covering path, and using it to lay out the target qubit's walk in a shallow quantum-hashing circuit is worth taking seriously. The CNOT cost formula is plausible, and the grid example shows a real improvement over [49] once you correct the arithmetic.\n\nThe problem is that Theorem 1 is not proved for Algorithm 4 as written. The theorem counts one CR_y per non-path vertex plus k-1 pairs of CR_y+SWAP. But Algorithm 4, Step 3 (and Step 6) apply a single CR_y to any neighbor not in U, including vertices already on the 1-covering path. On a 4-cycle with path P=(v1,v2), executing the algorithm literally gives cR(v4,v1), cR(v2,v1)+SWAP, then in Step 6 cR(v1,v2) and cR(v3,v2) — four CR_y gates (cost 8) plus one SWAP (3), for 11 CNOTs, while the theorem predicts (3*2+2*2)-5+2=7. The extra CR_y appears because v1, the initial target, is never added to U. The same kind of surplus occurs on LNN chains. The fix may be simple — exclude path vertices in Steps 3 and 6, or initialize U with the path — but as submitted, the proof counts a different circuit from the one the algorithm builds.\n\nOther soft spots are minor by comparison. The grid algebra has a sign slip (the constant should be -4, not -3), though the 101 vs 123 numbers are consistent once corrected. And the whole construction inherits a caveat the authors state in Appendix A: the shallow U_s circuit's parameter set with the same qubit count is not proven to exist, only seen in experiments. That doesn't invalidate the circuit-synthesis contribution, but it means the practical hashing application rests on an unproven assumption.\n\nWhat's genuinely good: the exact DP for 1-SNSCP and the approximation via CDS plus Euler tour are clean, the comparison to [49] is honest, and the claimed reductions to LNN and Falcon architectures are sensible. This is a serious group extending their own line of work, and the extensive self-citation is transparent and not itself a flaw.\n\nRecommendation: send it to peer review, but mark it as needing major revision. The algorithm and Theorem 1 must be reconciled; once that is done, the paper could be solid. As submitted, the central claim is not yet established.","headline":"The 1-covering-path compilation idea is real, but the submitted Algorithm 4 does not match Theorem 1's CNOT count, so the central claim needs repair.","tokens_in":18973,"tokens_out":11706,"would_cite":false,"duration_ms":104016,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":["03.67.Lx"],"model":"deepseek-v4-flash","headline":"Quantum hashing circuits can be routed on any chip graph via a shortest 1-covering path.","keywords":["quantum hashing","quantum fingerprinting","CNOT cost","qubit connectivity graph","1-covering path","shallow circuit","quantum finite automata","circuit synthesis"],"falsifier":"For a small prime $p$ and target error $\\varepsilon$ for the $MOD_p$ automaton, search for a good parameter set of size $t=\\lceil(2/\\varepsilon)\\ln 2p\\rceil$ that satisfies the shallow circuit's angle constraints, then implement the generated circuit on a $7\\times6$ grid and count CNOTs: if no such parameter set exists the circuit cannot realize the hashing operator, and if the count differs from $(3k+2(n-k'))\\ell-5\\ell+2$ the cost formula fails.","tokens_in":17939,"feed_emoji":"⚛️","tokens_out":14910,"duration_ms":130336,"temperature":0.7,"pith_summary":"Quantum hashing, or quantum fingerprinting, encodes a string into a short quantum state that can be used to test equality with bounded error. This paper gives a circuit-rewriting algorithm that implements the repeated hashing operator on any device whose two-qubit gates are limited by a qubit connectivity graph. The idea is to walk the target qubit along a shortest non-simple path that covers every qubit either by visiting it or by being adjacent to it, a 1-covering path, applying controlled rotations to unused neighbors and swapping the target along the path. For $\\ell$ applications the CNOT cost is $(3k+2(n-k'))\\ell-5\\ell+2$, where $k$ is the path length and $k'$ is the number of distinct vertices visited. The result matters because CNOT gates are the expensive hardware operation, and the paper reports a 16-17% reduction over the earlier arbitrary-graph construction on grid architectures while matching specialized circuits on others.","feed_headline":"1-covering path cuts CNOT cost of quantum hashing by 17%","feed_subtitle":"Routing a target qubit along a shortest covering path beats existing arbitrary-graph compilers on grid chips","key_machinery":"The load-bearing object is the shortest non-simple 1-covering path (1-SNSCP): a walk that may revisit vertices and whose visited set, together with all neighbors of visited vertices, is the whole vertex set. The path supplies the route of the target qubit, so every qubit either receives a controlled rotation directly or acts as the control for one without long-range routing. The exact solver computes, for every subset $S$ of vertices and last vertex $v$, the shortest walk $D(S,v)$ that visits all of $S$ and ends at $v$, and keeps only those $S$ whose closed neighborhood is all of $V$; this costs $O((m+n)2^n)$. The approximate solver combines a connected dominating set with an Euler tour of the induced subgraph, giving a $2(\\ln\\Delta+3)$-approximation in $O((n+m)\\log n)$ time. The circuit-level economy is that a controlled rotation followed by a SWAP can be rewritten with three CNOTs instead of five, because two consecutive CNOTs cancel.","core_discovery":"The paper's central claim is that the shallow quantum hashing operator $U_s$ can be implemented on any connected qubit connectivity graph with CNOT cost $(3k+2(n-k'))\\ell-5\\ell+2$ for $\\ell$ applications, where $P=(v_{i_1},\\dots,v_{i_k})$ is the shortest 1-covering path and $k'$ is the number of distinct vertices in $P$. The construction begins with a shortest non-simple path whose visited vertices together with their neighbors cover all vertices. The target qubit starts at the first path vertex, and for each path edge the algorithm applies a controlled rotation to every neighboring vertex not yet used, then to the next path vertex, then swaps the target along the edge; on alternating applications the traversal direction reverses, which lets two adjacent controlled rotations merge. The paper proves this cost formula and shows that the generic method recovers the specialized LNN cost, matches the circuits for the 16-qubit and 27-qubit device graphs, and improves on the earlier arbitrary-graph method on grids, where a $7\\times6$ grid costs 101 CNOT gates instead of 123 for $\\ell=1$.","pith_inferences":["If the Appendix A caveat is settled negatively, meaning the shallow circuit's rotation angles require exponentially more qubits, the algorithm's saving becomes a trade-off of extra qubits for fewer CNOTs rather than an unconditional improvement.","The same target-qubit-walk routing could be applied to other CNOT-heavy one-target subcircuits, such as stages of phase estimation, though the paper demonstrates only hashing.","A polynomial-time exact 1-SNSCP solver for grid-like device graphs would make the optimization routine practical for large chips; the paper leaves that as an open question.","The length of the shortest 1-covering path could serve as a hardware design metric: chips whose connectivity graphs have shorter such paths are cheaper for this family of circuits."],"forward_implications":["For any connected connectivity graph, the CNOT cost lies between $2n\\ell-4\\ell+2$ and $6n\\ell-7\\ell+2$, with the exact value set by the shortest 1-covering path.","On linear nearest-neighbor chains, the generic construction reproduces the cost of the specialized LNN circuit, so a single algorithm covers that common layout.","On grids with odd rows and even columns, the saving over the earlier arbitrary-graph method is more than 16% for a $7\\times6$ grid, namely 101 CNOTs versus 123.","The method is demonstrated on the $MOD_p$ and $EQ_p$ quantum automata, and the cost formula scales with input length $\\ell$ because even-numbered applications reverse the path and merge gates.","The paper argues the same rewriting applies to any circuit made of long CNOT sequences, such as those in the textbook quantum Fourier transform."],"supporting_citations":[{"why":"Provides the previous arbitrary-connectivity-graph circuit whose CNOT cost is the comparison baseline, including the grid example.","marker":"[49]"},{"why":"Gives the LNN-architecture circuit that the generic method is shown to match exactly.","marker":"[48]"},{"why":"Introduces the shallow quantum hashing circuit and the parameter search that the new construction realizes; the Appendix A qubit-count caveat belongs to this line.","marker":"[46,47]"},{"why":"Provides the circuits for 16-qubit and 27-qubit device graphs that the generic method reproduces.","marker":"[6]"},{"why":"Defines the shortest covering path problem that the new 1-SNSCP problem modifies.","marker":"[55]"},{"why":"Supplies the $(\\ln\\Delta+3)$-approximation for connected dominating sets used in the approximate solver.","marker":"[63]"},{"why":"Underlies the Euler-tour path approximation that gives the 2-approximation for the second subtask.","marker":"[64–66]"},{"why":"Provide the good coefficient sets whose rotation angles are used in the controlled rotations.","marker":"[9,10]"},{"why":"Supplies the quantum fingerprinting equality-testing construction that the hashing circuit implements.","marker":"[11]"}],"fun_headline_variants":["1-covering path slashes CNOT cost in quantum hashing by 17%","New routing path cuts CNOT overhead for arbitrary qubit connectivity","Quantum hashing optimized with 1-covering path on any chip graph","Shortest covering path reduces CNOT count in quantum fingerprinting","Path-based routing improves quantum hashing on limited-connectivity hardware"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The construction assumes that the rotation angles required by the shallow circuit can be realized with the same number of qubits as the standard quantum hashing circuit; the paper states in Appendix A that it is not known whether this is possible, and if it is not, the CNOT savings do not implement the intended hash.","fun_headline_variants_meta":{"raw":{"variants":["1-covering path slashes CNOT cost in quantum hashing by 17%","New routing path cuts CNOT overhead for arbitrary qubit connectivity","Quantum hashing optimized with 1-covering path on any chip graph","Shortest covering path reduces CNOT count in quantum fingerprinting","Path-based routing improves quantum hashing on limited-connectivity hardware"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000589,"raw_usage":{"total_tokens":2814,"prompt_tokens":1045,"completion_tokens":1769,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":661,"completion_tokens_details":{"reasoning_tokens":1675}},"tokens_in":661,"tokens_out":1769,"duration_ms":13739,"temperature":1.0,"reasoning_tokens":1675,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T22:52:38.121860+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a small prime $p$ and target error $\\varepsilon$ for the $MOD_p$ automaton, search for a good parameter set of size $t=\\lceil(2/\\varepsilon)\\ln 2p\\rceil$ that satisfies the shallow circuit's angle constraints, then implement the generated circuit on a $7\\times6$ grid and count CNOTs: if no such parameter set exists the circuit cannot realize the hashing operator, and if the count differs from $(3k+2(n-k'))\\ell-5\\ell+2$ the cost formula fails.","supporting_citations":[{"cited_title":"Approximation algorithms for connected domi- nating sets.Algorithmica, 20:374–387, 1998","cited_arxiv_id":null,"evidence_quote":"Supplies the $(\\ln\\Delta+3)$-approximation for connected dominating sets used in the approximate solver."}],"review_version":1}