Circuit Design for $k$-coloring Problem and Its Implementation in Any Dimensional Quantum System

With the evolution of quantum computing, researchers now-a-days tend to incline to find solutions to NP-complete problems by using quantum algorithms in order to gain asymptotic advantage. In this paper, we solve $k$-coloring problem (NP-complete problem) using Grover's algorithm in any dimensional quantum system or any $d$-ary quantum system for the first time to the best of our knowledge, where $d \ge 2$. A newly proposed comparator-based approach helps to generalize the implementation of the $k$-coloring problem in any dimensional quantum system. Till date, $k$-coloring problem has been implemented only in binary and ternary quantum system, hence, we abide to $d=2$ or $d=3$, that is for binary and ternary quantum system for comparing our proposed work with the state-of-the-art techniques. This proposed approach makes the reduction of the qubit cost possible, compared to the state-of-the-art binary quantum systems. Further, with the help of newly proposed ternary comparator, a substantial reduction in quantum gate count for the ternary oracle circuit of the $k$-coloring problem than the previous approaches has been obtained. An end-to-end automated framework has been put forward for implementing the $k$-coloring problem for any undirected and unweighted graph on any available Near-term quantum devices or Noisy Intermediate-Scale Quantum (NISQ) devices or multi-valued quantum simulator, which helps in generalizing our approach.


Introduction
Modern day researchers has shown a startling interest for implementing quantum algorithms [1][2][3], which give a potential speedup over many of their classical counterparts as the advancement of quantum computer has achieved a phenomenal success in recent years [4]. There is an immense urge for the implementation of NP-complete problems on quantum computers with the thriving quantum wave [5]. According to the seminal work on computational complexity by Karp [6], if a solution to any of the NP-complete problems can be obtained then any other NP-complete problem can be polynomially reducible to that problem. In this paper, we have focused on one of the well-known NP-complete problems i.e., k-coloring problem. Our main focus is to provide an end-to-end framework that automatically implements an NP-complete problem i.e., k-coloring problem in any dimensional quantum system, so that if anyone can map their computational problem to the k-coloring problem in polynomial time, will be able to implement further, without prior knowledge of gate-based quantum circuit implementation.
An automatic circuit synthesis for k-coloring problem with the help of Grover's algorithm [7] is presented in the context of multi-valued quantum system in this paper. We graduate to multi-valued quantum system or qudits [8], which in the course reduce the circuit complexity and commend the efficiency of quantum algorithms [9] to provide larger state space with simultaneous multiple control operations [10][11][12]. For instance, N qubits can be formulated as N log2d qudits, which immediately gives log 2 d-factor in run-time [13][14][15]. The multi-valued quantum system can be realized on mostly available quantum technologies, as for example, ion trap [16], continuous spin systems [17,18], topological quantum systems [19,20], nuclear magnetic resonance [21], photonic systems [22], superconducting transmon technology [23] and molecular magnets [24].
k-coloring problem is an NP-complete problem that assigns colors to every nodes or vertices of a given graph with the available k colors in such a way that every adjacent vertices connected by an edge having distinct colors. Suppose n is the number of nodes of a given graph, k is the number of colors, then to find an appropriate solution using a classical algorithm requires O(2 n * log d k ) number of steps in d-dimensional system [25,26]. On the other hand, by using oracle and the diffusion operator of multivalued Grover's algorithm [27,28], finding the exact solution needs O √ N number of iterations where N is 2 n * log d k .
Many researchers have already addressed graph coloring problem for binary and ternary quantum system. Earlier in [25,29], graph coloring problem with the help of Grover's algorithm is talked about with respect to the binary quantum systems. Again, in [30], SAT reduction technique, the state-of-the-art approach, is used for solving 3coloring problem and it gives an end-to-end framework for the implementation of it in the IBMQ quantum processor [31]. But, SAT reduction technique generates an immense qubit cost, resulting in inefficient circuit cost. Previously in [32] and [26], circuit synthesis for graph coloring problem using Grover's algorithm has been presented with respect to ternary quantum system with the help of ternary comparators, which have been proposed in [33]. Albeit, in these works, the gate cost remains colossal.
In [34], we proposed a comparator-based approach for implementing the k-coloring problem in binary quantum structure, which has less qubit cost as compared to the state-of-the-art. In this paper, we have generalized the comparator for d-ary quantum system, which helps to overcome the engineering challenge of the implementation of k-coloring problem in d-ary quantum system. We have proposed an automated end-to-end framework for any dimensional quantum system to implement k-coloring problem using newly proposed generalized comparator to map the high level description of proposed circuit to any hardware-level quantum operations with an abstraction with better quantum cost in terms of quantum gate cost relative to the state-of-the-art works. In addition to this, we have claimed the following, for further establishing the novelty of the propose research work: -We propose an automated end-to-end framework for k-coloring problem using quantum search algorithm in any dimensional quantum system for the first time, to the best of our knowledge. -The design of the proposed framework is such that, the quantum solution of kcoloring problem can be mapped into any available near-term quantum devices/multivalued quantum technology, which makes our approach generalized in nature. -We show that our newly proposed comparator helps to implement k-coloring problem with reduced quantum cost with respect to qubits and quantum gates as compared to state-of-the art approaches in binary and ternary quantum domain. -A generalized comparator for d-ary system is elaborated in this paper, which is a first of its kind approach.
The paper is structured as follows. In section 2, the brief description of Grover's algorithm and quantum circuits are described. The proposed methodology is vividly explained in section 3. In section 4, implementation of k-coloring problem has been shown. Concluding remarks are captured in Section 5.

