Entanglement-Aware Quantum Circuit Optimization through Globally Optimal Partitioning

CCS Concepts: • Applied computing → Physics; • Software and its engineering → Software libraries and repositories; • Theory of computation → Quantum computation theory; • Mathematics of computing → Solvers.

Additional Key Words and Phrases: Quantum, gate synthesis, quantum circuit, optimization, OSR, entanglement, partitioning

Introduction

Partitioning quantum circuits into valid multi-qubit blocks is a core primitive in modern compilation workflows or quantum computer simulation performance. It directly affects gate fusion (i.e. merging multiple gates as a single entity to reduce the arithmetic operations), and quantum circuit resynthesis with hardware-aware transpilation. The strategy to select the partitions determines both the optimization opportunities accessible during the circuit optimization and the computational cost of exploiting them. In the noisy quantum computer era, where gate count, depth, and noise budgets are all constrained, better partitioning can translate into substantially better circuit executables.

This importance has become even clearer as quantum compilers increasingly rely on block-level numerical optimization. Parameterized circuit instantiation has emerged as a powerful primitive for both circuit optimization and gate-set transpilation, enabling global improvements beyond purely local rewrite rules [1]. Likewise, synthesis frameworks such as QFAST show that expressive multi-qubit building blocks combined with numerical optimization can substantially improve circuit quality while remaining scalable in practice [2]. Subsequent work has pushed these synthesis perspectives in several complementary directions: LEAP improves the scalability of numerical-optimization-based synthesis through incremental prefixes and resynthesis [3], QSeed uses machine learning to seed synthesis and reduce search cost while preserving solution quality [4], QFactor accelerates circuit instantiation itself through a domain-specific tensor-network-based optimizer [5], and permutation-aware synthesis shows that jointly reasoning

Authors’ Contact Information: Gregory Morse, Department of Programming Languages and Compilers, Eötvös Loránd University, Budapest, Hungary; Muhammad Al Farizi, Department of Programming Languages and Compilers, Eötvös Loránd University, Budapest, Hungary; Jakab Nádori, Department of Physics of Complex Systems, Eötvös Loránd University, Budapest, Hungary and Qutility @ Faulhorn Labs, Budapest, Hungary; László Hajas, Department of Biological Physics, Eötvös Loránd University, Budapest, Hungary; Tamás Kozsik, Department of Programming Languages and Compilers, Eötvös Loránd University, Budapest, Hungary; Péter Rakyta, Department of Physics of Complex Systems, Eötvös Loránd University, Budapest, Hungary and Computational Sciences Department, HUN-REN Wigner Research Centre for Physics., Budapest, Hungary, [email protected]. about block implementations and qubit permutations can improve mapping quality on constrained hardware [6]. Earlier block-by-block optimization frameworks such as QGo also demonstrated that partitioning can be used to scale synthesis-based optimization to circuits with tens of qubits by regenerating and recomposing independently optimized subcircuits [7]. For wide circuits, TopAS further demonstrates that partitioned topology-aware synthesis can reduce depth and two-qubit gate count before or alongside mapping on sparse hardware topologies [8]. These developments strengthen the case for high-quality partitioning: if downstream tools operate on blocks, then the procedure that forms those blocks and processes them becomes a decisive part of the overall compiler stack.

Several widely used frameworks already include built-in partitioning routines. Qiskit provides the CollectMulti QBlocks pass, while BQSKit offers multiple strategies such as Quick, Scan, Cluster, and Greedy. In practice, however, these approaches are heuristic and prioritize speed over global optimality. Recent work has therefore sought to improve partition quality without abandoning scalability. Clark et al. introduced Tree-based Directed Acyclic Graph (TDAG) partitioning and subsequently Greedy Topology-Aware Quantum Circuit Partitioning (GTQCP), both of which improve upon earlier heuristic baselines while preserving practical runtimes [9, 10]. Related directions include graph-based acyclic partitioning for simulation [11], Integer Linear programming (ILP) based allocation of subcircuits across GPUs in Atlas [12], graph partitioning for distributed quantum computation [13], balanced partitioning via a two-level ILP [14], and ILP-driven routing and mapping methods that demonstrate the broader value of exact optimization in quantum circuit routing [15]. Partitioning is also central to approximation-oriented optimization: QuEST use partitioning to make approximate synthesis scalable and to trade fidelity against two-qubit gate count in a controlled way [16]. In more application-specific settings, compiler structure can be specialized even further: Bassman Oftelie et al. give constant-depth constructions for certain dynamic materials simulations, illustrating how domain-specific circuit generation can dramatically reduce depth for targeted Hamiltonian families [17]. Beyond gate count and depth, partition-aware compilation is increasingly being used to optimize other resources as well: circuit resizing in BQSKit leverages synthesis and instantiation to reduce qubit count, while Superstaq highlights how deeper, hardware-tailored optimization across abstraction layers can push more programs into the executable regime on real devices [18, 19]. Taken together, these lines of work reinforce that partitioning is not merely a preprocessing convenience, but a structural decision that shapes the efficiency of synthesis, mapping, transpilation, approximation, and even width reduction throughout the compiler pipeline.

Despite this progress, a practical exact method for globally optimal selection of bounded-size circuit partitions (i.e. partitions containing no more than a given number of qubits) at large scale is still missing. Achieving such an optimum requires two complementary ingredients. First, each candidate partition must be optimized by a reliable and fast decomposition procedure, since the quality and cost of the partition decomposition determine whether the global search can evaluate many partitions in practice. Secondly, the optimized partitions must be assembled by a globally optimal selection strategy rather than by a greedy local rule. The resulting optimality is conditional on the enumerated candidate partitions and their computed costs, while it is not a proof of minimum-CNOT synthesis for the whole circuit.

This paper therefore develops two tightly connected contributions. In the first part, we introduce an operator-Schmidt rank (OSR) based tree-search algorithm for small-partition decomposition. The method uses operator-Schmidt-rank information across subsystem cuts [20, 21] to derive dyadic rank certificates, weighted residual tail scores, and lower bounds on the additional CNOT gates needed to complete a candidate structure. These quantities guide search branch prioritization, allowing the gate structure search to focus on CNOT structures that are most likely to reduce the remaining entanglement obstruction. In this way, the OSR strategy provides the fast and reliable local synthesis engine required for evaluating candidate partitions.

In the second part, we turn to the global partitioning problem. Given the ability to optimize small partitions efficiently, we present a practical and scalable exact algorithm for global partition optimization in quantum circuits. Our method contracts single-qubit sub-chains, enumerates all feasible convex partitions, and selects an optimal cover of the original circuit through an ILP formulation. The resulting approach provides an exact reference for globally optimal bounded-width partition selection over the enumerated candidates and their computed costs, enabling rigorous benchmarking and more principled quantum compiler design. Both the OSR-based synthesis algorithm and the ILP-based global partitioning algorithm are implemented in the open-source SQUANDER package [22].¹ Then, in the third part we summarize the results of our numerical experiments on quantum circuit optimization.

OSR-guided gate synthesis strategy for topology-constrained decomposition

For topology-constrained synthesis, where the two-qubit gate connectivity between the qubits is limited, we use an OSR-guided search over ordered, topology-respecting CNOT gate structures. In the benchmark configuration, a Hilbert–Schmidt cost function [23] is used to optimize the single-qubit parameters of each trial gate structure. Then, operator-Schmidt spectra are evaluated to guide the discrete search over the viable CNOT gate structures decomposing the given quantum circuit. To fix notation used in this work, we recall that OSR is defined with respect to a bipartite partition of the underlying system. Suppose we have an operator

where $\mathcal{H}_A$ and $\mathcal{H}_B$ denote two subsystems. The operator can be expressed in its operator-Schmidt decomposition as

where $X_i$ and $Y_i$ are operators acting on subsystems $\mathcal{H}_A$ and $\mathcal{H}_B$, respectively, and $s_i > 0$ are the operator-Schmidt coefficients. The operator sets $\{X_j\}$ and $\{Y_k\}$ form orthonormal bases within the subspaces. The number of nonzero coefficients $r$ is called the operator-Schmidt rank. It quantifies the degree of coupling between the two subsystems and generalizes the concept of Schmidt rank for quantum states. An operator with OSR equal to one can be written as a simple tensor product

indicating a fully separable operation. Larger operator-Schmidt ranks correspond to increasingly complex and entangling interactions between the subsystems. In practice, the operator-Schmidt rank can be obtained by reshaping the operator tensor into a matrix representation with grouped subsystem indices and performing a singular value decomposition (SVD). The number of nonzero singular values determines the OSR. The operator-Schmidt rank is widely used in quantum information theory, tensor-network methods, matrix product operators, and the complexity analysis of quantum circuits and many-body systems [20, 21, 24, 25, 26]. Recent work develops a determinantal distance geometry for two-qubit synthesis [27]. In this work we develop a generic $N$-qubit approach to guide constructive structure search for quantum gate synthesis.

The relevance of OSR to CNOT counting is well established in the two-qubit and bipartite-unitary literature. A generic two-qubit unitary requires three CNOT gates, and three are also sufficient, giving a tight non-heuristic CNOT benchmark for this smallest nontrivial case [28, 29]. At the same time, all bipartite unitaries with operator-Schmidt rank two are locally equivalent to controlled unitaries, explaining why a single CNOT crossing a bipartition has OSR value of two and why a single cross-cut CNOT can increase OSR across that cut by at most a factor of two [21, 30]. More generally, OSR is submultiplicative under operator composition, so $[\log_2(\operatorname{OSR})]$ gives a natural cut-based lower bound on the number of crossing CNOT gates needed across a partition. This perspective is consistent with standard circuit-synthesis lower-bound arguments [31] and with bipartite-unitary constructions whose entanglement or nonlocal-gate costs scale with Schmidt rank [32].

Let $Q = \{0, \ldots, n - 1\}$ be the qubit set and $E_T$ the available two-qubit couplings. We define a trial gate structure synthesizing a given circuit partition by an ordered CNOT gate structure defined by the successive two-qubit coupling edges

