Near-term quantum computers often have connectivity constraints, i.e. restrictions, on which pairs of qubits in the device can interact. Optimally mapping a quantum circuit to a hardware topology under these constraints is a difficult task. While numerous approaches have been proposed to optimize qubit routing, the resulting gate count and depth overheads of the compiled circuits remain high due to the short-range coupling of qubits in many near-term devices. Resource states, such as Bell or Einstein-Podolsky-Rosen (EPR) pairs, can be used to mediate operations that facilitate long-range interactions between qubits. In this work, we studied some of the practical trade-offs involved in using resource states for qubit routing. We developed a method that leverages an existing state-of-the-art compiler to optimize the routing of circuits with both standard gates and EPR mediated remote controlled-NOT gates. This was then used to compile different benchmark circuits for a square grid topology, where a fraction of the qubits are used to store EPR pairs. We demonstrate that EPR-mediated operations can substantially reduce the total number of gates and depths of compiled circuits when used with an appropriate optimizing compiler that accounts for practical overheads. Our results highlight the relevance of developing efficient compilation tools that can integrate EPR-mediated operations.
Near-term quantum computers often have connectivity constraints, i.e. restrictions, on which pairs of qubits in the device can interact. Optimally mapping a quantum circuit to a hardware topology under these constraints is a difficult task. While numerous approaches have been proposed to optimize qubit routing, the resulting gate count and depth overheads of the compiled circuits remain high due to the short-range coupling of qubits in many near-term devices. Resource states, such as Bell or Einstein-Podolsky-Rosen (EPR) pairs, can be used to mediate operations that facilitate long-range interactions between qubits. In this work, we studied some of the practical trade-offs involved in using resource states for qubit routing. We developed a method that leverages an existing state-of-the-art compiler to optimize the routing of circuits with both standard gates and EPR mediated remote controlled-NOT gates. This was then used to compile different benchmark circuits for a square grid topology, where a fraction of the qubits are used to store EPR pairs. We demonstrate that EPR-mediated operations can substantially reduce the total number of gates and depths of compiled circuits when used with an appropriate optimizing compiler that accounts for practical overheads. Our results highlight the relevance of developing efficient compilation tools that can integrate EPR-mediated operations.
In many practical applications, quantum algorithms require several qubits, significantly more than those available with current noisy intermediate-scale quantum processors. Distributed quantum computing (DQC) is considered a scalable approach to increasing the number of available qubits for computational tasks. In the DQC setting, a quantum compiler must find the best partitioning for the quantum algorithm and then perform smart non-local operations scheduling to optimize the consumption of Einstein-Podolsky-Rosen (EPR) pairs. In this work, the focus is on minimizing the use of EPR pairs when the circuit structure allows for multiple non-local gates to utilize a single TeleGate operation. This is achieved by using a greedy algorithm that explores the circuit and groups together the gates that could share an EPR pair while also changing the order of commutative gates when necessary. With this preliminary pass, the compiled circuits show reduced depth and EPR usage. Since the quality of each EPR pair quickly deteriorates, the number of non-local gates using the same EPR pair should also be bounded. This means that, depending on the features of the target quantum network, the user can achieve different levels of optimization. Here, it is shown that this approach brings benefits even while assuming a low EPR pair lifetime.
For most practical applications, quantum algorithms require large resources in terms of qubit number, much larger than those available with current NISQ processors. With the network and communication functionalities provided by the Quantum Internet, Distributed Quantum Computing (DQC) is considered as a scalable approach for increasing the number of available qubits for computational tasks. For DQC to be effective and efficient, a quantum compiler must find the best partitioning for the quantum algorithm and then perform smart remote operation scheduling to optimize EPR pair consumption. At the same time, the quantum compiler should also find the best local transformation for each partition. In this paper we present a modular quantum compilation framework for DQC that takes into account both network and device constraints and characteristics. We implemented and tested a quantum compiler based on the proposed framework with some circuits of interest, such as the VQE and QFT ones, considering different network topologies, with quantum processors characterized by heavy-hexagon coupling maps. We also devised a strategy for remote scheduling that can exploit both TeleGate and TeleData operations and tested the impact of using either only TeleGates or both. The evaluation results show that TeleData operations can have a positive impact on the number of consumed EPR pairs, depending on the characteristic of compiled circuit. Meanwhile, choosing a more connected network topology helps reduce the number of layers dedicated to remote operations.
Abstract The limited qubit connectivity of quantum processors poses a significant challenge in deploying practical algorithms and logical gates, necessitating efficient qubit mapping and routing strategies. When implementing a gate that requires additional connectivity beyond the native connectivity, the qubit state must be moved to a nearby connected qubit to execute the desired gate locally. This is typically achieved using a series of SWAP gates creating a SWAP path. However, routing methods relying on SWAP gates often lead to increased circuit depth and gate count, motivating the need for alternative approaches. This work explores the potential of teleported gates to improve qubit routing efficiency, focusing on implementation within specific hardware topologies and benchmark quantum algorithms. We propose a routing method that is assisted by gate teleportation. It establishes additional connectivity using gate teleportation paths through available unused qubits, termed auxiliary qubits, within the topology. To optimize this approach, we have developed an algorithm to identify the best gate teleportation connections, considering their potential to reduce the depth of the circuit and address possible errors that may arise from the teleportation paths. Finally, we demonstrate depth reduction with gate teleportation-assisted routing in various benchmark algorithms, including case studies on the compilation of the Deutsch–Jozsa algorithm and the quantum approximation optimization algorithm for heavy-hexagon topology used in IBM 127-qubit Eagle r3 processors. Our benchmark results show a 10%–25% depth reduction in the routing of selected algorithms compared to regular routing without using teleported gates.
Qubits are powerful computational resources because each additional qubit doubles the size of the accessible state space. This expressive power comes at a cost: adding qubits also increases circuit size, constraint overhead, and exposure to hardware noise. These limitations are especially critical for near-term quantum computers, making the number of qubits required to formulate a problem a central practical concern. In this work, we present a method for efficiently mapping logistics and routing problems onto qubits through structure-aware encoding reduction. We demonstrate the method on a benchmark problem of latency-resilient routing under dual-link failures. For this benchmark, the reduced formulation substantially lowers both the qubit count and the compiled circuit complexity while preserving the original optimization task. By running the reduced model on the same trapped-ion quantum computer as the benchmark, we obtain a 100X improvement in the success probability. This finding shows how careful problem formulation can make current quantum hardware substantially more effective for practical optimization.
Despite rapid advances in quantum computing technologies, the qubit connectivity limitation remains to be a critical challenge. Both near-term NISQ quantum computers and relatively long-term scalable quantum architectures do not offer full connectivity. As a result, quantum circuits may not be directly executed on quantum hardware, and a quantum compiler needs to perform qubit routing to make the circuit compatible with the device layout. During the qubit routing step, the compiler inserts SWAP gates and performs circuit transformations. Given the connectivity topology of the target hardware, there are typically multiple qubit routing candidates. The state-of-the-art compilers use a cost function to evaluate the number of SWAP gates for different routes and then select the one with the minimum number of SWAP gates. After qubit routing, the quantum compiler performs gate optimizations upon the circuit with the newly inserted SWAP gates.In this paper, we observe that the aforementioned qubit routing is not optimal, and qubit routing should not be independent on subsequent gate optimizations. We find that with the consideration of gate optimizations, not all of the SWAP gates have the same basis-gate cost. These insights lead to the development of our qubit routing algorithm, NASSC (Not All Swaps have the Same Cost). NASSC is the first algorithm that considers the subsequent optimizations during the routing step. Our optimization-aware qubit routing leads to better routing decisions and benefits subsequent optimizations. We also propose a new optimization-aware decomposition for the inserted SWAP gates. Our experiments show that the routing overhead compiled with our routing algorithm is reduced by up to 69.30% (21.30% on average) in the number of CNOT gates and up to 43.50% (7.61% on average) in the circuit depth compared with the state-of-the-art scheme, SABRE.
This paper addresses the challenge of scaling quantum computing by employing distributed quantum algorithms across multiple processors. As quantum circuits grow in complexity, efficiently managing the entanglement resources required for communication between quantum processing units (QPUs) becomes increasingly critical. We propose novel methods to optimize entanglement consumption while accounting for network constraints. Our approach leverages graph partitioning techniques to optimize both qubit teleportation and gate teleportation, minimizing the number of Einstein-Podolsky-Rosen (EPR) pairs required to execute general quantum circuits. Additionally, we formulate an integer linear program (ILP) to further reduce entanglement requirements by mapping the logical resources of partitioned circuits to the physical constraints of the underlying quantum network. Finally, we analyze the entanglement cost for implementing the Quantum Fourier Transform (QFT) across multiple QPUs, employing an approach that exploits the circuit's structure to minimize total entanglement consumption. These contributions provide a pathway to scalable and resource-efficient distributed quantum computing.