A quantum-theoretic approach to genetic problems

Naeem Ullah

Giovanni Acampora, Giulio Minolfi, Roberto Schiattarella

Quantum Genetic Algorithms (QGAs) are emerging as a new class of algorithms that exploit the peculiarities of quantum computers to outperform classical evolutionary approaches in solving complex optimization problems. Despite the theoretical promises, their applicability has been strongly affected by the limitation of current noise-prone quantum hardware. It has only recently been demonstrated that acceptable levels of quantum noise can enhance the exploration capability of QGA in constrained optimization problems. The research corroborates the initial findings, providing further evidence of the efficacy of these algorithms by successfully resolving the NP-hard Ising Problem through the utilization of a QGA equipped with a quantum mating operator. The experimental results show that noisy simulations of QGA are capable of identifying better solutions than genetic algorithms that are equipped with state-of-the-art classical mating operators.

Robert Rosén

Nicolas P. Rashevsky

Quantum computers are computational devices that use the dynamics of atomic-scale objects to store and manipulate information.Only a few, small-scale quantum computers have been built to date, but quantum computers can in principle outperform all possible classical computers in significant ways.Quantum computation is therefore a subject of considerable theoretical interest that may also have practical applications in the future.Genetic programming can automatically discover new algorithms for quantum computers [Spector et al., 1998].We describe how to simulate a quantum computer so that the fitness of a quantum algorithm can be determined on classical hardware.We then describe ways in which three different genetic programming approaches can drive the simulator to evolve new quantum algorithms.The approaches are standard tree-based genetic programming, stack-based linear genome genetic programming, and stackless linear genome genetic programming.We demonstrate the techniques on four different problems: the two-bit early promise problem, the scaling majority-on problem, the four-item database search problem, and the two-bit and-or problem.For three of these problems (all but majority-on) the automatically discovered algorithms are more efficient than any possible classical algorithms for the same problems.One of the better-than-classical algorithms (for the two-bit and-or problem) is in fact more efficient than any previously known quantum algorithm for the same problem, suggesting that genetic programming may be a valuable tool in the future study of quantum programming.

Apoorva Patel