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 Nanoelectronic and Information Systems (iNIS)

Synthesis of Vertex Coloring Problem Using Grover's Algorithm

Amit Saha, Avik Chongder, Sudhindu Bikash Mandal, Amlan Chakrabarti

Published Dec 1, 2015• 12 citations
Publisher

Abstract

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.

DOI
10.1109/inis.2015.55

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

Novel Quantum Circuit Designs for the Oracle of Grover’s Algorithm to Solve the Vertex Cover Problem

Jehn‐Ruey Jiang, Wei-Han Yan

We propose new quantum circuit designs for the Grover oracle, i.e., the oracle of Grover’s algorithm, to solve the vertex cover problem (VCP) efficiently. Grover’s algorithm is an unstructured quantum search algorithm to search a target data item out of N data pieces by calling the oracle $\mathrm{O}(\sqrt{N})$ times. It represents a quadratic speedup compared to the classical unstructured data sequential search algorithm, which requires O(N) oracle calls. We are in the noisy intermediate-scale quantum (NISQ) era in which quantum computers have a limited number of qubits, short decoherence time, and low gate fidelity. It is thus desirable to design quantum circuits with three properties: (1) a reduced number of qubits, (2) shorter quantum depth, and (3) fewer gates. We created novel designs of a quantum counter and a quantum semaphore to be applied to the Grover oracle to have the three properties. Through the IBM Quantum Lab service, we executed Grover’s algorithm with the novel quantum circuit designs to solve the VCP to validate the design correctness.

IEEE Eurasia Conference on IOT, Communication and Engineering (ECICE)•Oct 27, 2023•5 citations

Classical Search and Quantum Search Algorithms for Synthesis of Quantum Circuits and Optimization of Quantum Oracles

Sazzad Hossain

We observe an enormous increase in the computational power of digital computers. This was due to the revolution in manufacturing processes and controlling semiconductor structures on submicron scale, ultimately leading to the control of individual atoms. Eventually, the classical electric circuits encountered the barrier of quantum mechanics and its effects. However, the laws of quantum mechanics can be also used to produce computational devices that lead to extraordinary speed increases over classical computers. Thus quantum computing becomes a very promising and attractive research area. The Computer Aided Design for Quantum circuits becomes an essential ingredient for such emerging research which may lead to these powerful computers to be realized—an era of Quantum computing. This thesis presents an integrated theoretical study of software algorithms to design circuits of quantum oracles as well as methods for designing quantum oracles for Grover algorithm to solve combinatorial problems. An implementation of quantum algorithm involves the initialization of the input state and its manipulation with quantum gates followed by the measurements. In Grover algorithm the problem to be solved is specified by a permutative logic oracle – the fundamental problem is then how to build this oracle from quantum logic circuits and how to optimize these circuits. These problems are NP-hard and require search algorithms. In future, the search will be also done in quantum and this thesis leads to quantum algorithms to design quantum circuits more efficiently.

•Jan 1, 2009•1 citation

Layout-Aware Quantum Circuitry and Algorithmic Extensions to Grover's Algorithm

Ali Al-Bayaty

