Pith. sign in

REVIEW 3 major objections 4 minor 58 references

Optimized Qubit Routing for Commuting Gates via Integer Programming

T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Qubit routing for commuting-gate circuits reduces to an exact integer-programming problem, the Token Meeting Problem, shown NP-hard with worst-case swap counts between $\Omega(n^2)$ and $O(n^2)$.

desk verdict Solid new combinatorial problem and IP models, but the advertised QAOA application rests on an aggregation assumption that fails for multi-round circuits. read the letter →

arxiv 2507.12199 v1 pith:S65E3VPC submitted 2025-07-16 math.OC quant-ph

Moritz Stargalla , Friedrich Wagner This is my paper · ORCID
classification math.OCquant-ph MSC 90C1090C2790C5781P6868Q17
keywords qubitroutingcommutinggatesTokenMeetingProblemintegerprogrammingquantumcircuitcompilationswapminimizationNP-hardnessQAOA
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper addresses a specific bottleneck in compiling quantum circuits: when all two-qubit gates commute, as in circuits for the Quantum Approximate Optimization Algorithm (QAOA), the compiler is free to reorder gates and must decide how to move qubits onto neighboring hardware positions with as few swap gates as possible, because swaps are a dominant source of error on current noisy devices. The authors claim that this qubit-routing-with-commuting-gates problem can be solved to a proven minimum swap count in two stages: first an exact integer program solves a combinatorial abstraction they call the Token Meeting Problem, returning an initial qubit placement and a sequence of swap layers; then a second integer program inserts the original gates into those layers to minimize circuit depth. To support the exact approach they prove the underlying problem NP-hard and establish worst-case bounds, showing that $O(n^2)$ swaps always suffice for $n$ qubits while some instances genuinely require $\Omega(n^2)$ swaps. Their experiments on small grid-like and cycle-like hardware report up to ten times fewer swaps and up to three times shallower circuits than the SABRE heuristic, and faster solves than the near-exact method they compare against. The payoff, if the claim holds, is a certificate-backed guarantee of minimal swap cost that heuristics cannot offer.

What carries the argument

