Keywords

1 Introduction

Quantum logic synthesis [1] is what we use to achieve corresponding quantum circuits with given quantum logical gates according to constraint conditions and limitations of no fan-out, no feedback and meeting technological requirements achieving quantum circuits, and also optimizes quantum circuits under a certain cost model, with qc being as little as possible.

Quantum circuits synthesis originate in the research for quantum computer. In order to achieve the LNN constraint of quantum technology and construct quantum circuits for LNN, so far, several approaches converting quantum circuits of arbitrary architecture to quantum circuits of LNN architecture have been come up with [2,3,4,5].

The time of quantum computation depends of the number of gates in quantum circuits and physical operations achieving every gate, which is called quantum cost [6]. Decoherence of quantum system will be caused by the interference of the external environment, as a result, quantum computation must be finished within limited and coherent time, which requires that qc in quantum circuits should be minimized. The circuit, which is of minimal cost, used to achieve a certain specific function of minimal qc is called optimal circuit.

For the sake of constructing optimized quantum circuits for LNN architecture, following work will be finished in this paper: (1) Find out quantum circuits of minimal NNC by full permutation of the whole circuit line with optimized evaluation algorithm for quantum circuits; (2) In order to achieve the convert to LNN architecture from the original quantum circuits, the optimized approach of adding swap gates should be finished based on (1) to realize the convert to LNN architecture, which will make physical realization easier; (3) In order to decrease qc of quantum circuits and make the minimal number of additive swap gates, related algorithms solving the problems of optimization of quantum circuits will be come up with.

2 Reversible Logical Algorithm of Lnn Based on Pre-Evaluation

2.1 Comprehensive Algorithm

Theorem 1. In the quantum circuits constructed by NCV gate library, the minimal number of additive swap gates when a single arbitrary quantum gate converts to an adjacent quantum gate is equal to NNC value of the arbitrary quantum gate.

The relationship between the minimal number of additive swap gates and NNC value of arbitrary quantum gates is as follows:

$$ sc \, = \, g\_nnc $$
(1)

There into sc is the minimal number of additive swap gates; g_nnc is NNC value of a single quantum gate.

From Theorem 1, we can know that the number of additive swap gates is certainly little. On the other hand, when adding swap gates to arbitrary quantum gates, we should take the circumstance of the qubit in quantum circuits into account to obtain as far as possible pairs of redundant swap gates with newly additive swap gates and existing swap gates in quantum circuits. Then, the pairs of redundant swap gates are removed to achieve the goal of decreasing swap gates in quantum circuits.

As for a know arbitrary quantum circuit, form left to right, the first arbitrary quantum gate is middle axle. The quantum circuits cascading system on the left side of this arbitrary quantum gate is N l (excluding the arbitrary quantum gate), the rest of quantum circuits on the right side of this arbitrary quantum gate is N r (including the arbitrary quantum gate). N m is a group of quantum circuits including only swap gates, which is required when cascading N l and N r , the two partial quantum circuits.

Detailed algorithm is as follows:

Step1: Initialize N l to null, N m null and N r = N.

Step2: Scan. Search the first non-adjacent quantum gate of quantum circuit from the input of the quantum circuit. If there is a non-adjacent quantum gate, we set it as g 1 and carry out Step3. If not, we carry out Step7.

Step3: Bounded by g 1, the left side of the quantum circuit is N l (excluding g 1) and the right side together with g 1 is N r .

Step4: Ordering. We undergo global reordering on N r and obtain quantum circuit set, N r (i) and swap gate group set, N m (i).

Step5: Adjacence. We convert g 1 (i) of the N r (i) to adjacent gate applying the algorithm of adding swap gate. (N m (i) and N r (i) can be cascaded to construct a quantum circuit)

Step6: The optimal evaluation of quantum circuit. After every operation of adjacence, we finally choose a minimal qc of N r (i) as N r applying the optimal evaluation of quantum circuit. Then, we turn to Step2.

Step7: Check up on redundant swap gates in established quantum circuit for LNN and remove those redundant.

Step8: End.

2.2 Optimal Evaluation Algorithm of Quantum Circuits

In quantum circuits constructed by NCV gate library, on the premise of input/output truth-value staying the same, we evaluate NNC and chaos value of quantum circuits by the heuristic algorithm and determine minimal set of results.

Detailed algorithm is as follows:

Step1: Calculate the high/low qubit of the non-adjacent quantum gate g 1. We suppose l i as its low qubit, l j high qubit and NNC n l .

Step2: Judge the quantum status of low qubit. If it is close, we carry out Step5.

