1 Introduction

Quantum circuits [25] represent a promising alternative to conventional circuit technologies allowing for solving many important problems (e.g. database search, factorization, graph problems) significantly faster (see e.g. [7, 9, 33]). Information is thereby stored in terms of qubits. In contrast to conventional bits, qubits do not only allow to represent Boolean 0’s and Boolean 1’s, but also the superposition of both. The states of the respective qubits are thereby modified by quantum operations which can be represented by unitary matrices. That is, each quantum computation is inherently reversible, but manipulates qubits rather than pure logic values. Since most of the solutions include a significant Boolean component to be realized (e.g. the Oracle function in the Deutsch Algorithm or Grover’s database search as well as the modular exponentiation in Shor’s factorization algorithm), synthesis of quantum circuits is often conducted by a two-stage procedure: First, a reversible circuit is designed using established reversible gate libraries (containing e.g. Toffoli gates [36]). To this end, several synthesis approaches have been introduced in the past (see e.g. [20, 28, 32, 35, 37, 39]). Then, the resulting (reversible) circuits are mapped into the respective quantum circuits. Here schemes as originally introduced by Barenco [2] or its recently optimized versions (see e.g. [19, 21]) are applied. By this, the Boolean parts of a quantum circuit to be realized are synthesized. This is reviewed in detail later in Sect. 3.

However, recent physical accomplishments have led to further constraints to be considered during quantum circuit synthesis. In particular, so called nearest neighbor constraints have been introduced. They are justified by the fact that many physical realizations of quantum circuits assume that computations are only performed between adjacent (i.e. nearest neighbor) signals. This was originally motivated by physical realizations based e.g. on trapped ions (see e.g. [10]), liquid nuclear magnetic resonance (see e.g. [18]), and architectures based on the original Kane model [15]. Nowadays, ion traps are no longer appropriately described as universally nearest neighbor architectures, liquid nuclear magnetic resonance is acknowledged as not scalable, and the original Kane proposal has been superseded by [13]. Nevertheless, nearest neighbor architectures are still an issue in recently proposed technologies including proposals for ion traps [1, 17, 24], nitrogen-vacancy centers in diamonds [5, 40], quantum dots emitting linear cluster states linked by linear optics [11], laser manipulated quantum dots in a cavity [14], and superconducting qubits [6, 26].

Motivated by that, synthesis methods have been introduced which realize circuits satisfying this condition (see e.g. [4, 12, 16, 22, 29]). A major problem is thereby that methods for nearest neighbor optimization usually work at the quantum circuit level only. Indeed, some previous work (e.g. [3]) considered nearest neighbor constraints already at the reversible circuit level. But due to the lack of proper metrics, only adjacency of Toffoli gates has been achieved so far, while the mapping to its corresponding quantum circuit realization may introduce further non-adjacent gates. In fact, nearest neighbor conditions cannot efficiently be addressed at the reversible circuit level yet. This is discussed in detail later in Sect. 4.

In this paper, we present an approach that allows the consideration of nearest neighbor constraints already at the reversible circuit level. For this purpose, a quantum gate library is applied which theoretically and conceptionally has been discussed in [23, 31]. We provide a precise metric of the nearest neighbor constraints that even can be used at the reversible circuit level. We illustrate how this metric can be applied to optimize reversible circuits with respect to these constraints.

The remainder of this paper is structured as follows. First, the required background on reversible as well as quantum circuits is provided and the mapping from reversible circuits to quantum circuits is reviewed in Sects. 2 and 3, respectively. Afterwards, how to consider nearest neighbor constraints is discussed in Sect. 4. This includes the introduction of metrics that even can be applied at the reversible circuit level. The application of this is then illustrated in Sect. 5 and evaluated in Sect. 6. Finally, the paper is concluded in Sect. 7.

2 Preliminaries

In order to keep the remainder of this paper self-contained, preliminaries on reversible and quantum circuits are briefly reviewed in this section.

2.1 Reversible gates & circuits