Background
In this section, we have explicitly described quantum circuit and Grover's algorithm.

Quantum circuit
Any quantum algorithm can be expressed or visualized in the form of a quantum circuit. Logical qubits/qudits and quantum gates comprise these quantum circuits [35]. The number of gates present in a circuit is called gate count and the number of qubits/qudits present in a circuit known as qubit/qudit cost.

Qubits/Qudits
Logical qubit/qudit that encodes input/output of a quantum algorithm is referred to as data qubit or qudit. Ancilla qubit/qudit are another type of qubit/qudit used to store temporary results. In d-dimensional quantum system qudit is the unit of quantum information. Qudit states can be manifested as a vector in the d dimensional Hilbert space H d . The span of orthonormal basis vectors {|0 , |1 , |2 , . . . |d − 1 } is the vector space. In qudit system, the general form of quantum state can be expressed as where

Generalized Quantum Gates
In this section, an outline of generalized qudit gates is conferred. The generalisation can be delineated as discrete quantum states of any arity. In a quantum algorithm, for modification of the quamtum state, unitary qudit gates are applied. For logic synthesis of Grover's algorithm in d-dimensional quantum system, it is necessary to take into account one-qudit generalized gates viz. NOT gate (X d ), phase-shift gate (Z d ), Hadamard gate (F d ), two-qudit generalized CNOT gate (C X,d ) and Generalized multi-controlled Toffoli gate (C n X,d ). These gates are expressed in detail for better understanding: Generalized NOT Gate: X d , the generalized NOT or increment gate, for a (d × d) matrix is as follows: Generalized Hadamard Gate: F d , the generalized quantum Fourier transform or generalized Hadamard gate, produces the superposition of the input basis states. The (d × d) matrix representation of it is as shown below : Generalized CNOT Gate: Quantum entanglement is a unparalleled property of quantum mechanics, and can be attained by a controlled NOT (CNOT) gate in a binary quantum system. For d-dimensional quantum systems, the binary 2-qubit CNOT gate is generalised to the IN CREM EN T gate: INCREMENT|x |y = |x |(x + y) mod d , if x = d − 1, and = |x |y , otherwise. The (d 2 ×d 2 ) matrix representation of the generalized CNOT C X,d gate is as follows: where I d and 0 d are both d × d matrices as shown below: Generalized Multi-controlled Toffoli Gate: We extend the generalized CNOT or IN CREM EN T further to operate over n qudits as a generalized Multi-controlled Toffoli Gate or n-qudit Toffoli gate C n X,d . For C n X,d , the target qudit is increased by 1 (mod d) only when all n − 1 control qudits have the value d − 1. The (d n × d n ) matrix representation of generalized Multi-controlled Toffoli (MCT) gate is as follows: Owing to technology constraints, a multi-controlled Toffoli gate can be substituted by an equivalent circuit comprising one-qudit and/ two-qudit gates, although at first the multi-controlled Toffoli must be decomposed into a set of Toffoli gates for any dimensional quantum system.
The binary [36] and ternary circuit [8,37] representation of all the above mentioned generalized gates are described in Figure 1.

