A Heuristic Qubit Placement Strategy for Nearest Neighbor Realization in 2D Architecture

Abstract

Recently, quantum computing has received massive attention of the researchers due to the advantages it offers in solving some problems efficiently compared to conventional computing. But there are several design challenges that need to be satisfied for various quantum technologies to perform reliable quantum operation. One such essential requirement demands to maintain the neighborhood organization of the operating qubits, referred to as the nearest neighbor (NN) constraint. This can be settled through insertion of SWAP gates which helps to synthesize a NN-compliant design by exchanging the positions of the qubits. Consequently, the cost overhead of the circuit enhances due to SWAP gate insertion as the number of gates in the circuit increases, thereby exploitation of various approaches to address this issue has turned out to be essential of late.

In this regard, here we have introduced an improved heuristic design approach for the synthesis of a two dimensional NN-compliant circuit with reduced cost overhead. The approach has been executed in three phases of qubit selection, qubit placement and SWAP gate insertion. Initially, the qubits have been chosen for placement based on some cost metric estimation and then organized them on the grid locations in a specific order in the second phase. Lastly, SWAP gate insertion phase has been exercised to make qubits adjacent. It has been observed that our method has performed comparatively better than the previous works after carrying out experimental evaluations over a wide range of benchmark specifications.

1 Introduction

Quantum computing has made a tremendous landmark in the computing paradigm because of its capability of solving some specific problems in polynomial time. Some of the applications that have turned out to be beneficial for quantum computation are factorization in RSA cryptosystem [1], database search [2], discrete logarithm etc. over conventional computation. Subsequently, a massive interest has been generated among the researchers for the development of a small scale quantum computer in the last decade. In this conjecture, design of quantum algorithms for the practical realization of quantum computer in terms of quantum circuits has turned out to be significant. Quantum circuits manipulate quantum information represented in the form of qubits than as bits used in the conventional computing paradigm. Qubits are similar to bits except that it can also exist in multiple states that can be considered as the linear combination of the basis states. In quantum circuit, a sequence of quantum gates basically operates on the qubits and subsequently transforms it into a different state during quantum information processing. It has been witnessed through experimental observations that the qubits are susceptible to changes due to environmental disturbances or noises that might result in computational errors. In order to overcome this issue, the interactions between the interacting qubits should be made adjacent so as to ensure the computational accuracy. This has been considered as the necessary criteria for the synthesis of several quantum technologies like ion trap [3], nuclear magnetic resonance [4], quantum dots [5] and superconducting qubits [6]. In order to bring the interacting qubits close to each other, a standard way of applying SWAP gates in the original circuit has been followed to satisfy the design constraints for the quantum technologies. Basically, SWAP gate exchanges the states of the qubits rather than its magnitude to bring the non-adjacent qubits close to each other. Consequently, such an operation induces some circuit design issues in the form of increase in circuit depth and quantum cost of the resultant NN based circuit. As a result, optimizing the NN based design by using less number of SWAP gates has turned out an essential design challenge for the researchers. They have attempted to fulfil this design issue by exploiting several design methodologies as discussed next.

Several design strategies have been suggested for linear arrangement of qubits in 1D format, where they can communicate with at most two adjacent neighbours. In [7], the authors mapped the NN based design problem into a task assignment one and applied harmony based search technique to solve the equivalent problem. To obtain a better design, a unique technique based on 1D arrangement of qubits has been introduced in [8], which emphasized on using limited number of SWAP gates. By mapping the qubits on a lattice structure not only reduces the SWAP gate count but also the technique becomes feasible for large benchmarks that have been undertaken in the work [9]. In [10], an NN based design has been optimized by constructing an interaction graph for the corresponding problem and then subsequently optimized it by employing a look-ahead policy. A graph-partitioning based approach has been presented in [11] to realize an NN based circuit with reduced cost overhead. An improved NN based design has been synthesized by employing an efficient conversion technique is discussed in [12]. As heuristic approach does not provide an optimal solution, so an exact approach based on SAT solvers has been implemented by Robert et al. [13] to synthesize an optimal NN based design but consumed substantial amount of time to process large benchmark circuits. A much improved design compared to the optimal one can be achieved by transforming the circuit representation from 1D format to 2D structure. As the number of interacting neighbours rises from 2 to 4, has resulted in a better cost effective design. Several works pertaining to 2D representation has been declared of late.

