Quantum circuit mapping (QCM) is a crucial preprocessing step for executing a logical circuit (LC) on noisy intermediate-scale quantum (NISQ) devices. Balancing the introduction of extra gates and the efficiency of preprocessing poses a significant challenge for the mapping process. To address this challenge, we propose the mutual-influence-aware (MIA) heuristic method by integrating an initial mapping search framework, an initial mapping generator, and a heuristic circuit mapper. Initially, the framework utilizes the generator to obtain a favorable starting point for the initial mapping search. With this starting point, the search process can efficiently discover a promising initial mapping within a few bidirectional iterations. The circuit mapper considers mutual influences of SWAP gates and is invoked once per iteration. Ultimately, the best result from all iterations is considered the QCM outcome. The experimental results on extensive benchmark circuits demonstrate that, compared to the iterated local search (ILS) method, which represents the current state-of-the-art, our MIA method introduces a similar number of extra gates while achieving nearly 95 times faster execution.
Quantum circuit mapping (QCM) is a crucial preprocessing step for executing a logical circuit (LC) on noisy intermediate-scale quantum (NISQ) devices. Balancing the introduction of extra gates and the efficiency of preprocessing poses a significant challenge for the mapping process. To address this challenge, we propose the mutual-influence-aware (MIA) heuristic method by integrating an initial mapping search framework, an initial mapping generator, and a heuristic circuit mapper. Initially, the framework utilizes the generator to obtain a favorable starting point for the initial mapping search. With this starting point, the search process can efficiently discover a promising initial mapping within a few bidirectional iterations. The circuit mapper considers mutual influences of SWAP gates and is invoked once per iteration. Ultimately, the best result from all iterations is considered the QCM outcome. The experimental results on extensive benchmark circuits demonstrate that, compared to the iterated local search (ILS) method, which represents the current state-of-the-art, our MIA method introduces a similar number of extra gates while achieving nearly 95 times faster execution.
The qubit mapping approach serves to transform a quantum logical circuit (LC) into a physical one that satisfies the connectivity constraints imposed by the noisy intermediate-scale quantum (NISQ) devices. The quality of the physical circuit generated by a mapping approach depends largely on the initial mapping, which specifies the correspondence between the qubits in the LC and the qubits on the NISQ device. There are a total ofn!different initial mappings for a qubit mapping problem withnqubits, and among them, there is at least one initial mapping corresponding to the smallest physical circuit that this mapping approach can output. Finding such an initial mapping is very important for reliable computations on the NISQ device. To this end, we propose an iterated local search framework as well as a heuristic circuit mapper. In this framework, we perform multiple local searches on the space of initial mappings, and during each local search, several promising neighborhoods of the current initial mapping are generated and evaluated by invoking the circuit mapper in a forward or a backward manner. This framework provides a way for the qubit mapping approach to find the best physical circuit that it can produce, allowing it to trade time for circuit quality, which is necessary in the NISQ era. The experimental results demonstrate the stability, scalability, and effectiveness of this approach in reducing the number of additional gates. Moreover, although this approach is a multipass circuit mapping process, it can generate a good-quality physical circuit within half an hour, even for the circuit with more than 10 000 gates.
Quantum circuit mapping is an essential process required by executing quantum circuits using a noisy intermediate-scale quantum (NISQ) device. Since qubits and quantum gates of a NISQ device are error-prone and variable in quality, it is crucial to choose qubits or quantum gates in a variation-aware manner to maximize the success rate of executing circuits. To this end, this article proposes a variation-aware method for quantum circuit mapping through the cooperation of multiple agents. Each agent in the proposed method can gradually construct a physical circuit that respects the device's connectivity constraints by inserting a SWAP gate at each step. Moreover, at each step, the circuit information of each agent is shared within the agent population through a communication mechanism that combines global and local information exchange, so that agents with poor fitness can get an opportunity to improve their physical circuits. The experimental results on extensive benchmark circuits confirm that the proposed method can effectively and consistently improve the overall circuit fidelity compared with the state-of-the-art methods.
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.
Mapping logical quantum circuits to Noisy Intermediate-Scale Quantum (NISQ) devices is a challenging problem which has attracted rapidly increasing interests from both quantum and classical computing communities. This article proposes an efficient method by (i) selecting an initial mapping that takes into consideration the similarity between the architecture graph of the given NISQ device and a graph induced by the input logical circuit and (ii) searching, in a filtered and depth-limited way, a most usefulswapcombination that makes executable as many as possible two-qubit gates in the logical circuit. The proposed circuit transformation algorithm can significantly decrease the number of auxiliary two-qubit gates required to be added to the logical circuit, especially when it has a large number of two-qubit gates. For an extensive benchmark set of 131 circuits and IBM's current premium Q system, viz., IBM Q Tokyo, our algorithm needs, in average, 0.3801 extra two-qubit gates per input two-qubit gate, while the corresponding figures for three state-of-the-art algorithms are 0.4705, 0.8154, and 1.0066, respectively.
Quantum algorithm design usually assumes access to a perfect quantum computer with ideal properties like full connectivity, noise-freedom, and arbitrarily long coherence time. In noisy intermediate-scale quantum (NISQ) devices, however, the number of qubits is highly limited and quantum operation error and qubit coherence are not negligible. Besides, the connectivity of physical qubits in a quantum processing unit (QPU) is also strictly constrained. Thereby, additional operations like SWAP gates have to be inserted to satisfy this constraint while preserving the functionality of the original circuit. This process is known as quantum circuit transformation. Adding additional gates will increase both the size and depth of a quantum circuit and, therefore, cause further decay of the performance of a quantum circuit. Thus, it is crucial to minimize the number of added gates. In this article, we propose an efficient method to solve this problem. We first choose by using simulated annealing an initial mapping which fits well with the input circuit and then, with the help of a heuristic cost function, stepwise apply the best-selected SWAP gates until all quantum gates in the circuit can be executed. Our algorithm runs in time polynomial in all parameters, including the size and the qubit number of the input circuit, and the qubit number in the QPU. Its space complexity is quadratic to the number of edges in the QPU. The experimental results on extensive realistic circuits confirm that the proposed method is efficient and the number of added gates of our algorithm is, on average, only 57% of that of state-of-the-art algorithms on IBM Q20 (Tokyo), the most recent IBM quantum device.
In the era of noisy intermediate-scale quantum (NISQ), a quantum logical circuit must undergo certain compilation before it can be used on a NISQ device, subject to connectivity constraints posed by NISQ devices. During compilation, numerous auxiliary quantum gates are inserted, but a circuit with too many is unreliable, necessitating gate minimization. This requirement gives rise to the qubit mapping problem (QMP), an NP-hard optimization problem that is critical in quantum computing. This work proposes a novel and effective local search algorithm dubbedEffectiveQM. First,EffectiveQMproposes a new mode-aware search strategy to alleviate the challenge of being trapped in local optima, where local search typically suffers. Moreover,EffectiveQMintroduces a novel potential-guided scoring function, which can thoroughly quantify the actual benefit brought by an operation of inserting auxiliary gates. By incorporating the potential-guided scoring function,EffectiveQMcan effectively determine the appropriate operation to be performed. Extensive experiments on a diverse collection of logical circuits and 6 NISQ devices demonstrate thatEffectiveQMcan generate physical circuits with significantly fewer inserted auxiliary gates than current state-of-the-art QMP algorithms, indicating thatEffectiveQMgreatly advances the state of the art in QMP solving.