Quantum computers are expected to scale in size to close the gap that currently exists between quantum algorithms and quantum hardware. To this end, quantum compilation techniques must scale along with the hardware constraints, shifting the current paradigm of obtaining an optimal compilation to relying on heuristics that allow for a fast solution, even though the quality of such a solution may not be optimal. Significant concerns arise as the execution time of current mapping techniques experiences a notable increase when applied to quantum computers with a high number of qubits. In this work, we present Route-Forcing, a quantum circuit mapping algorithm that shows a compilation time average speedup of 3.7 × compared to the state-of-the-art scalable techniques, reducing the depth of the mapped circuit by 4.7 × at the expense of adding 1.3 × more SWAP gates. Moreover, the proposed mapping algorithm is adapted and tuned for what is expected to be the next generation of quantum computers, in which different processors are interconnected to increase the total number of qubits, allowing for more complex computations.
Quantum computers are expected to scale in size to close the gap that currently exists between quantum algorithms and quantum hardware. To this end, quantum compilation techniques must scale along with the hardware constraints, shifting the current paradigm of obtaining an optimal compilation to relying on heuristics that allow for a fast solution, even though the quality of such a solution may not be optimal. Significant concerns arise as the execution time of current mapping techniques experiences a notable increase when applied to quantum computers with a high number of qubits. In this work, we present Route-Forcing, a quantum circuit mapping algorithm that shows a compilation time average speedup of 3.7 × compared to the state-of-the-art scalable techniques, reducing the depth of the mapped circuit by 4.7 × at the expense of adding 1.3 × more SWAP gates. Moreover, the proposed mapping algorithm is adapted and tuned for what is expected to be the next generation of quantum computers, in which different processors are interconnected to increase the total number of qubits, allowing for more complex computations.
Despite Noisy Intermediate-Scale Quantum devices being severely constrained, hardware- and algorithm-aware quantum circuit mapping techniques have been developed to enable successful algorithm executions. Not so much attention has been paid to mapping and compilation implementations for spin-qubit quantum processors due to the scarce availability of experimental devices and their small sizes. However, based on their high scalability potential and their rapid progress it is timely to start exploring solutions on such devices. In this work, we discuss the unique mapping challenges of a scalable crossbar architecture with shared control and introduce SpinQ , the first native compilation framework for scalable spin-qubit architectures. At the core of SpinQ is the Integrated Strategy that addresses the unique operational constraints of the crossbar while considering compilation scalability and obtaining a O(n) computational complexity. To evaluate the performance of SpinQ on this novel architecture, we compiled a broad set of well-defined quantum circuits and performed an in-depth analysis based on multiple metrics such as gate overhead, depth overhead, and estimated success probability, which in turn allowed us to create unique mapping and architectural insights. Finally, we propose novel mapping techniques that could increase algorithm success rates on this architecture and potentially inspire further research on quantum circuit mapping for other scalable spin-qubit architectures.
In the era of noisy intermediate-scale quantum (NISQ) computing, the limited connectivity between qubits is one of the common physical limitations faced by current quantum computing devices. Quantum circuit mapping methods transform quantum circuits into equivalent circuits that satisfy physical connectivity constraints by remapping logical qubits, making them executable. The optimization problem of quantum circuit mapping has NP-hard computational complexity, and existing heuristic mapping algorithms still have significant potential for optimization in terms of the number of quantum gates generated. To reduce the number of SWAP gates inserted during mapping, the solution space of the mapping problem is represented as a tree structure, and the mapping process is equivalent to traversing this tree structure. To effectively and efficiently complete the search process, a beam search framework (BSF) is proposed for solving quantum circuit mapping. By iteratively selecting, expanding, and making decisions, high-quality target circuits are generated. Experimental results show that this method can significantly reduce the number of inserted SWAP gates on medium to large circuits, achieving an average reduction of 44% compared to baseline methods, and is applicable to circuits of various sizes and complexities.
Abstract In this work we propose a high-quality decomposition approach for qubit routing by swap insertion. This optimization problem arises in the context of compiling quantum algorithms formulated in the circuit model of computation onto specific quantum hardware. Our approach decomposes the routing problem into an allocation subproblem and a set of token swapping problems. This allows us to tackle the allocation part and the token swapping part separately. Extracting the allocation part from the qubit routing model of Nannicini et al. (Optimal qubit assignment and routing via integer programming, 2021, http://arxiv.org/abs/2106.06446 ), we formulate the allocation subproblem as a binary linear program. Herein, we employ a cost function that is a lower bound on the overall routing problem objective. We strengthen the linear relaxation by novel valid inequalities. For the token swapping part we develop an exact branch-and-bound algorithm. In this context, we improve upon known lower bounds on the token swapping problem. Furthermore, we enhance an existing approximation algorithm which runs much faster than the exact approach and typically is able to determine solutions close to the optimum. We present numerical results for the fully integrated allocation and token swapping problem. Obtained solutions may not be globally optimal due to the decomposition and the usage of an approximation algorithm. However, the solutions are obtained fast and are typically close to optimal. In addition, there is a significant reduction in the number of artificial gates and output circuit depth when compared to various state-of-the-art heuristics. Reducing these figures is crucial for minimizing noise when running quantum algorithms on near-term hardware. As a consequence, using the novel decomposition approach leads to compiled algorithms with improved quality. Indeed, when compiled with the novel routing procedure and executed on real hardware, our experimental results for quantum approximate optimization algorithms show an significant increase in solution quality in comparison to standard routing methods.
Quantum circuit mapping is a crucial process in the quantum circuit compilation pipeline, facilitating the transformation of a logical quantum circuit into a list of instructions directly executable on a target quantum system. Recent research has introduced a postcompilation step known as remapping, which seeks to reconfigure the initial circuit mapping to mitigate quantum circuit errors arising from system variability. As quantum processors continue to scale in size, the efficiency of quantum circuit mapping and the overall compilation process has become of paramount importance. In this work, we introduce a quantum circuit remapping algorithm that leverages the intrinsic symmetries in quantum processors, making it well suited for large-scale quantum systems. This algorithm identifies all topologically equivalent circuit mappings by constraining the search space using symmetries and accelerates the scoring of each mapping using vector computation. Notably, this symmetry-based-circuit-remapping algorithm exhibits linear scaling with the number of qubits in the target quantum hardware and is proven to be optimal in terms of its time complexity. Moreover, we conduct a comparative analysis against existing methods in the literature, demonstrating the superior performance of our symmetry-based method on state-of-the-art quantum hardware architectures and highlighting the practical utility of our algorithm, particularly for large-scale quantum computing.
Quantum compilation is a multi-pass process that translates a high-level circuit into an equivalent one executable on quantum hardware. A critical stage in this process is mapping, where additional gates are inserted to satisfy hardware constraints. Current mapping techniques often suffer from significant performance degradation—in terms of added gate count, increased circuit depth, and longer compilation times that scale with circuit size. In this work, we propose a novel methodology that enhances quantum compilation by leveraging concepts from Electronic Design Automation. Our approach partitions a quantum circuit into sub-circuits that can be compiled independently, and reformulates the mapping problem as a temporal floorplanning instance—a well-established technique in classical circuit design. We validate our method on widely used quantum circuit benchmark suites, achieving an average depth reduction of 22.05 % compared to traditional monolithic compilation chains using IBM Qiskit. Moreover, our approach reduces overall compilation time to that required for compiling the largest partition, while our partitioning-floorplanning algorithm runs, on average, two orders of magnitude faster than compiling the full circuit.
Quantum computers are superior to existing classical supercomputers in terms of run time for specific tasks, and various studies on quantum computers are in progress. Despite this, there is a significant gap in technology between available technologies and actual quantum computers on the noisy intermediate-scale quantum-scale. Currently, various quantum algorithms have been implemented and verified using quantum simulations. Therefore, the runtime performance of a quantum circuit can be verified in the same environment as a real quantum machine. A quantum compiler compiles quantum circuits. When a quantum circuit is compiled, logical qubits in a quantum circuit should be mapped to physical qubits, called qubit mapping. As qubit mapping is an NP-Complete problem, the compilation time increases exponentially according to the number of qubits. Therefore, various studies on effective qubit mapping techniques have been developed to accelerate the execution time. This paper proposes a new parallelized Qubit mapping algorithm. The proposed method consists of three-step processes: one circuit is divided into several circuits; the SABRE enhanced algorithm is executed on each circuit in parallel and then merged. The performance was evaluated using 10 benchmarks. The experimental results revealed an acceleration of up to 6.42x and an average speed up of 4.8x, with an average overhead of 1.03x in terms of the number of gates obtained. The proposed method outperformed the well-known modern qubit-mapping algorithm in terms of the execution time with exponential speedup improvement.