Generalized Grover's Algorithm in d-dimensional Quantum System
The generalized Grover's algorithm in d-dimensional quantum system is presented here. There exists two sub-parts of the algorithm viz. oracle and diffusion [28]. As per convention, Grover's algorithm for searching in an unstructured database can be defined as follows: given a collection of unstructured database elements x = 1, 2, . . . , N , and an oracle function f (x) that acts on a marked element s as fol- perceive the marked element with as few calls to f (x) as possible [27,28]. The database is encoded into a superposition of quantum states where each element is assigned to a corresponding basis state. Grover's algorithm searches over every possible outcome, which is put forward as a basis vector |x in an n-dimensional Hilbert space in d-dimensional quantum system. Likewise, the marked element is encoded as |s . Thus, the search can be done in parallel, after application of unitary operations as an oracle function to the superposition of the different possible outcomes. The generalized diffusion operator, also known as inversion about the average operator, amplifies the amplitude of the marked state to increase its measurement probability using constructive interference, with simultaneous enfeeblement of all other amplitudes, and searches the marked element in O( . The circuit diagram for the generalized Grover's algorithm in a d-dimensional quantum system is presented in Figure 2, where at least n + 1 qudits are required. More elaborately, the steps of the Grover's algorithm are as follows: Initialization: The algorithm starts with the uniform superposition of all the basis states on the n input qudits in |0 by assimilating generalized Hadamard or quantum DFT gate. The last ancilla qudit is used as an output qudit which is initialized to Oracle query: The oracle (U f ) of Grover's search marks the marked state |s while keeping all the other states unchanged, and can be expressed as: The oracle block U f as shown in Figure 2 is dependant on the problem instance. The oracle using Unitary transformation is needed to be designed as per requirement.
Diffusion: The diffusion operator of Grover's search is generic, it doesn't depend on specific problem . As shown in Figure 2, the diffusion operator is initially assigned with generalized Hadamard (F ⊗n d ), then by 2|0 n 0 n | − I d n and generalized Hadamard (F ⊗n d ) again. The diffusion operator (D) can be expressed as: The matrix representation of generalized diffusion operator [27] for d-dimensional quantum system is shown below: The combination of the oracle and the diffusion gives generalized Grover operator G, We need to din the Grover's operator O( √ N ) times to get the coefficient of the marked state |s large enough so that it can be obtained from measurement with probability close to 1 and thus round off the Grover's algorithm.

Proposed Methodology of Circuit Synthesis for k-coloring Problem using Grover's Algorithm in any Dimensional Quantum System
The flowchart in Figure 3 depicts the complete flow of our proposed automated endto-end framework. Mainly three algorithms: AutoGenOracle K-color, MCT Realization and Qubit Mapping (Binary) are the basis of our framework. At first, AutoGenOracle K-color algorithm, which is based on the newly designed comparator, is implemented with inputs: graph information i.e, adjacency matrix of the given graph and the number of colors (k) to get the output, quantum circuit netlist in the form QASM. Now, MCT Realization algorithm takes as input, generated circuit netlist and MCT gates to NISQ hardware compatible 1-qubit and 2-qubit gates [38] and multi-valued quantum technology compatible 1-qudit and 2-qudit gates are realised. Due to multivalued quantum technology constraint, implementation of multi-valued circuit netlist on multi-valued quantum hardware is technologically infeasible till date, rather we have simulated and verified the multi-valued circuit netlist on multi-valued simulator. Finally, qubit mapping [39,40] algorithm has been used for mapping generated circuit to the NISQ devices based on the qubit topology.
The proposed methodology for the oracle circuit synthesis of the k-coloring problem in any dimensional quantum system as an application of the Grover's search algorithm is sketched in this section. Figure 4 shows the quantum circuit block of oracle for the k-coloring problem in d-dimensional quantum system. The construction of oracle for k-coloring problem is divided into four parts. It starts with initialization, which is essentially required in Grover's Algorithm.

