{"id":"628a402b-40b5-45de-a4f7-49464a76644f","arxiv_id":"2608.07973","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A compilation framework from the new language RQIMP to the existing RQC++ language compiles recursive quantum oracles with quantum-controlled recursion and adds recursion-aware automatic uncomputation.","lead":"This paper presents a compiler design that turns high-level recursive definitions of quantum oracles, whose recursion is controlled by quantum data, into lower-level reversible quantum programs. A smart generalist might read it to see how quantum algorithms that need recursive subroutines, such as graph traversal, could be specified more simply and compiled with controlled time and memory overhead.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"High-level transformations (App. D.1) deliberately relax the RQIMP type system, so Theorem 6.2, stated for well-typed RQIMP, may not cover the program the compiler actually runs; the proof's typing invariants could fail on transformed programs.","rationale":"I agree with the reader's CONDITIONAL verdict and their observation of a tension between Section 5.1 and Appendix D.1, but I identify the type-system relaxation as the single most load-bearing concern for the central claim. The reader's weakest_assumption focuses on the RQC++ extension (quantum variables as procedure parameters); that is a real concern, but it concerns the target-language foundation and is defended by an informal but plausible address-index argument. The type-system relaxation, by contrast, directly breaks the stated hypothesis of Theorem 6.2: the theorem quantifies over well-typed RQIMP programs, while the compiler compiles transformed programs that are admitted by the authors to be outside that type system. All of the typing-based invariants used in the compilation algorithms and in the proof sketch (first-time writes, global-variable discipline, return-mode restrictions) are established for the well-typed fragment; if they fail on the transformed program, the correctness proof has no foundation. This is not merely a missing proof detail but an identifiable mismatch between theorem statement and compilation pipeline. The concrete test is decisive: it can show that the transformed program is un-typeable, forcing either an extra inlining pass or a re-stated theorem. The paper has independent strengths: the running example is internally coherent, the QFT-based arithmetic circuits are standard, and the deferred-cleanup strategy for linear recursion is plausible and avoids the exponential recomputation described in Section 2. These strengths support a conditional acceptance, but the type-system gap must be resolved before the central claim can be taken as established.","tokens_in":61169,"tokens_out":8888,"duration_ms":93805,"concrete_test":"Apply the RQIMP type checker from §3.2 to the output of the §5.1/Appendix D.1 transformations. Concretely: write a minimal RQIMP program containing a C-mode conditional with a non-trivial branch (e.g., if x<y { b := true } { b := false } followed by use of b); run the branch-extraction transformation of D.1; then attempt to type the resulting program with Table 3/Table 7. The extraction introduces a procedure returning a C-mode variable, which fails the rule requiring return mode Q. If no well-typed derivation exists, check whether the Appendix F lemmas (F.19/F.53/F.63) are formulated for this relaxed grammar; if they are not, Theorem 6.2 does not apply to the program the compiler actually processes, and the paper must either add an inlining pass before compilation or extend the correctness proof to the relaxed language.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central correctness theorem (Thm 6.2) is stated for every well-typed RQIMP source program, but the compiler never compiles the well-typed program directly: Section 5.1 first applies high-level transformations, and Appendix D.1 explicitly says the type system is \"temporarily relaxed\" during these transformations. In particular, branch extraction for C-mode conditionals generates procedures whose return values are C-mode variables, which the RQIMP function-declaration rule (Table 7) forbids (\"functions are only allowed to return Q-mode variables\"). The paper says such calls \"can be inlined afterwards\" (D.1), but the compilation pipeline (Compile_Prog and descendants) compiles the transformed program directly, with no inlining pass before compilation. Therefore the actual input to the compiler is outside the well-typed fragment for which the type-soundness theorems (3.3, 3.4) and the typing-based invariants used throughout Section 5 (e.g., \"the source type system guarantees that mvq(s) is written for the first time\" in §5.6, and the global-variable discipline of §3.2) are proven. If any of these invariants fails on the transformed program, the key lemmas (F.19, F.53, F.63) may not go through. The review copy's Appendix F is truncated before these lemmas, so the reader cannot verify that they cover the relaxed grammar. This is a mismatch between the theorem's hypothesis and the compiler's actual input, directly threatening the semantic-preservation claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents ReOC, a compilation framework that translates programs in a new imperative source language RQIMP into recursive quantum programs in RQC++, with the goal of supporting quantum-controlled recursive oracles. The compiler uses an indexed static-register discipline to isolate live quantum variables across recursion layers and a recursion-aware uncomputation strategy that defers cleanup of recursive-call temporaries while cleaning non-recursive temporaries eagerly. The paper claims a semantic-preservation theorem (Theorem 6.2) covering termination equivalence, output correspondence, and correct uncomputation, as well as linear recursion-depth overhead for linear recursion in Section 4.","tokens_in":61384,"tokens_out":5113,"duration_ms":63836,"significance":"If the main claims hold, this addresses a genuine gap in quantum oracle compilation: structured high-level specifications of recursively defined oracles with quantum-dependent control flow, compiled to a target language with existing backend support. The paper is honest about its scope, makes no empirical claims, and avoids fitted parameters; the resource analysis is explicitly parameterized by per-layer costs, and the correctness statement includes uncomputation of temporary variables, which is a strong and falsifiable claim. The main value is conceptual: separating shareable from non-shareable registers and choosing cleanup timing by variable origin is a plausible and reusable design. However, the significance is conditional on closing the gap between the theorem's hypotheses and the compiler's actual input, and on providing the deferred proofs.","major_comments":[{"comment":"There is a load-bearing mismatch between the correctness theorem and the program actually compiled. Theorem 6.2 is stated for every well-typed RQIMP program, but the compilation pipeline in Figure 9 and Algorithm 1 first applies high-level transformations and then compiles the transformed program directly, with no separate inlining pass before Compile_Prog. Appendix D.1 explicitly says that C-mode conditionals are turned into non-recursive function calls that may return classical variables, even though the function-declaration rule in Table 7 restricts return values to Q-mode; the remark that such calls \"can be inlined afterwards\" is not reflected in the described pipeline. Since the type-soundness theorems in Section 3.4 and the typing-based invariants used in Section 5.6 (e.g., that mvq(s) is written for the first time) are proved for the original grammar, the paper does not establish that the input to the compiler satisfies the hypotheses of Theorem 6.2.","section":"Section 5.1, Appendix D.1, Theorem 6.2"},{"comment":"The target-language extension is not given a precise semantics. Every generated target program uses quantum variables as procedure parameters, but the formal operational semantics of RQC++ in Appendix B.3, especially rule (RC), substitutes formal parameters inside \"begin local u:=t; C end\" and rule (AS) assigns only classical expressions to classical variables. The paper's call-by-reference justification is an informal argument about compiling quantum arguments to classical address/index information, not a conservative-extension theorem for the defined semantics. Consequently, the statement that C_main is an RQC++ program whose semantics is covered by Theorem 6.2 is not well defined until this extension is formalized or shown to be an abbreviation of the original language.","section":"Appendix B, Section 4"},{"comment":"The advertised resource guarantee for linear recursion is not proved. The text asserts that additional space is bounded by (N+(n-1)K)+n+M and that time overhead is linear in recursion depth parameterized by per-layer costs, but N, K, and M are described only informally and no theorem in Section 6 or in the appendices states or proves such a bound in terms of the compilation algorithms of Section 5. Theorem 6.2 is purely a semantic equivalence theorem and contains no complexity clause. The authors should either state and prove a formal resource theorem or explicitly label the Section 4 analysis as heuristic rather than a contribution.","section":"Section 4, Section 6"},{"comment":"The detailed proof of the central correctness claim is not available for verification. The proof sketch of Theorem 6.2 depends on Theorem F.19, Lemma F.62, and the arguments in Appendix F.7, but the submitted Appendix F ends inside the notation section F.1, so these statements are never given. As received, the manuscript's main soundness claim rests on lemmas that the reader cannot check. The full appendix should be included, and the key lemmas on which the main theorem depends should be stated in the main text.","section":"Appendix F"}],"minor_comments":[{"comment":"The RQC++ program in Figure 14 shows \"Fsum(p1,r1,0));\" with an unbalanced parenthesis; this should be corrected for consistency with the indexed call in Figure 4.","section":"Figure 14"},{"comment":"The encoding E(σ,ρ) is written as a pair containing σ_c, but the text then says \"we omit σ_c and focus solely on the quantum part\"; the treatment of classical-mode variables in the target-state correspondence should be made explicit, otherwise the equality in the definition of ≈ is ambiguous.","section":"Section 6"},{"comment":"The typing rule for \"for\" loops in Table 3 requires the loop variable and bound to be in Q-mode, while Section 3.1 says that loops depending only on classical data are compiled by unrolling; the paper should clarify how classical loops are typed before the high-level transformations are applied.","section":"Table 3, Section 3.1"},{"comment":"The flag values 0, 1, 2 are introduced in Section 4 as cleanup-timing annotations but are formally attached to variable nodes only later in Section 5.2, where the relationship between a variable's flag and the flag of its composite node is defined; consolidating these definitions would avoid the impression that the meaning of the flag shifts between 'origin of the variable' and 'cleanup timing'.","section":"Section 4, Section 5.2"}],"recommendation":"major_revision","confidential_remarks":"The strongest issue is the first major comment: the theorem's hypothesis does not match the compiler's actual input unless the transformations are shown to be type-preserving or the theorem is extended to the relaxed grammar. This is fixable by adding a proof that the transformed program is in the fragment covered by the correctness theorem, or by inserting an inlining pass and proving its correctness. I recommend major revision rather than rejection because the proposed design is coherent and the central claim is defensible if these gaps are closed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take: the design is promising, but the correctness theorem has a gap the authors should fix. The direction—compiling recursive oracles with quantum control flow from a structured source language into RQC++—is genuinely useful, and the two core techniques (indexed static-register isolation, flag-based uncomputation) are sensible. The linear-recursion overhead argument is plausible, and the case studies (sum, union-find, DFS) show the intended scope.\n\nThe main soft spot is that Theorem 6.2 is stated for well-typed RQIMP programs, but the compiler first applies high-level transformations that the paper's own Appendix D.1 says 'temporarily relax' the type system. In particular, branch extraction for C-mode conditionals can generate procedures that return C-mode variables, which the RQIMP type system forbids. The paper says these calls can be inlined afterwards, but the compilation pipeline compiles the transformed program directly, with no inlining pass before Compile_Prog. So the actual input to the compiler may be outside the well-typed fragment for which the type-soundness lemmas and the proof of Theorem 6.2 are established. That's a real mismatch between the theorem's hypothesis and the compiler's behavior. It looks fixable—either by extending the correctness proof to the relaxed grammar, or by inserting the promised inlining pass—but as written the proof doesn't cover the program that actually gets compiled.\n\nThere's a second issue: the main proof is a sketch, with key lemmas (F.19, F.62, etc.) deferred to an appendix that wasn't in the review copy. For a PL paper, that is a serious handicap. I can't verify the central claim from the main text, and that makes the correctness result conditional. The paper is otherwise honest about its limitations: it lists machine-checked verification as future work, and the case studies include explicit caveats about the DFS cleanup. The resource analysis is parameterized, not overclaiming.\n\nWho should read it: people working on quantum control flow and reversible compilation, particularly recursion and uncomputation. The paper deserves a serious referee rather than a desk reject, but I'd expect major revision: complete the proof, resolve the type-system mismatch, and ideally add an implementation or machine-checked key lemmas before it's publishable.","headline":"Promising design for compiling recursive quantum oracles, but the main correctness theorem doesn't cover the program the compiler actually runs.","tokens_in":62004,"tokens_out":5166,"would_cite":false,"duration_ms":49652,"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":"This paper presents a compiler that turns classical-style recursive oracle specifications into reversible quantum programs with provably correct, recursion-aware uncomputation.","keywords":["quantum oracles","reversible compilation","recursive quantum programs","quantum control flow","uncomputation","RQIMP","RQC++","register reuse"],"falsifier":"Take a well-typed RQIMP program (for instance the sum oracle), run its compiled RQC++ target through the QRM backend on every basis input, and check that each temporary annotated for cleanup returns to $|0\\rangle$ after execution and that for linear recursion the number of recursive invocations grows linearly with input depth; any residual entanglement of temporaries, any violation of RQC++'s well-formedness conditions in a generated declaration, or an exponential invocation count would refute Theorem 6.2 or the linear-overhead claim.","tokens_in":60817,"feed_emoji":"⚛️","tokens_out":15620,"duration_ms":142090,"temperature":0.7,"pith_summary":"The paper claims that recursive quantum oracles—programs whose recursion path depends on quantum data in superposition—can be written in a classical-style imperative language and compiled automatically into reversible quantum programs. The compiler, ReOC, translates the source language RQIMP into RQC++, an existing quantum language with quantum control flow, and takes over the two tasks that make manual RQC++ programming hard: isolating quantum registers across recursion layers and uncomputing temporary variables. Its indexed static-register discipline turns live variables into indexed registers that each recursive call increments, so layers never collide, while its recursion-aware cleanup defers uncomputation of recursive-call temporaries (avoiding exponential recomputation) and eagerly cleans other temporaries (controlling space). For linear recursion the paper proves time and space overhead linear in recursion depth. The central result, Theorem 6.2, is a mathematical proof that every well-typed RQIMP program and its compiled target are semantically equivalent, with all temporary quantum variables correctly restored.","feed_headline":"Recursive oracles compile with cleanup linear in recursion depth","feed_subtitle":"Write oracles in classical style; the compiler adds register isolation and recursion-aware uncomputation automatically.","key_machinery":"The machinery is a compilation pipeline with three load-bearing components. RQIMP, the source language, is a typed imperative language with C/Q modes; its type system enforces single assignment, forbids non-main functions from modifying globals, and keeps globals read-only or write-only in main, all of which the correctness proof needs so that target procedures are well-formed and cleanup is reversible. The indexed static-register discipline is the storage mechanism: an index supplier $\\iota$ issues index variables, live quantum variables are rewritten as subscripted registers of the form $q[i]$, recursive calls pass $i+1$ so successive layers touch disjoint slots, and independent index variables are assigned to distinct recursive paths; variables already cleaned stay unsubscripted and are reused. The variable dependency graph is the cleanup scheduler: each variable node carries a flag (0 for eager cleanup of non-recursive temporaries, 1 for end-of-layer cleanup in non-linear recursion, 2 for cleanup postponed to the outermost call in linear recursion), mutually dependent variables are merged into composite nodes cleaned as a unit, and each node stores a cleanup circuit whose inverse restores it to $|0\\rangle$. On top of these, Theorem 6.2 states the main claim: for every well-typed RQIMP program, Compile_Prog yields a target with $C_{\\mathrm{main}} \\approx s_{\\mathrm{main}}$, proved by relating $k$-th syntactic approximations of the two programs.","core_discovery":"A programmer writes a recursive oracle in RQIMP—with quantum-mode guards, loops, and mutual recursion—and the compiler returns an RQC++ program whose observable behavior matches the source on every input. The paper's correctness statement is semantic equivalence between the target and source main procedures: for every initial source state, the two programs either both diverge or both terminate with the encoded result, and every auxiliary quantum register ends in $|0\\rangle$. The proof works by compiling under a live-variable discipline: at each recursive call the compiler converts the caller's live quantum variables into subscripted form with incremented indices, guaranteeing disjoint register slots per layer, and it annotates each temporary with a cleanup flag that decides whether uncomputation is eager (non-recursive statements), deferred to the end of a layer (non-linear recursion), or deferred to the outermost call (linear recursion). The running example is the sum oracle, whose naive per-layer uncomputation would recompute the recursive subcall at every layer and grow exponentially; the compiled target defers cleanup of those temporaries to the top level and keeps the invocation count linear.","pith_inferences":["The selective-cleanup recipe (defer only recursive-call temporaries, eagerly clean everything else, index only live variables) is a general design principle that could be adopted by other quantum languages with automatic uncomputation, even outside the RQC++/QRM setting; the paper itself does not claim this transfer.","The paper proves its linear-overhead bound as a per-layer accounting argument but lists an implementation as future work, so the natural test of the resource claims is to build the pipeline on the QRM backend and measure invocation counts and register footprints for the sum, power, find, and DFS examples; that measurement does not yet exist.","The paper's own case study notes that its per-layer cleanup for non-linear recursion can still risk exponential time in branch-heavy recursion such as DFS on a chain; a cost-model-driven policy that picks cleanup timing per call site from the dependency graph would be a concrete next step beyond this paper.","The correctness proof is mathematical rather than machine-checked and lives in a language extension (quantum call-by-reference parameters) whose reduction to classical address and index passing is argued rather than formally proved; a mechanized proof of the same theorem, or a proof that the extension is conservative over RQC++, would close the remaining gap."],"forward_implications":["Programmers can specify recursive oracles (recursive summation, exponentiation by squaring, union-find find, depth-first search) in a classical structured style and receive reversible RQC++ code, with register indexing and uncomputation generated automatically rather than hand-written.","For linear recursion the generated program runs with invocation overhead linear in recursion depth and additional space $O(n(K+1)+N+M)$ for depth $n$ and per-layer register counts $K,N,M$, so the exponential recomputation of naive per-layer cleanup is avoided.","Because the compiled main procedure leaves every auxiliary register in $|0\\rangle$, the generated oracle can be invoked inside larger quantum algorithms and cleaned up by executing the inverse of the whole call, without leaking temporary garbage into the output.","The generated targets inherit the existing RQC++-to-QRM compilation chain, giving an executable route from a high-level recursive specification to a quantum register machine with quantum control flow and recursive procedure calls.","Well-typed RQIMP programs are guaranteed by the proof to compile to semantically equivalent targets, so type checking the source takes the place of debugging index management and cleanup timing in the target."],"supporting_citations":[{"why":"Defines RQC++, the target language whose syntax, operational semantics, Hoare proof system, and well-formedness conditions the compiled programs must satisfy.","marker":"[35]"},{"why":"Provides the QRM backend that compiles RQC++ to a quantum register machine with quantum control flow and recursive procedure calls, and supplies the finite static-storage interpretation of indexed variables.","marker":"[38]"},{"why":"Supplies the eager-cleanup strategy that ReOC reuses for non-recursive temporaries.","marker":"[3]"},{"why":"The closest prior uncomputation method, whose garbage-mode transformation avoids redundant recomputation in recursive programs; ReOC's deferred-cleanup policy is positioned against it.","marker":"[31]"},{"why":"The quantum language with random-access memory whose context-transforming typing judgment RQIMP adopts, and which requires classically bounded recursion that ReOC targets.","marker":"[36]"},{"why":"Supplies the QFT-based arithmetic oracles that ReOC uses to compile arithmetic and Boolean expressions.","marker":"[13]"},{"why":"Establishes Bennett-style delayed cleanup, whose space overhead motivates the paper's selective uncomputation timing.","marker":"[4]"}],"fun_headline_variants":["Recursive quantum oracles compile without exponential blow-up","ReOC: recursion-aware cleanup compiles oracles linear time","Compile recursive oracles with linear uncomputation overhead","Quantum oracle compiler avoids exponential cleanup","Recursion-aware uncomputation: linear cost for recursive oracles"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"All compiled programs live in an extension of RQC++ that permits quantum variables as call-by-reference procedure parameters; the paper argues this reduces to passing classical address and index data for statically allocated storage, but does not itself prove that the extension is sound or that the QRM backend realizes it, so the correctness theorem is only as strong as that unproved reduction.","fun_headline_variants_meta":{"raw":{"variants":["Recursive quantum oracles compile without exponential blow-up","ReOC: recursion-aware cleanup compiles oracles linear time","Compile recursive oracles with linear uncomputation overhead","Quantum oracle compiler avoids exponential cleanup","Recursion-aware uncomputation: linear cost for recursive oracles"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000197,"raw_usage":{"total_tokens":1405,"prompt_tokens":1028,"completion_tokens":377,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":644,"completion_tokens_details":{"reasoning_tokens":299}},"tokens_in":644,"tokens_out":377,"duration_ms":5089,"temperature":1.0,"reasoning_tokens":299,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T00:36:49.166601+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a well-typed RQIMP program (for instance the sum oracle), run its compiled RQC++ target through the QRM backend on every basis input, and check that each temporary annotated for cleanup returns to $|0\\rangle$ after execution and that for linear recursion the number of recursive invocations grows linearly with input depth; any residual entanglement of temporaries, any violation of RQC++'s well-formedness conditions in a generated declaration, or an exponential invocation count would refute Theorem 6.2 or the linear-overhead claim.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the eager-cleanup strategy that ReOC reuses for non-recursive temporaries."}],"review_version":1}