Open access peer-reviewed chapter

# Evolutionary Logic Synthesis of Quantum Finite State Machines for Sequence Detection

By Martin Lukac and Marek Perkowski

Published: February 1st 2010

DOI: 10.5772/8049

## 1. Introduction

Quantum Finite State Machines (QFSM) are a well known model of computation that was originally formalized by Watrous [Wat95a, Wat95b, Wat97], Kondacs [KW97] and more generally Quantum Turing Machines (QTM) have been described by Bernstein [BV97]. In particular the 2-way QFSM have been shown to be more powerful than classical FSM [KW97]. Thus the interest in quantum computational models of automata and machines is not only theoretical but has also possible applications realization of future quantum computer and robotics controllers.

In this chapter we present the evolutionary approach to the synthesis of QFSM’s specified by a quantum circuits. This approach was originally proposed by [LP09] and is possible on yet only theoretical basis. In particular this approach requires a selective qubit-initialization in a quantum register. In contrast the current methodology and approaches to practical Quantum Computation, the current practical realization of quantum computation always starts with the initialization of the whole quantum register and terminates by the measurement of either all of the qubits or by the measurement of a given subset of qubits. Moreover in general there is no reuse of any element of the quantum register.

In this text we analyze in details what type of QFSM can be successfully synthesized.

The evolutionary approach will evaluate the results based on both the correctness and the cost of the evolved machines. Multiple parameters such as type of error evaluation, synthesis constraints and evolutionary operators will be discussed when evaluating to the obtained results.

In particular we show how to synthesize QFSMs as sequence detectors and illustrate their functionality both in the quantum world and in the classical (observable) world. The application of the synthesized quantum devices is illustrated by the analysis of recognized sequences.

Finally, we provide analytic method for the used evolutionary approach and we describe the experimental protocol, and its heuristic improvements. We also discuss the results. In addition, we investigate the following aspects of the Evolutionary Quantum Logic Synthesis:

• Quantum probabilistic FSM and Reversible FSM.

• Hardware acceleration for the Fitness evaluation using CBLAS [cbl] and using CUBLAS [cud] (CUDA[cud] implemented Basic Linear Algebra Subprograms (BLAS)[cbl] subroutines).

## 2. Background in quantum computing

In Quantum Computing the information is represented by a Quantum Bit also called qubit. The wave equation is used to represent a qubit or a set of them. Equation 1 shows a general form in the Dirac notation.

|ϕ=eiρcosθ+ei(ρ+ψ)sinθ|ϕ=eiρ(cosθ+eiψsinθ)E1

In Dirac notation represents a column vector, also called a ket. The bra element denoted stands for hermitian conjugate. In this manner a bra-ket represents the inner, dot-vector product while represents the outer vector product. The general equation (1), eiρcosθ|0+ei(ρ+ψ)sinθ|1can be written as α|0+β|1with|α|2+|β|2=1and |α|2is the probability of observing the state 0 while |β|2is the probability of observing 1.

In general, to describe basis states of a Quantum System, the Dirac notation is preferred to the vector-based Heisenberg notation. However, Heisenberg notation can be more practical to represent the exponential growth of the quantum register. Let two orthonormal quantum states be represented in the vector (Heisenberg) notation eq. 2.

|=|0=[10]|=|1=[01]E2

Different states in this vector notation are then multiplications of all possible states of the system, and for a two-qubit system we obtain (using the Kronecker product[Gru99, Gra81, NC00]) the states represented in eq. 3:

|00=[10][10]=[1000]            |10=[01][10]=[0010]|01=[10][01]=[0100]            |11=[01][01]=[0001]E3

The Kronecker product exponentially increases the dimension of the space for matrices as well:

IX=[1001][0101]=12[0100100000010010]E4

This tensor product operation for a parallel connection of to wires is shown in Figure 1.

Assume that qubit a (with possible states |0 and |1) is represented by|ψ=αa|0+βa|1and qubit b is represented by|ψb=αb|0+βb|1. Each of them is represented by the

superposition of their basis states, but put together the characteristic wave function of their combined states will be:

|ψaψb=αaαb|00+αaβb|01+βaαb|10βaβb|11E5

with a and b being the complex amplitudes of states of each EP respectively. As shown before, the calculations of the composed state used the Kronecker multiplication operator. Hence comes the possibility to create quantum memories with extremely large capacities and the requirement for efficient methods to calculate such large matrices.

Quantum Computation uses a set of Quantum properties. These are the measurement, the superposition and the entanglement. First, however, the principles of multi-qubit system must be introduced.

### 2.1. Multi-Qubit System

To illustrate the superposition let’s have a look at a more complicated system with two quantum particles a and b represented by |ψa=α0|0+βa|1and |ψb=αb|0+βb|1respectively. For such a system the problem space increases exponentially and is represented using the Kronecker product [Gru99].

|ψa|ψb=[α0β0][α1β1]=[α0α1α0β1β0α1β0β1]E6

Thus the resulting system is represented by |ψaψb=αaαb|00+αaβb|01+βaαb|10+βaβb|11(5) where the double coefficients obey the unity (completeness) rule and each of their powers represents the probability to measure the corresponding state. The superposition means that the quantum system is or can be in any or all the states at the same time. This superposition gives the massive parallel computational power to quantum computing.

### 2.2. Entanglement and projective measurements

Assume the above two-particle vector (two-qubit quantum system) is transformed using the quantum circuit from Figure 2.

This circuit executes first a Hadamard transform on the top qubit and then a Controlled-Not operation with the bottom qubit as the target. Depending on the initial state of the quantum register the output will be either|ψaψb=αaαb|00+βaβb|11or|ψaψb=αaβb|01+βaαb|10. Thus it is not possible to estimate with 100% probability the initial state of the quantum register.

Let |ab=|00at level a (Figure 2). The first step is to apply the [H] gate on the qubit-a and the resulting state at level b of the circuit is
|ab(HW)|ab=12(|0+|1)|0=12(|00+|10)=[120120]E7

Next the application of the CNOT gate results in:

