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.
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.
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.
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.
By connecting multiple quantum computers (QCs) through classical and quantum channels, a quantum communication network can be formed. This gives rise to new applications such as blind quantum computing, distributed quantum computing, and quantum key distribution. In distributed quantum computing, QCs collectively perform a quantum computation. As each device only executes a sub-circuit with fewer qubits than required by the complete circuit, a number of small QCs can be used in combination to execute a large quantum circuit that a single QC could not solve on its own. However, communication between QCs may still occur. Depending on the connectivity of the circuit, qubits must be teleported to different QCs in the network, adding overhead to the actual computation; thus, it is crucial to minimize the number of teleportations. In this paper, we propose an evolutionary algorithm for this problem. More specifically, the algorithm assigns qubits to QCs in the network for each time step of the circuit such that the overall teleportation cost is minimized. Moreover, network-specific constraints such as the capacity of each QC in the network can be taken into account. We run experiments on random as well as benchmarking circuits and give an outline on how this method can be adjusted to be incorporated into more realistic network settings as well as in compilers for distributed quantum computing. Our results show that an evolutionary algorithm is well suited for this problem when compared to the graph partitioning approach as it delivers better results while simultaneously allows the easy integration and consideration of various problem-specific constraints.
In this paper, a multi-layer hierarchical architecture is proposed for distributing quantum computation. In a distributed quantum computing (DQC), different units or subsystems communicate by teleportation in order to transfer quantum information. Quantum teleportation requires classical and quantum resources and hence, it is essential to minimize the number of communications among these subsystems. To this end, a two-level hierarchical optimization method is proposed to distribute the qubits among different parts. In Level I, an integer linear programming model is presented to distribute a monolithic quantum system into K balanced partitions which results in the minimum number of non-local gates. When a qubit is teleported to a destination part, it can be used optimally by other gates without being teleported back to the destination part. In Level II, a data structure is proposed for quantum circuit and a recursive function is applied to minimize the number of teleportations. Experimental results show that the proposed approach outperforms the previous ones.
Distributed quantum computing has been well-known for many years as a system composed of a number of small-capacity quantum circuits. Limitations in the capacity of monolithic quantum computing systems can be overcome by using distributed quantum systems which communicate with each other through known communication links. In our previous study, an algorithm with an exponential complexity was proposed to optimize the number of qubit teleportations required for the communications between two partitions of a distributed quantum circuit. In this work, a genetic algorithm is used to solve the optimization problem in a more efficient way. The results are compared with the previous study and we show that our approach works almost the same with a remarkable speed-up. Moreover, the comparison of the proposed approach based on GA with a random search over the search space verifies the effectiveness of GA.
Near-term quantum computers can hold only a small number of qubits. One way to facilitate large-scale quantum computations is through a distributed network of quantum computers. In this work, we consider the problem of distributing quantum programs represented as quantum circuits across a quantum network of heterogeneous quantum computers, in a way that minimizes the overall communication cost required to execute the distributed circuit. We consider two ways of communicating: cat-entanglement that creates linked copies of qubits across pairs of computers, and teleportation. The heterogeneous computers impose constraints on cat-entanglement and teleportation operations that can be chosen by an algorithm. We first focus on a special case that only allows cat-entanglements and not teleportations for communication. We provide a two-step heuristic for solving this specialized setting: (i) finding an assignment of qubits to computers using Tabu search, and (ii) using an iterative greedy algorithm designed for a constrained version of the set cover problem to determine cat-entanglement operations required to execute gates locally. For the general case, which allows both forms of communication, we propose two algorithms that subdivide the quantum circuit into several portions and apply the heuristic for the specialized setting on each portion. Teleportations are then used to stitch together the solutions for each portion. Finally, we simulate our algorithms on a wide range of randomly generated quantum networks and circuits, and study the properties of their results with respect to several varying parameters.