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 Eurasia Conference on IOT, Communication and Engineering (ECICE)

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

Jehn‐Ruey Jiang, Wei-Han Yan

Published Oct 27, 2023• 5 citations
Publisher

Abstract

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.

DOI
10.1109/ecice59523.2023.10383108

Related papers

Utilizing Novel Quantum Counters for Grover's Algorithm to Solve the Dominating Set Problem

Jehn‐Ruey Jiang, Qiao-Yi Lin

Grover's algorithm is a well-known unstructured quantum search algorithm run on quantum computers. It constructs an oracle and calls the oracle O($\sqrt N$) times to locate specific data out of N unsorted data. This represents a quadratic speedup compared to the classical unstructured data sequential search algorithm, which requires to call the oracle O(N) times. We are currently 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 components with three good properties: (i) a reduced number of qubits, (ii) shorter quantum depth, and (iii) fewer gates. This paper utilizes novel quantum counters with the above-mentioned three good properties to construct the oracle of Grover's algorithm to efficiently solve the dominating set problem (DSP), as defined below. For a given graph G=(V, E), a dominating set (DS) D is a subset of the vertex set V, such that every vertex is in D or has an adjacent vertex in D. The DSP is to decide for a given graph G and an integer k whether there exists a DS with size k. Algorithms solving the DSP have many applications. For example, they can be applied to check whether k routers suffice to connect all computers in a computer network. The DSP is an NP-complete problem, indicating that no classical algorithm exists to solve the DSP with polynomial time complexity in the worst case. Therefore, using quantum algorithms, such as Grover's algorithm, to exploit the potent computational capabilities of quantum computers to solve the DSP is highly promising. We execute the whole quantum circuit of Grover's algorithm using novel quantum counters through the IBM Quantum Lab service to validate that the circuit can solve the DSP efficiently and correctly.

arXiv:2312.09388•Dec 14, 2023•1 citation

Quantum Circuit Based on Grover’s Algorithm to Solve Exact Cover Problem

Jehn‐Ruey Jiang, Yujie Wang

In this paper, we propose a quantum circuit based on Grover’s algorithm to solve the exact cover problem (ECP), which is NP-hard. A novel controlled counter is designed and used to implement the ECP oracle to check if every element is covered by a set exactly once. If so, a feasible solution is found. The phase of the qubit state representing a feasible solution is flipped by calling the oracle, and the state’s amplitude is amplified through the diffusion operator o($\sqrt{2^{n}}$) times, where n is the number of sets given in the ECP. Thanks to Grover’s algorithm, the proposed quantum circuit achieves quadratic speedup compared with the classical algorithm that needs to call the oracle O($2^{n}$) times. To validate our approach, we execute the proposed quantum circuit using the IBM Quantum Lab service.

IEEE VTS Asia Pacific Wireless Communications Symposium (APWCS)•Aug 1, 2023•9 citations

Using a Simplified Quantum Counter to Implement Quantum Circuits Based on Grover’s Algorithm to Tackle the Exact Cover Problem

Jehn‐Ruey Jiang, Yujie Wang

In this paper, we use a simplified quantum counter to implement Grover’s algorithm-based quantum circuits to tackle the NP-hard exact cover problem (ECP). The ECP seeks a subcollection of sets such that every element is covered by exactly one set. Leveraging Grover’s algorithm, our quantum circuits achieve a quadratic speedup, querying the oracle O(N) times, compared to O(N) for classical methods, where N=2n is the total number of unstructured input instances and n is the number of input (quantum) bits. For the whole quantum circuit, the simplified quantum counter saves (4mb−4m)⌊π/4N/M⌋ quantum gates and reduces the quantum circuit depth by (2mb)⌊π/4N/M⌋ compared to Heidari et al.’s design, where b=⌊logn⌋+1 is the number of counting qubits used in a counter. Experimental results obtained using IBM Qiskit packages confirm the effectiveness of our quantum circuits.

Mathematics•Dec 29, 2024•9 citations

Solving Hamiltonian Cycle Problem with Grover’s Algorithm Using Novel Quantum Circuit Designs

Jehn‐Ruey Jiang, Tzu-Hao Kao

The Hamiltonian cycle problem (HCP) is related to the decision of whether there exists a cycle in a graph that visits every vertex exactly once. It is a well-known NP-complete problem, and thus there currently exists no classical algorithm solving it with polynomial time complexity in the worst case. With the emergence of quantum computers, the introduction of Grover’s algorithm has suggested new possibilities for solving the HCP more efficiently. In this article, we propose three novel quantum circuit designs of quantum counters to be embedded in the oracle of Grover’s algorithm to check if the input instance satisfies the HCP constraints to solve the HCP. We executed Grover’s algorithm with the novel quantum circuit designs, through the IBM Quantum Lab service, to solve the HCP to validate the design correctness.

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

