QUANTUM EVOLUTIONARY ALGORITHM FOR QUANTUM CIRCUIT SYNTHESIS

Considering the potential benefits that could be achieved from quantum computing devices, the new fields of Quantum Information Theory, Quantum Cryptography, Quantum Algorithms and Logic Design and many others emerged in the late twentieth century [31]. We use the classical accelerated implementation of the Graphics Processing Unit (GPU) to evaluate the behavior and performance of the proposed algorithm.

Introduction

One of the viable approaches that has emerged over the last decade is to create task-specific devices instead of general computers. Due to the relative success of this approach, there is increasing interest in considering different paradigms and insights about solving different computational tasks.

Reversible Computers as a Solution of Problem of Heat Generation . 16

Quantum Computers as an Implementation of a Reversible Com-

The transformations in quantum mechanics are unitary. Furthermore, any operation can be mathematically undone by applying an inverse matrix operation to the system. In this model, the state of the computer evolved over time, and so did each change to the system.

Physical Realization of Quantum Computer

Such systems would be free from dissipating heat demand, in fact they must be completely isolated from interaction with the outside world. The only two allowed interactions with the outside world would be a process of preparing the input and reading the output (quantum measurement).

Motivation for using Quantum Computers

State-of-the-art quantum computing research explores the possibility and feasibility of applying quantum computing algorithms and devices to another active research area: machine learning. This makes research in quantum computing and related problems attractive and important.

The Proposed Quantum Evolutionary Algorithm

Definitions in Vector Form Notation

One of the types of information that can be lost in measurement is the phase. 2.3) By analogy, the normalization condition for qutrits (equation (2.4)) also restricts all possible assignments of 𝛼 and 𝛽 and 𝛾. Equation (2.5) demonstrates an application of a NOT gate to a single qubit state (note the coefficient difference between equation (2.1) and equation. Furthermore, the logic of quantum circuits can be treated as rotations of the qubit state.

Building a quantum register of two or more qubits can be done by applying the Kronecker product to the qubit states. Equation (2.8) shows an example of using the Kronecker product to combine qubits |a⟩ and |b⟩ into a two-qubit quantum register:. 2.8) The multi-qubit states that can be constructed by sequence of Kronecker products of the individual qubits are called separable states [6].

Matrix Form

2.8) The multi-qubit states that can be constructed by sequence of Kronecker products of the individual qubits are called separable states [6]. There are multi-qubit systems that are not in a separable state, but rather in an entangled state [31], the state that cannot be split into a product of single qubit states. The entanglement effect can occur when logic gates affecting two or more qubits are applied in the circuit.

It is possible to influence the states of single qubits in the multi-qubit system as long as it is in a separable state. In matrix form, applying a function to a quantum state means multiplying the desired function represented in a matrix form by the state vector.

Quantum Circuits

Introduction to Quantum Circuits and Logic Design

Alternatively, these individual qubit gates could be represented in matrix form, as described in equation (2.15). To build a multi-qubit gate used for a multi-qubit system, the Kronecker product should be applied to all single-qubit logic gates. In the multi-qubit systems, control gates can be defined as a special class of gates.

This type of gate implements a function that applies to one wire only if the other wires are set to a value, in the case of inverting logic, the value of the control wires must be equal to 1. Figure 2-4 shows one of the most simple possible control, the Feynman gate and its function in matrix form.

Models for Quantum Circuit Design

The basic gate set for the Ising model consists of three single qubit gates representing rotations around the X, Y, Z axes of the Bloch sphere (see Figure 2-1) and two qubit Z interaction gates [17] .

Logic Circuits Design

Problem of Logic Design

Application of Evolutionary Computation to Circuit Synthesis

The population initialization step consists of mapping a problem to the population suitable for evolution. If the solution meeting the desired tolerance was obtained or the maximum number of iterations is reached, the algorithm stops. The purpose of this phase is to identify the best and the worst individuals to be treated in the next phase.

The most famous approaches to selection are stochastic universal sampling, roulette wheel selection, or tournament selection [1]. One of them is to combine and rearrange the genes of the two best candidates for the solution to build a new individual.

Quantum Evolutionary Computation

34; The number of required universes must be identified, i.e. the number of quantum registers, must be well described;. In order to run these algorithms, most studies design a special quantum coding and mapping of evolutionary operators that could potentially enable their algorithm to run on quantum computers. Our quantum evolutionary algorithm for synthesizing quantum circuits has been called a quantum coded quantum evolutionary algorithm because it does not fit directly into any classification of existing algorithms and is not inherently quantum.

This chapter is devoted to the description of the proposed algorithm, the constraints chosen and the optimization strategies used to overcome the increasing difficulty of the search. QE-QEA does not evolve circuits directly; instead a set of quantum gates (segments) are developed as a population.

