Abstract As quantum computation grows, the number of qubits involved in a given quantum computer increases. But due to the physical limitations in the number of qubits of a single quantum device, the computation should be performed in a distributed system. In this paper, a new model of quantum computation based on the matrix representation of quantum circuits is proposed. Then, using this model, we propose a novel approach for reducing the number of teleportations in a distributed quantum circuit. The proposed method consists of two phases: the pre-processing phase and the optimization phase. In the pre-processing phase, it considers the bi-partitioning of quantum circuits by Non-Dominated Sorting Genetic Algorithm (NSGA-III) to minimize the number of global gates and to distribute the quantum circuit into two balanced parts with equal number of qubits and minimum number of global gates. In the optimization phase, two heuristics named Heuristic I and Heuristic II are proposed to optimize the number of teleportations according to the partitioning obtained from the pre-processing phase. Finally, the proposed approach is evaluated on many benchmark quantum circuits. The results of these evaluations show an average of 22.16% improvement in the teleportation cost of the proposed approach compared to the existing works in the literature.
Abstract As quantum computation grows, the number of qubits involved in a given quantum computer increases. But due to the physical limitations in the number of qubits of a single quantum device, the computation should be performed in a distributed system. In this paper, a new model of quantum computation based on the matrix representation of quantum circuits is proposed. Then, using this model, we propose a novel approach for reducing the number of teleportations in a distributed quantum circuit. The proposed method consists of two phases: the pre-processing phase and the optimization phase. In the pre-processing phase, it considers the bi-partitioning of quantum circuits by Non-Dominated Sorting Genetic Algorithm (NSGA-III) to minimize the number of global gates and to distribute the quantum circuit into two balanced parts with equal number of qubits and minimum number of global gates. In the optimization phase, two heuristics named Heuristic I and Heuristic II are proposed to optimize the number of teleportations according to the partitioning obtained from the pre-processing phase. Finally, the proposed approach is evaluated on many benchmark quantum circuits. The results of these evaluations show an average of 22.16% improvement in the teleportation cost of the proposed approach compared to the existing works in the literature.
A new approach to reduce the teleportation cost and execution time in Distributed Quantum Circuits (DQCs) was proposed in the present paper. DQCs, a well-known solution, have been applied to solve the problem of maintaining a large number of qubits next to each other. In the distributed quantum system, the qubits are transferred to another subsystem by a quantum protocol like teleportation. Hence, a novel method was proposed to optimize the number of teleportation and to reduce the execution time for generating DQC. To this end, first, the quantum circuit was reordered according to the qubits placement to improve the computational execution time, and then the quantum circuit was modeled as a graph. Finally, we combined the genetic algorithm (GA) and the modified tabu search algorithm (MTS) to partition the graph model in order to obtain a distributed quantum circuit aimed at reducing the number of teleportation costs. A significant reduction in teleportation cost (TC) and execution time (ET) was obtained in benchmark circuits. In particular, we performed a more accurate optimization than the previous approaches, and the proposed approach yielded the best results for several benchmark circuits.
Abstract In the present work, a novel approach was proposed to optimize the teleportation cost in Distributed Quantum Circuits (DQCs) by applying a new approach. To overcome the difficulty with keeping a large number of qubits next to each other, DQCs, as a well-known solution, have always been employed. In a distributed quantum system, qubits are transferred from a subsystem to another subsystem by a quantum protocol such as teleportation. First, we proposed a heuristic approach through which we could replace the equivalent circuits in the initial quantum circuit. Then, we used a genetic algorithm to partition the placement of qubits so that the number of teleportations could be optimized for the communications of a DQC. Finally, results showed that the proposed approach could impressively work.
Distributed Quantum Computing (DQC) provides a means for scaling available quantum computation by interconnecting multiple quantum processor units (QPUs). A key challenge in this domain is efficiently allocating logical qubits from quantum circuits to the physical qubits within QPUs, a task known to be NP-hard. Traditional approaches, primarily focused on graph partitioning strategies, have sought to reduce the number of required Bell pairs for executing non-local CNOT operations, a form of gate teleportation. However, these methods have limitations in terms of efficiency and scalability. Addressing this, our work jointly considers gate and qubit teleportations introducing a novel meta-heuristic algorithm to minimise the network cost of executing a quantum circuit. By allowing dynamic reallocation of qubits along with gate teleportations during circuit execution, our method significantly enhances the overall efficacy and potential scalability of DQC frameworks. In our numerical analysis, we demonstrate that integrating qubit teleportations into our genetic algorithm for optimising circuit blocking reduces the required resources, specifically the number of EPR pairs, compared to traditional graph partitioning methods. Our results, derived from both benchmark and randomly generated circuits, show that as circuit complexity increases - demanding more qubit teleportations - our approach effectively optimises these teleportations throughout the execution, thereby enhancing performance through strategic circuit partitioning. This is a step forward in the pursuit of a global quantum compiler which will ultimately enable the efficient use of a 'quantum data center' in the future.
The presented work provides a procedure for optimizing the communication cost of a distributed quantum circuit (DQC) in terms of the number of qubit teleportations. Because of technology limitations which do not allow large quantum computers to work as a single processing element, distributed quantum computation is an appropriate solution to overcome this difficulty. Previous studies have applied ad-hoc solutions to distribute a quantum system for special cases and applications. In this study, a general approach is proposed to optimize the number of teleportations for a DQC consisting of two spatially separated and long-distance quantum subsystems. To this end, different configurations of locations for executing gates whose qubits are in distinct subsystems are considered and for each of these configurations, the proposed algorithm is run to find the minimum number of required teleportations. Finally, the configuration which leads to the minimum number of teleportations is reported. The proposed method can be used as an automated procedure to find the configuration with the optimal communication cost for the DQC.
Given the limitations on the number of qubits in current noisy intermediate-scale quantum (NISQ) devices, the implementation of large-scale quantum algorithms on such devices is challenging, prompting research into distributed quantum computing. This article focuses on the issue of excessive communication complexity in distributed quantum computing based on the quantum circuit model. To reduce the number of quantum state transmissions, i.e., the transmission cost, in distributed quantum circuits, a circuit partitioning method based on the quadratic unconstrained binary optimization (QUBO) model is proposed, coupled with the lookahead method for transmission cost optimization. Initially, the problem of distributed quantum circuit partitioning is transformed into a graph minimum cut problem. The QUBO model, which can be accelerated by quantum annealing algorithms, is introduced to minimize the number of quantum gates between quantum processing units (QPUs) and the transmission cost. Subsequently, the dynamic lookahead strategy for the selection of transmission qubits is proposed to optimize the transmission cost in distributed quantum circuits. Finally, through numerical simulations, the impact of different circuit partitioning indicators on the transmission cost is explored, and the proposed method is evaluated on benchmark circuits. Experimental results demonstrate that the proposed circuit partitioning method has a shorter runtime compared with current circuit partitioning methods. Additionally, the transmission cost optimized by the proposed method is significantly lower than that of current transmission cost optimization methods, achieving noticeable improvements across different numbers of partitions.
When dealing with NISQ computers (Noise Intermediate Scale Quantum), it is widely accepted that distributing circuits among processing agents is an effective way to increase scalability with small machines. This approach can improve overall computational power, but it requires using qubits for communication between partitions, dedicated for the teleportation protocol over time. The main challenge is to minimize this communication cost by using efficient circuit partitioning strategies. There are many different partitioning approaches in the literature, but a consensus is needed on the best method for distribution scenarios. Here, we explore the partitioning process of quantum circuits using a hypergraphic representation for the circuit, to run this task. First, explore and compare different approaches of hypergraphic partitioning. Then, we created a variation of the Fiduccia-Mattheyses heuristic to minimize the communication qubits between partitions. Thanks to our tunning and an applied approach, we reduced the cost of partitioning circuits of 10% to 50% with respect to the different algorithms from state of art. Our method involves three steps: logical segmentation and grouping of gates; translation of the circuit into a hypergraphic representation; and use of the Fiduccia-Mattheyses heuristic variation for hypergraphic partitioning. This research explores quantum circuits partitioning for different scenarios as multi-QPU and distributed machine over classical communication, consolidating important results for quantum development in distributed scenarios, for a set of benchmark algorithms.