Quantum Information & Computation
Volume 25, Issue 6
RESEARCH ARTICLE Open access

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, Jau-Der Shih

Author affiliations
  • Chu-Fu Wang1
  • Yih-Kai Lin1
  • Chia-Ho Ou2
  • Jau-Der Shih1
  1. Department of Computer Science and Artificial Intelligence, National Pingtung University, Pingtung, Taiwan, ROC
  2. Department of Computer Science and Information Engineering, National Pingtung University, Pingtung, Taiwan, ROC; Graduate School of Information Sciences, Tohoku University, Sendai, Japan

pp. 687-715 · 10.2478/qic-2025-0037

Read PDF View on Reference Global
On this page

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.
Open accessCC BY-NC-ND 4.0

Keywords

  • index terms-quantum computing
  • quantum logic
  • connected dominating set
  • wireless sensor networks

Suggested citation

Chu-Fu Wang, Yih-Kai Lin, Chia-Ho Ou, Jau-Der Shih (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

Download BibTeX

References (31)

  1. P.W. Shor (1994). Algorithms for quantum computation: Discrete log and factoring, in Proceeding of the 35th Annual Symposium on Foundations of Computer Science, pp.124-134.DOI: 10.1109/SFCS.1994.365700Google Scholar
  2. P.W. Shor (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, Society for Industrial and Applied Mathematics Journal on Computing, Vol.26, No.5, pp.1484-1509.DOI: 10.1137/S0097539795293172Google Scholar
  3. E. Rieffel and W. Polak (2000). An introduction to quantum computing for non-physicists. ACM Computing Surveys, Vol.32, Issue 3, pp.300-335.DOI: 10.1145/367701.367709Google Scholar
  4. A. Montanaro (2016). Quantum algorithms: an overview. NPJ Quantum Information, Vol.2.DOI: 10.1038/npjqi.2015.23Google Scholar
  5. Quantum logic gate (2024). Wikipedia:Quantum logic gate Wikimedia Foundation. en.wikipedia.org/wiki/Quantum-logic-gate.Google Scholar
  6. L.K. Grover (1996). A fast quantum mechanical algorithm for database search, In the Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, pp.212-219.DOI: 10.1145/237814.237866Google Scholar
  7. L.K. Grover (1998). A framework for fast quantum mechanical algorithms, In the Proceedings of the 30th Annual ACM Symposium on the Theory of Computing, pp.53-62.DOI: 10.1145/276698.276712Google Scholar
  8. S. Pabst and Y. Nam (2022). A quantum algorithm for network reliability. Quantum Physics.Google Scholar
  9. Y.J. Zhang, X.D. Mua, X.W. Liu, X.Y. Wang, X. Zhang, K. Li, T.Y. Wub, D. Zhao and C. Dong (2022). Applying the quantum approximate optimization algorithm to the minimum vertex cover problem. Applied Soft Computing, Vol.118, pp.1-8.DOI: 10.1016/j.asoc.2022.108554Google Scholar
  10. R. Wong, W.L. Chang, W.Y. Chung and A.V. Vasilakos (2023). Biomolecular and quantum algorithms for the dominating set problem in arbitrary networks. Scientific Reports, Vol.13, Article No.4205.DOI: 10.1038/s41598-023-30600-4Google Scholar
  11. C.H. Bennett, P. Bernstein, P. Brassard and P. Vazirani (1997). Strengths and weaknesses of quantum computing, SIAM Journal on Computing, Vol.26, Issue 5, pp1510-1523.DOI: 10.1137/S0097539796300933Google Scholar
  12. F. Glover, G. Kochenberger and R. Hennig (2022). Quantum bridge analytics I: a tutorial on formulating and using QUBO models. Annals of Operations Research, Vol.314, pp.141-183.DOI: 10.1007/s10479-022-04634-2Google Scholar
  13. L.P. Yu, C.Y. Chen, C.S. Lai, B. Sheu, S.K. Kao and C.R. Chang (2021). Annealing in the noisy intermediatescale quantum era: key concepts and approaches. IEEE Nanotechnology Magazine, Vol.15, No.6, pp.21-27, 2021.DOI: 10.1109/MNANO.2021.3113217Google Scholar
  14. G. Kochenberger, J.K. Hao, F. Glover, M. Lewis, Z. Lu, H. Wang and Y. Wang (2014). The unconstrained binary quadratic programming problem: a survey. Journal of Combinatorial Optimization, Vol.28, Issue 1, pp.58-81.DOI: 10.1007/s10878-014-9734-0Google Scholar
  15. C.H. Ou, C.Y. Chen, C.F. Wang and C.R. Chang (2023). Quantum-inspired vehicle routing scheme for rebalancing in bike sharing systems, Vol.13, No.2, pp.2340018-1-8, SPIN.DOI: 10.1142/S2010324723400180Google Scholar
  16. R. Nikouei, N. Rasoulib, S. Tahmasebic, S. Zolfid and H. Faragardie (2019). A quantum-annealing-based approach to optimize the deployment cost of a multi-sink multi-controller WSN. Procedia Computer Science, Vol.155, pp.250-257.DOI: 10.1016/j.procs.2019.08.036Google Scholar
  17. T. Krauss and J. Mccollum (2020). Solving the network shortest path problem on a quantum annealer. IEEE Transactions on Quantum Engineering, Vol.1, pp.1-12.DOI: 10.1109/TQE.2020.3021921Google Scholar
  18. M.R. Garey and D.H. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company.Google Scholar
  19. A.H. Karbasi and R.E. Atani (2013). Application of dominating sets in wireless sensor network. International Journal of Security and Its Applications, Vol.7, No.4, pp.185-202.Google Scholar
  20. J. Yu, N. Wang, G. Wang and D. Yu (2013). Connected dominating sets in wireless ad hoc and sensor networks-A comprehensive survey. Computer Communications, Vol.36, Issue 2, pp.121-134.DOI: 10.1016/j.comcom.2012.10.005Google Scholar
  21. D.Z. Du and P.J. Wan (2013). Connected Dominating Set: Theory and Applications, Springer.Google Scholar
  22. Z. Zhang, J. Zhou and D. Du (2016). Performance guaranteed approximation algorithm for fault-tolerant connected dominating set in wireless sensor networks, in Proceeding of the 35th Annual IEEE International Conference on Computer Communications (IEEE INFORCOM’16), pp.1-8.DOI: 10.1109/INFOCOM.2016.7524456Google Scholar
  23. L. Song, C. Liu, H. Huang, H. Du and X. Jia (2019). Minimum connected dominating set under routing cost constraint in wireless sensor networs with different transmission ranges. IEEE/ACM Transactions on Networking, Vol.27, No.2, pp.546-559.DOI: 10.1109/TNET.2019.2894749Google Scholar
  24. H. Tang, T.C.E. Cheng, and C.T. Ng (2009). Finite dominating sets for the multi-facility ordered median problem in networks and algorithmic applications. Computers & Industrial Engineering, Vol.57, Issue 3, pp.707-71.DOI: 10.1016/j.cie.2009.01.015Google Scholar
  25. Z. Shao, R. Kosari, R. Anoos, S. Sheikholeslami, J. Dayap and R.L (2020). Gutierrez, Outer-convex dominating set in the corona of graphs as encryption key generator, Complexity, 2020.DOI: 10.1155/2020/8316454Google Scholar
  26. J.R. Jiang and Q.Y. Lin (2023). Utilizing Novel Quantum Counters for Grover’s Algorithm to Solve the Dominating Set Problem. arXiv preprint arXiv:2312.09388.Google Scholar
  27. A.M. Krol and Z. Al-Ars (2024). Beyond Quantum Shannon: Circuit Construction for General n-Qubit Gates Based on Block ZXZ-Decomposition. arXiv preprint arXiv:2403.13692.Google Scholar
  28. M. A. Nielsen and I. L. Chuang (2010). Quantum Computation and Quantum Information, Cambridge University Press.Google Scholar
  29. Qiskit (2017). IBM Quantum. Version 1.0.0. Available at: https://qiskit.org/.Google Scholar
  30. Guifré Vidal (2003). Efficient classical simulation of slightly entangled quantum computations. Physical review letters, 91(14):147902.DOI: 10.1103/PhysRevLett.91.147902Google Scholar
  31. Ulrich Schollwöck (2011). The density-matrix renormalization group in the age of matrix product states. Annals of physics, 326(1):96–192.DOI: 10.1016/j.aop.2010.09.012Google Scholar