Elements in $P$ specify an ordered structure of CNOT gates forming a parametric circuit when surrounded with single qubit rotation gates. The circuit synthesis is performed via continuous optimization of the single-qubit gate parameters. For the results reported in this work, the continuous optimization stage uses Hilbert–Schmidt cost function. Thus, the method of gate synthesis alternates between a discrete combinatorial stage (the CNOT gate structure) and a continuous parameter tuning process.

For the fitted trial circuit $V_P$ (i.e. approximating the effect of the unitary $U$ with the tiral $V_P$ circuit), the fidelity of the approximation is evaluated by Hilbert–Schmidt cost function

with $n$ being the number of qubits. The cut profiles defined below are evaluated on the residual $V_PU^\dagger$.

Let $C\subset Q$ be a nontrivial bipartition of the qubit register $Q$ (made of the $n$ qubits) and let $\overline{C}=Q\setminus C$, being its complementary. The first step is to permute the rows and columns of the unitary $U$ to separate the partitions $C$ and $\overline{C}$. The permutation according to the subset $C$ is described by the operator $R_C$:

where $(a,a')\in\{0,\ldots,d_C-1\}^2$ index the $C$ subsystem and $(b,b')\in\{0,\ldots,\overline{d}_C-1\}^2$ index the complement. Finally, we compute a standard thin SVD,

with singular values

where $d_C=2^{|C|}$ and $\overline{d}_C=2^{|\overline{C}|}$ are the dimensions of the Hilbert-space associated with the cuts $C$ and $\overline{C}$. (Thin SVD keeps only the useful components from the singular value decomposition of $R_C(U)$) In our implementation in the SQUANDER package these singular values are normalized by the Frobenius norm of the target unitary,

so all OSR-derived quantities are comparable across different cuts.

OSR-Based Tree-Search Strategy with Branch Prioritization

To describe our circuit synthesis strategy, we first introduce the following quantities.

Discrete dyadic rank certificate: After solving the continuous optimization problem of the single-qubit rotation angles across a trial CNOT structure, we examine the resulting residual unitary $V_PU^\dagger$ across all nontrivial qubit-register cuts. Let $\mathcal{C}$ denote the set of nontrivial unordered bipartitions. For each cut $C\in\mathcal{C}$, we compute the normalized singular values $\widehat{\sigma}_j^{(C)}$ using the SVD procedure described in § 2 and define the numerical OSR count as

$r_C^{\mathrm{num}}$ evaluates the number of singular values for cut $C$ that are larger than $\tau$-times the largest singular value, with $0\leq\tau<1$. Based upon this quantity, we introduce the so-called discrete dyadic certificate used in the tree search, which is calculated as

This is the quantity returned as the OSR-based lower bound on the number of crossing CNOT gates required to disentangle the fitted residual across cut $C$ [21, 30].

Weighted Tail Loss: The weighted tail loss provides a secondary score for ranking trial gate structures:

with

The largest tail weights belong to the smallest singular values. The weighted tail score distinguishes trial gate structures with the same OSR lower bound and helps determine which structures the search explores first. It is a heuristic ordering score and does not give the exact number of CNOT gates needed to complete the decomposition. Its role in choosing additional CNOT connections is described below. For a given trial CNOT gate structure $P$ and optimized rotation parameters indexed by $C_0$, we introduce the full cut profile

This profile is what drives the discrete tree-search over the possible gate structures. The Hilbert–Schmidt fit improves a fixed structure, while the all-cut OSR post-evaluation estimates an optimistic lower bound on the additional CNOT gates required to complete it.

Estimation on the number of additional CNOT gates required to finish the synthesis: The cut profile is used to determine a combinatorial lower bound on the crossing interactions needed to synthesize the current fitted residual. For any cut $C\in\mathcal{C}$, let

be the set of two-qubit connection edges crossing $C$. If a future modification of the trial circuit adds $x_e\in\mathbb{Z}_{+,0}$ CNOTs on edge $e\in E_T$, then the induced cut coverage is

Since the dyadic rank certificate gives an optimistic lower bound on the number of CNOTs that must cross each cut, a circuit realizing that fixed residual must satisfy

Thus the lower bound on the required additional CNOT count is obtained from the optimization problem

subject to

This lower-bounding subproblem is solved by an exact combinatorial search over edge multiplicities $x_e$. It relaxes ordering and realizability constraints for the measured residual. Jointly refitting a child can change that residual, so this value is structural guidance rather than an admissible pruning certificate for every refitted descendant. The hard CNOT-budget check uses the actual path length, not an assumed admissible bound for all refitted descendants.

Secondary ordering via the weighted tail loss: The minimum in (15) is typically highly degenerate. To break ties meaningfully, the implementation solves a second lexicographic problem after the minimum CNOT count has been fixed. For a feasible edge-count vector $\mathbf{x}=\{x_{e_1},x_{e_2},\ldots\}$ with $\sum_e x_e=L_{C_0}(P)$, define the surplus on cut $C$ by

Among all minimizers of (15) we then minimize

subject to

This step is where the weighted tail loss $\kappa$ becomes critical. Cuts with the same dyadic bound $b_C$ need to be classified differently: a cut whose spectrum still carries a large weighted tail should influence the search more strongly than one whose post-threshold tail is already nearly extinguished. Equation (18) encodes exactly this preference. The optimization result $x_{C_0}^{\star}(P)$ (for which $S_{C_0}(P)$ is minimal) is then reused to rank topology edges (translated to new CNOT gate candidates) when adding CNOT gates to the trial structure.

Ordering the trial gate structures: Each fit $C_0$ yields a tuple

This tuple records, for one continuous fit, the optimistic residual CNOT bound $L_{C_0}(P)$, the weighted surplus tie-breaker $S_{C_0}(P)$, an optimal edge-count assignment $x_{C_0}^{\star}(P)$ for prioritizing topology edges, and its measured all-cut profile $\Gamma_{C_0}(P)$. (In the procedure we may run the continuous optimization multiple times and store only the best result.) For repeated fits of one structure, the best profile is selected lexicographically:

where

Write $(\bar{L},\bar{S},\bar{\Phi}) = K_{\mathrm{fit}}(P)$. The actual comparison keys between different structures are

Thus both widths use the same fitted-residual and cut-cover framework, but the four-qubit policy places the fitted HS score immediately after the residual CNOT bound. These are ordering rules inside an optimistic forward search with deferred candidates, not a claim of exhaustive A* optimality or backtracking. The external CNOT budget remains distinct from the residual estimate.

Heuristic to extend trial gate structures: After sorting and ordering the already visited gate structures, now we discuss the developed heuristic approach to further evolve the most promising gate structures (i.e. adding new CNOT layers to the gate structure). Once the current best CNOT gate structure $P$ has been identified during the gate synthesis, the search expands it by inserting additional CNOTs into the current ordered CNOT gate structure. The expansion mechanism is guided by the edge-count assignment vector $x^{\star}(P)$ associated with the chosen best gate structure, as the anchor of further extensions.

The fitted cut profile and its edge-cover assignment rank legal extensions. Single-CNOT additions are considered before more structured multi-CNOT insertion classes; constructive pair and motif proposals supplement this ordering. A deferred frontier avoids fitting every possible placement before trying a promising extension. These priorities are heuristic, rather than an exhaustive ordering of every insertion by one edge-demand vector.

Formally, for a chosen CNOT insertion multiplicity $m$, the neighborhood explored is a constrained subset

where the ordinary insertion generator uses the following guiding principles:

G1 Spatial coherence of inserted edges: After the first CNOT insertion, every subsequent inserted CNOT must share at least one qubit with a CNOT already inserted in the same expansion call. In other words, the set of newly inserted CNOTs is required to form a connected pattern in the line graph of the topology. This biases the search toward coherent local entangling motifs instead of disjoint edits.

G2 Repetition cap: Any candidate path containing four consecutive identical (or reverse-direction) CNOTs is discarded immediately, since any two-qubit unitary can be synthesized with at most three CNOT gates [28, 29, 33]. Pruning these candidates early removes a large family of syntactically distinct but practically useless trial gate structures.

G3 Canonical uniqueness filtering: Before evaluation, each candidate is passed through a structural uniqueness test. Ordered CNOT structures that are syntactically different but represent the same effective two-qubit interaction pattern are rejected, and a local visited set suppresses duplicates generated through different insertion orders. This canonicalization is essential for keeping the search tree from filling with isomorphic gate structures.

Algorithm 1: OSR-guided synthesis with certified constructive completion

Input: Target unitary $U$; topology $T = (Q, E_T)$; CNOT budget $L_{\max}$.

Output: A certified topology-respecting decomposition, or failure within the budget.

1. $C \leftarrow$ all nontrivial qubit cuts

2. Try the complete trial gate structures described above, using at most $L_{\max}$ CNOTs

3. if a completion is certified then

   4. return the completion, after testing CNOT removals and refitting when applicable

4. $P \leftarrow\varnothing$; fit its parameters and measure its all-cut residual profile

5. if $P$ passes full-unitary certification then

   7. return $P$

6. while an untried legal forward extension within $L_{\max}$ remains do

   9. Generate or resume the next deferred structured insertion class anchored at $P$

   10. Fit the next candidate with bounded HS optimization and evaluate its all-cut profile

   11. if the candidate passes full-unitary certification then

       12. return the candidate, after testing CNOT removals and refitting when applicable

   12. Rank the candidate using $K_n$ and the structured class priorities

   13. if the forward-progress conditions are met then

       15. Commit the candidate as the new current path $P$

   14. Otherwise continue the deferred class or the next insertion multiplicity

7. return failure

These guiding principles do not affect the validity of the lower bound in (8); they only restrict which children are materialized. Hence the combinatorial explosion of naive insertion search is kept under control.

Summary of the OSR based search procedure

