Improved Complexity of Quantum Oracles for Ternary Grover Algorithm for Graph Coloring

The paper presents a generalization of the well-known Grover Algorithm to operate on ternary quantum circuits. We compare complexity of oracles and some of their commonly used components for binary and ternary cases and various sizes and densities of colored graphs. We show that ternary encoding leads to quantum circuits that have significantly less qud its and lower quantum costs. In case of serial realization of quantum computers, our ternary algorithms and circuits are also faster.