Network Operations Scheduling Enables Minimum Makespan for Distributed Quantum Computing Architectures

Scaling up quantum computing power requires distributed architectures, and coordinating operations across these systems presents a significant challenge. Nitish Kumar Chandra from University of Pittsburgh, Eneet Kaur from Cisco Quantum Lab, and Kaushik P. Seshadreesan from University of Pittsburgh investigate methods for efficiently scheduling network operations in such distributed quantum systems. Their work focuses on minimising the overall time required to complete a quantum circuit, a measure known as ‘make span’, by intelligently allocating tasks to individual quantum processing units and coordinating the exchange of quantum information between them. The team compares a sophisticated scheduling approach, based on established resource-constrained project scheduling techniques, with a faster, more intuitive greedy algorithm, demonstrating that both methods can effectively address this complex problem and highlighting the strengths of each in different scenarios. This research advances the development of practical, scalable quantum computers by providing valuable insights into the optimisation of network operations.

This approach aims to increase overall quantum resources and potentially improve fault tolerance by distributing quantum computations across several QPUs. Key to this field is overcoming challenges related to limited qubit counts and the short duration of qubit coherence, the time qubits can reliably maintain quantum information. Researchers are investigating several core concepts and techniques, including circuit partitioning, qubit mapping, and establishing quantum communication.

Efficient resource allocation is also crucial, alongside methods to address noise and errors in both quantum computations and communication. Scientists are developing different network architectures, such as star, mesh, and fully connected systems, and refining techniques like entanglement distillation and quantum repeaters to improve communication quality and range. The field draws upon several approaches and algorithms, including Measurement-Based Quantum Computation (MBQC) and quantum teleportation. Hybrid classical-quantum optimization uses classical algorithms to optimize resource allocation, while advanced circuit compilation techniques further optimize quantum circuits for distributed execution.

Greedy algorithms offer simpler, efficient solutions for specific aspects of DQC. Despite progress, several challenges remain, including the overhead associated with establishing and maintaining entanglement between QPUs and the complexity of coordinating computations across multiple units. Building and managing large-scale DQC systems presents a major scalability challenge, and protecting quantum information from eavesdropping is paramount. Future research focuses on real-world benchmarking, integrating robust error correction schemes, and ensuring the authentication of QPUs within the network. This work emphasizes that DQC is a crucial step towards building practical and scalable quantum computers, requiring continued investigation into quantum communication, resource allocation, error correction, and optimization strategies.

Circuit Partitioning and Scheduling for Distributed QPUs

Scientists have developed a comprehensive methodology for scheduling quantum operations across distributed quantum processing units (QPUs), essential for scaling quantum computation. The study represents quantum circuits using both Directed Acyclic Graphs (DAGs) and Gantt charts, leveraging the strengths of each approach to capture circuit structure and execution timelines. DAGs illustrate dependencies between gates and qubits, while Gantt charts provide a time-based view of resource utilization. To optimize network operation, the team partitions complex quantum circuits using the METIS solver, minimizing the number of nonlocal entangling gates required between QPUs while maintaining a uniform qubit load across individual units.

This partitioning directly addresses the challenge of coordinating operations over short-range networks, essential for enabling entanglement between distant processing units. The research involves evaluating two scheduling approaches: one based on the Resource-Constrained Project Scheduling Problem (RCPSP) framework and a simpler greedy heuristic algorithm. The RCPSP approach focuses on efficiently managing limited quantum resources, while the greedy algorithm makes locally optimal decisions to minimize execution time. Researchers analyzed these approaches using instances of the Fourier Transform algorithm implemented on a star network topology with finite communication and memory qubit resources. The results demonstrate the effectiveness of the RCPSP framework in generating optimal schedules with minimized execution time, while also highlighting the relevance and efficiency of the greedy heuristic for this task. This work focuses on scheduling these operations to minimize the overall time required to complete a quantum computation, known as the make span. The workflow begins with partitioning a quantum circuit and assigning it to different QPUs, minimizing the number of nonlocal entangling gates while ensuring a nearly uniform qubit load across each QPU. This partitioning leverages the METIS solver, a graph partitioning algorithm, to efficiently distribute the computational workload.

Subsequently, the necessary network operations to deliver entanglement between QPUs are identified and mapped to specific sequences of actions. The core of the research involves scheduling these network operations to minimize the make span. Results demonstrate that the RCPSP approach outperformed the greedy heuristic in one instance, achieving a shorter make span, while both approaches yielded equivalent performance in another. These findings confirm the RCPSP framework’s ability to generate optimal schedules in resource-limited quantum networks, while also underlining the practicality and efficiency of greedy algorithms for this task. The team investigated a resource-constrained project scheduling (RCPSP) framework alongside a greedy heuristic algorithm, both designed to minimize the overall execution time of quantum circuits spread across multiple quantum processing units (QPUs). The approach involved partitioning quantum circuits and assigning them to QPUs, aiming for balanced qubit usage while minimizing the number of connections needed between them. Results demonstrate that the RCPSP framework can outperform the greedy heuristic in certain scenarios, specifically when using a quantum switch connected to two QPUs. This advantage stems from the framework’s ability to optimize resource allocation and scheduling, leading to shorter overall computation times.