{"id":"97730b4f-d1db-411f-92bf-782738ba1bfb","arxiv_id":"2507.00400","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The authors construct relative-phase n-qubit Toffoli gates without ancillas and O(log n)-depth multi-controlled SU(2)/U(2) decompositions, improving on earlier methods.","lead":"This paper describes new circuit decompositions that implement multi-controlled single-qubit quantum gates in logarithmic depth while needing fewer or no ancillary qubits. These gates are building blocks of many quantum algorithms, so lower depth and fewer ancillas translate directly into smaller, less error-prone circuits on near-term hardware.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The conditionally-clean control qubit of Fig. 8 (and Fig. 5) is not shown to be clean when the k1-controlled Toffoli blocks fire with k2=0; the three-mode argument only verifies the target, so Theorem 4's ancilla-free claim is unverified.","rationale":"The paper's central claim is Theorem 4, and the CNOT arithmetic in Theorems 1-4 is internally consistent; I found no independent error in the resource counts. The load-bearing step is the assumption that a control qubit can be reused as a conditionally clean ancilla inside Theorem 3's SU(2) block (and inside the ancestor construction of Fig. 5). The reader's weakest assumption identifies exactly this step, and on reading the three-mode justification in Section III I agree that it verifies only the target qubit, not the full unitary on the control/ancilla registers. In particular, the branch with all k1 controls active and k2=0 is an inactive branch of the global C^n U gate, yet the k1-controlled Toffoli blocks are active; the paper provides no algebraic identity, truth table, or simulation showing that this branch is the identity. Without that identity, the ancilla-free and O(log n) claims are not established. The concern is about missing verification rather than a demonstrated contradiction, so it does not warrant outright rejection if the authors can supply the check. No change to the reader's conditional verdict is needed; the condition is precisely that this branch be verified.","tokens_in":11039,"tokens_out":12573,"duration_ms":135745,"concrete_test":"Reconstruct Fig. 8 exactly as specified for n=6, m=1 (k1=5, k2=1), using A=Ry(pi/4) and the paper's relative-phase Toffoli blocks; evaluate the exact circuit unitary with a symbolic simulator (no transpilation). Verify two conditions: (active) with all six controls in |1>, the target receives the intended SU(2) operation; (inactive) with the five k1 controls in |1> and k2 in |0>, the full 7-qubit unitary is the identity on all qubits. If the inactive condition fails, the conditionally-clean ancilla assumption is invalid, and Theorem 4's ancilla-free O(log n) claim is not supported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 4 inherits its depth and ancilla-free status from Theorem 3, which uses the single qubit k2 (white diamond in Fig. 8) as a conditionally clean ancilla for the k1-controlled, m-target Toffoli gates, and from the analogous use of ctrl[0] in Fig. 5. The load-bearing fact is that this qubit is in a known state in every branch in which those Toffoli blocks act, and is returned to its original state when the global C^n U gate is inactive. The only verification offered is the three-mode target-qubit argument in Section III (\"A2 σx A2† = -|0><0|+|1><1| when steps 1 and 5 are inactive\") and the white-diamond notation. That argument tracks the target, not the control/ancilla register. It does not prove that the full unitary on the branch with all k1 controls equal to 1 and k2=0, where the global gate should be identity but the k1-controlled blocks still fire, is the identity on every qubit. A qubit whose known value is |1> is not a zeroed ancilla, and the paper never states how Step 3 uses it under the two possible k2 values. Thus the ancilla-free claim and the O(log n) depth claim both depend on an unproven conditionally-clean substitution. If this branch leaves any control or ancilla register changed, an extra clean ancilla is required or the decomposition corrupts inactive inputs.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes logarithmic-depth decompositions of multi-controlled single-qubit gates. It first presents an ancilla-free relative-phase n-qubit Toffoli gate (Theorem 1, 6n+4 CNOTs, O(log n) depth) and a one-clean-ancilla version (Theorem 2, 6n+2 CNOTs, O(log n) depth), replacing dedicated ancillas with 'conditionally clean' control qubits. It then extends these constructions to n-controlled m-target SU(2) gates (Theorem 3, 12n+8m−14 CNOTs, O(log n + log m) depth) and to approximate n-controlled U(2) gates (Theorem 4, 4(nb−1)²+24n−8nb−20 CNOTs, O(log n) depth, claimed ancilla-free), improving the linear-depth construction of Ref. [14]. The central claimed contribution is the first ancilla-free logarithmic-depth approximate multi-controlled U(2) decomposition.","tokens_in":11414,"tokens_out":10976,"duration_ms":111134,"significance":"If the central construction is sound, this is a significant advance: it would reduce both depth and ancilla count relative to the linear-depth ancilla-free method of Ref. [14] and the polylogarithmic-depth method of Ref. [13]. The paper gives concrete CNOT counts rather than only asymptotic statements, and the authors state that all software is freely available, which supports reproducibility. The algebraic simplification in Theorem 4 is correct. However, the significance is conditional on the unproven 'conditionally clean ancilla' substitution, which is load-bearing for Theorems 1, 3, and 4; the manuscript as written does not establish that substitution.","major_comments":[{"comment":"The central ancilla-free claims depend on using the single control qubit k2 as a conditionally clean ancilla inside the two C^{k1} multi-target Toffoli blocks. The proof states only that 'the qubit in k2 is used as a conditionally clean ancilla' and does not analyze the branch where all k1 controls are 1 and k2=0. In that branch the global C^n W gate is required to be identity, but the k1-controlled blocks still fire; no argument shows that those blocks leave the k2/control register unchanged, and no statement explains how a k2 in state |1> (the active branch) can serve as a |0> ancilla for the inner Toffoli construction. Since Theorem 4 inherits its ancilla-free and depth claims from Theorem 3, this is a load-bearing gap. Please supply a full truth-table or algebraic identity for both k2=0 and k2=1 branches, or modify the construction to include the required |0> ancilla.","section":"V.A, Fig. 8, Theorems 3–4"},{"comment":"The same gap appears in the relative-phase Toffoli construction. The three-mode verification (A2 σx A2† = -|0><0|+|1><1| when Steps 1 and 5 are inactive) tracks only the target qubit. It does not prove that ctrl[0], used as the Step-3 conditionally clean ancilla, is returned to its original state in every branch, especially the branch in which Steps 1 and 5 are inactive but Step 3 fires. The white-diamond notation asserts the needed property but is not a proof. As a result, the ancilla-free claim and the O(log n) depth claim of Theorem 1 are not fully established.","section":"III, Fig. 5, Theorem 1"}],"minor_comments":[{"comment":"The CNOT counting is not fully transparent: the text says Step 3 'requires 2 log(n−1)−3 Toffoli gates' and then says the target qubit requires a standard Toffoli gate; please clarify whether the standard gate is included in that number, and give an explicit breakdown that yields 6n+4.","section":"III, Theorem 1 proof"},{"comment":"The values '14 CNOT gates' and 'depth 27' for a 3-qubit Toffoli are said to be 'verified after Qiskit transpilation'; these are tool- and version-dependent, so please specify the Qiskit version and optimization level or replace them with analytic counts.","section":"III, Theorem 1 depth analysis"},{"comment":"The statement 'All software developed in this project is freely available' is not accompanied by a repository URL or any identifier, which limits reproducibility; please add a link or citation to the code.","section":"Abstract / Software availability"},{"comment":"The argument of the logarithm contains the ratio |θ|/arccos(1−ϵ²/2), which is dimensionally inconsistent unless θ is normalized; please clarify the intended units or normalization of θ.","section":"II.C, Eq. (1)"},{"comment":"The comparative depth plots are described as obtained 'after Qiskit transpilation' but no transpiler settings, noise model, or raw data are given; please state the settings explicitly or move the implementation details to supplementary material.","section":"V, Figs. 9 and 10"}],"recommendation":"major_revision","confidential_remarks":"The paper builds heavily on Refs. [13,14,16], and the self-citation to Ref. [14] is appropriate as a baseline. The novelty hinges entirely on the conditionally clean ancilla substitution; if that substitution is supplied with a rigorous proof or verified numerically on all branches, the result would be a meaningful contribution. As it stands, the main theorems are not fully established, so major revision is warranted rather than rejection, since the gap appears fixable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this paper has a real idea—using conditionally clean control qubits to get ancilla-free logarithmic-depth multi-controlled gates—but the load-bearing correctness argument for the ancilla-free circuits is incomplete. I would send it to a careful referee, but I wouldn't trust the headline claim until the missing verification appears.\n\nWhat's genuinely new: the relative-phase n-qubit Toffoli with no ancillas (Theorem 1), the single-ancilla variant (Theorem 2), the extension to multi-target SU(2) with O(log n + log m) depth (Theorem 3), and the approximate ancilla-free U(2) decomposition (Theorem 4). These are concrete steps beyond Ref. [13]'s polylog depth and Ref. [14]'s linear depth. The resource-count arithmetic is internally consistent—I checked the 6n+4, 6n+2, 12n+8m−14, and 4(nb−1)^2+24n−8nb−20 counts. The plots comparing transpiled depths against [14] are appropriate, and the paper is honest about the trade-off of 10 extra CNOTs for the ancilla-free Toffoli.\n\nThe soft spot is exactly where the stress-test lands. The \"conditionally clean\" substitution in Figs. 5 and 8 is verified only by a three-mode verbal argument that tracks the target qubit. It never shows that the qubit used as the ancilla—ctrl[0] in Fig. 5, k2 in Fig. 8—is returned to its original state in every branch, especially the branch where the global gate is inactive but the inner k1-controlled blocks still fire. A qubit that is known to be |1> is not a zeroed ancilla. Without a truth table, algebraic identity, or simulation output covering the inactive branch, Theorems 1, 3, and 4 rest on an unproven premise. This is fixable—the constructions may well be correct—but it is exactly the kind of thing that can collapse. No code artifact is provided despite the abstract promising software, so there's no independent check.\n\nMinor quibbles: the depth constants (27, 18) come from Qiskit transpilation and are not analytical; the 'best-known' claim in the abstract should be qualified against [13], though log beats polylog asymptotically if the correctness holds.\n\nBottom line: this deserves a serious referee, not a desk reject. The idea is good, the arithmetic is solid, and the gap is identifiable and likely repairable. I'd ask the authors to provide a machine-checked or simulated verification of the inactive branches before publication.","headline":"A plausible log-depth, ancilla-free multi-controlled U(2) construction that rests on an unverified conditionally-clean ancilla claim; worth refereeing, but not trustable yet.","tokens_in":11933,"tokens_out":5033,"would_cite":false,"duration_ms":52103,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68"],"pacs":["03.67.Lx"],"model":"deepseek-v4-flash","headline":"Approximate n-controlled single-qubit gates use no ancillas and O(log n) depth.","keywords":["multi-controlled gates","relative-phase Toffoli","conditionally clean ancilla","logarithmic depth","CNOT count","approximate decomposition","U(2) gates","ancilla-free synthesis"],"falsifier":"Compute the full unitary of the ancilla-free circuit of Fig. 5 for $n=6$ and $n=10$ and compare it with the claimed relative-phase Toffoli action on every computational basis state; if any input with at least one control at $|0\\rangle$ leaves the borrowed control qubit changed, or the output map differs from identity up to a phase by more than $\\epsilon$, the central construction fails.","tokens_in":10841,"feed_emoji":"⚛️","tokens_out":14727,"duration_ms":154028,"temperature":0.7,"pith_summary":"This paper claims that large controlled single-qubit operations can be implemented far more cheaply than previous decompositions: an $n$-control $U(2)$ gate can be approximated to a user-chosen error $\\epsilon$ in $O(\\log n)$ circuit depth, with no ancillary qubits and a CNOT count that grows only linearly in $n$. The key move is to let one of the control qubits double as a temporary workspace during the internal logarithmic-depth Toffoli construction, in the subspace where it is guaranteed to be in a known state, and then restore it exactly in every branch. The same idea is first developed for relative-phase and single-ancilla versions of the $n$-qubit Toffoli gate, then extended to multi-target $X$ and $SU(2)$ gates, and finally substituted into the central block of the approximate $U(2)$ scheme. The stated result improves the best-known ancilla-free depth for these gates from polylogarithmic to logarithmic and cuts the linear CNOT coefficient of the earlier approximate scheme by about 25 percent.","feed_headline":"Multi-controlled single-qubit gates: zero ancillas, log depth","feed_subtitle":"New decomposition reaches O(log n) depth with no ancilla qubits and CNOT count 4(nb-1)^2 + 24n - 8nb - 20.","key_machinery":"The load-bearing object is the conditionally clean ancilla: a control qubit that is guaranteed to be in a known basis state (such as $|1\\rangle$) whenever the controls it helps verify are all active, so it can be borrowed as workspace inside that subspace and later uncomputed. The construction repeatedly uses a three-mode behavior of a relative-phase Toffoli block: when the outer condition is off but the inner Step 3 ladder fires, the target only picks up the relative-phase operator $A^2\\sigma_x (A^\\dagger)^2 = -|0\\rangle\\langle0|+|1\\rangle\\langle1|$ (with $A=R_y(\\pi/4)$); when the inner ladder is off, nothing happens; and when all controls are active, the full sequence composes to $\\sigma_x$. That separation is what lets a single control qubit play two roles without leaving behind an altered state.","core_discovery":"The central claim is that the qubit verifying the outer control condition can be reused as a conditionally clean ancilla inside the very Toffoli ladder that implements the gate, so the linear-depth block in the standard approximate $U(2)$ decomposition can be replaced by a logarithmic-depth block. Theorem 4 states that $C^nU$, with $U\\in U(2)$, is approximated to error $\\epsilon$ using at most $4(n_b-1)^2+24n-8n_b-20$ CNOTs and depth $O(\\log n)$, for $n\\ge n_b+5$, where $n_b$ is fixed by $\\epsilon$ through Eq. (1). The supporting theorems give ancilla-free relative-phase Toffoli gates with $6n+4$ CNOTs and one-ancilla Toffoli gates with $6n+2$ CNOTs, both in $O(\\log n)$ depth, plus an $n$-controlled $m$-target $SU(2)$ decomposition with $12n+8m-14$ CNOTs and depth $O(\\log n+\\log m)$. These counts are upper bounds from the construction, and the depth scalings follow because the recursive AND-ladder is arranged in geometrically growing layers.","pith_inferences":["A head-to-head test against the polylogarithmic-depth no-ancilla construction of Ref. [13] is the natural next step: at fixed $\\epsilon$ and realistic noise levels, the crossover where $O(\\log n)$ depth beats polylogarithmic depth with fewer CNOTs is not derived in the paper.","Because the Toffoli blocks are relative-phase gates, embedding them in algorithms that demand exact identity on inactive branches will require tracking or uncomputing those phases; the paper gives resource counts but not this integration cost.","The constant 14 CNOTs for the 3-qubit Toffoli gate comes from a specific compilation setting; on other gate sets the constant may shift, which could move the breakeven point between the new construction and the linear-depth one for small $n$.","If the conditionally-clean restoration passes full unitary checks near $n=10$ to $20$, the same dual-role trick is worth testing in other recursive circuits, such as adders and state preparation, that currently reserve dedicated workspace qubits."],"forward_implications":["Approximate $n$-controlled $U(2)$ gates become ancilla-free with $O(\\log n)$ depth, so algorithms that stack many multi-controlled rotations no longer pay a linear depth penalty or need extra workspace qubits.","At fixed error $\\epsilon$, the CNOT count $4(n_b-1)^2+24n-8n_b-20$ is linear in $n$, with asymptotic coefficient $24n$, roughly 25 percent below the $32n$ coefficient of the earlier approximate decomposition.","The borrowed control qubit is returned to its original state in every branch, so the same construction can be applied recursively inside larger circuits without accumulating workspace garbage.","Multi-controlled $X$ and $SU(2)$ gates with $m$ targets run in $O(\\log n+\\log m)$ depth, letting one controlled operation fan out to many qubits in parallel rather than as a cascade."],"supporting_citations":[{"why":"Supplies the five-step logarithmic-depth Toffoli construction with conditionally clean ancillas that Sections III-IV modify to remove or reduce ancillas.","marker":"[16]"},{"why":"Provides the approximate n-controlled U(2) scheme and the error formula Eq. (1) whose central linear-depth SU(2) block Theorem 4 replaces.","marker":"[14]"},{"why":"Supplies the 3-CNOT relative-phase Toffoli gate (Lemma 6) and the algebraic identity A sigma_x A-dagger used in the three-mode argument.","marker":"[9]"},{"why":"Introduces the conditionally clean ancilla concept that allows control qubits to double as temporary workspace.","marker":"[15]"},{"why":"Is the prior no-ancilla polylogarithmic-depth construction whose depth scaling the paper improves to logarithmic.","marker":"[13]"},{"why":"Provides the 6-CNOT relative-phase 3-qubit Toffoli used in Steps 1 and 5 of the single-ancilla variant.","marker":"[8]"},{"why":"Supplies the CNOT fan-out pattern used to extend single-target Toffoli gates to m targets in parallel.","marker":"[24]"}],"fun_headline_variants":["Zero-ancilla multi-controlled gates in log depth","Log-depth controlled-U gates without ancillas","Reusing control qubit slashes depth to logarithmic","Ancilla-free decomposition for multi-controlled gates","Approx multi-controlled gates hit log depth, no ancilla"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The borrowed control qubit is restored to its original state in every computation branch, including branches where the multi-controlled gate is inactive; the paper supports this with a three-mode case analysis rather than a full algebraic identity or numerical verification.","fun_headline_variants_meta":{"raw":{"variants":["Zero-ancilla multi-controlled gates in log depth","Log-depth controlled-U gates without ancillas","Reusing control qubit slashes depth to logarithmic","Ancilla-free decomposition for multi-controlled gates","Approx multi-controlled gates hit log depth, no ancilla"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000371,"raw_usage":{"total_tokens":2021,"prompt_tokens":1014,"completion_tokens":1007,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":630,"completion_tokens_details":{"reasoning_tokens":932}},"tokens_in":630,"tokens_out":1007,"duration_ms":10634,"temperature":1.0,"reasoning_tokens":932,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T21:19:19.360305+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the full unitary of the ancilla-free circuit of Fig. 5 for $n=6$ and $n=10$ and compare it with the claimed relative-phase Toffoli action on every computational basis state; if any input with at least one control at $|0\\rangle$ leaves the borrowed control qubit changed, or the output map differs from identity up to a phase by more than $\\epsilon$, the central construction fails.","supporting_citations":[{"cited_title":"Rise of conditionally clean ancillae for efficient quantum circuit constructions,","cited_arxiv_id":null,"evidence_quote":"Supplies the five-step logarithmic-depth Toffoli construction with conditionally clean ancillas that Sections III-IV modify to remove or reduce ancillas."},{"cited_title":"Linear decomposition of approximate multi-controlled single qubit gates,","cited_arxiv_id":null,"evidence_quote":"Provides the approximate n-controlled U(2) scheme and the error formula Eq. (1) whose central linear-depth SU(2) block Theorem 4 replaces."},{"cited_title":"Quantum circuits for isometries,","cited_arxiv_id":null,"evidence_quote":"Supplies the 3-CNOT relative-phase Toffoli gate (Lemma 6) and the algebraic identity A sigma_x A-dagger used in the three-mode argument."},{"cited_title":"Polylogarithmic-depth controlled-not gates without ancilla qubits,","cited_arxiv_id":null,"evidence_quote":"Is the prior no-ancilla polylogarithmic-depth construction whose depth scaling the paper improves to logarithmic."},{"cited_title":"Advantages of using relative-phase toffoli gates with an application to multiple control toffoli optimization,","cited_arxiv_id":null,"evidence_quote":"Provides the 6-CNOT relative-phase 3-qubit Toffoli used in Steps 1 and 5 of the single-ancilla variant."},{"cited_title":"Improving the mapping of reversible circuits to quantum circuits using multiple target lines,","cited_arxiv_id":null,"evidence_quote":"Supplies the CNOT fan-out pattern used to extend single-target Toffoli gates to m targets in parallel."}],"review_version":1}