1 Introduction

Quantum computation [1] exploits quantum mechanical phenomena such as superposition, entanglement, etc. and utilizes qubits rather than conventional bits for computation. This allows for solving many practically relevant problems much faster than with conventional circuits. Prominent examples include problems such as factorization (for which Shor’s algorithm [2] has been proposed) or database search (for which Groover’s iteration [3] has been proposed). While first corresponding quantum circuits have been developed by hand, the design of more complex quantum functionality will require automatic methods – motivating the research in Computer-Aided Design (CAD) for quantum circuits. Since each quantum computation is inherently reversible, methods for the design of reversible circuits are frequently utilized for this purpose.

This led to the development of first CAD methods e.g. for the synthesis of reversible circuits [4–12], the corresponding mapping to quantum circuits [13–16], or design schemes which directly address quantum circuit synthesis [17–21]. Besides that, physical constraints and how to already consider them during the design phase has received increasing attention. In particular, the satisfaction of so-called nearest neighbor constraints was an objective of recent developments. Here, the interaction distance between the involved qubits is limited and it is required that computations are performed between adjacent, i.e. nearest neighbor, qubits only. Corresponding CAD-methods addressing this restriction have been proposed e.g. in [22–27].

In this work, we consider the global reordering scheme as employed in [22, 26, 27] whose main idea is to determine a qubit order which – applied through the entire circuit – yields the smallest nearest neighbor costs. This often provides the basis for further optimization steps and, hence, constitutes an important part of nearest neighbor optimization. However, since determining the best possible qubit order requires the consideration of n! possible permutations (where n is the number of qubits), existing solutions either

  • apply a heuristic which aims for generating a single, dedicated permutation only which, in many cases, is far from optimal or

  • apply an exact approach which guarantees an optimal solution but suffers from the underlying complexity.

Motivated by this, we are considering the research question how to optimize heuristic global reordering in order to generate nearly-optimal results while, at the same time, remaining efficient. To this end, we propose the utilization of Permutation Decision Diagrams (\(\pi \)DDs, [28]) – a data-structure for the efficient representation and manipulation of sets of permutations. Using \(\pi \)DDs it is possible to consider all permutations at once in an efficient fashion and to subsequently reduce them with respect to the nearest neighbor constraints. This provides an ideal compromise between the existing solutions which directly worked towards a single permutation only and, hence, likely excluded better options or had to deal with an inefficient handling of the complexity. Experimental evaluations confirm the benefits of the proposed approach: In all cases, optimal or almost optimal results are generated in a fraction of the runtime needed for the exact approach.

The remainder of this work is structured as follows: Sect. 2 reviews the background on quantum circuits and nearest neighbor optimization, while Sect. 3 reviews the corresponding optimization methods. These sections build the motivation of the proposed approach whose general idea is afterwards presented in Sect. 4. Then, details on the solution are presented in Sect. 5. Finally, experimental results are reported and discussed in Sect. 6 and the paper is concluded in Sect. 7.

2 Background

In order to keep the paper self-contained, this section briefly reviews the quantum circuit model usually applied in electronic design automation and provides the background on nearest neighbor optimization.

2.1 Quantum Circuits

In contrast to conventional computation, quantum computation [1] works on qubits instead of bits. A qubit is a two level quantum system, described by a two dimensional complex Hilbert space. The two orthogonal quantum states \(\left| 0\right\rangle \) \(\equiv \left( {\begin{array}{c}1\\ 0\end{array}}\right) \) and \(\left| 1\right\rangle \equiv \left( {\begin{array}{c}0\\ 1\end{array}}\right) \) are used to represent the Boolean values 0 and 1. Any state of a qubit may be written as \(\left| x\right\rangle = \alpha \left| 0\right\rangle + \beta \left| 1\right\rangle ,\) where the amplitudes \(\alpha \) and \(\beta \) are complex numbers with \(|\alpha |^2 + |\beta |^2 = 1\).