Lov K. Grover introduced, in 1996, Grover's algorithm as a quantum search algorithm to find all solutions for quantum oracles representing classical problems. My research observed that the Grover diffusion operator of Grover's algorithm gives wrong solutions when Boolean oracles are designed in some logical structures. Therefore, I invented the new "controlled-diffusion operator" for Boolean oracles as a new approach for Grover's algorithm that always correctly solves the problem of Grover's algorithm. Another important problem in quantum computing is designing reliable and cost-effective quantum gates using reversible binary logic. In classical logic design, the stage of logic design can be separated from the stage of mapping topological circuits to geometrical architecture. In contrast to classical logic design, the stages of quantum circuit design are not separable. For practical quantum applications, a quantum circuit is realized (transpiled) into the layout of a real quantum device. For a real quantum device, two factors affect the cost-effective transpilation: the utilization of supported (native) gates and the geometrical connectivity pattern of n neighboring physical qubits, where native gates ensure cost-effective transpilation and n ≥ 2. In this dissertation, I introduced two new approaches to leverage these two factors for real IBM quantum devices. The first approach initializes the uniform distribution for all qubits using IBM native √X gates, instead of using the conventional Hadamard gates, which are IBM non-native gates producing cost-expensive transpilation. The second approach geometrically constructs generic and cost-effective quantum gates using IBM native gates. In literature the Bloch sphere is used as a visualization tool for a quantum gate, which is initially designed using unitary matrices computations. In contrast, I introduced the Bloch sphere approach (BSA) as a "geometrical design tool" to design a quantum gate using the Bloch sphere, which leads to fewer unitary matrices computations. I employed the BSA to design various generic and cost-effective quantum gates and libraries based on the layouts of IBM quantum devices. Using the BSA, I invented two quantum libraries to investigate the trade-off between scalability and reliability, for the purpose of how the input qubits of a quantum gate are routed into the layout of an IBM quantum device and how many ancilla qubits are utilized. Experimentally, for the same layout of an IBM quantum device, I prove that the transpiled quantum circuits of oracles utilizing my two approaches always have lower quantum costs and shorter depths than those of the transpiled quantum

•Mar 6, 2025•2 citations

Automatic Generation of Grover Quantum Oracles for Arbitrary Data Structures

Raphael Seidel, Colin Kai‐Uwe Becker, Bock, Sebastian +3 more

The steadily growing research interest in quantum computing - together with the accompanying technological advances in the realization of quantum hardware - fuels the development of meaningful real-world applications, as well as implementations for well-known quantum algorithms. One of the most prominent examples till today is Grover's algorithm, which can be used for efficient search in unstructured databases. Quantum oracles that are frequently masked as black boxes play an important role in Grover's algorithm. Hence, the automatic generation of oracles is of paramount importance. Moreover, the automatic generation of the corresponding circuits for a Grover quantum oracle is deeply linked to the synthesis of reversible quantum logic, which - despite numerous advances in the field - still remains a challenge till today in terms of synthesizing efficient and scalable circuits for complex boolean functions. In this paper, we present a flexible method for automatically encoding unstructured databases into oracles, which can then be efficiently searched with Grover's algorithm. Furthermore, we develop a tailor-made method for quantum logic synthesis, which vastly improves circuit complexity over other current approaches. Finally, we present another logic synthesis method that considers the requirements of scaling onto real world backends. We compare our method with other approaches through evaluating the oracle generation for random databases and analyzing the resulting circuit complexities using various metrics.

arXiv:2110.07545•Oct 14, 2021•2 citations

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

