In this paper we present Quanrum Encoded Quantum Evolutionary Algorithm (QEQEA) and compare its performance against a a classical GPU accelerated Genetic Algorithm (GPUGA). The proposed QEQEA differs from existing quantum evolutionary algorithms in several points: Representation of candidates circuits is using qubits and qutrits and the proposed evolutionary operators can theoretically be implemented on quantum computer provided a classical control exists. The synthesized circuits are obtained by a set of measurements performed on the encoding units of quantum representation. Both algorithms are accelerated using (general purpose graphic processing unit) GPGPU. The main target of this paper is not to propose a completely novel quantum genetic algorithm but to rather experimentally estimate the advantages of certain components of genetic algorithm being encoded and implemented in a quantum compatible manner. The algorithms are compared and evaluated on several reversible and quantum circuits. The results demonstrate that on one hand the quantum encoding and quantum implementation compatible implementation provides certain disadvantages with respect to the classical evolutionary computation. On the other hand, encoding certain components in a quantum compatible manner could in theory allow to accelerate the search by providing small overhead when built in quantum computer. Therefore acceleration would in turn counter weight the implementation limitations.