Operations on n-qubits states are performed through multiplication of appropriate \(2^n \times 2^n\) unitary matrices. Thus, each quantum computation is inherently reversible but manipulates qubits rather than pure logic values. At the end of the computation, a qubit can be measured. Then, depending on the current state of the qubit, either a 0 (with probability of \(|\alpha |^2\)) or a 1 (with probability of \(|\beta |^2\)) returns. After the measurement, the state of the qubit is destroyed.

Table 1. Quantum gates
Full size table

Quantum computations are usually represented by quantum circuits. Here, the respective qubits are denoted by solid circuit lines. Operations are represented by quantum gates. Table 1 lists common quantum gates together with the corresponding unitary matrices describing their operation. In order to perform operations on more than one qubit, controlled quantum gates are applied. These gates are composed of a target line \(\left| t\right\rangle \) and a control line \(\left| c\right\rangle \) and realize the unitary operation represented by the matrix

where U denotes the operation applied to the target line. In the remainder of this work, we use the following formal notation:

Definition 1

A quantum circuit is denoted by the cascade \(G=g_1g_2\dots g_{|G|}\) (in figures drawn from left to right), where |G| denotes the total number of gates. The number of qubits and, thus, the number of circuit lines is denoted by n. The costs of a quantum circuit (also denoted as quantum cost) are defined by the number |G| of gates.

Example 1

Figure 1 shows a quantum circuit composed of \(n=2\) circuit lines and \(|G|=3\) gates. This circuit gets \(\left| 11\right\rangle \) as input and transforms the qubits as indicated at the circuit signals.

Fig. 1.
figure 1

Quantum circuit

Full size image

In the following, we do not focus on the dedicated functionality of a quantum circuit, but on the structure and whether it satisfies nearest neighbor constraints (as reviewed next). To this end, we omit unary quantum gates (as they are irrelevant for nearest neighbor optimization) and generically denote quantum gates using the notation .

2.2 Nearest Neighbor Optimization

In the recent years, researchers proposed several physical realizations for quantum circuits. This led to a better understanding of their physical limitations and constraints, e.g. with respect to the interaction distance, decoherence time, or scaling (see e.g. [29–31]). Besides that, so-called nearest neighbor constraints have to be satisfied for many quantum circuit architectures. This particularly holds for technologies based on proposals for ion traps [32–34], nitrogen-vacancy centers in diamonds [35, 36], quantum dots emitting linear cluster states linked by linear optics [37], laser manipulated quantum dots in a cavity [38], and superconducting qubits [39, 40]. Here, nearest neighbor constraints limit the interaction distance between gate qubits and require that computations are performed between adjacent, i.e. nearest neighbor, qubits only.

In order to formalize this restriction for electronic design automation, a corresponding metric representing the costs of a quantum circuit to become nearest neighbor compliant has been introduced in [22]. There, the authors defined the Nearest Neighbor Cost as follows.

Definition 2

Assume a 2-qubit quantum gate g(c, t) with a control at the line c and a target at line t where c and t are numerical indices holding \(0 \le c,t < n\). Then, the Nearest Neighbor Cost (NNC) for g is calculated using the distance between the target and the control line. More precisely,

$$\begin{aligned} NNC(g) = |c -t|-1. \end{aligned}$$

As a result, a single control gate g is termed nearest neighbor compliant if \(NNC(g)=0\). 1-qubit gates are assumed to have NNC of 0. The resulting NNC for a complete quantum circuit is defined by the sum of the NNC of its gates:

$$\begin{aligned} NNC(G) = \sum _{g \in G} NNC(g). \end{aligned}$$

A quantum circuit G is termed nearest neighbor compliant if \(NNC(G) = 0\), i.e. if all quantum gates are 1-qubit gates or adjacent 2-qubit gates.

Example 2

Consider the circuit G depicted in Fig. 2(a). Gates are denoted by \(G=g_1{\dots }g_7\) from the left to the right. As can be seen, gates \(g_2\), \(g_6\), as well as \(g_7\) are non-adjacent and have nearest neighbor costs of \(NNC(g_2)=1\), \(NNC(g_6)=2\), as well as \(NNC(g_7)=2\), respectively. Hence, the entire circuit has nearest neighbor costs of \(NNC(G)=5\).

Fig. 2.
figure 2