|ψaψb12(1000010000010010)x(1010)=12(1001)=12(|00+|11)E8

For an output 0 (on the qubit-a), the projective measurement of the first (topmost) qubit (qubit-a on Figure 2) on this stage would collapse the global state (with a single measurement) to the state |00:

|abM0|abab|M0M0|ab=[1000]T=|00E9
with
M0|ab=12[1000010000000000][1001]=12[1000]E10
and
ab|M0M0|ab=12[1001][1000010000000000][1001]=12[1001][1000]=12E11

Similarly, the probability of measuring output on the qubit-a in state |0 is:

p(0)=[120012]([1000000000000000]+[0000010000000000])[120012]=[120012][1000010000000000][120012]=12E12

If one would look to the output of the measurement on the second qubit (qubit-b), the probability for obtaining |0 or |1 is in this case the following:

p(0)=[120012]([1000000000000000]+[0000000000100000])[120012]=[120012][1000000000100000][120012]=p(1)=12E13

Thus the expectation values for measuring both values 0 or 1 on each qubit independently are12.

If however one looks on the second and non-measured qubit (if the qubit-a is measured, it is the qubit-b, and vice versa) and calculates the output probabilities, the output is contradictory to the expectations given by standard probabilistic distribution such as a coin toss q = 1 − p. To see this let’s start in the state

[120012]E14

and measure the qubit-a and obtain a result. In this case assume the result of the measurement is given by:

|ψM0|ψψ|M0M0|ψ=[1000]E15

Then measuring the second qubit (qubit-b) will not affect the system because the measurement of the qubit-a has collapsed the whole system into a single basis state:

|ψM|00E16

The probability for obtaining a |1 on the qubit-b is thus 0 and the measurement on qubit-b (after having measured qubit-a) has no effect on the system at all. The states of qubits are thus correlated. This non-locality paradox was first described by Einstein-Podolsky-Rosen work[EPR35] and is known as the EPR paradox. This particular phenomenon is one of the most powerful in quantum mechanics and quantum computing, as it allows together with superposition the speedup of finding solutions to certain types of problems. Finally, it can be noted that mathematically, the entangled state is such that it cannot be factored into simpler terms. For example, the state (|00+|01)212(|0+|1)|0and thus it can be factored. However, the states as those introduced in eq. 15 cannot be transformed in such a manner and are thus entangled; physically implying that they are related through measurement or observation.

### 2.3. Single-Qubit quantum gates

We are now concerned with matrix representation of operators. The first class of important quantum operators are the one-qubit operators realized in the quantum circuit as the one-qubit (quantum) gates. Some of their matrix representations can be seen in equation 17.

a)X=[0110]          b)Y=[0ii0]          Z=[1001]d)H=12[1111]          e)V=(1+i)2[1ii1]          f=Phase[100i]E17

Each matrix of an Operator has its inputs from the top (from left to right) and the outputs on the side (from top to bottom). Thus taking a state |ψ(eq.18) and an unitary operator H (eq. 19)

|ψ=α|0+β|1E18
H=12[1111]E19

the result of computation is represented in equation 20.

H|ψ=12[1111][αβ]=[α+β2αβ2]E20
00  01   10   11                                                 U=00011011[1000010000010010]E21

Equation 21 shows the inputs (input minterms) on the top of the matrix and the output minterms on the left side. Thus for an input |10 (from the top) the output is |11 (from the side).

### 2.4. Multi-Qubit quantum gates

The second class of quantum gates includes the Controlled-U gates. Schematic representation of such gates can be seen in Figure 3. Gates in Figure 3a – Figure 3c represent the general structures for single-control-qubit single-qubit gate, two-control-qubit single-qubit gate, single-control-qubit two-qubit gate and two-control-qubit two-qubit gate respectively. The reason for calling these gates Controlled is the fact that they are based on two operations: first there is one or more control bits and second there is a unitary transformation similar to matrices from equation 17 that is controlled. For instance the Feynman gate is a Controlled-NOT gate and has two input qubits a and b as can be seen in

Figure 3. Its unitary matrix with input and output minters is shown in eq. (21). Thus qubits controlling the gate are called the control qubits and the qubits on which the unitary transform is applied to are called the target qubits.

Figures 3d - Figure 3f represent special cases where the controlled unitary operator is Not, Not and Swap, respectively. The respective unitary matrices are in equations 21, 22a and 22b.

Equation 21 shows that if the input state is for instance |00 (from the top) the output is given by. Similarly for all other possible input /output combinations.
(a)[1000000001000000001000000001000000001000000001000000000100000010](b)[1000000001000000001000000001000000001000000000100000010000000001]E22

The Controlled-U gate means that while the controlled qubit a is equal to 0 the qubits on output of both wires are the same as they were before entering the gate (a’ = a, b’ = b). Now if qubit a equals to 1, the result is a’ = a and b’ = b according to matrix in equation (17.a). It can be easily verified that the CCNOT (Toffoli) gate is just a Feynman gate with one more control qubit and the Fredkin gate is a controlled swap as shown on Figure 3.

A closer look at equations (21 and 22) gives more explanation about what is described in eq. 21: CNOT, eq. 22a : Toffoli and eq. 22b : Fredkin gates. For instance, equation 21 shows that while the system is in states |00 and |01 the output of the circuit is a copy of the input. For the inputs |10 and |11 the second output is inverted and it can be seen that the right-lower corner of the matrix is the NOT gate. Similarly in the other two Controlled gates the NOT gate matrix can be found.

### 2.5. NMR-based quantum logic gates

The NMR (Nuclear Magnetic Resonance) technology approach to quantum computing [Moo65, PW02, DKK03] is the most advanced quantum realization technology used so far, mainly because it was used to implement the Shor algorithm [Sho94] with 7 qubits [NC00]. Yet other technologies such as Ion trap [DiV95], Josephson Junction [DiV95] or cavity QED [BZ00] are being used. The NMR quantum computing has been reviewed in details in [PW02, DKK03] and for this paper it is important that it was so far the NMR computer that allowed the most advanced algorithm (7 qubit logic operation) to be practically realized and analyzed in details. Thus it is based on this technology that the constraints of the synthesis are going to be established for the cost and function evaluation. Some prior work on synthesis has been also already published [LLK+06] and few simple cost functions have been established.

