Share Pdf : Quantum Genetic Algorithms For Computer Scientists

Download and Preview : Quantum Genetic Algorithms For Computer Scientists

Report CopyRight/DMCA Form For : Quantum Genetic Algorithms For Computer Scientists

## Transcription

Computers 2016 5 24 2 of 31, in fields either economics biology chemistry and many others However from a theoretical point. of view is it possible to simulate Darwinian evolution in a quantum computer In 1987 Calvin 5. coined the term Darwin machine to refer to a machine analogous to a Turing machine which. returns as output the result of an iterative process similar to a GA From a theoretical point of view the. architecture of a conventional computer is adequate to implement GAs and also to simulate from a. Darwinian perspective the most important aspects of biological evolution Consequently whereas a. digital computer can successfully simulate a Darwin machine the possibility to simulate a Darwin. quantum machine in a quantum computer remains today a controversial question However what is. known as Quantum Darwinism 6 will open up the possibility Therefore the Darwin s concept of. survival of the fittest could be simulated in any device capable of data manipulation based on quantum. mechanical phenomena 7 In any case and without going into theoretical issues since 1956 8 when. was first proposed the genetic algorithms Evolutionary Computation has made great progress In 2002. Han 9 introduced a novel evolutionary algorithm inspired by quantum computing growing from this. date the number of publications on quantum inspired genetic algorithms In 2010 Ying 10 proposed. that quantum computing could be used to achieve certain goals in Artificial Intelligence AI Over the. last decade the possibility to emulate a quantum computer has led to a new class of GAs known as. Quantum Genetic Algorithms In this review we present a discussion future potential pros and. cons of this new class of GAs including some material presented in a lecture delivered at 11. Table 1 Main steps of a simple genetic algorithm SGA. 1 Randomly initialize a population P 0, 2 Evaluate P 0. 3 while not termination condition do, 6 Selection of parents from population P t. 7 Crossover, 8 Mutation, 9 Evaluate P t, 2 What is Quantum Computing. One of the most striking ideas of quantum computing is that as long as a digital computer is a. symbolic machine i e an instruction execution engine a quantum computer is a physical machine. This means that in a quantum computer the hardware software duality is less obvious than in a classical. computer being the quantum circuit hardware itself an isolated quantum system Therefore while. in a digital computer a computation is given by the logical operations performed in a symbolic. system in a quantum computer a computation is the evolution experienced by the quantum system. According to quantum mechanics the evolution of an isolated quantum system from an initial. state to another final state e g a quantum computer is governed by the Schr dinger equation. i t i H t t i, where i is the imaginary number 1 and is a constant term named reduced Planck constant.

Planck s constant plays the role of relating the energy in a photon to frequency and since frequency is. measured in cycles per second it is more convenient to use h 2 According to the mathematical. expression the Schr dinger equation is a partial differential equation which physical variable is a. state vector t i written in a somewhat special notation that we will discuss later The t i vector. depends on time and describes the state of a quantum system at time t in this case the quantum. Computers 2016 5 24 3 of 31, computational state Since we are dealing with a differential equation the equation also includes a rate. of change or differential term i e t t i The Schr dinger equation is the holy grail of quantum. computing because it characterizes the evolution of a computing state through time The term H t is. known as Hamiltonian operator and somehow given the initial state 0 i it represents the sequence. of operations performed by a quantum computer Establishing a parallelism between quantum and. digital computers we assume that quantum state 0 i resembles the input of a digital computer. An interesting point is that if we know the Hamiltonian then the Schr dinger equation can be solved. so without going into details we will denominate U t as the solution of this equation Hence given an. initial state 0 i the solution of the Schr dinger equation at time t is given by the following linear. mapping in the state space, t i U t 0 i, Therefore and according with the above reasoning we can conclude that in a quantum computer. the output is the result of the i evolution of the Schrodinger equation and subsequent ii measurement. the meaning of measurement in quantum mechanics is introduced later As may be seen the equation. uses for the state vector a notation that is rather unusual The reason is because quantum mechanics. has its own customized notation for classical vector and matrix operations 12 In 1930 the theoretical. physicist Paul Dirac published the book The Principles of Quantum Mechanics introducing the ket. notation to refer to a column vector, and bra notation to denote a row vector. hW w1 w2 wi, Hence the product of a bra and a ket vectors which is written in the notation of Dirac as follows. is the ordinary inner product, hW V i w1 w2 wi w1 v1 w2 v2 wi vi.