Establishing nearest neighbor compliance

Full size image

A naive way to make an arbitrarily given quantum circuit nearest neighbor compliant is to modify it by additional SWAP gates.

Definition 3

A SWAP gate is a quantum gate \(g(q_i,q_j)\) including two qubits \(q_i\), \(q_j\) and maps \((q_0, \dots , q_i, q_{j}, \dots , q_{n-1})\) to \((q_0, \dots , q_j, q_i, \dots , q_{n-1})\). That is, a SWAP gate realizes the exchange of two quantum values (in figures drawn using two connected \(\times \) symbols).

These SWAP gates allow for making all control lines and target lines adjacent and, by this, help to satisfy the nearest neighbor constraint. More precisely, a cascade of adjacent SWAP gates can be inserted in front of each gate g with non-adjacent circuit lines in order to shift the control line of g towards the target line, or vice versa, until they are adjacent. Afterwards, SWAP gates are inserted to restore the original ordering of circuit lines.

Example 3

Consider again the circuit depicted in Fig. 2(a). In order to make this circuit nearest neighbor compliant, SWAP gates in front and after all these gates are inserted as shown in Fig. 2(b).

3 Motivation

Adding SWAP gates in a naive fashion as reviewed in the previous section is a simple way of transforming any given quantum circuit into a nearest neighbor compliant version (in fact, this can be conducted in linear time with respect to the number of gates). But the insertion of SWAP gates obviously increases the quantum cost: For each non-adjacent gate, \(2\cdot (|t -c| -1)\) SWAP gates are additionally inserted to the circuit. In order to minimize these additional costs, researchers investigated how to reduce the number of SWAP gate insertions in order to make a given quantum circuit nearest neighbor compliant.

A broad variety of different approaches has been presented for this purpose – including solutions relying on templates [22], local and global reordering strategies [22], dedicated data-structures [23–25], etc. Also exact approaches, i.e. solutions guaranteeing the minimal number of SWAP gate insertions, have been proposed [26, 27]. The work published in [27] provides a good overview. All these approaches particularly focus on how to properly reorder the qubits in the circuit so that the respective interaction distance (and, hence, the number of required SWAP gates) is reduced.

In this work, we consider global reordering schemes, where the main objective is to determine a qubit order which – applied through the entire circuit – yields the smallest nearest neighbor costs. Results obtained from global reordering often provide the basis for further optimization steps and, hence, constitute an important part of nearest neighbor optimization. Unfortunately, determining the best qubit order requires the explicit checking of all possible qubit permutations. For a circuit with n qubits, this yields n! possible combinations – a significant complexity. Two complementary solutions to deal with this complexity represent the current state-of-the-art:

The first one is a heuristic solution proposed in [22]. Here, a good permutation is determined by calculating the contribution of each circuit line of a given quantum circuit G. Therefore, for each 2-qubit gate g of G with control line at position c and target line at position t, the NNC value (see Definition 2) is calculated. Afterwards, this value is added to variables \(imp_c\) and \(imp_t\) which are used to store the “impacts” of the circuit lines c and t on the total NNC, respectively. More precisely, the impact \(imp_i\) of the \(i^{th}\) circuit line (\(0 \le i < n\)) is calculated by

$$\begin{aligned} imp_i = \sum \limits _{g(c,t) \in G ~|~ c = i ~\vee ~ t =i} NNC(g). \end{aligned}$$

Using these impacts, the algorithm selects the circuit line with the greatest value and permutes it with the middle circuit line. If the selected line already is the middle line, the one with the next greatest impact is selected. This whole procedure is repeated until no further improvements are achieved.

The second one is an exact solution proposed in [26, 27], which determines the best possible permutation. To this end, the underlying design problem is formulated as an optimal linear arrangement problem which, in turn, is formulated as an instance of pseudo-Boolean Optimization (PBO, see e.g. [41]). By utilizing corresponding solving engines, the resulting PBO problem is solved.

Example 4

