Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Symposium on Multiple-Valued Logic (ISMVL)

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

Yushi Wang, Marek A. Perkowski

Published May 1, 2011• 27 citations
Publisher

Abstract

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.

DOI
10.1109/ismvl.2011.42

Related papers

Synthesis of Ternary Grover's Algorithm

Sudhindu Bikash Mandal, Amlan Chakrabarti, Susmita Sur‐Kolay

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.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2014•11 citations

Synthesis of Vertex Coloring Problem Using Grover's Algorithm

Amit Saha, Avik Chongder, Sudhindu Bikash Mandal +1 more

Many applications such as Graph coloring, Triangle finding, Boolean satisfiability, Traveling salesman problem can be solved by Grover's search algorithm, which is one of the remarkable quantum computing algorithm. To design a quantum circuit for a given quantum algorithm, which involves Grover's search, we need to define an oracle circuit specific to the given algorithm and the diffusion operator for amplification of the desired quantum state. In this paper, we propose a quantum circuit implementation for the oracle of the vertex coloring problem based on Grover's algorithmic approach. To the best of our knowledge, this is a first of its kind approach in regards to the quantum circuit synthesis of the vertex coloring oracle in binary quantum domain. We have performed the synthesis of the proposed oracle circuit for the six commonly available Physical Machine Description (PMD) gate libraries using the Fault Tolerant Quantum Logic Synthesis (FTQLS) tool. The synthesis results have been presented to understand the cost estimation of the oracle circuit for the various PMDs in terms of number of quantum operations and number of cycles.

IEEE International Symposium on Nanoelectronic and Information Systems (iNIS)•Dec 1, 2015•12 citations

A Grover Search-Based Algorithm for the List Coloring Problem

Sayan Mukherjee

Graph coloring is a computationally difficult problem, and currently the best known classical algorithm for$k$-coloring of graphs on$n$vertices has runtimes$\Omega (2^n)$for$k\geq 5$. The list coloring problem asks the following more general question: given alistof available colors for each vertex in a graph, does it admit a proper coloring? We propose a hybrid classical-quantum algorithm based on Grover search 12 to quadratically speed up exhaustive search. Our algorithm loses in complexity to classical ones in specific restricted cases, but improves exhaustive search for cases, where the lists and graphs considered are arbitrary in nature.

arXiv:2108.09061•IEEE Transactions on Quantum Engineering•Jan 1, 2022•25 citations

A Quantum Framework for K Coloring of Graphs

Lord Sen, Shyamapada Mukherjee

Graph coloring is a well-known NP-complete problem with applications in scheduling, register allocation, frequency assignment, and network optimization. Quantum computing offers the potential for polynomial or even super-polynomial speedups in certain problem instances, yet practical quantum graph coloring methods must carefully balance qubit resources, circuit depth, and constraint enforcement. We proposed a solver agnostic quantum framework for $K$-coloring. Along with a novel encoding and efficient constraint implementation for its exact coloring exploiting Grover search and almost optimal coloring by the Quantum Approximate Optimization Algorithm \emph{(QAOA)}, and \emph{Quantum Annealing}. Unlike using $O(NK)$ qubits as in \emph{SOTA}, we reduced the qubit requirements to $O(N \log_2 K)$, along with optimized comparator circuits enforcing adjacency constraints. Further symmetry-based graph reduction is incorporated as an optional preprocessing step to further reduce the instance size before quantum execution.

quant-pharXiv:2609.32348•International Conference on Computational Intelligence and Communication Networks (CICN)•Sep 29, 2026•0 citations

Comparison of Influence of Two Data-Encoding Methods for Grover Algorithm on Quantum Costs

Sidharth Dhawan, Marek A. Perkowski

It is important to be able to calculate realistic estimates of quantum costs for real oracles used in quantum algorithms. In this paper, we compare Perkowski's oracle data encoding method with Hogg's encoding method for Grover algorithm, to examine the decrease in Oracle gate cost, if any, for four common constraint satisfaction problems: Graph coloring, Satisfiability, Send-More-Money and Max Clique.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2011•3 citations