The resulting control flow is summarized in Algorithm 1. A zero cut-cover bound alone does not prove that the decomposition is valid. A candidate is accepted only if a fixed-structure Hilbert–Schmidt fit reaches the synthesis tolerance. Otherwise, the search continues until the CNOT budget is exhausted. For both three- and four-qubit partitions, the search uses post-fit OSR bounds, $\kappa$-weighted ordering, and structured child generation, with the width-dependent keys above and the same strict certification requirement. It does not guarantee a minimum-CNOT solution.

Complexity considerations. The dominant cost of one node evaluation is the repeated BFGS refinement together with the SVDs needed to evaluate the induced all-cut profile. By contrast, the combinatorial solver for (15) is inexpensive because the topology size is fixed and small relative to the ambient unitary dimension. The search is therefore designed to spend substantial floating-point effort only on nodes that survive the strong discrete guidance. This is precisely why the definition of $\kappa$ in (9) and the $\kappa$-weighted surplus objective (18) are not cosmetic details: they are what turn a coarse dyadic OSR certificate into a practically discriminative best-first ordering.

From OSR-Guided Local Synthesis to Global Circuit Optimization via Partitioning

The OSR-guided search described above provides the local synthesis engine used to evaluate small subcircuits. Its purpose is to decide, for a fixed set of qubits and a fixed hardware topology, which CNOT structures are promising enough to be refined by continuous single-qubit gate parameter optimization. The global problem considered in the remainder of the paper is complementary: instead of asking how to decompose one small unitary, we ask how a large circuit DAG should be divided into subcircuits so that each subcircuit can be optimized locally while the collection of optimized subcircuits will lead to the most compressed quantum circuit. This section introduces the graph-theoretic and optimization concepts that connect these two levels.

To formalize the global step, we model the input circuit as a directed acyclic graph (DAG)[34, 35], whose vertices are gates and whose edges encode gate dependencies. A candidate partition is useful only if it can be treated as a self-contained subcircuit to be passed to the local synthesis procedure. This requirement is captured by closed convexity in the DAG: whenever two gates belong to the same partition, every directed path between them must remain inside the partition. Thus, in our formulation, valid circuit partitions correspond to closed convex sets of the DAG. Open convex sets can also be enumerated efficiently [36], but they are not appropriate here because they may split a partition into disconnected fragments that no longer define a single coherent local synthesis task.

The OSR-based decomposition routine is intended for small partitions, so every candidate partition is additionally restricted by a maximum number of qubits. This bound is both algorithmic and physical: it keeps the OSR-guided synthesis problem small enough to solve reliably, and it reflects hardware and simulation constraints on the number of qubits that should be optimized as one block. In practice, this limit is usually in the range of 3–5 qubits. The special case of two-qubit blocks is comparatively simple, as any two-qubit unitary can be decomposed at most 3 CNOT gates[37].

Efficient enumeration and validation of the partitions relies on standard graph operations. The transitive closure of a DAG introduces an edge $(u,v)$ whenever a path $u \to v$ exists in the original graph. This makes convexity and dependency checks easier to express. We compute the closure information using Nuutila’s transitive-closure approach [38]. Its strongly connected component (SCC) subroutine admits linear-time implementations, such as Tarjan’s algorithm [39] and textbook variants [40].

Once all feasible convex partitions of the original circuit have been generated, the remaining task is to select the subset that yields the optimally compressed quantum circuit. We formulate this global optimization step as an Integer Linear Programming (ILP) problem [41]. All candidate subcircuits, including overlapping and non-overlapping ones, are enumerated subject to the maximum qubit budget. Each candidate subcircuit is then optimized using the OSR-based decomposition routine, and the resulting costs are used to determine an optimal exact cover of the original circuit. In other words, to reproduce the original quantum program, we select a subset of optimized subcircuits that minimizes the total number of CNOT gates. The ILP constraints ensure that every gate in the original circuit is assigned to exactly one selected partition, while the objective function encodes the desired global cost, such as the CNOT count of the resulting circuit.

For completeness, additional preprocessing and postprocessing routines are provided in the appendices. Appendix A.2 details the contraction of single-qubit chains, while Appendix A.3 explains their recombination after ILP optimization. In brief, single-qubit chains without parents or children form partitions trivially. Chains with only one neighbor are joined to that neighbor’s partition, whereas chains with both a parent and a child require a choice. In our implementation we consider both of the choices equivalently good.

Identifying convex partitions in the circuit

When exploring feasible partitions in the circuit, it is essential to enforce constraints such as the maximum number of qubits $Q_{\max}$ allowed in a single partition. A purely structural reachability analysis may admit candidate partitions that exceed this qubit budget. To avoid such candidates, we use a procedure that propagates only through subgraphs of the DAG whose cumulative qubit sets remain within the prescribed limit.

Formally, let $G=(V,E)$ denote the gate-dependency DAG, where $V$ is the set of gates in the circuit to be optimized and $E$ is the set of dependency edges between them. Let $g(v)$ and $r(v)$ denote the forward and reverse adjacency sets of a gate $v$, respectively. Each gate $v \in V$ is associated with the set of qubits $Q(v) \subseteq Q$ on which it acts. The procedure explores backward reachability under the constraint

where $u \preceq v$ indicates that $u$ is on a valid backward path from $v$.

Algorithm 2, given in Appendix A.1, implements the outlined reachability procedure, ensuring that only gates belonging to subcircuits whose total qubit footprint does not exceed $Q_{\max}$ are considered reachable. Thus, infeasible sub-circuits are pruned early, substantially reducing the search space compared to unrestricted reachability.

The identified partitions are also filtered according to their convexity. A partition $P \subseteq V$ is convex if, whenever $u,v \in P$ and $u \preceq w \preceq v$, then $w \in P$ as well. Convexity guarantees that partitions correspond to contiguous subgraphs without “holes,” while qubit number-awareness ensures that no partition exceeds the imposed bound $Q_{\max}$. We improve the efficiency of the convex set enumeration algorithm [36] by maintaining the sets of forward-reachable vertices, denoted by $A$, and backward-reachable vertices, denoted by $B$. We also track $Q$, the current set of qubits in the candidate partition. The current partition is then greedily extended by appending gates from the frontier sets $A$ and $B$. The complete algorithm with a pseudocode for this enumeration procedure is given in Algorithm 3 in Appendix § 7.§ 1.

Formulating the optimization problem to find the optimal partitioning

The previous sections described how to generate all feasible subcircuit partitions of a quantum circuit and how the OSR-guided strategy recompiles them. We now formulate an ILP optimization problem that selects a subset of these optimized subcircuits whose recomposition preserves the original quantum program while optimizing a chosen global metric, such as the overall CNOT gate count used in this work. Let $V$ denote the set of gates in the original circuit, and let $\mathcal{P} = \{P_1, P_2, \ldots, P_m\}$ denote the set of all candidate unoptimized partitions. We write $\widetilde{\mathcal{P}}$ for the corresponding set of optimized partitions, where $\widetilde{P}_i \in\widetilde{\mathcal{P}}$ is the resynthesized version of the subcircuit $P_i \in\mathcal{P}$. Each partition $P_i$ contains a subset of the gates in $V$. To reconstruct a circuit equivalent to the original quantum program, the selected optimized partitions must correspond to unoptimized partitions that do not share gates. To achieve this, lets first construct the sets $\mathcal{P}(g)$ for all $g \in V$ describing which partitions $P_i \in\mathcal{P}$ contain the gate $g$. Thus, for every gate $g \in V$, let

be the set of partition indices $j$ for which $g \in P_j$. For each partition $P_j \in\mathcal{P}$ we introduce a binary variable $x_j = 1$ if partition $P_j$ is selected for the circuit reconstruction and 0 otherwise. Then the ILP optimization is formulated as

subjected to

Constraint (27) ensures that each gate is covered by exactly one selected partition in the recombination of the circuit. The objective (26) minimizes the total optimized CNOT count, where $\operatorname{CNOT}(\widetilde{P}_j)$ denotes the number of CNOT gates in the optimized partition $\widetilde{P}_j$. This objective can be replaced by any suitable cost function that reflects the goal of the circuit optimization. For example, one may minimize the count of another hardware-expensive gate or use a cost function that models the cumulative noise of the gates in the reconstructed circuit. For simplicity, in this work we focus on the CNOT gate count.

Enforcing acyclicity among partitions

The procedure described above minimizes the selected cost over the enumerated, resynthesized partitions, but it can also introduce inconsistencies in the ordering of gate operations. If the selected partitions cannot be arranged in a valid gate-execution order, the resulting circuit may implement a different quantum program from the original circuit. Figure 1 shows an example of such ill-conditioned case. The figure shows two partitions, highlighted with black and red colors. Although both partitions are mathematically convex, they induce a cyclic dependency between each other. Specifically, gate $G_3$ in the black partition depends on the execution of gate $G_2$ in the red partition, while gate $G_4$ in the red partition depends on the execution of gate $G_1$ in the black partition. Thus, the red partition depends on the black partition and vice versa, so the two partitions cannot be ordered acyclically. Generally speaking, even if each partition is individually convex and locally optimizable by the OSR-based synthesis procedure, the resulting graph induced by the selected optimized partitions must originate from partitions being in acyclic relation to preserve a valid execution order. Cycle-inducing selections can become more frequent as the maximum qubit limit per partition grows, so the algorithm must detect and eliminate these cases. In our implementation provided within the SQUANDER package, we use cycle-elimination ideas related to chordless-cycle enumeration algorithms such as those of Uno and Satoh [42] and Dias et al. [43], which are also reflected in practical graph libraries such as NetworkX.

This section formalizes the concept of the partition–interaction digraph and presents three complementary strategies to enforce acyclicity on the solution of the ILP problem.

Strategy I: Static cycle-elimination constraints. Let $G=(V,E)$ be again the the original DAG and let $\mathcal{P}=\{S_1,\ldots,S_m\}$ be the set of candidate partitions for the ILP problem. Lets define the partition–interaction directed graph as