Consider again the circuit depicted in Fig. 2(a). Applying the heuristic of [22], the resulting impacts of the circuits lines are \(imp_{x1}=5\), \(imp_{x2}=0\), \(imp_{x3}=1\), and \(imp_{x4}=4\), respectively. Permuting the line order such that the lines with high impact are located in the middle (descending towards the outer lines) results in the circuit depicted in Fig. 3(a). Compared to the naive method (see result depicted in Fig. 2(b)), this reduces the number of required SWAP gates from 10 to 4. However, significantly further reductions can be achieved if the best permutation is determined (using the exact solution from [26, 27]). Then, a circuit as shown in Fig. 3(b) results which reduces the required number of SWAP gates by another 50 % to 2.

Fig. 3.
figure 3

Global reordering (applied to the circuit from Fig. 2(a))

Full size image

Overall, it can be concluded that the heuristic solution provides a very efficient way of further reducing the number of SWAP gates compared to the naive method. But the obtained results are still far from optimal. In contrast, exact methods guarantee minimality with respect to the number of additionally required SWAP gates, but suffer from the significant complexity (and, hence, the resulting run-time and scalability issues). Motivated by this, we are considering the research question how to optimize heuristic global reordering in order to generate nearly-optimal results while, at the same time, remaining scalable to larger quantum circuits.

4 General Idea

Obviously, considering more permutations – ideally all n! possible ones – will allow for the determination of a qubit order that is better than the one determined by the heuristic solution reviewed above. But then, the question remains how to deal with the corresponding complexity? In this work, we are proposing a scheme which utilizes the compact representation of Permutation Decision Diagrams (\(\pi \)DDs) for this purpose. In this section, we first review the basics of \(\pi \)DDs. Afterwards, we describe the general idea of utilizing this data-structure and illustrate its potential by means of an example.

4.1 Permutation Decision Diagrams (\(\pi \)DDs)

A \(\pi \)DD is a graph which represents a set of permutations and is based on transposition decomposition [28]. Compared to other representation relying on arrays, \(\pi \)DDs can represent sets of permutations more compactly. Besides that, \(\pi \)DDs are also capable of efficiently conducting operations on the represented sets of permutations. Before introducing the structure of \(\pi \)DDs in detail, we describe the decomposition of a permutation called transposition decomposition.

Let \(\pi = \pi _1 \ldots \pi _n\) be a permutation of length n. Then, \(\pi \) can be considered as a numerical sequence satisfying \(\pi _i \in \{1 \ldots , n\}\) for \(1 \le i \le n\) and \(\pi _i \ne \pi _j\) for \(1 \le i < j \le n\). A transposition \(\tau _{i,j}\) is a swap between two elements \(\pi _i\) and \(\pi _j\). Any permutation of length n can be uniquely decomposed into a sequence of at most \(n-1\) transpositions by conducting the following two steps:

  1. 1.

    Prepare the initial permutation \(1 \ldots n\).

  2. 2.

    For each k running from n to 1, move \(\pi _k\) to the k-th position by applying a transposition.

Fig. 4.
figure 4

Two reduction rules of \(\pi \)DDs

Full size image
Fig. 5.
figure 5

A \(\pi \)DD repr. \(\{2431,4231,1423\}\)

Full size image

Example 5

Consider a permutation \(\pi = 2 4 3 1\) to be decomposed. First, we start with the initial permutation 12 34 and set \(k=n=4\). Since \(\pi _k = 1\), we swap the first element and the fourth element (\(\tau _{1,4}\)) and obtain 42 31. The third element 3 is at the same position as given by \(\pi \), i.e. no transposition is needed for \(k=3\). Finally, since \(\pi _2 = 4\) is at the first position of 42 31, we swap the first element and the second element (\(\tau _{1,2}\)) and obtain \(2 4 3 1 = \pi \). By this, the given permutation \(\pi = 2 4 3 1\) is uniquely decomposed into a transposition sequence \(\tau _{1,4} \tau _{1,2}\).

Following this transposition decomposition, a \(\pi \)DD is defined as follows:

Definition 4

