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 VTS Asia Pacific Wireless Communications Symposium (APWCS)

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

Jehn‐Ruey Jiang, Yujie Wang

Published Aug 1, 2023• 9 citations
Publisher

Abstract

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.

DOI
10.1109/apwcs60142.2023.10234054

Related papers

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

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

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

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 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

Quantum algorithm for minimum dominating set problem with circuit design

Haoying 皓颖 Zhang 张, Shaoxuan 绍轩 Wang 王, Xinjian 新建 Liu 刘 +2 more

Using quantum algorithms to solve various problems has attracted widespread attention with the development of quantum computing. Researchers are particularly interested in using the acceleration properties of quantum algorithms to solve NP-complete problems. This paper focuses on the well-known NP-complete problem of finding the minimum dominating set in undirected graphs. To expedite the search process, a quantum algorithm employing Grover’s search is proposed. However, a challenge arises from the unknown number of solutions for the minimum dominating set, rendering direct usage of original Grover’s search impossible. Thus, a swap test method is introduced to ascertain the number of iterations required. The oracle, diffusion operators, and swap test are designed with achievable quantum gates. The query complexity is O(1.414 n ) and the space complexity is O(n). To validate the proposed approach, qiskit software package is employed to simulate the quantum circuit, yielding the anticipated results.

Chinese Physics B•Oct 13, 2023•6 citations
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.
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.
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.
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.
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.
Using quantum algorithms to solve various problems has attracted widespread attention with the development of quantum computing. Researchers are particularly interested in using the acceleration properties of quantum algorithms to solve NP-complete problems. This paper focuses on the well-known NP-complete problem of finding the minimum dominating set in undirected graphs. To expedite the search process, a quantum algorithm employing Grover’s search is proposed. However, a challenge arises from the unknown number of solutions for the minimum dominating set, rendering direct usage of original Grover’s search impossible. Thus, a swap test method is introduced to ascertain the number of iterations required. The oracle, diffusion operators, and swap test are designed with achievable quantum gates. The query complexity is O(1.414 n ) and the space complexity is O(n). To validate the proposed approach, qiskit software package is employed to simulate the quantum circuit, yielding the anticipated results.