where $\{1,\ldots,|\mathcal{P}|\}$ describes the set of the partitions through their indices from $\mathcal{P}$ and $A$ describes the directed arcs between the elements. An arc $(i,j)$ is element of $A$ if and only if there exist edges $(u,v)\in E$ such that

That is, we add an arc whenever the original graph contains a cross edge from the exclusive part of $S_i$ to the exclusive part of $S_j$ (with $S_i$ and $S_j$ being two subcircuits.). This excludes edges attributable to partition overlap, which are already handled by the base ILP through the explicit non-overlap constraint. In the implementation, we further prune $H$ by computing its strongly connected components (SCCs) and retaining only arcs internal to those components, since arcs crossing distinct SCCs cannot participate in any directed cycle. (An SCC is a maximal set of vertices in which every vertex can reach every other vertex via directed paths. Therefore, vertices outside SCCs cannot belong to the same directed cycle.) Additionally, we use the exclusive-part rule (27) above to avoid spurious arcs due to overlaps. We can drop arcs between pairs that are already mutually forbidden by the base ILP (e.g., when $S_i\cap S_j\ne\varnothing$ and $x_i+x_j\le1$ is present).

As before in Sec. 3.2, let $x_i\in\{0,1\}$ denote whether partition $S_i$ is selected to be used in the recombination of the resulting circuit or not. For any directed simple cycle $C$ in the directed graph $H$, the inequality

forbids selecting all vertices of $C$ simultaneously, thereby eliminating that cycle. Here, $C$ is a set of indices whose corresponding partitions form a directed cycle of length $|C|$. However, pre-enumerating all such cycles can scale exponentially in the worst case. Therefore, when computational budget is a concern, one may restrict the enumeration to cycles up to a prescribed length. Important special cases include:

• cycles of length 2: if $(i,j)\in A$ and $(j,i)\in A$, then $x_i+x_j\le1$;

• cycles of length 3: if $(i,j),(j,k),(k,i)\in A$, then $x_i+x_j+x_k\le2$.

When cycle enumeration is limited to a prescribed length, this approach must be combined with Strategy II or III, discussed below, to guarantee global acyclicity.

Strategy II: Introduction of continuous order variables to the partitions. The idea in this strategy is to assign new continuous variables $u_i\in[0,|\mathcal{P}|]$ to each partition and compose such constraints between these variables which cannot be fulfilled for partitions forming a cycle. Such a constraint can be given with indicator constraints

for every arc $(i,j) \in A$. If both $(i,j)$ and $(j,i)$ belong to $A$, forming a cycle of length 2, these constraints cannot be satisfied simultaneously: summing them yields $u_i + u_j \ge u_i + u_j + 2$. The same argument extends to cycles of arbitrary length. This yields a compact, single-shot model with $O(|A|)$ additional constraints. It is attractive when the pruned arc set $A$ is moderate, while for extremely large $A$ the extra constraints may still be heavy.

Strategy III: Lazy cycle cuts (cutting-plane enforcement). In contrast to Strategies I and II, this strategy eliminates cycles only when they are discovered in a currently best solution during optimization. Starting from the base ILP formulation without acyclicity constraints, whenever the solver finds a new best solution $\bar{x}$, we consider the subgraph induced by the selected partitions,

If $H[\bar{X}]$ contains a SCC of size at least 2, we extract a simple directed cycle $C$ from that SCC and add the corresponding cycle-cut constraint (30). We then re-optimize the problem and repeat this procedure until the currently best solution contains no cycle violations. Modern solvers, such as Gurobi, support this approach through a lazy-constraint callback at the MIPSOL event, which allows on-the-fly SCC detection and insertion of (30) before the incumbent is accepted.

For practical considerations, we mention that if $A$ becomes modestly large after pruning, Strategy II is simple and effective. For very large graphs, though, Strategy III generally yields the best time–memory trade-off. Strategy I is useful for adding a small library of short-cycle cuts upfront (e.g., all 2- and 3-long cycles), and can be combined with strategies II or III. All three strategies produce solutions in which the partition–interaction digraph induced by selected partitions is acyclic, thereby satisfying the decomposition requirement.

Experimental Results

We evaluated the proposed entanglement-driven OSR decomposition using its implementation in the SQUANDER package. SQUANDER combines OSR-based partition resynthesis with the ILP based partitioning formulation described above, which selects a globally optimal circuit partitioning with respect to the chosen cost function. In these experiments, the objective is to maximize circuit compression by reducing the number of CNOT gates. To assess the impact of these newly developed techniques, we compare the resulting circuit-optimization workflow with the well-established Berkeley Quantum Synthesis Toolkit (BQSKit) [44].

The end-to-end workflows use different routing methods: the BQSKit reference uses SeqPAM [6], while SQUANDER uses OSR to resynthesize small subcircuits on the allowed qubit connections. SQUANDER records these circuits and their CNOT counts for different assignments of the subcircuits’ input and output qubits, then selects compatible circuits and assignments, adding SWAP gates where needed. Consequently, the end-to-end comparison measures combined workflow outcomes rather than isolating the effect of partitioning or resynthesis. Both workflows target a linear connectivity topology. The proposed workflow is compatible with arbitrary qubit-connectivity topologies.

The circuit optimization workflow consists of three stages. First, the circuit is optimized under the assumption of all-to-all qubit connectivity. This stage is denoted by A2A in the tables 1-10 summarizing our results. In the SQUANDER workflow, this stage uses ILP-based partition selection and OSR resynthesis. Second, the resulting circuit is mapped to the linear target topology using the routing method of its respective workflow. (In this stage the linear topology can be replaced by any meaningful connectivity between the qubits.) This stage is denoted by Routed in the tables. Third, the routed circuit undergoes a final connectivity-aware partition optimization and resynthesis. This stage is denoted by Final. In the SQUANDER workflow, the final stage again uses the ILP and OSR techniques.

We tested circuits from QASMBench [45] and the IBM-EAGLE benchmark set used in the GUOQ evaluation [46]. Before synthesis, we converted each circuit to the ($u3$, CX) basis. The tfim circuit present in the tables is from QFAST/QSearch benchmark tfim-4-60 [2], not a member of the original QASMBench suite. The tables report CNOT counts and stage runtimes for maximum partition sizes of three and four qubits. Routing uses blocks of at most three qubits in both settings. We include only completed and verified results. The availability audit records missing results, failures, and timeouts.

We validate the end-to-end result by numerically checking accepted local rewrites (i.e. partition resynthesis) and checking the ordered sequence of partition covers, basis conversions, and routing mappings. The exported gates and parameters must match this validated sequence. For large circuits, this compositional check avoids simulating the full circuit, which would be otherwise highly demanding.

Across the 35 matched IBM Eagle circuits optimized using three-qubit partitions (Table 1 and Table 2), OSR’s CNOT advantage is clearest before routing and after final optimization. Paired tests confirm lower counts in the A2A and Final stages, while the Routed-stage difference is not significant. This suggests that routing can offset some of the gains from resynthesis, even though OSR often produces fewer routed CNOTs on individual circuits. Runtime results show a similar stage-dependent trade-off: OSR is usually faster in A2A, and typical routing times are comparable, but a few long OSR runs dominate its total routing time. The largest runtime gap appears in Final, where OSR’s total is much higher despite similar per-circuit median times. Overall, OSR generally improves final CNOT counts, but runtime is less predictable and can be dominated by a small number of expensive cases.

Circuit	Qubits	Initial CNOTs	OSR CNOTs A2A	OSR CNOTs Routed	OSR CNOTs Final	BQSKit CNOTs A2A	BQSKit CNOTs Routed	BQSKit CNOTs Final
tof_3	5	18	14	17	17	18	21	19
barenco_tof_3	5	24	18	23	23	22	26	26
mod5_4	5	28	20	27	25	22	30	29
tof_4	7	30	22	30	30	28	34	32
tof_5	9	42	30	42	42	40	49	46
barenco_tof_4	7	48	34	46	46	42	52	48
mod_mult_55	9	48	40	75	70	48	82	79
QFT8	8	56	52	77	72	56	85	77
vbe_adder_3	10	70	46	64	61	47	77	68
barenco_tof_5	9	72	50	68	68	70	83	79
csla_mux_3_original	15	80	71	156	145	71	171	160
rc_adder_6	14	93	71	103	103	81	119	119
gf2^E4_mult	12	99	99	294	225	99	241	228
tof_10	19	102	70	102	102	90	107	105
mod_red_21	11	105	81	161	154	99	208	198
gf2^E5_mult	15	154	154	443	409	154	441	431
csum_mux_9_corrected	30	168	140	432	358	164	392	375
QFTAdd8	16	184	176	424	376	183	477	435
qcla_com_7	24	186	143	326	310	156	334	328
barenco_tof_10	19	192	130	178	178	182	216	187
gf2^E6_mult	18	221	221	743	549	221	665	628
QFT16	16	228	220	440	344	228	449	392
qcla_adder_10	36	233	209	503	439	211	470	445
gf2^E7_mult	21	300	300	1077	780	300	936	875
qcla_mod_7	26	382	350	1166	1054	352	1054	998
gf2^E8_mult	24	405	405	1467	1301	405	1387	1316
adder_8	24	409	298	680	607	377	653	606
gf2^E9_mult	27	494	494	1640	1437	494	1956	1878
gf2^E10_mult	30	609	609	2534	2193	609	2846	2720
QFT32	32	612	596	2000	1667	612	1827	1721
QFTAdd16	32	716	700	2302	1568	716	2102	1897
QFT64	64	1380	1346	6050	4453	1380	7570	7241
gf2^E16_mult	48	1581	1581	8916	7001	1581	6867	6597
mod_adder_1024	28	1720	1236	3000	2659	1611	2446	2229
QFTAdd32	64	1900	1868	9524	7364	1899	8680	8136
Total	–	12989	11894	45130	36230	12668	43153	40748

