Imagine you are a conductor trying to lead a complex orchestra (a quantum circuit) to play a symphony. However, you don't own a single concert hall. Instead, you have to rent space in several different, scattered music rooms (Quantum Computers or QCs) connected by hallways (Quantum Networks).

Each music room has its own rules:

Some rooms are huge but expensive to rent.
Some are small and cheap but can only hold a few musicians at a time.
Some rooms have great acoustics for specific instruments (gates), while others are terrible for them.
Moving a musician from one room to another takes time and money, either by walking down the hall (Migration) or by using a magical teleportation device that requires pre-arranged magic links (Teleportation).

Your goal is to get the whole symphony played as quickly and cheaply as possible. You have to make four big decisions:

How many musicians to rent from each room.
Where to park each musician at every moment in time.
Which room plays which part of the song.
How to move musicians between rooms when the music demands it.

The authors of this paper call this the Joint Qubit Leasing and Quantum Circuit Distribution (JQLQCD) problem.

The Core Challenge: A Puzzle Too Hard to Solve Perfectly

The authors prove that for a general, messy orchestra with many rooms and complex rules, finding the perfect solution is mathematically impossible to do quickly. In computer science terms, the problem is NP-complete. It's like trying to solve a Sudoku puzzle that gets exponentially harder the more numbers you add; a computer would have to check every single possible arrangement of musicians to find the absolute best one, which would take longer than the age of the universe for a large orchestra.

The "Special Cases" Where It's Easy

However, the authors found that if the situation is simplified, you can find the perfect answer quickly. They identified six "special scenarios" where the math becomes manageable:

The "Unlimited Room" Scenario: If one room is infinitely big and free, you might as well just put everyone there and ignore the others.
The "Identical Rooms" Scenario: If all rooms are exactly the same and moving musicians is free, you just spread them out evenly to finish the song fast.
The "Linear Chain" Scenario: If the song is just one long line of notes (no branching), you can figure out the best path by simply tracing the line, like finding the shortest route on a map.
The "Independent Bands" Scenario: If the orchestra is actually several small bands playing different songs that don't interact, you can solve each band's problem separately.
The "Infinite Resources" Scenario: If money and space don't matter, you just focus on finishing the song as fast as physics allows.
The "Tree Structure" Scenario: If the song's structure is a simple tree (like a family tree), you can work backward from the end to the beginning to find the cheapest path.

The "Greedy" Solution for the Real World

Since most real-world quantum circuits aren't these simple special cases, the authors needed a way to get a good answer quickly, even if it's not perfect. They created a "Greedy Algorithm."

Think of this algorithm as a very efficient, slightly impatient manager. Instead of checking every possible arrangement (which takes forever), the manager makes a series of smart, local decisions:

Score the Rooms: The manager looks at each room and gives it a score based on how cheap it is to rent and how easy it is to reach from other rooms.
Pick the Best: They pick the highest-scoring room first.
Fill it Up: They assign musicians to that room, prioritizing musicians who play instruments that work well there and who are already near other musicians they need to interact with.
Refine: After the initial assignment, the manager does a quick "local search," checking if swapping a musician to a different room would save a little money or time. If yes, they make the swap.

The Results: Fast and Good Enough

The authors tested this "Greedy Manager" against a much slower, more thorough method called Simulated Annealing (which is like a very patient manager who tries random changes over and over to see if they get lucky).

Speed: The Greedy Manager was 50 to 200 times faster than the patient manager. For a large orchestra, the Greedy Manager finished the plan in less than a second, while the patient manager took over 30 minutes.
Quality: The Greedy Manager's plans were only 8% to 15% more expensive than the best possible plans found by the patient manager.

The Bottom Line

The paper argues that while finding the perfect way to rent quantum computers and distribute a quantum circuit is mathematically impossible to do quickly for complex tasks, we don't need perfection. We need speed. Their "Greedy Algorithm" acts like a highly efficient logistics coordinator: it makes smart, quick decisions that get the job done almost as well as the perfect solution, but in a fraction of the time. This makes it practical for real-world scenarios where decisions need to be made instantly.

Technical Summary: Joint Optimization of Qubit Leasing and Quantum Circuit Distribution

1. Problem Definition

The paper addresses the Joint Qubit Leasing and Quantum Circuit Distribution (JQLQCD) problem. This problem arises for an agent seeking to execute a specific quantum circuit using resources leased from a heterogeneous network of Quantum Computers (QCs) connected via a quantum network.

Unlike prior work that focuses solely on circuit partitioning or mapping to a single device, JQLQCD requires the agent to make four interdependent decisions simultaneously:

Leasing: Determining how many storage and execution qubits to lease from each QC.
Placement: Deciding at which QC to store different circuit qubits during specific time slots.
Scheduling: Assigning each gate in the circuit to a specific QC for execution.
Movement: Selecting the method for moving qubits between QCs (either migration via physical transfer or teleportation via pre-shared entanglement) to satisfy gate operand requirements.

The objective is to minimize a total system cost function comprising:

Leasing costs (storage and execution capacity).
Gate execution costs (which vary by QC).
Communication costs (migration and teleportation).
Makespan (circuit completion time), weighted by a parameter $\beta$ .

The problem is constrained by QC storage and execution capacities, gate availability (some gates may not run on all QCs), and circuit precedence constraints (DAG structure).

2. Methodology

A. Mathematical Formulation

The authors formulate JQLQCD as a comprehensive Integer Linear Programming (ILP) model. The formulation explicitly models:

Decision Variables: Binary variables for qubit location ( $x_{q,p,t}$ ), execution usage ( $z_{q,p,t}$ ), movement type (migration $\gamma$ or teleportation $w$ ), and gate assignment ( $u_{g,p}$ ); integer variables for start times ( $t_g$ ) and makespan ( $T_{max}$ ).
Constraints: Capacity limits, qubit uniqueness, gate assignment validity, operand presence at execution time, precedence constraints, and movement consistency (ensuring location changes correspond to valid migration or teleportation events).
Cost Modeling: The model incorporates distance-dependent costs for both migration and teleportation, acknowledging the trade-offs between physical transfer and entanglement-based communication.

B. Complexity Analysis

The paper proves that the general JQLQCD problem is NP-complete. This is demonstrated by showing a polynomial-time reduction from the multiprocessor scheduling problem with precedence constraints ( $P|prec|C_{max}$ ), a known NP-complete problem. Furthermore, the problem is shown to be strongly NP-complete, implying that no pseudo-polynomial time algorithm exists unless $P=NP$.

However, the authors also establish that the problem is Fixed-Parameter Tractable (FPT) when parameterized by the number of QCs ( $|P|$ ), maximum QC capacity ( $\kappa$ ), and the tree-width of the circuit dependency graph.

C. Special Cases and Exact Algorithms

Recognizing the general hardness, the paper identifies six special cases where the problem can be solved optimally in closed form or via polynomial-time algorithms:

Unlimited Capacity QC in a Heterogeneous Network: Derives sufficient and necessary conditions under which a centralized solution (using only the unlimited QC) is optimal.
Homogeneous QCs with Zero Movement Cost: Provides algorithms to determine the optimal number of QCs to use based on the trade-off between leasing costs and makespan ( $\beta$ ).
Chain Topology with Sequential Gates: Reduces the problem to a shortest-path problem on a time-expanded graph, solvable via Dijkstra's algorithm or Dynamic Programming (DP).
Independent Subcircuits: Proposes a decomposition approach where the circuit is split into disjoint components, each solved independently.
Infinite Resources with Makespan Minimization Only: Reduces to the classical multiprocessor scheduling problem, solvable via critical path analysis.
Tree-Structured Circuit: Uses a DP approach processing gates in reverse topological order to find the optimal cost.

D. Heuristic for General Instances

For general instances where exact solutions are computationally prohibitive, the authors propose a Greedy Algorithm with Local Search Refinement:

Greedy Phase: QCs are scored based on a composite metric of leasing costs and average communication costs. Qubits are assigned to QCs iteratively, prioritizing those with lower scores and higher affinity (co-locating interacting qubits).
Refinement Phase: A local search iteratively attempts to reassign qubits to different QCs to reduce the total cost, accepting moves that improve the objective function.

3. Key Contributions

The paper's primary contributions are:

Problem Formulation: The first comprehensive ILP formulation for the joint optimization of resource leasing and circuit distribution, explicitly modeling both migration and teleportation primitives.
Complexity Proof: Proof of NP-completeness and strong NP-completeness for the general problem.
Special Case Analysis: Identification of six specific scenarios admitting polynomial-time or closed-form optimal solutions, along with necessary and sufficient conditions for optimality in heterogeneous networks.
Heuristic Development: A practical greedy algorithm with local search, designed for real-time decision-making in distributed quantum computing.
Empirical Validation: Extensive numerical evaluation demonstrating the algorithm's performance relative to Simulated Annealing (SA) and optimal solutions.

4. Numerical Results

The authors evaluated the proposed greedy algorithm against Simulated Annealing (SA) and optimal solvers for special cases across various parameters (circuit size, number of QCs, makespan weight $\beta$ ).

Solution Quality:
- For general instances, the greedy algorithm achieves solutions within 8–15% of the cost found by SA.
- For special cases with known optimal solutions, the greedy algorithm finds solutions within 4–12% of the optimum.
- In sequential circuit cases (Case 3), the greedy algorithm performs exceptionally well, staying within 3–5% of the optimal solution.
Computational Efficiency:
- The greedy algorithm is 50–200 times faster than SA.
- For large-scale instances (50 qubits, 500 gates, 10 QCs), the greedy algorithm completes in 4.2 seconds, whereas SA requires over 2000 seconds (33 minutes).
- The greedy algorithm exhibits near-linear time complexity in practice ( $O(|G|^{1.15})$ ), scaling effectively to large circuits.
Scalability: The algorithm maintains consistent solution quality relative to SA as problem sizes increase, making it suitable for real-time scenarios where fast decision-making is critical.

5. Significance and Claims

The paper claims to fill a critical gap in the literature by addressing the joint optimization of resource leasing and circuit distribution, a problem distinct from prior work on circuit partitioning or single-device mapping.

The authors assert that their work is significant for the emerging landscape of quantum cloud computing, where users must rent resources from multiple providers. By providing a tractable heuristic that balances cost and performance, the paper offers a practical tool for agents managing distributed quantum workloads. The results suggest that while the general problem is computationally hard, efficient approximations are viable for real-world deployment, particularly given the constraints of current and near-future quantum hardware (limited qubit counts and coherence times).

The paper concludes modestly, noting that future work could explore approximation algorithms with provable guarantees, extended formulations incorporating fidelity and dynamic execution, and experimental validation on real quantum network testbeds.

Joint Optimization of Qubit Leasing and Quantum Circuit Distribution