Quantum oracles play key roles in the studies of quantum computation and quantum information. But implementing quantum oracles efficiently with universal quantum gates is a hard work. Motivated by genetic programming, this paper proposes a novel approach to evolve quantum oracles with a hybrid quantum-inspired evolutionary algorithm. The approach codes quantum circuits with numerical values and combines the cost and correctness of quantum circuits into the fitness function. To speed up the calculation of matrix multiplication in the evaluation of individuals, a fast algorithm of matrix multiplication with Kronecker product is also presented. The experiments show the validity and the effects of some parameters of the presented approach. And some characteristics of the novel approach are discussed too.
Quantum oracles play key roles in the studies of quantum computation and quantum information. But implementing quantum oracles efficiently with universal quantum gates is a hard work. Motivated by genetic programming, this paper proposes a novel approach to evolve quantum oracles with a hybrid quantum-inspired evolutionary algorithm. The approach codes quantum circuits with numerical values and combines the cost and correctness of quantum circuits into the fitness function. To speed up the calculation of matrix multiplication in the evaluation of individuals, a fast algorithm of matrix multiplication with Kronecker product is also presented. The experiments show the validity and the effects of some parameters of the presented approach. And some characteristics of the novel approach are discussed too.
This paper illustrates the application of a Hybrid Quantum Inspired Evolutionary Algorithm (HQIEA) in evolving a variety of Quantum equivalents of classical circuits. Taking the matrix corresponding to an oracle as input, this HIQEA designs classical circuits using quantum gates. A library consisting of single, two and three qubit Quantum gates and the desired circuit matrix were given as input and algorithm was able to successfully design half adder, full adder and binary-gray conversion circuits apart from circuits for two, three and four qubit Boolean functions, using Quantum gates. The circuits obtained compare favorably with earlier attempts in terms of number of gates, ancillary inputs and garbage outputs required for constructing these circuits and the time taken to evolve them.
Quantum computing is a new way of data processing based on the concept of quantum mechanics. Quantum circuit design is a process of converting a quantum gate to a series of basic gates and is divided into two general categories based on the decomposition and composition. In the second group, using evolutionary algorithms and especially genetic algorithms, multiplication of matrix gates was used to achieve the final characteristic of quantum circuit. Genetic programming is a subfield of evolutionary computing in which computer programs evolve to solve studied problems. In past research that has been done in the field of quantum circuits design, only one cost metrics (usually quantum cost) has been investigated. In this paper for the first time, a multi-objective approach has been provided to design quantum circuits using genetic programming that considers the depth and the cost of nearest neighbor metrics in addition to quantum cost metric. Another innovation of this article is the use of two-step fitness function and taking into account the equivalence of global phase in quantum gates. The results show that the proposed method is able to find a good answer in a short time.
We apply a hybrid evolutionary algorithm to minimize the depth of circuits in quantum computing. More specifically, we evaluate two different variants of the algorithm. In the first approach, we combine the evolutionary algorithm with an optimization subroutine to optimize the parameters of the rotation gates present in the quantum circuit. In the second, the algorithm solely relies on evolutionary operations (i.e., mutations and crossover). We approach the problem from two sides: (1) constructing circuits from the ground up by starting with random initializations and (2) initializing individuals with a target circuit in order to optimize it further according to the fitness function. We run experiments on random circuits with 4 and 6 qubits varying in circuit depth. Our results show that the proposed methods are able to significantly reduce the depth of circuits while still retaining a high fidelity to the target state.
Automatic quantum circuit design is motivated by the difficulties in manual design, because quantum algorithms are highly non-intuitive and practical quantum computer hardware is not yet available. Thus, quantum computers have to be simulated on classical hardware which naturally entails an exponential growth of computational costs and allows only to simulate small quantum systems, i. e., with only few qubits. Huge search spaces render evolutionary approaches nearly unable to achieve breakthrough solutions in the development of new quantum algorithms. Consequently, at present we must be content to evolve essentially already existing (black-box) quantum algorithms. This thesis presents empirical results on the evolution of quantum circuits using genetic programming. For that purpose, a linear and a linear-tree GP system (allowing intermediate measurements) with integrated quantum computer simulator were implemented. Their practicality in evolving quantum circuits is shown in different experiments for 1-SAT (solutions act like Hogg's algorithm) and the Deutsch-Jozsa problem. These experiments confirm that the evolution of quantum circuits is practically feasible only for sufficiently small problem instances. In this context, scalability and the detection of scalability becomes very important. It is shown that scalable quantum circuits are evolvable to a certain degree: a general quantum circuit can be inferred manually from the evolved solutions for small instances of the given problem. Besides, further experiments indicate that 're-evolution' is effective for the evolution of scalable quantum circuits. With this method the start population of a problem instance is inoculated with evolved solutions for a smaller problem instance. Furthermore, investigations of fitness landscapes and selection strategies are made, with the aim of improving the efficiency of evolutionary search. A notable result is that using the crossover operator damages rather than benefits evolution of quantum circuits.
The increasing interest, in the last two decades, of evolutionary computation community in the combination of quantum computing and evolutionary computing, has led to the definition of a novel class of quantum-inspired evolutionary algorithms which exploit the concepts of quantum bits and quantum gates with the aim of improving the efficiency of current optimization methods. In this paper, a new method which hybridizes differential evolution with quantum computing is proposed. The method consists of two phases. In the first phase, it performs a new quantum-inspired evolutionary method until it does not get stuck into a local optimum, then, in the second phase, it runs differential evolution by using as initial population that obtained at the end of the first phase. Experiments on classical benchmark functions show that the hybridization outperforms standard methods by sensibly improving the fitness value and speeding up the convergence process.
The goal of this work is to understand the application of the evolutionary programming approach to the problem of quantum circuit design. This problem is motivated by the following observations: In order to keep up with the seemingly insatiable demand for computing power our computing devices will continue to shrink, all the way down to the atomic scale, at which point they become quantum mechanical systems. In fact, this event, known as Moore?s Horizon, is likely to occur in less than 25 years. The recent discovery of several quantum algorithms which can solve some interesting problems more efficiently than any known classical algorithm. While we are not yet certain that quantum computers will ever be practical to build, there do now exist the first few astonishing experimental devices capable of briefly manipulating small quantities of quantum information. The programming of these devices is already a nontrivial problem, and as these devices and their algorithms become more complicated this problem will quickly become a significant challenge. The Evolutionary Programming (EP) approach to problem solving seeks to mimic the processes of evolutionary biology which have resulted in the awesome complexity of living systems, almost all of which are well beyond our current analysis and engineering capabilities. This approach is motivated by the highly successful application of Koza?s Genetic Programming (GP) approach to a variety of circuit design problems, and specifically the preliminary reports byWilliams and Gray and also Rubinstein who applied GP to quantum circuit design. Accompanying this work is software for evolutionary quantum circuit design which incorporates several advances over previous approaches, including: A formal language for describing parallel quantum circuits out of an arbitary elementary gate set, including gates with one or more parameters. A fitness assessment procedure that measures both average case fidelity with a respect for global phase equivalences, and implementation cost. A Memetic Programming (MP) based reproductive strategy that uses a combination of global genetic and local memetic searches to effectively search through diverse circuit topologies and optimize the parameterized gates they contain. Several benchmark experiments are performed on small problems which support the conclusion that Evolutionary Programming is a viable approach to quantum circuit design and that further experiments utilizing more computational resources and more problem insight can be expected to yield many new and interesting quantum circuits.