Have a personal or library account? Click to login
Toward an Algorithmic Framework and Grover’s search speedup for Quantum Circuit Design—Leveraging the Minimum Connected Dominating Set Problem as an Example Cover

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
Volume 25 (2025): Issue 6 (December 2025)
By: Chu-Fu Wang,  Yih-Kai Lin,  Chia-Ho Ou and  Jau-Der Shih  
Open Access
|Mar 2026

Figures & Tables

Figure 1.

The backbone routing for wireless sensor networks using the connected dominating set.
The backbone routing for wireless sensor networks using the connected dominating set.

Figure 2.

The fundamental concept for quantum states.
The fundamental concept for quantum states.

Figure 3.

A numerical example of a CDS problem.
A numerical example of a CDS problem.

Figure 4.

A numerical example for cost function representation.
A numerical example for cost function representation.

Figure 5.

The AND and OR quantum operations.
The AND and OR quantum operations.

Figure 6.

An example for the qubit formula update.
An example for the qubit formula update.

Figure 7.

A numerical example for characteristic determination.
A numerical example for characteristic determination.

Figure 8.

An example for results output and the measurement.
An example for results output and the measurement.

Figure 9.

The architecture of the proposed solution method.
The architecture of the proposed solution method.

Figure 10.

The solution method for the dominating test process (the dominated flag qubits updating operations).
The solution method for the dominating test process (the dominated flag qubits updating operations).

Figure 11.

The solution method for the dominating test process (the dominating test qubit characteristic determination operations).
The solution method for the dominating test process (the dominating test qubit characteristic determination operations).

Figure 12.

The solution method for the Connected test process (the reachable flag qubit updating operations).
The solution method for the Connected test process (the reachable flag qubit updating operations).

Figure 13.

The quantum operations for the Connected test process (the Reachability test operations (QC3Reach-akQC3_{{\rm{Reach - a}}}^k)).
The quantum operations for the Connected test process (the Reachability test operations (QC3Reach-akQC3_{{\rm{Reach - a}}}^k)).

Figure 14.

The quantum operations for the Connected test process (the Reachability test operations (QC3Reach-bkQC3_{{\rm{Reach - b}}}^k and QC3ReachkQC3_{{\rm{Reach}}}^k)).
The quantum operations for the Connected test process (the Reachability test operations (QC3Reach-bkQC3_{{\rm{Reach - b}}}^k and QC3ReachkQC3_{{\rm{Reach}}}^k)).

Figure 15.

The operation steps for the Reachability testing process.
The operation steps for the Reachability testing process.

Figure 16.

The operation steps for the Connected test process.
The operation steps for the Connected test process.

Figure 17.

The quantum circuit for the Connected test process (QC3).
The quantum circuit for the Connected test process (QC3).

Figure 18.

The quantum circuit for the Size computation process (QC4) (the Half adder approach).
The quantum circuit for the Size computation process (QC4) (the Half adder approach).

Figure 19.

The quantum circuit for the Size computation process (QC4) (the Toffoli gate approach).
The quantum circuit for the Size computation process (QC4) (the Toffoli gate approach).

Figure 20.

The illustration of the Results output & the measurement.
The illustration of the Results output & the measurement.

Figure 21.

Geometric visualization of the weighted search algorithm in the two-dimensional subspace. The initial state |v〉 makes angle θ2{\theta \over 2} with the horizontal axis, while |xt〉 represents the target state (vertical). Each guf iteration rotates the quantum state by θ, where θ ≈ 2αxt depends on the initial target amplitude. After k iterations, the initial state |v〉 is rotated into a final state, denoted |ϕ〉, that is closely aligned with the target state |xt〉.
Geometric visualization of the weighted search algorithm in the two-dimensional subspace. The initial state |v〉 makes angle θ2{\theta \over 2} with the horizontal axis, while |xt〉 represents the target state (vertical). Each guf iteration rotates the quantum state by θ, where θ ≈ 2αxt depends on the initial target amplitude. After k iterations, the initial state |v〉 is rotated into a final state, denoted |ϕ〉, that is closely aligned with the target state |xt〉.

Figure 22.

QC201 and QC210.
QC201 and QC210.

Figure 23.

Implementation of QC301, QC310, QC312, QC321, QC323, QC332, QC334, QC343, QC345, QC354, QC314, and QC341.
Implementation of QC301, QC310, QC312, QC321, QC323, QC332, QC334, QC343, QC345, QC354, QC314, and QC341.

Figure 24.

Implementation of the truth table approach for finding the size of the dominating set.
Implementation of the truth table approach for finding the size of the dominating set.

Figure 25.

The implementation of the half-adder approach for finding the size of the dominating set.
The implementation of the half-adder approach for finding the size of the dominating set.

Figure 26.

Comparison of the simulation time of graph G between using fast adder and half adder. The x-axis is the number of shots in the simulation, and the y-axis represents the simulation time (in seconds).
Comparison of the simulation time of graph G between using fast adder and half adder. The x-axis is the number of shots in the simulation, and the y-axis represents the simulation time (in seconds).

Figure 27.

Comparison of the simulation time of graph G′ = (V, E – {e14}) between using fast adder and half adder The x-axis represents the number of shots in the simulation, and the y-axis represents the simulation time (in seconds).
Comparison of the simulation time of graph G′ = (V, E – {e14}) between using fast adder and half adder The x-axis represents the number of shots in the simulation, and the y-axis represents the simulation time (in seconds).
DOI: https://doi.org/10.2478/qic-2025-0037 | Journal eISSN: 3106-0544 | Journal ISSN: 1533-7146
Journal RSS Feed
Language: English
Page range: 687 - 715
Submitted on: Sep 7, 2025
|
Accepted on: Oct 20, 2025
|
Published on: Mar 9, 2026
Published by: Cerebration Science Publishing Co., Limited
In partnership with: Paradigm Publishing Services
Publication frequency: 1 issue per year
Keywords:
index terms-quantum computing,
quantum logic,
connected dominating set,
wireless sensor networks
Related subjects:
Physics,
Quantum physics,
Mathematics,
Applied mathematics,
Computer sciences,
Computer sciences in the humanities,
Computer sciences,
Computer sciences in natural sciences

© 2026 Chu-Fu Wang, Yih-Kai Lin, Chia-Ho Ou, Jau-Der Shih, published by Cerebration Science Publishing Co., Limited
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Previous articleVolume 25 (2025): Issue 6 (December 2025)Next article