Dicke State Quantum Search for Solving the Vertex Cover Problem

Jehn‐Ruey Jiang

This paper proposes a quantum algorithm, named Dicke state quantum search (DSQS), to set qubits in the Dicke state |Dkn⟩ of D states in superposition to locate the target inputs or solutions of specific patterns among 2n unstructured input instances, where n is the number of input qubits and D=nk=O(nk) for min(k,n−k)≪n/2. Compared to Grover’s algorithm, a famous quantum search algorithm that calls an oracle and a diffuser O(2n) times, DSQS requires no diffuser and calls an oracle only once. Furthermore, DSQS does not need to know the number of solutions in advance. We prove the correctness of DSQS with unitary transformations, and show that each solution can be found by DSQS with an error probability less than 1/3 through O(nk) repetitions, as long as min(k,n−k)≪n/2. Additionally, this paper proposes a classical algorithm, named DSQS-VCP, to generate quantum circuits based on DSQS for solving the k-vertex cover problem (k-VCP), a well-known NP-complete (NPC) problem. Complexity analysis demonstrates that DSQS-VCP operates in polynomial time and that the quantum circuit generated by DSQS-VCP has a polynomial qubit count, gate count, and circuit depth as long as min(k,n−k)≪n/2. We thus conclude that the k-VCP can be solved by the DSQS-VCP quantum circuit in polynomial time with an error probability less than 1/3 under the condition of min(k,n−k)≪n/2. Since the k-VCP is NP-complete, NP and NPC problems can be polynomially reduced to the k-VCP. If the reduced k-VCP instance satisfies min(k,n−k)≪n/2, then both the instance and the original NP/NPC problem instance to which it corresponds can be solved by the DSQS-VCP quantum circuit in polynomial time with an error probability less than 1/3. All statements of polynomial algorithm execution time in this paper apply only to VCP instances and similar instances of other problems, where min(k,n−k)≪n/2. Thus, they imply neither NP ⊆ BQP nor P = NP. In this restricted regime of min(k,n−k)≪n/2, the Dicke state subspace has a polynomial size of D=nk=O(nk), and our DSQS algorithm samples from it without asymptotic superiority over exhaustive enumeration. Nevertheless, DSQS may be combined with other quantum algorithms to better exploit the strengths of quantum computation in practice. Experimental results using IBM Qiskit packages show that the DSQS-VCP quantum circuit can solve the k-VCP successfully.

Mathematics•Sep 17, 2025•3 citations

Quantum Circuit Based on Grover Algorithm to Solve Hamiltonian Cycle Problem

Jehn‐Ruey Jiang

We propose the concepts of the explicit oracle and the implicit oracle for realizing quantum algorithms. Then, the quantum circuit of the well-known Grover algorithm is constructed with the explicit oracle to solve the Hamiltonian cycle problem for the complete graph. The quantum circuit has a quadratic speedup over the classical unstructured search algorithm for solving the same problem. The IBM quantum computer simulator is used to run the quantum circuit to validate that it can indeed derive the Hamiltonian cycle of the complete graph.

