A quantum genetic algorithm with quantum crossover and mutation operations

被引:60
作者
SaiToh, Akira [1 ,4 ]
Rahimi, Robabeh [2 ]
Nakahara, Mikio [3 ,4 ]
机构
[1] Natl Inst Informat, Quantum Informat Sci Theory Grp, Chiyoda Ku, Tokyo 1018430, Japan
[2] Univ Waterloo, Inst Quantum Comp, Waterloo, ON N2L 3G1, Canada
[3] Kinki Univ, Dept Phys, Higashiosaka, Osaka 5778502, Japan
[4] Kinki Univ, Interdisciplinary Grad Sch Sci & Engn, Res Ctr Quantum Comp, Higashiosaka, Osaka 5778502, Japan
关键词
Genetic algorithm; Quantum computing; Computational complexity; CIRCUITS; BOUNDS; GATE;
D O I
10.1007/s11128-013-0686-6
中图分类号
O4 [物理学];
学科分类号
070305 [高分子化学与物理];
摘要
In the context of evolutionary quantum computing in the literal meaning, a quantum crossover operation has not been introduced so far. Here, we introduce a novel quantum genetic algorithm that has a quantum crossover procedure performing crossovers among all chromosomes in parallel for each generation. A complexity analysis shows that a quadratic speedup is achieved over its classical counterpart in the dominant factor of the run time to handle each generation.
引用
收藏
页码:737 / 755
页数:19
相关论文
共 55 条
[1]
[Anonymous], P GEN EV COMP C GECC
[2]
[Anonymous], P 8 INT C INFORMATIC
[3]
[Anonymous], ARXIVQUANTPH0610105
[4]
[Anonymous], P 2 QUANT INT S QI 2
[5]
[Anonymous], P 1999 C EV COMP CEC
[6]
[Anonymous], ARXIVCS0403003
[7]
[Anonymous], P 12 ANN GEN EV COMP
[8]
[Anonymous], DIT04105 U TRENT
[9]
[Anonymous], P 2010 2 INT C INT H
[10]
[Anonymous], ARXIVQUANTPH9911082