1
Joint Optimization of Qubit Leasing and Quantum Circuit Distribution
arXiv:2606.00501v1 [quant-ph] 30 May 2026
Anoushka Dey, Gaurav S. Kasbekar, Senior Member, IEEE
Abstract—We consider an agent, who would like to execute a given quantum circuit using resources leased from a set of quantum computers (QCs) connected by a quantum network. For this purpose, the agent needs to make the following four key decisions: (i) how many qubits to lease from each QC, (ii) at which QCs to store different circuit qubits in different time slots, (iii) at which QC to execute each gate in the circuit, and (iv) how to move qubits between QCs, choosing between migration and teleportation. We refer to this problem facing the agent as the joint qubit leasing and quantum circuit distribution (JQLQCD) problem, and provide a comprehensive integer linear programming (ILP) formulation for it. We show that the JQLQCD problem is NP-complete. Next, we identify several special cases in which the problem can be optimally solved in closed form or via polynomial-time algorithms. Also, we propose a greedy algorithm with local search refinement to solve large instances of the general JQLQCD problem. Finally, we evaluate the performance of the proposed greedy algorithm using extensive numerical computations. Index Terms—Quantum Computers, Qubits, Quantum Circuit Distribution, Qubit Leasing, Integer Linear Program
I. I NTRODUCTION Quantum computing promises exponential speedups for certain computational problems, but current quantum computers (QCs) face severe limitations in qubit count and coherence time [1]. Distributing quantum computations across multiple QCs connected by a quantum network offers a path to overcoming the constraints of a single device and scaling up operations [2], [3], [4]. However, this distribution introduces significant challenges in resource allocation, qubit placement, and communication management [1]. The problem of mapping quantum circuits to hardware has been extensively studied for single QCs [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [15], [16], [17], [18], [19], [20], [21], [22], [23], where the primary challenge is mapping logical qubits to physical qubits subject to connectivity constraints and gate fidelity considerations. As quantum devices grow and quantum networks emerge, distributed quantum computing has gained attention as a promising approach to overcoming the limitations of individual devices [1], [2], [3], [4]. Various aspects of distributed quantum computing, including compilation [24], [25], [26], [27], qubit allocation and circuit optimization [28], [29], [30], distributed quantum computing architectures [4], [31], and circuit partitioning strategies [32], [33], [34], [35], [36], [37], [38], [39], [40], [41], [42], [43] have been studied in prior work. Also, quantum The authors are with the Department of Electrical Engineering, Indian Institute of Technology (IIT) Bombay, Mumbai, 400076, India. Their email addresses are [email protected] and [email protected].
communication, entanglement distribution, resource allocation in quantum networks, and quantum cloud computing have been investigated in several papers [44], [45], [46], [47], [48], [49], [50], [51], [52], [53], [54]. As the number and scale of commercial providers of resources such as qubits and gates for distributed quantum computing are expected to increase rapidly in the near future [1], an agent who would like to execute a given quantum circuit in a distributed manner must be able to efficiently determine the numbers of resources to lease out from different providers, in addition to solving the traditional problem of partitioning the circuit across the available QCs. Also, the numbers of resources to lease from different QCs and the partitioning of the circuit must be jointly optimized to effectively achieve various objectives, including minimization of the leasing cost, communication cost, and makespan (circuit completion time). Although the problem of quantum circuit partitioning has been extensively studied in prior work [32], [33], [34], [35], [36], [37], [38], [39], [40], [41], [42], [43], to the best of our knowledge, joint optimization of resource leasing and quantum circuit distribution has not been addressed. This is the space in which we contribute in this paper. We consider an agent, who would like to execute a quantum circuit with a given set of logical qubits. Also, there is a set of QCs connected by a quantum network. Each QC from this set offers resources for lease, subject to its storage capacity, which represents the maximum number of qubits that can be stored at the QC, and its execution capacity, which represents the maximum number of qubits that can be actively processed during a time slot. The agent needs to execute its quantum circuit using resources leased from different QCs. For this purpose, the agent makes the following four key decisions: (i) how many qubits to lease from each QC, (ii) at which QCs to store different circuit qubits in different time slots, (iii) which QC executes each gate in the circuit, and (iv) how qubits are moved between QCs, choosing between migration and teleportation based on cost considerations. We refer to this problem facing the agent as the joint qubit leasing and quantum circuit distribution (JQLQCD) problem. The goal is to minimize the total system cost subject to capacity and execution constraints. This total cost balances multiple components: the leasing costs for storage and execution capacity at different QCs, the gate execution costs, which vary across different QCs, the communication costs for qubit movement (either migration or teleportation), and the circuit makespan. A challenge is that different QCs may have heterogeneous capabilities, costs, and connectivity. E.g., some QCs may offer low leasing costs, but limited gate support or
2
costly qubit movements, while others may have higher leasing costs, but provide faster execution or better connectivity to other QCs. Some additional challenges are to ensure that circuit precedence constraints and QC capacity limits are satisfied and to determine the temporal scheduling of gate executions to minimize the overall makespan, while keeping costs low. We present an integer linear programming (ILP) formulation of the JQLQCD problem that explicitly models leasing costs, gate execution costs, and two distinct qubit relocation primitives– migration and teleportation. Migration physically transfers qubits along quantum channels, while teleportation uses pre-shared entanglement [44]. Our model enables a realistic analysis of the trade-offs between these two communication primitives. The main contributions of this paper are as follows: We provide a comprehensive ILP formulation for the JQLQCD problem, which features distributed quantum circuit execution for an agent, with explicit modeling of both migration and teleportation with distance-dependent costs. Unlike prior work in which QCs autonomously negotiate or operate under federated control [34], our model features passive QCs that provide resources to a single decision-making agent. This architecture reflects emerging quantum cloud platforms where users rent resources from multiple providers [53]. • We show that the JQLQCD problem is NP-complete by proving that the multiprocessor scheduling problem with precedence constraints (denoted P |prec|Cmax in standard scheduling notation), which is known to be NP-complete [55], [56], [57], is polynomial-time reducible to it. • Although the general JQLQCD problem is NP-complete, several special cases admit efficient solutions. We identify several special cases in which the problem can be solved optimally in closed form or via polynomialtime algorithms, including those in which (A) there is an unlimited capacity QC in a heterogeneous network, (B) homogeneous QCs with zero movement cost, (C) chain topology with sequential gates, (D) independent subcircuits with partitioned resources, (E) infinite resources with makespan minimization only, and (F) a tree-structured circuit with an arbitrary QC network. For case (A), we derive necessary and sufficient conditions for centralized execution on a single QC with unlimited resources to be optimal, whereas for cases (B) to (F), we provide polynomial-time algorithms for optimal solution of the JQLQCD problem. • We propose a greedy heuristic algorithm with local search refinement to solve large instances of the general JQLQCD problem. • Using extensive numerical computations, we demonstrate that our proposed greedy algorithm achieves solutions within 8 − 15 % of simulated annealing [58], while being 50 − 200× faster. For several special cases with known optimal solutions, the greedy algorithm finds solutions that are within 4 − 12 % of the optimal solution. These results validate the practical utility of the proposed greedy algorithm for real-time distributed quantum computing •
scenarios where fast decision-making is critical. The rest of this paper is organized as follows. Section II provides a review of related work. Section III presents the system model and problem formulation. Section IV proves the NP-completeness of the general problem. Section V analyzes polynomial-time solvable special cases and Section VI presents the greedy algorithm. Section VII provides our numerical results. Section VIII concludes and provides some directions for future work. II. R ELATED W ORK A. Single-Device Quantum Circuit Mapping The problem of mapping quantum circuits to physical hardware has been extensively studied for single QCs; surveys on this topic are [14], [17]. Early work focused on qubit allocation and routing subject to connectivity constraints [5], [6]. These approaches typically use SWAP gate insertion to route interactions between non-adjacent qubits in the device topology. More recent work has incorporated noise-aware compilation [7], [8] and crosstalk mitigation [9]. Recent advances in efficient mapping techniques [10], [11] have improved the performance for single-device scenarios. Several optimization formulations have been proposed, including SAT-based approaches [12], SMT solvers [13], and heuristic methods based on A* search [6]. Recent work on optimal subarchitectures [11] and efficient mapping tools [10] has advanced single-device mapping. In [22], a quantum circuit compiler based on a multi-objective heuristic optimization approach was proposed to achieve Pareto-optimality in the compilation. The work [23] proposed a scalable multiobjective genetic algorithm for quantum circuit optimization tailored to Noisy Intermediate-Scale Quantum (NISQ) devices. In [15], PowerMove, an efficient compiler for neutral atom QCs with zoned architecture, which leverages qubit movement capabilities, was proposed. The work [16] presented the design of a multi-target Multi-Level Intermediate Representation (MLIR)-based quantum compiler, which supports advanced optimizations. A routing-aware placement method for zoned neutral atom-based quantum computing architectures was proposed in [19]. In [18], a unified qubit mapping and routing framework applicable to diverse quantum instruction set architectures, was proposed. A scheme for automatically generating qubit mapping and routing compilers for evaluating quantum circuits on arbitrary quantum processors was proposed in [21]. A framework, called the MQT Predictor, which allows one to automatically select a suitable quantum device for a particular quantum circuit and application and provides an optimized compiler for the selected device, was proposed in [20]. However, these techniques are limited to single-device scenarios and do not address the resource allocation and communication challenges that arise in distributed quantum computing. B. Distributed Quantum Computing Distributed quantum computing has emerged as a promising approach to overcome the limitations of single QCs; recent
3
surveys on this topic are [1], [2], [3]. In [24], [25], [26], [27], compilers for distributed quantum computing were proposed. Qubit allocation and circuit optimization for distributed quantum computing were studied in [28], [29], [30]. The work [4], [31] has explored practical aspects of distributed quantum computing architectures. Several quantum circuit partitioning strategies have been proposed [32], [33], [40], [41], [42]. In [34], automated methods were developed for distributing quantum circuits across multiple devices, with a focus on minimizing the number of required entangled pairs. In [35], optimization techniques for partitioning circuits were proposed taking into account both communication costs and device capabilities. In [36], an algorithm for circuit partitioning was proposed based on deep reinforcement learning. In [37], a graph-based formulation was proposed for partitioning quantum circuits, which allows the joint optimization of gate and state teleportation costs. A framework for partitioning quantum circuits, which uses multilevel techniques that coarsen hypergraphs and partition at multiple levels of granularity, was proposed in [38]. In [39], a time-aware heuristic based on beam search was proposed to solve the quantum circuit partitioning problem, which is designed to minimize communication overhead without incurring prohibitive computational time. The work [43] studied the problem of efficiently distributing multiple quantum circuits across a shared quantum network under decoherence and network constraints. However, none of these papers addresses the problem of jointly leasing out qubits and distributing quantum circuits, which is studied in our paper.
C. Quantum Communication and Networks, Entanglement Distribution, and Quantum Cloud Computing Resource allocation in quantum networks has been studied from various perspectives. Early theoretical work established the foundations of quantum communication [44] and entanglement distribution [45]. High-fidelity entanglement distribution and purification in quantum networks were investigated in [46], [47], [48], [49], [50], [51]. The work [52] specifically addressed resource allocation in quantum networks for distributed quantum computing. Prior work on quantum cloud computing has explored scenarios in which users rent resources from multiple providers [53], [54]. However, none of these papers considers the problem of jointly leasing out qubits and quantum circuit distribution that we address in this paper.
D. Complexity The complexity of quantum circuit optimization problems has been studied in various contexts. Qubit routing on constrained topologies is known to be NP-hard [59]. Makespan minimization for quantum circuits with precedence constraints relates to the classical multiprocessor scheduling problem P |prec|Cmax , which is strongly NP-hard [60], [61]. However, the complexity of the JQLQCD problem that we study in this paper has not been analyzed in prior work.
III. S YSTEM M ODEL AND P ROBLEM F ORMULATION A. System Model Consider an agent, shown at the top of Fig. 1, who would like to run a quantum circuit with a set of logical qubits Q and a set of gates G. For each gate g, Og denotes the set of operand qubits required to execute that gate. Time is divided into discrete slots and T denotes the set of slots. Also, there is a set, P , of QCs, which are connected by a quantum network. Each QC p ∈ P is characterized by two capacity parameters: storage capacity sp , which limits the number of qubits that can be stored simultaneously at p, and execution capacity ep , which limits the number of qubits that can be actively processed at p during any time slot. The agent needs to execute its quantum circuit using resources leased from the QCs in P . For this purpose, the agent needs to make four key decisions: (i) how many qubits to lease from each QC, (ii) at which QCs to store different circuit qubits in different time slots, (iii) which QC will execute each gate in the circuit, and (iv) how qubits will be moved between QCs, i.e., whether they will be migrated or teleported. As illustrated in Fig. 1, the available QCs, p1 , . . . , p|P | , are passive resource providers connected via quantum and classical channels. The agent coordinates all resource allocation and circuit execution decisions. The bottom-right panel shows the input quantum circuit represented as a directed acyclic graph (DAG) with gates g1 , . . . , g|G| that must satisfy the precedence constraints indicated by the arrows. Table I describes the notation used throughout this paper. The per-qubit leasing cost for storage (respectively, execution capacity) at QC p ∈ P is denoted by csp (respectively, cep ). The execution cost of gate g ∈ G at QC p ∈ P is denoted by cgp . Note that our model considers the general case where the different QCs in P may be heterogeneous, possibly based on different storage and computation technologies, and may have different gate fidelities, execution latencies, etc. Two primitives– migration and teleportation– for qubit relocation are modeled (see the panel on the left of Fig. 1). Migration involves physically transferring a qubit along a quantum channel between two QCs, with cost growing with physical distance and link reliability. Teleportation transfers a quantum state using pre-shared entanglement and classical communication [44]. No physical qubit moves, but fresh entangled pairs must be consumed. The effective cost includes the number of Bell pairs that must be distributed [48], fidelity loss with distance, and classical communication latency. Let E(p′ , p) be the cost of teleporting a qubit from QC p′ to QC p; it includes the entanglement cost of sharing a Bell pair between QCs p′ and p. This would typically scale with the physical distance and the number of network hops. Similarly, let d(p′ , p) represent the migration cost, i.e., the cost of physically transferring a qubit from QC p′ to QC p along a quantum channel. The parameter β is the weight for the makespan (circuit completion time) term in the objective function (see (1)) and allows us to achieve different trade-offs between the makespan and the other costs. Gate availability is captured by the indicator Ap,g , which equals 1 if gate g can execute at QC p and 0 otherwise. This models heterogeneous
4
Fig. 1. The figure illustrates the system model. The agent leases resources from multiple QCs (QC p1 to QC p|P | ) connected by a quantum network. Each QC p has qubit storage capacity sp and qubit execution capacity ep , and charges costs csp and cep for leasing storage and execution qubits, respectively. The execution cost of gate g at QC p is cgp . The figure also shows the quantum circuit that the agent would like to run using the leased resources.
QC capabilities where not all gates can be executed on all QCs. Each gate g has an associated duration τg representing its execution time. We now describe the decision variables that appear in our optimization problem (see Table I). These variables fall into four categories: resource allocation, qubit placement, qubit movement, and gate scheduling. Resource Allocation Variables: Let the integer variable rps (respectively, rpe ) denote the number of storage (respectively, execution) qubits that the agent leases from QC p ∈ P . Qubit Placement Variables: These track qubit locations and resource usage over time. The binary variable xq,p,t indicates whether qubit q is located at QC p in time slot t, while zq,p,t indicates whether qubit q actively uses execution capacity at QC p in time slot t. The distinction between these variables allows us to model scenarios where a qubit may be stored at a QC without actively consuming execution resources. Qubit Movement Variables: These model the two qubit t relocation primitives. The binary variable γq,p ′ ,p equals 1 if ′ qubit q is migrated from QC p to QC p in time slot t. t ′ Similarly, wq,p ′ ,p equals 1 if qubit q is teleported from p to p in time slot t using pre-shared entanglement. Our formulation ensures that exactly one movement method is used for each qubit relocation. The cost of teleporting qubit q from p′ to p
at time t is modeled as t TeleportCost(q, p′ , p, t) = E(p′ , p) · wq,p ′ ,p .
Similarly, the migration cost from p′ to p at time t is t MigrationCost(q, p′ , p, t) = d(p′ , p) · γq,p ′ ,p .
Gate Scheduling Variables: They determine when and where gates execute. The binary variable ug,p indicates whether gate g is assigned to QC p for execution. The integer variable tg specifies the start time of gate g, and Tmax represents the overall makespan (completion time) of the circuit execution.
B. Problem Formulation In this section, we formulate the JQLQCD problem, which is the focus of this paper. The objective of the agent is as
5
are as follows.
TABLE I T HE TABLE DESCRIBES THE NOTATION USED IN THIS PAPER .
Symbol Q P T G Og sp ep csp cep cgp d(p′ , p) E(p′ , p) β Ap,g τg rps rpe xq,p,t zq,p,t t γq,p ′ ,p t wq,p ′ ,p ug,p tg Tmax
Description Set of logical qubits (index q) Set of quantum computers (index p) Set of discrete time slots (index t) Set of gates in the circuit (index g) Set of operand qubits for gate g Storage capacity at QC p Execution capacity at QC p Per-qubit leasing cost for storage at QC p Per-qubit leasing cost for execution capacity at QC p Cost of execution of gate g at QC p Cost of migration of a qubit from p′ to p Cost of teleportation of a qubit from p′ to p Makespan weight 1 if gate g can execute at QC p else 0 Duration of gate g Number of storage qubits leased from p Number of execution qubits leased from p 1 if qubit q is located at QC p at time t else 0 1 if qubit q uses execution at p at t else 0 1 if qubit q is migrated from p′ to p at t else 0 1 if qubit q is teleported from p′ to p at t else 0 1 if gate g executes at QC p else 0 Start time of gate g Makespan (circuit completion time)
rps ∈ {0, 1, . . . , sp }, ∀p,
(2)
rpe ∈ {0, 1, . . . , ep }, ∀p, t ′ ′ γq,p ′ ,p ∈ {0, 1}, ∀q, p , p, t, where p ̸= p, t ′ ′ wq,p ′ ,p ∈ {0, 1}, ∀q, p , p, t, where p ̸= p,
(4)
xq,p,t ∈ {0, 1}, ∀q, p, t,
(6)
zq,p,t ∈ {0, 1}, ∀q, p, t,
(7)
ug,p ∈ {0, 1}, ∀g, p,
(8)
xq,p,t ≤ rps , ∀p, t,
(9)
zq,p,t ≤ rpe , ∀p, t.
(10)
xq,p,t = 1, ∀q, t,
(11)
X
(3) (5)
q∈Q
X q∈Q
X p∈P
zq,p,t ≤ xq,p,t , ∀q, p, t, X ug,p = 1, ∀g,
(12) (13)
p∈P
ug,p ≤ Ap,g , ∀g, p,
(14)
ug,p ≤ xq,p,tg , ∀q ∈ Og , p, g.
(15)
tg2 ≥ tg1 + τg1 , ∀g1 , g2 such that g1 ≺ g2 , (16) Tmax ≥ tg + τg , ∀g, t t γq,p ′ ,p + wq,p′ ,p ≤ 1,
min
∀q, p , p, t,
xq,p,t − xq,p,t−1 ≤ ′ max′
p ∈P, p ̸=p
follows.
(17)
′
t t γq,p ′ ,p + wq,p′ ,p
(18)
′
, ∀q, p , p, t. (19)
X
XX g cp ug,p csp rps + cep rpe + g∈G p∈P
p∈P
{z
| +
Leasing cost
}
X X XX
|
{z
}
Gate execution cost
t d(p′ , p) γq,p ′ ,p
q∈Q p′ ∈P p∈P t∈T
| +
{z
Migration cost
X X XX
}
t E(p′ , p) wq,p ′ ,p +β Tmax .
(1)
q∈Q p′ ∈P p∈P t∈T
|
{z
Teleportation cost
}
The first two terms correspond to the leasing and gate execution costs. The third term corresponds to the migration cost and the fourth term to the teleportation cost. The final term corresponds to the makespan. The constraints of the problem, which are explained below,
Resource Capacity Constraints ((2) and (3)): Constraints (2) and (3) ensure that the numbers of storage and execution qubits leased from each QC p must be non-negative and bounded by that QC’s maximum storage and execution capacities sp and ep , respectively. Binary Decision Variables ((4), (5), (6), (7), and (8)): Constraints (4), (5), (6), (7), and (8) enforce the binary nature t t of the decision variables γq,p ′ ,p , wq,p′ ,p , xq,p,t , zq,p,t , and ug,p , respectively. Resource Usage Constraints ((9) and (10)): Constraints (9) and (10) enforce that in any time slot, the number of qubits stored at a QC cannot exceed the leased storage capacity, and the number of qubits being processed cannot exceed the leased execution capacity, respectively. Qubit Location Uniqueness ((11)): Each qubit q must be located at exactly one QC at any given time t. Execution Requires Presence ((12)): If a qubit q uses execution capacity at a QC p, it must be located there. Gate Assignment Constraints ((13) and (14)): Constraint (13) ensures that each gate g is assigned to exactly one QC p. Constraint (14) ensures that gates are only assigned to QCs that are capable of executing them. Operands Present ((15)): When a gate g executes at a QC p, all qubits q in its operand set Og must be present at that QC at the gate’s start time tg . Precedence and Makespan Constraints ((16) and (17)): Constraint (16) enforces circuit precedence relationships: If
6
gate g1 precedes g2 (denoted by g1 ≺ g2 ), then g2 cannot start until g1 completes. Constraint (17) ensures that the makespan Tmax is the completion time of the last gate. Movement Consistency Constraints ((18) and (19)): Constraint (18) ensures that migration and teleportation are mutually exclusive for any qubit movement. Constraint (19) enforces that if a qubit’s location changes between time slots, a migration or teleportation operation must have occurred. Collectively, the above constraints ensure a physically feasible circuit execution process in which resource capacity constraints are satisfied, gates execute in the correct order, and all operations follow the principles of quantum mechanics. Remark 1. We make the following assumptions about the qubit movement times. The general formulation assumes that the qubit movement operations, migration and teleportation, take some non-negative amounts of time, denoted by τmigrate (p′ , p) and τteleport (p′ , p), respectively, to complete. Specifically, we assume that these movement times are at most the width of a single time slot, i.e., τmigrate (p′ , p), τteleport (p′ , p) ∈ [0, 1],
∀ p′ , p ∈ P, p′ ̸= p, (20) so that any qubit movement completes within the same time slot in which it begins. This ensures consistency with the discrete time-slot formulation, in which the movement consistency constraint (19) implicitly captures the effect of movement on qubit location across consecutive slots. Some of the special cases in Section V (specifically, those in Section V-B) assume instantaneous movement (τmove = 0) to enable closed-form analysis. This assumption is explicitly stated when applicable and is discussed in detail in Section V-B. For the general problem, τmigrate (p′ , p) and τteleport (p′ , p) are problemdependent parameters determined by the physical quantum network characteristics, including channel transfer rates for migration and entanglement distribution rates and classical communication latency for teleportation. IV. C OMPUTATIONAL C OMPLEXITY A. NP-Completeness Theorem 1. The JQLQCD problem is NP-complete. Proof: A candidate solution to the JQLQCD problem t t specifies rps , rpe , xq,p,t , zq,p,t , ug,p , tg , γq,p ′ ,p , and wq,p′ ,p for ′ all q ∈ Q, p, p ∈ P, t ∈ T , and g ∈ G. Given a candidate solution, checking whether capacity constraints P P it satisfies the s e x ≤ r and z ≤ r for all p, t requires q,p,t q,p,t p p q q O(|Q|·|P |·T ) time. Checking the qubit uniqueness constraints P x = 1 for all q, t can be done in O(|Q| · |P | · T ) time. q,p,t p P The gate assignment constraints p ug,p = 1 for all g can be checked in O(|G| · |P |) time. The precedence constraints tg2 ≥ tg1 + τg1 for all g1 , g2 such that g1 ≺ g2 can be checked in O(|E|) time, where |E| is the number of precedence edges. The makespan constraint Tmax ≥ tg + τg for all g can be checked in O(|G|) time. The movement consistency constraints ((18) and (19)) can be checked in O(|Q| · |P |2 · T ) time. Finally, the total cost given in (1) can be computed in O(|P | · |G| + |Q| · |P |2 · T ) time. The total verification time
is O(|Q| · |P |2 · T + |G| · |P | + |E|), which is polynomial in the input size. Hence, the problem is in class NP [58]. Now, we show that the multiprocessor scheduling problem with precedence constraints, denoted P |prec|Cmax in standard scheduling notation, which is known to be NP-complete [55], [56], [57], is polynomial-time reducible to the (decision version of the) JQLQCD problem. Consider the following instance of the P |prec|Cmax problem: We are given a set of tasks T = {T1 , T2 , . . . , Tn } with processing time πi for task Ti , a set of m identical parallel processors, a set of precedence constraints Ti ≺ Tj forming a DAG, and a target makespan bound K, where the makespan is defined as the completion time of the last task. The problem is to decide whether there exists a schedule with makespan at most K. This problem was shown to be strongly NP-hard in [55] and it remains NP-hard even when all tasks have unit processing time (πi = 1 for all i) and the precedence graph is restricted to certain structures (e.g., trees with bounded degree, series-parallel graphs). From the above instance of the P |prec|Cmax problem, we construct an instance of the JQLQCD problem as follows. The quantum circuit is created by generating a gate gi with duration τgi = πi for each task Ti . We introduce n qubits Q = {q1 , q2 , . . . , qn }, where each gate gi operates exclusively on its corresponding qubit qi as a single-qubit gate. The precedence constraints are mapped directly: If Ti ≺ Tj in the scheduling instance, then we enforce gi ≺ gj in the circuit. We configure the quantum circuit created as explained above with the following parameters. We create |P | = m QCs– one for each processor. Each QC has infinite capacity, so we set sp = ep = ∞ for all p ∈ P . All costs are set to zero: csp = cep = 0, cgp = 0, ′
∀p ∈ P,
(21)
∀p ∈ P, g ∈ G, ′
d(p , p) = E(p , p) = 0,
(22) ′
∀p, p ∈ P.
(23)
The availability of gates is unrestricted, with Ap,g = 1 for all p ∈ P, g ∈ G, i.e., all gates can run on all QCs. Finally, we set the makespan weight β = 1, ensuring that the objective function in (1) equals the makespan Tmax . Note that this reduction can be performed in polynomialtime as it involves creating n gates and n qubits, which requires O(n) time, copying precedence constraints, which requires O(|E|) time, creating m QCs, which requires O(m) time, and setting cost matrices to zero, which requires O(m2 + m · n) time, yielding an overall complexity of O(m2 + mn + |E|). In the above instance of the JQLQCD problem, we ask: Does there exist a solution with makespan Tmax ≤ K? We will now prove that the instance of P |prec|Cmax has a schedule with makespan at most K if and only if the instance of the JQLQCD problem has a solution with makespan Tmax ≤ K. To prove necessity, suppose the instance of P |prec|Cmax has a schedule S with makespan at most K. We map this schedule to a solution to the JQLQCD problem as follows. For each task Ti scheduled on processor j with a start time of t in S, we assign gate gi to QC pj by setting ugi ,pj = 1, set the gate start time tgi = t, and place qubit qi at QC pj for all relevant time slots by setting xqi ,pj ,t′ = 1 for t′ ∈ [t, t+πi ]. No qubit move-
7
t t ′ ments are needed, so γq,p ′ ,p = wq,p′ ,p = 0 for all q, p, p , t. The resulting makespan is Tmax = maxg∈G (tg + τg ). Since S satisfies all precedence constraints and has makespan at most K, the constructed solution to the JQLQCD problem also satisfies all precedence constraints (see (16)) and has objective function value Tmax ≤ K (see (17) and (1)). All capacity constraints are trivially satisfied because sp = ep = ∞. Thus, the JQLQCD problem has a feasible solution with makespan Tmax ≤ K, which shows necessity. To prove sufficiency, suppose the JQLQCD problem instance has a feasible solution with makespan Tmax ≤ K. We construct a schedule S for the P |prec|Cmax problem as follows. For each gate gi assigned to QC pj (i.e., ugi ,pj = 1) with start time tgi , we schedule task Ti on processor j with a start time of tgi . This schedule S is feasible because the solution to the JQLQCD problem instance satisfies the gate assignment constraint (see (13)), ensuring that each gate is assigned to exactly one QC, and thus each task is assigned to exactly one processor; also, the precedence constraints (see (16)) guarantee that if gi ≺ gj , then tgj ≥ tgi + τgi , which translates to Ti ≺ Tj being satisfied in S. The makespan constraint (see (17)) ensures that Tmax ≥ tg + τg for all g, so the makespan of S is Tmax ≤ K. Therefore, S is a valid schedule with makespan at most K, which shows sufficiency. The result follows. In fact, in the above proof of Theorem 1, we have shown the following stronger result.
Corollary 1. The JQLQCD problem remains NP-complete even when (a) all QCs have infinite capacity (sp = ep = ∞), (b) all costs except makespan are zero (csp = cep = cgp = d(p′ , p) = E(p′ , p) = 0 for all q, p, p′ ), (c) all gates can execute on all QCs (Ap,g = 1 for all p, g), and (d) the circuit consists only of single-qubit gates. Proof: This result follows directly from the reduction used to prove Theorem 1, which uses exactly these restricted conditions. Recall that a problem is said to be strongly NP-complete if it remains NP-complete even when all numerical parameters are bounded by a polynomial in the input size [55], [57]. Corollary 2. The JQLQCD problem is strongly NP-complete. Proof: The P |prec|Cmax problem is known to be strongly NP-complete [55], [57]. We show that the reduction used to prove Theorem 1 can be carried out with all numerical parameters polynomially bounded in the input size. Recall that in the reduction, the gate durations are set to τgi = πi , which are polynomially bounded whenever the processing times πi are. All costs are set to zero, which is trivially polynomially bounded. The storage and execution capacities, which were set to ∞ in the proof of Theorem 1, can be replaced by M = |Q| · |G|, since no feasible solution ever needs to store more than |Q| qubits at any QC or process more than |Q| qubits in any time slot; thus, setting sp = ep = M for all p ∈ P is functionally equivalent to unlimited capacity within
any feasible solution, while keeping all parameters polynomially bounded in the input size. Hence, the reduction is a valid polynomial-time reduction from a strongly NP-complete problem in which all numerical parameters are polynomially bounded, and the result follows. Strong NP-completeness implies that no pseudopolynomial-time algorithm for finding the optimal solution of the JQLQCD problem exists (unless P = NP), ruling out dynamic programming (DP) approaches that work for polynomially bounded numerical parameter values. B. Parameterized Complexity While the general JQLQCD problem is NP-complete, we now show that it is tractable for some specific parameter ranges. Natural parameters to consider include the circuit width wc = maxg∈G |Og | (maximum number of qubits in any gate’s operand set), the circuit depth d (length of the longest path of dependent gates from input to output, i.e., critical path), the number of QCs |P |, the tree-width wt of the circuit dependency graph [62], [63], and the maximum QC capacity κ = maxp min(sp , ep ). Theorem 2. The JQLQCD problem is fixed-parameter tractable (FPT) [64], [65] when parameterized by the number of QCs |P | and the maximum QC capacity κ, assuming that the circuit has bounded tree-width wt , |P |, and κ [62], [63]. Proof: With bounded tree-width wt and bounded |P | and κ, we construct a tree decomposition of the circuit’s dependency graph and apply DP over it. Each node in the tree decomposition contains a bag– a subset of at most wt + 1 qubits that must be considered together. State encoding. For each bag, the DP state records: (i) the assignment of each qubit in the bag to a QC, i.e., a mapping from qubits to P , which encodes xq,p,t ; (ii) the current execution capacity usage at each QC, which encodes P zq,p,t and allows us to determine rpe = maxt q zq,p,t ; (iii) the gate assignment ug,p for each gate g whose operand qubits are all present in the current bag; and (iv) the earliest feasible start time tg for each such gate, respecting the precedence constraints (16) within the bag. The leasing variables rps and rpe are not independent decisions but are derived fromP the qubit s placement and execution assignments as r = max t p q xq,p,t P and rpe = maxt q zq,p,t , so they are determined once the placement is fixed. Transitions. When two child bags are merged at a parent bag, the DP combines their partial solutions by: checking that shared qubits have consistent QC assignments across the two children; computing qubit movement costs via (18) and (19) for qubits that change QC between bags; enforcing the mutual exclusivity constraint (18) for migration and teleportation; and propagating the earliest feasible start times for gates in the parent bag respecting inter-bag precedence constraints (16). Optimality. The DP computes, for each bag and each state, the minimum partial cost (leasing cost, gate execution cost, and movement cost) over all feasible assignments of qubits and gates within that subtree of the decomposition. Since the tree decomposition ensures that all interactions between qubits
8
separated across bags are mediated through shared qubits appearing in the bag boundary, the optimal global solution is obtained by combining optimal partial solutions bottom-up, with the root bag yielding the globally optimal assignment and the makespan Tmax computed as maxg∈G (tg + τg ) per constraint (17). Complexity. The state space per bag is O(|P |wt · κ|P |·wt ), tracking the QC assignment of each qubit in the bag and the capacity usage at each QC. With O(|G|) bags in the tree decomposition and O(|P |2wt ) transitions per bag, the total complexity is O(|G| · |P |3wt · κ|P |·wt ), which is polynomial in |G| for fixed |P |, wt , and κ, establishing FPT tractability. The result follows. For typical quantum circuits, wt ≤ 2 for nearest-neighbor architectures with limited qubit connectivity, wc ≤ 2 for circuits with only single and two-qubit gates, and |P | is typically small (e.g., 2-10 distributed QCs). These observations suggest that practical instances may be more tractable than the worst-case complexity suggests, motivating the development of efficient algorithms for special cases with restricted parameter ranges. In Section V, we propose polynomial-time algorithms for several special cases. V. P OLYNOMIAL -T IME O PTIMAL A LGORITHMS FOR S PECIAL C ASES Although Theorem 1 shows that the general JQLQCD problem is NP-hard, in this section, we identify several special cases in which the problem can be solved optimally in closedform or via polynomial-time algorithms.
p0 ) may still be optimal. In Section V-A1, we present multiple sets of sufficient conditions under which this occurs. Remark 2. We make the following assumptions about qubit locations. Before the start of circuit execution, all qubits are located at p0 . After the circuit execution completes, all qubits must be returned to p0 . These assumptions are natural in the cloud computing setting where p0 is the agent’s home QC: qubits originate at p0 , may be temporarily moved to QCs in P ′ for cheaper execution, and must be returned to p0 upon completion. Under these assumptions, any distributed solution that moves qubits to QCs in P ′ incurs round-trip movement costs. Note that a distributed solution may still keep some qubits entirely at p0 throughout execution (incurring no movement cost for those qubits), while moving other qubits to QCs in P ′ for some gates and returning them to p0 afterward. 1) Sufficient Conditions for Optimality of Centralized Solution: The centralized solution is optimal if any of the conditions S1 to S4 given below holds. Condition S1 (Dominant Movement Cost): The minimum movement cost to any QC in P ′ exceeds the total potential savings from both lower gate execution costs and lower leasing costs at QCs in P ′ compared to p0 : min min(d(p0 , p), E(p0 , p)) > ∆Cgate + ∆Clease ,
p∈P ′
(25)
where + 1 X max′ cgp0 − cgp , p∈P |Q| g∈G s + ∆Clease = max′ (cp0 + cep0 ) − (csp + cep ) , ∆Cgate =
p∈P
+
A. Case 1: Unlimited Capacity QC in a Heterogeneous Network Problem Setting: The quantum network consists of one QC p0 ∈ P with unlimited capacity (sp0 = ep0 = ∞) and a set of additional QCs P ′ = P \ {p0 } with finite capacities sp , ep < ∞ for all p ∈ P ′ . The QCs are connected in an arbitrary network topology with heterogeneous migration costs d(p′ , p), teleportation costs E(p′ , p), leasing costs csp , cep , and gate execution costs cgp . We refer to the QCs in P ′ as “limited QCs” since their capacities are finite. Base Solution: When all qubits of the given quantum circuit are statically assigned to p0 , no migration or teleportation is required. The problem reduces to gate scheduling with precedence constraints, whose optimal solution can be found by topological sorting of the circuit DAG to determine valid gate orderings [66], [67] and applying a list scheduling algorithm [68], [69] to minimize the makespan Tmax . The complexity of this algorithm is O(|G| + |E|), where E denotes the set of precedence edges in the circuit. The achieved cost (value of the objective function in (1)) is X ∗ opt Ccentralized = csp0 · |Q| + cep0 · |Q| + cgp0 + β · Tmax , (24) g∈G opt where Tmax is the critical path length of the circuit DAG [66]. Despite the availability of other QCs, viz., those in P ′ , the above centralized solution (statically allocating all qubits to
and x = max(0, x). Intuitively, ∆Cgate captures the average per-qubit savings in gate execution costs from running gates at cheaper QCs in P ′ instead of p0 , and ∆Clease captures the maximum perqubit savings in leasing costs from storing and processing qubits at a cheaper QC in P ′ instead of p0 . Condition (25) ensures that even when both sources of savings are combined, the movement cost required to exploit them exceeds the total benefit, making the centralized solution at p0 optimal. Condition S2 (Prohibitive Movement Cost): All movement costs from p0 to any other QC are sufficiently high: min′ min(d(p0 , p), E(p0 , p)) > ∆Cgate + ∆Clease , (26) p∈P
where + ∆Cgate = max cgp0 − min′ cgp , p∈P g∈G s + ∆Clease = max′ (cp0 + cep0 ) − (csp + cep ) , p∈P
AND the centralized solution is no worse than executing the circuit using only the QCs in P ′ : ∗ ∗ Ccentralized ≤ Cisolated ,
(27)
∗ where Cisolated is a lower bound on the cost of executing the circuit using only QCs in P ′ (i.e., without p0 ): ∗ Cisolated ≤
X p∈P ′
(csp + cep ) · min (|Q|, min(sp , ep )) +
X g∈G
min cgp .
p∈P ′
(28)
9
Intuitively, the first part, (26), ensures that hybrid solutions (using both p0 and QC(s) in P ′ ) are suboptimal by enforcing that moving qubits between p0 and any limited QC costs more than the potential savings in gate execution costs and leasing costs combined. The second part, (27), ensures that centralized execution at p0 is also better than circuit execution without using p0 at all. Together, the two parts guarantee global optimality of the centralized solution. Condition S3 (Capacity Bottleneck): The total network capacity excluding p0 is insufficient to store all qubits: X min(sp , ep ) < |Q|, (29) p∈P ′
and the maximum total savings achievable by moving any subset of qubits to QCs in P ′ – from both lower leasing costs and lower gate execution costs– do not exceed the minimum movement cost incurred by doing so: + X max′ (csp0 + cep0 ) − (csp + cep ) · min(sp , ep ) p∈P
+
X
p∈P ′
max′ cgp0 − cp
g∈G
≤
g +
p∈P
X p∈P ′
min(sp , ep ) · min′ min(d(p0 , p), E(p0 , p)), p∈P
(30)
where the first term on the LHS P is the maximum leasing cost savings from moving up to p∈P ′ min(sp , ep ) qubits to QCs in P ′ , the second term on the LHS is the maximum gate execution cost savings from running gates at cheaper QCs in P ′ , and the RHS is the minimum total movement cost of sending those qubits to P ′ . Intuitively, since P ′ lacks sufficient aggregate capacity to P store all |Q| qubits, at least k = |Q| − p∈P ′ min(sp , ep ) qubits must reside at p0 . However, the remaining qubits that could fit in P ′ need not be moved there: they may simply be processed entirely at p0 without any movement. Conditions (29) and (30) together ensure that even if we were to move as many qubits as possible to P ′ to exploit lower leasing and gate execution costs, the combined savings from doing so would not offset the movement costs incurred. Hence, all qubits are best kept at p0 , making centralized execution optimal. Here, min(sp , ep ) represents the effective usable capacity of QC p. Condition S4 (Communication Bottleneck): The following two conditions together guarantee that centralized execution at p0 is globally optimal. First, the cost of centralized execution at p0 is no worse than any solution that assigns some qubits entirely to QCs in P ′ with no movement between p0 and P ′ : 1 X g cp0 csp0 + cep0 + |Q| g∈G 1 X ≤ min′ csp + cep + min cgp , (31) p∈P p∈P ′ |Q| g∈G
where the LHS is the per-qubit cost of centralized execution at p0 (leasing plus average gate execution cost), and the RHS is the minimum per-qubit leasing cost over all QCs in P ′ plus the average per-gate minimum execution cost over all QCs in P ′ (noting that different gates may be executed at different QCs in P ′ in the optimal solution).
Second, the minimum movement cost between p0 and any QC in P ′ exceeds the maximum per-qubit savings achievable by moving a qubit from p0 to some QC in P ′ :
min min(d(p0 , p), E(p0 , p)) > h + i + 1 X max′ csp0 + cep0 − csp + cep max′ cgp0 − cgp , + p∈P p∈P |Q| p∈P ′
g∈G
(32)
where the first term on the RHS is the maximum per-qubit leasing cost saving from moving a qubit to the cheapest QC in P ′ , and the second term is the average per-gate execution cost saving from running each gate at its cheapest QC in P ′ . Intuitively, there are two types of potentially cheaper solutions to rule out: (i) Hybrid solutions with no movement, in which some qubits are processed entirely at p0 and others entirely at QCs in P ′ with no inter-QC movement. Condition (31) rules these out by ensuring that the per-qubit-and-gate cost at p0 is no worse than the best achievable by splitting execution across P ′ , accounting for the fact that different gates may be run at different QCs in P ′ . (ii) Hybrid solutions with movement, in which qubits are moved between p0 and QCs in P ′ to exploit lower costs there. Condition (32) rules these out by ensuring that the movement cost exceeds the combined leasing and gate execution cost savings from such movement. Together, (31) and (32) guarantee that centralized execution at p0 is globally optimal. 2) Necessary Conditions for Optimality of Distributed Solution: We now present multiple conditions, N1 to N3, each of which is necessary for a distributed solution to outperform pure centralization at p0 . These conditions are stated under the qubit location assumptions of Remark 2. Condition N1 (Cost Advantage From Partial Distribution): There exists at least one QC p ∈ P ′ and gate g ∈ G such that the total cost of executing g at p– including the leasing cost at p, the round-trip movement cost from p0 to p and back, and the gate execution cost at p– is strictly less than the total cost of executing g at p0 including its leasing cost:
cgp + (csp + cep ) + 2 · min(d(p0 , p), E(p0 , p)) < cgp0 + (csp0 + cep0 ). (33) Intuitively, for any distributed solution to be beneficial, there must exist at least one gate g and QC p ∈ P ′ such that executing g at p (including the leasing cost at p and paying for the round-trip movement of the operand qubits from p0 to p and back) is cheaper than executing g at p0 (including its leasing cost). The round-trip movement is necessary because, by Remark 2, all qubits start and end at p0 . Condition N2 (Sufficient Savings From Distribution): There exists a subset of gates G′ ⊆ G and an assignment of these gates to QCs in P ′ such that the total savings from executing G′ at QCs in P ′ instead of p0 exceed the total costs incurred
10
by doing so: X g∈G′
cgp0 − min′ cgp p∈P X
> +
X
+ (csp0 + cep0 ) q∈Q(G′ )
2 · min′ min(d(p0 , p), E(p0 , p))
q∈Q(G′ )
X
p∈P
(csp + cep ) · |Qp |,
(34)
p∈P ′
S where Q(G′ ) = g∈G′ Og is the set of qubits involved in the gates in G′ ,Sand Qp ⊆ Q(G′ ) denotes the qubits assigned to QC p with p∈P ′ Qp = Q(G′ ). Intuitively, the LHS is the total savings from running gates G′ at cheaper QCs in P ′ instead of p0 , plus the leasing cost savings at p0 for the qubits in Q(G′ ) that are moved away from p0 . The RHS is the total round-trip movement cost for the qubits in Q(G′ ) (since by Remark 2 they must return to p0 ) plus the leasing costs at the QCs in P ′ where those qubits are processed. For a distributed solution to be beneficial, the savings must exceed these costs. Condition N3 (Network Capacity Requirement): The network must have sufficient aggregate capacity to store and execute at least one gate: X min(sp , ep ) ≥ min |Og |. (35) g∈G
p∈P ′
Intuitively, the network must be able to store and process at least the operand qubits of the gate with the fewest operands in the circuit. Without this minimal capacity, no distributed execution is possible regardless of cost considerations. 3) Necessary and Sufficient Condition: For the restricted case where all gate execution costs are identical (cgp = cg for all p, g), we now provide a necessary and sufficient condition for the centralized solution (static allocation of all qubits to p0 ) to be optimal. Theorem 3. Suppose cgp = cg for all p, g, and that the following condition holds: (36) csp0 + cep0 ≤ min′ csp + cep , p∈P
which ensures that p0 is the cheapest QC for qubit storage and execution, so that the optimal solution necessarily stores at least one qubit at p0 . Under this condition, the centralized solution at p0 is optimal if and only if h i min′ (csp + cep ) − (csp0 + cep0 ) + 2 min(d(p0 , p), E(p0 , p)) ≥ 0.
p∈P
(37) ′
The condition in (37) states that for every QC p ∈ P , the additional per-qubit leasing cost at p compared to p0 , plus the round-trip movement cost, must be non-negative. If this holds, moving any qubits to P ′ cannot reduce total cost, making centralized execution optimal. Conversely, if some QC in P ′ has sufficiently lower leasing costs to offset movement costs (making the expression negative), then partial distribution becomes beneficial. Proof of Theorem 3: With homogeneous gate costs (cgp = g c for all p, g), gate execution costs are identical regardless of where gates execute, so the only potential cost savings from
partial distribution can come from reduced per-qubit leasing costs. Condition (36) ensures that p0 has the lowest per-qubit leasing cost among all QCs. Therefore, in any cost-minimizing solution, it is never beneficial to store all qubits exclusively at QCs in P ′ while leaving p0 unused; the optimal solution necessarily stores at least one qubit at p0 . For any qubit q to benefit from moving to some QC p ∈ P ′ , the leasing cost savings at p must exceed the round-trip movement cost: (csp0 + cep0 ) − (csp + cep ) > 2 min(d(p0 , p), E(p0 , p)). The factor of 2 accounts for round-trip movement, i.e., for moving the qubit from p0 to p, and eventually returning to p0 (since p0 stores at least one qubit, there must be gates executed at p0 , requiring qubits to return). Rearranging, centralized execution at p0 is optimal if and only if no QC in P ′ offers sufficient cost advantage: (csp +cep )−(csp0 +cep0 )+2 min(d(p0 , p), E(p0 , p)) ≥ 0, ∀p ∈ P ′ . Taking the minimum over all p ∈ P ′ gives condition (37). 4) Computational Complexity of Verification: Verification of the sufficient conditions S1-S4 and necessary conditions N1-N3 involves computing cost differences and capacities in ∗ O(|P | · |G|) time, computing Ccentralized via topological sort ∗ in O(|G| + |E|) time, computing the lower bound Cisolated in O(|P |·|G|) time, and gate availability matrix checks in O(|P |· |G|) time. The total complexity is O(|P |·|G|+|E|). However, since the JQLQCD problem is NP-complete, this verification is significantly more efficient than determining if a distributed solution is optimal without using the necessary or sufficient conditions and by solving the full ILP. Algorithm 1 provides a practical decision procedure that leverages these sufficient and necessary conditions to avoid expensive ILP solving when centralized execution is provably optimal. Algorithm 1 Verification of Sufficient and Necessary Conditions 1: Input: Instance with p0 (unlimited QC), P ′ (limited QCs) ∗ 2: Compute Ccentralized via gate scheduling on p0 ∗ 3: Compute lower bound Cisolated for execution on P ′ only 4: if any of S1–S4 holds then return Optimal centralized solution 5: else if any of N1–N3 fails then return Optimal centralized solution 6: elsereturn Solve full ILP 7: end if 5) Example: We now provide an example in which the centralized solution is optimal. Suppose p0 has csp0 = cep0 = 0 (free unlimited capacity), P ′ = {p1 , p2 } with cspi = cepi = 10, communication costs d(p0 , pi ) = E(p0 , pi ) = 50 for i ∈ {1, 2}, and all gate costs are identical at cgp = 1. We now show that Condition S2 holds. First, we verify (26). We have ∆Cgate = 0 since all gate costs are identical, and + ∆Clease = max′ (csp0 + cep0 ) − (csp + cep ) p∈P
= max(0 − 20, 0)+ = 0,
11
since the leasing costs at P ′ are higher than at p0 . So, condition (26) becomes min(50, 50) = 50 > 0 + 0 = 0, which is true. This confirms that hybrid solutions involving movement between p0 and P ′ are not cost-effective. We now verify (27). Note that ∗ opt Ccentralized = 0 · |Q| + 0 · |Q| + |G| · 1 + β · Tmax opt = |G| + β · Tmax , ∗ Cisolated ≥ (csp1 + cep1 ) · min(|Q|, min(sp1 , ep1 )) + (csp2 + cep2 ) · min(|Q|, min(sp2 , ep2 )) + |G| · 1
(10). Given such an assignment and schedule, the minimum sufficient leasing quantities are X rpsi = max xq,pi ,t , i ∈ {1, . . . , kmin }, (39) t∈T
rpei = max t∈T
For |Q| ≥ 1, ∗ opt ∗ Cisolated ≥ 20 + |G| > |G| + β · Tmax = Ccentralized , opt ≤ 20, which where the last inequality holds when β · Tmax
is satisfied, e.g., when β = 0 or when the circuit is shallow opt enough that Tmax ≤ 20 β . Since both parts of Condition S2 are satisfied, the centralized solution is optimal. B. Case 2: Homogeneous QCs with Zero Movement Cost Problem Setting: All QCs are identical (sp = s, ep = e, csp = cs , cep = ce , cgp = cg , Ap,g = 1 for all p, g), and d(p′ , p) = E(p′ , p) = 0 for all p′ ̸= p. Solution Strategy: Movement is free, so qubits can be relocated without cost. The optimal strategy depends on the weight β of the makespan term in (1). In Sections V-B1 and V-B2, we consider the cases in which β = 0 and β > 0, respectively. 1) When β = 0 (Cost Minimization Only): Since all QCs have identical costs and movement is free, minimizing the total leasing cost requires minimizing the number of QCs used. The optimal strategy is to use the minimum number of QCs necessary to satisfy the capacity constraints. The minimum number of QCs needed is determined by both storage and execution capacity constraints: |Q| maxt |{q : executing at t}| kmin = max , , s e (38) where the first term ensures sufficient storage capacity across all QCs and the second term ensures sufficient execution capacity for the peak execution demand. An optimal solution is to select any kmin QCs from P (all choices are optimal since the QCs are identical), say QCs {p1 , p2 , . . . , pkmin }, and set rps = rpe = 0 for all p ∈ / {p1 , . . . , pkmin }. For the selected QCs {p1 , . . . , pkmin }, the optimal values of rpsi and rpei are not fixed in advance but depend on the specific assignment of qubits and gates to QCs and their schedule over time. In general, any feasible assignment of qubits to the kmin selected QCs and gate schedule is optimal when β = 0, provided it respects the capacity constraints (9) and
X
zq,pi ,t ,
i ∈ {1, . . . , kmin },
(40)
q∈Q
i.e., the storage (respectively, execution) leasing at each QC pi equals the peak number of qubits stored (respectively, actively executing) at pi over all time slots, ensuring no over-leasing occurs. The optimal total cost is ∗ Cβ=0 =
= 20 · min(|Q|, min(sp1 , ep1 )) + 20 · min(|Q|, min(sp2 , ep2 )) + |G|.
q∈Q
kX min
X g cs · rpsi + ce · rpei + c ,
i=1
(41)
g∈G
where the leasing terms are minimized by choosing the assignment and schedule that minimize the peak storage and execution usage at each QC. Since all QCs are identical and cs , ce are the same for all QCs, the total leasing cost satisfies kX min
cs · rpsi + ce · rpei ≥ cs · |Q|
i=1
+ ce · max |{q : executing at t}|, t
(42) with equality achievable when qubits and gates are distributed such that the peak storage and execution loads are spread as evenly as possible across the kmin QCs. Intuitively, exactly kmin QCs are used for the following reason. Using fewer than kmin QCs violates capacity constraints and hence is infeasible. Using more than kmin QCs increases the total leasing cost without reducing it when β = 0, since the total storage and execution requirements are fixed by the circuit and do not decrease by spreading them across more QCs. We now explain why multiple optimal solutions exist. Since all QCs are identical and the movement cost is zero, there | are k|P optimal choices of which kmin QCs to use. For min each such choice, any feasible assignment of qubits to the selected QCs and any feasible P gate schedule achieves the same total gate execution cost g∈G cg , and the total leasing cost depends only on the peak storage and execution loads induced by the assignment and schedule. Hence, the optimal solution is not unique, and any assignment and schedule that minimizes the peak loads at each selected QC is optimal. 2) When β > 0 (Makespan Matters): The optimal solution trades off leasing cost against makespan by distributing gates across multiple QCs to enable parallel execution. Since all QCs are identical and movement is free, the optimal number of active QCs k ∗ is the solution to ( k X ∗ k = argmin cs · rpsi (k) + ce · rpei (k) k∈{kmin ,...,|P |}
i=1
) + β Tmax (k) ,
(43)
P s where rP = maxt∈T q xq,pi ,t and rpei (k) = pi (k) maxt∈T q zq,pi ,t are the optimal leasing quantities at QC pi
12
under the best feasible assignment and schedule using k QCs, and Tmax (k) is the minimum achievable makespan using k QCs. Both rpsi (k), rpei (k), and Tmax (k) depend on the specific gate assignment and qubit placement chosen for k QCs, and need not correspond to an equal distribution of qubits or gates across QCs. In general, finding the optimal assignment and schedule for a given k requires solving a scheduling subproblem, and Tmax (k) is determined by both the circuit’s critical path length and the available parallelism. Since the leasing cost and makespan trade off against each other as k varies– using more QCs can reduce makespan but increases total leasing cost– the optimal k ∗ is found by evaluating the above objective over all feasible k ∈ {kmin , . . . , |P |}. In the general case in which the circuit has limited parallelism or heterogeneous gate dependencies, Tmax (k) may not decrease with k beyond a certain point (e.g., when the critical path dominates), and the optimal leasing quantities may be highly asymmetric across QCs due to uneven gate distributions. In such cases, the full ILP given in Section III-B must be solved to find both the optimal k ∗ and the corresponding optimal assignment and schedule. 3) Characterization of All Optimal Solutions: A solution is optimal if and only if the following conditions hold: The solution satisfies minimal leasing, wherein for each QC p, P P rps = maxt q xq,p,t and rpe = maxt q zq,p,t , ensuring that no over-leasing occurs. The gate schedule achieves optimal ∗ for the chosen set of active QCs, representing makespan Tmax the minimum possible execution time. Finally, optimal QC selection ensures that the number of active QCs k minimizes the total cost as specified in the formula above. Since the movement cost is zero, the specific assignment of qubits and gates to QCs is irrelevant, as long as capacity constraints are satisfied and makespan is minimized. Note that the assumption d(p′ , p) = E(p′ , p) = 0 we have made in Case 2 means that movement has zero cost, but does not necessarily imply instantaneous movement. Two interpretations are possible: (i) Zero cost, zero time where movement is both free and instantaneous, allowing qubits to be relocated between QCs without affecting the makespan; in this case, the optimization focuses purely on minimizing leasing costs, while achieving the best possible makespan through parallelization. (ii) Zero cost, non-zero time assumes that movement is free, but takes time τmove > 0, requiring the makespan calculation to crit account for movement delays as Tmax ≥ Tmax + nmoves · τmove , where nmoves is the number of qubit movements in the solution. We have adopted interpretation (i): movement is instantaneous (τmove = 0). Under this assumption, there are exponentially many optimal solutions that differ only in which QCs are used and how work is distributed among them, but all achieve the same total cost. Note that if movement takes non-zero time, then even with zero cost, the problem becomes more constrained, as the optimizer must minimize the number of movements to reduce makespan, even though movement cost does not contribute to the objective function. 4) Conditions for the Optimality of Load Balancing: In general, load balancing may not be optimal due to the following reason. Load balancing across all |P | QCs minimizes the makespan, but increases the leasing cost because more
QCs must lease resources. When β is small (cost-dominant regime), concentrating the load on fewer QCs is cheaper. A sufficient condition for load balancing across all |P | QCs to be optimal is that for all k ∈ {1, . . . , |P | − 1}, |P | X
cs · rpsi (|P |) + ce · rpei (|P |) + β · Tmax (|P |)
i=1
<
k X
cs · rpsi (k) + ce · rpei (k) + β · Tmax (k),
(44)
i=1
where rpsi (k) and rpei (k) are the optimal peak storage and execution leasing quantities at QC pi under the best feasible assignment and schedule using k QCs, and Tmax (k) is the minimum achievable makespan using k QCs. Both quantities depend on the specific circuit structure, gate dependencies, and qubit assignments, and must in general be evaluated by solving the scheduling subproblem for each k. This condition must be verified for each k, requiring O(|P |) comparisons. We now provide a cost formula for the special case in which the circuit is perfectly parallelizable, meaning its gates can be partitioned into k independent groups of equal total duration executable simultaneously on k QCs with no interQC dependencies. In this case, the cost of using k QCs is given by Cost(k) =
k X
cs · rpsi (k) + ce · rpei (k)
i=1
+
X g∈G
crit Wtotal , c + β · max Tmax , k g
(45)
P crit where Wtotal = g∈G τg is the total work and Tmax is the critical path length. The max(·) term reflects the fact that Tmax (k) is bounded below by both the critical path length (due to sequential dependencies that cannot be parallelized) and Wktotal (the average work per QC even with perfect load balancing). For circuits that do not satisfy the perfect parallelizability assumption, (45) provides only a lower bound on the true cost, and the full ILP given in Section III-B must be solved to find the optimal solution. C. Case 3: Chain Topology with Sequential Gates 1) Single-Qubit Sequential Gates: Problem Setting: The circuit is a linear chain of singlequbit gates g1 , g2 , . . . , g|G| on one qubit q, with precedence constraints gi ≺ gi+1 for all i ∈ {1, . . . , |G| − 1}, and gate durations τg = 1 for all g ∈ G. The QCs form an arbitrary network topology. Note that this special case, while theoretically tractable, represents only a very limited class of quantum transformations (arbitrary single-qubit unitaries) and hence does not capture the complexity of realistic quantum circuits. Solution: This problem reduces to finding a minimum-cost path in a time-expanded graph G, where each node (p, i) represents the qubit being at QC p after executing gate gi , and each edge represents either staying at the current QC to execute the next gate or moving to another QC before executing it. The cost of a stay edge from (p, i) to (p, i + 1) is
13
g
cpi+1 (gate execution cost at p). The cost of a move edge from g (movement (p, i) to (p′ , i+1) is min(d(p, p′ ), E(p, p′ ))+cpi+1 ′ cost plus gate execution cost at p′ ), plus the one-time leasing cost csp′ + cep′ if p′ has not been used before. Theorem 4. The shortest path in G corresponds to an optimal solution to the special case of the JQLQCD problem in which the quantum circuit is a single-qubit sequential circuit with unit-duration gates. Proof: Any feasible solution specifies a sequence of QC locations (p0 , p1 , . . . , p|G| ) where pi is the QC where gate gi executes, which naturally corresponds to a path (p0 , 0) → (p1 , 1) → · · · → (p|G| , |G|) in G. The total cost of a solution is X
(csp + cep ) +
|G| X
cgpii
i=1
p∈Pused |G|
+
X
1{pi ̸=pi−1 } · min(d(pi−1 , pi ), E(pi−1 , pi )),
(46)
i=1
where Pused = {pi : i ∈ {0, 1, . . . , |G|}} is the set of distinct QCs used, with leasing costs paid once per QC. Since G is a DAG with non-negative edge costs, Dijkstra’s algorithm (or DP) finds the shortest path, which corresponds to the minimum-cost solution when edge costs properly account for one-time leasing charges as described in Algorithm 2. Any other solution corresponds to a longer path with higher cost. Algorithm 2 Minimum-Cost Path for Sequential Single-Qubit Gate Execution 1: Input: Set of QCs P , gates G = {g1 , . . . , g|G| }, costs csp , cep , cgp , d(p, p′ ), E(p, p′ ) 2: Output: Minimum-cost execution path 3: Construct the DAG G = (V, E): 4: Nodes: V = {(p, i) : p ∈ P, i ∈ {0, 1, . . . , |G|}} 5: where (p, i) means the qubit is at QC p after executing gate gi (i = 0 is the initial state) 6: Initialize edges E = ∅, leasing costs L(p) = csp + cep for each p ∈ P 7: for i = 0 to |G| − 1 do 8: for each (p, i) ∈ V do g 9: Stay edge: Add (p, i) → (p, i + 1) with cost cpi+1 ′ ′ 10: for each p ∈ P, p ̸= p do 11: Move edge: Add (p, i) → (p′ , i + 1) with cost g ′ min(d(p, p ), E(p, p′ )) + cpi+1 ′ 12: end for 13: end for 14: end for 15: Apply Dijkstra’s algorithm or DP on G, initializing each starting node (pinit , 0) with cost cspinit + cepinit , and adding the one-time leasing cost csp′ + cep′ the first time any QC p′ is visited along a path 16: return Minimum-cost path and its total cost The nodes of G are pairs (p, i) with p ∈ P and i ∈ {0, . . . , |G|}, giving O(|P |·|G|) nodes. Each node has at most
|P | outgoing edges, giving O(|P |2 · |G|) edges in total. The one-time leasing costs are tracked along each path during the shortest-path computation. Using Dijkstra’s algorithm with a Fibonacci heap, the complexity is O(|P |2 · |G| · log(|P | · |G|)), or O(|P |2 · |G|) using DP. 2) Multi-Qubit Sequential Gates: Problem Setting: The circuit is a linear chain of gates g1 , g2 , . . . , g|G| with precedence constraints gi ≺ gi+1 for all i ∈ {1, . . . , |G| − 1} and gate durations τg = 1 for all g ∈ G. Each gate gi operates on a subset of qubits Ogi ⊆ Q with |Ogi | ≥ 1. QCs form an arbitrary network topology. This is a generalization of the scenario considered in Section V-C1 and encompasses realistic quantum circuits such as sequential quantum Fourier transforms (QFTs), layered variational quantum circuits, CNOT ladders, and quantum error correction (QEC) syndrome extraction circuits [70]. Solution: The problem still reduces to shortest path finding, but the state space must track the locations of all qubits involved in each gate. Algorithm 3 extends Algorithm 2 to handle multiple operand qubits per gate. The nodes of G are pairs (σ, i) where σ ∈ Config(Ogi ) and i ∈ {0, . . . , |G|}, giving O(|P |kmax · |G|) nodes, where kmax = maxi |Ogi |. Each node has at most |P | outgoing edges (one per target QC for the next gate), giving O(|P |kmax +1 ·|G|) edges. Using DP, the time complexity is O(|P |kmax +1 · |G|) and space complexity is O(|P |kmax · |G|). For circuits with at most two-qubit gates (kmax ≤ 2), this gives O(|P |3 · |G|) time, which is polynomial and tractable for moderate-sized networks. Theorem 5. The shortest path in G corresponds to an optimal solution of the special case of the JQLQCD problem in which there is a sequential multi-qubit circuit with unit-duration gates. Proof: Any feasible solution specifies a sequence of qubit configurations (σ0 , σ1 , . . . , σ|G| ), which corresponds to a unique path in G. The total cost equals the sum of edge costs along the path, including incremental leasing costs accumulated as new qubits are assigned to QCs at each stage. Since G is a DAG with non-negative edge costs, DP finds the optimal path. Some practical optimization strategies are as follows. Locality exploitation prunes configurations where qubits are unnecessarily dispersed if the circuit has qubit locality, meaning qubits in consecutive gates overlap significantly. Greedy initialization uses a greedy heuristic to identify a good initial path, then performs local search around this solution. Capacity-aware pruning eliminates configurations that violate capacity constraints early to reduce the state space. D. Case 4: Independent Subcircuits with Partitioned Resources Problem Setting: The circuit decomposes into k independent subcircuits {C1 , C2 , . . . , Ck } with no shared qubits. Different subcircuits C1 , . . . , Ck operate on disjoint qubit sets Q1 , . . . , Qk , respectively. This problem represents a significant generalization beyond the k = 1 case, and we defer the full treatment of
14
Algorithm 3 Minimum-Cost Path for Multi-Qubit Sequential Gate Execution 1: Input: Gates G = {g1 , . . . , g|G| }, QCs P , qubit operand sets Ogi , costs csp , cep , cgp , d(p, p′ ), E(p, p′ ) 2: Output: Minimum-cost execution path 3: Construct DAG G = (V, E): 4: Nodes: V = {(σ, i) : σ ∈ Config(Ogi ), i ∈ {0, 1, . . . , |G|}} 5: where Config(Ogi ) = {σ : Ogi → P } is the set of all mappings from qubits in Ogi to QCs, with |Config(Ogi )| = |P ||Ogi | , and (σ, i) represents the qubit configuration after executing gate gi 6: Initialize edges E = ∅ 7: for i = 0 to |G| − 1 do 8: for each state (σ, i) ∈ V do 9: for each p ∈ P with |Ogi+1 | ≤ min(sp , ep ) and Ap,gi+1 = 1 do 10: Define σ ′ : Ogi+1 → P by σ ′ (q) = p for all q ∈ Ogi+1 11: Compute movement cost: MoveCost(σ, σ ′ ) = P q∈Ogi+1 1{σ(q)̸=p} · min(d(σ(q), p), E(σ(q), p)) 12: Compute incremental leasing cost: For each QC p, let nprev (p) be the number of qubits leased at p before stage i + 1 and nnew (p) be the number of qubits in Ogi+1 assigned to P p under σ ′ ; the incremental leasing cost is: LeaseCost = p∈P max(0, nnew (p) − nprev (p)) · (csp + cep ) g 13: Compute edge cost: c = LeaseCost + cpi+1 + ′ MoveCost(σ, σ ) 14: Add edge (σ, i) → (σ ′ , i + 1) with cost c to E 15: end for 16: end for 17: end for 18: Apply DP to find minimum-cost path from initial configuP ration (σ0 , 0) with initial leasing cost p∈P ninit (p)·(csp + cep ), where ninit (p) is the number of qubits in Og0 initially at p, to any final configuration (σf , |G|) 19: return Minimum-cost path
the k > 1 case until future work. For completeness, we provide a decomposition-based approach, which is described in Algorithm 4. The decomposition step, which identifies the connected components of the qubit interaction graph H = (Q, EH )– where Q is the set of qubits and EH is the set of edges with (q, q ′ ) ∈ EH if there exists a gate in G that operates on both qubits q and q ′ – has complexity O(|Q| + |EH |) using depth-first search [58]. Here, |Q| is the number of qubits and |EH | ≤ |G| is the number of edges in the qubit interaction graph. The total complexity of Algorithm 4 is O(|Q| + |EH |) for the decomposition step, plus the sum of complexities for solving the JQLQCD problem for each subcircuit. This approach provides a feasible solution, but it may not be optimal if subcircuits can share QC resources efficiently.
Algorithm 4 Decomposition-Based Approach for Circuit Partitioning and Assignment 1: Input: Gate set G, qubit set Q, set of QCs P 2: Output: Assignment of circuit components to QCs 3: Construct the qubit interaction graph H = (Q, EH ), where (q, q ′ ) ∈ EH if some gate in G operates on both q and q ′ 4: Identify connected components {C̃1 , C̃2 , . . . , C̃m } of H using depth-first search 5: Note: m is the number of connected components found (may differ from k in Section V-D) 6: Assign each component C̃i to QCs using a bin-packing heuristic [71], e.g., first-fit decreasing by resource demand 7: for each component C̃i do 8: Let Pi be the set of QCs assigned to component C̃i 9: if |Pi | = 1 then 10: Solve the subproblem for C̃i using our method for Case 1 (Section V-A) 11: else 12: Solve the JQLQCD problem for circuit C̃i and set of QCs Pi 13: end if 14: end for 15: return Combined solution from all subproblems
E. Case 5: Infinite Resources with Only Makespan Minimization Problem Setting: For all p and g, sp = ep = ∞, csp = cep = g cp = 0, and β > 0. Additionally, we assume that migration ′ ′
and teleportation costs are zero, i.e., d(p , p) = E(p , p) = 0 for all p′ , p ∈ P , and that qubit movement is instantaneous, i.e., τmigrate (p′ , p) = τteleport (p′ , p) = 0 for all p′ , p ∈ P . Under these assumptions, qubits can be freely relocated between QCs without incurring any cost or time overhead, and hence the objective function in (1) reduces to β · Tmax , which is proportional to the makespan. Solution: Since all resources are free, infinite, and movement is instantaneous, the only constraint on gate scheduling is the circuit’s precedence structure. The problem therefore reduces to the classical problem of multiprocessor scheduling with precedence constraints, P |prec|Cmax [55], [56], [57], described in Section IV-A. The circuit’s execution dependencies can be represented by a DAG in which there is a node corresponding to each gate g ∈ G, and a directed edge g1 → g2 exists if gate g1 must complete before g2 can begin, i.e., g1 ≺ g2 . This occurs when g2 operates on qubits modified by g1 . The graph is acyclic because gates execute in temporal order without circular dependencies. The optimal makespan is determined by the critical path in the circuit DAG, which is the longest path from any source gate to any sink gate, accounting for gate durations: X opt Tmax = max τg . (47) paths π in DAG
g∈π
Algorithm 5 computes the critical path length using DP on the DAG and produces a gate assignment that achieves the optimal makespan. Since resources are infinite and free, and
15
movement is instantaneous, gates can be distributed across as many QCs as needed to maximize parallelism: independent gates (those with no precedence relation) can be assigned to different QCs and executed simultaneously, while dependent gates must respect the ordering imposed by the precedence constraints. The complexity of Algorithm 5 is O(|G| + |E|), where |E| is the number of precedence edges in the circuit DAG. Algorithm 5 Critical Path Scheduling for Gate Assignment 1: Input: Gates G with precedence constraints, durations τg , set of QCs P 2: Output: Gate assignment to QCs with optimal makespan 3: Step 1: Compute critical path length 4: Perform topological sort on gates G 5: for each gate g in topological order do 6: Compute earliest start time: 7: L(g) = maxg′ :g′ ≺g L(g ′ ) + τg′ , 8: where L(g) is the earliest start time of gate g 9: end for opt 10: Compute optimal makespan Tmax = maxg∈G (L(g) + τg ) 11: Step 2: Assign gates to QCs 12: Assign independent gates (those with no precedence relation between them) to distinct QCs to enable parallel execution, respecting precedence constraints; apply list scheduling [68], [69] to produce a valid schedule achievopt ing Tmax 13: return Gate assignment and schedule For P |prec|Cmax , finding the optimal makespan is strongly NP-hard in general [55]. However, the critical path provides a lower bound, and various polynomial-time algorithms achieve constant-factor approximations [61]. When |P | ≥ |Q| (enough QCs to hold all qubits simultaneously) and movement is opt instantaneous, the critical path lower bound Tmax in (47) is achievable, making the problem optimally solvable in polynomial time. This bound is tight when the circuit has sufficient parallelism and |P | is large enough. F. Case 6: Tree-Structured Circuit with Arbitrary QC Network Problem Setting: The circuit has a tree structure, meaning that the gate dependency graph forms a tree. Since each node in a tree (except the root) has exactly one parent and each node has at most one child, a tree-structured gate dependency graph must in fact be a linear chain: g1 → g2 → · · · → g|G| , where each gate gi (except the last) has exactly one successor gi+1 , and each gate gi (except the first) has exactly one predecessor gi−1 . Note that a gate can still operate on multiple qubits (e.g., a two-qubit CNOT gate), but the dependency ordering among gates must form this linear chain structure. We make the following assumptions. The leasing costs csp and cep , gate execution costs cgp , migration costs d(p′ , p), and teleportation costs E(p′ , p) are arbitrary non-negative values. Qubit movement is instantaneous, i.e., τmigrate (p′ , p) = τteleport (p′ , p) = 0 for all p′ , p ∈ P , so that movement does not contribute to the makespan. All QCs have infinite storage and execution capacity: sp = ep = ∞ for all p ∈ P . The
makespan weight is β = 0, so the objective function (1) reduces to minimizing only the leasing cost, gate execution cost, and movement cost. Under these assumptions, since all QCs have infinite P capacity, the optimal leasing P quantities are rps = maxt∈T q xq,p,t and rpe = maxt∈T q zq,p,t , i.e., the peak number of qubits stored and actively executing at each QC. The QC network can have an arbitrary topology– QCs can be connected in any graph structure (mesh, star, fully connected, etc.). Note that Case 6 is equivalent to Case 3 (Section V-C) under the additional assumption of β = 0 and instantaneous movement, since the tree structure reduces to a linear chain. The DP approach of Algorithm 6 provides an alternative formulation that makes the optimal substructure explicit. Algorithm 6 describes a DP approach that processes gates in post-order traversal (which coincides with reverse sequential order for a linear chain) to compute optimal costs bottom-up. Algorithm 6 DP for Linear-Chain Circuit Optimization 1: Input: Circuit with linear-chain gate dependency g1 → g2 → · · · → g|G| , set of QCs P with leasing costs csp , cep , gate costs cgp , movement costs d(p′ , p) and E(p′ , p) for all p, p′ ∈ P 2: Output: Optimal cost C ∗ and gate assignment to QCs 3: Initialization: 4: Initialize Cost(g, p) table for all gates g and QCs p 5: DP (processed in reverse order g|G| , g|G|−1 , . . . , g1 ): 6: for each gate g in reverse sequential order do 7: for each p ∈ P do 8: if g = g|G| (last gate, no successor) then 9: Cost(g, p) ← cgp + csp + cep 10: else 11: Let g ′ be the unique successor of g 12: Cost(g, p) ← cgp + csp + cep + minp′′ ∈P [Cost(g ′ , p′′ ) + min(d(p, p′′ ), E(p, p′′ ))] 13: end if 14: end for 15: end for 16: Compute optimal cost: 17: C ∗ ← minp∈P Cost(g1 , p) 18: Reconstruction: 19: Backtrack through the DP table to determine: 20: - Which QC executes each gate 21: - Which qubits move between which QCs 22: - Whether to use migration or teleportation for each movement 23: return C ∗ and optimal assignment
Theorem 6. For circuits with linear-chain gate dependencies, infinite QC capacities, instantaneous qubit movement, β = 0, and an arbitrary QC network topology, Algorithm 6 computes the optimal solution. Proof: We prove the result by induction on the gates processed in reverse sequential order.
16
Base case: For the last gate g|G| with no successor, the minimum cost of executing g|G| at QC p is Cost(g|G| , p) = cgp + csp + cep ,
(48)
which is trivially optimal since there are no subsequent gates. Inductive step: Assume that Cost(g ′ , p′′ ) has been computed optimally for the unique successor g ′ of gate g and all QCs p′′ ∈ P . We claim that Cost(g, p) = cgp + csp + cep + min [Cost(g ′ , p′′ ) + MoveCost(p, p′′ )] (49) ′′ p ∈P
computes the optimal cost for executing gate g at QC p and all subsequent gates, where MoveCost(p, p′′ ) = min(d(p, p′′ ), E(p, p′′ )). Consider any feasible solution S for executing g and all its successors. It must specify the QC p where g executes and the QC p′′ where g ′ executes. The total cost is: C(S) = cgp + csp + cep + C(Sg′ ) + MoveCost(p, p′′ ),
(50)
where Sg′ is the subsolution for g ′ and all its successors. By the induction hypothesis, C(Sg′ ) ≥ Cost(g ′ , p′′ ). Therefore, C(S) ≥ cgp + csp + cep + Cost(g ′ , p′′ ) + MoveCost(p, p′′ ) ≥ cgp + csp + cep + min [Cost(g ′ , p′′ ) + MoveCost(p, p′′ )] ′′
A. Algorithm Design 1) QC Scoring Function: The key idea is to iteratively select QCs based on a composite score that balances leasing costs and communication overhead, and then allocate qubits until capacity is exhausted. For each QC p ∈ P , we define a selection score: csp + cep maxp′ ∈P (csp′ + cep′ ) AvgCommCost(p) , + αcomm · maxp′ ∈P AvgCommCost(p′ )
Score(p) = αlease ·
(51)
where αlease , αcomm ≥ 0 are weights with αlease + αcomm = 1, and AvgCommCost(p) measures the average communication cost from p to other QCs: AvgCommCost(p) =
X 1 |P | − 1 ′
min(d(p, p′ ), E(p, p′ )).
p ∈P \{p}
(52) Lower scores indicate more desirable QCs. The weights allow tuning based on the problem requirements: if circuits require frequent qubit movement, then high αcomm is used to prioritize well-connected QCs; otherwise, high αlease is used to prioritize cheap QCs. Algorithm 7 describes this greedy selection strategy; it iteratively chooses QCs in increasing order of score and assigns qubits to QCs based on the gate execution costs and affinity, as we now explain.
p ∈P
= Cost(g, p). Equality holds when Sg′ is optimal and p′′ is chosen optimally. The global optimal cost is C ∗ = minp∈P Cost(g1 , p). We now analyze the time and space complexity of Algorithm 6. Proposition 1. Under the assumption that each gate operates on at most kmax ≤ 2 qubits, Algorithm 6 has time complexity O(|G| · |P |2 ) and space complexity O(|G| · |P |). Proof: The DP table Cost(g, p) has |G|·|P | entries, giving space complexity O(|G| · |P |). For each gate g and each QC p, computing Cost(g, p) requires minimizing over all p′′ ∈ P , taking O(|P |) time. Summing over all gates and QCs gives total time complexity O(|G| · |P |2 ). VI. G REEDY A LGORITHM The special cases in Section V cover only a narrow class of practical scenarios. Real-world quantum circuits– including QFTs, variational quantum eigensolvers (VQEs), and QEC circuits [70]– exhibit DAG structures where gates have multiple predecessors and successors, violating the tree property required by Case 6 (Section V-F). For such general circuits, exact solution of the ILP formulation of the JQLQCD problem (Section III-B) is computationally prohibitive for large instances, since the problem is NP-complete (see Section IV). Hence, in this section, we present a greedy heuristic for solving the general JQLQCD problem.
Algorithm 7 Greedy QC Selection and Qubit Allocation 1: Input: Circuit with qubits Q, gates G, QCs P , capacities sp , ep , costs 2: Output: Initial qubit-to-QC assignment 3: Initialize: Pavail ← P , Qunassigned ← Q 4: Compute Score(p) for all p ∈ P using (51) 5: Sort QCs in ascending order of score: p1 , p2 , . . . , p|P | 6: for each QC pi in sorted order do 7: nassign ← min(spi , epi , |Qunassigned |) 8: Select nassign qubits from Qunassigned one at a time greedily, i.e., in increasing order of QubitScore(q, pi ) given in (53), recomputing scores after each selection since Affinity(q, pi ) changes as qubits are assigned 9: Assign selected qubits to pi 10: Qunassigned ← Qunassigned \ {selected qubits} 11: if Qunassigned = ∅ then 12: break 13: end if 14: end for 15: return qubit-to-QC assignment 2) Qubit Selection Strategy: While assigning qubits to a selected QC p, we use a secondary greedy criterion as follows. For each unassigned qubit q, we compute QubitScore(q, p) =
X
cgp
g:q∈Og
minp′ ∈P cgp′
− λ · Affinity(q, p), (53)
17
where Affinity(q, p) equals the fraction of gate operands involving q that are already assigned to p:
Affinity(q, p) =
X |Og ∩ Qp | , |Og |
(54)
g:q∈Og
with Qp being the set of qubits already assigned to p and λ ≥ 0 a weight parameter. Lower qubit scores are preferred. The first term encourages assignment of qubits to a QC p where their gates execute cheaply. The second term (subtracted) rewards co-location of qubits that interact frequently: a higher Affinity(q, p) lowers the score, making qubit q more attractive to assign to p, thereby reducing interQC communication. After each qubit is assigned to pi , the Affinity(q, pi ) values change for the remaining unassigned qubits, so QubitScore(q, pi ) must be recomputed before each subsequent selection.
Algorithm 8 Local Search Refinement 1: Input: Assignment obtained using greedy algorithm (Algorithm 7) 2: Output: Refined assignment 3: Compute total cost Ccurrent of initial assignment 4: repeat 5: Cbest ← Ccurrent 6: for each qubit q and QC pair (p, p′ ) where q is assigned to p do 7: if p′ has available capacity and Ap′ ,g = 1 for all gates g with q ∈ Og then 8: Tentatively reassign q from p to p′ 9: Compute new cost Cnew 10: if Cnew < Cbest then 11: Cbest ← Cnew 12: Record this move as best improvement 13: end if 14: Undo tentative reassignment 15: end if 16: end for 17: if best improvement found then 18: Apply best move 19: Ccurrent ← Cbest 20: end if 21: until no improving move found or iteration limit reached 22: return refined assignment
B. Complexity Analysis VII. N UMERICAL R ESULTS Computing the communication costs AvgCommCost(p) and scores Score(p) for all QCs p ∈ P requires O(|P |2 ) time, and sorting QCs takes O(|P | log |P |) time. For the qubit assignment step, consider the processing of a single QC pi . Up to nassign ≤ |Q| qubits are selected one at a time. Before each selection, QubitScore(q, pi ) must be recomputed for each remaining unassigned qubit q ∈ Qunassigned , since Affinity(q, pi ) changes after each qubit is assigned to pi . Recomputing QubitScore(q, pi ) for a single qubit q requires O(|G|) time (summing over all gates involving q). Since there are at most |Q| unassigned qubits and up to |Q| selections per QC, the qubit score evaluation for a single QC pi takes O(|Q|2 · |G|) time in the worst case. Summing over all |P | QCs, the total time for qubit score evaluation is O(|P | · |Q|2 · |G|). Hence, the overall time complexity of the greedy algorithm is
O |P |2 + |P | · |Q|2 · |G| .
(55)
C. Refinement via Local Search
The greedy assignment obtained using Algorithm 7 can be refined using local search, which is described in Algorithm 8.
In this section, we evaluate the performance of the proposed greedy algorithm (Algorithm 7) through extensive numerical experiments. We compare the greedy approach with simulated annealing (SA) [58], a metaheuristic that can find nearoptimal solutions to the ILP formulation, and polynomial-time algorithms that compute optimal solutions for special cases (Section V). Our evaluation focuses on two key metrics: solution quality measured by total cost as defined by the objective function (see (1)), and computational efficiency measured by execution time in seconds. A. Experimental Setup We generated diverse instances of the JQLQCD problem, with the characteristics shown in Table II, designed to represent realistic quantum computing scenarios. We used quantum circuits with varying numbers of qubits and gates, with gate types distributed as 60 % single-qubit and 40 % two-qubit gates, organized in a random DAG topology with average degree 2.5, and gate durations uniformly distributed between 1 and 5 time units. The table also specifies various parameters of the QC network, including the number of QCs, storage and execution capacities per QC, network topology, which is a random graph with edge probability 0.4, and various cost distributions for migration, teleportation, leasing, and gate execution. The gate availability is set such that each gate can execute on approximately 80 % of the QCs. We vary the makespan weight β to study the trade-off between cost and makespan. For each parameter configuration, we report the results obtained by averaging over 20 random instances.
18
Parameter Number of qubits Number of gates Gate types Circuit topology Gate durations Number of QCs Storage capacity Execution capacity Network topology Migration costs Teleportation costs Leasing costs Gate exec. costs Gate availability Makespan weight
Values/ Distribution |Q| ∈ {5, 10, 15, 20, 25, 30} |G| ∈ {10, 25, 50, 100, 150, 200} Single-qubit (60 %), two-qubit (40 %) Random DAG, avg. degree 2.5 Uniform[1, 5] time units |P | ∈ {2, 3, 4, 5, 6, 8, 10} sp ∼ Uniform{5, . . . , 15} qubits ep ∼ Uniform{3, . . . , 8} qubits Random graph, edge prob. 0.4 d(p′ , p) ∼ Uniform(5, 20) for connected QCs E(p′ , p) ∼ Uniform(10, 30) for connected QCs csp , cep ∼ Uniform(1, 5) cg p ∼ Uniform(0.5, 2.0) Ap,g = 1 w.p. 0.8 (80 % avg.) β ∈ {0, 0.1, 0.5, 1.0, 2.0, 5.0}
co-location cost P requirements,t increasing P the communication ′ t terms q,p′ ,p,t d(p′ , p)γq,p ′ ,p and q,p′ ,p,t E(p , p)wq,p′ ,p in (1). The makespan term βTmax in (1) may also increase for circuits with longer critical paths. While leasing costs remain fixed for a given QC allocation, the cumulative effect of growing gate execution and communication costs results in the approximately linear relationship between total cost and circuit size observed in Fig. 2. Cost vs. Circuit Size 1000
Simulated Annealing Greedy Algorithm
800
Total Cost
TABLE II T HE TABLE PROVIDES THE VALUES / DISTRIBUTION OF DIFFERENT PARAMETERS USED TO OBTAIN THE NUMERICAL RESULTS .
600 400 200 25
B. Algorithms
C. Results for General Problem Instances 1) Performance vs. Circuit Size: Fig. 2 shows the total cost (value of the objective function in (1)) as a function of the number of gates |G|, with |Q| = 20 qubits, |P | = 5 QCs, and β = 1.0. The greedy algorithm achieves costs within 8 − 15 % of SA across all circuit sizes. For larger circuits (|G| ≥ 100), the gap narrows to approximately 10 %, showing that the greedy approach scales well. Both algorithms exhibit approximately linear cost growth with circuit size. The total cost increases with the number of gates |G| for two First, the gate execution cost component P primary P reasons. g c u in the objective function in (1) grows g,p g∈G p∈P p linearly with |G| since each additional gate incurs some execution cost. Second, more gates typically require additional qubit movements among QCs to satisfy the gate operand
75
100
125
Number of Gates |G|
150
175
200
Fig. 2. The figure shows the total cost versus number of gates for the greedy algorithm and SA.
Fig. 3 compares the execution times for the same problem instances as for Fig. 2. The greedy algorithm is consistently 50 − 200× faster than SA. The greedy algorithm’s execution time grows approximately as O(|G|1.2 ), close to the theoretical O(|G|) bound, while SA’s execution time grows super-linearly at approximately O(|G|1.8 ). For the largest instances (|G| = 200), the greedy algorithm completes in less than 1 second, while SA requires over 100 seconds. Execution Time vs. Circuit Size Execution Time (seconds, log scale)
We evaluated and compared the performance of the following algorithms. 1) Greedy Algorithm: It was implemented as described in Algorithm 7 with parameters αlease = 0.5 and αcomm = 0.5 (balanced weighting), λ = 2.0 (moderate affinity weight), and 100 local search iterations (Algorithm 8). 2) Simulated Annealing [58]: The parameter values used were as follows: initial temperature T0 = 1000, geometric cooling schedule Tk+1 = 0.95 · Tk , 50 iterations per temperature, termination at temperature T < 0.01 or 10, 000 total iterations, and neighborhood moves consisting of random reassignment of one qubit to a different QC or the swapping of two qubits. 3) Optimal Algorithms: For the special cases studied in Section V, we used topological sort plus list scheduling for Case 1 (Section V-A), optimal k selection via exhaustive search over k ∈ {1, . . . , |P |} for Case 2 (Section V-B), and Dijkstra’s algorithm on the time-expanded graph for Case 3 (Section V-C). All algorithms were implemented in Python 3.9 and executed on a machine with an Intel Core i7-10700K CPU (8 cores, 3.8 GHz) and 32 GB RAM.
50
Simulated Annealing Greedy Algorithm
101
100
10 1 25
50
75
100
125
Number of Gates |G|
150
175
200
Fig. 3. The figure shows the execution time versus number of gates for the greedy algorithm and SA.
2) Performance vs. Number of QCs: Fig. 4 shows how the solution quality varies with the number of available QCs, with |Q| = 15 qubits, |G| = 75 gates, and β = 1.0. The cost decreases in the number of QCs due to increased parallelism opportunities, resulting in lower makespan. The rate of decrease diminishes beyond |P | = 6 QCs, which is due to limited parallelism in typical circuits. The greedy algorithm’s relative performance gap to SA remains consistent at 10 − 12 % across different values of |P |. Fig. 5 compares the execution times of the two algorithms for different values of the number of QCs, |P |, with |Q| = 15 qubits, |G| = 75 gates, and β = 1.0. SA’s execution time increases more rapidly than that of the greedy algorithm as the
19
Cost vs. Number of QCs Simulated Annealing Greedy Algorithm
280
Total Cost
260 240 220
as the complexity is determined primarily by the problem size rather than the optimization objective. SA shows a slight increase in the execution time for high values of β due to the increased complexity of balancing multiple objectives. The speedup ratio remains consistently around 100 − 120× across all values of β. Execution Time vs. Makespan Weight
2
3
4
5
6
7
Number of QCs |P|
8
9
10
Fig. 4. The figure shows the total cost versus number of QCs for the greedy algorithm and SA.
number of QCs increases. The greedy algorithm is 80 − 100× faster than SA.
Execution Time (seconds)
200
Simulated Annealing Greedy Algorithm
100 80 60 40 20 0
0
1
2
3
4
Makespan Weight
5
Execution Time (seconds)
Execution Time vs. Number of QCs Simulated Annealing Greedy Algorithm
100
Fig. 7. The figure shows the execution time versus makespan weight β for the greedy algorithm and SA.
80 60 40 20 0
2
3
4
5
6
7
Number of QCs |P|
8
9
10
Fig. 5. The figure shows the execution time versus number of QCs for the greedy algorithm and SA.
3) Performance vs. Makespan Weight β: Fig. 6 shows the total cost versus β, with |Q| = 15 qubits, |G| = 75 gates, and |P | = 5 QCs. At β = 0, the greedy algorithm performs within 8 % of SA. As β increases, both algorithms use more QCs and increase the number of qubits leased since they prioritize parallelization to reduce the makespan; this increases the leasing and movement costs. For β ≥ 2, the gap widens slightly to 15 %, showing that SA is better at balancing parallelism. The greedy algorithm’s performance is most competitive in the regime β < 1. Cost vs. Makespan Weight Simulated Annealing Greedy Algorithm
500
D. Results for the Special Cases of Section V 1) Case 1 (Section V-A): We compare the greedy algorithm, SA, and the optimal algorithm (topological sort plus list scheduling) for instances with one unlimited-capacity QC and 2 − 4 limited-capacity QCs. We use the parameter values |Q| ∈ {10, 15, 20}, |G| ∈ {25, 50, 75, 100}, sp0 = ep0 = ∞, sp ∈ [5, 10] and ep ∈ [3, 6] for p ∈ P ′ . Fig. 8 shows a comparison of the total costs under the three algorithms as the circuit size increases. The optimal algorithm achieves the minimum cost, with values ranging from approximately 150 for |G| = 25 to 400 for |G| = 100. SA achieves costs within 3 − 6 % of the optimal solution across all circuit sizes, demonstrating its effectiveness at finding near-optimal solutions. The greedy algorithm produces solutions within 7 − 12 % of optimal, showing good practical performance despite its polynomial-time complexity. All three algorithms exhibit approximately linear cost growth with respect to the number of gates, with the absolute cost differences between different algorithms remaining relatively stable as circuits scale. Fig. 9 shows that the optimal algorithm’s execution time is comparable to that of the greedy algorithm, with both being O(|G|), while SA is 100 − 150× slower than the latter. Case 1: Total Cost Comparison
400 350
400
300
350
250 200
0
1
2
3
Makespan Weight
4
5
Fig. 6. The figure shows the total cost versus makespan weight β for the greedy algorithm and SA.
Fig. 7 shows the execution times versus β for the same parameter values as used for Fig. 6. The greedy algorithm maintains a nearly constant execution time regardless of β,
Total Cost
Total Cost
450
Optimal Algorithm Simulated Annealing Greedy Algorithm
300 250 200 150 30
40
50
60
70
Number of Gates |G|
80
90
100
Fig. 8. The figure compares the total costs under the optimal, greedy, and SA algorithms for Case 1.
20
Case 1: Execution Time Comparison 60
Execution Time (seconds, log scale)
Execution Time (seconds)
70
Optimal Algorithm Greedy Algorithm Simulated Annealing
50 40 30 20 10 0
30
40
50
60
70
Number of Gates |G|
80
90
Case 2: Execution Time Comparison
102 101
Optimal Algorithm Greedy Algorithm Simulated Annealing
100 10 1 30
100
40
50
60
70
Number of Gates |G|
80
90
100
Fig. 9. The figure compares the execution times of the optimal, greedy, and SA algorithms for Case 1.
Fig. 11. The figure compares the execution times of the optimal, greedy, and SA algorithms for Case 2.
2) Case 2 (Section V-B): For this special case, we set all QCs to have identical parameters: s = 10, e = 5, cs = ce = 2, cg = 1, d(p′ , p) = E(p′ , p) = 0, and Ap,g = 1 for all p, p′ , g. We vary |P | ∈ {2, 3, 4, 5, 6} and β ∈ {0, 0.5, 1.0, 2.0}. Fig. 10 shows a comparison of the total costs for different β values with |Q| = 15 qubits and |G| = 50 gates. The costs increase in β as the algorithms prioritize parallelization. For β = 0, the greedy algorithm is within 5 % of optimal, correctly concentrating resources on fewer QCs. As β increases, the gap of the greedy algorithm widens to 12 − 18 % as optimal parallelization becomes more complex, while SA remains within 4 − 8 % of optimal across all values of β. The optimal algorithm’s complexity is O(|P | + |G| log |P |) and, as shown in Fig. 11, it is orders of magnitude faster than both greedy and SA; this is due to the availability of a closed-form solution for the optimal k ∗ .
is faster than the optimal algorithm across all circuit sizes tested, since the graph construction overhead of Dijkstra’s algorithm dominates even for moderate values of |G|. SA is the slowest of the three, struggling more with sequential circuits and requiring longer runs to converge, likely due to the reduced neighborhood structure in sequential problems. Optimal Algorithm Greedy Algorithm Simulated Annealing
240
Total Cost
220 200 180 160 140 120
20
40
60
80
Number of Gates |G|
100
120
Case 2: Total Cost vs.
260
Optimal Algorithm Simulated Annealing Greedy Algorithm
240
Fig. 12. The figure compares the total costs under the optimal, greedy, and SA algorithms for Case 3.
220 200 180 160 0.00
0.25
0.50
0.75
1.00
1.25
Makespan Weight
1.50
1.75
2.00
Fig. 10. The figure compares the total costs under the optimal, greedy, and SA algorithms for Case 2.
3) Case 3 (Section V-C): We generate sequential circuits with |G| single-qubit gates on one qubit, forming a linear chain. The QC network has |P | = 5 QCs with heterogeneous costs. Figs. 12 and 13 compare the three algorithms. The greedy algorithm performs exceptionally well on sequential circuits, achieving costs within 3 − 5 % of optimal across all circuit sizes. SA achieves intermediate performance, staying within 6 − 7 % of optimal. The consistent gap shows that sequential circuits are relatively easy to handle for the greedy heuristic algorithm, as the optimal path structure is less complex than in general DAG circuits. The optimal algorithm (Dijkstra on the time-expanded graph) has complexity O(|G| · |P |2 log(|G|·|P |)). As shown in Fig. 13, the greedy algorithm
Execution Time (seconds, log scale)
Total Cost
Case 3: Cost Comparison
260
Case 3: Execution Time Comparison
102 101 100
Optimal Algorithm Greedy Algorithm Simulated Annealing
10 1 20
40
60
80
Number of Gates |G|
100
120
Fig. 13. The figure compares the execution times of the optimal, greedy, and SA algorithms for Case 3.
E. Scalability Analysis To evaluate the scalability to large problem instances, we generated circuits with up to |Q| = 50 qubits, |G| = 500 gates, and |P | = 10 QCs. Fig. 14 shows the execution times versus the number of gates, |G|, on a log-log plot. The greedy algorithm’s execution time grows approximately as O(|G|1.15 ), close to theoretical complexity, while SA’s execution time
21
grows as O(|G|1.9 ). For the largest instance (|Q| = 50, |G| = 500, |P | = 10), the greedy algorithm completes in 4.2 seconds, while SA requires over 2000 seconds (33 minutes). Memory usage remains manageable for the greedy algorithm (less than 500 MB) even for the largest instances, while SA requires over 2 GB.
1.14 Sensitivity to QC Scoring Weights for Different Circuit Types
Relative Cost (normalized)
Execution Time (seconds, log scale)
Scalability Analysis: Execution Time 102
minimize frequent inter-qubit communication overhead. The performance degradation from non-optimal weights ranges from 5 − 12 %, with two-qubit dominated circuits being the most sensitive to the choice of parameters.
Greedy Algorithm Simulated Annealing O(|G|) reference O(|G|²) reference
101 100
1.10 1.08 1.06 1.04 1.02 1.00 0.98
10 1 102
Single-qubit dominated (60% single, 40% two-qubit) Balanced circuit (50% single, 50% two-qubit) Two-qubit dominated (30% single, 70% two-qubit)
1.12
0.0
0.2
0.4
0.6
Leasing Weight _{lease}
0.8
1.0
Fig. 16. The figure shows the sensitivity to QC scoring weights for different circuit types.
Number of Gates |G| (log scale) Fig. 14. The figure compares the scalability of the greedy and SA algorithms by showing their execution times on a log-log scale.
G. Summary of Numerical Results Fig. 15 shows the total costs under the greedy and SA algorithms. The relative performance gap between the greedy algorithm and SA remains stable at 10 − 12 % across all circuit sizes, demonstrating that the greedy algorithm’s solution quality does not degrade as problems scale. The consistent gap suggests that the greedy algorithm achieves a similar performance relative to SA regardless of the problem size, while maintaining its significant computational advantage. 5000
Scalability Analysis: Total Cost Greedy Algorithm Simulated Annealing
Total Cost
4000 3000 2000 1000 100
200
300
Number of Gates |G|
400
500
Fig. 15. The figure shows the total costs under the greedy and SA algorithms.
F. Parameter Sensitivity Analysis We vary the weight parameters, αlease and αcomm , in the QC scoring function (see (51)) to study their impact on solution quality for three different circuit types. Fig. 16 shows our results for |Q| = 20, |G| = 100, |P | = 5, and β = 1.0. The optimal weight balance strongly depends on the circuit composition. Single-qubit dominated circuits (60 % singlequbit gates) achieve the minimum cost at αlease ≈ 0.75, as leasing costs dominate with minimal inter-qubit communication. Balanced circuits (50 % single, 50 % two-qubit gates) perform best at αlease = 0.5, requiring equal consideration of leasing and communication costs. Two-qubit dominated circuits (30 % single, 70 % two-qubit gates) perform optimally at αlease ≈ 0.25, prioritizing well-connected QCs to
Table III summarizes the key performance metrics across all experiments. The greedy algorithm consistently produces highquality solutions, typically within 8−15 % of SA and 3−12 % of optimal (when known). The greedy algorithm is 50 − 200× faster than SA, making it the only practical option for largescale instances (|G| > 200). The greedy algorithm exhibits near-linear time complexity in practice, scaling to circuits with 500 or more gates in seconds. For sequential circuits (Case 3), the greedy algorithm performs exceptionally well (within 5 % of optimal), showing that it effectively exploits the circuit structure. The performance is relatively insensitive to parameter choices, with balanced default parameters (αlease = αcomm = 0.5) working well across diverse problems. Thus, for real-time distributed quantum computing scenarios, which require fast decisions, the greedy algorithm offers an excellent balance of solution quality and computational efficiency. TABLE III T HE TABLE SHOWS A SUMMARY OF THE ALGORITHM PERFORMANCE ACROSS ALL EXPERIMENTS . Metric
Greedy SA General Instances Avg. gap to SA 8-15% — Avg. exec. time 0.8 s 92 s Speedup over SA 115× 1× Case 1: Single Unlimited QC Avg. gap to opt. 7-12% 3-6% Avg. exec. time 0.5 s 78 s Case 2: Homogeneous, Zero Movement Avg. gap to opt. 5-18% 4-8% Avg. exec. time 0.6 s 85 s Case 3: Sequential Gates Avg. gap to opt. 3-5% 6.5% Avg. exec. time 0.3 s 95 s Large-Scale Instances Max size tested 50Q, 500G, 10P 30Q, 200G, 8P Time (largest) 4.2 s 2000 s
Optimal — — — 0% 0.4 s 0% 0.02 s 0% 0.7 s — —
VIII. C ONCLUSIONS AND F UTURE W ORK We presented a comprehensive ILP formulation for the JQLQCD problem and showed that it is NP-complete. Also,
22
we identified several special cases in which the problem can be optimally solved in closed form or via polynomial-time algorithms, including those in which (A) there is an unlimited capacity QC in a heterogeneous network, (B) homogeneous QCs with zero movement cost, (C) chain topology with sequential gates, (D) independent subcircuits with partitioned resources, (E) infinite resources with makespan minimization only, and (F) a tree-structured circuit with an arbitrary QC network. We proposed a greedy algorithm with local search refinement for solving general instances of the JQLQCD problem. Using extensive numerical computations, we demonstrated that our proposed greedy algorithm achieves solutions within 8 − 15 % of SA, while being 50 − 200× faster, which shows that it is practical for large-scale instances. Some promising directions for future research are to develop approximation algorithms with provable guarantees for the general JQLQCD problem, investigate parameterized complexity for bounded structural parameters, and enhance the ILP with tight relaxations. Another open problem is to study extended formulations of the JQLQCD problem that incorporate fidelity tracking, dynamic circuit execution, multi-objective optimization, and stochastic programming. Another direction for future research is to design specialized strategies for solving the problem in the cases in which the quantum circuit to be run by the agent is a quantum variational algorithm circuit, QEC circuit, circuit for quantum simulation, etc. An important open problem is to experimentally validate the results of this paper via a real quantum network testbed. Finally, an interesting avenue for future research is to explore heterogeneous qubit technologies, error and fault tolerance, energy minimization, and dynamic pricing mechanisms for the JQLQCD problem. R EFERENCES [1] M. Caleffi, M. Amoretti, D. Ferrari, J. Illiano, A. Manzalini, and A. S. Cacciapuoti, “Distributed quantum computing: a survey,” Computer Networks, vol. 254, p. 110672, 2024. [2] D. Barral, F. J. Cardama, G. Dı́az-Camacho, D. Faı́lde, I. F. Llovo, M. Mussa-Juane, J. Vázquez-Pérez, J. Villasuso, C. Piñeiro, N. Costas et al., “Review of distributed quantum computing: From single QPU to high performance quantum computing,” Computer Science Review, vol. 57, p. 100747, 2025. [3] H. T. Larasati and B.-S. Choi, “Towards fault-tolerant distributed quantum computation (FT-DQC): Taxonomy, recent progress, and challenges,” ICT Express, vol. 11, no. 3, pp. 417–435, 2025. [4] M. Caleffi, A. S. Cacciapuoti, and G. Bianchi, “Quantum internet: From communication to distributed computing!” ACM SIGCOMM Computer Communication Review, vol. 52, no. 2, pp. 3–7, 2022. [5] M. Y. Siraichi, V. F. d. Santos, C. Collange, and F. M. Q. a. Pereira, “Qubit allocation,” in Proceedings of the International Symposium on Code Generation and Optimization (CGO), 2018, pp. 113–125. [6] A. Zulehner, A. Paler, and R. Wille, “An efficient methodology for mapping quantum circuits to the IBM QX architectures,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 38, no. 7, pp. 1226–1236, 2018. [7] P. Murali, N. M. Linke, M. Martonosi, A. J. Abhari, N. H. Nguyen, and C. H. Alderete, “Full-stack, real-system quantum computer studies: architectural comparisons and design insights,” in Proceedings of the 46th International Symposium on Computer Architecture (ISCA), 2019, pp. 527–540. [8] S. S. Tannu and M. K. Qureshi, “Not all qubits are created equal: A case for variability-aware policies for NISQ-era quantum computers,” in Proceedings of the 24th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2019, pp. 987–999.
[9] P. Murali, J. M. Baker, A. Javadi-Abhari, F. T. Chong, and M. Martonosi, “Software mitigation of crosstalk on noisy intermediate-scale quantum computers,” in Proceedings of the 25th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2020, pp. 1001–1016. [10] R. Wille and L. Burgholzer, “MQT QMAP: Efficient quantum circuit mapping,” in Proceedings of the 2023 International Symposium on Physical Design, 2023. [11] T. Peham, L. Burgholzer, and R. Wille, “On optimal subarchitectures for quantum circuit mapping,” ACM Transactions on Quantum Computing, vol. 4, no. 4, pp. 23:1–23:20, July 2023. [12] R. Wille, L. Burgholzer, and A. Zulehner, “Mapping quantum circuits to IBM QX architectures using the minimal number of SWAP and H operations,” in Proceedings of the 53rd Annual Design Automation Conference (DAC), 2016, pp. 1–6. [13] Z.-H. Guo and T.-C. Wang, “SMT-based layout synthesis approaches for quantum circuits,” in Proceedings of the International Symposium on Physical Design, 2024, pp. 235–243. [14] G. Yan, W. Wu, Y. Chen, K. Pan, X. Lu, Z. Zhou, Y. Wang, R. Wang, and J. Yan, “Quantum circuit synthesis and compilation optimization: Overview and prospects,” arXiv preprint arXiv:2407.00736, 2024. [Online]. Available: https://doi.org/10.48550/arXiv.2407.00736 [15] J. Ruan, X. Fang, H. Zhang, A. Li, T. Humble, and Y. Ding, “Powermove: Optimizing compilation for neutral atom quantum computers with zoned architecture,” in Proceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3, 2025, pp. 163–178. [16] M. Letras, J. Echavarria, M. N. Farooqi, M. De Pascale, M. H. Vera, N. Tornow, L. Schulz, and M. Schulz, “Towards a unified multi-target MLIR-based compiler: A heterogeneous compilation framework for high-performance and quantum computing integration,” in 2025 IEEE International Conference on Quantum Computing and Engineering (QCE), vol. 2. IEEE, 2025, pp. 28–33. [17] C. Zhu, X. Wu, Z. Yang, J. Wang, A. Wu, S. Zheng, and X. Wang, “Quantum compiler design for qubit mapping and routing: A crossarchitectural survey of superconducting, trapped-ion, and neutral atom systems,” arXiv preprint arXiv:2505.16891, 2025. [18] Z. Yang, K. Zhang, X. Tian, X. Ren, Y. Liu, Y. Li, D. Ding, J. Chen, and Y. Xie, “Unifying qubit routing across diverse quantum ISAs via canonical representation,” arXiv preprint arXiv:2511.04608, 2025. [19] Y. Stade, W.-H. Lin, J. Cong, and R. Wille, “Routing-aware placement for zoned neutral atom-based quantum computing,” in 2025 IEEE/ACM International Conference On Computer Aided Design (ICCAD). IEEE, 2025, pp. 1–9. [20] N. Quetschlich, L. Burgholzer, and R. Wille, “MQT Predictor: Automatic device selection with device-specific circuit compilation for quantum computing,” ACM Transactions on Quantum Computing, vol. 6, no. 1, pp. 1–26, 2025. [21] A. Molavi, A. Xu, E. Cecchetti, S. Tannu, and A. Albarghouthi, “Generating compilers for qubit mapping and routing,” Proceedings of the ACM on Programming Languages, vol. 10, no. POPL, pp. 2265– 2294, 2026. [22] A. Świerkowska, J. Echavarria, L. Schulz, and M. Schulz, “Achieving Pareto-optimality in quantum circuit compilation via a multi-objective heuristic optimization approach,” in 2024 IEEE International Conference on Quantum Computing and Engineering (QCE), vol. 2. IEEE, 2024, pp. 306–310. [23] R. Ghlib, R. Bouhadouza, and F. Hnaien, “Scalable multi-objective genetic algorithm for quantum circuit optimization,” Scientific Reports, 2026. [24] D. Ferrari, A. S. Cacciapuoti, M. Amoretti, and M. Caleffi, “Compiler design for distributed quantum computing,” IEEE Transactions on Quantum Engineering, vol. 2, pp. 1–20, 2021. [25] D. Ferrari, S. Carretta, and M. Amoretti, “A modular quantum compilation framework for distributed quantum computing,” IEEE Transactions on Quantum Engineering, vol. 4, pp. 1–13, 2023. [26] K. Liu, Y. Zhou, H. Luo, L. Xiong, Y. Zhu, E. Casey, J. Cheng, S. Y.C. Chen, and Z. Liang, “ECDQC: Efficient compilation for distributed quantum computing with linear layout,” in 2025 IEEE International Symposium on Circuits and Systems (ISCAS). IEEE, 2025, pp. 1–5. [27] P. Promponas, A. Mudvari, L. Della Chiesa, P. Polakos, L. Samuel, and L. Tassiulas, “Compiler for distributed quantum computing: a reinforcement learning approach,” in ICC 2025-IEEE International Conference on Communications. IEEE, 2025, pp. 4615–4621. [28] Y. Mao, Y. Liu, and Y. Yang, “Qubit allocation for distributed quantum computing,” in IEEE INFOCOM 2023-IEEE Conference on Computer Communications. IEEE, 2023, pp. 1–10.
23
[29] L. Sünkel, J. Stein, M. Zorn, T. Gabor, and C. Linnhoff-Popien, “Timeaware qubit assignment and circuit optimization for distributed quantum computing,” in 2025 IEEE International Conference on Quantum Computing and Engineering (QCE), vol. 1. IEEE, 2025, pp. 937–947. [30] L. Sünkel, J. Stein, G. Stenzel, M. Kölle, T. Gabor, and C. LinnhoffPopien, “Evolutionary-based circuit optimization for distributed quantum computing,” in 2025 IEEE International Conference on Quantum Artificial Intelligence (QAI). IEEE, 2025, pp. 261–268. [31] D. Cuomo, M. Caleffi, and A. S. Cacciapuoti, “Towards a distributed quantum computing ecosystem,” IET Quantum Communication, vol. 1, no. 1, pp. 3–8, 2020. [32] R. G Sundaram, H. Gupta, and C. Ramakrishnan, “Efficient distribution of quantum circuits,” in Proceedings of the 35th International Symposium on Distributed Computing (DISC). Schloss Dagstuhl–LeibnizZentrum für Informatik, 2021, pp. 41–1. [33] R. G. Sundaram, H. Gupta, and C. Ramakrishnan, “Distribution of quantum circuits over general quantum networks,” in Proceedings of the IEEE International Conference on Quantum Computing and Engineering (QCE), 2022, pp. 415–425. [34] P. Andrés-Martı́nez and C. Heunen, “Automated distribution of quantum circuits via hypergraph partitioning,” Physical Review A, vol. 100, no. 3, p. 032308, 2019. [35] O. Daei, K. Navi, and M. Zomorodi-Moghadam, “Optimized quantum circuit partitioning,” International Journal of Theoretical Physics, vol. 59, pp. 3804–3820, 2020. [36] A. Pastor, P. Escofet, S. B. Rached, E. Alarcón, P. Barlet-Ros, and S. Abadal, “Circuit partitioning for multi-core quantum architectures with deep reinforcement learning,” in Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS), 2024, pp. 1–5. [37] F. Burt, K.-C. Chen, and K. K. Leung, “Generalised circuit partitioning for distributed quantum computing,” in 2024 IEEE International Conference on Quantum Computing and Engineering (QCE), vol. 2. IEEE, 2024, pp. 173–178. [38] ——, “A multilevel framework for partitioning quantum circuits,” Quantum, vol. 10, p. 1984, 2026. [39] R. P. Wu, C. Ranaweera, S. Rajasegarar, R. R. Joseph, J. Choi, and S. W. Loke, “Efficient time-aware partitioning of quantum circuits for distributed quantum computing,” in 2026 International Conference on Quantum Communications, Networking, and Computing (QCNC). IEEE, 2026, pp. 720–724. [40] E. Kaur, S. Pouryousef, H. Shapourian, J. Zhao, M. Kilzer, R. Kompella, and R. Nejabati, “Optimized quantum circuit partitioning across multiple quantum processors,” IEEE Transactions on Quantum Engineering, vol. 6, 2025. [41] F. Burt, K.-C. Chen, and K. K. Leung, “Entanglement-efficient distribution of quantum circuits over large-scale quantum networks,” in 2025 IEEE International Conference on Quantum Computing and Engineering (QCE), vol. 1. IEEE, 2025, pp. 1111–1122. [42] Y. Yang, R. G. Sundaram, and H. Gupta, “Distributing quantum circuits using pre-distributed entanglement pairs over quantum networks,” in 2026 International Conference on Quantum Communications, Networking, and Computing (QCNC). IEEE, 2026, pp. 252–258. [43] ——, “Efficient execution of multiple quantum circuits over a quantum network,” in 2025 IEEE International Conference on Quantum Computing and Engineering (QCE), vol. 1. IEEE, 2025, pp. 1123–1133. [44] C. H. Bennett, G. Brassard, C. Crépeau, R. Jozsa, A. Peres, and W. K. Wootters, “Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels,” Physical Review Letters, vol. 70, no. 13, pp. 1895–1899, 1993. [45] H.-J. Briegel, W. Dür, J. I. Cirac, and P. Zoller, “Quantum repeaters: The role of imperfect local operations in quantum communication,” Physical Review Letters, vol. 81, no. 26, pp. 5932–5935, 1998. [46] H. Gu, Z. Li, R. Yu, X. Wang, F. Zhou, J. Liu, and G. Xue, “FENDI: Toward high-fidelity entanglement distribution in the quantum internet,” IEEE/ACM Transactions on Networking, vol. 32, no. 6, pp. 5033–5048, 2024. [47] J. Halder, A. Rajabov, R. Bassoli, F. H. Fitzek, and G. P. Fettweis, “Optimal routing and end-to-end entanglement distribution in quantum networks,” Scientific Reports, vol. 14, no. 1, p. 19262, 2024. [48] Á. G. Iñesta, G. Vardoyan, L. Scavuzzo, and S. Wehner, “Optimal entanglement distribution policies in homogeneous repeater chains with cutoffs,” npj Quantum Information, vol. 9, no. 46, 2023. [49] H. Gu, Z. Li, X. Wang, D. Yang, G. Xue, and R. Yu, “Cost-aware high-fidelity entanglement distribution and purification in the quantum internet,” IEEE Transactions on Networking, vol. 34, pp. 681–696, 2025. [50] X. Fan, Y. Yang, H. Gupta, and C. Ramakrishnan, “Distribution and purification of entanglement states in quantum networks,” in 2025
International Conference on Quantum Communications, Networking, and Computing (QCNC). IEEE, 2025, pp. 74–82. [51] X. Fan, C. Zhan, H. Gupta, and C. Ramakrishnan, “Optimized distribution of entanglement graph states in quantum networks,” IEEE Transactions on Quantum Engineering, vol. 6, 2025. [52] C. Cicconetti, M. Conti, and A. Passarella, “Resource allocation in quantum networks for distributed quantum computing,” in Proceedings of the IEEE International Conference on Smart Computing (SMARTCOMP), 2022, pp. 124–132. [53] M. Golec, E. S. Hatay, M. Golec, M. Uyar, M. Golec, and S. S. Gill, “Quantum cloud computing: Trends and challenges,” Journal of Economy and Technology, vol. 2, pp. 190–199, 2024. [54] H. T. Nguyen, P. Krishnan, D. Krishnaswamy, M. Usman, and R. Buyya, “Quantum cloud computing: a review, open problems, and future directions,” arXiv preprint arXiv:2404.11420, 2024. [55] J. D. Ullman, “NP-Complete scheduling problems,” Journal of Computer and System Sciences, vol. 10, no. 3, pp. 384–393, 1975. [56] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. [57] J. K. Lenstra and A. H. G. R. Kan, “Complexity of scheduling under precedence constraints,” Operations Research, vol. 26, no. 1, pp. 22–35, 1978. [58] J. Kleinberg and E. Tardos, Algorithm design. Pearson Education India, 2006. [59] A. Botea, A. Kishimoto, and R. Marinescu, “On the complexity of quantum circuit compilation,” Proceedings of the Eleventh International Symposium on Combinatorial Search (SOCS), pp. 138–142, 2018. [60] J. D. Ullman, “NP-complete scheduling problems,” Journal of Computer and System Sciences, vol. 10, no. 3, pp. 384–393, 1975. [61] R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan, “Optimization and approximation in deterministic sequencing and scheduling: A survey,” Annals of Discrete Mathematics, vol. 5, pp. 287–326, 1979. [62] N. Robertson and P. D. Seymour, “Graph minors. II. algorithmic aspects of tree-width,” Journal of Algorithms, vol. 7, no. 3, pp. 309–322, 1986. [63] H. L. Bodlaender, “A partial k-arboretum of graphs with bounded treewidth,” Theoretical Computer Science, vol. 209, no. 1-2, pp. 1–45, 1998. [64] R. G. Downey and M. R. Fellows, Fundamentals of Parameterized Complexity. Springer, 2013. [65] M. Cygan, F. V. Fomin, Łukasz Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh, Parameterized Algorithms. Springer, 2015. [66] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. MIT Press, 2009. [67] D. E. Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3rd ed. Addison-Wesley, 1997. [68] R. L. Graham, “Bounds on multiprocessing timing anomalies,” SIAM Journal on Applied Mathematics, vol. 17, no. 2, pp. 416–429, 1969. [69] E. G. Coffman, Jr., and R. L. Graham, “Optimal scheduling for twoprocessor systems,” Acta Informatica, vol. 1, no. 3, pp. 200–213, 1972. [70] M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information. Cambridge University Press, 2010. [71] D. S. Johnson, A. Demers, J. D. Ullman, M. R. Garey, and R. L. Graham, “Worst-case performance bounds for simple one-dimensional packing algorithms,” SIAM Journal on Computing, vol. 3, no. 4, pp. 299–325, 1974.