IEEE Eurasia Conference on IOT, Communication and Engineering (ECICE)•Oct 28, 2022•10 citations
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.
Grover's algorithm is a well-known unstructured quantum search algorithm run on quantum computers. It constructs an oracle and calls the oracle O(N\sqrt NN​) times to locate specific data out of N unsorted data. This represents a quadratic speedup compared to the classical unstructured data sequential search algorithm, which requires to call the oracle O(N) times. We are currently 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 components with three good properties: (i) a reduced number of qubits, (ii) shorter quantum depth, and (iii) fewer gates. This paper utilizes novel quantum counters with the above-mentioned three good properties to construct the oracle of Grover's algorithm to efficiently solve the dominating set problem (DSP), as defined below. For a given graph G=(V, E), a dominating set (DS) D is a subset of the vertex set V, such that every vertex is in D or has an adjacent vertex in D. The DSP is to decide for a given graph G and an integer k whether there exists a DS with size k. Algorithms solving the DSP have many applications. For example, they can be applied to check whether k routers suffice to connect all computers in a computer network. The DSP is an NP-complete problem, indicating that no classical algorithm exists to solve the DSP with polynomial time complexity in the worst case. Therefore, using quantum algorithms, such as Grover's algorithm, to exploit the potent computational capabilities of quantum computers to solve the DSP is highly promising. We execute the whole quantum circuit of Grover's algorithm using novel quantum counters through the IBM Quantum Lab service to validate that the circuit can solve the DSP efficiently and correctly.
In this paper, we propose a quantum circuit based on Grover’s algorithm to solve the exact cover problem (ECP), which is NP-hard. A novel controlled counter is designed and used to implement the ECP oracle to check if every element is covered by a set exactly once. If so, a feasible solution is found. The phase of the qubit state representing a feasible solution is flipped by calling the oracle, and the state’s amplitude is amplified through the diffusion operator o(2n\sqrt{2^{n}}2n​) times, where n is the number of sets given in the ECP. Thanks to Grover’s algorithm, the proposed quantum circuit achieves quadratic speedup compared with the classical algorithm that needs to call the oracle O(2n2^{n}2n) times. To validate our approach, we execute the proposed quantum circuit using the IBM Quantum Lab service.
In this paper, we use a simplified quantum counter to implement Grover’s algorithm-based quantum circuits to tackle the NP-hard exact cover problem (ECP). The ECP seeks a subcollection of sets such that every element is covered by exactly one set. Leveraging Grover’s algorithm, our quantum circuits achieve a quadratic speedup, querying the oracle O(N) times, compared to O(N) for classical methods, where N=2n is the total number of unstructured input instances and n is the number of input (quantum) bits. For the whole quantum circuit, the simplified quantum counter saves (4mb−4m)⌊π/4N/M⌋ quantum gates and reduces the quantum circuit depth by (2mb)⌊π/4N/M⌋ compared to Heidari et al.’s design, where b=⌊logn⌋+1 is the number of counting qubits used in a counter. Experimental results obtained using IBM Qiskit packages confirm the effectiveness of our quantum circuits.
The Hamiltonian cycle problem (HCP) is related to the decision of whether there exists a cycle in a graph that visits every vertex exactly once. It is a well-known NP-complete problem, and thus there currently exists no classical algorithm solving it with polynomial time complexity in the worst case. With the emergence of quantum computers, the introduction of Grover’s algorithm has suggested new possibilities for solving the HCP more efficiently. In this article, we propose three novel quantum circuit designs of quantum counters to be embedded in the oracle of Grover’s algorithm to check if the input instance satisfies the HCP constraints to solve the HCP. We executed Grover’s algorithm with the novel quantum circuit designs, through the IBM Quantum Lab service, to solve the HCP to validate the design correctness.
This paper proposes a quantum algorithm, named Dicke state quantum search (DSQS), to set qubits in the Dicke state |Dkn⟩ of D states in superposition to locate the target inputs or solutions of specific patterns among 2n unstructured input instances, where n is the number of input qubits and D=nk=O(nk) for min(k,n−k)≪n/2. Compared to Grover’s algorithm, a famous quantum search algorithm that calls an oracle and a diffuser O(2n) times, DSQS requires no diffuser and calls an oracle only once. Furthermore, DSQS does not need to know the number of solutions in advance. We prove the correctness of DSQS with unitary transformations, and show that each solution can be found by DSQS with an error probability less than 1/3 through O(nk) repetitions, as long as min(k,n−k)≪n/2. Additionally, this paper proposes a classical algorithm, named DSQS-VCP, to generate quantum circuits based on DSQS for solving the k-vertex cover problem (k-VCP), a well-known NP-complete (NPC) problem. Complexity analysis demonstrates that DSQS-VCP operates in polynomial time and that the quantum circuit generated by DSQS-VCP has a polynomial qubit count, gate count, and circuit depth as long as min(k,n−k)≪n/2. We thus conclude that the k-VCP can be solved by the DSQS-VCP quantum circuit in polynomial time with an error probability less than 1/3 under the condition of min(k,n−k)≪n/2. Since the k-VCP is NP-complete, NP and NPC problems can be polynomially reduced to the k-VCP. If the reduced k-VCP instance satisfies min(k,n−k)≪n/2, then both the instance and the original NP/NPC problem instance to which it corresponds can be solved by the DSQS-VCP quantum circuit in polynomial time with an error probability less than 1/3. All statements of polynomial algorithm execution time in this paper apply only to VCP instances and similar instances of other problems, where min(k,n−k)≪n/2. Thus, they imply neither NP ⊆ BQP nor P = NP. In this restricted regime of min(k,n−k)≪n/2, the Dicke state subspace has a polynomial size of D=nk=O(nk), and our DSQS algorithm samples from it without asymptotic superiority over exhaustive enumeration. Nevertheless, DSQS may be combined with other quantum algorithms to better exploit the strengths of quantum computation in practice. Experimental results using IBM Qiskit packages show that the DSQS-VCP quantum circuit can solve the k-VCP successfully.
We propose the concepts of the explicit oracle and the implicit oracle for realizing quantum algorithms. Then, the quantum circuit of the well-known Grover algorithm is constructed with the explicit oracle to solve the Hamiltonian cycle problem for the complete graph. The quantum circuit has a quadratic speedup over the classical unstructured search algorithm for solving the same problem. The IBM quantum computer simulator is used to run the quantum circuit to validate that it can indeed derive the Hamiltonian cycle of the complete graph.