The central object is the Token Meeting Problem: tokens (logical qubits) are moved by a sequence of swap layers, each layer a matching of the hardware graph $H$, until every connection of the algorithm graph $A$ has been placed on an edge of $H$ at some time. Four pieces of machinery carry the argument. Lemma 2.7 gives the halting rule: because $MS(H,A,t)-t$ is strictly decreasing for all $t\ge MT(H,A)$ and reaches zero exactly at $t=MS(H,A)$, the loop that solves fixed-step models for increasing $t$ until $MS(H,A,t)=t$ provably outputs the global swap optimum. The integer program ZIEQ, a network-flow formulation on a time-expanded copy of the hardware graph with binary location variables and linearized connection-satisfied variables $z^t_{pq}$, proved fastest among the four proposed models in the experiments. The polyhedral results in the appendix give exact linear descriptions of the polytopes of (placement of token $p$, placement of token $q$, connection indicator) triples in terms of inclusion-maximal bicliques and antibicliques of the corresponding bipartite graph, and are stated for a generalized family of polytopes with potential uses beyond this work. Finally, the asymptotic bounds come from a constructive depth-first-search swap algorithm that routes any tree instance with at most $(n-2)^2$ swaps, together with degree-counting arguments (the parameters $\Delta'(H)$ and $D(H)$) bounding how many new connections a single swap or a single step can satisfy, which yield the $\Omega(n^2)$ and $\Omega(n)$ lower bounds.

What would settle it

Compute $MT(QSST_n,K_n)$ exactly for quadratic subdivided stars with $n=m^2+1$ (10, 17, 26, 37, ...) using the paper's own integer programs: if the minimum step count grows faster than linearly in $n$, Conjecture 3.12, which asserts $\Theta(n)$ steps for all trees, is refuted. For the central swap-optimality guarantee, build a circuit from two commuting blocks that share a qubit pair (for instance two QAOA layers on the same problem graph) and compare the pipeline's output against exhaustive enumeration that respects block order: if the aggregated model returns a circuit that is not equivalent to the original, or if respecting block order forces strictly more swaps, then the Section 2 aggregation assumed an order freedom the original circuit does not possess.

Watch

Extended reading notes

Core claim

The paper's central claim is that qubit routing for circuits consisting of commuting two-qubit gates reduces to an exact combinatorial problem, the Token Meeting Problem (TMP), which it then solves to proven optimality by integer programming. In the TMP, the hardware is an undirected graph $H=(V,E)$, the circuit is condensed into an algorithm graph $A=(Q,C)$ whose edges are the pairs of logical qubits that must interact, and a solution is an initial bijection of qubits to hardware nodes plus a sequence of swap layers, each a matching of $E$; the adjacency condition requires that every connection of $A$ sits on an edge of $H$ at some time step. The authors prove that both natural decision versions of the TMP, minimizing steps and minimizing swaps, are NP-complete by reduction from subgraph isomorphism, and they prove matching asymptotic bounds: any instance on $n$ nodes admits a solution with $O(n^2)$ swaps, and instances with constant-degree hardware and complete algorithm graph require $\Omega(n^2)$ swaps. On the algorithmic side, Lemma 2.7 shows the sequence $MS(H,A,t)-t$ decreases strictly once solutions exist, so the fixed-step integer programs used to compute $MS(H,A,t)$ can be iterated in a loop that provably terminates at the global minimum swap count. The resulting two-stage pipeline first fixes a swap-optimal layer structure and then schedules gates into it, and the computational study reports that this exact pipeline uses materially fewer swaps and shallower circuits than existing heuristics on the tested hardware topologies.

Load-bearing premise

The guarantee rests on the circuit's two-qubit gates genuinely commuting with one another, so that condensing every qubit pair into a single edge of the algorithm graph loses no ordering information, and on the only permitted routing move being a swap along an undirected hardware edge; if either premise fails, the Token Meeting model and its swap-optimal guarantee do not apply.

Editorial extensions

If this is right

  • QAOA and Hamiltonian-simulation circuits (all gates commuting) can be compiled with a certificate-backed minimum swap count, and among all swap-optimal solutions the second-stage scheduler produces one of minimum depth.
  • Every $n$-qubit commuting-gate instance is routable with $O(n^2)$ swaps, and the bound is tight: constant-degree hardware graphs with all-to-all algorithm graphs require $\Omega(n^2)$ swaps.
  • The Token Meeting Problem is NP-hard in both its step and swap variants, so no polynomial-time exact algorithm is expected and integer programming with polyhedral strengthening is a reasonable exact route for small and mid-size instances.
  • The depth-scheduling integer program solved every tested instance in under $0.12$ seconds, so once a swap layer sequence is known, depth minimization is cheap and could be appended to heuristic swap strategies.
  • Fixing the initial qubit placement for complete algorithm graphs reduces integer-programming runtime by factors of 2 to 12 in the experiments, which is directly relevant to QAOA on all-to-all problem graphs.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The Token Meeting abstraction is not tied to swap-count minimization: the same layer-skeleton machinery would produce depth-first or noise-aware routings by changing only the second-stage objective, since the first stage's optimality proof is independent of what is optimized afterward.
  • For circuits made of several commuting blocks (as in multi-layer QAOA), aggregating gates by qubit pair relaxes genuine ordering constraints, so the pipeline's swap count is a lower bound on what the unrelaxed circuit needs; that makes it a candidate fast prescreener or bound-prover for heuristic compilers even where exactness does not transfer.
  • The generalized biclique and antibiclique linear descriptions were proven for arbitrary bipartite graphs with partitions, so they apply to any integer program containing products of two assignment vectors, such as pairing or matching formulations with adjacency requirements.
  • If a quadratic subdivided star family turns out to require $\omega(n)$ steps, the true worst-case step count for trees lies strictly between the $\Theta(n)$ conjecture and the $O(n^{3/2})$ theorem, giving a sharp target for improved upper-bound constructions.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper proposes an exact two-step integer-programming approach for qubit routing of circuits whose two-qubit gates are commuting. In the first step, a circuit is abstracted into an algorithm graph A=(Q,C) in which all gates on the same pair of logical qubits are merged into one edge, and the Token Meeting Problem (TMP) is solved to find an initial mapping plus a sequence of swap matchings minimizing the total number of swaps. In the second step, the original gates are inserted into the swap layers or into new empty layers to minimize depth. The authors prove NP-completeness of two decision versions of TMP, give O(n^2) upper and Omega(n^2) lower bounds on the number of swaps, derive bounds on the number of steps, develop four integer programming models (YEQ, YIEQ, ZEQ, ZIEQ), prove linear descriptions of two associated polytopes, and report computational comparisons against SABRE, the Weidenfeller et al. heuristic, and TB-OLSQ2.

Significance. Taken as a standalone combinatorial optimization problem, the TMP core of this paper is solid and useful: the NP-hardness proofs are explicit, the asymptotic bounds are self-contained and parameter-free, the IP models are carefully developed, and the code is publicly available. The polyhedral results may be of independent interest. However, the paper's stated application to QAOA and its claim that the implemented method is guaranteed swap-optimal are not supported by the current text and experiments. The main contribution is therefore best read as an exact method for a restricted single-block commuting-gate model, not as a validated method for full multi-round QAOA compilation.

major comments (3)
  1. [Section 2, first paragraph; Section 1, p. 2] The reduction from a circuit to the algorithm graph A=(Q,C) aggregates all two-qubit gates on the same pair of logical qubits into a single edge, and the TMP requires each connection to be adjacent at least once. This is valid only if all two-qubit gates in the circuit can be reordered freely with no intervening non-commuting gates. In the motivating QAOA application, each round contains a commuting ZZ block followed by X rotations, and an X rotation on qubit i does not commute with a ZZ gate incident to i; consequently two ZZ gates on the same pair in different rounds cannot be executed in a single adjacency event. The TMP solution may make each pair adjacent only once and therefore may not correspond to any valid routing of the original multi-round circuit. The swap-optimality guarantee stated in the abstract and in Section 2 thus applies only to a single commuting block, not to the full QAOA circuits cited as the motivating application. The authors should either restrict the scope of the optimality claim accordingly or extend the model to handle multiple commuting blocks separated by non-commuting gates.
  2. [Section 5.3, definition of (CQR); Section 5.2] The complete algorithm in Section 2.1 requires computing MS(H,A) via Algorithm 1, which in Section 5.2 is implemented by solving ZIEQ with MS(H,A,MT(H,A))-1 steps and then solving ZOPT to certify infeasibility or find a strictly better solution. The CQR method used in the experiments solves only ZIEQ (with the step-optimal number of steps), which yields MS(H,A,MT(H,A)) and is not guaranteed to equal MS(H,A). Section 5.2 reports instances where these two values differ by up to 3 swaps, so the swap counts reported for CQR are not certified optimal. To support the paper's central optimality claim, the computational study should include ZOPT in CQR, or CQR should be explicitly labeled as a near-optimal variant and the abstract/conclusion adjusted accordingly.
  3. [Section 5.3, definition of (WEI)] The WEI baseline is supplied with a swap-layer strategy attaining MS(H,K_n,MT(H,K_n)) and a minimal edge coloring, regardless of the actual algorithm graph A being compiled. The reported factor-of-10 swap overhead for sparse algorithm graphs therefore reflects the mismatch between a strategy optimized for the complete graph and the actual instance, rather than an intrinsic limitation of the Weidenfeller et al. method. To support the conclusion that the proposed approach outperforms this heuristic, the strategy supplied to WEI should be adapted to the actual instance (or the comparison should be restricted to cases where a K_n-optimal strategy is a natural baseline). As written, the claim that WEI uses 'up to 10 times more swaps' is an artifact of the experimental setup.
minor comments (4)
  1. [Algorithm 2, line 8] The instruction 'k←k+1' inside the for-loop is either redundant or an error; if the intent is to skip some nodes, this should be expressed with a continue statement or by restructuring the loop.
  2. [Section 1, p. 2] The sentence 'The presence of single-qubit gates does not alter the resulting qubit routing problem' is too strong; it is true only if the single-qubit gates commute with the two-qubit gates or can be ignored, which is not the case in QAOA. The authors should qualify this statement.
  3. [Section 4.4 and Section 5.1] The claim that the derived linear descriptions speed up solution time by a factor of up to 5 is not directly evidenced by the reported experiments, which compare complete models YEQ, YIEQ, ZEQ, and ZIEQ rather than solving the same model with and without the polytope cuts. Please clarify how this speed-up factor is measured.
  4. [Throughout] The code availability statement says 'publicly available here' without an actual URL or repository identifier; this should be added before publication.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the optimality proofs, NP-hardness reduction, and polytope derivations are self-contained, and the self-citations are confined to related work.

full rationale

The central derivation chain is not circular. The two-stage approach solves the Token Meeting Problem exactly by integer programming (Section 4), and the optimality of the swap count follows from the IP formulation's one-to-one encoding of swap solutions (2a)-(2i) and Lemma 2.7, not from any fitted parameter or assumed conclusion. NP-hardness is proved by a direct reduction from Subgraph Isomorphism in Appendix A; the asymptotic bounds in Theorems 3.5 and 3.9 are proven from Lemma 3.7 and Proposition 3.8 with elementary counting arguments. The polytope results cite Kuen et al. [47] as an external source, but the paper supplies its own proofs (Theorems B.2, B.8, B.9) and total-unimodularity argument; this is independent support, not self-citation. The self-citations ([7], [9]) appear only in the related-work survey and are not load-bearing. The only 'by construction' statement is in the experimental comparison, where (WEI) is intentionally supplied with an optimal TMP strategy and the paper explicitly says 'By construction, (WEI) uses the same number of swaps as (CQR) for the complete algorithm graph'; this is a transparently disclosed benchmark setup, not a prediction masquerading as a result. The modeling assumption that all two-qubit gates on a pair can be aggregated (Section 2) is a scoping restriction about which circuits are covered; if single-qubit gates break commutativity between blocks, that is a correctness/scope concern, not a circular derivation. The paper also openly states the depth-scheduling limitation ('scheduling all swap gates belonging to the same matching in a single swap layer might exclude depth-optimal solutions'), so no unproven global depth claim is smuggled in.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No fitted parameters are used in the derivation; the models are exact. The axioms are standard graph-theoretic results, a cited polyhedral theorem, and the domain assumption that commuting-gate circuits can be abstracted into a static graph. The Token Meeting Problem is a new problem formulation rather than a postulated physical entity.

assumptions (5)
  • standard math Vizing's theorem: any graph with maximum degree Delta can be edge-colored with Delta+1 colors
    Used in Section 5.3 to bound the number of empty layers needed for depth-optimal gate insertion.
  • standard math Subgraph Isomorphism is NP-complete
    Used in the NP-hardness reduction in Theorem 3.16 and Appendix A.
  • domain assumption A circuit whose gates all commute can be represented by a static graph with one edge per pair of logical qubits
    Used in Section 2 to define the Token Meeting Problem; valid for QAOA blocks and Hamiltonian simulation, but not for general circuits.
  • standard math Bipartite implication polytope facets from Kuen et al. [47] are valid
    Used in Appendix B.2 to derive linear descriptions of P_pqt and P<_pqt; the cited paper provides the facet classification.
  • domain assumption Hardware graph is undirected and swapping is the only routing primitive
    Throughout, swap gates are transpositions along hardware edges; directional connectivity or other routing mechanisms are out of scope.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimized Qubit Routing for Commuting Gates via Integer Programming." pith.science (2026). https://pith.science/paper/S65E3VPC

@misc{pith2026250712199,
  author       = {Pith},
  title        = {Pith review of: Optimized Qubit Routing for Commuting Gates via Integer Programming},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/S65E3VPC}},
  note         = {Machine review of arXiv:2507.12199}
}
read the original abstract