A logic function \(f:\mathbb B ^n\rightarrow \mathbb B ^m\) over inputs \(X=\{x_1,\ldots , x_n\}\) is reversible if and only if

  • its number of inputs is equal to its number of outputs (i.e. \(n=m\)) and

  • it maps each input pattern to a unique output pattern.

Otherwise, the function is termed irreversible. In other words, a reversible function represents a bijection.

A reversible function can be realized by a circuit \(G=g_1g_2\dots g_d\) comprised of a cascade of reversible gates \(g_i\), where \(d\) is the number of gates. Fanouts and feedback are not directly allowed [25]. Several different reversible gates have been introduced including the Toffoli gate [36], the Fredkin gate [8], and the Peres gate [27]. In the following, we focus on Toffoli gates which are universal gates, i.e. all reversible functions can be realized by means of this gate type alone [36].

A multiple control Toffoli gate has a target line \(x_j\) and control lines \(\{\!x_{i_1},\!x_{i_2},\ldots ,x_{i_k}\}\). This gate maps \((x_1, x_2, \ldots , x_j, \ldots , x_n)\) to \((x_1,x_2,\ldots , x_{i_1} x_{i_2}\ldots x_{i_k} \oplus x_j, \ldots , x_n)\). That is, the target line is inverted if all control lines are set to 1; otherwise the value of the target line is passed through unchanged. A Toffoli gate with no control lines always inverts the target line and is a NOT gate. A Toffoli gate with a single control line is called a controlled-NOT gate (also known as the CNOT gate). The case of two control lines is the original gate defined by Toffoli. For brevity, we refer to a multiple-control Toffoli gate as a Toffoli gate.

In the following, a Toffoli gate is denoted by the tuple \(T(C,t)\) where \(C\subset X\) is the possibly empty set of control lines and \(t\in X\setminus C\) is the target line. Note that the control lines and unconnected lines pass through a gate unchanged. For drawing circuits, we follow the established convention of using the symbol \(\oplus \) to denote the target line and solid black circles to indicate control connections for the gate.

Example 1

Figure 1 shows a reversible circuit composed of \(n=4\) circuit lines and \(d=4\) Toffoli gates. This circuit maps e.g. the input pattern \(1111\) to the output pattern \(1000\) (as shown in Fig. 1). Inherently, every computation can be performed in both directions (i.e. computations towards the outputs and towards the inputs can be performed).

Fig. 1
figure 1

Reversible circuit

Full size image

2.2 Quantum gates & circuits

The basic building block for a quantum computer is the qubit. A qubit is a two level quantum system, described by a two dimensional complex Hilbert space. The two orthogonal quantum states \(|0 \rangle \equiv \left( ^{1}_{0}\right) \) and \(|1 \rangle \equiv \left( ^{0}_{1}\right) \) are used to represent the values 0 and 1. Any state of a qubit may be written as \( | \Psi \rangle = \alpha |0 \rangle + \beta |1 \rangle , \) where \(\alpha \) and \(\beta \) are complex numbers with the following condition \(|\alpha |^2 + |\beta |^2 = 1\). The quantum state of a single qubit is denoted by the vector \({\alpha \atopwithdelims ()\beta }\). The state of a quantum system with \(n > 1\) qubits is given by an element of the tensor product of the single state spaces and can be represented as a normalized vector of length \(2^n\), called the state vector. The state vector is changed through multiplication of appropriate \(2^n \times 2^n\) unitary matrices [25].

Since this allows an infinite number of qubit-values and corresponding operations, researchers defined proper models and gate libraries in order to realize Boolean functions in quantum logic. In this work, the following two libraries are considered.

2.2.1 NCV library