A \(\pi \)DD is a rooted and directed graph consisting of five types of components: internal nodes, 0-edges, 1-edges, the 0-sink, and the 1-sink. Figure 5 shows an example of a \(\pi \)DD. Each internal node is labeled with a transposition, and has exactly two out-going edges: a 0-edge and a 1-edge. Each path from a root to the 1-sink corresponds to a permutation held by the \(\pi \)DD as follows: if a 1-edge originates from a node with label \(\tau _{x,y}\), the decomposition of the permutation contains \(\tau _{x,y}\), while a 0-edge means that the decomposition does not contain \(\tau _{x,y}\).

In order to make a \(\pi \)DD compact and canonical, we apply the following two rules called reduction rules (as illustrated in Fig. 4):

  • sharing rule: share all nodes which have the same labels and child nodes.

  • deleting rule: delete all nodes whose 1-edge points to the 0-sink.

Example 6

Consider the three permutations \(\{2431,4231,1423\}\). The transposition decomposition easily shows that all these permutations can be realized by the transpositions \(\tau _{1,4} \tau _{1,2}, \tau _{1,4} \), and \(\tau _{3,4}\tau _{2,3}\). Hence, all of them can be represented by the \(\pi \)DD as shown in Fig. 5.

Although the number of \(\pi \)DD nodes is exponential in the length of permutations in the worst case, in many practical cases, it demonstrates a high compression ratio. For example, Fig. 6 shows an example of an exponentially compact \(\pi \)DD; it represents a set of \(2^5\) permutations with only 5 internal nodes.

Fig. 6.
figure 6

A \(\pi \)DD with 5 nodes representing \(2^5\) permutations

Full size image

A notable feature of the \(\pi \)DD is that it supports efficient restriction operations that make a \(\pi \)DD representing a restricted subset from the original \(\pi \)DD. An instance of restriction used in the following section is an adjacent restriction; it makes a \(\pi \)DD that only contains permutations such that two elements a and b must be adjacent in the permutation.

Since \(\pi \)DD operations are implemented as recursive procedures on a graph, the computation time of \(\pi \)DD operations depends on the number of \(\pi \)DD nodes, not on the cardinality of the set represented by a \(\pi \)DD. Hence, if a \(\pi \)DD is highly compressed and has a small number of nodes, manipulation on a set of permutations can be efficient.

4.2 Proposed Exploitation of \(\pi \)DDs

The concept of \(\pi \)DDs allows one to efficiently represent all n! possible qubit permutations at once. Based on that, the general idea of the proposed nearest neighbor optimization is to iteratively reduce this set of permutations to a subset including efficient permutations only. “Efficiency” is thereby defined by the number of SWAP gates that would be required in order to make a given quantum circuit – whose qubits are aligned according to these permutations – nearest neighbor compliant. Hence, permutations are removed which would clearly yield a quantum circuit with high NNC. In the following, the general idea is sketched by means of an example.

Example 7

For the quantum circuit from Fig. 2(a), a qubit order is to be determined. To this end, all \(4!=24\) possible qubit permutations are considered at the beginning. Those are efficiently represented by the \(\pi \)DD depicted in Fig. 7(a). Now, permutations shall be excluded which are clearly not efficient. Obviously, the interactions between qubits \(x_1\) and \(x_4\) dominates in the circuit from Fig. 2(a). Accordingly, we are removing all permutations in which these two qubits are not adjacent. This can easily be employed using \(\pi \)DDs and, eventually, yields to a total of 12 remaining permutations represented by the structure shown in Fig. 7(b).

Fig. 7.
figure 7

Reducing the considered permutations using a \(\pi \)DD representation

Full size image

In a similar fashion, further permutations can be removed. This can be continued until either

  • all permutations are excluded, i.e. an empty set results, or

  • no further restrictions are left to be considered.

In the first case, restrictions have to be loosened again – even if this would yield a quantum circuit which is not nearest neighbor compliant. After all, the representations is satisfying as many of the restrictions as possible. In the second case, no further actions are needed. From the resulting subset, the permutation leading to the lowest NNC is chosen and used in order to realize the circuit. Again, the example illustrates the issue.

Example 8

