New Classes of Quantum Algorithms

Richard J. Lipton, Kenneth W. Regan, Atri Rudra B

We identify a sub-class of BQP that captures certain structural commonalities among many quantum algorithms including Shor's algorithms. This class does not contain all of BQP (e.g. Grover's algorithm does not fall into this class). Our main result is that any algorithm in this class that measures at most O(log n) qubits can be simulated by classical randomized polynomial time algorithms. This does not dequantize Shor's algorithm (as the latter measures n qubits) but our work also highlights a new potentially hard function for cryptographic applications. Our main technical contribution is (to the best of our knowledge) a new exact characterization of certain sums of Fourier-type coefficients (with exponentially many summands).

Andris Ambainis

Diederik Aerts

Shukhrat Toirov, Ulugbek Narmuradov

This article describes optimization processes of functions and their solutions using quantum genetic algorithms. These are continuous heuristic optimization methods based on simulated genetic mechanisms, i.e., on dynamic processes in a population such as mutation, crossover, selection, and so on. This process leads to the emergence of a new class called quantum genetic algorithms. In this article, we have presented a discussion of new classes of quantum genetic algorithms, future capabilities, and benefits.

Peter W. Shor

Rafael Lahoz-Beltrá

Genetic algorithms (GAs) are a class of evolutionary algorithms inspired by Darwinian natural selection. They are popular heuristic optimisation methods based on simulated genetic mechanisms, i.e., mutation, crossover, etc. and population dynamical processes such as reproduction, selection, etc. Over the last decade, the possibility to emulate a quantum computer (a computer using quantum-mechanical phenomena to perform operations on data) has led to a new class of GAs known as “Quantum Genetic Algorithms” (QGAs). In this review, we present a discussion, future potential, pros and cons of this new class of GAs. The review will be oriented towards computer scientists interested in QGAs “avoiding” the possible difficulties of quantum-mechanical phenomena.