For the NMR-constrained logic synthesis the conditions are:

1. Single qubit operations: rotations Rx,Ry,Rz for various degrees of rotation . With each unitary rotation (Rx, Ry, Rz) represented in equation 23

2. Two-qubit operation; depending on approach the Interaction operator is used as Jzz or Jxy for various rotations

Rx(θ)=eiθX/2=cosθ2Iisinθ2X=(cos(θ2)isin(θ2)isin(θ2)cos(θ2))Ry(θ)=eiθY/2=cosθ2Iisinθ2Y=(cos(θ2)sin(θ2)sin(θ2)cos(θ2))RZ(θ)=eiθZ/2=cosθ2Iisinθ2Z=(eiθ/200eiθ/2)E23

Thus a quantum circuit realized in NMR will be exclusively built from single qubit rotations about three axes x,y,z and from the two-neighbor-qubit operation of interaction allowing to realize such primitives as CNOT or SWAP gates. Examples of gates realized using NMR quantum primitives are shown in Figure 5 to Figure 8.

Also, the synthesis using the NMR computing model using EM pulses, is common to other technologies such as Ion Trap [CZ95, PW02] or Josephson Junction [BZ00]. Thus the cost model used here can be applied to synthesize circuits in various technologies, all of these technologies having the possibility to express the implemented logic as a sequence of EM pulses.

## 3. Quantum finite state machines

The paradigms of quantum circuits from Section 2 are applied in this paper to the synthesis of computational models such as QFSM as defined in [LPK09]. This section briefly introduces the knowledge about Quantum computational models and their properties as well as specifies the types of devices that are going to be synthesized. We describe the 1-way Quantum Finite State Machines (FSM) from both the theoretical (computational) point of view as well as from the engineering (circuit) point of view. Most of the work in this area is still on the theoretical level but the proofs of concept quantum devices [Dun98, SKT04, MC06, RCHCX+08, YCS09] allow to speculate that such models will be useful for quantum logical devices that will appear in close future.

### 3.1. 1-way quantum finite automata

Quantum Finite State Machines (QFSM) are a natural extension of classical (probabilistic) FSM’s. Two main types of QFSM are well known: One-way QFSM (1QFSM) [AF98, MC00] and two-way QFSM (2QFSM)[AW02, KW97]. As will be illustrated and explained the 1QFSM, can accept sequentially classical input, quantize it, process it and measures its quantum memory after each operation (Figure 9). In this work the focus is on the synthesis of the 1QFSM from Figure 9(b). From now on the general designation of QFSM will refer to 1QFSM in this work. Other type of described QFSMs will be specifically named.

In contrast to that, the 2QFSM is designed to operate on quantum input data (allowing to put the reading head in superposition with the input tape, and requiring all the input data to be present at once for the maximum efficiency) and the measurement is done only at the end of a whole process.

Definition 3.1

Quantum State Machine - a QFSM is a tuple Γ = {Q,Λ, q0,Qac,QrjI, δ}, where Q is a finite set of states, σ is the input alphabet, δ is the transition function. The states q0 Q′, Qac Q and Qrj Q are the initial states, the set of accepting states and the set of rejected states, respectively.

The QFSM machine action maps the set of machine states and the set of input symbols into the set of complex machine next states. The computation of such machine is required to be done using unitary operators and is performed on the basis set Bq using unitary operators U, . In particular the QFSM uses a set of Unitary Operators corresponding to the input of input characters on the input tape. Thus for a given string to be processed and prior to the whole process termination (string either accepted or rejected), the overall processing can be represented as:

MUθnMUθn1MUθn2...MUθ3MUθ2Uθ1|q0E24

with MUθnbeing the application of the Uθnoperator to the current state and creating the configuration Uθn|q followed by the measurement of the current state M (projecting the state into G).

The 1QFSM was proven to be less powerful or equally powerful to its classical counterpart 1FSM [Gru99, KW97] in that it can recognize the same classes of regular languages as the classical FSM can recognize.

The above described 1QFSM is also called the measure-many quantum finite automaton [KW97]. A model called measure-once quantum finite automata was also introduced and studied by Moore [MC00]. The measure-many 1QFSM is similar to the concepts of the 2QFSM. For comparison we illustrate the main differences between the 1QFSM and 2QFSM below.

Example 3.1.1 1QFSM

Let Q={|q0,|q1}be two possible states (including the accepting and rejecting states) of a single-qubit machine M and with transition functions specified by the transitions defined in eq. 25 corresponding to the state diagram in Figure 10a.

V#|qi=|qiV$|q0=|qacV$|q1=|qrj          V0|qi=12|q0+12|q1V0|qi=12|q012|q1V1|q0=|q0V1|q1=|q1E25
V#|qi=|q0V$|q0=|qacV$|q1=|qrjE26

