Logo PTI Logo FedCSIS

Proceedings of the 21st Conference on Computer Science and Intelligence Systems (FedCSIS)

Annals of Computer Science and Information Systems, Volume 47

Quantum Counting for Topological Analysis of Noncoherent Systems

,

DOI: http://dx.doi.org/10.15439/2026F3315

Citation: Tomas Sobek,

Full text

Abstract. Topological analysis of binary-state systems is a fundamental part of reliability engineering. While efficient computing methods exist for coherent systems, noncoherent systems require exhaustive enumeration of all 2n states. Recent works have explored quantum computing for reliability analysis through Bayesian networks and general optimization frameworks, but no prior study has addressed computation of topological measures of noncoherent systems using quantum solution. This paper presents a systematic procedure for constructing a quantum oracle from a compact Boolean netlist and combines it with the quantum counting algorithm to achieve a quadratic speedup. This research also investigates ancilla qubit recycling, achieving 18--46\% qubit reduction, and identify its incompatibility with controlled operations in quantum phase estimation. The approach is verified on five reference systems and LGSynth'91 benchmarks. These results establish quantum counting as a viable computational framework for topological analysis of noncoherent systems.

References

  1. M. Rausand, A. Barros, and A. Høyland, System Reliability Theory. Bognor Regis, UK: John Wiley & Sons, Ltd., 3 ed., 2020.
  2. E. Zaitseva and V. Levashenko, “Investigation multi-state system reliability by structure function,” in 2nd International Conference on Dependability of Computer Systems (DepCoS-RELCOMEX ’07), (Szklarska Por˛ eba, Poland), pp. 81–90, 2007.
  3. M. Kvassay and E. Zaitseva, “Topological Analysis of Multi-state Systems Based on Direct Partial Logic Derivatives,” in Recent Advances in Multi-state Systems Reliability: Theory and Applications (A. Lisnianski, I. Frenkel, and A. Karagrigoriou, eds.), pp. 265–281, Cham: Springer International Publishing, 2018.
  4. E. Zaitseva, P. Sedlacek, and V. Levashenko, “Importance analysis of non-coherent multi-state system,” Reliability Engineering & System Safety, vol. 266, p. 111618, 2026.
  5. I. Gioda, D. Caputo, E. Fadda, D. Manerba, B. Silva Fernández, and R. Tadei, “Solving assignment problems via quantum computing: a case-study in train seating arrangement,” in 2021 16th Conference on Computer Science and Intelligence Systems (FedCSIS), pp. 217–220, 2021.
  6. M. Yazdi, “Application of Quantum Computing in Reliability Analysis,” in Advances in Computational Mathematics for Industrial System Reliability and Maintainability (M. Yazdi, ed.), pp. 139–154, Cham: Springer Nature Switzerland, 2024.
  7. S. Salfale, G. Dhakad, S. Bara, Abhinav Krishnan T. K., and I. Hazra, “Quantum Bayesian Networks for Reliability Analysis of Unmanned Systems,” in Proceedings of the ASME International Mechanical Engineering Congress and Exposition India (IMECE-INDIA2025), American Society of Mechanical Engineers Digital Collection, Dec. 2025.
  8. L. K. Grover, “A fast quantum mechanical algorithm for database search,” in Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC ’96, (Philadelphia, Pennsylvania, United States), pp. 212–219, ACM Press, 1996.
  9. A. Rauzy, “Mathematical foundations of minimal cutsets,” IEEE Transactions on Reliability, vol. 50, pp. 389–396, Dec. 2001.
  10. M. Kvassay, V. Levashenko, and E. Zaitseva, “Analysis of minimal cut and path sets based on direct partial Boolean derivatives,” Proceedings of the Institution of Mechanical Engineers, Part O: Journal of Risk and Reliability, vol. 230, pp. 147–161, Apr. 2016.
  11. M. O. Locks, “A Minimizing Algorithm for Sum of Disjoint Products,” IEEE Transactions on Reliability, vol. R-36, pp. 445–453, Oct. 1987.
  12. M. O. Locks, “Recursive Disjoint Products, Inclusion-Exclusion, and Min-Cut Approximations,” IEEE Transactions on Reliability, vol. R-29, pp. 368–371, Dec. 1980.
  13. Y. Crama and P. L. Hammer, Boolean Functions: Theory, Algorithms, and Applications. Cambridge University Press, May 2011. GoogleBooks-ID: 3KmyKpw_pbUC.
  14. M. Kvassay, E. Zaitseva, V. Levashenko, and J. Kostolny, “Reliability Analysis of Multiple-Outputs Logic Circuits Based on Structure Function Approach,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 36, pp. 398–411, Mar. 2017.
  15. W. G. Schneeweiss, “A short Boolean derivation of mean failure frequency for any (also non-coherent) system,” Reliability Engineering & System Safety, vol. 94, pp. 1363–1367, Aug. 2009.
  16. S. Upadhyaya and H. Pham, “Analysis of noncoherent systems and an architecture for the computation of the system reliability,” IEEE Transactions on Computers, vol. 42, pp. 484–493, Apr. 1993.
  17. L. G. Valiant, “The complexity of enumeration and reliability problems,” SIAM Journal on Computing, vol. 8, no. 3, pp. 410–421, 1979.
  18. R. E. Bryant, “Graph-based algorithms for boolean function manipulation,” IEEE Transactions on Computers, vol. C-35, no. 8, pp. 677–691, 1986.
  19. J. Kostolny, M. Kvassay, and S. Kovalik, “Reliability Analysis of Noncoherent Systems by Logical Differential Calculus and Binary Decision Diagrams,” Communications - Scientific letters of the University of Zilina, vol. 16, pp. 114–120, Feb. 2014.
  20. E. Zaitseva, V. Levashenko, and J. Kostolny, “Importance analysis based on logical differential calculus and Binary Decision Diagram,” Reliability Engineering & System Safety, vol. 138, pp. 135–144, June 2015.
  21. M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, Dec. 2010.
  22. A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter, “Elementary gates for quantum computation,” Physical Review A, vol. 52, pp. 3457–3467, Nov. 1995.
  23. G. G. Fogel, B. Baran, and M. Villagra, “Comparison of two types of quantum oracles based on grover’s adaptative search algorithm for multiobjective optimization problems,” in 2017 Federated Conference on Computer Science and Information Systems (FedCSIS), pp. 421–428, IEEE, 2017.
  24. R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca, “Quantum algorithms revisited,” Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, vol. 454, pp. 339–354, Jan. 1998.
  25. M. Boyer, G. Brassard, P. Høyer, and A. Tapp, “Tight Bounds on Quantum Searching,” Fortschritte der Physik, vol. 46, no. 4-5, pp. 493– 505, 1998.
  26. S. Aaronson and P. Rall, “Quantum approximate counting, simplified,” in 2020 Symposium on Simplicity in Algorithms (SOSA), pp. 24–32, 2020.
  27. C. R. Wie, “Simpler Quantum Counting,” Quantum Information and Computation, vol. 19, no. 11-12, 2019.
  28. M. Soeken, G. Meuli, B. Schmitt, F. Mozafari, H. Riener, and G. De Micheli, “Boolean satisfiability in quantum compilation,” Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, vol. 378, p. 20190161, Dec. 2019.
  29. S. Hadfield, “On the Representation of Boolean and Real Functions as Hamiltonians for Quantum Computing,” ACM Transactions on Quantum Computing, vol. 2, pp. 18:1–18:21, Dec. 2021.
  30. S. Yang, Logic synthesis and optimization benchmarks user guide: version 3.0. Microelectronics Center of North Carolina (MCNC) Research Triangle Park, NC, USA, 1991.
  31. R. K. Brayton, G. D. Hachtel, C. McMullen, and A. SangiovanniVincentelli, Logic minimization algorithms for VLSI synthesis, vol. 2. Springer Science & Business Media, 1984.
  32. Z. Diao, C. Huang, and K. Wang, “Quantum Counting: Algorithm and Error Distribution,” Acta Applicandae Mathematicae, vol. 118, pp. 147– 159, Apr. 2012.
  33. G. Brassard, P. HØyer, and A. Tapp, “Quantum counting,” in Automata, Languages and Programming (K. G. Larsen, S. Skyum, and G. Winskel, eds.), (Berlin, Heidelberg), pp. 820–831, Springer, 1998.
  34. IBM Quantum, “Introduction to Qiskit.” https://quantum.cloud.ibm.com/ docs/en/guides/quick-start, 2026. Accessed: Apr. 13, 2026.