Name
Abstract | ||
|---|---|---|
In this article, we formulate for the first time the notion of a quantum evolutionary algorithm. In fact we define a quantum analogue for any elitist (1+1) randomized search heuristic. The quantum evolutionary algorithm, which we call (1+1) quantum evolutionary algorithm (QEA), is the quantum version of the classical (1+1) evolutionary algorithm (EA), and runs only on a quantum computer. It uses Grover search [13] to accelerate the search for improved offsprings. To understand the speedup of the (1+1) QEA over the (1+1) EA, we study the three well known pseudo-Boolean optimization problems OneMax, LeadingOnes, and Discrepancy. We show that although there is a speedup in the case of OneMax and LeadingOnes in the quantum setting, the speedup is less than quadratic. For Discrepancy, we show that the speedup is at best constant. The reason for this inconsistency is due to the difference in the probability of making a successful mutation. On the one hand, if the probability of making a successful mutation is large then quantum acceleration does not help much. On the other hand, if the probabilities of making a successful mutation is small then quantum enhancement indeed helps. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1145/1830483.1830746 | GECCO |
Keywords | Field | DocType |
quantum evolutionary algorithm,successful mutation,quantum computer,quantum analogue,quantum enhancement,quantum version,quantum setting,evolutionary algorithm,quantum acceleration,grover search,random search,theory,timing analysis,quantum algorithm | Quantum phase estimation algorithm,Evolutionary algorithm,Computer science,Quantum computer,Theoretical computer science,Quantum algorithm,Artificial intelligence,Speedup,Quantum,Mathematical optimization,Algorithm,Quantum sort,Quantum algorithm for linear systems of equations,Machine learning | Conference |
Citations | PageRank | References |
5 | 0.41 | 19 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Daniel Johannsen | 1 | 211 | 13.73 |
| Piyush P. Kurur | 2 | 88 | 9.41 |
| Johannes Lengler | 3 | 70 | 14.94 |