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

Realization of Deterministic Quantum Circuits for Non-Deterministic or Incompletely Specified Quantum State Machines

Manjith Kumar, Marek Perkowski

Author affiliations
  • Manjith Kumar1
  • Marek Perkowski1
  1. Department of Electrical and Computer Engineering, Portland State University, 1900 SW 4th Avenue, Portland, USA

pp. 716-738 · 10.2478/qic-2025-0038

Read PDF View on Reference Global
On this page

Abstract

In classical logic design, there are machine learning methods based on converting a set of input-output traces to non-deterministic automata that are then converted to deterministic automata and synthesized using logic gates. This approach has not yet been extended to quantum automata. In this paper, we present a method to convert a set of input-output traces to a non-deterministic automaton, which is then converted to an incompletely specified multi-output Boolean function. The existing logic synthesis approaches for designing quantum circuits are insufficient to handle incompletely specified functions. So, we present a novel algorithm to synthesize logic functions with don’t cares using permutative quantum gates. The original MMD (D.M.Miller, D. Maslov, and G.W.Dueck) algorithm minimizes only completely specified reversible functions using cascades of reversible gates. In this paper, this algorithm is modified to allow for the inclusion of don’t cares within the given function’s truth table (reversible or irreversible). The distinguishing property of our presented algorithm QAS, is that it does not add any ancilla qubits if it is not necessary. This algorithm solves the problem of synthesizing deterministic and non-deterministic quantum state machines, both completely specified and incompletely specified.
Open accessCC BY-NC-ND 4.0

Keywords

  • deterministic quantum state machines
  • non-deterministic quantum state machines
  • incompletely specified boolean functions
  • reversible logic
  • quantum gates
  • quantum logic synthesis
  • ancilla qubit minimization
  • quantum cost
  • quantum automata

Suggested citation

Manjith Kumar, Marek Perkowski (2025). Realization of Deterministic Quantum Circuits for Non-Deterministic or Incompletely Specified Quantum State Machines. Quantum Information & Computation, 25(6), 716-738. https://doi.org/10.2478/qic-2025-0038

Download BibTeX

