{"id":"35558776-86d2-4ca9-a99a-73994359a606","arxiv_id":"1908.08853","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A simulated-annealing plus two-level look-ahead heuristic reduces the added-gate overhead of mapping quantum circuits onto IBM QX5 and Q20 hardware compared with prior algorithms.","lead":"This paper presents a compiler algorithm that rewires quantum circuits to fit the limited connectivity of real quantum chips while adding as few extra gates as possible. It combines simulated annealing to find a good starting layout and a search that looks two steps ahead to choose the best swap operations.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The abstract's 57% reduction claim is computed on added gates, not on output circuit size as stated; the same Table 4 shows only ~17.7% total size reduction.","rationale":"The paper is a solid engineering contribution: the double look-ahead heuristic and simulated-annealing initial mapping are plausible, code is provided, and the relative improvement in overhead is real. However, the headline claim as written is internally inconsistent with Section 3's definition of size and Section 5's improvement metric. The reader's conditional verdict is appropriate, but the condition should include correcting the central claim, not only specifying C*. If the claim were rewritten to 'reduce the number of added gates by 57%', the data support it; if 'size of output circuits' is kept, it is false. The C* omission is a legitimate reproducibility issue but is secondary because the final search heuristic likely mitigates initial mapping choices to some degree; the metric error directly affects how the contribution is interpreted.","tokens_in":21161,"tokens_out":12378,"duration_ms":115698,"concrete_test":"Recompute the aggregate improvement in Table 4 under the paper's own definition of size (total elementary gates): (220312 - 181282)/220312 is about 17.7%, versus 57.28% for added gates. This single arithmetic check settles whether the abstract's claim about output circuit size is overstated; if the released code also reports output sizes, compare the printed total gate counts to confirm which metric was actually used.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim, repeated in the abstract, Section 1, and the reader's strongest_claim, states that the method can reduce by 57% on average the size of the output circuits compared with the algorithm in [13] on IBM Q20. This is not what the data show. The paper defines circuit size as total elementary gates (Section 3) and defines the improvement ratio in Section 5 on the number of added gates: (ncomp - nours)/ncomp. Table 4's aggregate row gives original gates 152170, [13] 220312, proposed 181282. The added-gate counts are therefore 68142 and 29112, yielding a 57.28% reduction in added gates. But the reduction in total output circuit size is (220312 - 181282)/220312 = 17.7%. So the 57% figure is an overhead reduction, not a size reduction, and the abstract as written is not supported. A secondary but related reproducibility gap: the simulated-annealing initial mapping in Eq. (3) uses an unspecified subset C*, and the conclusion admits initial mapping quality is unstable, yet no seed variance is reported, so the exact 57% number may be brittle.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a quantum circuit transformation algorithm that first constructs an initial qubit mapping via simulated annealing and then performs a heuristic search with a two-level look-ahead to route CNOT gates under the connectivity constraints of IBM QX5 and IBM Q20. The authors report polynomial time complexity and quadratic space complexity, and they benchmark the method against the algorithms of Zulehner et al. [25], Li et al. [13], and Cowtan et al. [7]. The main quantitative claim in the abstract and introduction is that the method reduces the size of the output circuits by about 57% on average compared with the state-of-the-art algorithm on IBM Q20.","tokens_in":21462,"tokens_out":6128,"duration_ms":58600,"significance":"The algorithmic ingredients are well motivated and the paper provides a public code repository, polynomial runtime bounds, and benchmarks on a substantial set of realistic circuits. If the empirical claims are stated correctly, the work is a useful contribution to the NISQ circuit compilation literature. However, the headline '57% reduction of output circuit size' is not supported by the data in Table 4, because the reported improvement ratio is computed on the number of added auxiliary gates, not on total output size. In addition, the simulated-annealing initial mapping depends on an unspecified gate subset C* in Eq. (3), and the many hand-set parameters are not subjected to sensitivity analysis. These issues do not invalidate the underlying algorithm, but they must be fixed before the paper's central empirical claims can be accepted.","major_comments":[{"comment":"The abstract and Section 1 claim that the method 'can reduce by 57% on average the size of the output circuits' compared with the algorithm in [13] on IBM Q20. However, Section 5 defines the improvement ratio as (ncomp - nours)/ncomp, where ncomp and nours are the numbers of added auxiliary gates, not the total output circuit sizes. Using the aggregate row of Table 4 (original 152170 gates, [13] 220312 gates, proposed 181282 gates), the reduction in total output circuit size is (220312 - 181282)/220312 ≈ 17.7%, while the 57.28% figure is the reduction in added gates: (68142 - 29112)/68142. The headline claim must be rewritten to refer to added-gate overhead, or the experiments must be recomputed with the total size metric that the abstract states.","section":"Abstract, Section 1, Section 5, Table 4"},{"comment":"The initial mapping is defined as the minimizer of the sum of gate costs over a subset C* of the logical circuit, but the paper never specifies how C* is selected. Algorithm 1 takes C* as an input without describing its construction, and Section 4.2 only says that using all gates would be 'unnecessary' because tail gates have little impact. Since the quality of the initial mapping is load-bearing for the final routing cost, and since Section 6 concedes that the SA initial mapping is 'not stable,' the selection rule for C* must be stated explicitly and its influence on the reported improvements should be evaluated.","section":"Eq. (3), Algorithm 1, Section 4.2"},{"comment":"The algorithm relies on several empirically chosen parameters: the simulated-annealing temperatures Tmax, Tmin, the cooling factor Delta, the repetition count R, the look-ahead layer count l, the heuristic weights w_k and ws in Eq. (4), and the fallback threshold K. The paper gives no sensitivity analysis and reports no variance across SA random seeds; the conclusion itself states that initial-mapping quality is unstable. Because the aggregate improvement in Table 4 is the paper's central quantitative result, the authors should report the spread of results across runs and justify the parameter choices, or explicitly limit the claims to the particular parameter configuration used.","section":"Section 4.2, Section 4.3, Section 5, Section 6"}],"minor_comments":[{"comment":"The row for decod24-v2 reads '43 52 85 52 100.00%', which appears to contain an extra value and an improvement that cannot be produced by the stated formula (added gates 9 vs. 9 would give 0%). Please correct the entry or the formatting.","section":"Table 2"},{"comment":"The row for alu-v0_27 reports original gates 36, algorithm [13] output 39, proposed output 42, and improvement -75.00%. Under the stated added-gate formula, the added gates are 3 and 6, giving (3-6)/3 = -100%. Please reconcile the table entry with the definition.","section":"Table 4"},{"comment":"The text in Section 5 says 'we set ... w4 = 0.4 x (DAG - 1) x Nswap in Eq. (4)', but Eq. (4) uses the symbol ws rather than w4. Please align the notation.","section":"Section 5, Eq. (4)"},{"comment":"Eq. (4) sums over layers k=0 to l with weights w_k, but the text says '1 = w0 >= w1 >= ...' and does not state a value for w0. Please specify w0 explicitly, especially because the example in Table 1 uses w1 = 1, w2 = 0.8, w3 = 0.6, ws = 0.4 without mentioning w0.","section":"Eq. (4)"},{"comment":"The convergence of the simulated annealing procedure is shown for a single circuit (adr4-197). Since the quality of SA is stochastic and Section 6 reports instability, it would be helpful to state whether similar convergence behavior was observed for the other benchmarks or to report a summary statistic over multiple runs.","section":"Figure 5"}],"recommendation":"major_revision","confidential_remarks":"The paper's central algorithm appears sound and the code is public, but the abstract's 57% size-reduction claim is not what Table 4 shows. I would request a revision that corrects the metric or recomputes the claim, specifies the C* selection rule, and adds some sensitivity analysis. If these are addressed, the paper could be a reasonable empirical contribution to the circuit transformation literature."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about this paper before reading: the headline 57% number is an added-gate reduction, not a reduction in total output circuit size, and the method itself is a legitimate incremental improvement in heuristic qubit routing. The paper combines simulated annealing for initial mapping with a double look-ahead cost function, pruning, and a remote-CNOT fallback. That combination appears to be new. All components are standard, but the engineering is careful: code is on GitHub, the complexity analysis is polynomial, and the benchmarks cover QX5 and Q20 across many circuits. Compared with Li et al. on Q20, the proposed algorithm saves roughly 39k of 220k output gates, about 17.7% total size, or 57% of the overhead gates. That is a real, useful improvement for NISQ compilation, especially on larger circuits. The comparison with Zulehner et al. on QX5 is also consistently positive.\n\nThe soft spots are real but not fatal. The abstract and introduction say 'size of output circuits' when the 57% is only overhead reduction. That needs fixing. Also, Eq. (3) uses an unspecified subset C*, and the paper gives no selection rule, so the initial mapping cannot be exactly reproduced. SA parameters and weights are empirical, with no sensitivity analysis. The conclusion admits initial mapping quality is unstable, and no seed variance is reported, so the exact percentages are brittle. A few table entries don't match the stated improvement formula (e.g., alu-v0_27). These are all fixable with reporting changes and a sensitivity study; they don't undermine the core evidence that the method helps on large circuits.\n\nWho is this for? People working on NISQ circuit compilation or qubit routing. It is not a conceptual breakthrough, but it is a solid, well-tested heuristic that deserves peer review. I would like to see it published after the abstract is corrected and the missing specifications are added.\n\nRecommendation: send it to review. My own verdict would be conditional accept pending those clarifications.","headline":"Solid heuristic engineering for NISQ qubit routing, but the abstract's 57% figure is an added-gate reduction, not a total-size reduction; the underlying 17.7% total-size gain is still real and worth publishing after fixes.","tokens_in":21921,"tokens_out":3630,"would_cite":true,"duration_ms":33158,"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":"Using simulated annealing for the initial qubit placement and a grandchild look-ahead search for routing, the paper reports a 57% average reduction in added gates on a 20-qubit device.","keywords":["quantum circuit transformation","qubit mapping","simulated annealing","heuristic search","look-ahead","NISQ","SWAP insertion","architecture graph"],"falsifier":"Re-run the benchmark suite on the 20-qubit Tokyo architecture with several explicit subset rules for $C^*$—the first $k$ gates, a uniformly random sample of $k$ gates, the last $k$ gates, and all gates—and compare added-gate totals against the reverse-traversal baseline. If the 57.28% average reduction does not persist across these transparent subset choices, or if some natural choice of $C^*$ changes the ranking, the central claim fails.","tokens_in":20985,"feed_emoji":"⚛️","tokens_out":9816,"duration_ms":93169,"temperature":0.7,"pith_summary":"Real quantum chips only allow two-qubit gates between specific adjacent physical qubits, so an ideal circuit must be rewritten by inserting SWAP and Hadamard gates that move qubits around. This paper claims that the amount of inserted hardware can be sharply reduced by separating the task into two phases: simulated annealing chooses an initial logical-to-physical qubit placement that minimizes the total CNOT-implementation distance over a selected subset of gates, and a heuristic search then routes the remaining gates by looking one step beyond each candidate move. On a 20-qubit Tokyo device the algorithm adds 57.28% fewer elementary gates on average than the best previous mapping method, while running in polynomial time and quadratic space in the number of architecture edges. If the claim is right, the same circuits can be run on today's noisy hardware with less accumulated error, and larger circuits become compilable in practice.","feed_headline":"Two-phase algorithm cuts added quantum gates by 57 percent","feed_subtitle":"Simulated annealing picks the starting qubit map; grandchild look-ahead prunes SWAP overhead on a real 20-qubit device.","key_machinery":"The load-bearing object is the CNOT distance $\\mathrm{dist}_{\\mathrm{cnot}}(v,v')$, defined as the fewest auxiliary CNOT and Hadamard gates needed to implement a CNOT between physical qubits $v$ and $v'$ in a given architecture graph; for an undirected graph of distance $d$ it is $3(d-1)$, and for a directed graph it is $7(d-1)$ or $7(d-1)+4$ depending on whether a shortest path already has the correct direction. This distance supplies both the simulated-annealing cost for the initial mapping and the layer-weighted heuristic cost in Eq. (4). The argument is carried by the double look-ahead: every candidate child state is scored by the best of its grandchildren, so the search avoids committing to a child whose short-term gain hides a poor next step. A remote-CNOT fallback and a pruning rule keep the search terminating in polynomial time.","core_discovery":"On the paper's own terms, the central claim is that the NP-hard transformation of a logical circuit into one that respects a chip's connectivity graph splits cleanly into an initial-placement problem and a routing problem. Simulated annealing solves the placement problem by minimizing a gate cost over a chosen subset $C^*$ of the logical circuit: the cost of a gate is $\\mathrm{dist}_{\\mathrm{cnot}}(\\tau(q),\\tau(q'))$, the number of auxiliary CNOT and Hadamard gates needed to implement the gate at the current physical locations. The routing problem is then solved by a depth-two heuristic search: from the current state, generate all child states reachable by one SWAP insertion or by flipping a CNOT direction with four Hadamard gates, generate their grandchildren, score each grandchild as gates already inserted plus a layer-weighted heuristic cost for the remaining circuit, and move to the child that owns the cheapest grandchild. Reported results are a 57.28% average reduction in added gates relative to the reverse-traversal baseline on the 20-qubit Tokyo architecture, a 13.36% average reduction relative to the $A^*$-based baseline on QX5, polynomial time, and space quadratic in the number of architecture edges.","pith_inferences":["The double look-ahead selection rule is transferable: any graph rearrangement problem where a single swap is the unit move and future costs are layer-like could use the same child-owned-by-best-grandchild rule, not just quantum circuit transformation.","Since the cost function ignores gate error rates and decoherence, a natural follow-up is to replace the fixed layer weights with device-calibrated error weights; the size reductions reported might then translate into even larger fidelity gains, or reveal trade-offs.","The authors note the simulated-annealing output is not stable across runs; a concrete extension is to restart it several times and feed the best of several mappings into the search, which would test whether the 57% figure is sensitive to the randomness in the placement phase.","The choice of the gate subset $C^*$ in Eq. (3) is left unspecified; comparing subset rules (first $k$ gates, uniform sample, all gates) would show how much of the reported gain comes from the placement phase versus the routing phase."],"forward_implications":["On the 20-qubit Tokyo architecture, the algorithm's total added-gate count across the 24 benchmark circuits is 181,282 versus 220,312 for the reverse-traversal baseline, a 57.28% improvement.","On the 16-qubit QX5 architecture, the algorithm beats the $A^*$-based baseline by 13.36% on average and handles circuits up to 30,000 elementary gates within two minutes.","With look-ahead depth increased, output circuits get still smaller but runtime grows quickly; the paper's one-level look-ahead is the chosen trade-off.","The heuristic's layer weights are adjustable, so the same algorithm can be re-tuned for different architectures and circuit families without changing the search structure."],"supporting_citations":[{"why":"Supplies the reverse-traversal baseline on Q20, the main comparison target, and the layered look-ahead cost idea the paper extends.","marker":"[13]"},{"why":"Supplies the $A^*$-based baseline algorithm on QX5 whose added-gate count the proposed algorithm reduces by 13.36% on average.","marker":"[25]"},{"why":"Supplies the qubit-routing baseline for directed and undirected architecture graphs compared in the appendix.","marker":"[7]"},{"why":"Supplies the simulated-annealing optimization procedure used to approximate the optimal initial mapping.","marker":"[11]"},{"why":"Defines the quantum circuit transformation problem, the architecture graph model, and the NP-hardness context the algorithm builds on.","marker":"[6]"},{"why":"Supplies the remote CNOT construction used by the fallback mechanism to guarantee search termination.","marker":"[18]"}],"fun_headline_variants":["Simulated annealing + look-ahead cuts added gates by 57%","Two-phase algorithm with SA and look-ahead shrinks circuit size","Heuristic look-ahead search cuts SWAP overhead by 57%","SA for mapping + look-ahead routing: 57% fewer gates","Look-ahead heuristic plus SA: 57% fewer SWAPs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole reported advantage rests on the unstated rule for selecting the subset $C^*$ of gates used by the simulated-annealing initial mapping; if that subset is not representative of the circuit as a whole, the initial placement may not generalize and the benchmark improvements could shrink or reverse.","fun_headline_variants_meta":{"raw":{"variants":["Simulated annealing + look-ahead cuts added gates by 57%","Two-phase algorithm with SA and look-ahead shrinks circuit size","Heuristic look-ahead search cuts SWAP overhead by 57%","SA for mapping + look-ahead routing: 57% fewer gates","Look-ahead heuristic plus SA: 57% fewer SWAPs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001021,"raw_usage":{"total_tokens":4382,"prompt_tokens":1093,"completion_tokens":3289,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":709,"completion_tokens_details":{"reasoning_tokens":3194}},"tokens_in":709,"tokens_out":3289,"duration_ms":23894,"temperature":1.0,"reasoning_tokens":3194,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:27:52.299541+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Re-run the benchmark suite on the 20-qubit Tokyo architecture with several explicit subset rules for $C^*$—the first $k$ gates, a uniformly random sample of $k$ gates, the last $k$ gates, and all gates—and compare added-gate totals against the reverse-traversal baseline. If the 57.28% average reduction does not persist across these transparent subset choices, or if some natural choice of $C^*$ changes the ranking, the central claim fails.","supporting_citations":[{"cited_title":"Tackling the qubit mapping problem for nisq-era quantum devices","cited_arxiv_id":null,"evidence_quote":"Supplies the reverse-traversal baseline on Q20, the main comparison target, and the layered look-ahead cost idea the paper extends."},{"cited_title":"An efficient methodology for mapping quantum circuits to the ibm qx architectures.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018","cited_arxiv_id":null,"evidence_quote":"Supplies the $A^*$-based baseline algorithm on QX5 whose added-gate count the proposed algorithm reduces by 13.36% on average."},{"cited_title":"Optimization by simulated annealing.science, 220(4598):671–680, 1983","cited_arxiv_id":null,"evidence_quote":"Supplies the simulated-annealing optimization procedure used to approximate the optimal initial mapping."}],"review_version":1}