Qubit Mapping is a critical task in Quantum Compilation, as modern Quantum Processing Units (QPUs) are constrained to nearest-neighbor interactions defined by a qubit coupling graph. This compiler pass repairs the connectivity of two-qubit gates whose operands are not adjacent by inserting SWAP gates that move the state of qubits between directly connected qubits. Deciding when to introduce SWAPs while minimizing their count is critical because the error in quantum programs increases exponentially with the circuit latency, measured in number of gates along the critical path of the circuit. Prior work for this problem relied on heuristics and exact methods that partition the circuit into two or more layers, but failed to exploit valuable dependence information in any form.This paper introduces a novel qubit mapping algorithm based on the weight of transitive dependences. The introduced mapper models quantum circuits with affine abstractions, thereby providing the ability to compute transitive dependences. In turn, the newfound information is used to partition circuits by dependence distances and compute, efficiently, distinct weights for each layer. We evaluate the efficiency of our mapper on IBM and Rigetti QPUs, using the large datasets from the QUEKO and QASMBench benchmark suites, and against four baseline tools (QMAP, Sabre, Cirq and TKET), demonstrating notable improvements in circuit depth and swap count while delivering competitive scalability.
Qubit Mapping is a critical task in Quantum Compilation, as modern Quantum Processing Units (QPUs) are constrained to nearest-neighbor interactions defined by a qubit coupling graph. This compiler pass repairs the connectivity of two-qubit gates whose operands are not adjacent by inserting SWAP gates that move the state of qubits between directly connected qubits. Deciding when to introduce SWAPs while minimizing their count is critical because the error in quantum programs increases exponentially with the circuit latency, measured in number of gates along the critical path of the circuit. Prior work for this problem relied on heuristics and exact methods that partition the circuit into two or more layers, but failed to exploit valuable dependence information in any form.This paper introduces a novel qubit mapping algorithm based on the weight of transitive dependences. The introduced mapper models quantum circuits with affine abstractions, thereby providing the ability to compute transitive dependences. In turn, the newfound information is used to partition circuits by dependence distances and compute, efficiently, distinct weights for each layer. We evaluate the efficiency of our mapper on IBM and Rigetti QPUs, using the large datasets from the QUEKO and QASMBench benchmark suites, and against four baseline tools (QMAP, Sabre, Cirq and TKET), demonstrating notable improvements in circuit depth and swap count while delivering competitive scalability.
Qubit mapping is a critical pass in quantum compilation. Despite various advances, dynamic circuits, those exhibiting data dependent control-flow, often resulting from qubit measurements, are not yet supported by the vast majority of available qubit mappers. The crucial limitation to overcome is the dependence on flat, one-dimensional representations of circuits. Further, qubit mappers currently lack compiler abstractions that capture the hierarchical nature of circuits, hindering the qubit mapping process. In this paper, 1 we introduce a new qubit mapping method and analyses to tackle hierarchical dynamic circuits. Our novelty resides in four key aspects: modeling (statically) sub-circuits in disjoint control-flow paths, introducing a novel Qubit Reconciliation pass to maintain consistency between sub-circuit and control-flow boundaries, a loop-entry remapping pass, and a refined cost function enhanced for SWAP count, circuit depth, circuit latency and error. We demonstrate the efficiency of our approach on a wide range of dynamic circuits on two monolithic Quantum Processing Units of 127 and 156 qubits, and on chiplet hexagon-based QPUs. On monolithic QPUs, our qubit mapper improves the SWAP count by up to 52%, depth by up to 18%, latency by up to 18.6%, and error by up to 40%. On chiplet architectures, we achieve improvements of up to 36% on SWAP count, 8.7% on depth, 15% on latency, and 15% of error.
Most quantum compiler transformations and qubit allocation techniques to date are either peep-hole focused or rely on sliding windows that depend on a number of external parameters including the topology of the quantum processor. Thus, global optimization criteria are still lacking. In this article, we explore the synergies and impact of affine loop transformations in the context of qubit allocation and mapping. With this goal in mind, we designed and implemented AXL , a domain specific language and source-to-source compiler for quantum circuits that can be directly described with affine relations. We conduct an extensive evaluation spanning circuits from the recently introduced QUEKO benchmark suite, eight quantum circuits taken from the literature, three distinct coupling graphs, four affine transformations (including the Pluto dependence distance minimization and Feautrier’s minimum latency algorithms), four qubit allocators, and two back-end quantum compilers. Our results demonstrate that affine transformations using global optimization criteria can cooperate effectively in several scenarios with quantum qubit mapping algorithms to reduce the circuit depth, size and allocation time.
Quantum computing has been accumulating tremendous attention in recent years. In current superconducting quantum processors, each qubit can only be connected with a limited number of neighbors. Therefore, the original quantum circuit should be converted to a hardware-dependent circuit, and this process is called qubit mapping and routing, in which typically extra SWAP gates need to be inserted. Due to a limited qubit lifetime, one of the main objectives of qubit mapping and routing is to minimize the circuit depth, which is a time-consuming process. By studying several existing greedy mappers, we extract and analyze two patterns that significantly impact the mapping and routing performance. Then, we propose a sliding window method named SWin, which dramatically reduces the computational cost with negligible performance degradation. For devices with constrained executable circuit depth, we propose SWin+, which introduces adaptive circuit slicing methods with VF2++subgraph isomorphism initial mapping methods. Compared with the state-of-the-art greedy methods, SWin can find an effective result by up to 39% depth decrease, on average of 16% for large-scale circuits. Moreover, SWin can be easily modified to be noise-aware, while the depth reduction will yield better performance for real execution. Furthermore, SWin still performs well for various chip couplings. SWin+ significantly enhances processing efficiency, achieving improvements up to$22.3\times $, with an average increase of$6.1\times $. Concurrently, it maintains the effectiveness of the transformed circuit depth.
One of the key compilation steps in Quantum Computing (QC) is to determine an initial logical to physical mapping of the qubits used in a quantum circuit. The impact of the starting qubit layout can vastly affect later scheduling and placement decisions of QASM operations, yielding higher values on critical performance metrics (gate count and circuit depth) as a result of a quantum compilers introducing communication operations to meet the underlying physical neighboring and connectivity constraints of the quantum device.We present our ongoing work on qubit mapping with affine abstractions, which aims to compute effective initial qubit layouts. The key assumption is that the quantum program is represented in an affine representation, a property which permits us to apply aggressive program analyses to determine the potential of sharing qubit accesses among groups of quantum operations prescribed by linear and affine relations. We present preliminary results demonstrating the effectiveness of our novel approach on 69 quantum circuits, while using the QISKIT compiler on IBM Tokyo and Google Sycamore, obtaining between 16% and 21% average improvement on circuit depth and 24%–47% improvement on the number of added gates.
One of the key compilation steps in Quantum Computing (QC) is to determine an initial logical to physical mapping of the qubits used in a quantum circuit. The impact of the starting qubit layout can vastly affect later scheduling and placement decisions of QASM operations, yielding higher values on critical performance metrics (gate count and circuit depth) as a result of quantum compilers introducing SWAP operations to meet the underlying physical neighboring and connectivity constraints of the quantum device. In this paper we introduce a novel qubit mapping approach, string-based qubit mapping. The key insight is to prioritize the mapping of logical qubits that appear in longest repeating non-overlapping substrings of qubit pairs accessed. This mapping method is complemented by allocating qubits according to their global frequency usage. We evaluate and compare our new mapping scheme against two quantum compilers (QISKIT and TKET) and two device topologies, the IBM Manhattan (65 qubits) and the IBM Kolkata (27 qubits). Our results demonstrate that combining both mapping mechanisms often achieve better results than either one individually, allowing us to best QISKIT and TKET baselines, yielding between 13% and 17% average improvement in several group sizes, up to 32% circuit depth reduction and 63% gate volume improvement.
Quantum algorithms need to be compiled to respect the constraints imposed by quantum processors, which is known as the mapping problem. The mapping procedure will result in an increase of the number of gates and of the circuit latency, decreasing the algorithm’s success rate. It is crucial to minimize mapping overhead, especially for noisy intermediate-scale quantum (NISQ) processors that have relatively short qubit coherence times and high gate error rates. Most of prior mapping algorithms have only considered constraints, such as the primitive gate set and qubit connectivity, but the actual gate duration and the restrictions imposed by the use of shared classical control electronics have not been taken into account. In this article, we present a mapper called Qmap to make quantum circuits executable on scalable processors with the objective of achieving the shortest circuit latency. In particular, we propose an approach to formulate the classical control restrictions as resource constraints in a conventional list scheduler with polynomial complexity. Furthermore, we implement a routing heuristic to cope with the connectivity limitation. This router finds a set of movement operations that minimally extends circuit latency. To analyze the mapping overhead and evaluate the performance of different mappers, we map 56 quantum benchmarks onto a superconducting processor named Surface-17. Compared to a prior mapping strategy that minimizes the number of operations, Qmap can reduce the latency overhead (LtyOH) up to 47.3% and operation overhead up to 28.6%, respectively.