Alternatively the product of a ket and bra vectors is the outer product of the two vectors. v 1 w1 v 1 w2 v1 wi, 2 1 v 2 w2 v2 wi, V i hW w1 w2 wi. vi v i w1 v i w2 v i wi, In quantum computing the elements of vectors and matrices are complex numbers but in practice. we can ignore this detail, Computers 2016 5 24 4 of 31. 2 1 Quantum Information, The unit of information in a quantum computer is the quantum bit or qubit storing 0i and 1i. states as well as a linear combination of both states superposition principle This linear combination. represents a qubit in its coherent state or quantum superposition i e i 0i 1i where. and are the qubit amplitudes of the states 0i and 1i Amplitudes are complex numbers C so. the exact state of a qubit is specified by two complex numbers describing the particular combination of. 0 and 1 in the superposition state The normalization of the states to the unit ensures that 2 2 1. and therefore 2 2 are the probabilities of finding the qubit in 0i or 1i states According to Dirac. notation such superposition is represented in vector form as follows. and therefore we will represent 0i and 1i states of a qubit. In the realm of quantum mechanics the states of a qubit are represented geometrically in what is. called as Bloch sphere From a mathematical point of view the state vector i representing the state of. a qubit is defined in a space referred as Hilbert space In a very general sense and without going into. details a Hilbert space is a complex vector space with the advantage that allows us to treat a function. i as a vector conducting mathematical operations by the simple application of standard algebraic. methods In consequence the quantum computing state which evolution is ruled by Schr dinger. equation is defined by a Hilbert space associated with a finite number of n qubits Despite all these. abstract concepts finally the definition of a universal quantum computer is close to the conceptual. framework of classical computation 13, One of the most amazing ideas of quantum mechanics is that any attempt to measure a quantum.

superposition or equivalently any interaction of the quantum system with the environment causes. the destruction of the superposition interference principle This is a natural phenomenon known in. quantum physics as collapse of wave function i and represents a major challenge in building a. quantum computer Consequently a measurement or observation of the qubit in its coherent state. results in a lost of the superposition transforming the qubit in a classic decoherent bit i e 0 or 1 state. The interference principle has recently been simulated based on a new class of hybrid cellular. automata 14 performing as either a quantum cellular automata QCA or as a classical von Neumann. automata CA, In a quantum computer the input is stored in a quantum memory register. i i1 i2 i n, The register state is the result of Kronecker or tensor product among two or more qubits. operation that is represented with the symbol as, x0 y0 x0 y1. x1 y1 x1 y0, Computers 2016 5 24 5 of 31, For instance number 5 is represented in binary numbering system as 101i being the register state. 5i i1 i2 i3 1i 0i 1i, However there are quantum states which cannot be written as a tensor product of two states.

being known these special states as entangled states entanglement principle In this case measurement. results are dependent as it will occur at the following quantum state. 0i A 0i B 1i A 1i B 00i 11i, Once the information is processed by a quantum circuit the output is the result of a measurement. or observation of the qubits states resulting the collapse of wave function i Computation concludes. once such measures have been made In summary in terms of computing a quantum algorithm. maps an input state 0 i or represented for simplicity as i0 onto the output or final state t i. represented as i F, where U or U t the solution of the Schr dinger equation is referred to as unitary evolution. operator An important issue is that U operator can be decomposed in a sequence of q elementary. quantum gates abbreviated as Q gates defining these gates a quantum circuit Q gates perform. unitary transformations on qubits bearing in their function a resemblance with classical Boolean gates. Consequently from left to right, U Uq Uq 1 U1, A quantum circuit thus the U decomposition represents a quantum algorithm being somehow. equivalent to a classical algorithm in a digital computer However quantum circuits show special. features allowing to a quantum computer conduct computations with a lower number of exponential. operations than classical computers, 2 2 Quantum Gates. Quantum gates Q gates operate on qubits undergoing unitary transformations being such. operations represented by matrices Since these unitary transformations are rotations in the Bloch. sphere then Q gates are reversible gates The most important quantum gates that operate with a single. qubit are the identity gate I and Pauli gates X Y and Z. 1 0 0 1 0 i 1 0, 0 1 1 0 i 0 0 1, The identity gate I leaves a qubit unchanged Pauli X gate performs a Boolean NOT operation.

