REVIEW 3 major objections 5 minor 25 references
Quantum Circuit Transformation Based on Simulated Annealing and Heuristic Search
T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read 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.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [Abstract, Section 1, Section 5, Table 4] 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.
- [Eq. (3), Algorithm 1, Section 4.2] 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 4.2, Section 4.3, Section 5, Section 6] 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.
minor comments (5)
- [Table 2] 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.
- [Table 4] 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 5, Eq. (4)] 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.
- [Eq. (4)] 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.
- [Figure 5] 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.
Circularity Check
No circularity: the transformation algorithm is self-contained; the reported benchmark improvements are external to the method's construction, though the abstract's 57% claim is a metric mismatch, not a circular step.
full rationale
The paper's derivation chain is self-contained. Gate cost (Eq. 2) is defined from the architecture graph's precomputed CNOT distance; the initial mapping (Eq. 3) minimizes that cost over a subset C* via simulated annealing; the heuristic completion cost (Eq. 4) is a layered estimate with empirically set weights; and the search cost (Eq. 5) combines actual auxiliary-gate overhead with that heuristic estimate. Every quantity is defined from the input circuit and architecture graph, not from the benchmark outcomes. The reported improvement over [13], [25], and [7] is obtained by running the algorithm on external benchmark circuits and comparing output sizes, so it is not an input to the construction. No load-bearing self-citation appears: the comparison algorithms are external prior work, and no uniqueness theorem or ansatz is imported from the authors' own prior papers. The paper's own stated limitations—an unspecified C*-selection procedure (Section 4.2) and admitted instability of the simulated-annealing initial mapping (Section 6)—are reproducibility or robustness concerns, not circularity. The abstract's '57% reduction in size' also does not match the Section 5 improvement ratio, which is defined on added gates rather than total output circuit size; that is a claim-support discrepancy, not a circular derivation. Accordingly, no circular step is exhibited and the score is 0.
Assumptions & free parameters
free parameters (5)
- Heuristic weights w1, w2, w3, ws in Eq. (4) =
w1=1, w2=0.8, w3=0.6, ws=0.4*(DAG-1)*Nswap
- Look-ahead layer count l =
3
- SA parameters Tmax, Tmin, Delta, R =
Tmax=100, Tmin=1, Delta=0.98, R=100
- Fallback threshold K =
0.5*DAG
- C* gate subset for initial mapping =
not specified
assumptions (4)
- domain assumption Input logical circuits consist only of CNOT gates after removing single-qubit gates (Section 3).
- standard math The dependency graph and layer decomposition (Section 3.1) correctly capture gate execution order.
- ad hoc to paper The heuristic cost function Eq. (4) with decreasing layer weights is a valid proxy for remaining routing cost.
- standard math SWAP gate decompositions in Fig. 3 require 3 CNOTs for undirected architectures and 7 gates for directed QX5, and the CNOT distance formula is correct.
Cite this review
Pith. "Pith review of Quantum Circuit Transformation Based on Simulated Annealing and Heuristic Search." pith.science (2026). https://pith.science/paper/S5QU6LG2
@misc{pith2026190808853,
author = {Pith},
title = {Pith review of: Quantum Circuit Transformation Based on Simulated Annealing and Heuristic Search},
year = {2026},
howpublished = {\url{https://pith.science/paper/S5QU6LG2}},
note = {Machine review of arXiv:1908.08853}
}
read the original abstract
Quantum algorithm design usually assumes access to a perfect quantum computer with ideal properties like full connectivity, noise-freedom and arbitrarily long coherence time. In Noisy Intermediate-Scale Quantum (NISQ) devices, however, the number of qubits is highly limited and quantum operation error and qubit coherence are not negligible. Besides, the connectivity of physical qubits in a quantum processing unit (QPU) is also strictly constrained. Thereby, additional operations like SWAP gates have to be inserted to satisfy this constraint while preserving the functionality of the original circuit. This process is known as quantum circuit transformation. Adding additional gates will increase both the size and depth of a quantum circuit and therefore cause further decay of the performance of a quantum circuit. Thus it is crucial to minimize the number of added gates. In this paper, we propose an efficient method to solve this problem. We first choose by using simulated annealing an initial mapping which fits well with the input circuit and then, with the help of a heuristic cost function, stepwise apply the best selected SWAP gates until all quantum gates in the circuit can be executed. Our algorithm runs in time polynomial in all parameters including the size and the qubit number of the input circuit, and the qubit number in the QPU. Its space complexity is quadratic to the number of edges in the QPU. Experimental results on extensive realistic circuits confirm that the proposed method is efficient and can reduce by 57% on average the size of the output circuits when compared with the state-of-the-art algorithm on the most recent IBM quantum device viz. IBM Q20 (Tokyo).
Figures
Figures from the paper (7 more)
Reference graph
Works this paper leans on
-
[25]
Alwin Zulehner, Alexandru Paler, and Robert Wille. An efficient methodology for mapping quantum circuits to the ibm qx architectures.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018. 24
work page 2018
-
[13]
Tackling the qubit mapping problem for nisq-era quantum devices
Gushu Li, Yufei Ding, and Yuan Xie. Tackling the qubit mapping problem for nisq-era quantum devices. In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, pages 1001–1014. ACM, 2019
work page 2019
-
[7]
On the qubit routing problem.arXiv preprint arXiv:1902.08091, 2019
Alexander Cowtan, Silas Dilkes, Ross Duncan, Alexandre Krajenbrink, Will Simmons, and Seyon Sivara- jah. On the qubit routing problem.arXiv preprint arXiv:1902.08091, 2019
arXiv 1902
-
[1]
Qiskit: An open-source framework for quantum computing
Gadi Aleksandrowicz, Thomas Alexander, P Barkoutsos, L Bello, Y Ben-Haim, D Bucher, FJ Cabrera- Hernández, J Carballo-Franquis, A Chen, CF Chen, et al. Qiskit: An open-source framework for quantum computing. Accessed on: Mar, 16, 2019
work page 2019
-
[2]
Noga Alon, Fan RK Chung, and Ronald L Graham. Routing permutations on graphs via matchings.SIAM journal on discrete mathematics, 7(3):513–530, 1994
work page 1994
-
[3]
Elementary gates for quantum computation
Adriano Barenco, Charles H Bennett, Richard Cleve, David P DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A Smolin, and Harald Weinfurter. Elementary gates for quantum computation. Physical review A, 52(5):3457, 1995. 22
work page 1995
-
[4]
Kyle EC Booth, Minh Do, J Christopher Beck, Eleanor Rieffel, Davide Venturelli, and Jeremy Frank. Com- paring and integrating constraint programming and temporal planning for quantum circuit compilation. In Twenty-Eighth International Conference on Automated Planning and Scheduling, 2018
work page 2018
-
[5]
On the complexity of quantum circuit compilation
Adi Botea, Akihiro Kishimoto, and Radu Marinescu. On the complexity of quantum circuit compilation. In Eleventh Annual Symposium on Combinatorial Search, 2018
work page 2018
Show all 25 references
-
[6]
Circuit transformations for quantum architectures
Andrew M Childs, Eddie Schoute, and Cem M Unsal. Circuit transformations for quantum architectures. arXiv preprint arXiv:1902.09102, 2019
1902 arXiv
-
[8]
Qubit allocation for noisy intermediate-scale quantum computers.arXiv preprint arXiv:1810.08291, 2018
Will Finigan, Michael Cubeddu, Thomas Lively, Johannes Flick, and Prineha Narang. Qubit allocation for noisy intermediate-scale quantum computers.arXiv preprint arXiv:1810.08291, 2018
2018 arXiv
-
[9]
A software methodology for compiling quantum programs.Quantum Science and Technology, 3(2):020501, 2018
Thomas Häner, Damian S Steiger, Krysta Svore, and Matthias Troyer. A software methodology for compiling quantum programs.Quantum Science and Technology, 3(2):020501, 2018
2018
-
[10]
Quantum circuit compilers using gate commutation rules
Toshinari Itoko, Rudy Raymond, Takashi Imamichi, Atsushi Matsuo, and Andrew W Cross. Quantum circuit compilers using gate commutation rules. InProceedings of the 24th Asia and South Pacific Design Automation Conference, pages 191–196. ACM, 2019
2019
-
[11]
Optimization by simulated annealing.science, 220(4598):671–680, 1983
Scott Kirkpatrick, C Daniel Gelatt, and Mario P Vecchi. Optimization by simulated annealing.science, 220(4598):671–680, 1983
1983
-
[12]
Cnot circuit extraction for topologically-constrained quantum memories
Aleks Kissinger and Arianne Meijer-van de Griend. Cnot circuit extraction for topologically-constrained quantum memories. arXiv preprint arXiv:1904.00633, 2019
1904 arXiv
-
[14]
Approximation and hardness for token swapping.arXiv preprint arXiv:1602.05150, 2016
Tillmann Miltzow, Lothar Narins, Yoshio Okamoto, Günter Rote, Antonis Thomas, and Takeaki Uno. Approximation and hardness for token swapping.arXiv preprint arXiv:1602.05150, 2016
2016 arXiv
-
[15]
Noise-adaptive compiler mappings for noisy intermediate-scale quantum computers
Prakash Murali, Jonathan M Baker, Ali Javadi-Abhari, Frederic T Chong, and Margaret Martonosi. Noise-adaptive compiler mappings for noisy intermediate-scale quantum computers. In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming...
2019
-
[16]
Quantum circuit optimizations for nisq architectures
Beatrice Nash, Vlad Gheorghiu, and Michele Mosca. Quantum circuit optimizations for nisq architectures. arXiv preprint arXiv:1904.01972, 2019
1904 arXiv
-
[17]
Quantum information and quantum computation.Cambridge: Cambridge University Press, 2(8):23, 2000
Michael A Nielsen and Isaac L Chuang. Quantum information and quantum computation.Cambridge: Cambridge University Press, 2(8):23, 2000
2000
-
[18]
Extracting success from ibm’s 20-qubit machines using error-aware compilation.arXiv preprint arXiv:1903.10963, 2019
Shin Nishio, Yulu Pan, Takahiko Satoh, Hideharu Amano, and Rodney Van Meter. Extracting success from ibm’s 20-qubit machines using error-aware compilation.arXiv preprint arXiv:1903.10963, 2019
1903 arXiv
-
[19]
On the influence of initial qubit placement during nisq circuit compilation
Alexandru Paler. On the influence of initial qubit placement during nisq circuit compilation. InInterna- tional Workshop on Quantum Technology and Optimization Problems, pages 207–217. Springer, 2019
2019
-
[20]
Quantum computing in the nisq era and beyond.Quantum, 2:79, 2018
John Preskill. Quantum computing in the nisq era and beyond.Quantum, 2:79, 2018
2018
-
[21]
Qubit allocation
Marcos Yukio Siraichi, Vinícius Fernandes dos Santos, Sylvain Collange, and Fernando Magno Quintão Pereira. Qubit allocation. In Proceedings of the 2018 International Symposium on Code Generation and Optimization, pages 113–125. ACM, 2018
2018
-
[22]
John Wiley & Sons, 2014
Rodney Van Meter.Quantum networking. John Wiley & Sons, 2014. 23
2014
-
[23]
Temporal planning for compilation of quantum approximate optimization circuits
Davide Venturelli, Minh Do, Eleanor G Rieffel, and Jeremy Frank. Temporal planning for compilation of quantum approximate optimization circuits. InIJCAI, pages 4440–4446, 2017
2017
-
[24]
Computer-aided design for quantum computation
Robert Wille, Austin Fowler, and Yehuda Naveh. Computer-aided design for quantum computation. In 2018 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pages 1–6. IEEE, 2018
2018
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.