The machine M, specified in eq. 25 represents a state machine that uses the H gate when the input is 0 (V0 = H) and the Pauli-Z rotation gate when the input is 1 (V1 = Z). Observe that machine M would have different behavior for measure-once and measure-many implementation. In the measure-many case, the machine generates a quantum coin-flip while receiving input 0 and while receiving input 1 the Pauli-Z rotation is applied. Observe in the measure-once case, that for example for the string input = ”010” the many-measure machine will implement a NOT using [H][Z][H]. Note that in this approach to QFSM each input symbol {#, \$, 0, 1} is represented by a unitary transform that can be seen as shown in Figure 10. No measurement is done here on |q while the sequence of quantum operators is applied to this state. The 2QFSM operates on a similar principle as the 1QFSM model but with the main difference being the application of the measurement. This is schematically shown in Figure 11 for the completeness of explanation.

### 3.2. Quantum logic synthesis of sequence detectors

The problem to synthesize the QFSM is to find the simplest quantum circuit for a given set of input-output sequences thus letting the state assignment problem for this machine be directly solved by our synthesis algorithm. This direct synthesis approach can be applied to binary, multiple-valued and fuzzy quantum machines with no principle differences - only fitness functions are modified in an evolutionary algorithm [LPG+03, LP05].

Let us assume that there exists a sequential oracle that represents for instance Nature, robot control or robot’s environment. In our example this oracle is specified by a state diagram in Figure 12a. This oracle can represent partial knowledge and a deterministic or probabilistic machine of any kind. Assume that there is a clearing signal (denoted by an arrow in Figure 12a) to set the oracle into its initial state. By giving initial signals and input sequences and observing output sequences the observer can create a behavior tree from Figure 12b.

As in general this oracle is never fully known, we perform experiments with it to determine some of its input-output behaviors. Assume that the oracle from Figure 12a is represented by the sequences from the experiments. These input-output sequences are shown in eq. 26 with |iqo represents the input qubit, the state qubit and the output qubit respectively. Observe that the diagnostic tree form Figure 12(b) shows the state with {a, b} and the inputs and the outputs as 0 and 1.

|iq0|iq0000011001011100111101110110101111101E27

As the full knowledge of the oracle is in general impossible - the oracle is approximated by sets of input-output sequences and the more such sequences that we create - the more accurate characterization of the oracle as a QFSM can be created.

The overall procedure for the detection of a sequence of length j can be summarized as follows:

1. Initialize all qubits of the quantum register to the initial desired state,

2. repeat j times:

• Initialize the input qubit to a desired state and set the output qubit to |0

• Apply the quantum operator on the quantum register of the QFSM

• Measure the output qubit and observe the result

Using the procedure describe above one can synthesize quantum circuits for oracles being well known universal quantum gates such as Fredkin. The input-output sequences found from this oracle are next used to synthesize the QFSM from Figure 13a. Figure 13b shows the state-diagram of the machine.

We will call the machine in Figure 13(a) the QFSM of the first class. This is because both the output and the input qubits are initialized after each computation. Observe that it is represented with feedback lines as in Figure 9 with input and output being initialized for each input and the state initialized only once - at the beginning of the computation. The interested reader can read more on this representation in [LP09], however it is important to understand that the feedback lines are shown here only as the equivalent notation to the classical FSM as in Figure 9. The circuit-based approach to QFSM does not require this notation as this ”loop” is represented by the fact that the quantum qubit preserves its state [LP09].

A set of input-output sequences defining partially the "Fredkin QFSM" is represented in eq. 27.

|iq0|iqo000000001000100100101100110101111101E28

A class two QFSM has in turn the initialization In applied only to the input qubit. This way the generated sequence is now expressed not only as a function f(i,q)|0but rather asf(i,q)|0. This means that now the output is directly dependent also on the previous output state. This QFSM of the second class is shown in Figure 14. The difference between the QFSM of the first and of the second class can be seen on the output qubit |0where in the case of the QFSM of the first class the initialization Inomeans the initialization of the output at each computation step while the class two QFSM uses I0oinitializes the output only once, at the beginning of the computation.

For instance, a class two QFSM constructed from a "Fredkin oracle" differs from the class by different possible state transition. This is shown in Table 1. The first column represent the current state of the quantum register build from the input, state and output qubits |iqo. The second column shows the state transitions of the class one QFSM. Observe that as the output qubit is always being initialized to |0 only four possible initial states exists (see eq. 27). The third column representing the state transitions of the class two QFSM and as can be seen in this case the state transition function is the full "Fredkin oracle" function.

Moreover, the difference between the first and the second class of these QFSM’s has also deeper implications. Observe that the QFSM presented in this paper, if implemented without the measurement on the output and the input qubit (the measurement is executed only after l computational steps) the QFSM becomes the well-known two-way QFSM

[KW97] because the machine can be in superposition with the input and the output. This is equivalent to stating that the reading head of a QFSM is in superposition with the input tape as required for the time-quadratic recognition of the {anbn} language [KW97].

Observe that to represent the 1-way and the 2-way QFSM in the circuit notation the main difference is in the missing measurement operations between the application of the different CU (Controlled-U) operations. This is represented in Figures 15 and 16 for 1-way and the 2-way QFSMs, respectively.

An interesting example of QFSM is a machine with quantum controls signals. For instance a circuit with the input qubit in the superposition generating the EPR quantum state [NC00] is shown in Figure 17.

Observe the behavior of this QFSM as both class one and class two machine given in Table 2. In this case the distinction between the class one and class two machines is negligible because any measurement of the system collapses the whole system as the result of the entanglement present in it.

Figure 17 shows that because of the entanglement this machine has two distinct possible recognizable sequences. When the machine uses exclusively the output qubit initialized to |0 the possible initial states are only |00 and |10 because the measurement of the output state resulting in |11In0|10and|01In0|00.

## 4. Evolutionary algorithms and quantum logic synthesis

In general the evolutionary problem solving can be split into two main categories; not separated by the methods that each of the trends are using but rather by the problem representation and by the type of problem solved. On one hand, there is the Genetic Algorithm (GA) [Gol89, GKD89] and Evolutionary strategies (ES) [Bey01, Sch95] that in general represents the information by strings of characters/integers/floats and in general attempts to solve combinatorial problems. On the other hand the design of algorithms as well as state machines was traditionally done by the Genetic Programming (GP) [Koz94, KBA99] and the Evolutionary Programming (EP) [FOW66, ES03].

Each of this approaches has its particular advantages and each of them has been already more or less successfully applied to the Quantum Logic synthesis. In the EQLS field the main body of research was done using the Genetic Programming (GP) for the synthesis of either quantum algorithms and programs [WG98, Spe04, Lei04, MCS04] or some specific types of quantum circuits[WG98, Rub01, SBS05, SBS08, LB04, MCS05]. While the GP approach has been quite active area of research the Genetic Algorithm approach is less popular and recently only [LP08, YI00] were using a Genetic Algorithm for the synthesis of quantum circuits. However, it was shown in [LP09] that it is also possible to synthesize quantum finite state machines specified as quantum circuit using a GA. The difference between the popularity of the usage between the GP and the GA for EQLS is mainly due to fact that the problem space of quantum computing is not well known and is extremely large. Thus synthesizing quantum algorithms or circuits using the circuit approach (as in GA) can be much harder than using a rule-based or a program based approach (as in GP). Thus one could conclude that the GP approach deals only with the required information (programming, logic rules, relations) while the GA circuit based approach synthesize the overall unitary operator without any regards to the structure of the required information itself.

## 5. Genetic algorithm

A Genetic algorithm is a set of directed random processes that make probabilistic decisions - simulated evolution. Table 3 shows the general structure of a GA algorithm used in this work and this section follows this structure with the focus on the information encoding in the individuals and on the evaluation of the designed QFSMs that are created by the GA.

### 5.1. Encoding/Representation

For quantum logic synthesis the representation that we use is based on the encoding introduced in [LPMP02]. This representation allows to describe any Quantum or Reversible circuit [LPG+03, LP02]. All individuals in the GA are strings of ordered characters (each character representing a quantum gate) partitioned into parallel Blocks (Figure 18). Each block has as many inputs and outputs as the width of the quantum array (five in the case

of Figure 18). The chromosome of each individual is a string of characters with two types of tags. First a group of characters is used to represent the set of possible gates that can be used in the individual string representation. Second, a single character ’p’ is used as a separator between parallel blocks of quantum gates. An example of a chromosome can be seen in Figure 18. In this encoding each space (empty wire or a gate) is represented by a character with appropriate decoding shown. Our problem-specific encoding was applied to allow the construction of as simple genetic operators as possible. The advantage of these strings is that they allow encoding of an arbitrary QL or RL circuit without any additional parameters. Several such parameters were used in previous research [LPG+03, LP05] and using them made the genetic algorithm more complicated. Please note that only the possibility to move gate characters, remove and add them to the chromosome consequently make it possible to construct an arbitrary circuit and also to modify this circuit in order to optimize it.

### 5.2. Initialization steps of GA

The GA requires an input file (c.f. Pseudo-Code 28 and Pseudo-Code 29) which specifies all input parameters and required settings.

20:Measurment:121:Measured qubits indexes:022:1622:0:(1,0)23:1:(1,0)...38>0>(1,0)E29

However, for the clarity of explanation we focus only on particular settings required for the synthesis of the QFSM. The lines (20-38) shows the to search for a QFSM recognizing a sequence, first the measurement is required (line 20), the index of the output qubit is given (line 21) and finally the desired input sequence is given. This is done by both specifying the input value (here 0 or 1) and the probability of detection (here 1). Observe that the probabilities are specified as complex numbers with only the real component defined, e.g. (1,0). The use of complex coefficients for these observation probabilities is due to the fact that as in our previous work [LP05, Luk09] it allows to specify don't cares. For instance the coefficient (0,1) represents a logical don't care.

The GA has several other settings, (common to most of GA methods) but also requires to specify circuit specific parameters. The initial circuits are created with a random size within the interval specified by a maximal (tmax) and minimal number of segments (tmin) in each individual (chromosome). Thus the size of the chromosome is not limited during the lifetime of an individual to a precise value, rather each individual has a dynamically changing genome within the bounds defined by the above variables. The presented GA is a subclass of the Messy GA [GKD89].

Another important parameter is related to the cost of the implemented Quantum Circuit. Each evolutionary run has specified the minimal cost MinCost that represents the known minimum for the target function or device. If such minimal value is not known, a small value is used so that it always underestimates a possible minimal cost of the implementation. This circuit cost value is used in the cost function described in Section 5.4.1.

44:145:146:wire47:(1,0)(0,0)48:(0,0)(1,0)...64:265:166:Controlled_V66:(1,0)(0,0)(0,0)(0,0)67:(0,0)(1,0)(0,0)(0,0)68:(0,0)(0,0)(0.5,0.5)(0.5,0.5)69:(0.5,0.5)(0.5,0.5)(0,0)(0,0)E30

The input specifications also include the elementary quantum gates to be used as components, like the single qubit H, X, Y, Z or V gates and two qubit operations such as CNOT or CV, which are the building blocks of the quantum circuits to be found. The quantum gates are represented as quantum unitary (and Hermitian) matrices with the cost specified for each gate. This is shown in eq. 29, where for each input gate the number of wires and its cost is given as well. For instance, lines 66 to 69 in eq. 29 shows the unitary matrix of the CV gate[BBC+95], line 64 shows the number of qubits of this gate and the line 65 shows its cost.

Observe that each unitary matrix is specified by complex coefficients with real and imaginary component. For instance (1, 0) represents the real state while (0.5, 0.5) represents a complex state with coefficient1+i2.

In the presented experiments various sets of Quantum gates have been used but only the most succesful runs are presented. In particular only circuits with the most common gates are shown. These gates include single-qubit gates such as Pauli rotations, the V and V gates, two-qubit gates such as CNOT, CV and CV and three-qubit macros such as Toffoli gates.

### 5.3. Evaluation of synthesis errors in sequential quantum circuits

In order to properly evaluate a a QFSM for sequence detection the measurement operation must by applied on several occasions during the detection procedure. As was explained in the section 2, a quantum system must be measured in order for the information to be obtainable and readable in the macro world. Moreover, the measurement is a vital operation if one desires to reuse a quantum state. Recently, it was proven that a unknown quantum state cannot be completely erased [PB99] but is also easily understandable by observing the nature of the quantum computing.

The simplest explanation of the impossibility of completely erase an unknown state is due to the fact that there is no such a reversible quantum operation that would bring any quantum state to let’s say the |0 state. This is because every reversible operation is a permutation (even when it contains complex coefficients) and any operation that would achieve such a state reduction is inherently non reversible and by default non-quantum. An example of such non-reversible operation is shown in eq. 30.

Ξ|ψ|0Ξ=(1100)E31

Thus measuring a quantum state allows to determine its observable and consequently allows to apply a Unitary transformation that would generate the desired state. The model of computation for Quantum Finite State Machines proposed in [LPK09] is used here as model. Figure 19 shows steps of evaluation of a sequential Quantum Circuit. Observe that this QFSM has one qubit |q for state, one qubit |i for input and one qubit |o for output. From the classical point of view this can be seen as an instance of a Mealy finite state machine.

The synthesis process generates a unitary transformation matrix U, that during the evaluation is applied to the sequence of quantum states. Observe that both the input qubit and the output qubit must be measured in order to preserve a valid quantum state qubit |q as well as allow to properly restore both the input and the output qubit. After each iteration of the computation (application of the U operator) the output qubit is set to |0 while the input qubit is set to either |0 or |1 depending on the the user specifications from the input file.

Equation 31 shows the first and the last step of the QFSM evaluation for the detection of the input sequence starting with s = {10011001110001}. Note that the detection requires that for all the input values but the last one the output qubit is set to |0 and is set to |1 for the last character.

|000I11|010|010U|ψ|ψMo|ρ|o|ρ|op0(0)M1|q|i|o...|q00I11|010|q10U|ψ|ψM1|ρ|o|ρ|op0(1)M1|q|i|oE32

At the end of each evaluation sequence, the state of the output qubit and of the input qubit is determined by the measurement and can be reset with desired Unitary transformation to either |0 or to |1. The machine state qubit |q is known only at the beginning of each evaluation sequence. This means that the state of the qubit can be in superposition or an orthonormal state. This also means that the machine state can be a multi qubit state that can become entangled between the various state qubits.

Finally, the evaluation process is recored as a set of probabilities denoted as p0(0) and p0(1). They represent the probability of observation of the desired output 0 or 1 during the sequence detection. In particular, in this case the overall correctness of the detection can be written as:

p(s)=p0(0)*p0(0)*p0(0)*...*p0(1)=[n2p0(0)]*p0(1)E33

To evaluate the error of the detector either the eq. 32 was used as a direct measure (it represents the correctness of the detection with respect to the selected observables), or a more standard calculation was used. The eq. 33 shows the standard RMS error computation. Both of these error evaluations are compared in the experimental section of this work.

p(s)=1n([j=0n2(1pj0(0))2]+(1pn10(1))2)E34

### 5.4. Fitness functions of the GA

During the search for the QFSM’s a parameterized fitness function was used. This was done in order to allow the minimization for both the error and the cost of the synthesized Quantum circuit. This "weighted function" methodology was based on our previous experience in the evolutionary quantum Logic synthesis [LPG+ 03, LP05, LP09].

The parameterization allows to select the weight with which the error of the circuit and the cost of the circuit modifies the overall fitness value. The choice of this weight is left on the user that can decide what criteria of evaluation is more important. However, we experimentally determined some optimal settings that allowed correct circuits with minimal cost to be synthesized.

#### 5.4.1. The cost function

The cost function is based on a parameter known as the minimum cost that is provided by the user and that permits to estimate a normalization constant. This means that the cost function acts as a bonus inversely proportional to the size of the circuit to the fitness function for a given estimated and unreachable minimum. In this work the cost function is defined by

G(c)=exp(MinCostCost)2Cost22E35

where Mincost is the parameter given by the user and Cost, given byj1kcj, is the sum of costs of all gates in the evolved circuit. Equation 34 was experimentally determined to be sensitive enough to influence both circuits far and close to the optimal cost.

#### 5.4.2. The weighted fitness function

The weighted fitness functions used is shown in eq. 35 and an alternative version is in eq. 36. Both equations calculate the fitness value using the fitness function and the cost function together. In this case, the error of the circuit (QFSM) is calculated with respect to the overall probability of detecting the desired sequence as specified by eq. 32.

Each component of these weighted functions can be adjusted by the values of parameters and .

f3=α(1e)+βG(c)E36
f3=α(1e+1)βG(c)E37

The reasons for these various fitness functions are the following:

1. to allow different selection pressures during the individual selection process,

2. by calibrating the cost to always underestimate the minimal possible size of the desired circuit it is possible to further manipulate the selection process.

3. the parameterization allows in the extreme cases to completely eliminate the cost component and thus also includes fitness functions solely based on the correctness of the circuit.

For instance the fitness function 35 is not equal to one, unless both the cost of the circuit and the error are minimal. Thus a GA using such a weighted function has more freedom for searching a solution, because the fitness function is now optimizing the circuit for two parameters. Similarly in the case of the fitness function 36 which decreases the value of the fitness of longer circuits, therefore preferring the shorter ones. Thus individuals with different circuit properties will have equal fitness value.

### 5.5. Other evolutionary settings

For the clarity and the focus of this paper we present the rest of the settings in the Table 4. Only the final parameters are shown and in particular only those that were used during the runs that generated the presented results. To sum it up, the SUS[Bak87] selection method was used with n = 4 individuals. The mutation operator was used both on the level of individual quantum gates but also on the level of the parallel blocks. The crossover was a two parent, two point recombination process that preserves the width of the quantum circuit by selecting cut points only between the parallel blocks.

### 5.6. CUDA acceleration

The CUDA framework was developed by NVIDIA for the growing usage of the GPU for computing tasks. The acceleration implemented in the GA is restricted only to the matrix calculation. Figure 20 shows where the CUDA acceleration is used.

The reason for using the accelerated matrix multiplication only during the matrix multiplication and not for the Kronecker matrix product is the fact that the Kronecker product is less computationally expensive as it requires only 2n ×2n multiplications while the matrix product requires 2n×2n multiplications and 2n additions. Moreover, in order to maximize the CUDA usage it is more optimal to use multiplication on matrices of the same dimensions without requiring to re-parameterize the CUDA device. This is the case in the matrix multiplication between each parallel block in a Quantum Circuit.

## 6. Experiments and discussion

The experiments carried in this section confirms the possibility to design classical sequence detectors using the 1-way (measure many) circuit-based QFSM’s model. The experimentation was done over a set of random sequences of various length. Each sequence was being tested for circuits with different number of state qubits. This was done in order to observe the role of embedding of the non-reversible sequence into a larger, reversible unitary matrix.

The general function that the QFSM generates on the output is described by the eq. 37

o(λ)={1ifj<length(s)0o.w.}E38

with being a symbol read from the input and j is the index of the symbol in the sequence. Thus the minimal condition for each sequence to be detected properly is that the amount of the states is large enough to embed all the zero output to one half of the truth table. this is a required consequence because the QFSM must have both the output function and the state transition function reversible.

The experimentation was done for 5 randomly generated binary sequences with 7, 10, 15, 20 and 35 binary digits each. The sequences are shown in eq. 38

s7={0101111}s10={1011011000}s15={010100110101011}s20={01011111000111100111}s25={1011011110100101111000010}E39

Each sequence was synthesized using a circuit with 3,4,5 and 6 qubits. The six qubit circuit is large enough to embed even the largest sequence so as a reversible function is synthesizable. Figures 21, 24 and 27 shows some examples of obtained circuits for each of the sequences.

Figure 21 is an example of Quantum Circuit that was used to detect the s 7 sequence and does not use any probabilistic states. For the sake of understanding let us analyze the sequence detection procedure using this circuit. The desired sequence is s 7 = { 0 1 0 1 1 1 1 } thus the set of input states is given by{|0F|00,|ϕ10,|ϕ00,|ϕ10,|ϕ10,|ϕ10,|ϕ10}, with | being the unmeasured component of the automata state. Naturally there are cases where it is going to be determined by the measurement but for the clarity it is left in symbolic form and thus allowing it to be in superposed or entangled state.

The size of the QFSM is four qubits with two topmost qubits |q0, |q1 are the state qubits, |i is the input qubit and |o is the output qubit (Figure 21). Table 22 represents the consecutive states as obtained during the QFSM procedure described in this work (Section 5.3). In particular this QFSM shows that it recognize the given sequence without the use of any probabilistic or superposed states.

This can also be seen on the circuit matrix that can easily be build from the given sequence of gates. For clarity the state transition is also shown in the form of a equation (eq. 39).

s00:|0000U|0000s11:|0000|0010U|1110s20:|1110|1100U|1010s31:|1010U|0010s41:|0010U|1110s51:|1110U|0110s61:|0110U|0101E40

Observe that two different steps can be clearly distinguished in eq. 39; first a standard step that acts directly on a previously generated machine state such as in steps s0, s3, s4, s5 and s6, second a step that requires explicit modification of the previous machine state, in particular a state that requires an initialization of the output and/or the input qubit, such as shown in steps s1 to s2. Observe that this particular sequence detector does not requires - for this sequence – any re-initialization of the input qubit as a result of previous step; the input qubit is not modified by the automaton. Also observe that despite the fact that this circuit can generate quantum states, these states are not generated during the sequence s7. This can be seen on Figure 23.

The states in a circle represent natural states as would be obtained by the cycle of the reversible function, while the states in the hexagons represents forced states that are obtained after modifying the input qubit. The Figure 23 also represents the forced states with one dotted arrow incoming and one outgoing dashed arrows. The arrow incoming to the forced state is indexed with a binary number representing the required input change so that the forced state is obtained. The outgoing arrow represents that the forced state is then used as a normal natural state; i.e. a Unitary transform is applied to it and the result is computed. For instance the s1 character recognition, starts with the machine in the state |0000, which is forced to |0010 and then the Unitary transformation is applied and yields |1110 state. The whole sequence detection can be in this manner analysed from eq. 39 and Figure 23.

A more interesting example is shown in Figure 24. The displayed circuit also recognizes the same sequence s7 but in this case the automaton uses probabilistic and superposed quantum states. This can be seen in Table 25; this table has every row split in half so that it fits in size. For more details eq. 40 shows step by step the process of recognition performed by this automaton. Observe that as the result of the last step the output of the circuit is |o = |1 thus confirming the correct sequence has been detected.

s00:|0000U|0000s11:|0000|0000U1+i2|0110+1i2|1000s20:1+i2|0110+1i2|10001i2|1000U1i2|1010s31:1i2|1010U1i2|0010s41:1i2|0010Ui2|0110+i2|1000s51:i2|0110+i2|1000|0110U|1100s61:|0110|1100U1i4|0011+1i4|0111+1i4|1001+12|1011+1+i4|1101+i2|1111E41

### 6.1. Sequence detection

The detection of a given sequence by the here formulated QFSM’s can be analyzed starting from Reversible Circuits. Assume, the initial state is 0000 for the rest of this discussion. As example take the reversible (deterministic) detector such as given in figure 21. It is obvious that the power of properly detecting a given sequence; i.e. to generate a sequence 0 × n + 1 × 1 is proportional to the cycle of this detector given by the reversible circuit for a fixed n and to the fact of having the cycle connected to a finish sequence either by a forced change of input or by a natural evolution.

To see this, just assume that the given circuit is specified by the following permutation cycle (0, 4, 8, 12)(2, 6, 10, 14)(1, 3, 5, 7, 9, 11, 13, 15). Clearly, the first cycle (0, 4, 8, 12) represents the states containing the 0 as input and 0 as output, the (2, 6, 10, 14) cycle represents the states having 1 for input and 0 as output and the last cycle represents all outputs having the output bit set to 1. The longest possible sequence this automaton can detect (without using the force states transitions) is of length 0 becausethe detecting cycle is disjoint from both the cycles identifying 0’s and 1’s.

For illustration assume the Reversible Circuit specifying the automaton be described by (0,6,4,2) (8,12,10,14,1) (3,5,7,9,11,13,15) permutation cycles. This automaton will not detect successfully any sequence if starting from the initial state 0000. This is shown in figure 26. Observe that no matter the input change of any of the state of the cycle (0,6,4,2) will always lead back to a state from the same cycle. Thus such a machine cannot generate a 1 on the output when starting in the state |0000.

The Figure 26 shows that in order to have a successful detector, at least one natural transition |ϕU|ϕ'or a forced transition |ρ|i|o|ρ|i|omust lead to a cycle that allows to generate an output with value 1.

Now consider an Reversible Circuit defined by the permutations given by (0, 4, 8, 12, 3) (2, 6, 10, 14, 1) (5, 7, 9, 11, 13, 15). Such automaton now can detect any sequence that contains at least four consecutive 0’s or four consecutive 1’s. To maximize the length of a given sequence it is possible to allow the automaton to modify also its input qubit. In that case, as also seen in the presented protocol in the Section 5.3, the maximal complexity of the detected sequence is still equal to the sequence of maximum four 0’s and four 1’s.

The important cycles used for detection of the above specified Reversible circuit are shown in Figure 28. Observe that only two out of three cycles are shown as the last cycle contains all minterms that have 1 as output and thus can only be used as the end of sequence indicator. Also the cycles are shown only up to a final state. Thus for instance the state |0011 is not connected back to |0000 because once such state is attained the detection is terminated. Such specified detector will detect any sequence that terminates with four 1’s or four 0’s.

Finally observe that for a given sequence it is possible to design a detector that is either specified by only natural state transitions - as specified by the cycles of a reversible quantum function or by combining the cycle with forced transitions. The former method will always generate larger circuits while the later will allow more compact designs. However in the framework of the presented Quantum detectors these approaches are equivalent from the point of view of implementation. That is, at the begining of each computation cycle one need to know exactly the input quantum state. Thus the main adavantage in designing detectors with only natural state transitions resides in the fact that no initialization of the input qubit is required because it is set at the output of the previous computational cycle.

To close this discussion about the detectors it is possible to synthesize detectors using both purely Reversible or Quantum Unitary matrix. The size of the required circuit is dependent on the amount of continuous 0’s or 1’s however it is not restricted by it. It is straight forward to imagine such sequence detector that will have only smaller cycles and still will detect similar sequence. This is because if the unitary transform modifies the input qubit, smaller cycles can be combined to detect these particular sequences. For instance Figure 29 shows a portion of a detector specified by a Reversible circuit. This detector will detect among others the sequences terminating with three 0's or two 1's. Recall that only natural transitions are used for the detection procedure. Thus for instance in figure 29 |1110 changes to state |1100 when the input is changed from 1 to 0 and the consequent application of the Unitary matrix on this state generates an 1 on output. This is the final state, and it indicates that at least three 0 have been successfully detected before attaining it. The interested reader is encouraged to read more about reversible and quantum sequence detector in [LP09, LPK09].

Table 5 shows the minimum number of qubits that have been experimentally obtained in order to properly detect the sequences studied here. The sequence s7 has a sequence of four 1’s and a set of individual 1 and thus cannot be detected by less than circuit with 4 qubits.

The sequence s10 has two cycles at least: one with a sequence of two 1’s followed by a 0 and a sequence of three 0’s. It is also not possible to construct such detector on 3 qubits because the number of states required is at least 4 for both sequence and not counting the individual 0’s and 1’s. Similarly other sequences can be analyzed.

The Genetic Algorithm was run for multiple sizes for each sequence starting with three qubits. The search was terminated when a circuit satisfying the constraints was found and multiple searches were performed at the minimal width. Figure 30 shows the average of the Fitness value for the s7, s10 and s15 sequences. The drawings show each curve over 500 generation cycles required for the detection of each of the sequences after which the maximum generation is attained. Each curve is an average of 15 runs and the most interesting feature is that similarly to quantum function logic synthesis the algorithm finds a circuit that is very close to the complete solution and then stagnates before finding a solution. This problem is related to both the difficulty of synthesis as well as the fact that Quantum circuit are specified by Unitary matrices in which the error is of symmetric nature. Such error can be seen as a step function where with each step a pair of coefficient in the Unitary matrix is corrected.

Also observe how the fitness value stagnates with larger sequences with the presented qubits despite the fact that a solution was found for each sequence for the presented number of qubits. Interestingly, observe that the sequence s7 to s20 are from the same class as they have been identified by detectors of similar size. This goes back to the discussion above about the limits of a Quantum and Reversible circuit to recognize a particular class of sequences.

## 7. Conclusion

In this paper we presented a methodology and we showed some experimental results confirming that our approach is possible in simulated environment. Also because all simulated elements of the presented experiments are based on existing Quantum operations, the simulated detectors are Quantum-realizable.

It is well known that the state assignment problem is a NP-complete problem [Esc93] and the finding a minimal State Assignment has been solved only for particular subsets of FSM’s [LPD95] or using Quantum computing [ANdMM08]. This problem is here naturally solved (without addressing it). The setup of this experimental approach automatically generates a state assignment such that when the detection is successful the state assignment is as well. This is a natural consequence of both the fact that the machine is reversible and the fact that the sequence is successfully identified.

The presented algorithm proved successful in the design of Quantum detectors. Despite the sequences were randomly generated the proposed approach was possible due to the hardware accelerated computational approach. For more details about this approach the reader can consult [LM09].

The synthesis of quantum detectors has not been completely explored and remains still an open issue mainly because Quantum computing implementation is not a well established approach. Each technology provides different possibilities and has different limitations. In some cases specification using Quantum circuits is the most appropriate in others Hamiltonians must be used. Thus one of the main remaining tasks is to completely describe Quantum detectors and formally define their issues related with implementation and define classes of circuits more approapriate for different technologies.

chapter PDF
Citations in RIS format
Citations in bibtex format

## How to cite and reference

### Cite this chapter Copy to clipboard

Martin Lukac and Marek Perkowski (February 1st 2010). Evolutionary Logic Synthesis of Quantum Finite State Machines for Sequence Detection, New Achievements in Evolutionary Computation, Peter Korosec, IntechOpen, DOI: 10.5772/8049. Available from:

### Related Content

#### New Achievements in Evolutionary Computation

Edited by Peter Korosec

Next chapter

#### Conflicting Multi-Objective Compatible Optimization Control

By Lihong Xu, Qingsong Hu, Haigen Hu and Erik Goodman

#### Particle Swarm Optimization

Edited by Alex Lazinica

First chapter

#### Novel Binary Particle Swarm Optimization

By Mojtaba Ahmadieh Khanesar, Hassan Tavakoli, Mohammad Teshnehlab and Mahdi Aliyari Shoorehdeli

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

View all Books