The quantum gate library introduced by Barenco et al. [2] is mostly applied in the development of design methods for quantum circuits. Here, the following set of quantum gates is considered:

  • NOT gate \(T(\emptyset ,t)\): A single qubit \(t\) is inverted.

  • Controlled NOT (CNOT) gate \(T(\{c\},t)\): The target qubit \(t\) is inverted if the control qubit \(c\) is 1.

  • Controlled \({{\mathrm{V}}}\) gate \({{\mathrm{V}}}(\{c\},t)\): A \({{\mathrm{V}}}\) operation is performed on the target qubit \(t\) if the control qubit \(c\) is 1. The \({{\mathrm{V}}}\) operation is also known as the square root of NOT, since two consecutive \({{\mathrm{V}}}\) operations are equivalent to an inversion.

  • Controlled \({{\mathrm{V^\dagger }}}\) gate \({{\mathrm{V^\dagger }}}(\{c\},t)\): A \({{\mathrm{V^\dagger }}}\) operation is performed on the target qubit \(t\) if the control qubit \(c\) is 1. The \({{\mathrm{V^\dagger }}}\) gate performs the inverse operation of the \({{\mathrm{V}}}\) gate, i.e. \({{\mathrm{V^\dagger }}}= {{\mathrm{V}}}^{-1}\).

More precisely, these gates transform the target qubit \(t\) as specified by the unitary matrices

If the input signals and all control lines are restricted to Boolean values, a 4-valued logic results where each qubit may represent one value of \(\{ 0, 1, v_0, v_1 \}\) with \( v_0 = \frac{1+i}{2} {1 \atopwithdelims ()-i}\) and \( v_1 = \frac{1+i}{2} {-i \atopwithdelims ()1}\). Figure 2 shows the resulting transitions with respect to the possible NOT, \({{\mathrm{V}}}\), and \({{\mathrm{V^\dagger }}}\) operations. This is sufficient to realize every reversible function as a quantum circuit [2]. Furthermore, this keeps the gate library simple enough to become physically realizable. In the following, this model is called NCV gate library.

Fig. 2
figure 2

State transitions for NOT, CNOT, \({{\mathrm{V}}}\), and \({{\mathrm{V^\dagger }}}\) operations

Full size image

Example 2

Figure 3 shows a quantum circuit composed of \(n=4\) circuit lines and \(d=6\) quantum gates. This circuit again maps e.g. the input pattern 1111 to the output pattern 1000, but in contrast to the circuit from Fig. 1 quantum values and quantum operations are utilized for this purpose.

Fig. 3
figure 3

Quantum circuit using the NCV gate library

Full size image

2.2.2 NCV-\(|v_1\rangle \) library

Although the NCV library is universal, i.e. every Boolean function can be represented by it [2], extensions of it have been introduced recently (see e.g. [30, 31]). In this work, we additionally consider the quantum gate library introduced in [31] which is based on the theoretical discussion on physical realizations from [23]. Here, qudits instead of qubits are assumed, i.e. a basic building block which does not rely on a two level quantum system, but a (multiple-valued) \(d\)-level quantum system is assumed. Any state of a qudit may be written as \(|\Psi \rangle = c_0 |0\rangle + c_1 |1\rangle + \ldots + c_{d-1} |d-1\rangle \) where \(c_i\) for all \(i=0,\ldots ,d-1\) are complex numbers such that \(|c_0|^2+|c_1|^2 + \ldots + |c_{d-1}|^2 = 1\). Similar to qubits, the states of a qudit are represented by a state vector. The state vector is changed through multiplication of appropriate unitary matrices. In the case of an uncontrolled transformation the dimension of the unitary matrices is \(d \times d\), in the case of an controlled transformation the dimension is \(d^2 \times d^2\). However, in contrast to a qubit, the controlled gates for qudits perform the respective operation not when the control line is \(|1 \rangle \), but rather when the control line is set to the value \(|d-1 \rangle \).

In [23], a corresponding gate library for qudits has been presented and discussed. In [31], this model is adopted with a 4-level logic, i.e. \(d=4\). The basic states are, in that order, \(0\), \(v_0\), \(1\), and \(v_1\). As already explained, the controlled gates are only transforming the target qudit if the value of the control line is set to \(|d-1 \rangle \equiv v_1\). We emphasize this fact by labeling the control connections for the respective gates with \(v_1\).

