{"id":"87e2a73d-1adf-4c28-aa92-2c2e67f9f0eb","arxiv_id":"2504.20291","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A single-platform benchmark of gate decomposition algorithms yields practical profiles that rank algorithms for compilation-time and execution-time priorities.","lead":"This paper benchmarks quantum gate decomposition algorithms implemented in the Ket compiler, measuring CNOT counts and circuit depths across three gate families. It proposes two compilation profiles, one that minimizes compilation time and one that minimizes quantum execution time.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The Table 2 profiles rest entirely on unvalidated proxies—CNOT count for compilation time and CNOT-only depth for execution time—while no wall-clock or hardware execution measurement is reported.","rationale":"The reader's weakest assumption is exactly the one I identify: Section 5 equates CNOT count with compilation time and CNOT-only depth with execution time, and no validation against actual compilation timings or hardware/simulator executions is provided. I agree that this is the load-bearing weakness because the paper's central contribution is not the decomposition algorithms themselves but the two profiles in Table 2, which are rankings derived from those proxies. The paper is still conditionally acceptable: the proxies are stated transparently, the artifact is available, and the proposed test is straightforward to run. The Section 7 concession about circuit mapping's impact further supports treating the profiles as conditional rather than as established empirical findings. I do not see an internal inconsistency or a reason to reject; the missing validation is precisely the condition that needs to be met.","tokens_in":13821,"tokens_out":7513,"duration_ms":76494,"concrete_test":"Using the released artifact (DOI 10.5281/zenodo.16964846), run the full Libket compilation pipeline—not just the decomposition step—on the same benchmark instructions ('ctrl(c, X)(t)', 'ctrl(c, RX(pi/2))(t)', 'ctrl(c, H)(t)') for n = 200, 500, 1000, and 2000, and measure wall-clock seconds for every algorithm ranked in Table 2. Compare the resulting ranking with the CNOT-count ranking; if the fastest wall-clock algorithms differ from the 'Compilation Time' column, the compilation-time profile is unsupported as stated, and if they match, the proxy is validated for this platform.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 5 states: 'We measure the compilation time based on the number of CNOTs and the quantum execution time based on the quantum circuit depth... No actual quantum execution was performed during the tests; only the decomposition was evaluated.' This is the load-bearing step because the entire contribution—Table 2's two compilation profiles—is a ranking of algorithms by these proxies, yet the profiles are named after real time costs. The proxy is not harmless: later compiler passes such as qubit mapping and routing have time costs that depend on circuit structure and qubit connectivity, not merely on CNOT count, and real execution time depends on routing, gate errors, connectivity, and auxiliary-qubit allocation/reset costs, none of which appear in CNOT-only depth. The paper itself concedes in Section 7 that 'circuit mapping may have a significant impact on the final performance.' If, for example, Network C2X's requirement of n-2 clean auxiliary qubits triggers expensive allocation or reset in a concrete compiler, its first-place ranking in both profiles could be reversed. Since the headline claim is specifically about which algorithms minimize compilation and execution time, the unvalidated proxy is the single most load-bearing weakness.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper addresses the first step of quantum compilation, the decomposition of multi-qubit gates into one- and two-qubit gates, within the Ket quantum programming platform. It surveys and implements a set of decomposition algorithms for Pauli, rotation, and phase/Hadamard gates, and reports benchmark data on CNOT count and CNOT-only circuit depth as proxies for compilation time and execution time. Based on the resulting rankings, it proposes two compilation profiles: one for minimizing compilation time and one for minimizing quantum execution time, summarized in Table 2. The central result is that the Network decomposition with approximate C2X/C3X gates ranks first in both profiles across all gate families, provided clean auxiliary qubits are available.","tokens_in":14038,"tokens_out":8013,"duration_ms":74906,"significance":"If the proxy assumption were empirically supported, the paper would be a useful engineering comparison; its single-platform implementation of many decomposition algorithms is a genuine contribution, and the artifact is deposited at Zenodo. The explicit acknowledgement of hardware-dependent effects (Section 7) and the absence of any wall-clock or hardware execution measurement mean, however, that the headline profiles are not established for the quantities they claim to minimize. The paper is likely to be useful to compiler developers as an organized comparison of CNOT counts and depths, but the two 'time' profiles are not yet a reliable basis for compiler decisions.","major_comments":[{"comment":"The paper equates compilation time with the number of CNOTs and execution time with the circuit depth computed over CNOTs only, stating in Section 5 that 'We measure the compilation time based on the number of CNOTs and the quantum execution time based on the quantum circuit depth' and that 'No actual quantum execution was performed during the tests; only the decomposition was evaluated.' This is an unvalidated modeling choice at the load-bearing center of the paper: Table 2's two profiles are named after real time costs, yet no evidence is given that CNOT count is proportional to compiler runtime (which includes graph manipulation, mapping, and scheduling passes) or that CNOT-only depth determines execution time on hardware (which depends on routing, gate errors, connectivity, and auxiliary-qubit allocation/reset costs). The authors themselves concede in Section 7 that 'circuit mapping may have a significant impact on the final performance.' Without validation of these proxies, the first-place ranking of Network decomposition in both profiles is not justified; at minimum, the profiles should be re-labeled as CNOT-count-minimizing and depth-minimizing, or supplemented with wall-clock compilation measurements and mapped-circuit execution estimates.","section":"Section 5 (Algorithms Benchmark), also Section 2"},{"comment":"The rankings in Table 2 are presented as absolute, but the underlying curves in Figures 9–11 cross as a function of n. The text itself states in Section 6 that logarithmic-depth algorithms 'demonstrate their advantages only in scenarios involving more than 1000 qubits.' Because the table gives no qubit-count range, a compiler developer could apply the 'Execution Time' profile to small circuits where a linear-depth algorithm with fewer CNOTs may actually execute faster. The profiles need to specify the n-range for which each ranking is intended, or provide the lookup table mentioned in Section 7 as a concrete artifact rather than a future possibility.","section":"Section 6 (Results Analysis) and Table 2"},{"comment":"The sentence 'The quantum circuit depth and the number of CNOTs presented in Table 1 were obtained by fitting the curves of the benchmark data' is the only description of the fitting procedure. The paper does not report the qubit-count samples, the number of data points, the fit function class (e.g., linear regression through the origin), or goodness-of-fit measures. Since Table 1 presents exact-looking constants (e.g., 4n, 6n, n^2/10), the uncertainty in these fitted values is unclear; this matters for the ordering in Table 2 if two algorithms' curves are close. The methodology should be fully described for reproducibility.","section":"Section 5 and Table 1 (caption)"}],"minor_comments":[{"comment":"The entry 'Liner Depth' in the Phase and Hadamard section appears to be a typo for 'Linear Depth'.","section":"Table 1"},{"comment":"The Pauli Gates section of Table 1 omits the Linear Depth row, although Figure 9 and Table 2 include it; since Linear Depth is described in Section 4.1 as the fallback for any gate, the table should list it under Pauli Gates for completeness.","section":"Table 1 and Figure 9"},{"comment":"The horizontal-axis labels appear to be rendered incorrectly (e.g., 'Number of  bits' instead of 'Number of qubits'); please check the figure source files.","section":"Figures 9 and 10"},{"comment":"The sentence 'Figure 3 illustrates two variants of the algorithm for a 8-controlled Pauli X gate' should read 'an 8-controlled Pauli X gate.'","section":"Section 4.1"},{"comment":"The claim that this is 'the first study to both implement and analyze the current state-of-the-art decomposition methods within a single platform' is a strong novelty assertion; the authors should either soften it or provide a reference to demonstrate that no prior unified implementation exists.","section":"Abstract and Section 1"}],"recommendation":"major_revision","confidential_remarks":"To the editor: The paper is an engineering comparison whose central claim depends on an unvalidated proxy. There is a notable proportion of self-citations (the authors' own prior algorithms are among those benchmarked), but this is not disqualifying; the more serious issue is the gap between the proxy-based rankings and the time-based claims. The manuscript may be better served by reframing the contributions as CNOT-count and depth benchmarks rather than compilation/execution time profiles, unless the authors can provide validation data. If the profiles are reframed and the ranking ranges are clarified, the paper could become a useful reference for compiler developers."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe short version: this is a solid, clearly presented benchmark of known gate-decomposition algorithms, all implemented in one platform (Ket), with the results organized into two \"compilation profiles.\" The profiles are read directly off the measurements, so there is no fitting-to-the-conclusion circularity. The one load-bearing weakness is that the paper names the profiles after real time costs while only measuring proxies: CNOT count for compilation time and CNOT-only depth for execution time. That mismatch is worth fixing before publication.\n\nWhat is actually new is the unified implementation and the head-to-head numbers. The algorithms are all prior art, but having them in a single platform with consistent measurement is useful. The finding that Network wins on both metrics across all gate types—at the price of many clean auxiliary qubits—is concrete and actionable. The clean-vs-dirty auxiliary gap is also a nice observation. The artifact link is a plus.\n\nThe paper is honest: it explicitly states no quantum execution was performed, and Section 7 concedes that circuit mapping can change the final performance. That honesty helps. But the profile names in Table 2 go beyond what was measured. The rationale for CNOT count as a proxy for compilation time—downstream passes that scale with gate count—is plausible but not validated. A real compiler's routing or optimization pass might have cost structures that change the ranking. Same for depth: it is a standard ideal-circuit metric, but real execution depends on connectivity and auxiliary-qubit allocation/reset. Network's O(n) clean auxiliary requirement could be a practical bottleneck that a pure depth ranking misses. So the data is fine; the interpretation is conditional.\n\nMinor points: the \"first unified implementation\" claim is hard to verify from the text, and the curve fits for Table 1 could be documented better. Neither changes the bottom line.\n\nWho should read it: anyone building or choosing a quantum compiler, and researchers needing a quick comparison of decomposition methods. It is not a breakthrough, but it is a useful engineering reference. I'd send it to peer review, and I'd ask the authors to either validate the proxies on at least one real backend or rename the profiles to \"CNOT-count-minimizing\" and \"depth-minimizing.\" The underlying work deserves referee time.","headline":"A useful, honest benchmark of known decomposition algorithms in a single platform, but the proposed 'compilation time' and 'execution time' profiles are built on unvalidated proxies (CNOT count and depth) that need either validation or softer naming.","tokens_in":14540,"tokens_out":2956,"would_cite":true,"duration_ms":29771,"reading_group":"maybe","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 claims that, in a single-platform implementation, the Network decomposition produces the fewest CNOT gates and the shallowest circuits for every class of multi-controlled gate, and that the remaining algorithms sort into two…","keywords":["quantum computing","quantum compilation","gate decomposition","multi-controlled gates","CNOT count","circuit depth","compilation profiles","auxiliary qubits"],"falsifier":"Run the same decomposition algorithms with actual clock-based compilation timings and hardware execution timings (or a cycle-accurate simulation) on multi-controlled gates with 100 to 2000 control qubits; if the algorithm ranked first in Table 2 is not the fastest in practice, the CNOT-count and CNOT-depth proxies fail.","tokens_in":13635,"feed_emoji":"⚛️","tokens_out":9872,"duration_ms":84716,"temperature":0.7,"pith_summary":"The paper sets out to make the first step of quantum compilation—decomposing multi-qubit gates into one- and two-qubit operations—a data-driven choice rather than a guess. It implements the state-of-the-art decomposition algorithms inside the Ket quantum programming platform and benchmarks them on multi-controlled Pauli, rotation, and phase/Hadamard gates. The central claim is that the Network decomposition is the most efficient algorithm across all gate types, and that the other algorithms can be ranked into two compilation profiles: one favoring few CNOT (two-qubit) gates as a proxy for fast compilation, and one favoring shallow CNOT depth as a proxy for fast execution. If the ranking is right, compiler writers can pick a decomposition strategy by gate type, auxiliary-qubit budget, and whether they are compiling for near-term machines or for large-scale fault-tolerant ones.","feed_headline":"Network decomposition beats all rivals in gate benchmarks","feed_subtitle":"Single-platform test of decomposition algorithms yields profiles for fast compilation vs. fast execution.","key_machinery":"The load-bearing object is the decomposition circuit itself: each algorithm is a concrete rewrite rule that expands one $n$-controlled single-qubit gate into a pattern of CNOTs and single-qubit rotations, and the paper measures the pattern's cost in CNOT count and in CNOT-only circuit depth. The key identity inside these patterns is the relative-phase Toffoli approximation (the C2X and C3X constructions), which lets a multi-controlled gate be assembled from blocks of $O(\\log n)$ depth. The benchmark instrument is a single compiler that applies any of these rewrites to the same source instruction while automatically allocating clean or dirty auxiliary qubits, which is what makes the comparison across algorithms consistent.","core_discovery":"On the paper's own terms, the central discovery is that the choice among decomposition algorithms can be settled empirically rather than left to asymptotic intuition. In the unified Ket implementation, the Network decomposition is the most efficient algorithm across all gate types—lowest CNOT count and lowest depth—but it demands the most clean auxiliary qubits. The benchmark data also show that clean auxiliary qubits outperform dirty ones by a wide margin, with the Single Aux Linear algorithm as an exception, and that logarithmic-depth algorithms only win in very large circuits, beyond about 1000 qubits. These observations are condensed into two profile rankings: a Compilation Time profile for minimizing CNOT count and an Execution Time profile for minimizing circuit depth counting only CNOTs.","pith_inferences":["My inference: the paper's profiles are really circuit-quality profiles, not end-to-end performance profiles, because routing, pulse scheduling, and single-qubit gate costs could reorder the table on specific hardware.","My inference: a direct test of the proxy assumption would be to repeat the benchmark using actual wall-clock compilation times and hardware execution times rather than CNOT counts and CNOT depth.","My inference: the same single-platform methodology could be extended to non-Clifford gates, where quantum error correction overhead may change which decomposition is cheapest in practice."],"forward_implications":["A compiler following the Compilation Time profile will use Network C2X or C3X whenever enough clean auxiliaries exist, producing the smallest CNOT counts among the surveyed methods.","A compiler targeting large-scale fault-tolerant machines should follow the Execution Time profile, where Network variants dominate and Single Aux Log is the best single-auxiliary option for Pauli gates.","Because clean auxiliaries sharply improve both metrics over dirty ones, having roughly double the qubits needed by the program can dramatically reduce both compilation and execution cost.","Linear Depth remains the crucial no-auxiliary fallback for most gate types, so near-term compilers should keep it, though its relevance may decline as more qubits become available.","The benchmark data can be arranged into a lookup table that selects the best decomposition for a given gate type and control count below 2200 qubits, where performance is not easily predictable from asymptotics."],"supporting_citations":[{"why":"It supplies the Network decomposition (p. 183) that the paper ranks as most efficient across all gate types.","marker":"[19]"},{"why":"It provides the relative-phase Toffoli C2X and C3X approximations that the Network and V Chain decompositions rely on.","marker":"[17]"},{"why":"It proposes the V Chain decomposition, one of the algorithms benchmarked for Pauli gates.","marker":"[3]"},{"why":"It introduces the Single Aux Linear and SU(2) Linear decompositions used in the compilation-time profile for rotation gates.","marker":"[32]"},{"why":"It presents the Single Aux Log decomposition that gives logarithmic-depth Pauli and rotation circuits with one auxiliary qubit.","marker":"[5]"},{"why":"It introduces the Linear Depth decomposition, the no-auxiliary fallback for general U(2) gates.","marker":"[8]"},{"why":"It defines the SU(2) Rewrite decomposition and earlier optimized decompositions on which the Ket implementations build.","marker":"[22]"},{"why":"It describes the automated auxiliary-qubit allocation that lets the compiler manage clean and dirty auxiliaries during the benchmarked decompositions.","marker":"[23]"},{"why":"It introduces the Ket quantum programming platform and its compiler, the single environment where all algorithms were implemented and benchmarked.","marker":"[7]"}],"fun_headline_variants":["Network decomposition outperforms but needs clean qubits","Two profiles: compile-optimized vs runtime-optimized","Single platform benchmarks decomposition algorithms","Clean qubits beat dirty ones in gate compilation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The ranking rests on treating the number of CNOT (two-qubit) gates as a faithful proxy for how long compilation takes, and the depth of those CNOTs as a faithful proxy for how long the quantum circuit runs; the paper assumes this equivalence rather than testing it against real timings.","fun_headline_variants_meta":{"raw":{"variants":["Network decomposition outperforms but needs clean qubits","Two profiles: compile-optimized vs runtime-optimized","Single platform benchmarks decomposition algorithms","Clean qubits beat dirty ones in gate compilation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001141,"raw_usage":{"total_tokens":4678,"prompt_tokens":830,"completion_tokens":3848,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":446,"completion_tokens_details":{"reasoning_tokens":3790}},"tokens_in":446,"tokens_out":3848,"duration_ms":29061,"temperature":1.0,"reasoning_tokens":3790,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T05:31:48.040751+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the same decomposition algorithms with actual clock-based compilation timings and hardware execution timings (or a cycle-accurate simulation) on multi-controlled gates with 100 to 2000 control qubits; if the algorithm ranked first in Table 2 is not the fastest in practice, the CNOT-count and CNOT-depth proxies fail.","supporting_citations":[{"cited_title":"Bennett, Richard Cleve, David P","cited_arxiv_id":null,"evidence_quote":"It proposes the V Chain decomposition, one of the algorithms benchmarked for Pauli gates."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It describes the automated auxiliary-qubit allocation that lets the compiler manage clean and dirty auxiliaries during the benchmarked decompositions."}],"review_version":1}