Circuit	OSR time (min) A2A	OSR time (min) Routing	OSR time (min) Final	BQSKit time (min) A2A	BQSKit time (min) Routing	BQSKit time (min) Final
tof_3	0.05	0.36	0.04	0.84	0.52	0.47
barenco_tof_3	0.05	0.40	0.06	1.08	0.57	0.43
mod5_4	0.11	0.48	0.07	1.11	0.51	0.79
tof_4	0.04	0.43	0.10	1.08	0.59	0.55
tof_5	0.05	0.47	0.12	1.07	0.71	0.61
barenco_tof_4	0.11	0.51	0.16	1.07	0.66	0.69
mod_mult_55	0.14	0.63	0.28	0.80	0.76	1.02
QFT8	0.31	1.17	0.37	0.59	0.89	1.28
vbe_adder_3	0.35	0.55	0.24	0.74	0.37	0.43
barenco_tof_5	0.24	0.60	0.22	1.14	0.99	0.90
csla_mux_3_original	0.25	1.22	1.06	1.10	1.67	1.07
rc_adder_6	0.10	0.79	0.11	0.76	0.97	0.71
gf2^E4_mult	0.04	0.87	1.21	0.87	1.35	1.25
tof_10	0.08	0.75	0.12	1.12	1.07	0.59
mod_red_21	0.11	0.85	0.88	1.49	1.23	1.43
gf2^E5_mult	0.04	1.40	2.19	0.96	1.94	1.32
csum_mux_9_corrected	0.15	1.79	1.85	1.35	2.00	1.90
QFTAdd8	0.73	3.26	1.91	1.19	2.09	2.25
qcla_com_7	0.25	1.70	1.08	1.53	1.65	1.09
barenco_tof_10	0.17	1.15	0.18	1.79	2.12	0.91
gf2^E6_mult	0.05	1.81	5.37	1.11	2.75	2.10
QFT16	0.58	4.16	2.99	0.81	2.18	2.39
qcla_adder_10	0.26	2.91	2.59	0.96	2.33	1.57
gf2^E7_mult	0.06	2.54	11.07	1.31	3.66	2.70
qcla_mod_7	0.44	3.73	7.84	1.27	3.74	3.12
gf2^E8_mult	0.06	3.74	10.56	1.63	4.80	3.16
adder_8	0.70	2.91	3.55	1.70	3.75	2.18
gf2^E9_mult	0.07	4.83	13.19	1.98	5.92	5.94
gf2^E10_mult	0.08	6.48	36.77	2.35	7.31	8.83
QFT32	1.02	10.51	26.56	1.52	5.77	7.91
QFTAdd16	2.11	14.16	55.70	1.67	6.92	9.52
QFT64	3.10	59.87	340.67	2.66	12.76	28.04
gf2^E16_mult	0.17	29.49	650.61	5.99	19.38	19.04
mod_adder_1024	8.48	10.46	48.41	8.51	17.15	6.55
QFTAdd32	4.81	85.66	880.19	5.79	17.53	48.43
Total	25.38	262.65	2108.31	60.95	138.61	171.19

For the matched QASMBenchmarks circuits optimized using three-qubit partitions (Table 3 and Table 4), OSR reduces CNOT counts across A2A, Routed, and Final, with paired differences significant at every stage. This contrasts with IBM Eagle, where the routed-stage difference is not significant, suggesting the benefit of resynthesis survives routing more consistently on this benchmark set. These results describe a strong overall trend, not a per-circuit guarantee, as some circuits tie or favor BQSKit. Runtime tells a more nuanced story: OSR’s median time is slightly lower at each stage, but BQSKit’s cumulative stage time is lower because a small number of OSR runs take much longer. Thus, three-qubit partitions provide a statistically supported CNOT advantage on QASMBenchmarks, while the runtime benefit is typical rather than dependable in aggregate.

Circuit	Qubits	Initial CNOTs	OSR CNOTs			BQSKit CNOTs
			A2A	Routed	Final	A2A	Routed	Final
adder_n4	4	10	10	13	10	10	16	16
bv_n14	14	13	13	24	24	13	27	24
cat_state_n22	22	21	–	–	21	–	–	21
ghz_state_n23	23	22	–	–	22	–	–	22
multiply_n13	13	40	40	82	78	40	80	78
tfim	4	60	–	–	29	–	–	56
bv_n140	140	72	72	282	143	72	348	334
swap_test_n25	25	84	84	109	107	84	106	106
ising_n10	10	90	–	–	50	–	–	76
dnn_n8	8	192	64	109	101	64	134	126
grover_19	19	192	124	190	181	165	204	198
ising_n98	98	194	–	–	194	–	–	194
hhl_n7	7	196	86	163	151	89	197	192
grover_23	23	240	154	238	227	218	262	244
multiplier_n15	15	246	184	428	391	210	450	418
heisenberg-16-20	16	360	–	–	193	–	–	204
grover_33	33	360	229	359	337	322	389	371
dnn_n16	16	384	128	233	224	128	314	276
qft_20	20	410	387	941	832	389	992	908
adder_n64	64	455	287	563	368	343	2400	2366
grover_45	45	504	319	555	507	429	530	510
grover_61	61	696	439	761	697	613	744	705
grover_81	81	936	589	1021	937	824	999	955
quantum_volume_n40_d20_i0	40	1200	1170	9264	8076	1170	11797	11070
Total	–	6977	4379	15335	13900	5183	19989	19470

Circuit	OSR time (min)			BQSKit time (min)
	A2A	Routing	Final	A2A	Routing	Final
adder_n4	0.02	0.34	0.03	0.14	0.14	0.39
bv_n14	0.00	0.28	0.00	0.12	0.22	0.21
cat_state_n22	–	–	0.00	–	–	0.11
ghz_state_n23	–	–	0.00	–	–	0.12
multiply_n13	0.04	0.57	0.43	0.81	0.70	1.10
tfim	–	–	3.84	–	–	0.57
bv_n140	0.01	10.50	1.88	0.18	0.72	0.71
swap_test_n25	0.10	1.73	0.26	1.21	4.05	0.95
ising_n10	–	–	1.03	–	–	0.39
dnn_n8	5.05	3.60	0.85	0.87	3.41	1.16
grover_19	0.36	1.47	0.89	2.01	2.25	1.11
ising_n98	–	–	0.17	–	–	0.29
hhl_n7	1.53	1.14	1.12	1.19	0.94	0.75
grover_23	0.46	1.78	0.85	1.90	2.39	1.23
multiplier_n15	0.34	1.70	1.69	1.78	2.13	2.02
heisenberg-16-20	–	–	1.49	–	–	1.17
grover_33	0.80	2.78	1.37	2.79	3.94	0.81
dnn_n16	6.92	5.23	0.61	0.93	5.06	6.61
qft_20	1.58	8.40	6.64	1.15	3.37	3.75
adder_n64	1.75	8.01	4.01	1.58	3.58	3.48
grover_45	1.41	4.95	2.47	4.02	4.39	1.44
grover_61	2.56	10.49	3.87	5.45	6.00	1.86
grover_81	4.57	25.31	6.39	7.05	7.81	2.11
quantum_volume_n40_d20_i0	70.15	148.80	602.62	2.38	92.26	50.72
Total	97.64	237.06	642.50	35.57	143.34	83.05

These results motivate our next experiment with four-qubit partitions. Larger blocks let resynthesis consider more gates together and may therefore capture additional opportunities to reduce CNOT counts, at the cost of increased synthesis time. The following results evaluate this expected compression–runtime trade-off.

On the 20 IBM Eagle circuits with paired four-qubit results (Table 5 and Table 6), OSR achieves significantly lower CNOT counts than BQSKit at every stage. It reduces the count in most circuits, and the advantage remains evident after routing and final optimization; this contrasts with the three-qubit comparison, where the routed-stage difference was not significant. Comparing OSR on the same circuits at the two partition sizes, four-qubit partitions modestly reduce aggregate CNOT counts across all three stages, although individual circuits do not uniformly improve. This additional compression comes at a substantial runtime cost relative to three-qubit OSR. Against BQSKit, however, four-qubit OSR is much faster overall in the A2A and Final stages, while routing remains slower and OSR is faster in only a small number of routing cases. These results show that larger partitions strengthen the CNOT outcome and can reduce total optimization time relative to BQSKit in two stages, but they do not improve every circuit or every stage and require more OSR computation than the three-qubit setting.

Circuit	Qubits	Initial CNOTs	OSR CNOTs A2A	OSR CNOTs Routed	OSR CNOTs Final	BQSKit CNOTs A2A	BQSKit CNOTs Routed	BQSKit CNOTs Final
tof_3	5	18	14	17	17	18	19	19
barenco_tof_3	5	24	18	23	23	24	27	27
mod5_4	5	28	16	20	18	12	23	19
tof_4	7	30	22	30	30	30	36	34
tof_5	9	42	30	42	42	41	53	48
barenco_tof_4	7	48	34	46	46	44	52	50
mod_mult_55	9	48	34	92	74	40	95	68
vbe_adder_3	10	70	38	62	52	38	75	57
barenco_tof_5	9	72	50	68	68	65	97	75
csla_mux_3_original	15	80	68	184	140	70	188	160
rc_adder_6	14	93	71	103	97	79	117	96
gf2^E4_mult	12	99	91	248	215	99	296	260
tof_10	19	102	70	102	102	96	123	117
gf2^E5_mult	15	154	149	479	416	154	583	541
csum_mux_9_corrected	30	168	126	420	321	132	446	417
qcla_com_7	24	186	140	317	280	155	415	347
barenco_tof_10	19	192	130	178	178	186	263	244
gf2^E6_mult	18	221	203	735	634	221	733	656
qcla_adder_10	36	233	200	531	429	205	470	432
adder_8	24	409	243	588	497	251	650	578
Total	–	2317	1747	4285	3679	1960	4761	4245

Circuit	OSR time (min)			BQSKit time (min)
	A2A	Routing	Final	A2A	Routing	Final