The libary is composed of the three unitary gates (i.e. gates without a control line) performing the NOT, \({{\mathrm{V}}}\), and \({{\mathrm{V^\dagger }}}\) operation as well as single-control versions of these gates. More precisely, these gates transform the target qubit \(t\) as specified by the unitary matrices

Again, restricting the inputs to Boolean values still allows for the realization of any arbitrary reversible functions. In the following, this model is called NCV-\(|v_1\rangle \) gate library.

Example 3

Figure 4 shows a quantum circuit composed of \(n=4\) circuit lines and \(d=5\) quantum gates. This circuit performs the same computation as the circuits from Figs. 1 and 3, but is composed of gates from the NCV-\(|v_1\rangle \) library introduced in [31].

Fig. 4
figure 4

Quantum circuit NCV-\(|v_1\rangle \) gate library

Full size image

3 Mapping reversible circuits to quantum circuits

Since any quantum operation can be represented by a unitary matrix [25], each quantum circuit is inherently reversible. Consequently, every reversible circuit can be transformed to a quantum circuit. Motivated by this, synthesis of Boolean components of quantum circuits is usually conducted in two steps: First, the desired logic is synthesized as reversible circuit. Afterwards, each gate of the resulting circuit is mapped to a corresponding cascade of quantum gates. To this end and depending on the addressed gate library, different mapping schemes have been proposed.

3.1 Mapping to gates from the NCV library

Mapping of reversible gates to NCV gates has intensely been considered in the past. Originally, Barenco et al. proposed the initial mappings in [2]. Afterwards, further improvements have been introduced e.g. in [19] and, more recently, in [21].

Example 4

Consider a Toffoli gate with two control lines as shown in the left-hand side of Fig. 5a. A functionally equivalent realization in terms of gates from the NCV library is depicted in the right-hand side of Fig. 5a.

Fig. 5
figure 5

Mapping reversible circuits to quantum circuits. a Mapping to gates from the NCV library. b Mapping to gates from the NCV-\(|v_1\rangle \) library

Full size image

Similar mappings exist for Toffoli gates with more than two control lines. But with increasing number of control lines, the resulting quantum circuits become more expensive, i.e. require more quantum gates. Furthermore, also the number of the ancillarly lines, i.e. the number of circuit lines which neither are a control line nor a target line, affect the size of the resulting quantum circuit. To provide some numbers, Table 1a lists the respective number of quantum gates for different Toffoli gate configurations according to the current state-of-the-art NCV mapping scheme introduced in [21].

Table 1 Number of quantum gates
Full size table

3.2 Mapping to gates from the NCV-\(|v_1\rangle \) library

With the NCV-\(|v_1\rangle \) library, also a corresponding mapping scheme has been introduced in [31]. This scheme fully exploits the \(|v_1\rangle \)-sensitivity of the control lines which enables a more efficient mapping of reversible gates than the mapping to gates from the NCV library. The general principle of this mapping is illustrated by means of the following example.

Example 5

Consider a Toffoli gate with an arbitrary number of control lines as shown in the left-hand side of Fig. 5b. A functionally equivalent realization in terms of gates from the NCV-\(|v_1\rangle \) library is depicted in the right-hand side of Fig. 5b. First, all control lines are \(|v_1\rangle \)-sensitized, i.e. (\(v_1\)-controlled) \({{\mathrm{V}}}\)-gates are applied setting the values of the control lines to \(v_1\) iff they all have initially been set to 1. By this, a \(v_1\)-controlled NOT gate ensures that the value of the target line is only flipped iff all control lines have been set to 1. Afterwards, (\(v_1\)-controlled) \({{\mathrm{V^\dagger }}}\)-gates are applied to de-sensitize the control lines.