Initialization
Let there be a graph which has n vertices and e edges, k is the given number of colors, then the total number of data qudits that are required for representing all the colored vertices are n * log d k . The oracle performs a check to find all possible right combination of properly colored vertices with k/fewer colors from a combination of all possible colored vertices. A superposition of m = n * log d k qudits thus generates all possible combination of colored vertices. The initial data qudits in Figure 4 include m qudits prepared in the ground state |ψ = |0 ⊗m , due to the re-usability property of ancilla qudits, r = n ancilla qudits in the exited state |θ = |d−1 ⊗r (These r ancilla qudits are required to prepare Invalid Color detector block and comparator block that are thoroughly explained in the next subsection), one ancilla qudit in the ground state |ζ = |0 (1 ancilla is required if invalid color exists), and one output qudit in the excited state |φ = |d − 1 is required to perform generalized CNOT/Toffoli/MCT operation of the oracle. This entire initialization can be mathematically depicted as:

Generalized Hadamard Transformation
The next step after the initialization is Hadamard transformation. The genralized Hadamard transform F d ⊗m on data qudits and F d on output qudit is performed, hence all possible states are superposed as |ψ 0 ⊗ |θ 0 ⊗ |ζ 0 ⊗ |φ 0 , where 3 Proposed U f Transformation for d dimensional system: The proposed unitary U f transformation is distinctly divided into two parts.
(1)Reduction of Invalid Colors: As color, c = log d k , so maximum d c colors are considered. If d c = k, then all colors are valid colors, else there exists a set of d c − k invalid colors. The valid colors are used to optimize the search space. Using the following steps this can be executed: Qudit Activation: Colors should be numbered sequentially as {0, 1, 2....d c − 1}. After the generalized Hadamard transformation, the input data qudit lines act as the d-dimensional representation of combination of all possible colored vertices. The oracle performs a check for only k, which is the combination of valid colors. All the input qudit lines should be in the excited state |d − 1 for those particular combinations of invalid colors by making input qudit lines suitable as control lines for Generalized CNOT/Toffoli/MCT operation to be assured that the oracle is checking only the k-colored combination of vertices. A number of generalized NOT gates must be imposed on the input qudit lines, that are in the ground state |0 accompanied by the application of 'Invalid Color Detector'. Again after 'Invalid Color Detector', this 'Qudit Activation' is to be applied to roll back to the initial superposed quantum state.
Invalid Color Detector: In any combination of colored vertices if any invalid color is noticed then that combination is rejected with the use of the function ICD (Invalid Color Detector) as: The circuit synthesis of 'Invalid Color Detector', that is functionally depicted in Equation 4 for n vertices, where I 1 , I 2 , .., I n are the data qubits, is described in Figure  5 . The circuit synthesis of 'Invalid Color Detector' for ternary quantum system is described in Figure 6. That is again, functionally shown in Equation 5 for n vertices, where I 1 , I 2 , .., I n are the data qutrits.
(2)Comparator: A newly proposed generalized comparator circuit for d-dimensional quantum system can be defined as: where a and b are the comparing inputs representing the colored vertices of the given graph and the ancilla qudit is f . In Figure 7, circuit synthesis for 2-qubit and 4-qubit comparator is shown, the functional description of which is given in Equation 7. The complete circuit synthesis for the binary comparator is designed using CNOT, NOT, Toffoli/MCT gates.  Induced from the above, a newly proposed ternary comparator can be defined as: Circuit synthesis for 2-qutrit ternary comparator is shown in Figure 8. M-S gate and 1-qutrit permutative gate are used to design the complete circuit synthesis for ternary comparator. Initially, the total number of gate count of our newly proposed comparator is reduced by one as compared to the comparator proposed in [33]. But, gate count can be reduced further at the time of oracular circuit synthesis as one of the outputs of our comparator is 2 instead of 1 [33]. As everything has to be mirrored at the time of circuit synthesis in order to eliminate the cost of wires, there is a need to design an inverse comparator. Our newly proposed 2-qutrit ternary inverse comparator is shown in Figure 9. This newly proposed ternary inverse comparator has a reduced gate count compared to the work in [33].

Generalized MCT Operation
The |φ 0 , output qudit state, is initialized as: Applying a Generalized MCT gate on the output line with ancilla qudits as control, an eigenvalue kickback ω (d−1)(d−1) occurs as a result. This causes a phase shift for the respective input state(s), which in turn helps in finding out all the combinations of properly colored set of vertices. In next subsection, we have elaborately sketched about generalized Grover's diffusion operator.

