Hypergraphic Partitioning of Quantum Circuits for Distributed Quantum Computing

Abstract

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.