Using this scheme, every Toffoli gate \(T(C,x_j)\) with \(x_j\in X\) and \(C\subset X\backslash \{x_j\}\) can be mapped to an equivalent cascade of \(2\cdot |C|+1\) NCV-\(|v_1\rangle \) quantum gates [31]. In comparison to the mapping to gates from the NCV library, this is (1) significantly more compact and (2) does not even require ancillary lines. Table 1 provides a more precise comparison between these two mappings. Note that the physical costs of the respective gates may differ in the respective libraries. However, comparing the number of elementary gates seems to be an acceptable abstraction until the physically realizations eventually advanced.

4 Consideration of nearest neighbor constraints

As discussed in [31] and briefly reviewed in the previous section, the NCV-\(|v_1\rangle \) library enables a much more compact mapping of reversible circuits to quantum circuits with respect of gates. Beyond that, the NCV-\(|v_1\rangle \) mapping additionally allows to consider nearest neighbor constraints of quantum circuits already at the reversible circuit level.

Nearest neighbor constraints have been introduced as many physical realizations of quantum circuits assume that computations are only performed between adjacent, i.e. nearest neighbor, signals (see Sect. 1). Accordingly, synthesis methods have been introduced which realize circuits satisfying this condition (see e.g. [4, 12, 16, 22, 29]).

However, as shown in the first part of this section, these methods usually work on the quantum circuit level. In the second part of this section, we illustrate how this can be lifted to the reversible circuit level.

4.1 In the NCV library

The quantum circuits resulting by using the NCV library and the state-of-the art mappings reviewed in Sect. 3.1, often do not satisfy the nearest neighbor constraint. For example, already the mapping illustrated in Fig. 5a leads to a non-adjacent gate.

A naive approach to address that, is to add SWAP gates to the circuit. SWAP gates \(S(x_i,x_j)\) have two target lines \(x_i,x_j\in X\) and map \((x_1\ldots x_i \ldots x_j\ldots x_n)\) to \((x_1\ldots x_j \ldots x_i\ldots x_n)\), i.e. the values of these target lines are interchanged. In order to satisfy the nearest neighbor condition of quantum circuits, SWAP gates can be added in front of each gate \(g\) with non-adjacent control and target lines to “move” the control (target) line of \(g\) towards the target (control) line until they become adjacent. Afterwards, SWAP gates are added to restore the original order of circuit lines. Since SWAP gates can easily be represented by a cascade of three controlled NOT-gates, the resulting quantum circuit is still composed of gates from the supported library. But obviously this procedure increases the number of gates of the circuit.

Example 6

Consider again the Toffoli gate with two control lines and its corresponding NCV mapping as shown in Fig. 5a. As can be seen, the last gate is non-adjacent. Thus, to satisfy the nearest neighbor constraint, SWAP gates in front and after the last gate are inserted as shown in Fig. 6a. Since each SWAP gate requires three controlled NOT gates, this increases the total number of NCV-gates from to 5 to 11. Even a minimal nearest neighbor-aware mapping of this Toffoli gate (as shown in Fig. 6b; taken from [29]) requires a total of 9 NCV-gates.

Fig. 6
figure 6

Consideration of nearest neighbor constraints in the NCV library. a Naive mapping. b Minimal mapping

Full size image

Already this simple example illustrates the effects a consideration of nearest neighbor constraints has on the size of the resulting circuits. Moreover, any further configuration of Toffoli gates (e.g. a different position of the target line or a larger number of control lines) leads to other non-adjacent gates for which other SWAP gates have to be added. In fact, no metric exists covering all the possible mappings of arbitrary Toffoli gate configurations to quantum circuits satisfying the nearest neighbor conditions. As a consequence, nearest neighbor conditions cannot efficiently be addressed at the reversible circuit level. Instead, the established mapping from a reversible circuit to a quantum circuit is conducted first and adjacency of the resulting quantum gates is ensured by a post-synthesis process afterwards. To this end, methods introduced e.g. in [4, 12, 16, 22, 29] are applied.

Fig. 7
figure 7

Nearest neighbor-aware mapping of reversible gates

Full size image