Quantum Gates Representation

Rotation gates

The rotation angle 𝜃 is represented by the qubit parameter specifying its complex amplitudes: 𝑒−𝑖𝜋𝜃. The axis of rotation is obtained by measuring the state of the qutrit. We repeat the measurement process several times to approximate the state of the qutrit, without removing the uncertainty.

Interaction gates and templates

By introducing interaction matrix templates, we reduced the number of parameters required to construct the interaction gateway to one. The use of templates allows to exclude the 𝑆𝑊 𝐴𝑃 gates that were used to simulate the interaction gates between non-neighboring qubits in the GPGPU version [20] during the evolution process. Note that the number of possible interaction ports relative to their application threads increases slowly with the size of the problem.

During the preparation phase of the algorithm, the template matrices for non-neighboring qubits are constructed as follows from Figure 3-3. When an interaction gate is to be inserted into a quantum circuit, the template must be multiplied by the qubit value.

Population Initialization

Note that the purpose of the coding is, on the one hand, to exploit quantum parallelism and direct coding of quantum circuits directly on the qubits, and on the other hand, it is supposed to be accelerated by current classical parallel technologies. The first eight qubits encoding the circuit segments correspond to the rotation applied to the first input wire (labeled "wire 1" in Figure 3-4). In this particular case, there are exactly eight qubits because the population consists of two individuals of size four.

Similarly, the next eight qubits correspond to rotation on the second wire (labeled "wire 2" in Figure 3-4). The figure does not contain qutrits in it, qutrits are described on figure 3-7.

Circuit Construction

Circuit Segments

Segments Construction

Circuit construction

Fitness Evaluation

Segment Fitness

The fitness value assigned to each segment is the same as the fitness value of the circuit it was built with. Moreover, an elitist approach was implemented: if the new fitness value of a segment is better than the previous best value, the states of the qubits and qutrits are retained, otherwise they are discarded. That is, the same segment will be represented by different fitness values ​​depending on where it was located within the synthesized circuit.

Evolutionary Search

Evaluation of QEQEA

Table 4.1 shows the outputs of the algorithm obtained in the CNOT gate synthesis process. Each row in the table from top to bottom represents the coded circuit segments in the order as they appear in the synthesized circuit. Each row of the table contains all the information needed to decode the circuit segment information.

The third column of the table contains the conditions of the box trip, which after measurement indicates the direction of the rotary gate. Some terms of the matrix have differences from original Toffoli gate, therefore the circuit obtained is not exact, but the error per term is on average ≈0.02.

Experiments Description

A significant (≈70) number of samples were rejected because the approach used differed significantly from that presented in this work. Either implementation errors occurred or the optimization strategy was judged to have a negative impact on the algorithm. The predominance of experiments with the classical fitness function is due to the fact that the function change occurred at a relatively late stage of the work.

Another possible reason is that no specific parameter setting was applied after the Quantum Fitness function was set. Another reasoning, elitist approach would require classical control added to quantum computer running the algorithm.

Comparing QEQEA and GPUGA

Table 4.3 shows the speed differences in obtaining the different ports for which we tested both algorithms. Note that in all cases the classical algorithm was faster than the QEQEA algorithm (iteration of QEQEA takes significantly more time). The reason is the fact that the QEQEA develops gates instead of entire circuits, while the classic GA develops entire circuits.

The first and third columns of Table 4.3 show the accuracy of the best results achieved by each algorithm. The iteration number could also serve as a benchmark for performance comparison, but for the QEQEA this data is only partially available.

Discussion and Future Work Suggestion

As an important extension of the algorithm, synthesis can be restarted after convergence to local maxima has been achieved. The expansion should be aimed at finding 𝑇 𝑎𝑟𝑔𝑒𝑡⊕𝑅𝑒𝑠𝑢𝑙𝑡 which can later be used to find better results. The algorithm could benefit significantly from an extension that would allow the sequences of segments to be preserved.

Now the segments are fixed to position in the circle, but grouping them and calculating fitness of group segments might help.

Conclusion

In other words, even if all components of the algorithm were made compatible with quantum implementation, many components would remain classical. The comparison with the classical GPUGA showed that the quantum evolutionary model shows worse performance than the classical evolution. The lower performance is due to the many limitations included in the QEQEA, which have resulted in a strong simplification of the evolutionary process.

In a quantum computer, an efficient implementation requires exploiting the properties of entanglement that would make the search much more efficient. Evolutionary Quantum Logic Synthesis of Reversible Logic Embedded Logic Circuits in Triple Quantum Space Using Heuristics, 2011.