Generalized Diffusion Operator
The circuit implementing the function of diffusion is the second part of Grover's algorithm. The component along |ψ 0 is kept unchanged when the operation is applied to a superposition state, while inverting the components in dimensions that are perpendicular to |ψ 0 . This can be represented as where, |i Figure 10 shows the generalized circuit for Grover's diffusion operator in ddimensional quantum system. It can be constructed using generalized Hadamard gate, generalized NOT gate and generalized multi-controlled Toffoli gate. The algorithm that causes the gate level synthesis of the proposed method is discussed in the next subsection.

Proposed Algorithm for Oracle Circuit Synthesis in any Dimensional Quantum System
The proposed algorithm Algorithm 1 (AutoGenOracleK-Coloring) of automated oracular circuit synthesis for the k-coloring problem in any dimensional quantum system is illustrated in this subsection. The algorithm accepts the adjacency matrix of the given graph and the number of colors k as input parameters. A circuit netlist in the form of QASM is the output of the algorithm.
The total number of qudit lines that are required for the generation of the oracle circuit can be easily evaluated from the details of the adjacency matrix and the number of given colors. All the input data qudits are initialized with |0 followed by genaralized Hadamard, ancilla lines (A r ) are initialized with |d − 1 , ancilla line A r+1 is initialized with |0 and the output line is initialized with |d − 1 followed by generalized Hadamard. First of all, Invalid Color Detector is applied with suitable Qudit Activation (if invalid color exists) with I r , A r as control and A r+1 as the target. After that, between two adjacent vertices(i, j), a generalized comparator circuit is used with two input lines(i, j) as control and the ancilla line(A r ) as output. They perform the same task for all the adjacent vertices. Following this, a generalized MCT gate is used with all the ancilla lines A r and A r+1 as control and the output line as output for the flip operation of the Grover's oracle. In order to achieve the mirror of the oracle circuit, we have repeated the previous steps as shown in Algorithm 1.

Circuit Cost Estimation
The design of generalized oracle for our proposed algorithm has already been described. Now, in this subsection, we furnish the circuit cost analysis of the oracular circuit in Table 1.
n * log d k data qubits are required for n-vertices graph and k given color. At most n + 1 number of ancilla and at most O(n 2 * log d n) gates are required to design the oracular circuit for n-vertices graph. As for example, for binary quantum system, a graph of three vertices with three connected edges (K 3 ) is shown in Figure 11 and a graph of three vertices with two connected edges for ternary quantum system is shown in Figure 12 which illustrates the gate-optimized circuit synthesis of the 3-coloring problem, r ← f , m ← f 8: for j ← i + 1 to n do 9: if adj(i, j) ← 1 (i and j are connected by an edge(e)) then 10: Use a generalized comparator circuit with the input lines (I i , I j ) corresponding (i, j) as control and the ancilla line Ar as target. 11: r ← r + 1 12: end if 13: end for 14: if r > f + 1 then 15: Use a generalized Toffoli/MCT gate with all ancilla lines Ar as control and A l as target 16: l ← l − 1 17: for m ← i + 1 to n do 18: if adj(i, j) ← 1 (i and j are connected by an edge(e)) then 19: Use a generalized comparator circuit with the input lines (I i , Im) corresponding (i, j) as control and the ancilla line Am as target. 20 Fig. 11 Gate level representation of 3-coloring problem for example graph in binary quantum system The focus of this subsection is the mapping of generated oracle circuit to NISQ devices through MCT realization and qubit mapping algorithm. Due to the constraint of the number of qubits, NISQ Devices are "noisy," thus a certain range of error should be allowed during the estimation of the simulated result of a quantum state [4]. Superconducting quantum circuits, quantum dot, ion trap, neutral atom are the most popular NISQ technologies for implementing the quantum circuit. For mapping the logical synthesized circuit to quantum hardware, each one of the above mentioned technologies has a specific dedicated qubit topology, as in Figure 13. Certain 1-qubit and 2-qubit gates that are supported by most of the quantum hardware are illustrated in Table 2. The logical quantum gates are needed to be realized to hardware specific gates for making it hardware compatible for implementation. id, x, y, z, h, r2, r4, r8, rx, ry, rz, u1, u2, u3, s, t, sdg, tdg 2-qubit gates swap, srswap, iswap, xy, cx, cy, cz, ch, csrn, ms, yy, cr2, cr4, cr8, crx, cry, crz, cu1, cu2, cu3, cs, ct, csdg