Pauli Y gate maps 0i i 1i or 1i i 0i and Pauli Z gate changes the phase of a qubit thus. 0i 0i 1i 1i For instance let s consider the following operations between one of the above. quantum gates and 0i or 1i qubit states, 1 0 1 1 0 1 1 0 1 0 0 0. I 0i X 0i Z 1i, 0 1 0 0 1 0 0 1 0 1 1 1, Computers 2016 5 24 6 of 31. One of the most useful Q gates is the Hadamard or H gate This gate is a generalization of the. discrete Fourier transform which can be defined recursively for two three or more qubits. Let s be i a superposition vector, multiplying the matrix H by the above vector we obtain. For example if we multiply H by 0i we obtain, 1 1 1 1 1 1. 2 1 1 0 2 1, or using a different notation 0i 12 1i Figure 1 Therefore if we measure or observe the qubit.

state then we will have exactly 50 chance of seeing as 0 or 1 Similarly if now we multiply H by 1i. 1 1 1 0 1 1, 2 1 1 1 2 1, or in the alternative notation 1 0i 1 1i Figure 1. Computers 2016 5 24 2 2 7 of 31, Figure 1 Qubit, Qubit transformations with Hadamard. transformations with Hadamard gate, Of course there are also Q gates for two or more qubits operations e g SWAP CNOT Toffoli. One of the applications of Hadamard gate is the initialization of a quantum register Generalizing. Fredkin gates etc The SWAP gate swaps two qubits, the H gate multiplication by 0i to an n qubit register that stores the value 0n i results in a superposition. or mixed state 1n 0 0 0, 1 20 10 1 0, SWAP 2 n x i.

x0 0 1 0 0, Other Q gates exhibit the special feature of including one or more qubits controlling the. operation These gates are called U controlled gates e g CNOT Toffoli and Fredkin gates For. instance the CNOT gate 2 qubits performs according to truth table Table 2 the operation. CNOT Q1 Q2 Q1 Q 2 Q1 Figure 2a Note that, Q2 Q2 Q1 value is observed after. Computers 2016 5 24 7 of 31, Computers 2016 5 24 7 of 31. It is interesting to note that in the case we could observe the quantum register in the above mixed. state then we would see each of the 2n binary numbers x with equal probability. Of course there are also Q gates for two or more qubits operations e g SWAP CNOT Toffoli. Fredkin gates etc The SWAP gate swaps two qubits, Figure 1 Qubit transformations with Hadamard gate. Other Q gates exhibit the special feature of including one or more qubits controlling the. operation These, Of course theregates are Q gates, are also U controlled.

called for two or more gates, qubits e g CNOT, operations Toffoli. SWAP Fredkin, CNOT gates, For instance the CNOT gate 2 qubits performs. Fredkin gates etc The SWAP gate swaps two qubits according to truth table Table 2 the operation. CNOT Q1 Q2i Q1 Q2 Q1i Figure 2a Note that Q2 Q2 Q1 value is observed after. performing the measurement 1 0 0 0, Q1 Q2 Q1 Q2, Other Q gates exhibit the special. 0 of including, 0 or more qubits controlling the, operation These gates are called U controlled. 0 1 gates e g, 1 Toffoli and Fredkin gates For, instance the CNOT gate 2 qubits performs according to truth 1 table Table 2 the operation.

Quantum Genetic Algorithms for Computer Scientists Rafael Lahoz Beltra Department of Applied Mathematics Biomathematics Faculty of Biological Sciences Complutense University of Madrid Madrid 28040 Spain lahozraf ucm es Tel 34 91 394 5243 Academic Editor Prakash Panangaden Received 7 July 2016 Accepted 11 October 2016 Published 15 October 2016 Abstract Genetic algorithms GAs