Yushi Wang, Marek A. Perkowski

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.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2011•27 citations
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.
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.
We propose new quantum circuit designs for the Grover oracle, i.e., the oracle of Grover’s algorithm, to solve the vertex cover problem (VCP) efficiently. Grover’s algorithm is an unstructured quantum search algorithm to search a target data item out of N data pieces by calling the oracle O(N)\mathrm{O}(\sqrt{N})O(N​) times. It represents a quadratic speedup compared to the classical unstructured data sequential search algorithm, which requires O(N) oracle calls. We are in the noisy intermediate-scale quantum (NISQ) era in which quantum computers have a limited number of qubits, short decoherence time, and low gate fidelity. It is thus desirable to design quantum circuits with three properties: (1) a reduced number of qubits, (2) shorter quantum depth, and (3) fewer gates. We created novel designs of a quantum counter and a quantum semaphore to be applied to the Grover oracle to have the three properties. Through the IBM Quantum Lab service, we executed Grover’s algorithm with the novel quantum circuit designs to solve the VCP to validate the design correctness.
We observe an enormous increase in the computational power of digital computers. This was due to the revolution in manufacturing processes and controlling semiconductor structures on submicron scale, ultimately leading to the control of individual atoms. Eventually, the classical electric circuits encountered the barrier of quantum mechanics and its effects. However, the laws of quantum mechanics can be also used to produce computational devices that lead to extraordinary speed increases over classical computers. Thus quantum computing becomes a very promising and attractive research area. The Computer Aided Design for Quantum circuits becomes an essential ingredient for such emerging research which may lead to these powerful computers to be realized—an era of Quantum computing. This thesis presents an integrated theoretical study of software algorithms to design circuits of quantum oracles as well as methods for designing quantum oracles for Grover algorithm to solve combinatorial problems. An implementation of quantum algorithm involves the initialization of the input state and its manipulation with quantum gates followed by the measurements. In Grover algorithm the problem to be solved is specified by a permutative logic oracle – the fundamental problem is then how to build this oracle from quantum logic circuits and how to optimize these circuits. These problems are NP-hard and require search algorithms. In future, the search will be also done in quantum and this thesis leads to quantum algorithms to design quantum circuits more efficiently.
Lov K. Grover introduced, in 1996, Grover's algorithm as a quantum search algorithm to find all solutions for quantum oracles representing classical problems. My research observed that the Grover diffusion operator of Grover's algorithm gives wrong solutions when Boolean oracles are designed in some logical structures. Therefore, I invented the new "controlled-diffusion operator" for Boolean oracles as a new approach for Grover's algorithm that always correctly solves the problem of Grover's algorithm. Another important problem in quantum computing is designing reliable and cost-effective quantum gates using reversible binary logic. In classical logic design, the stage of logic design can be separated from the stage of mapping topological circuits to geometrical architecture. In contrast to classical logic design, the stages of quantum circuit design are not separable. For practical quantum applications, a quantum circuit is realized (transpiled) into the layout of a real quantum device. For a real quantum device, two factors affect the cost-effective transpilation: the utilization of supported (native) gates and the geometrical connectivity pattern of n neighboring physical qubits, where native gates ensure cost-effective transpilation and n ≥ 2. In this dissertation, I introduced two new approaches to leverage these two factors for real IBM quantum devices. The first approach initializes the uniform distribution for all qubits using IBM native √X gates, instead of using the conventional Hadamard gates, which are IBM non-native gates producing cost-expensive transpilation. The second approach geometrically constructs generic and cost-effective quantum gates using IBM native gates. In literature the Bloch sphere is used as a visualization tool for a quantum gate, which is initially designed using unitary matrices computations. In contrast, I introduced the Bloch sphere approach (BSA) as a "geometrical design tool" to design a quantum gate using the Bloch sphere, which leads to fewer unitary matrices computations. I employed the BSA to design various generic and cost-effective quantum gates and libraries based on the layouts of IBM quantum devices. Using the BSA, I invented two quantum libraries to investigate the trade-off between scalability and reliability, for the purpose of how the input qubits of a quantum gate are routed into the layout of an IBM quantum device and how many ancilla qubits are utilized. Experimentally, for the same layout of an IBM quantum device, I prove that the transpiled quantum circuits of oracles utilizing my two approaches always have lower quantum costs and shorter depths than those of the transpiled quantum
The steadily growing research interest in quantum computing - together with the accompanying technological advances in the realization of quantum hardware - fuels the development of meaningful real-world applications, as well as implementations for well-known quantum algorithms. One of the most prominent examples till today is Grover's algorithm, which can be used for efficient search in unstructured databases. Quantum oracles that are frequently masked as black boxes play an important role in Grover's algorithm. Hence, the automatic generation of oracles is of paramount importance. Moreover, the automatic generation of the corresponding circuits for a Grover quantum oracle is deeply linked to the synthesis of reversible quantum logic, which - despite numerous advances in the field - still remains a challenge till today in terms of synthesizing efficient and scalable circuits for complex boolean functions. In this paper, we present a flexible method for automatically encoding unstructured databases into oracles, which can then be efficiently searched with Grover's algorithm. Furthermore, we develop a tailor-made method for quantum logic synthesis, which vastly improves circuit complexity over other current approaches. Finally, we present another logic synthesis method that considers the requirements of scaling onto real world backends. We compare our method with other approaches through evaluating the oracle generation for random databases and analyzing the resulting circuit complexities using various metrics.