Quantum computers promise to outperform their classical counterparts at certain tasks. However, existing quantum devices are error-prone and restricted in size. Thus, effective compilation methods are crucial to exploit limited quantum resources. In this work, we address the problem of qubit routing for commuting gates, which arises, for example, during the compilation of the well-known Quantum Approximate Optimization Algorithm. We propose a two-step decomposition approach based on integer programming, which is guaranteed to return an optimal solution. To justify the use of integer programming, we prove NP-hardness of the underlying optimization problem. Furthermore, we derive asymptotic upper and lower bounds on the quality of a solution. We develop several integer programming models and derive linear descriptions of related polytopes, which generalize to applications beyond this work. Finally, we conduct a computational study showing that our approach outperforms existing heuristics in terms of quality and exact methods in terms of runtime.

Figures

Figures reproduced from arXiv: 2507.12199 by the authors.

Figure 1
Figure 1. Example of a quantum circuit with commuting gates (left), a hardware graph (center), and a [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. A routed quantum circuit that is equivalent to the circuits in Figure [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 3
Figure 3. The overall solution approach. First, a quantum circuit [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figures from the paper (13 more)
Figure 4
Figure 4. Figure 4: An instance to the Token Meeting Problem, defined by the graphs [PITH_FULL_IMAGE:figures/full_fig_p005_4.png]
Figure 5
Figure 5. Figure 5: Two solutions S1 (left) and S2 (right) to the TMP instance of [PITH_FULL_IMAGE:figures/full_fig_p005_5.png]
Figure 6
Figure 6. Figure 6: Illustration of two steps of Algorithm 2. For each step t, the nodes vt (white), lt (orange) and the node labels ℓ are shown on the left. Each edge involved in a swap is highlighted in blue, with labels denoting the order in which the edge swaps are applied to move qt …
Figure 7
Figure 7. Figure 7: A sequence of 7 steps where each token is placed on the upper leaf at least once and the token [PITH_FULL_IMAGE:figures/full_fig_p010_7.png]
Figure 8
Figure 8. Figure 8: An example for the time-expanded hardware [PITH_FULL_IMAGE:figures/full_fig_p012_8.png]
Figure 9
Figure 9. Figure 9: Graphs H1 (left) and H2 (right). shown in [PITH_FULL_IMAGE:figures/full_fig_p015_9.png]
Figure 10
Figure 10. Figure 10: Runtime comparison for all models and instances of [PITH_FULL_IMAGE:figures/full_fig_p016_10.png]
Figure 11
Figure 11. Figure 11: Minimum number of steps (blue) and the minimum number of swaps (green) for instances of [PITH_FULL_IMAGE:figures/full_fig_p016_11.png]
Figure 12
Figure 12. Figure 12: Runtime comparison between ZIEQ and ZIEQ + ZOPT for H1 (left) and H2 (right). 5.2 The Cost of Optimality In Section 5.1, we have computed the value of MS(H, A, MT(H, A)). To obtain a swap-optimal solution, we now solve the fastest model ZIEQ with MS(H, A, MT(H, A)) − …
Figure 13
Figure 13. Figure 13: Visualization of the process of turning a TMP solution into a routed circuit. [PITH_FULL_IMAGE:figures/full_fig_p018_13.png]
Figure 15
Figure 15. Figure 15: Comparison with heuristics. 2 4 6 8 9 11 13 15 1718 20 22 24 2627 29 31 33 3536 Number of edges 10−2 10−1 100 101 102 103 runtime in s ZIEQ TB-OLSQ2 2 3 5 6 7 9 10 12 13 14 16 17 19 20 21 23 24 26 27 28 Number of edges 10−3 10−2 10−1 100 101 102 103 runtime in s ZIEQ …
Figure 16
Figure 16. Figure 16: Runtime comparison between ZIEQ and TB-OLSQ2 for H1 (left) and H2 (right). 20 [PITH_FULL_IMAGE:figures/full_fig_p020_16.png]
Figure 17
Figure 17. Figure 17: Transforming a Subgraph Isomorphism instance (G1, G2) into a STMP and PTMP instance (G′ 1 , G′ 2 ) as defined in the proof of Theorem 3.16. B.1 Linearization 1 The goal of this subsection is to derive a linear description of P ≤ pq. Recall that P ≤ pq = conv{(w t pi, …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

58 extracted references · 40 canonical work pages

  1. [1]

    Quantum algorithms for quantum chemistry and quantum materials science.Chemical Reviews, 120(22):12685–12717, Octo- ber 2020

    Bela Bauer, Sergey Bravyi, Mario Motta, and Garnet Kin-Lic Chan. Quantum algorithms for quantum chemistry and quantum materials science.Chemical Reviews, 120(22):12685–12717, Octo- ber 2020. doi:10.1021/acs.chemrev.9b00829

    doi:10.1021/acs.chemrev.9b00829 2020

  2. [2]

    Quantum algorithm for alchemical optimization in material design.Chemical science, 12(12):4345–4352, 2021

    Panagiotis Kl Barkoutsos, Fotios Gkritsis, Pauline J Ollitrault, Igor O Sokolov, Stefan Woerner, and Ivano Tavernelli. Quantum algorithm for alchemical optimization in material design.Chemical science, 12(12):4345–4352, 2021

    work page 2021

  3. [3]

    Cerezo, Guillaume Verdon, Hsin-Yuan Huang, Lukasz Cincio, and Patrick J

    M. Cerezo, Guillaume Verdon, Hsin-Yuan Huang, Lukasz Cincio, and Patrick J. Coles. Challenges and opportunities in quantum machine learning.Nature Computational Science, 2(9):567–576, Sep

    work page

  4. [4]

    Egger, Bruce G

    Amira Abbas, Andris Ambainis, Brandon Augustino, Andreas Bärtschi, Harry Buhrman, Carleton Coffrin, Giorgio Cortiana, Vedran Dunjko, Daniel J. Egger, Bruce G. Elmegreen, Nicola Franco, Filippo Fratini, Bryce Fuller, Julien Gacon, Constantin Gonciulea, Sander Gribling, Swati Gupta, Stuart Hadfield, Raoul Heese, Gerhard Kircher, Thomas Kleinert, Thorsten Ko...

    2024

  5. [5]

    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

  6. [6]

    Bishop, Oktay Günlük, and Petar Jurcevic

    Giacomo Nannicini, Lev S. Bishop, Oktay Günlük, and Petar Jurcevic. Optimal qubit assignment and routing via integer programming.ACM Transactions on Quantum Computing, 4(1), October

    work page

  7. [7]

    Improving quantum computation by optimized qubit routing

    Friedrich Wagner, Andreas Bärmann, Frauke Liers, and Markus Weissenbäck. Improving quantum computation by optimized qubit routing. Journal of Optimization Theory and Applications , 197(3):1161–1194, May 2023. URL: http://dx.doi.org/10.1007/s10957-023-02229-w, doi: 10.1007/s10957-023-02229-w. 22

    doi:10.1007/s10957-023-02229-w 2023

  8. [8]

    Baker, Ali Javadi-Abhari, Frederic T

    Prakash Murali, Jonathan M. Baker, Ali Javadi-Abhari, Frederic T. Chong, and Margaret Mar- tonosi. Noise-adaptive compiler mappings for noisy intermediate-scale quantum computers. In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Program- ming Languages and Operating Systems, ASPLOS ’19, page 1015–1029, New York, NY...

    arXiv 2019

Show all 58 references
  1. [9]

    Optimized noise suppression for quantum circuits

    Friedrich Wagner, Daniel J Egger, and Frauke Liers. Optimized noise suppression for quantum circuits. INFORMS Journal on Computing, 37(1):22–41, 2025

    2025

  2. [10]

    Nielsen and Isaac L

    Michael A. Nielsen and Isaac L. Chuang.Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010

    2010

  3. [11]

    The solovay-kitaev algorithm.arXiv preprint quant- ph/0505030, 2005

    Christopher M Dawson and Michael A Nielsen. The solovay-kitaev algorithm.arXiv preprint quant- ph/0505030, 2005

    2005

  4. [12]

    A quantum approximate optimization al- gorithm

    Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization al- gorithm. arXiv preprint arXiv:1411.4028, 2014

    2014 arXiv

  5. [13]

    Egger, David Ochsner, and Stefan Woerner

    Almudena Carrera Vazquez, Daniel J. Egger, David Ochsner, and Stefan Woerner. Well-conditioned multi-product formulas for hardware-friendly Hamiltonian simulation.Quantum, 7:1067, July 2023. doi:10.22331/q-2023-07-25-1067

    2023 doi

  6. [14]

    Quantum circuit synthesis and compilation optimization: Overview and prospects

    Yan Ge, Wu Wenjie, Chen Yuheng, Pan Kaisen, Lu Xudong, Zhou Zixiang, Wang Yuhan, Wang Ruocheng, and Yan Junchi. Quantum circuit synthesis and compilation optimization: Overview and prospects. arXiv preprint arXiv:2407.00736, 2024

    2024

  7. [15]

    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, 38(7):1226–1236, 2018

    2018

  8. [16]

    On the qubit routing problem.arXiv preprint arXiv:1902.08091, 2019

    Alexander Cowtan, Silas Dilkes, Ross Duncan, Alexandre Krajenbrink, Will Simmons, and Seyon Sivarajah. On the qubit routing problem.arXiv preprint arXiv:1902.08091, 2019

    1902 arXiv

  9. [17]

    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, 2019

    2019

  10. [18]

    t| ket>: a retargetable compiler for nisq devices.Quantum Science and Technology, 6(1):014003, 2020

    Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington, and Ross Duncan. t| ket>: a retargetable compiler for nisq devices.Quantum Science and Technology, 6(1):014003, 2020

    2020

  11. [19]

    Compilation for dynamically field- programmable qubit arrays with efficient and provably near-optimal scheduling

    Daniel Bochen Tan, Wan-Hsuan Lin, and Jason Cong. Compilation for dynamically field- programmable qubit arrays with efficient and provably near-optimal scheduling. In Proceedings of the 30th Asia and South Pacific Design Automation Conference, pages 921–929, 2025

    2025

  12. [20]

    Haqa: A hardware-guided and fidelity-aware strategy for efficient qubit mapping optimization.arXiv preprint arXiv:2504.16468, 2025

    Wenjie Sun, Xiaoyu Li, Lianhui Yu, Zhigang Wang, Geng Chen, Desheng Zheng, and Guowu Yang. Haqa: A hardware-guided and fidelity-aware strategy for efficient qubit mapping optimization.arXiv preprint arXiv:2504.16468, 2025

    2025 arXiv

  13. [21]

    Optimality study of existing quantum computing layout synthesis tools

    Bochen Tan and Jason Cong. Optimality study of existing quantum computing layout synthesis tools. IEEE Transactions on Computers, 70(9):1363–1373, 2020

    2020

  14. [22]

    Mapping quantum circuits to ibm qx archi- tectures using the minimal number of swap and h operations

    Robert Wille, Lukas Burgholzer, and Alwin Zulehner. Mapping quantum circuits to ibm qx archi- tectures using the minimal number of swap and h operations. InProceedings of the 56th Annual Design Automation Conference 2019, pages 1–6, 2019

    2019

  15. [23]

    Qubit mapping and routing via maxsat

    Abtin Molavi, Amanda Xu, Martin Diges, Lauren Pick, Swamit Tannu, and Aws Albarghouthi. Qubit mapping and routing via maxsat. In 2022 55th IEEE/ACM international symposium on Microarchitecture (MICRO), pages 1078–1091. IEEE, 2022

    2022

  16. [24]

    Quantum circuit mapping based on incremental and parallel sat solving

    Jiong Yang, Yaroslav A Kharkov, Yunong Shi, Marijn JH Heule, and Bruno Dutertre. Quantum circuit mapping based on incremental and parallel sat solving. In27th International Conference on Theory and Applications of Satisfiability Testing (SAT 2024), pages 29–1. Schloss Dagstuhl...

    2024

  17. [25]

    Optimal layout synthesis for deep quantum circuits on nisq processors with 100+ qubits.arXiv preprint arXiv:2403.11598, 2024

    Irfansha Shaik and Jaco Van de Pol. Optimal layout synthesis for deep quantum circuits on nisq processors with 100+ qubits.arXiv preprint arXiv:2403.11598, 2024. 23

    2024 arXiv

  18. [26]

    Optimal layout-aware cnot circuit synthesis with qubit per- mutation

    Irfansha Shaik and Jaco van de Pol. Optimal layout-aware cnot circuit synthesis with qubit per- mutation. InECAI 2024, pages 4207–4215. IOS Press, 2024

    2024

  19. [27]

    Optimal layout synthesis for quantum computing

    Bochen Tan and Jason Cong. Optimal layout synthesis for quantum computing. InProceedings of the 39th International Conference on Computer-Aided Design, pages 1–9, 2020

    2020

  20. [28]

    Scalable optimal lay- out synthesis for nisq quantum processors

    Wan-Hsuan Lin, Jason Kimko, Bochen Tan, Nikolaj Bjørner, and Jason Cong. Scalable optimal lay- out synthesis for nisq quantum processors. In2023 60th ACM/IEEE Design Automation Conference (DAC), pages 1–6. IEEE, 2023

    2023

  21. [29]

    Valor, Julien Gacon, Caroline Tornow, Luciano Bello, Stefan Wo- erner, and Daniel J

    Johannes Weidenfeller, Lucia C. Valor, Julien Gacon, Caroline Tornow, Luciano Bello, Stefan Wo- erner, and Daniel J. Egger. Scaling of the quantum approximate optimization algorithm on super- conducting qubit based hardware. Quantum, 6:870, December 2022. URL: http://dx.doi.or...

    2022 doi

  22. [30]

    2qan: Aquantumcompilerfor2-localqubithamiltoniansimulation algorithms

    LinglingLaoandDanEBrowne. 2qan: Aquantumcompilerfor2-localqubithamiltoniansimulation algorithms. InProceedings of the 49th Annual International Symposium on Computer Architecture, pages 351–365, 2022

    2022

  23. [31]

    A sat approach to the initial mapping problem in swap gate insertion for commuting gates

    Atsushi Matsuo, Shigeru Yamashita, and Daniel J Egger. A sat approach to the initial mapping problem in swap gate insertion for commuting gates. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 106(11):1424–1431, 2023

    2023

  24. [32]

    Exploiting the regular structure of modern quantum architectures for compiling and optimizing programs with permutable operators

    Yuwei Jin, Fei Hua, Yanhao Chen, Ari Hayes, Chi Zhang, and Eddy Z Zhang. Exploiting the regular structure of modern quantum architectures for compiling and optimizing programs with permutable operators. In Proceedings of the 28th ACM International Conference on Architectural S...

    2023

  25. [33]

    Improved qubit routing for qaoa circuits, 2023

    Ayse Kotil, Fedor Simkovic, and Martin Leib. Improved qubit routing for qaoa circuits, 2023. URL: https://arxiv.org/abs/2312.15982, arXiv:2312.15982

    2023 arXiv

  26. [34]

    Assessing quantum layout synthesis tools via known optimal-swap cost benchmarks.arXiv preprint arXiv:2502.08839, 2025

    Shuohao Ping, Wan-Hsuan Lin, Daniel Bochen Tan, and Jason Cong. Assessing quantum layout synthesis tools via known optimal-swap cost benchmarks.arXiv preprint arXiv:2502.08839, 2025

    2025 arXiv

  27. [35]

    Springer Publishing Company, Incorporated, 2008

    John Adrian Bondy and Uppaluri Siva Ramachandra Murty.Graph theory. Springer Publishing Company, Incorporated, 2008

    2008

  28. [36]

    Algorithmic theory of qubit routing

    Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto. Algorithmic theory of qubit routing. InAlgorithms and Data Structures Symposium, pages 533–546. Springer, 2023

    2023

  29. [37]

    Progress in mathematical programming solvers from 2001 to 2020.EURO Journal on Computational Optimization, 10:100031,

    Thorsten Koch, Timo Berthold, Jaap Pedersen, and Charlie Vanaret. Progress in mathematical programming solvers from 2001 to 2020.EURO Journal on Computational Optimization, 10:100031,

    2001

  30. [38]

    Dey, Thomas Kalinowski, Marco Molinaro, and Fabian Rigterink

    Natashia Boland, Santanu S. Dey, Thomas Kalinowski, Marco Molinaro, and Fabian Rigterink. Bounding the gap between the mccormick relaxation and the convex hull for bilinear functions. Mathematical Programming, 162(1–2):523–535, May 2016. URL: http://dx.doi.org/10.1007/ s10107-...

    2016 doi

  31. [39]

    doi:10.1016/j.ejco.2022.100031

    2022

  32. [40]

    Quantum approximate optimization of non-planar graph problems on a planar superconducting processor.Nature Physics, 17(3):332–336, 2021

    Matthew P Harrigan, Kevin J Sung, Matthew Neeley, Kevin J Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C Bardin, Rami Barends, Sergio Boixo, et al. Quantum approximate optimization of non-planar graph problems on a planar superconducting processor.Nature Physics, 1...

    2021

  33. [41]

    A new reformulation-linearization technique for bilinear programming problems

    Hanif D Sherali and Amine Alameddine. A new reformulation-linearization technique for bilinear programming problems. Journal of Global optimization, 2:379–410, 1992

    1992

  34. [42]

    Wood, Jake Lishman, Julien Gacon, Simon Martiel, Paul D

    Ali Javadi-Abhari, Matthew Treinish, Kevin Krsulich, Christopher J. Wood, Jake Lishman, Julien Gacon, Simon Martiel, Paul D. Nation, Lev S. Bishop, Andrew W. Cross, Blake R. Johnson, and Jay M. Gambetta. Quantum computing with Qiskit, 2024. arXiv:2405.08810, doi:10.48550/ arXi...

    2024 doi arXiv

  35. [43]

    Topological and subsystem codes on low-degree graphs with flag qubits.Physical Review X, 10(1):011022, 2020

    Christopher Chamberland, Guanyu Zhu, Theodore J Yoder, Jared B Hertzberg, and Andrew W Cross. Topological and subsystem codes on low-degree graphs with flag qubits.Physical Review X, 10(1):011022, 2020

    2020

  36. [44]

    Springer Berlin Heidelberg, 2005

    Ingo Wegener.Complexity Theory: Exploring the Limits of Efficient Algorithms, page 81. Springer Berlin Heidelberg, 2005. doi:10.1007/3-540-27477-4

    2005 doi

  37. [45]

    Z3: An efficient smt solver

    Leonardo De Moura and Nikolaj Bjørner. Z3: An efficient smt solver. InInternational conference on Tools and Algorithms for the Construction and Analysis of Systems, pages 337–340. Springer, 2008

    2008

  38. [46]

    Integer programming models

    Michele Conforti, Gérard Cornuéjols, Giacomo Zambelli, Michele Conforti, Gérard Cornuéjols, and Giacomo Zambelli. Integer programming models. Springer, 2014

    2014

  39. [47]

    John Wiley & Sons, 1998

    A Schrijver.Theory of linear and integer programming. John Wiley & Sons, 1998

    1998

  40. [49]

    The bipartite implication polytope: Con- ditional relations over multiple sets of binary variables

    Tobias Kuen, Robert Burlacu, and Patrick Gemander. The bipartite implication polytope: Con- ditional relations over multiple sets of binary variables. Optimization Online, 2025. URL: https://optimization-online.org/?p=26208. A Proof of NP-completeness In this section, we reduc...

    2025

  41. [50]

    if” direction holds by definition. For the “only if

    The “if” direction holds by definition. For the “only if” direction, suppose thatG′ 2 is isomorphic to a subgraph ofG′

  42. [51]

    Let σ : V (G′ 2)↦→V (G′

  43. [52]

    be a bijection such that(i,j )∈ E(G′

  44. [53]

    We know thatσ maps v∗ 2 to a node in V (G′

    implies (σ(i),σ (j))∈ E(G′ 1). We know thatσ maps v∗ 2 to a node in V (G′

  45. [54]

    exchange

    which is connected to all other nodes. Ifσ mapsv∗ 2 to a nodev∗̸=v∗ 1, we can “exchange”v∗ and v∗

  46. [55]

    Consequently, we define the bijectionσ′ : V (G′ 2)↦→V (G′

  47. [56]

    Thus, (i,j )∈E(G′

    = v∗ 1, σ′(σ−1(v∗ 1)) = σ(v∗ 2), andσ′(v) =σ(v) for all other nodesv∈V (G′ 2). Thus, (i,j )∈E(G′

  48. [57]

    Restrictingσ′ to the nodes ofˆG1, we obtain thatˆG2 is isomorphic to a subgraph ofˆG1 and thus alsoG2 is isomorphic to a subgraph ofG1

    still implies(σ′(i),σ′(j))∈E(G′ 1). Restrictingσ′ to the nodes ofˆG1, we obtain thatˆG2 is isomorphic to a subgraph ofˆG1 and thus alsoG2 is isomorphic to a subgraph ofG1. Finally, for both STMP and PTMP, we construct the instance with A =G′ 2,H =G′ 1, andk = 0. Lemma A.2 esta...

  49. [58]

    B.1 Linearization 1 The goal of this subsection is to derive a linear description ofP≤ pq

    as defined in the proof of Theorem 3.16. B.1 Linearization 1 The goal of this subsection is to derive a linear description ofP≤ pq. Recall that P≤ pq = conv{(wt pi,wt qj,yt pqij)∈{ 0, 1}T(2|V|+| ¯E|) : (2c),(3c)−(3e)}. More generally, we study the following polytope. Definitio...

  50. [2022]

    doi:10.1038/s43588-022-00311-3

    doi

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.