30-10-2009, 03:37 PM
[attachment=339]
Grover's Algorithm A Fast Search Method Using Quantum Parallelism
Genetic Algorithms provide an effective way of searching complex fitness landscapes. Grover’s Algorithm is a quantum algorithm used to search through a database of values and determine where a particular target value is stored. It does so by using quantum parallelism so that it is more efficient than its classical counter- parts. The way the algorithm was originally designed allows for finding only a single value. We use repeated applications of Grover’s Algorithm to get a variety of decent chromosomes that will then be used to form a starting population for classical genetic search.
Basic ideas:
1. Initialize a quantum computer using l qubits, where l is the necessary length of the chromosomes.
2. Set the quantum computer to a superposition of all possible chromosomes. This represents a population of all possible solutions.
3. Decide on the size, n, of the seed population needed. This is based upon the complexity of the problem and the available computing resources.
4. Perform Grover’s Algorithm n times using the fitness function f to guide the search. Each solution found will be a single chromosome of the final seed population. The quantum registers are re-initialized in between each run.
5. Use the n solutions from above as an initial seed population for classical genetic search. This seed population will be fitter than a randomly generated population, as is commonly used as a starting population.