Utilizing Novel Quantum Counters for Grover's Algorithm to Solve the
  Dominating Set Problem
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.
Jehn-Ruey Jiang Qiao-Yi Lin