Toward an Algorithmic Framework and Grover’s search speedup for Quantum Circuit Design—Leveraging the Minimum Connected Dominating Set Problem as an Example
Quantum Information & Computation · 01.12.2025 · 25 (6) · 687-715
DOI: 10.2478/qic-2025-0037 ↗Kurz gefasst
Fachartikel in der Zeitschrift Quantum Information & Computation, online erschienen am 09.03.2026. Verfasst von Chu-Fu Wang und 3 weiteren Autor:innen. Die Arbeit nennt 31 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0).
Abstract (Originalsprache)
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.
Zitieren
APA
Wang, C., Lin, Y., Ou, C., & Shih, J. (2025). Toward an Algorithmic Framework and Grover’s search speedup for Quantum Circuit Design—Leveraging the Minimum Connected Dominating Set Problem as an Example. Quantum Information & Computation, 25(6), 687-715. https://doi.org/10.2478/qic-2025-0037
Vancouver
Wang C, Lin Y, Ou C, Shih J. Toward an Algorithmic Framework and Grover’s search speedup for Quantum Circuit Design—Leveraging the Minimum Connected Dominating Set Problem as an Example. Quantum Information & Computation. 2025;25(6):687-715. doi:10.2478/qic-2025-0037
BibTeX
@article{Wang2025,
author = {Wang, Chu-Fu and Lin, Yih-Kai and Ou, Chia-Ho and Shih, Jau-Der},
title = {Toward an Algorithmic Framework and Grover’s search speedup for Quantum Circuit Design—Leveraging the Minimum Connected Dominating Set Problem as an Example},
journal = {Quantum Information & Computation},
year = {2025},
volume = {25},
number = {6},
pages = {687--715},
doi = {10.2478/qic-2025-0037}
}
EUVIMED