tof_3	0.24	0.64	0.38	17.67	0.38	32.95
barenco_tof_3	0.26	0.76	0.41	28.08	0.50	5.94
mod5_4	0.79	0.83	0.27	290.28	0.22	25.15
tof_4	0.39	0.75	0.44	31.02	1.06	31.25
tof_5	0.51	0.78	0.64	110.37	0.71	14.89
barenco_tof_4	0.67	1.05	0.65	22.92	0.68	8.37
mod_mult_55	1.98	1.32	2.22	866.15	0.52	120.32
vbe_adder_3	1.01	1.04	1.25	387.52	0.43	80.95
barenco_tof_5	0.88	1.23	0.93	71.18	0.80	79.25
csla_mux_3_original	4.23	3.00	9.01	69.07	1.55	93.58
rc_adder_6	0.72	1.64	1.02	63.24	0.83	36.32
gf2^E4_mult	4.26	2.67	8.71	35.86	1.23	190.22
tof_10	0.47	1.15	0.65	186.80	1.20	35.41
gf2^E5_mult	3.82	3.11	15.07	160.07	1.72	484.14
csum_mux_9_corrected	1.49	3.31	8.99	423.66	1.37	373.43
qcla_com_7	2.98	3.53	9.77	356.93	1.52	208.98
barenco_tof_10	0.81	1.95	0.99	39.69	1.98	49.16
gf2^E6_mult	4.97	4.89	17.77	40.22	2.75	470.18
qcla_adder_10	4.31	6.75	14.21	220.84	2.20	380.15
adder_8	9.66	9.95	16.59	353.28	2.48	181.86
Total	44.44	50.36	109.96	3774.84	24.12	2902.52

Considering all 35 IBM Eagle circuits with OSR results at both partition sizes gives a more qualified picture than the 20-circuit paired comparison above. In this broader OSR-only comparison, four-qubit partitions reduce the aggregate A2A count (11,339 versus 11,894 for three-qubit partitions), but the routed count is higher (47,461 versus 45,130), and the final totals are virtually identical (36,200 versus 36,230). Thus, the A2A savings do not carry through routing in this cohort, while post-routing optimization leaves the final aggregate essentially unchanged. This does not contradict the modest reductions across all stages in the 20 paired circuits: the broader totals also include 15 circuits for which BQSKit did not complete the four-qubit optimization within the 24-hour limit (Table 7), so they describe the effect of partition size on OSR rather than a 35-circuit comparison with BQSKit. Together, the two views suggest that the benefit of larger partitions depends on the circuit cohort and compilation stage, and should be weighed against their substantially higher OSR runtime.

Circuit	Qubits	Initial CNOTs	A2A CNOTs	A2A Time (min)	Routed CNOTs	Routed Time (min)	Final CNOTs	Final Time (min)
gf2^E9_mult	27	494	468	6.19	2117	12.58	1797	56.99
QFT8	8	56	51	15.52	85	2.37	73	2.22
mod_red_21	11	105	78	2.08	158	2.31	148	4.22
QFTAdd8	16	184	173	39.50	551	8.10	371	18.34
QFT16	16	228	220	26.85	416	6.53	343	20.80
gf2^E7_mult	21	300	279	7.25	1076	8.34	918	26.24
qcla_mod_7	26	382	345	7.54	1154	9.20	985	34.71
gf2^E8_mult	24	405	381	3.74	1505	6.93	1281	35.59
gf2^E10_mult	30	609	577	7.80	2926	72.29	2142	103.26
QFT32	32	612	596	27.39	1945	16.99	1554	103.87
QFTAdd16	32	716	673	129.87	2407	200.01	1633	107.15
QFT64	64	1380	1348	29.82	5974	59.85	4183	483.09
gf2^E16_mult	48	1581	1492	14.41	9718	26.40	7427	593.42
mod_adder_1024	28	1720	1124	22.93	3335	9.38	2131	118.91
QFTAdd32	64	1900	1787	143.74	9809	75.77	7535	717.71
Total	–	10672	9592	484.63	43176	517.07	32521	2426.53

For the four-qubit QASMBenchmarks (Table 8 and Table 9), OSR’s CNOT advantage is significant at all three stages, with the clearest per-circuit gains after routing: it uses fewer CNOTs in 11 of 12 Routed comparisons, with a median reduction of 51. The A2A reductions are smaller (7 wins and 5 ties; median reduction 3.5), while OSR also has fewer CNOTs in 12 of 18 Final comparisons, with ties in the other six (median reduction 19.5). The A2A and Routed comparisons each include 12 circuit pairs, whereas Final includes 18, so their totals describe different paired samples and should be interpreted stage by stage. Runtime shows a distinct trade-off. OSR is faster in every paired A2A and Final run, its median times are 1.58 versus 307.52 minutes and 2.80 versus 70.69 minutes, respectively, and the summed times favor OSR in both stages as well. Routing reverses this pattern: OSR is faster in only one of 12 pairs, with a higher median time (3.53 versus 1.70 minutes) and higher summed time (73.90 versus 26.74 minutes). Overall, four-qubit OSR provides a consistent CNOT benefit on these paired benchmarks and substantial A2A and Final runtime savings relative to BQSKit, but the routing stage remains slower. The runtime comparisons are descriptive, while statistical tests apply to CNOT counts.

Circuit	Qubits	Initial CNOTs	OSR CNOTs A2A	OSR CNOTs Routed	OSR CNOTs Final	BQSKit CNOTs A2A	BQSKit CNOTs Routed	BQSKit CNOTs Final
adder_n4	4	10	7	9	9	7	14	10
bv_n14	14	13	13	24	24	13	25	24
cat_state_n22	22	21	–	–	21	–	–	21
ghz_state_n23	23	22	–	–	22	–	–	22
multiply_n13	13	40	40	82	72	40	146	121
tfim	4	60	–	–	12	–	–	12
bv_n140	140	72	72	282	143	72	345	334
swap_test_n25	25	84	84	109	107	84	106	106
ising_n10	10	90	–	–	44	–	–	58
grover_19	19	192	124	190	181	177	224	201
ising_n98	98	194	–	–	194	–	–	194
hhl_n7	7	196	84	158	149	87	201	179
grover_23	23	240	154	238	227	218	286	271
multiplier_n15	15	246	138	358	269	142	503	396
heisenberg-16-20	16	360	–	–	138	–	–	157
grover_33	33	360	229	359	337	336	419	390
grover_45	45	504	319	555	506	476	789	745
grover_61	61	696	439	761	696	647	815	768
Total	–	3400	1703	3125	3151	2299	3873	4009

Circuit	OSR time (min)			BQSKit time (min)
	A2A	Routing	Final	A2A	Routing	Final
adder_n4	0.12	0.35	0.09	63.37	0.23	49.69
bv_n14	0.01	0.30	0.09	0.22	0.19	1.35
cat_state_n22	–	–	0.00	–	–	0.22
ghz_state_n23	–	–	0.00	–	–	0.26
multiply_n13	1.12	0.82	2.23	39.11	0.45	69.80
tfim	–	–	5.29	–	–	366.97
bv_n140	0.02	10.58	2.05	0.36	0.72	21.10
swap_test_n25	1.24	2.18	0.63	17.38	4.15	15.36
ising_n10	–	–	1.80	–	–	66.07
grover_19	1.52	2.58	3.37	320.21	2.17	89.68
ising_n98	–	–	1.72	–	–	4.01
hhl_n7	6.52	4.03	5.14	851.19	0.94	178.91
grover_23	1.64	3.14	3.70	675.88	2.35	111.43
multiplier_n15	3.78	3.91	9.03	626.61	1.23	291.27
heisenberg-16-20	–	–	4.41	–	–	71.58
grover_33	2.01	4.59	4.79	294.82	3.56	91.16
grover_45	2.69	7.32	5.19	359.53	4.41	199.25
grover_61	3.99	34.10	6.69	570.96	6.34	113.37
Total	24.66	73.90	56.20	3819.65	26.74	1741.47

Comparing OSR across partition sizes on the QASMBenchmarks with results at both partition sizes (Table 3, Table 8, and Table 10) shows a mixed, modest aggregate effect. For stage A2A the three- and four-qubit partition totals are 4,379 and 4,230 CNT gates. For the stage Routed the same quantities are 15,335 and 15,573 CNOTs gates, across 24 circuits. For stage Final, the totals are 13,900 and 13,531 CNOT gates across the same circuits. Thus, four-qubit partitions slightly lower the stages A2A and Final totals but slightly increase the Routed total, rather than delivering a consistent reduction at every stage. These aggregates do not imply that every circuit benefits. The four-qubit totals include OSR-only results for six circuits whose BQSKit optimization did not complete within the 24-hour limit, so this is a comparison of OSR partition sizes, not a fully paired OSR–BQSKit comparison.

Circuit	Qubits	Initial CNOTs	A2A CNOTs	A2A Time (min)	Routed CNOTs	Routed Time (min)	Final CNOTs	Final Time (min)
qft_20	20	410	319	104.90	1198	15.15	873	47.69
dnn_n8	8	192	61	12.59	106	6.67	97	4.88
dnn_n16	16	384	122	23.07	227	16.16	207	10.84
grover_81	81	936	589	6.28	1021	49.96	936	9.21
quantum_volume n40_d20_i0	40	1200	1170	233.99	9264	148.31	7914	509.09
adder_n64	64	455	266	2.83	632	7.08	353	5.99
Total	—	3577	2527	383.67	12448	243.34	10380	587.70

Across the completed IBM Eagle and QASMBenchmarks results (Table 1, Table 3, Table 5, Table 7, Table 8, and Table 10), A2A resynthesis reduces CNOT counts relative to the initial circuits for both partition sizes. For the 53 circuits with A2A, Routed, and Final CNOT counts, the initial total is 19,219 CNOTs. For stage A2A the total is 16,273 CNOTs with three-qubit partitions and 15,569 with four-qubit partitions, reductions of 15.3% and 19.0%, respectively, compared to the intial values. Mapping to the target topology then increases the counts substantially. Final optimization removes some of this routing overhead: on the same 53 circuits, it reduces Routed totals from 60,465 CNOTs to 49,621 CNOTs for three-qubit partitions (17.9%), and from 63,034 to 49,300 CNOTs for four-qubit partitions (21.8%). Although four-qubit partitions yield a slightly greater reduction from Routed to Final, the Final totals for both settings remain above the initial count due to the topology constraint.