4.2 In the NCV-\(|v_1\rangle \) library

Using the NCV-\(|v_1\rangle \) library reviewed in Sect. 3.2, nearest neighbor constraints can be satisfied much easier. In fact, the mapping shown in Fig. 5b already satisfies it since only adjacent gates are included here. However, this does not hold for all configurations: Applying the same scheme for a Toffoli gate as shown in the left-hand side of Fig. 7, a quantum circuit as shown in the right-hand side of Fig. 7 results still including two non-adjacent gates. In contrast to the NCV library, the number of SWAP gates to be applied is linear and can always be derived from the configuration of the considered reversible gate.

More precisely, let \(T(C,x_j)\) be a Toffoli gate with \(x_j\in X\) and \(C\subset X/\{x_j\}\). Assume that all control and target lines in \(T(C,x_j)\) are already adjacent. Furthermore, w.l.o.g. assume that \(x_1, x_2, \dots \in X\) are the top lines and \(\dots , x_{n-1}, x_n\in X\) are the bottom lines of the circuit, respectively. Then, this Toffoli gate can be mapped to a cascade of adjacent quantum gates with respect to the following two cases:

  1. 1.

    The target line \(x_j\) is “either on the top or the bottom”, i.e. either \(\forall x_i\in C: i<j\) or \(\forall x_i\in C: i>j\) holds. In this case, the mapping already introduced in Fig. 5b can be used. This already satisfies the nearest neighbor condition, i.e. no additional SWAPs are needed and a total of \(2\cdot |C|+1\) gates are required.

  2. 2.

    The target line \(x_j\) is “between the control lines”, i.e. \(\exists x_i\in C: i<j\) and \(\exists x_k\in C: k>j\) holds. In this case, the Toffoli gate can be represented by a quantum gate cascade as shown in Fig. 7. This requires \(\text{ min }(2\cdot (j-1+1),2(k-j+1))\) SWAP gates in order to satisfy the nearest neighbor condition (assuming that both, \(x_i\) and \(x_k\) are the control lines at the top and the bottom, respectively, i.e. \(\not \exists x_l\in C: l<i\) and \(\not \exists x_m\in C: m>k\)). That is, a total of \((2\cdot |C|+1) + 3\cdot \text{ min }(2\cdot (j-1+1),2(k-j+1))\) gates are required.

Hence, if a Toffoli gate \(T(C,x_j)\) is adjacent, a linear mapping to a quantum circuit satisfying nearest neighbor constraints can be derived. In contrast to the mapping for the NCV library, this provides a precise metric for the nearest neighbor constraints that can even be used at the reversible circuit level. By this, existing synthesis procedures for reversible circuits can be extended in order to directly support nearest neighbor architectures right from the beginning of the design process.

5 Nearest neighbor-aware optimization of reversible circuits

Using the new metric provided above, this section introduces an approach that exemplarily illustrates the consideration of nearest neighbor constraints at the reversible circuit level. Therefore, an optimization method is proposed that is inspired by the work from [29]. Here a re-ordering scheme was applied to quantum circuits in order to reduce the number of non-adjacent quantum gates. The application of this scheme to the reversible circuit level is illustrated by means of an example.

Example 7

Consider the reversible circuit shown in Fig. 8a. Using the metric from Sect. 4.2, it can be calculated that a quantum circuit satisfying the nearest neighbor constraints would be composed of \(50\) gates, i.e. \(5+5+5+5=20\) gates resulting from the mapping plus \(3\cdot 5=15\) gates to swap the control and target lines of the first, third, and fourth reversible gate plus \(3\cdot 5=15\) gates to undo this swapping. However, it can be calculated that, by slightly reordering the lines as shown in Fig. 8b, the total number of quantum gates necessary can be reduced to \(32\). Due to the absence of a precise metric, previous methods were not able to precisely determine such optimizations at the reversible circuit level.

Fig. 8
figure 8

Nearest neighbor-aware optimization of a reversible circuits. a Original circuit. b Optimized circuit