Quantum Grover's Oracles with Symmetry Boolean Functions

Peng Dong Gao

Quantum computing has become an important research field of computer science and engineering. Among many quantum algorithms, Grover's algorithm is one of the most famous ones. Designing an effective quantum oracle poses a challenging conundrum in circuit and system-level design for practical application realization of Grover's algorithm. In this dissertation, we present a new method to build quantum oracles for Grover's algorithm to solve graph theory problems. We explore generalized Boolean symmetric functions with lattice diagrams to develop a low quantum cost and area efficient quantum oracle. We study two graph theory problems: cycle detection of undirected graphs and generalized hypercube partitioning. We present a novel method to design a quantum oracle to solve Boolean function minimization problems which occur in classical circuit optimization.

•Aug 9, 2021•0 citations
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.
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.
Many applications such as Graph coloring, Triangle finding, Boolean satisfiability, Traveling salesman problem can be solved by Grover's search algorithm, which is one of the remarkable quantum computing algorithm. To design a quantum circuit for a given quantum algorithm, which involves Grover's search, we need to define an oracle circuit specific to the given algorithm and the diffusion operator for amplification of the desired quantum state. In this paper, we propose a quantum circuit implementation for the oracle of the vertex coloring problem based on Grover's algorithmic approach. To the best of our knowledge, this is a first of its kind approach in regards to the quantum circuit synthesis of the vertex coloring oracle in binary quantum domain. We have performed the synthesis of the proposed oracle circuit for the six commonly available Physical Machine Description (PMD) gate libraries using the Fault Tolerant Quantum Logic Synthesis (FTQLS) tool. The synthesis results have been presented to understand the cost estimation of the oracle circuit for the various PMDs in terms of number of quantum operations and number of cycles.
Graph coloring is a computationally difficult problem, and currently the best known classical algorithm forkkk-coloring of graphs onnnnvertices has runtimesΩ(2n)\Omega (2^n)Ω(2n)fork≥5k\geq 5k≥5. The list coloring problem asks the following more general question: given alistof available colors for each vertex in a graph, does it admit a proper coloring? We propose a hybrid classical-quantum algorithm based on Grover search 12 to quadratically speed up exhaustive search. Our algorithm loses in complexity to classical ones in specific restricted cases, but improves exhaustive search for cases, where the lists and graphs considered are arbitrary in nature.
Graph coloring is a well-known NP-complete problem with applications in scheduling, register allocation, frequency assignment, and network optimization. Quantum computing offers the potential for polynomial or even super-polynomial speedups in certain problem instances, yet practical quantum graph coloring methods must carefully balance qubit resources, circuit depth, and constraint enforcement. We proposed a solver agnostic quantum framework for KKK-coloring. Along with a novel encoding and efficient constraint implementation for its exact coloring exploiting Grover search and almost optimal coloring by the Quantum Approximate Optimization Algorithm \emph{(QAOA)}, and \emph{Quantum Annealing}. Unlike using O(NK)O(NK)O(NK) qubits as in \emph{SOTA}, we reduced the qubit requirements to O(Nlog⁡2K)O(N \log_2 K)O(Nlog2​K), along with optimized comparator circuits enforcing adjacency constraints. Further symmetry-based graph reduction is incorporated as an optional preprocessing step to further reduce the instance size before quantum execution.
Quantum computing has become an important research field of computer science and engineering. Among many quantum algorithms, Grover's algorithm is one of the most famous ones. Designing an effective quantum oracle poses a challenging conundrum in circuit and system-level design for practical application realization of Grover's algorithm. In this dissertation, we present a new method to build quantum oracles for Grover's algorithm to solve graph theory problems. We explore generalized Boolean symmetric functions with lattice diagrams to develop a low quantum cost and area efficient quantum oracle. We study two graph theory problems: cycle detection of undirected graphs and generalized hypercube partitioning. We present a novel method to design a quantum oracle to solve Boolean function minimization problems which occur in classical circuit optimization.