Step3: Calculate the number (i) of removed qubits, add correspondent number (i) of swap gates, remove redundant swap gate group and update the value of n l of g l .

Step4: Judge the value of n l . If it is 0, turning to Step7.

Step5: Judge the quantum status of high qubit. If it is closed, we carry out Step6; otherwise, we carry out Step3.

Step6: According to the value of n l , we add in minimal but necessary swap gates and then convert non-adjacent quantum gates to adjacent ones.

Step7: End.

2.3 The Algorithm of Computing Minimal Chaos Value

In order to find out a proper N m structure cascading N l and N r , solve the problems of reordering quantum circuits, and determine chaos value of N m , this paper proposes an algorithm to compute minimal chaos value.

Detailed algorithm is as follows:

Step1: Starting with i = 0, we read the element of origin.

Step2: Judge whether the element read is the last element of origin or not. If so, we carry out Step5; if not, we carry out Step3.

Step3: Store the location information of origin in target array in t[i].

Step4: Remove the element in the location in target array (forward elements in follow-up locations lead), and then carry out Step2.

Step5: Remove all of the elements in target array. Calculate the sum marked by t of elements in t[i].

Step6: End.

2.4 The Algorithm of Adding Swap Gates

In the algorithm of adding swap gates, this paper presents an approach of adding swap gates to arbitrary quantum gates, which can precisely compute whether every arbitrary quantum gate can get redundant swap gates pairs which could be deleted or not as well as compute how many pairs of redundant swap gates can be removed. We can obtain swap gates with minimal addition making use of the algorithm of adding swap gates, thus obtain quantum circuits of minimal qc.

The swap gates in N m structure and additive swap gates in the algorithm of adding swap gates can form some pairs of redundant swap gates, which can be removed from quantum circuits to achieve the goal of decreasing qc.

Detailed algorithm is as follows:

Step 1: Compute the high/low qubit of arbitrary quantum circuit g l (l i , l j , k). Suppose its low qubit is l i , high qubit is l j , its NNC is n 1.

Step 2: Judge the quantum state of low qubit. If it is close, carry out Step 5.

Step 3: Compute cancellation layers of the qubit, add i corresponding swap gates, remove these i pairs of redundant swap gates, and update the NNC value, n 1 of quantum gate, g 1.

Step 4: Judge whether the value of n 1 is 0 or not. If so, turn to Step 7.

Step 5: Judge the quantum state of high qubit. If is close, carry out Step 6, otherwise carry out Step 3.

Step 6: According to the value of n 1, add minimal yet necessary swap gates to make arbitrary quantum gates adjacent.

Step 7: End.

3 Experimental Results and Analysis

The Experimental data in this paper all come from revlib, from which 31 groups of data are tested and 3 to 8 quantum circuits are covered. The number of quantum gates from test data is 0 to 50 (Table 1).

Table 1. Experimental results
Full size table

Experimental results are compared with representative reference [5], which is shown in Table 1. From the comparison and analysis of number of additive swap gates to quantum circuits, we find that in the same test data 23, 4 groups of experimental data present less number of additive swap gates than that in reference [5]; 9 groups of experimental data present equal number of additive swap gates to that in reference [5]; 7 groups of experimental data present more number of additive swap gates than that in reference [5].

We find from Fig. 1 that the optimization efficiency of additive swap gates (qc) in the algorithm proposed in this paper is stable and fruitful in the process of dealing with quantum circuits within the scope of 4 to 8 circuits. By contrast, the algorithm in reference [5] can only deal with more simple quantum circuits within 5 circuits, but the comprehensive algorithm in this paper can deal with quantum gates at a higher quantity level. With the increasing of quantum circuits, the optimization efficiency of the algorithm in this paper has obvious advantages. The optimization efficiency of NNC of quantum circuits for LNN architecture applying the algorithm of optimized evaluation of quantum circuits is 47.22%. This algorithm also has advantages in performance period of CPU on the premise that searched space grow exponentially.

Fig. 1.
figure 1

optimization efficiency comparison chart

Full size image

4 Conclusion

This paper presents an algorithm of adding swap gates to arbitrary quantum gates. While adding swap gates to arbitrary swam gates, the algorithm can produce redundant “swap gates pair” by newly-additive swap gates and existing ones in quantum circuits. Not only can this algorithm reduce the add of swap gates in the process of adding swap gates to arbitrary quantum gates, but also remove an original swap gate in quantum circuits. The algorithm can also accurately compute whether there is any chance that every arbitrary quantum gate can form redundant swap gates pair which is deletable as well as the number of redundant swap gates. We can obtain the number of minimal additive swap gates, that is quantum circuits of minimal qc, within a shorter time applying the algorithm.