Full size image

Motivated by this, a reversible circuit can be optimized with respect to nearest neighbor constraints as follows: First, the “contribution” of each line to the total number of needed SWAPs is calculated. More precisely, for each gate \(g\) with control lines \(C\) and target line \(x_j\), the number of SWAPs needed to make \(C\) and \(x_j\) adjacent is determined. This number is added to variables \(prop_i\) with \(i \in C \cup \{x_j\}\) which are used to save the proportion of a circuit line \(i\) on the total number of SWAPs. Next, the line \(i\) with the highest value of \(prop_i\) is chosen for reordering and placed at the middle of the circuit (i.e. line \(i\) is swapped with the middle line). If the selected line is the middle line itself, a line with the next larger value is selected. This procedure is repeated until no improvements are achieved.

Example 8

Applying the proposed scheme to the circuit shown in Fig. 8, values \(prop_{x_1}=5\), \(prop_{x_2}=1\), \(prop_{x_3}=2\), \(prop_{x_4}=3\), and \(prop_{x_5}=4\) result. Thus, the lines \(x_1\) (largest proportion) and \(x_3\) (middle line) are swapped. Since further swaps do not lead to further improvements, the reordering terminates leading to the circuit shown in Fig. 8b.

Note that this only exemplarily illustrates the consideration of nearest neighbor constraints at the reversible circuit level. In fact, thanks to the metric from Sect. 4.2 other existing synthesis and optimization approaches for reversible circuits can be adjusted accordingly. However, the experimental evaluation summarized in next section confirms that already the this rather simple re-ordering scheme leads to significant improvements.

6 Experimental evaluation

The optimization approach presented in the previous section has been implemented in C++ on top of RevKit [34] and applied to all benchmark circuits available at RevLib [38]. Thanks to the rather heuristic nature of the approach, all circuits have been processed with negligible run-time (i.e. within a couple of minutes) on an Intel Core i5-3210M machine with 2.5 GHz and 4 GB of memory.

The evaluation showed that, over all considered circuits, a reduction in the number of gates of the resulting quantum gate cascades of approx. 8 % can be achieved on average. This includes many small circuits for which no improvement at all has been obtained. In contrast, for larger circuits improvements of up to 68 % are possible.

Table 2 shows the best improvements which have been observed during our evaluation. The first columns give thereby the name, the number \(n\) of lines, and the number \(g\) of gates of the respective reversible circuits. Afterwards, the number of quantum gates are reported for the original circuits (w/o optimization) and for the improved circuits (w/ optimization). In both cases, of course the metric from Sect. 4.2 has been applied, i.e. the nearest neighbor condition was considered. The total improvement is provided by the last column.

Table 2 Experimental evaluation
Full size table

7 Conclusions

In this paper, we presented an approach that allows for the consideration of nearest neighbor constraints already at the reversible circuit level. By this, a gap in today’s design flows for corresponding quantum circuits has been closed. So far, only adjacency of Toffoli gates has been achieved at the reversible circuit level, while the mapping to its corresponding quantum cascades may have introduced further non-adjacent gates. Using the gate library proposed in [23, 31], we were able to provide a metric where such cases are covered. By this, nearest neighbor constraints can directly be addressed in the reversible circuit. Exemplarily, this has been illustrated by means of an optimization approach.

Future work consists of two major pillars: First, this work as well as the previous contributions in [23, 31] just provided a theoretical and conceptual discussion on the applicability of the NCV-\(|v_1\rangle \) library. Hence, physical realizations and concepts on how to realize this library is subject to future work. This includes (1) direct realizations of the qudits, (2) the emulation of qudits e.g. by existing qubit-realizations, and (3) the compatibility to existing fault-tolerant quantum error correction protocols. Second, the optimization approach presented here was applied to illustrate the applicability of the proposed metric and, hence, is rather simple. More detailed investigations on synthesis and optimization approaches for reversible circuits exploiting these concepts are left for future work, too.