To realize an improved NN based design compared to the linear based designs, a mixed integer programming approach for mapping the qubits on a grid has been reported in [14]. Lye et al. [15] exercised an exact search strategy to derive an optimal solution for small sized benchmarks as it was not applicable for larger benchmarks due to extensive computational cost. In [16], the authors presented a meta-heuristic approach for the realization of an efficient NN-compliant design. To obtain an improved and scalable design, a heuristic qubit placement scheme has been employed for mapping the qubits on a grid location based on the degree of interactions has been summarized in the work [17]. To optimize the NN design further, another heuristic approach based on look-ahead policy has been introduced by Robert et al. [18], where SWAP gates have been reduced extensively. For better placement of qubits in the grid structure, a priority based ordering strategy has been followed by the authors of [19]. In addition to 2D design synthesis, mapping of circuits in 3D configuration has been demonstrated in one of the recent works [19]. Although representation of circuits in 3D platform provides a better cost-effective design than in 2D format as the number of adjacent neighbours of qubits escalates to 6 but at the same time controlling of such qubit representation becomes a cumbersome problem compared to 2D orientation of qubits.

In this work, we have presented a design synthesis approach for 2D representation of any quantum circuit. The primary intention of the design strategy is to obtain a cost effective NN based design by reducing the SWAP gate count. In this conjecture, our design policy has been executed in three phases for the realization of a 2D NN-complaint circuit. We have conducted a comprehensive experimental analysis over a number of different benchmarks and the resulting observations are recorded in the result tables, which suggest that our strategy has performed reasonably well than the reported 2D works regarding NN based optimization of 2D quantum circuits.

The remaining portion of the paper has been organized as follows. Section 2 discusses about the preliminaries of quantum computation and nearest neighbour criteria. Discussion of our design methodology and experimental evaluations has been presented in Sects. 3 and 4 respectively. Finally, we conclude the paper in Sect. 5.

2 Background

A qubit represents the basic unit of information acted upon by a set of elementary quantum gates constituting a quantum circuit. These quantum information units can be found in either one of the basis states of $\left| 0 \right\rangle$, $\left| 1 \right\rangle$ or in other states which can be expressed as the combination of the basis states by means of a state vector as

$$ \left|\upvarepsilon \right\rangle =\upalpha\left| 0 \right\rangle +\upbeta\left| 1 \right\rangle $$

(1)

where α and β represents the probability amplitudes of the basis states $\left| 0 \right\rangle$ and $\left| 1 \right\rangle$ satisfying the condition α² + β² = 1. To have a better interpretation about the concepts, we have introduced some fundamental terminologies related to quantum computing and nearest neighbor constraint.

Definition 1:

A quantum circuit consists of a set of elementary quantum gates that perform manipulation on qubits to implement a specific function.

Generally, quantum gates from various quantum gate libraries are exercised to implement a quantum algorithm. Some of the most commonly used libraries are NCV, NCVW, Clifford +T group [20,21,22,23] for the logical representation of any specific function. However, in the present work we have restricted our investigation only on gate level representations from NCV library. Basically, the quantum gate operations can be represented as 2ⁿ × 2ⁿ transformation matrices. These transformation matrices are all unitary in nature that operates on the states of the input qubits. Table 1 represents some of the basic quantum gates along with their corresponding symbolic representation as summarized below.

Table 1. Some basic quantum gates and their symbolic representations

Despite, quantum circuits are used to realize the Boolean functions in their gate level representation but there are some physical constraints that need to be fulfilled for the realization of such circuits. One such major criterion is to accomplish the neighborhood arrangement of qubits to enable the so-called nearest neighbor property. This is considered as one of the essential design criteria for the synthesis of efficient quantum circuit representation. To address this design challenge, a solution of SWAP gate insertion (diagrammatically represented in Fig. 1) is being followed to attain the nearest neighbor property.

Fig. 1.

SWAP gate representation

Definition 2:

The interaction distance between the positions of the control (c) and target (t) qubits of any 2-qubit gates (G) represents the nearest neighbor cost (NNC) and it can be expressed mathematically as NNC_G = |c – t| + 1, where NNC_G denotes the NNC of any 2-qubit gate.

To determine the NNC for the entire circuit (NNC_C), an overall sum for all the 2-qubit gates in the given circuit (C) is computed. A quantum gate is said to satisfy the nearest neighbor constraint if it is either a 1-qubit gate or for 2-qubit gates the NNC, NNC_G = 0.

Definition 3:

SWAP gate is a 2-qubit gate that acts on qubits q_a, q_b and interchanges the states than values of these qubits. For instance it acts on qubits q₇, q₉ and transforms them from the state (q₁, q₂,…,q₇, q₈, q₉,…,q₂₀) to (q₁, q₂,…,q₉, q₈, q₇,…,q₂₀).

Example 1:

The circuit depicted in Fig. 2(a) does not satisfy the NN design criteria as the interaction distance of all the 2-qubit gates is having a positive numeral (interacting qubits are not placed adjacent). The corresponding NN based design of Fig. 2(a) has been obtained by adding SWAP gates before each of the non-adjacent gates as shown in Fig. 2(b). It is evident from Fig. 2(b) that 14 SWAP gates have been incorporated to accomplish the NN-compliant design of the circuit of Fig. 2(a).

Fig. 2(a).

Original circuit with NNC = 7

Fig. 2(b).

NN based design of Fig. 2(a)

Though we have attained the equivalent NN design of the original circuit by means of SWAP insertion but still a room for improving the design further exists by projecting the entire circuit representation into 2D platform. Such higher dimensional representation facilitates to obtain a better design compared to 1D platform as less SWAP gates are required to derive the equivalent NN design of the given circuit.

A quantum circuit can be projected into a 2D format by organizing the qubits on a grid structure rather than organizing in a linear fashion. In way, the communication between the neighbors in such a representation enhances due to higher number of adjacent neighbors results in a lesser use of SWAP gates. Several possible 2D configurations exist in which the qubits can be mapped on the grid structure. Lets consider the circuit of Fig. 2(a) where the qubits are arranged linearly but several choices exists to represent the corresponding circuit in 2D format is represented in Fig. 3. Different configurations may influence the neighborhood organization of the qubits that in turn affects the nearest neighbor criteria.

Fig. 3.

Possible grid configurations for qubit mapping in 2D layout

The circuit in Fig. 2(a) has been transformed into a 2D structure by positioning the qubits in a 2 × 2 grid structure as depicted in Fig. 4(a) and the corresponding NN based design is shown in Fig. 4(b). We observe that only a single SWAP gate is required to obtain the NN design in 2D platform compared to 14 SWAP gates needed for the same circuit in 1D representation.

Fig. 4(a).

Quantum circuit of Fig. 2(a) is represented in 2D layout

Fig. 4(b).

2D NN-compliant realization of Fig. 4(a)

3 Proposed Technique

Here, we have discussed about our proposed approach exercised for the purpose of designing of NN-compliant quantum circuit in 2D configuration. In order to attain the NN-compliant nature of any given circuit, the method initially arranges the qubits in the grid locations and then finally applies SWAP gates to bring any two non-neighboring interacting qubits operating over a quantum gate close to each other. In this context, we have implemented a qubit selection and placement strategies followed by SWAP gate insertion method to achieve the NN-compliant design of a given circuit are described next.

3.1 Qubit Selection Approach

In the present section, we have applied a heuristic technique that determines the sequence in which the qubits are preferred for placement in the grid location. In this regard, we have performed a number of calculations to derive the order in which the qubits are to be placed in a grid structure. Initially, we have estimated the time interval of interactions for each qubit by estimating the difference between the start and end time instants and recorded the same in a time span table (see Table 2) for the given circuit (see Fig. 5). From the time span table, we have computed the cost impact table (see Table 3) in which the cost factor of each qubit over their respective time intervals (obtained from the time span table) has been determined. In other words, the total nearest neighbor costs contributed by each qubit has been estimated. For instance, qubit q₁ interacts at the first, fourth, sixth and seventh time units of the given circuit (see Fig. 5) and contributes a cost of 2, 1, 1 and 2 (Total cost = 2 + 1 + 1 + 2 = 6) at the respective gate positions. Finally, the cost impact table has been sorted in a descending order based upon the cost factors and stored in a qubit order table (see Table 4) that determines the order in which the qubits are to be selected for placement in a 2D grid. It has been observed that the qubits q₁, q₄ have same cost factor but q₁ has been given higher priority for selection over q₄ (see Table 4) as q₁ has the least time interval compared to the one of q₄. Therefore, q₁ has been placed before q₄ in the qubit order table.

Table 2. Time span table

Fig. 5.

Quantum circuit

Table 3. Cost impact table

Table 4. Qubit order table

3.2 Qubit Placement Technique