Routing can substantially change CNOT counts, making the contribution of partition resynthesis difficult to distinguish in an end-to-end comparison. We therefore compare OSR and BQSKit one-to-one on the same partition unitaries, holding each target fixed. This isolates local synthesis quality and efficiency from differences in partition selection and routing.

To isolate the efficiency of local synthesis, Table 11 compares matched three- and four-qubit targets from frozen benchmark-derived and random samples. The complete frozen cohort was rerun on 22 October 2026 using the current native build. Both methods receive the same unitary, coupling graph, unitary decomposition-infidelity threshold of $10^{-10}$, and a 30-second process watchdog, including startup, and a 4-GiB memory limit per solve. Each solve is pinned to one CPU, and the local OSR benchmark uses double precision. The table reports solver-only median times on jointly verified targets. Exported circuits are checked independently against the target and topology. Quality comparisons include only jointly verified pairs, while completion rates are reported separately. The sample excludes compressed source archives larger than 8 MiB. This frozen corpus is a calibration benchmark rather than an independent held-out evaluation.

Context	Targets	Paired	OSR valid	BQSKit valid	OSR fail and BQSKit valid	OSR W/T/L	$\Delta$CX (95% CI)	Paired time OSR/BQSKit (s)
3q/a2a	147	147	147	147	0	87/60/0	−1.24 [−1.46, −1.03]	0.50/3.16
3q/random_a2a	32	32	32	32	0	26/6/0	−1.94 [−2.50, −1.41]	3.17/4.91
3q/random_path	32	32	32	32	0	28/4/0	−2.53 [−3.19, −1.91]	0.33/2.66
3q/routing_catalog	83	83	83	83	0	65/18/0	−1.33 [−1.52, −1.10]	0.24/2.25
3q/topology	143	143	143	143	0	99/44/0	−1.29 [−1.57, −1.04]	0.02/2.06
4q/a2a	81	32	80	32	0	25/7/0	−1.75 [−2.43, −1.21]	1.02/10.04
4q/random_a2a	32	15	21	15	0	14/1/0	−2.07 [−3.13, −1.20]	0.03/4.08
4q/random_cycle	32	16	25	16	0	15/1/0	−2.06 [−3.25, −1.19]	0.03/4.07
4q/random_path	32	21	30	21	0	21/0/0	−2.10 [−2.62, −1.57]	0.03/4.54
4q/random_star	32	20	31	20	0	19/1/0	−2.50 [−3.60, −1.60]	0.03/4.70
4q/topology	126	76	117	76	0	67/9/0	−3.36 [−3.88, −2.80]	0.05/11.34

Across every listed context, the mean CNOT difference favors OSR: each reported 95% confidence interval for $\Delta\mathrm{CX}$ lies below zero, and OSR has no losses among jointly verified pairs, though some are ties. This advantage appears for both all-to-all and topology-constrained targets, and is largest in the four-qubit topology context ($\Delta\mathrm{CX} = -3.36$). OSR also has a lower reported median solve time in every context. These quality comparisons are paired: three-qubit results are complete for both methods, whereas the four-qubit comparisons cover smaller jointly verified subsets. Completion rates should therefore be considered alongside paired quality.

The source code and benchmark reproduction tools are available in the SQUANDER repository [22]. The end-to-end benchmark archive contains the input and optimized OpenQASM circuits, per-circuit configurations and source fingerprints, and stage-wise CNOT counts and runtimes for OSR and BQSKit at both partition sizes. Recorded failures and timeouts are retained alongside completed results. Compressed replay audits record the local rewrites and circuit-composition steps leading to each completed output.²

Conclusion

In this work we introduced two complementary methodological contributions for quantum-circuit optimization: a globally optimal ILP-based partitioning algorithm and an entanglement-driven OSR approach for local block resynthesis. Together, they connect global circuit-structure optimization with topology-aware synthesis of the selected subcircuits.

The partitioning method enumerates admissible closed convex subcircuits, assigns their computed resynthesis costs, and selects an acyclic exact cover by ILP. Single-qubit-chain contraction and qubit-number-aware reachability reduce candidate-generation cost. Cycle-elimination constraints exclude covers that cannot be scheduled. Global optimality here means optimal partition selection over the enumerated feasible candidates and their computed costs, not a proof that the final circuit has the minimum possible CNOT count.

The OSR contribution uses operator-Schmidt spectra as constructive guidance for exploring CNOT structures, not merely as a posteriori descriptors. After Hilbert–Schmidt fitting of a candidate structure, all-cut dyadic rank bounds and $\kappa$-weighted residual scores prioritize topology-respecting extensions. A zero residual bound still requires a tighter fixed-structure synthesis check. This separation of fitting, structural guidance, and certification is the method evaluated here.

The stage-wise end-to-end tables show the outcomes of the complete SQUANDER and BQSKit workflows, including their different routing methods. The matched local-synthesis study provides the cleaner OSR comparison: across 772 fixed unitary decomposition targets, OSR verifies 741 outputs versus 617 for BQSKit, with 466 CNOT-count wins, 151 ties, and no losses on the 617 jointly verified pairs. Four-qubit completion rates and solver timeouts must be considered alongside paired CNOT quality, rather than counted as quality wins or losses.

The end-to-end circuit optimization CNOT results are stage- and benchmark-dependent. Across 53 circuits with counts for all OSR stages, A2A resynthesis reduces the initial CNOT total by 15.3% with three-qubit partitions and 19.0% with four-qubit partitions. Mapping to the target topology raises the counts substantially. Final optimization reduces the routed totals by 17.9% and 21.8%, respectively, but both final totals remain above the initial count, due to the topology constraint. Four-qubit partitions yield a slightly lower aggregate final count than three-qubit partitions (49,300 versus 49,621 CNOTs), but routed totals are higher. Paired comparisons with BQSKit also vary across benchmark sets and stages. Thus, gains from local resynthesis must be assessed together with partition selection and topology mapping.

Larger blocks expose additional synthesis opportunities, but the end-to-end benefit depends on partition selection and routing as well as local synthesis. Future work will focus on scaling topology-aware routing without losing the gains measured in the matched local study.

Acknowledgments

This research was supported by the Ministry of Culture and Innovation and the National Research, Development and Innovation Office through the Quantum Information National Laboratory of Hungary (Grant No. 2022-2.1.1-NL-2022-00004), financed by the National Research, Development and Innovation Fund, and by the Hungarian Scientific Research Fund (OTKA) under Grants No. K134437. We also acknowledge support received through the EUREKA project AI4QT—Artificial Intelligence for Quantum Technologies (Grant No. 2020-1.2.3-EUREKA-2022-00029). We further acknowledge support from the Horizon Europe programme HORIZON-CL4-2022-QUANTUM-01-SGA through the OpenSuperQPlus100 project (Grant No. 101113946). We acknowledge the computational resources provided by the Wigner Scientific Computational Laboratory (WSCLAB), formerly the Wigner GPU Laboratory.

AI assistance disclosure

OpenAI GPT-5.5/5.6/6.0/6.1 Sol models, used through the Codex harness in medium and extra-high reasoning modes, assisted with method development, implementation, computational experiments, literature and citation checks, and manuscript preparation. The authors remain responsible for all scientific claims, computations, references, and text.

Supplementary Algorithms and Results

Qubit Number-Aware Reachability and Convex Partition Enumeration

This appendix gives the pseudocode for the qubit number-aware reachability and convex partition enumeration routines used in § 3.2. The main text describes the role of these routines in pruning the partition search space; here we provide the implementation-level details. Algorithm 2 restricts reachability to subgraphs whose cumulative qubit footprint remains within the budget $Q_{\max}$. Algorithm 3 then uses this restricted reachability inside a depth-first enumeration of convex, qubit-feasible candidate partitions.

Algorithm 2: Qubit Number-Aware Reachability

Input:

$X$ &nbsp;&nbsp; initial set of gates,

$g, r_g$ &nbsp;&nbsp; forward and reverse adjacency of circuit DAG,

$R$ &nbsp;&nbsp; set of admissible gates,

$Q$ &nbsp;&nbsp; mapping gate $\mapsto$ qubits,

$Q_{\max}$ &nbsp;&nbsp; maximum allowed qubits per partition.

Output: Set of gates reachable without exceeding qubit bound.

1. Initialize level $\leftarrow X$, visited $\leftarrow\varnothing$, nextlevel $\leftarrow\varnothing$, and qubit-sets $Q_s$;

2. while level $\ne\varnothing$ do

3. &nbsp;&nbsp;&nbsp;&nbsp;foreach $v \in$ level do

4. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Let $R_v \leftarrow r_g(v) \cap R$; /* backward restriction check */

5. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if $R_v \subseteq$ visited then

6. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if $v \in X$ then

7. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$Q_s[v] \leftarrow Q$;

8. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else

9. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$Q_s[v] \leftarrow Q(v) \cup\bigcup_{u \in R_v} Q_s[u]$;

10. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if $\lvert Q_s[v]\rvert\le Q_{\max}$ then

11. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;visited $\leftarrow$ visited $\cup\{v\}$;

12. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;nextlevel $\leftarrow$ nextlevel $\cup(g(v) \cap R)$;

13. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else

14. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;delete $Q_s[v]$;

15. Swap(level, nextlevel); clear(nextlevel);

16. return set of vertices with defined $Q_s$;

Algorithm 3: Qubit Number-Aware Convex Partition Enumeration

Input: $G = (V,E)$ circuit DAG, with topological order $\pi$, $g, r_g$ forward and reverse adjacency, reach, revreach precomputed closures, $Q(v)$ qubit set of each gate, $Q_{\max}$ maximum qubits per partition.