Realization of MCT Gate
The process of decomposition of MCT gate to NISQ compatible 1-qubit and 2-qubit gates [38] is shown in Figure 14. At first, the MCT gate is to be decomposed to MCZ gate. After that, MCZ gate is realized to MCR x (π). Lastly, without using any ancilla qubit, MCR x (π) is reduced to 1-qubit and 2-qubit gates.

Qubit Mapping to NISQ Devices
As, our proposed quantum circuit is logical, there is no constraint of qubit connectivity. There is a specific qubit topology or coupling graph for NISQ devices. The interaction between two physical qubits is defined by coupling graph. This is different for different NISQ devices. Hence, obviously mapping the logical circuit to the physical one is challenging. The solution to this problem is to insert SWAP gates between the two qubits to comply to the hardware constraint without compromising on the logic of the quantum circuit. The concept behind a good qubit mapping problem is to minimize the number of SWAP insertion gates as well as the depth of the circuit. Li et. al. proposed SWAP-based BidiREctional heuristic search algorithm (SABRE) in [39], which deals with any arbitrary qubit topology for any NISQ devices. Three main features make SABRE noticeable. Firstly, an exhaustive search is not performed on the entire circuit, but a SWAP-based heuristic search is performed keeping in mind the qubit dependency. Then, initial mapping is optimized with the use of a novel reverse traversal technique. Lastly, the decay effect being introduced to enable the trade-off between the depth and the number of gates of the entire algorithm. Tan et. al. formulated layout synthesis for quantum computing, which is a benchmark, as optimization problems [40]. They handed over two synthesizers: an exact layout synthesizer (OLSQ) and an approximate, transition based synthesizer (TB-OLSQ). OLSQ is the first, that guarantees optimality and efficiency both in time and space for general quantum processors, as compared to previous exact approaches. This approach shows some promises of being beneficial for realistic applications for near-term quantum computers. Our proposed circuit can easily be mapped to any arbitrary qubit topology by using one of these protocols.

Realization of Generalized MCT Gate
In [42], Saha et. al. have shown the decomposition of multi-controlled Toffoli gate in d-dimensional quantum system. A generalized Toffoli decomposition in d-dimensional system using |d state is shown in Figure 15. An akin construction for the Toffoli gate in binary using qutrit is evident from a previous work [43]; Saha et. al. have extended it for d-dimensional quantum system. The idea is to execute an X d operation on the target qudit (third qudit) if and only if the two control qudits, are both |d − 1 . Firstly, a |d − 1 -controlled X +1 d+1 , where +1 and d + 1 are used to denote that the target qudit is incremented by 1 (mod d + 1), is implemented on the first and the second qudits. This eventually upgrades the second qudit to |d as long as the first and the second qudits were both |d − 1 . Then, a |d -controlled X d gate is applied to the target qudit. Therefore, X d is executed only when both the first and the second qudits were |d − 1 , as expected. The controls are rolled back to their original states by a |d − 1 -controlled X −1 d+1 gate, which reverses the effect of the first gate. The most important aspect in this decomposition is that the |d state from d + 1-dimensional quantum system can be used instead of ancilla to store temporary information. Fig. 15 Generalized Toffoli in d-dimensional quantum system [42] For further decomposition of the Toffoli for simulation purpose, the d+1-dimensional Toffoli gate has been decomposed into d+2-dimensional CNOT gates. A generalized CNOT gate for d + 2-dimensional quantum system as C +1 X,d+2 , where +1 and d + 2 denote that the target qudit is incremented by 1 (mod d + 2) only when the control qudit value is d + 1. The ((d + 2) 2 × (d + 2) 2 ) matrix representation of the C +1 X,d+2 gate is as follows: where X +1 d+2 and 0 d+2 are both (d + 2) × (d + 2) matrices as shown below: As an example, a 8-qudit Toffoli gate is shown in Figure 16(a). First, we need to decompose it as in [43] as shown in Figure 16(b). Further, we need to decompose all the d+1-dimensional Toffoli gates into (d+2)-dimensional CNOT gates as shown in Figure 16(c) with the help of the Saha et. al. decomposition of the generalized Toffoli in any dimensional quantum system [42]. All the d − 1-controlled Toffoli gates are decomposed into d − 1-controlled and d-controlled CNOT gates as shown in Figure  16(c). Likewise, all the d-controlled Toffoli gates are decomposed into d-controlled and d + 1-controlled CNOT gates. Consequently, with the help of |d and |d + 1 quantum state of (d + 2)-dimensional system, X d is caried out effectively if all the controlled qudits are in |d − 1 state. In this way, any dimensional multi-controlled Toffoli gate can be decomposed.

