Evolving blackbox quantum algorithms using genetic programming

Although it is known that quantum computers can solve certain computational problems exponentially faster than classical computers, only a small number of quantum algorithms have been developed so far. Designing such algorithms is complicated by the rather nonintuitive character of quantum physics. In this paper we present a genetic programming system that uses some new techniques to develop and improve quantum algorithms. We have used this system to develop two formerly unknown quantum algorithms. We also address a potential deficiency of the quantum decision tree model used to prove lower bounds on the query complexity of the parity problem.