Quantum Genetic Algorithm
We all wonder how life came into existence and why we are here?
Starting life on earth have a list of popular theories, but the most popular theory says: Life on earth happened by chance, about 3.5–4.5 billion years ago, when a complex molecule(DNA) came into existence by chance and can create duplicates(child molecules).
The evolutionary path taken by these early molecules is responsible for creating all the life forms on earth.
In this article, we will discuss one of the theories that will help us understand evolution with the help of quantum specs.
Basics:
DNA(Deoxyribonucleic acid) is the molecule responsible for life on earth; the DNA strand consists of a chain of nucleotides.
Each nucleotide is composed of one of four bases (cytosine [C], guanine [G], adenine [A], or thymine [T]), a sugar called deoxyribose, and a phosphate group.
A,T, G, and C bases and according to base-pairing rules
- A makes hydrogen bonds with T
- C makes hydrogen bonds with G
Double-stranded DNA is the result of base-pairing rules. Both strands of double-stranded DNA store the same biological information. Segments of DNA that contains the information to create a protein are known as Gene.
DNA is organized into long structures called a chromosome.
Darwin's theory of evolution:
Darwin gave the theory of natural selection. According to the theory of Natural selection, individuals with traits that enable them to adapt to their environments will help them survive and have more offspring, which will inherit those traits. Individuals with less adaptive traits will less frequently survive to pass them on. Over time, the traits that enable species to survive and reproduce will become more frequent in the population, and the population will change or evolve, according to BioMed Central. Through natural selection, Darwin suggested, genetically diverse species could arise from a common ancestor.
QUANTUM GENETIC ALGORITHM:
Step 1 — Creating a Quantum population Q(t =0).
A quantum population is a set of chromosomes (a Chromosome is a long structure of DNA that represents an organism.)
A chromosome(ψ) is a collection of genes,
Here is the gene representation for QGA.
We have discussed that the collection of genes forms a chromosome/individual. So, representation for a chromosome will be,
A set of chromosomes are known as a population. We apply a Hadamard gate on state |0> qubit to initialize the probability. This results in a superposition state we equal probability for both |0> and |1> state.
Then we pass it through a phase gate U(θ), where θ is a random angle between [0-π/2]. In the end, Initialization will be described as equations given below.
Now we have a quantum population from which we can easily generate a classical population by observing the qubits/genes from each individual/chromosome.
After observation, we get a string of 0’s and 1’s as given below, which is represented by x(classical population).
NOTE: “After observation, we have lost the superposition states so to avoid classical population constructed according to the probability amplitudes of individual genes.”
From a theoretical point of view, the evolution of the population is governed by Schrödinger’s equation, so there will be a unitary operator U(t) that plays the role of the “genetic mechanisms” transforming chromosomes since evolution takes place in a complex vector space.
Operator U(t) will be describing the evolution of quantum generation as follows:
for each time frame t, we create classical population P(t) from Q(t) by observing qubit states.
The process described above will be repeated until we hit the termination condition(that is to produce an optimal population/solution for a given environment/problem).
NOTE: “After observation, we have lost the superposition states. which means it is difficult to perform QGA on Quantum computers. there is another algorithm, Reduced Quantum Genetic Algorithm(RQGA) which can be performed on quantum computers.
Reduced Quantum Genetic Algorithms(RQGA):
RQGA is a true quantum evolutionary algorithm
step 1 we have seen in QGA,
In step 2 we are creating a quantum fitness operator F.
Fitness operator uses an Oracle O,
such that,
because the oracle will mark the desired state, With Grover’s search.
Let’s understand with an example.
Suppose we are solving an optimization problem given as
The f(x) function has an optimum reached with x = 11, thus 1011 in the binary.
To solve this problem, we are using four qubits. So,
Step 1 will be to create an Initial population with a superposition
Now F and O will mark the desired state. As an operator, it looks like,
After marking the 11th qubit, the population will become,
which graphically looks similar to
Now, if we follow the step of inversion of Grover’s search algorithm which inverts the above amplitude around the mean(represented by dotted line).
After inversion, the amplitude will look similar to the picture given below,
This process increases the probability of getting a marked state and reduces getting undesired states.
if we repeat the marking of the desired state and take inversion around the mean for Grover’s maximum number of iterations i.e.
where n is the number of qubits, we will get the final population as
after measurement, we find state |11> with probability 0.95,
The algorithm RQGA demonstrates that using quantum computing, the genetic search strategy becomes unnecessary; evolution takes place in a single generation.
If you want to learn more about the implementation part, check out my GitHub repository.
Till then, stay safe, stay curious :)
