Quantum Computing

"The full range of physically computable functions is now within the scope of GP, which is beginning to find interesting new programs that humans had not previously discovered."[1]

In theory certain computational problems can be solved on a quantum computer with a lower complexity than possible on classical computers. Therefore, in view of its potential, design of new quantum algorithms is desirable, although up to now no working quantum computer is built. Unfortunately, the development of quantum algorithms seems to be difficult, as they are non-intuitional.

This project is motivated by papers of Lee Spector et al. [2,3] treating the evolution of quantum algorithms using genetic programming (GP). It was shown, that GP is capable of rediscovering already known quantum algorithms, like Grover's, and - which is even more interesting - evolving new better-than-classical quantum algorithms.

Within the framework of the quantum computation project at the Chair of Systems Analysis a GP system for the evolution of quantum algorithms was developed. Already simple algorithms with a few qubits could be evolved. Considering the evolutionary way of problem solving, the task remains, to search for computational problems, meeting especially two requirements:
- the problem may be solved efficiently on quantum computers, and
- it seems promising to use GP to evolve a quantum algorithm solving this problem.

Due to the exponential search space of quantum computations the immanent risk exists of getting "lost in space". Therefore, it is necessary to analyze the evolutionary dynamics of GP related to quantum computations.

Another important aspect is the scalability of algorithms. The simulation of quantum algorithms on a classical computer is calculationally expensive for a very few qubits already. Thus, the analysis of the algorithmic structure has to show, whether the algorithms can be extended on an arbitrary number of input qubits.

[1] Spector, L. 2000. The Evolution of Arbitrary Computational Processes. In IEEE Intelligent Systems, May/June 2000, pp. 80-83.
[2] Spector, L., H. Barnum, and H.J. Bernstein. 1999. Quantum Computing Applications of Genetic Programming. In Advances in Genetic Programming, Volume 3, edited by L. Spector, U.-M. O'Reilly, W. Langdon, and P. Angeline, pp. 135-160. Cambridge, MA: MIT Press.
[3] Barnum, H., H.J. Bernstein, and L. Spector. 2000. Quantum circuits for OR and AND of ORs. Journal of Physics A: Mathematical and General, Vol. 33 No. 45 (17 November 2000), pp. 8047-8057.