References (63)

  1. Richard P Feynman (1986). Quantum mechanical computers. Found. Phys., 16(6):507–532.DOI: 10.1007/BF01886518Google Scholar
  2. Eleanor Rieffel and Wolfgang Polak (2000). An introduction to quantum computing for non-physicists. ACM Computing Surveys (CSUR), 32(3):300–335.DOI: 10.1145/367701.367709Google Scholar
  3. Michael A Nielsen and Isaac L Chuang (2001). Quantum computation and quantum information, volume 2. Cambridge university press Cambridge.Google Scholar
  4. Asher Peres (1985). Reversible logic and quantum computers. Physical review A, 32(6):3266.DOI: 10.1103/PhysRevA.32.3266Google Scholar
  5. Charles H Bennett (1973). Logical reversibility of computation. IBM journal of Research and Development, 17(6):525–532.DOI: 10.1147/rd.176.0525Google Scholar
  6. Cristopher Moore and James P Crutchfield (2000). Quantum automata and quantum grammars. Theoretical Computer Science, 237(1-2):275–306.DOI: 10.1016/S0304-3975(98)00191-1Google Scholar
  7. Attila Kondacs and John Watrous (1997). On the power of quantum finite state automata. In Proceedings 38th annual symposium on foundations of computer science, pages 66–75. IEEE.DOI: 10.1109/SFCS.1997.646094Google Scholar
  8. AC Cem Say and Abuzer Yakaryılmaz (2014). Quantum finite automata: A modern introduction. In Computing with New Resources: Essays Dedicated to Jozef Gruska on the Occasion of His 80th Birthday, pages 208–222. Springer.DOI: 10.1007/978-3-319-13350-8_16Google Scholar
  9. Jozef Gruska, Daowen Qiu, and Shenggen Zheng (2015). Potential of quantum finite automata with exact acceptance. International Journal of Foundations of Computer Science, 26(03):381–398.DOI: 10.1142/S0129054115500215Google Scholar
  10. Manjith Kumar, Samy Boshra-riad, Yasodha Nachimuthu, and Marek A Perkowski (2010). Comparison of state assignment methods for “quantum circuit” model of permutative quantum state machines. In IEEE Congress on Evolutionary Computation, pages 1–8. IEEE. 2010.DOI: 10.1109/CEC.2010.5586003Google Scholar
  11. Martin Lukac and Marek Perkowski (2009). Quantum finite state machines as sequential quantum circuits. In 2009 39th International Symposium on Multiple-Valued Logic, pages 92–97. IEEE.DOI: 10.1109/ISMVL.2009.46Google Scholar
  12. Sebastian Horvat, Xiaoqin Gao, and Borivoje Dakić (2022). Universal quantum computation via quantum controlled classical operations. Journal of Physics A: Mathematical and Theoretical, 55(7):075301.DOI: 10.1088/1751-8121/ac4393Google Scholar
  13. Yuchen Huang, Marek Perkowski, Xiaoyu Song, and John M Acken (2025). Quantum finite automaton using ternary rotation quantum gates and chrestenson family quantum gates. Quantum Information and Computation, 25(1):57.DOI: 10.2478/qic-2025-0003Google Scholar
  14. Ali Javadi-Abhari, Matthew Treinish, Kevin Krsulich, Christopher J Wood, Jake Lishman, Julien Gacon, et al. (2024). Quantum computing with qiskit. arXiv preprint arXiv:2405.08810.Google Scholar
  15. Alexander S Green, Peter LeFanu Lumsdaine, Neil J Ross, Peter Selinger, and Benoît Valiron (2013). Quipper: a scalable quantum programming language. In Proceedings of the 34th ACM SIGPLAN conference on Programming language design and implementation, pages 333–342.DOI: 10.1145/2491956.2462177Google Scholar
  16. Lov K Grover (1996). A fast quantum mechanical algorithm for database search. In Proceedings of the twentyeighth annual ACM symposium on Theory of computing, pages 212–219.DOI: 10.1145/237814.237866Google Scholar
  17. Edward Farhi and Sam Gutmann (1998). Quantum computation and decision trees. Physical Review A, 58(2):915.DOI: 10.1103/PhysRevA.58.915Google Scholar
  18. Ali Al-Bayaty and Marek Perkowski (2024). Bht-qaoa: The generalization of quantum approximate optimization algorithm to solve arbitrary boolean problems as hamiltonians. Entropy, 26(10):843.DOI: 10.3390/e26100843Google Scholar
  19. Himanshu Thapliyal and Nagarajan Ranganathan (2010). Design of reversible sequential circuits optimizing quantum cost, delay, and garbage outputs. ACM Journal on Emerging Technologies in Computing Systems (JETC), 6(4):1–31.DOI: 10.1145/1877745.1877748Google Scholar
  20. Georgios Giantamidis, Stavros Tripakis, and Stylianos Basagiannis (2021). Learning moore machines from input-output traces. International Journal on Software Tools for Technology Transfer, 23(1):1–29.DOI: 10.1007/s10009-019-00544-0Google Scholar
  21. Martin Lukac and Marek Perkowski (2007). Inductive learning of quantum behaviors. Facta universitatis-series: Electronics and Energetics, 20(3):561–586.DOI: 10.2298/FUEE0703561LGoogle Scholar
  22. Raymond Edward Miller (1965). Switching theory. volume 1-combinational circuits(book on switching theory covering circuit synthesis and analysis, boolean algebra, functional theory, relay type network, etc). John Wiley and Sons, Inc., New York, 351 P.Google Scholar
  23. Andris Ambainis and John Watrous (2002). Two-way finite automata with quantum and classical states. Theoretical Computer Science, 287(1):299–311.DOI: 10.1016/S0304-3975(02)00138-XGoogle Scholar
  24. D Michael Miller, Dmitri Maslov, and Gerhard W Dueck (2003). A transformation based algorithm for reversible logic synthesis. In Proceedings of the 40th annual Design Automation Conference, pages 318–323.DOI: 10.1145/775832.775915Google Scholar
  25. K Chakrabarty and JP Hayes. Balanced boolean functions (1998). IEE Proceedings-Computers and Digital Techniques, 145(1):52–62.DOI: 10.1049/ip-cdt:19981769Google Scholar
  26. JE Hopcroft (2001). Introduction to automata theory, languages, and computation.DOI: 10.1145/568438.568455Google Scholar
  27. Ryszard S Michalski and Kenneth A Kaufman (2001). The aq19 system for machine learning and pattern discovery: A general description and user’s guide. Technical report.Google Scholar
  28. Marek Perkowski, Tim Ross, Dave Gadd, Jeffrey A Goldman, and Ning Song (1995). Application of esop minimization in machine learning and knowledge discovery. In Proc. Reed Muller, volume 95.Google Scholar
  29. Dong Wang, Yiwei Li, Edison Tsai, Xiaoyu Song, Marek Perkowski, and Han Li (2020). Boolean function decomposition based on grover algorithm and its simulation using quantum language quipper. In International Conference on Artificial Intelligence and Security, pages 582–592. Springer.DOI: 10.1007/978-981-15-8083-3_52Google Scholar
  30. Colin De La Higuera (2005). A bibliographical study of grammatical inference. Pattern recognition, 38(9):1332–1348.DOI: 10.1016/j.patcog.2005.01.003Google Scholar
  31. Dana Angluin (1987). Learning regular sets from queries and counterexamples. Information and computation, 75(2):87–106.DOI: 10.1016/0890-5401(87)90052-6Google Scholar
  32. John F Wakerly (2008). Digital Design: Principles and Practices, 4/E. Pearson Education India.Google Scholar
  33. Oleg B Lupanov (1963). A comparison of two types of finite automata. Problemy kibernetiki, 9:321–326.Google Scholar
  34. Frank R Moore (1971). On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata. IEEE Transactions on computers, 100(10):1211–1214.DOI: 10.1109/T-C.1971.223108Google Scholar
  35. Albert R Meyer and Michael J Fischer (1971). Economy of description by automata, grammars, and formal systems. In 12th annual symposium on switching and automata theory (swat 1971), pages 188–191. IEEE Computer Society.DOI: 10.1109/SWAT.1971.11Google Scholar
  36. Amandeep Singh Bhatia and Ajay Kumar (2019). Quantum finite automata: survey, status and research directions. arXiv preprint arXiv:1901.07992.Google Scholar
  37. Paulo Mateus, Daowen Qiu, and LvzhouLi (2012). On the complexity of minimizing probabilistic and quantum automata. Information and Computation, 218:36–53.DOI: 10.1016/j.ic.2012.07.002Google Scholar
  38. Yuchen Huang and Marek Perkowski (2023). One hot encoding synthesis of quantum automata from flowcharts. Journal of Quantum Information Science, 13(3):156–176.DOI: 10.4236/jqis.2023.133009Google Scholar
  39. E.M. Sentovich, K.J. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha et al. (1992). Sangiovanni-Vincentelli. Sis: A system for sequential circuit synthesis. Technical Report UCB/ERL M92/41.Google Scholar
  40. Martin Lukac, Michitaka Kameyama, and Marek A Perkowski (2013). Quantum finite state machines-a circuit based approach. Int. J. Unconv. Comput., 9(3-4):267–301.Google Scholar
  41. Manjith Kumar, Bala Iyer, Natalie Metzger, Ying Wang, and Marek Perkowski (2007). Realization of incompletely specified functions in minimized reversible cascades. Proceedings of Reed-Muller 2007, pages 59–65.Google Scholar
  42. Martin Lukac and Marek Perkowski (2010). Evolutionary logic synthesis of quantum finite state machines for sequence detection. New Achievements in Evolutionary Computation, page 77.DOI: 10.5772/8049Google Scholar
  43. Kazuo Iwama, Yahiko Kambayashi, and Shigeru Yamashita (2002). Transformation rules for designing cnotbased quantum circuits. In Proceedings of the 39th annual Design Automation Conference, pages 419–424.DOI: 10.1145/513918.514026Google Scholar
  44. Alan Mishchenko and Marek Perkowski (2002). Logic synthesis of reversible wave cascades.Google Scholar
  45. Vivek V Shende, Aditya K Prasad, Igor L Markov, and John P Hayes (2002). Reversible logic circuit synthesis. In Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, pages 353–360.DOI: 10.1109/ICCAD.2002.1167558Google Scholar
  46. Abhinav Agrawal and Niraj K Jha (2004). Synthesis of reversible logic. In Proceedings Design, Automation and Test in Europe Conference and Exhibition, volume 2, pages 1384–1385. IEEE.DOI: 10.1109/DATE.2004.1269099Google Scholar
  47. D Maslov and GW Dueck (2003). Reversible function synthesis with minimum garbage outputs. In International Symposium on Representations and Methodology of Future Computing Technologies (RM2003), Trier, Germany.Google Scholar
  48. D Michael Miller and Gerhard W Dueck (2003). Spectral techniques for reversible logic synthesis. In 6th International Symposium on Representations and Methodology of Future Computing Technologies, pages 56–62.Google Scholar
  49. Dmitri Maslov, Christina Young, D Michael Miller, and Gerhard W Dueck (2005). Quantum circuit simplification using templates. In Design, Automation and Test in Europe, pages 1208–1213. IEEE.DOI: 10.1109/DATE.2005.249Google Scholar
  50. Marc Grau Davis, Ethan Smith, Ana Tudor, Koushik Sen, Irfan Siddiqi, and Costin Iancu (2019). Heuristics for quantum compiling with a continuous gate set. arXiv preprint arXiv:1912.02727.Google Scholar
  51. Ethan Smith, Marc Grau Davis, Jeffrey Larson, Ed Younis, Lindsay Bassman Oftelie, Wim Lavrijsen, and Costin Iancu (2003). Leap: Scaling numerical optimization based synthesis using an incremental approach. ACM Transactions on Quantum Computing, 4(1):1–23.DOI: 10.1145/3548693Google Scholar
  52. Ed Younis, Koushik Sen, Katherine Yelick, and Costin Iancu (2020). Qfast: Quantum synthesis using a hierarchical continuous circuit space. arXiv preprint arXiv:2003.04462.Google Scholar
  53. Mathias Weiden, Ed Younis, Justin Kalloor, John Kubiatowicz, and Costin Iancu (2023). Improving quantum circuit synthesis with machine learning. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE), volume 1, pages 1–11. IEEE.DOI: 10.1109/QCE57702.2023.00093Google Scholar
  54. Thomas Fösel, Murphy Yuezhen Niu, Florian Marquardt, and Li Li (2021). Quantum circuit optimization with deep reinforcement learning. arXiv preprint arXiv:2103.07585.Google Scholar
  55. David Kremer, Victor Villar, Hanhee Paik, Ivan Duran, Ismael Faro, and Juan Cruz-Benito (2024). Practical and efficient quantum circuit synthesis and transpiling with reinforcement learning. arXiv preprint arXiv:2405.13196.Google Scholar
  56. Anouk Paradis, Jasper Dekoninck, Benjamin Bichsel, and Martin Vechev (2024). Synthetiq: Fast and versatile quantum circuit synthesis. Proceedings of the ACM on Programming Languages, 8(OOPSLA1):55–82.DOI: 10.1145/3649813Google Scholar
  57. Mozammel HA Khan and Marek Perkowski (2011). Synthesis of reversible synchronous counters. In 2011 41st IEEE International Symposium on Multiple-Valued Logic, pages 242–247. IEEE.DOI: 10.1109/ISMVL.2011.25Google Scholar
  58. Majid Mohammadi and Mohammad Eshghi (2008). Heuristic methods to use don’t cares in automated design of reversible and quantum logic circuits. Quantum Information Processing, 7:175–192.DOI: 10.1007/s11128-008-0081-xGoogle Scholar
  59. Marek Perkowski, Robert Fiszer, Paweł Kerntopf, and Martin Lukac (2012). Synthesis of reversible circuits with pse gates. In 21st International Workshop on Post-Binary ULSI Systems. University of Victoria.Google Scholar
  60. Robert Adrian Fiszer (2014). Synthesis of irreversible incompletely specified multi-output functions to reversible eosops circuits with pse gates. Master’s thesis, Portland State University.Google Scholar
  61. Mathias Soeken, Martin Roetteler, Nathan Wiebe, and Giovanni De Micheli (2017). Logic synthesis for quantum computing. arXi vpreprint arXiv:1706.02721.Google Scholar
  62. Dmitri Maslov (2005). Reversible logic synthesis benchmarks page. https://reversiblebenchmarks.github.io/.Google Scholar
  63. Barry C Sanders (2025). Superconducting quantum computing beyond 100 qubits. Physics, 18:45.DOI: 10.1103/Physics.18.45Google Scholar