Synthesis of Ternary Grover´s Algorithm

Grover´s search algorithm is one of the well-studied quantum computing algorithms, which plays a key role in many applications such as graph coloring, triangle finding, Boolean satisfiability. Although there are many works on circuit synthesis for Grover´s algorithm in the binary quantum domain, only a few exist for the ternary version of the algorithm. In this paper, we first propose a new ternary superposition operator and utilize it to synthesize a ternary quantum logic circuit for Grover´s algorithm. Our proposed circuits for a ternary oracle and the ternary Grover´s diffusion operator require 4 and 6 gate levels respectively per iteration, and for the ternary oracle 1 ancilla qutrit. To the best of our knowledge, this is the first circuit for the Grover´s diffusion operator using ternary gates. Finally, we use these two circuits to present a ternary quantum circuit for the vertex coloring problem. The oracle circuit for this problem has smaller gate count compared to existing solutions.