Experimental result of k-coloring Problem in NISQ Device
The generated oracle circuit for example graph has been taken as an example case for the simulation of k-coloring problem as shown in Figure 11. The simulation is performed on IBMQ cloud based physical device [18]. The resultant probabilistic output after applying Grover's diffusion operator is shown in Figure 17, where the amplitude of the solution state has been amplified. The location of the solution states are |011000 , |100100 , |000110 , |010010 , |001001 , and |100001 where 00, 01, and 10 are the valid colors as we take 11 as invalid color. These are the properly colored vertex combinations in the given example graph that solves the k-coloring problem with high probability. As we have taken K 3 graph as an example graph and the three valid colors are 00, 01, and 10, solution states must be all possible combination of the valid colors.

Experimental result of k-coloring Problem in Ternary Quantum System
Our ternary circuit instance is verified through simulation with the help of MATLAB simulator [44]. Unfortunately, MATLAB has some limitations of memory constraints. For that, the verification of our circuit needs to be restricted with at most six qutrits. Therefore, a graph of three vertices is taken, where one vertex is connected with other two vertices as an example case for simulating the graph coloring problem. As per the Algorithm 1, as a three vertices graph is taken, three qutrits(n * log 3 n ) are required to represent them. As the example graph having two edges, two ancilla qutrit is required to perform the comparator circuit synthesis and one final qutrit as output. As three colors are given, which are encoded as |0 , |1 and |2 . Generally, a graph with three vertices can be colored with the help of three colors in 3 3 = 27 different ways, that can be represented in the ternary quantum system as |000 . . . |222 . Thus, our database contains 27 elements. In Figure 12, the gate level representation of the Grover's circuit is shown. The simulation steps of Figure 12 are: Step 1: At first, all the qutrits of the 3-qutrit register are initialized with |0 .
Step 4: The output of ternary oracle is acted upon by the ternary diffusion operator. This diffusion operator amplifies the amplitudes of the marked states of step 2.
Step 5: Steps 3 and 4 are repeated for N/M times. (For the multiple solution of Grover's operator having N= number of elements in the database and M= number of marked states).
Step 5 after one iteration is shown in Figure 18 where, the amplitude amplification is performed using diffusion operator to amplify the amplitudes of marked state. It can be verified that the location of the searched states (output of step 2) by subtracting one from the index value of Figure 18 and then converting it to its equivalent ternary value. For example, if index value is taken five form Figure 18, after subtracting one and converting it to ternary we get the string |011 , which is one of the searched state. Analysis of the simulation result confirms that our oracle successfully verifies that any set of vertices of a graph is properly colored by the given set of colors.

Comparative Analysis
Our proposed comparator-based oracle gives better result with respect to data qubit and ancilla qubit as n * log 2 k and O(n) respectively, as compared to [30]. The comparative analysis is shown in Table 3. The new ternary oracle circuit for 3 vetices graph achieved 41% reduction in the quantum gate cost as compared to the most recent related work [26] and 85% reduction in the quantum gate cost as compared to the work [32]. Table 4 shows the comparative analysis for higher vertices graphs as well. We show that for 4-vertices and 5-vertices graph, it can be reached to 43% reduction of gate cost.

Conclusion
Here, in this paper, we have proposed an end-to-end framework, which includes mapping of k-coloring problem to any NISQ devices/multi-valued quantum technology through automatic generation of oracle circuit using Grover's search followed by MCT realization for any dimensional quantum system. This proposed approach for any dimensional quantum system is applicable for any undirected and unweighted given graph, which makes our approach generalized in nature. Our comparator-based approach can reduce qubit cost to n * log 2 k as compared to n * k of reductionbased approach from 3-SAT problem to 3-Color problem. This leads to a reduction of query complexity from O(n * k) to O(n * log 2 k). Further, we have shown that our newly proposed ternary comaparator is a key component in designing the circuit for the k-coloring problem using quantum search algorithm. Our new ternary oracle circuit achieved an at least 41% reduction in the quantum gate cost as compared to the most recent related work [26] and an at least 85% reduction in the quantum gate cost as compared to the work [32]. In future, with the evolution of qudit-supported quantum hardware, we would like to validate our designs.