Using the subset represented by the \(\pi \)DD shown in Fig. 7(b), another restriction is employed, namely that qubits \(x_1\) and \(x_2\) shall be adjacent (this is motivated by the fact that there are 2 gates in which these two qubits interact). Applying this restriction yields the \(\pi \)DD shown in Fig. 7(c). Because of the same reason, \(x_2\) and \(x_3\) are enforced to be adjacent in the next step (yielding the \(\pi \)DD shown in Fig. 7(d)). Finally, \(x_1\) and \(x_3\) is enforced to be adjacent. However, the last restriction yields a \(\pi \)DD representing the empty set (see Fig. 7(e)). Because of that, this restriction is waived (i.e. we backtrack to the \(\pi \)DD shown in Fig. 7(d)). As no further restrictions are left (all qubit interactions of the original circuit from Fig. 2(a) have been considered), the best permutation regarding its NNC can be calculated and taken from the resulting \(\pi \)DD (shown in Fig. 7(d)). This eventually yields the circuit already shown in Fig. 3(b), i.e. the proposed approach determined a permutation requiring a minimal number of SWAP gates.

Following this scheme aims for keeping permutations that satisfy certain restrictions, while excluding those which are identified as non-efficient (motivated by the interactions of qubits in the circuit). This is a clear improvement compared to the previously proposed heuristic which directly worked towards a single permutation only and, hence, likely excluded better options. The increased complexity caused by considering and manipulating (sub)sets of permutations is tackled through the efficient representation provided by the \(\pi \)DDs. However, the order in which restrictions are applied (and, hence, permutations are excluded) still has an effect on the determined result. The next section deals with how the proposed solution handles this ordering problem.

5 Applying Restrictions to the \(\pi \)DDs

As illustrated in the example from above, the interactions between the qubits provide crucial information on the nearest neighbor compliance of a given permutation. Accordingly, this information builds the basis for deciding what permutations are removed from further consideration. This section describes how this information is obtained, represented and, eventually, applied to the \(\pi \)DD.

5.1 Obtaining and Weighting Restrictions

In order to store information on the interaction of the qubits (and, eventually, derive restrictions from it), a pre-process is conducted which traverses the entire circuit G. For each gate \(g\in G\), the corresponding interaction between the involved qubits is determined and stored. This way, an adjacency matrix is built representing what and how many interactions between qubits are conducted. More formally:

Definition 5

For a given quantum circuit G with n qubits, an adjacency matrix A of size \(n\times n\) represents the number of interactions between all qubits. Each entry \(a_{i,j} \in A\) contains the number of interactions between the qubits \(x_i\) and \(x_j\) and between the qubits \(x_j\) and \(x_i\). Since no qubit interacts with itself, all entries \(a_{ii}\) are left empty. Furthermore, since A is symmetric, only half of the entries has to be considered.

Example 9

Consider the quantum circuit from Fig. 8(a). The corresponding adjacency matrix is shown in Fig. 8(b).

Fig. 8.
figure 8

Obtaining and weighting restrictions from a given circuit

Full size image

From this representation, the restrictions to be applied to the \(\pi \)DDs can easily be derived. Each interaction between the qubits \(x_i\) and \(x_j\) motivate to restrict the set of considered permutation to only those in which \(x_i\) and \(x_j\) are adjacent. Moreover, the adjacency matrix can be used to assign a weight to each restriction. For example, if the qubits \(x_i\) and \(x_j\) interact more frequently than the qubits \(x_k\) and \(x_l\), then the restriction of having (\(x_i\),\(x_j\)) adjacent should be prioritized to the restriction of having (\(x_k\),\(x_l\)) adjacent.

Example 10

From the adjacency matrix shown in Fig. 8(b), restrictions and their weights as shown in Fig. 8(c) are derived.

5.2 Applying Resulting Restrictions to the \(\pi \)DD

In an ideal scenario, all restrictions derived above should be applied to the \(\pi \)DD. Then, a subset of permutations would remain in which all qubits that have interactions with each other are adjacent (eventually leading to a nearest neighbor compliant quantum circuit). However, in most of the cases this would yield an empty subset of permutations. Hence, a procedure is required deciding which restrictions are applied and which are not.

