{"id":"385eb2fd-99f7-4c41-ba78-8b213e2e775b","arxiv_id":"2608.08765","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A depth-aware heuristic scheduler, Bona, automatically reuses dirty ancilla qubits in quantum circuits, reducing dirty-ancilla usage by up to 99% on tested benchmarks, with a claimed proof that the general borrowing problem is NP-hard.","lead":"This paper presents Bona, the first automated scheduler for reusing 'dirty' ancilla qubits in quantum circuits, and claims a proof that optimally scheduling such borrowing is NP-hard. The tool is evaluated on parallel quantum walk, Shor's algorithm, and component circuits, showing large width reductions with bounded depth overhead.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Appendix C's key claim that dirty paths e[i,m]x can only splice into e[0,i-1]y is not proved; arbitrary splicing order makes it locally false, so the NP-hardness reduction may be unsound.","rationale":"The paper makes two central claims: the dirty-qubit borrowing problem is NP-hard, and the Bona scheduler nearly eliminates dirty ancillas with controlled depth overhead. The Bona contribution is well supported: the Endpoint DAG abstraction is clean, Theorem 4.4 gives a plausible sound-and-complete correspondence, Theorem 6.1 proves semantic soundness of the scheduler, and the code is available. The experimental evaluation is substantial, though the abstract overstates the PQW depth advantage: in Table 1, for PQW70_6, Bona's final depth (30175) is actually slightly larger than Decross's (29184), so the claim of \"significantly smaller circuit depth\" should be qualified to \"at most scales,\" as the body text does.\n\nThe load-bearing concern is the NP-hardness proof. The reader's weakest-assumption diagnosis is correct: the converse of the Appendix C reduction depends on an invariant about splice order that is not derived. The invariant is not even true for individual legal splice steps, as shown by the e2 s into e0 b example above. The proof's sentence \"Since all paths having the form e[0,j-1]y, 1<=j<=i-1 have been spliced\" assumes an ordering of splices that Complete-Borrowing does not impose. The theorem may be repairable via a counting or rank argument, but the manuscript does not supply one. As written, the NP-hardness result is unproven, which affects the paper's headline theoretical contribution.\n\nBecause the flaw is in the proof rather than in the tool or its evaluation, conditional acceptance pending a repaired proof remains the appropriate verdict. The reader's CONDITIONAL verdict should not be changed.","tokens_in":35605,"tokens_out":21028,"duration_ms":234242,"concrete_test":"Implement edge-splicing for the Appendix C construction and exhaustively search all valid splice sequences for small UDG instances (e.g., all UDGs with up to 3 vertices and 2 uncertain edges, covering both uncertain-tail and uncertain-head cases). For each complete borrowing sequence that maps all dirty ancillas, check: (a) does any step splice a dirty path e[i,m]x into a working path e[0,k-1]y with k e0 e2 s b satisfies the unreachable condition and is a legal edge-splicing step. Thus the claimed invariant is false for the individual steps the reduction must reason about.\n\nThe proof needs an additional argument that no complete borrowing sequence contains such a crossing. One possible repair is a rank/counting argument: each index group i creates exactly as many dirty paths as short working paths with prefix e[0,i-1], and the lowest group cannot use the long vertex paths, forcing group 1 to consume its own paths, then group 2, and so on. But the manuscript does not provide this argument; it assumes the conclusion. If the claim fails, the extraction of a UDG realization from the final DAG is not well-defined, and the reduction DAG-in-UDG <= Complete-Borrowing is unsound, leaving the NP-hardness headline unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper formalizes dirty-qubit borrowing in quantum circuits via a small imperative language with explicitly scoped borrow statements and a set of semantics-preserving transitions. It introduces the Endpoint DAG abstraction, proves a step-correspondence theorem between edge-splicing in the DAG and circuit-level borrowing, and claims NP-completeness of the Complete-Borrowing problem through a reduction from DAG-in-UDG. The authors then present Bona, a depth-aware heuristic scheduler, and evaluate it on parallel quantum walk, Shor's algorithm, component-level circuits, and randomly composed RevLib circuits, reporting reductions of roughly 99% in dirty-ancilla usage, moderate depth overheads, and a depth advantage for dirty-ancilla implementations in parallel circuits.","tokens_in":35878,"tokens_out":11403,"duration_ms":132510,"significance":"The Endpoint DAG model and the step-correspondence theorem are a clean conceptual contribution, and the paper is the first to provide an automated scheduler specifically for dirty-ancilla borrowing. The evaluation is broad, includes realistic algorithm instances, and the data-availability statement makes the implementation reproducible, which is a notable strength. The claimed NP-hardness result is central to the paper's theoretical contribution, and the current proof has a load-bearing gap; until that gap is repaired, the hardness results are conditional. If the proof can be completed and the scheduler results are reproducible, the paper would be a solid contribution to quantum circuit compilation.","major_comments":[{"comment":"The central claim that a dirty path e[i,m]x can only splice into a working path e[0,i-1]y is not established. The induction step assumes that all paths e[0,j-1]y with 1 <= j <= i-1 \"have been spliced\", but Complete-Borrowing permits arbitrary splicing order and the unreachable condition of Definition 4.3 does not enforce the index ordering. In the construction itself, a working path e[0,j-1]y with j < i and a dirty path e[i,m]x satisfy the two unreachable tests whenever y is not reachable to x: e_i cannot reach e_{j-1} because all e-edges go forward, and the constructed paths contain no edges from the original vertices back to the e-chain. Thus the crossing splice is locally legal under the paper's own rules. To make the reduction sound, the proof needs an additional argument, for example a rank or counting argument showing that every complete borrowing sequence must splice in nondecreasing index order, and no such argument appears. Without it, the extraction of a UDG realization from the final DAG T' is not well-defined, and Theorem 5.5 is unproven.","section":"Appendix C, proof of Theorem 5.5"},{"comment":"The NP-hardness of Complete-Borrowing is the only route given for Corollary 5.6 and for the width-then-depth and depth-then-width statements. Since the proof of Theorem 5.5 is incomplete (see previous comment), these hardness claims are currently unsupported. In addition, the depth-then-width reduction is only sketched: appending an \"extremely long\" dummy working qubit that shares gates with every dirty ancilla is asserted to lock the optimal depth, but no argument is given that the construction preserves the width-optimization instance or that the appended gates do not create new borrowing opportunities. The authors should provide a complete reduction or explicitly state these as conjectures.","section":"Section 5.2, Corollary 5.6 and the Complexity Landscape"},{"comment":"The abstract's phrase \"controlled depth overhead\" is stronger than what Table 1 shows for the main PQW results. For the max-ancilla versions, Recycle+Bona increases depth by 101%–330%, while the much smaller overheads of 1%–18% are achieved only after manual preprocessing (the Manual+Bona columns). The claim is defensible if \"controlled\" is interpreted relative to the large width reduction, but the current wording invites a stronger reading. Please either report the average with the manual-preprocessing qualification stated clearly or adjust the wording in the abstract and introduction.","section":"Section 7.2.1, Table 1"}],"minor_comments":[{"comment":"The paper does not state whether paths of length zero are allowed in the definition of reachability. The unreachable condition in Definition 4.3 and Lemma B.1 rely on this distinction when fst(d) equals u or v equals lst(d), since a self-loop would then be created. Please clarify that reachability is reflexive in these arguments.","section":"Section 2.1, Definition of reachability"},{"comment":"There are typos: \"grantee\" should be \"guarantee\", and \"loop\" should be \"cycle\". The wording in the last paragraph, \"Then, for every literal y_j in c_j, y_j x_false c c_j forms a path\", would be clearer if the path were written as y_j -> x_false -> c -> c_j -> y_j.","section":"Appendix C, proof of Lemma 5.4"},{"comment":"The name \"Decross\" appears in Table 1 while the reference is \"DeCross et al.\"; please use a consistent spelling. Also, the notation \"TrivD\" and \"Manual+TrivD\" is used without an explicit definition in the experimental setup; a one-sentence description of the TrivD baseline would improve readability.","section":"Throughout"},{"comment":"The implementation appendix describes a restriction that boundary nodes of dirty ancillas are not exposed during the initial sweep, so that dirty-dirty recycling is postponed. This behavior is not present in Algorithm 1 in Section 6.2, which pools all edges. Please state explicitly that Algorithm 1 is a graph-theoretic abstraction and that the OpGrid implementation adds this policy, so the reader can match the algorithm description to the implementation.","section":"Appendix D.2"}],"recommendation":"major_revision","confidential_remarks":"The main risk is the NP-hardness proof in Appendix C. The rest of the paper, especially the Endpoint DAG model and the empirical evaluation, appears sound and well presented. If the authors can supply the missing rank/counting argument for the splice-order invariant, the paper would likely be acceptable; otherwise the theoretical contribution should be weakened accordingly. I would not reject solely on this gap, because the issue is local to one proof and may be fixable within the manuscript's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The practical part of this paper is genuinely useful. Bona is the first automatic scheduler for dirty-ancilla borrowing that I know of, and the Endpoint DAG abstraction is a clean way to turn borrowing into edge-splicing. The step-correspondence theorem (4.4) is proved in the appendix and looks right; the frozen-topology linear-time result (5.1) is a nice contrast; and the soundness proof for Bona (6.1) is solid. The evaluation across PQW, Shor, component benchmarks, and random parallel compositions is thorough, with code available. The width reductions are impressive.\n\nThe soft spot is the NP-hardness proof in Appendix C. The claim that a dirty path e[i,m]x can only splice into a working path e[0,i-1]y is not true as a local statement about legal edge-splicing steps. The stress-test's example works: with a suitable UDG, d_2 can legally splice into a W_1 path (e0 y) if the endpoint reachability conditions hold. The proof justifies the claim by saying all lower-indexed paths have already been spliced, but that is exactly what needs to be shown for arbitrary complete borrowing sequences. This looks circular as written. I think the theorem is probably true and repairable: a counting plus reachability argument should force D_1 to use W_1, then D_2 to use W_2, etc., because a dirty path whose first node is e_i cannot be hosted on a working path that contains any e_j with j >= i. But that argument is not in the paper. As it stands, the NP-hardness headline is not rigorously supported.\n\nMinor: the abstract's PQW claim overstates things. At the largest completed instance (PQW70_6), Bona's depth (30175) is slightly larger than Decross's (29184), so 'significantly smaller depth' holds at most scales, not universally. Also, the dirty vs clean comparison compares different gate decompositions; that is a legitimate end-to-end comparison, but the paper could be clearer about it.\n\nWho is this for? Researchers in quantum compilation and ancilla management will get value from the scheduler and the model. The NP-hardness question is less settled until the proof is repaired. I would send it to peer review and ask for a revised Appendix C and a toned-down abstract claim.","headline":"Good practical scheduler with an elegant graph model, but the NP-hardness proof has a gap that should be fixed before the theory headline is fully trusted.","tokens_in":36489,"tokens_out":19792,"would_cite":true,"duration_ms":183221,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","81P68"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper formalizes dirty-qubit borrowing, proves the scheduling problem NP-hard, and presents Bona, a depth-aware heuristic that reuses nearly 99% of dirty ancillas on benchmark circuits while keeping depth overhead controlled.","keywords":["dirty ancilla","qubit borrowing","circuit width optimization","quantum circuit depth","NP-completeness","edge splicing","Endpoint DAG","ancilla scheduling"],"falsifier":"Take a small unsatisfiable 3-SAT formula, build the Endpoint DAG exactly as in the reduction, and enumerate all valid edge-splicing sequences; if any sequence maps every dirty ancilla while keeping the graph acyclic, the reduction's claim that unsatisfiability forces a failure is wrong and NP-hardness collapses. A weaker probe: on a satisfiable instance, find a complete borrowing assignment in which a dirty path is spliced into a working path not of the prescribed lower-indexed form, which would contradict the order-dependence lemma.","tokens_in":35360,"feed_emoji":"⚛️","tokens_out":10372,"duration_ms":102716,"temperature":0.7,"pith_summary":"Dirty ancillas are qubits borrowed from temporarily idle wires, used without knowing their initial state, and then restored, letting a compiler shrink circuit width (the number of qubits the computation needs at once). This paper tries to establish that dirty-ancilla management can be automated: it defines a formal transition system for borrowing, proves the scheduling optimization NP-hard, and presents Bona, a depth-aware heuristic scheduler. On benchmark circuits Bona eliminates 99–100% of dirty ancillas in parallel quantum walk and cuts Shor's dirty ancillas from 192–6400 down to 3–20, with depth overhead at most 20%. In parallel circuits the paper finds a scheduling advantage: after optimization, dirty-ancilla circuits match clean-ancilla width while ending up significantly shallower. If right, this makes dirty ancillas a compiler-managed resource rather than a hand-crafted trick.","feed_headline":"Bona reuses 99% of dirty ancillas in quantum circuits","feed_subtitle":"The scheduling problem is NP-hard; a depth-aware heuristic still matches clean-ancilla width with lower depth.","key_machinery":"The load-bearing object is the Endpoint DAG, a directed acyclic graph whose edges trace each qubit's temporal flow through the circuit, with dirty ancillas marked as distinguished qubits. Borrowing is reformulated as edge-splicing: to borrow a dirty ancilla $d$ into an idle edge $(u,v)$, cut $(u,v)$ and insert $d$'s operation path between $u$ and $v$; the step is valid exactly when $\\mathrm{fst}(d)$ is not reachable from $u$ and $v$ is not reachable from $\\mathrm{lst}(d)$, which prevents cycles. This characterization carries both halves of the paper: it makes the NP-hardness reduction tractable, and it gives Bona its depth-aware selection rule, a look-ahead cost $c_{\\Delta d}$ estimating how much a splice stretches the critical path, with zero-cost soft splices handled through an interval pool and costly hard splices through a graph-wide scan.","core_discovery":"The central claim is that deciding whether every dirty ancilla can be mapped away—the Complete-Borrowing problem—is NP-complete, so exact optimal scheduling of width and depth is intractable in general, yet the same graph formulation supports a near-optimal practical scheduler. The paper proves hardness by reducing 3-SAT through a new graph problem, DAG-in-UDG, to borrowing on the Endpoint DAG, and shows depth-aware variants of the optimization are NP-hard as well. For practice, Bona greedily splices dirty ancillas into idle edges, preferring zero-depth soft borrows found through an interval pool and reserving graph-wide hard searches for the rest, and the paper proves each splice satisfies the unreachable condition, so the output circuit is semantically equivalent to the input. Empirically, Bona reduces dirty-ancilla usage by nearly 99% on average, matches manual optimization in width on three of four component benchmarks, and on parallel quantum walk attains clean-ancilla width with substantially smaller depth.","pith_inferences":["Given the NP-hardness result, adding hardware-level constraints such as routing or mid-circuit reset can only make scheduling harder, so physical-level dirty-ancilla managers will likely also need heuristics of Bona's kind.","Bona's look-ahead cost approximates the true depth change rather than measuring it; comparing it against brute-force optimal schedules on small circuits could measure the approximation gap and guide a better cost function.","The Clean-then-Dirty order encodes a general allocation principle—serve the most constrained requests first—that could carry over to other flexible compilation resources, such as reusable mid-circuit measurement slots.","The measured crossover between dirty and clean schemes at a certain parallelism level is a testable prediction: on hardware with mid-circuit measurement and reset, dirty borrowing should beat clean recycling in post-optimization depth once parallelism exceeds that threshold."],"forward_implications":["Because Complete-Borrowing is NP-complete, exact optimal dirty-ancilla scheduling is out of reach for large circuits, and heuristic schedulers such as Bona are the practical route.","A compiler can run a clean-ancilla optimizer first and then Bona, since dirty borrowing fills idle gaps that clean recycling leaves behind; this Clean-then-Dirty order reproduces manual optimization on most tested components.","On parallel quantum walk and randomly composed parallel circuits, dirty-ancilla circuits optimized with Bona reach essentially the same width as clean-ancilla circuits but end up shallower, which is direct evidence that dirty ancillas are not merely a fallback.","Every splice Bona performs obeys the unreachable condition, so its output is guaranteed to be a valid circuit semantically equivalent to the input.","If topological reordering is frozen, the minimal width is computable in linear time by a structural recursion, isolating dynamic reordering as the source of hardness."],"supporting_citations":[{"why":"supplies the clean-ancilla recycling solver used as the first pipeline pass and as a baseline for width and depth comparison.","marker":"[21]"},{"why":"provides the clean-ancilla qubit-reuse compilation baseline that the dirty-ancilla pipeline is compared against on parallel benchmarks.","marker":"[9]"},{"why":"gives the dirty-ancilla data-lookup oracle construction underlying the parallel quantum walk benchmarks.","marker":"[27]"},{"why":"provides the modular exponentiation implementation and manual dirty-ancilla reuse strategy used in Shor's algorithm benchmarks.","marker":"[16]"},{"why":"describes the parallel quantum walk block-encoding structure that forms the benchmark family.","marker":"[48]"},{"why":"supplies the multi-controlled-NOT and incrementer component circuits used as component-level benchmarks.","marker":"[12]"},{"why":"supplies the reversible-circuit benchmark pool used for randomly composed parallel test circuits.","marker":"[45]"},{"why":"formalizes the safe-use semantics of dirty ancillas that the paper adopts as its safety condition.","marker":"[41]"},{"why":"introduces the foundational dirty-ancilla elementary-gate constructions that define the technique.","marker":"[4]"}],"fun_headline_variants":["Bona solves dirty ancilla borrowing with NP-hard proof and 99% reuse","NP-hard proof behind Bona's 99% dirty-ancilla reuse","Depth-aware heuristic matches clean widths while reusing 99% dirty ancillas","Bona proves dirty borrowing NP-complete, yet reuse hits 99%"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The NP-hardness proof depends on a fixed splice order: it assumes a dirty path can only enter one specific position because all earlier positions are already filled, and if valid borrowings can occur in a different order, the constructed hard instances might have unintended complete solutions and the hardness collapse.","fun_headline_variants_meta":{"raw":{"variants":["Bona solves dirty ancilla borrowing with NP-hard proof and 99% reuse","NP-hard proof behind Bona's 99% dirty-ancilla reuse","Depth-aware heuristic matches clean widths while reusing 99% dirty ancillas","Bona proves dirty borrowing NP-complete, yet reuse hits 99%"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.0006,"raw_usage":{"total_tokens":2818,"prompt_tokens":975,"completion_tokens":1843,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":591,"completion_tokens_details":{"reasoning_tokens":1759}},"tokens_in":591,"tokens_out":1843,"duration_ms":13721,"temperature":1.0,"reasoning_tokens":1759,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T04:25:48.461576+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small unsatisfiable 3-SAT formula, build the Endpoint DAG exactly as in the reduction, and enumerate all valid edge-splicing sequences; if any sequence maps every dirty ancilla while keeping the graph acyclic, the reduction's claim that unsatisfiability forces a failure is wrong and NP-hardness collapses. A weaker probe: on a satisfiable instance, find a complete borrowing assignment in which a dirty path is spliced into a working path not of the prescribed lower-indexed form, which would contradict the order-dependence lemma.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"describes the parallel quantum walk block-encoding structure that forms the benchmark family."},{"cited_title":"Wille, D","cited_arxiv_id":null,"evidence_quote":"supplies the reversible-circuit benchmark pool used for randomly composed parallel test circuits."}],"review_version":1}