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

arXiv:2312.09388

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

Jehn‐Ruey Jiang, Qiao-Yi Lin

Published Dec 14, 2023• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2312.09388

Related papers

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

Practical Guide to Quantum Computing: Grover's Algorithm # 4

Mikhail Pavlov

Abstract This guide is based on the IBM Quantum course Phase Estimation and Factoring and focuses on Grover’s algorithm, a quantum algorithm for unstructured search problems that provides a quadratic speedup over classical approaches. In an unstructured search problem, we are given a function (often represented as an oracle) that marks one or more “correct” solutions among NNN possible candidates. A classical algorithm requires on the order of O(N)O(N)O(N) evaluations in the worst case. In contrast, Grover’s algorithm finds a solution using only O(N)O(\sqrt{N})O(N) oracle queries. This quadratic improvement implies: The quantum algorithm requires roughly the square root of the number of operations needed classically. Any classical algorithm for unstructured search must have cost at least quadratic relative to Grover’s quantum procedure. Core Idea of the Algorithm Grover’s algorithm relies on: Preparation of a uniform superposition (typically using Hadamard gates). An oracle that marks valid solutions via phase inversion. The Grover diffusion operator, which amplifies the probability amplitude of the marked states through interference. By repeatedly applying the Grover operator, the amplitude of the desired solution grows while others diminish, allowing measurement to reveal the correct answer with high probability. Practical Considerations Despite its theoretical elegance and wide applicability, the quadratic speedup of Grover’s algorithm is unlikely to yield near-term practical advantage. Modern classical hardware operates at extremely high clock rates and is vastly more mature than current quantum devices. For problem sizes accessible to today’s quantum computers, classical systems remain dominant. However, history shows that even sub-quadratic classical improvements — such as: Fast Fourier Transform (FFT) Efficient sorting algorithms like quicksort and mergesort have had transformative practical impact. The crucial distinction is that Grover’s algorithm depends on fundamentally different hardware — quantum processors — which are still in early development. Long-Term Perspective As quantum hardware advances in qubit count, coherence time, and error correction, Grover’s quadratic advantage may become practically significant for: Cryptographic key search Optimization heuristics Combinatorial search problems Amplitude amplification subroutines in broader quantum algorithms Through hands-on experimentation on IBM Q, this lesson demonstrates how theoretical amplitude amplification translates into executable quantum circuits, reinforcing the relationship between interference, probability amplitudes, and computational complexity.

•Mar 4, 2026•0 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

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

Toward an Algorithmic Framework and Grover’s search speedup for Quantum Circuit Design—Leveraging the Minimum Connected Dominating Set Problem as an Example

Chu‐Fu Wang, Yih–Kai Lin, Chia‐Ho Ou +1 more

Abstract In recent years, quantum computing has gradually extended its influence beyond the realm of physics research into the fields of electrical engineering and computer science. Most researchers and programmers remain more familiar with traditional algorithmic techniques based on conventional computer architectures. To address this gap, this study proposes a quantum algorithmic circuit design framework with Grover’s search speedup technique and provides theoretical proofs for some design techniques, aiming to facilitate knowledge transfer and ease the learning curve for designers entering the field of quantum algorithm development. Since combinatorial optimization problems in graph theory serve as the foundation for many practical applications, this study adopts the well-known Connected Dominating Set (CDS) problem as a design example to illustrate the practical applicability of the proposed quantum algorithmic design framework and presents a quantum circuit as a potential solution for addressing realworld challenges in network optimization and related applications. In addition, the circuit proposed in this paper can serve as a quantum oracle to identify connected dominating sets (CDSs) of a graph. When the oracle is applied to a superposition of vertex subsets, Grover’s search algorithm achieves a quadratic speedup. We designed a method for adjusting the initial amplitudes so that the search can be biased toward smaller CDSs, which maximizes the probability of finding the minimum CDS.

Quantum Information and Computation•Dec 1, 2025•0 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
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 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.
Abstract This guide is based on the IBM Quantum course Phase Estimation and Factoring and focuses on Grover’s algorithm, a quantum algorithm for unstructured search problems that provides a quadratic speedup over classical approaches. In an unstructured search problem, we are given a function (often represented as an oracle) that marks one or more “correct” solutions among NNN possible candidates. A classical algorithm requires on the order of O(N)O(N)O(N) evaluations in the worst case. In contrast, Grover’s algorithm finds a solution using only O(N)O(\sqrt{N})O(N) oracle queries. This quadratic improvement implies: The quantum algorithm requires roughly the square root of the number of operations needed classically. Any classical algorithm for unstructured search must have cost at least quadratic relative to Grover’s quantum procedure. Core Idea of the Algorithm Grover’s algorithm relies on: Preparation of a uniform superposition (typically using Hadamard gates). An oracle that marks valid solutions via phase inversion. The Grover diffusion operator, which amplifies the probability amplitude of the marked states through interference. By repeatedly applying the Grover operator, the amplitude of the desired solution grows while others diminish, allowing measurement to reveal the correct answer with high probability. Practical Considerations Despite its theoretical elegance and wide applicability, the quadratic speedup of Grover’s algorithm is unlikely to yield near-term practical advantage. Modern classical hardware operates at extremely high clock rates and is vastly more mature than current quantum devices. For problem sizes accessible to today’s quantum computers, classical systems remain dominant. However, history shows that even sub-quadratic classical improvements — such as: Fast Fourier Transform (FFT) Efficient sorting algorithms like quicksort and mergesort have had transformative practical impact. The crucial distinction is that Grover’s algorithm depends on fundamentally different hardware — quantum processors — which are still in early development. Long-Term Perspective As quantum hardware advances in qubit count, coherence time, and error correction, Grover’s quadratic advantage may become practically significant for: Cryptographic key search Optimization heuristics Combinatorial search problems Amplitude amplification subroutines in broader quantum algorithms Through hands-on experimentation on IBM Q, this lesson demonstrates how theoretical amplitude amplification translates into executable quantum circuits, reinforcing the relationship between interference, probability amplitudes, and computational complexity.
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.
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.
Abstract In recent years, quantum computing has gradually extended its influence beyond the realm of physics research into the fields of electrical engineering and computer science. Most researchers and programmers remain more familiar with traditional algorithmic techniques based on conventional computer architectures. To address this gap, this study proposes a quantum algorithmic circuit design framework with Grover’s search speedup technique and provides theoretical proofs for some design techniques, aiming to facilitate knowledge transfer and ease the learning curve for designers entering the field of quantum algorithm development. Since combinatorial optimization problems in graph theory serve as the foundation for many practical applications, this study adopts the well-known Connected Dominating Set (CDS) problem as a design example to illustrate the practical applicability of the proposed quantum algorithmic design framework and presents a quantum circuit as a potential solution for addressing realworld challenges in network optimization and related applications. In addition, the circuit proposed in this paper can serve as a quantum oracle to identify connected dominating sets (CDSs) of a graph. When the oracle is applied to a superposition of vertex subsets, Grover’s search algorithm achieves a quadratic speedup. We designed a method for adjusting the initial amplitudes so that the search can be biased toward smaller CDSs, which maximizes the probability of finding the minimum CDS.
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.