A new Pattern for Quantum Evolutionary Algorithms

Abstract

Quantum Evolutionary Algorithms have been discussed in the literature in different forms. One branch in these efforts studies approaches for the representation of genetic information, i.e., problem information, in terms of qubits. A typical downside of this representation has been the loss of quantum information in the evaluation and selection steps of the algorithm. I.e., algorithms are implemented in a hybrid-classical setup and require measurements in each iteration. This inevitably destroys superpositions and entanglement structures in the genome representation. In this work, we propose a new implementation approach for genetic information and the evaluation and selection phase, which realizes those steps within the quantum circuit. To achieve this, we utilize qudits for representing the evolving entities. Additionally, we make use of patterns for the design of quantum sub-circuits to compose control structures known from the classical realm. As a result, we show a quantum circuit design for anytime algorithms that does not have to be measured in every iteration and that does not depend on classical control. The overall progress of the evolutionary process only needs to be checked occasionally on a flag-qubit. The approach currently comes with some limitations e.g., in the objective function. It is presented here for the toy problem Leading Ones.