Output: Set $\mathcal{P}$ of all convex qubit-feasible partitions.

1. $\mathcal{P} \gets\emptyset$;

2. foreach vertex $t$ in topological order do

3. $X \gets\{t\}$, $Y \gets\{v : \pi(v) > \pi(t)\}$, $Q \gets Q(t)$;

4. $A \gets\operatorname{reach}[t] \cap Y$, $B \gets\operatorname{revreach}[t] \cap Y$;

5. prune $Y,A$ using Alg. 2 with $(X,g,r_g,A,Q)$;

6. $\operatorname{stack} \gets\{(X,Y,A,B,Q)\}$;

7. while stack not empty do

8. Pop $(X,Y,A,B,Q)$;

9. if $A \ne\emptyset$ then

10. select $v \in A$ and set $R \gets(A \cap\operatorname{revreach}[v]) \cup\{v\}$

11. else if $B \ne\emptyset$ then

12. select $v \in B$ and set $R \gets(B \cap\operatorname{reach}[v]) \cup\{v\}$

13. else

14. $\mathcal{P} \gets\mathcal{P} \cup\{X\}$; continue

15. push $(X,Y \setminus\{v\},A,B,Q)$ to stack;

16. $Y' \gets Y \setminus R$, $X' \gets X \cup R$, $Q' \gets Q \cup\bigcup_{u\in R} Q(u)$;

17. if $\lvert Q'\rvert\le Q_{\max}$ then

18. $A' \gets(A \setminus R) \cup\bigcup_{u\in R}(\operatorname{reach}[u] \cap Y')$;

19. $B' \gets(B \setminus R) \cup\bigcup_{u\in R}(\operatorname{revreach}[u] \cap Y')$;

20. prune $Y',A'$ with Alg. 2 $(X',g,r_g,A',Q')$;

21. prune $Y',B'$ with Alg. 2 $(X',r_g,g,B',Q')$;

22. push $(X',Y',A',B',Q')$ to stack;

23. return $\mathcal{P}$;

Preprocessing. The forward and backward reachability closures for sets $A$ and $B$ are computed using Nuutila’s transitive-closure algorithm [38], applied to the graph and its reverse:

These closures are then indexed by a topological order $\pi: V \to\{1,\ldots,n\}$ of the DAG. For each topologically earliest seed gate $t \in V$, the algorithm initiates a convex set $X = \{t\}$ with remaining candidate vertices $Y = \{v : \pi(v) > \pi(t)\}$ and qubit footprint $Q(t)$. The two frontier sets $A,B \subseteq Y$ are always maintained relative to the current partition $X$. The search proceeds in a depth-first manner with a stack of states. At each step, one candidate vertex $v \in A \cup B$ is selected, and a region $R$ (all vertices forced in by convexity) is added to the current partition $X$. If the enlarged partition’s qubit set remains within $Q_{\max}$, the frontier sets are updated and pruned by the qubit number-aware BFS reachability routine (Alg. 2). Otherwise, the branch is discarded. The search proceeds in a depth-first manner (i.e. explores one path as deeply as possible before backtracking). Whenever both frontier sets $A,B$ are exhausted, the current convex set $X$ is finalized as a valid partition and recorded. The process backtracks until all convex partitions rooted at $t$ have been enumerated.

Using the outlined approach, each partition is discovered once, and each recursive expansion checks only admissible $Q_{\max}$-bounded frontiers. The worst-case complexity is exponential in $\lvert V\rvert$ (since the number of convex partitions can be exponential), but per-step overhead is polynomial, with $O(|E|)$ for reachability updates and $O(Q_{\max})$ for qubit-set unions. In practice, the qubit bound $Q_{\max}$ is small, so the algorithm scales to circuits with hundreds or thousands of gates.

Algorithm for Contracting Single-Qubit Chains

In this appendix, we describe the procedure used to contract single-qubit chains within a quantum circuit. The algorithm operates on a directed acyclic graph (DAG) representation of the circuit, where vertices correspond to gates, and edges represent data dependencies. For each qubit, consecutive single-qubit gates are merged into chains to reduce the effective graph size while preserving circuit semantics.

Algorithm 4: Contracting Single-Qubit Chains

Input:

$G$ forward adjacency map of the DAG (successors of each gate),

$G^{-1}$ reverse adjacency map of the DAG (predecessors of each gate),

$Q(g)$ mapping from each gate $g$ to the set of qubits it acts on,

$\mathcal{T}$ a valid topological ordering of all gates.

Output:

$G'$ contracted forward adjacency map,

$G'^{-1}$ contracted reverse adjacency map,

$\mathcal{T}'$ updated topological ordering excluding contracted gates,

$C$ dictionary mapping each representative gate to its contracted single-qubit chain.

1. $S \leftarrow\{g \in V(G): |Q(g)| = 1\}$; /* Set of single-qubit gates */

2. $C \leftarrow\varnothing$; /* Initialize contracted chains */

3. foreach $g \in\mathcal{T}$ do

4. &nbsp;&nbsp;if $g \in S$ then

5. &nbsp;&nbsp;&nbsp;&nbsp;if $G^{-1}(g) \ne\varnothing$ then

6. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;let $p \leftarrow$ an arbitrary predecessor of $g$;

7. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$C[g] \leftarrow C[p]$ if $p \in C$ else $\varnothing$;

8. &nbsp;&nbsp;&nbsp;&nbsp;else

9. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$C[g] \leftarrow\varnothing$;

10. &nbsp;&nbsp;&nbsp;&nbsp;append $g$ to $C[g]$;

11. &nbsp;&nbsp;&nbsp;&nbsp;if $G^{-1}(g) \ne\varnothing$ then

12. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;let $p \leftarrow$ an arbitrary predecessor of $g$;

13. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$G(p) \leftarrow(G(p) \setminus\{g\}) \cup G(g)$;

14. &nbsp;&nbsp;&nbsp;&nbsp;if $G(g) \ne\varnothing$ then

15. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;let $s \leftarrow$ an arbitrary successor of $g$;

16. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$G^{-1}(s) \leftarrow(G^{-1}(s) \setminus\{g\}) \cup G^{-1}(g)$;

17. &nbsp;&nbsp;&nbsp;&nbsp;remove $g$ from $G$ and $G^{-1}$;

18. $\mathcal{T}' \leftarrow\mathcal{T} \setminus S$;

19. return $(G,G^{-1},\mathcal{T}',C)$;

The algorithm proceeds as follows:

1. Identify all single-qubit gates.

2. Traverse the circuit in topological order, extending single-qubit chains whenever possible.

3. For each gate in a chain, update adjacency relations by bypassing the contracted node, ensuring that dependency edges are preserved.

4. Remove contracted nodes from the adjacency maps and the topological order.

This contraction reduces the number of nodes considered during later partitioning stages, while a dictionary map (labeled by $C$ in Alg. 4) maintains explicit records of the merged single-qubit gates to allow full reconstruction of the original circuit.

Complexity Analysis. Let $|V|$ denote the number of gates and $|E|$ the number of dependency edges in the circuit DAG. Identifying single-qubit gates requires $O(|V|)$ time. The traversal in topological order visits each gate once and processes each adjacency update in $O(1)$ expected time using hash-based adjacency maps. Since each edge is considered at most once when bypassing contracted gates, the total update cost is $O(|E|)$. Therefore, the total time complexity is

The space complexity is also linear: adjacency maps store $O(|V| + |E|)$ entries, and the dictionary $C$ introduces only an additional $O(|V|)$ storage overhead. Hence, the algorithm is asymptotically optimal with respect to both time and space for this task.

Algorithm for Recombining Single-Qubit Chains

After circuit partitioning has been performed on the contracted DAG, we must restore the original single-qubit gates to ensure correctness of the final partitioning. The following algorithm reinserts contracted single-qubit chains into the partition sets, maintaining consistency with gate dependencies.

Algorithm 5: Recombining Single-Qubit Chains

Input: $G$ forward adjacency map of the contracted DAG, $G^{-1}$ reverse adjacency map of the contracted DAG, $C$ dictionary of single-qubit chains (as returned by Algorithm 4), $\mathcal{L}$ a partition of the contracted circuit gates into disjoint sets.

Output: $\mathcal{L}'$, a partition of the full circuit including recombined single-qubit chains.

1  L ← {set(P) : P ∈ L};                                      /* Convert partitions to mutable sets */
2  initialize map M : g ↦ P such that g ∈ P for each gate g and partition P ∈ L;
3  foreach chain C ∈ unique(C) do
4      let g_head ← C[0] and g_tail ← C[−1];
5      if G⁻¹(g_head) ≠ ∅ then
6          let p ← an arbitrary predecessor of g_head;
7          M(p) ← M(p) ∪ C;
8      else if G(g_tail) ≠ ∅ then
9          let s ← an arbitrary successor of g_tail;
10         M(s) ← M(s) ∪ C;
11     else
12         L ← L ∪ {C};                                         /* Chain is isolated, forms a new partition */
13 return L;

The procedure works by traversing each contracted chain $C$ and merging it back into the partition containing one of its neighboring gates:

(1) If the chain has a predecessor in $G^{-1}$, it is merged into the same partition as that predecessor.

(2) Otherwise, if the chain has a successor in $G$, it is merged into that partition.

(3) If the chain is isolated (no predecessors or successors), it is appended as its own partition.

Complexity Analysis. Let $|V|$ denote the number of contracted gates, $|E|$ the number of edges, and $|C|$ the number of single-qubit chains. Constructing the mapping $M$ requires $O(|V|)$ time. Each chain is processed exactly once, with constant-time set merges and membership lookups using hash tables. The total number of insertions across all chains is $O\left(\sum_{C \in\mathcal{C}} |C|\right) = O(|V|)$, since each gate belongs to at most one chain. Therefore, the overall time complexity is

The space complexity is $O(|V| + |\mathcal{C}|)$, dominated by the partition map $M$ and storage of chain memberships.