In this phase, a qubit placement strategy has been executed after determining the order in which the qubits are to be arranged in a grid structure obtained in the previous phase. In way, the placement strategy organizes the qubits in a grid in the order in which they appear in the qubit order table. After obtaining the qubit order table, the placement strategy places the highest priority qubit in the centre of the grid. Then the rest of the qubits are selected from the order table and placed them around the location of the highest priority qubit by following the order viz. right, top, left, bottom depending upon the availability of space as explained in Algorithm 1. In our case, the qubit q₁ has been chosen for placement in a 2D grid as it is having the highest priority for selection compared to other qubits (see Table 4) and placed it in the centre of the grid (see Fig. 6(a)). Then, the next qubit q₄ is chosen from Table 3 and placed it on the right of the location of q₁ since it is empty (see Fig. 6(b)). Now, we select the qubit appearing after q₄ viz. q₂ from the order table and checks whether the cell on the top of q₁ is available or not. Due to its availability, qubit q₂ has been allocated on the top of the location of q₁ (see Fig. 6(c)). Similarly, the last occurring qubit q₃ has been placed on the left of q₁ (see Fig. 6(d)).

Fig. 6(a).

Placing qubit q₁ in the center of the grid

Fig. 6(b).

Placing qubit q₄ on the right of q₁

Fig. 6(c).

Placing qubit q₂ on the top of q₁

After allocating all the qubits from the qubit order table on the grid locations, finally SWAP gates are incorporated to bring the positions of any two interacting qubits close to each other to enable the nearest neighborhood property for the given circuit is illustrated next.

Algorithm 1 describes about the process of arrangement of qubits in a 2D grid by selecting qubits from the qubit order table.

3.3 SWAP Gate Insertion

Here, SWAP gates are being utilized to obtain the NN-compliant design for the quantum circuit represented in Fig. 5.

For this purpose, we have examined each individual gate in the circuit to investigate whether its operating qubits are placed adjacent or not and subsequently inserted SWAP gates to alter the positions of the qubits of the corresponding non-adjacent gate in such a manner so that its interacting qubits approach towards each other and finally becomes adjacent. We have considered the grid obtained in the previous phase (see Fig. 6(d)) as input of this phase and applied SWAP gates wherever we find any gate whose qubits are not adjacent by traversing the circuit from the left. The entire process of SWAP gate insertion for the circuit of Fig. 5 is represented in Fig. 7.

Fig. 6(d).

Placing qubit q₃ on the left of q₁

Fig. 7.

SWAP gate insertion process

To understand the methodology more clearly, we have further illustrated the entire transformation process by considering a benchmark circuit as discussed next (Fig. 8(a), 8(b) and 8(c)).

Fig. 8(a).

Example benchmark (4gt11_84)

Fig. 8(b).

Placement of qubits from qubit order table

Fig. 8(c).

SWAP gate insertion

Example 2:

Let’s consider the NN-complaint transformation process of a benchmark circuit “4gt11_84” in this example. All the associated computational stages have also been summarized (Tables 5, 6 and 7).

Table 5. Time span table

Table 6. Cost impact table

Table 7. Qubit order table

4 Experimental Results

We have implemented the proposed method in C and executed on a system with configurations of intel5 processor, 3.30 GHz clock and 4 GB RAM. Experimental analysis has been carried out on various benchmark functions available on [24] as shown in Tables 8 and 9 respectively. Table 8 represents the experimental evaluations performed over small and medium size benchmarks (up to 16 qubits) while Table 9 represents the results carried out over large size benchmarks (more than 16 qubits).

Table 8. Improvements in SWAP gates over existing 2D works

Table 9. Results for large size benchmarks

We have performed a detailed evaluation over SWAP gate count and compared the results with some of the related 2D works as represented in the result table. After analyzing the result table, we observe that our methodology organizes the qubits in an efficient manner such that less number of SWAP gates is used than the ones used in existing works.

5 Conclusion

Here, we have implemented a heuristic design strategy for arranging qubits in a 2D structure so as to obtain the NN based design of a given circuit. To this end, we have segmented the design strategy into three phases of qubit selection followed by qubit placement and lastly applying SWAP insertion technique. Such application of heuristic policy for determining a suitable qubit placement leads to faster execution. We have evaluated the SWAP gate count for different benchmark functions and witnessed significant improvements over the related works.

Though, we have achieved better results over the reported works, but these are far from optimal due to the application of heuristic based design policy thereby we would investigate better design policies so as to obtain optimal or near optimal results in the future.