In order to achieve speedup over conventional classical computing for finding solution of computationally hard problems, quantum computing was introduced. Quantum algorithms can be simulated in a pseudo quantum environment, but implementation involves realization of quantum circuits through physical synthesis of quantum gates. This requires decomposition of complex quantum gates into a cascade of simple one qubit and two qubit gates. The methodological framework for physical synthesis imposes a constraint regarding placement of operands (qubits) and operators. If physical qubits can be placed on a grid, where each node of the grid represents a qubit then quantum gates can only be operated on adjacent qubits, otherwise SWAP gates must be inserted to convert non-Linear Nearest Neighbor architecture to Linear Nearest Neighbor architecture. Insertion of SWAP gates should be made optimal to reduce cumulative cost of physical implementation. A schedule layout generation is required for placement and routing apriori to actual implementation. In this paper, two algorithms are proposed to optimize the number of SWAP gates in any arbitrary quantum circuit. The first algorithm is intended to start with generation of an interaction graph followed by finding the longest path starting from the node with maximum degree. The second algorithm optimizes the number of SWAP gates between any pair of non-neighbouring qubits. Our proposed approach has a significant reduction in number of SWAP gates in 1D and 2D NTC architecture.
In order to achieve speedup over conventional classical computing for finding solution of computationally hard problems, quantum computing was introduced. Quantum algorithms can be simulated in a pseudo quantum environment, but implementation involves realization of quantum circuits through physical synthesis of quantum gates. This requires decomposition of complex quantum gates into a cascade of simple one qubit and two qubit gates. The methodological framework for physical synthesis imposes a constraint regarding placement of operands (qubits) and operators. If physical qubits can be placed on a grid, where each node of the grid represents a qubit then quantum gates can only be operated on adjacent qubits, otherwise SWAP gates must be inserted to convert non-Linear Nearest Neighbor architecture to Linear Nearest Neighbor architecture. Insertion of SWAP gates should be made optimal to reduce cumulative cost of physical implementation. A schedule layout generation is required for placement and routing apriori to actual implementation. In this paper, two algorithms are proposed to optimize the number of SWAP gates in any arbitrary quantum circuit. The first algorithm is intended to start with generation of an interaction graph followed by finding the longest path starting from the node with maximum degree. The second algorithm optimizes the number of SWAP gates between any pair of non-neighbouring qubits. Our proposed approach has a significant reduction in number of SWAP gates in 1D and 2D NTC architecture.
Synthesis and optimization of quantum circuits have received significant attention from researchers in recent years. Developments in the physical realization of qubits in quantum computing have led to new physical constraints to be addressed. One of the most important constraints that is considered by many researchers is the nearest neighbor constraint which limits the interaction distance between qubits for quantum gate operations. Various works have been reported in the literature that deal with nearest neighbor compliance in multi-dimensional (mostly 1D and 2D) qubit arrangements. This is normally achieved by inserting SWAP gates in the gate netlist to bring the interacting qubits closer together. The main objective function to minimize here is the number of SWAP gates. The present paper proposes an efficient qubit placement strategy in a three-dimensional (3D) grid that considers not only qubit interactions but also the relative positions of the gates in the circuit. Experimental evaluation on a number of benchmark circuits show that the proposed method reduces the number of SWAP gates by 16.2% to 47.0% on the average as compared to recently published works.
In some practical quantum physical architectures, the qubits need to be distributed on 2-dimensional (2-D) grid structure to implement quantum computation. In order to map an 1-dimensional (1-D) quantum circuit into a 2-D grid structure and satisfy the nearest neighbor constraint of qubit interaction in the grid structure, a mapping method from 1-D quantum circuit to 2-D grid structure is proposed in this paper. This method firstly determines the order of placing qubits, and then presents the layout strategy of qubits in 2-D grid. We also proposed an algorithm for establishing interaction paths between non-adjacent qubits in 2-D grid structure, which can satisfy the physical constraints of the interaction of quantum bits in the grid in the process of mapping an 1-D quantum circuit to a 2-D grid structure. For some benchmark circuits, after using the method of this paper to place qubits, it is possible to make every 2-qubit gate in the circuit have a nearest neighbor, so that there is no need to use SWAP gate to establish channel routing. Compared with the latest available methods, the average optimization rate is 82.38%.
In the last few years, tremendous improvement in the field of quantum computing has been witnessed. Although quantum technologies such as ion-trap, NMR, quantum dots have emerged as the promising platforms for implementing quantum circuits but these technologies have faced several design issues. One such important design problem is the nearest neighbor condition, which requires the qubits to interact with adjacent neighbors. This problem can be addressed by adding SWAP gates in the circuit. By doing so, the overhead in the circuit increases thus NN designs with minimum number of SWAP gates need to be developed. Focusing on this, here, in this work, we introduce a heuristic design method for efficient NN realization of quantum circuits in 2D architecture. Our NN transformation process is carried out in two phases, where initially in the first phase, the input circuit is mapped to 2D configuration using a qubit placement strategy and then in the second phase NN designs are obtained through SWAP gate insertion. At the end, the design algorithm has been evaluated over a large set of benchmark functions and the results are compared with some of the existing works. From this comparison, it is seen that our proposed method performs better than the reported works.
Abstract In some quantum technologies, an interaction is only allowed between physically adjacent qubits, hence the nearest-neighbor requirement is needed. In such technologies, quantum gates are limited to operate on adjacent qubits. To make a quantum circuit compliant with the nearest-neighbor requirement, SWAP gates are inserted into the circuit to move the interacting qubits of a gate to be adjacent to each other. The mapping of qubits on the physical environment has an important role on reducing the number of SWAP gates and thus the circuit latency. Focusing on this issue, in this paper, a method is proposed that maps a quantum circuit onto a 3D physical hardware such as a 3D optical lattice. A new methodology for this mapping problem is proposed based on a complex network spectral clustering algorithm and graph theory, which are suitable for very large scale networks. It includes three steps: finding the order of qubit mapping, placing physical qubits, and routing. Simulation results show that the proposed mapping approach not only decreases the average number of SWAP gates by about 37% but also improves the average runtime by about 87% for the 2D architecture compared to PAQCS. Moreover, it reduces the average number of SWAP gates for the 3D architecture by 17.1% compared to the best studies in the literatures.
In recent years, quantum computing has received extensive attention for its superior efficiency and application potential. For some physical architecture, one qubit can only interact with its adjacent qubits, SWAP gates are inserted to make a quantum circuit nearest neighbor compliant. The initial qubit placement algorithm in a 2D grid structure is proposed based on the constructed interaction cost metric model, and the method of dynamic grid decision is given. In order to obtain a better way of inserting SWAP gates, the gate level and circuit level interaction routing policies are put forward, and a heuristic pruning of interaction routing records is employed so as to reduce the runtime and additional quantum cost. Experimental results show that our proposed methods can achieve better performance than existing methods, and the average optimization rate of quantum cost is 21.76% and 17.23% respectively.