Keywords

1 Introduction

Quantum computing has drawn the attention of researchers over several decades. Unlike conventional binary logic systems that manipulate bits, quantum systems manipulate qubits that can exist as a state of superposition: \(\phi = \alpha |0 \rangle + \beta |1 \rangle \), where \(|\alpha |^2 + |\beta |^2 = 1\). Qubits can be implemented using technologies like ion-trap [1], photonics [4], nuclear magnetic resonance [3], etc. In some technology like ion-trap, the operation requires that the interacting qubits must be adjacent to each other known as the Nearest Neighbor Constraint. This is achieved by inserting an appropriate number of SWAP gates for nearest neighbor compliance. Several works have been proposed for arranging qubits in 1D [2, 5, 6] and 2D [7,8,9] architectures where the main aim is to minimize the number of SWAP gates. 2D architectures require fewer number of SWAP gates for NNC. In this paper, a heuristic procedure for mapping qubits to a 2D grid is proposed, which considers gate position, degree of lookahead and strength of interaction among qubits.

The paper is organized as follows. Section 2 explains the proposed method and steps of algorithm using examples. In Sect. 3, experimental results and comparison with previous works have been presented followed by concluding remarks in Sect. 4.

2 Proposed Method

This section presents a qubit placement and SWAP gate insertion approach to make a quantum circuit NNC. This is based on a lookahead strategy that considers the frequency of occurrence of gates and their relative positions. Given the lookahead value LA, a window of LA gates \(C=g_i g_{i+1} g_{i+2} \ldots g_{(i+LA-1)}\) is analyzed to determine the most interactive and frequently occurring qubits in the block. A data structure as shown in Fig. 1 is constructed for each qubit consisting of their interacting qubits, number of interactions and gate numbers. Using this structure, an interaction table is created as shown in Tables 1(a) and (b), from which the priority of the qubits is determined. Having the qubit priority list as in Table 1(g), qubit placement in the 2D grid as explained by Algorithm 1 is carried out such that the highest priority qubit is placed at the center and its interacting qubits are placed around it in the order <bottom, right, top, left>. Using the 2D grid, appropriate number of SWAP gates are inserted before the gate to bring the interacting qubits adjacent to each other and the new position of the qubit is retained. Finally, the total number of SWAP gates is counted and recorded. The same process is repeated for the next block of LA gates and also for the pair of blocks combined. This method is applied to other blocks of the same circuit and for different values of LA, and the configuration with minimum SWAP gate count is chosen as the best.

Fig. 1.
figure 1

Data structure of 1st block

Full size image

2.1 The Proposed Algorithm

Knowing the LA value, different blocks of the circuit are defined by scanning the circuit from left to right. For each block, data structure and priority table are constructed and placement of the qubits in the 2D grid is performed (see Algorithm 1). Firstly, a qubit from the qubit priority table is selected and placed in the grid followed by its interaction qubits as shown in Fig. 2. If the qubit is already present, nothing is done. Initially it checks if the cell is empty; if not, it checks the next cell for space availability. This process is repeated until it finds an empty cell and inserts the qubit. Next SWAP gates are inserted as needed. Lastly the number of SWAP gates is calculated and recorded.

figure a
Table 1. Illustration for the first block. (a) Random Interaction Table, (b) Interaction Table (after sorting), (c) Qubit Table, (d) Qubit Table (after sorting based on maximum interactions), (e) Qubit Table (after sorting the gate numbers), (f) Qubit Table with time interval, (g) Qubit Priority Table
Full size table

2.2 Illustrative Example

Consider the benchmark circuit 4gt4-v0_80 that consists of 6 qubits and 44 gates. We illustrate the steps of qubit mapping for \(LA=8\). In the first invocation of the lookahead mechanism the block will consist of the first 8 gates. In the second call it will consist of the next 8 gates, and in the last call it will consist of all the 16 gates. In the first invocation a data structure as shown in Fig. 1 is constructed to find out the interacting qubits, the number of interactions and gate numbers where they interact within this block. Then a random interaction table is created by filling it randomly as shown in Table 1(a).

This random priority table is then sorted based on the interactions to get Table 1(b). If there is more than one gate with the same interacting qubits then we keep a record of just one gate, sum up the interactions, append the gate numbers and sort it again. Using the modified priority table, for each qubit, we calculate the total interactions and record all the gate numbers as shown in Table 1(c) followed by sorting as in Table 1(d). Next, the gate numbers of each qubit are sorted in ascending order as in Table 1(e). From this table, the qubits, their total interactions, the gate numbers, and the interval between the gates of each qubit is calculated as shown in Table 1(f). It is seen that qubits a2, a3 and a5 have four interactions but their frequencies of interaction are different. So qubit with the least time interval gets the highest priority, viz. a2, as seen in Table 1(g). Lastly, the circuit is scanned again to check if any qubit not in the block is left unfilled in the qubit priority table. If so, the qubit is appended in the table. Using this priority table, qubit placement is done as Algorithm 1 and illustrated in Fig. 2.

After qubit placement is completed in a 2D grid, SWAP gates insertion is performed. The process is illustrated for a benchmark 4gt11_84 that have five qubits, one of which (viz. \(a_4\)) is not involved in any gate interactions. The steps are shown in Fig. 3 which requires 2 SWAP operations.

Fig. 2.
figure 2

Qubit placement of 1st block

Full size image
Fig. 3.
figure 3

Swap gate insertion

Full size image
Table 2. Improvements in SWAP gates of 2D qubit placement over [7,8,9]
Full size table

3 Experimental Results

The proposed method has been implemented in C and run on a core-i5 based desktop with 4 GB of RAM. Experiments have been carried out on NCV benchmarks that was used in [7,8,9] and results are shown in Table 2 along with previous results. The first two columns represent the benchmark name and number of qubits (n). SWAP gates count (swap) observed in [8] is presented next followed by number of SWAP gates for joint lookahead (\(swap_\bigtriangleup \)) and iterative lookahead (\(swap_\bigtriangledown \)) reported in [9] in the next two columns respectively. After this, SWAP gate count of [7] is presented. In the next three columns, SWAP gate count of proposed approach (swap), LA value and 2D configuration (grid) are reported. The last four columns show the % improvement of the proposed approach over [7,8,9]. On an average improvements of \(22.4\%\) (\(53.2\%\) in the best case) over [8], \(3.3\%\) and \(36.1\%\) (\(31.3\%\) and \(70.3\%\) in the best case) over joint and iterative lookahead strategy from [9], and \(32.4\%\) (\(54.2\%\) in the best case) over [7] are observed.

4 Conclusion

In this work, a new lookahead approach for qubit placement in a 2D grid to minimize the number of SWAP gates for NN-compliance is proposed. Prioritization of the qubits has been worked out to determine which qubit should be placed earlier by considering the qubit’s number of interactions and position in the circuit. The most frequent qubit with less interval gets a higher priority. The results obtained are found to be better than those reported in existing works.