The weight which is assigned to each restriction provides an obvious metric for this purpose. But still, options exists how this metric is utilized. The following two possible schemes could be applied:

  • In a greedy scheme, all restrictions are applied in the order of their weight. That is, the restriction with the highest weight is considered first; afterwards, the restriction with the second highest weight; and so on. This way, stronger restrictions are clearly preferred over weaker restrictions. However, there might be cases in which the application of several restrictions with a relatively small weight outperforms the application of a single restriction with a higher weight.

  • This motivates the consideration of an advanced scheme which works as follows: First, a threshold e is defined stating the maximum number of restrictions which shall be considered together. Then, all possible combinations of the e restrictions with the highest weight are considered (including all e restrictions solely as well as all possible supersets of them). The combination of restrictions which can be applied to the \(\pi \)DD without causing an empty set of permutations and, additionally, satisfies the highest weight is eventually chosen. Afterwards, all remaining restrictions are applied following the greedy scheme.

The two schemes are illustrated by the following example:

Example 11

Consider again the quantum circuit from Fig. 8(a) and the obtained restrictions as shown in Fig. 8(c). Following the greedy scheme would suggest an application of R1, followed by R2, R3, R4, and R5. This eventually results in a set of permutations whose best one would lead to a circuit requiring 10 SWAP gates.

In contrast, the advance scheme would consider all combinations of the \(e=4\) restrictions with the highest weight, i.e. {R1}, {R2}, {R3}, {R4}, {R1,R2}, {R1,R3}, {R1,R4}, {R2,R3}, {R2,R4}, {R3,R4}, {R1,R2,R3}, etc. This way it can be observed that {R1,R2} can be applied together but not {R1,R2,R3}. Since the combination {R1,R3,R4} (i.e. without R2) yields a higher weight than all other non-empty combinations, this set of restrictions is applied to the \(\pi \)DD. Eventually, this results in a quantum circuit requiring 6 SWAP gates.

6 Experimental Evaluation

The solution proposed in the previous sections has been implemented on top of the \(\pi \)DD-package introduced in [28]. Based on this implementation, the performance of the proposed solution has been evaluated using benchmark quantum circuits taken from RevLib [42]. Afterwards, the obtained results have been compared to results obtained by the previously proposed solutions reviewed in Sect. 3. This section summarizes and discusses the obtained results. All evaluations have been conducted on an Intel i3-4030U machine with 1.9 GHz and 4 GB of memory.

Table 2 summarizes the obtained results. The first columns provide the name of the considered benchmarks as well as its respective number of lines (n) and gates (|G|). Afterwards, the number of required SWAP gates are reported if the naive method (reviewed in Sect. 2.2), the heuristic and exact method (reviewed in Sect. 3), as well as the proposed method (introduced in Sects. 4 and 5 and following the advanced scheme) are applied. In the case of the exact method as well as the proposed method, the required runtime (in CPU seconds) is additionally provided (both, the naive and heuristic approach where able to determine all results in negligible time, i.e. in less than a second). Finally, the last columns provide a comparison of the results obtained by the proposed approach to the respective numbers from the naive, heuristic, and exact approaches.

The results clearly confirm that the proposed approach fulfills the promises discussed in Sect. 3. By considering sets of permutations (rather than constructing a single one only), significantly better results compared to the previously proposed heuristic can be obtained. Improvements of more than 66 % in the best case are reported. Moreover, the proposed solution is capable of generating optimal or almost optimal results (see comparison of the proposed approach to the exact solution). This quality is achieved by requiring only a fraction of the runtime needed for the exact approach thus far. That is, \(\pi \)DDs as utilized in this work allow for determining results of optimal or almost optimal quality while, at the same time, they handle the underlying complexity in an efficient fashion.

Table 2. Experimental evaluation
Full size table

7 Conclusions

In this work, we considered nearest neighbor optimization of quantum circuits using \(\pi \)DDs. Since \(\pi \)DDs allow for an efficient representation and manipulation of sets of permutations, they allow for considering all possible permutations at once and an subsequent reduction of them with respect to the nearest neighbor constraints. This way, an ideal compromise between existing solutions is provided. Experimental evaluations confirmed the efficiency and quality of the obtained results.