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

Manjith Kumar; Marek Perkowski

doi:10.2478/qic-2025-0038

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.

References

Richard P Feynman (1986). Quantum mechanical computers. Found. Phys., 16(6):507–532.
Search in Google Scholar Back to article
Eleanor Rieffel and Wolfgang Polak (2000). An introduction to quantum computing for non-physicists. ACM Computing Surveys (CSUR), 32(3):300–335.
Search in Google Scholar Back to article
Michael A Nielsen and Isaac L Chuang (2001). Quantum computation and quantum information, volume 2. Cambridge university press Cambridge.
Search in Google Scholar Back to article
Asher Peres (1985). Reversible logic and quantum computers. Physical review A, 32(6):3266.
Search in Google Scholar Back to article
Charles H Bennett (1973). Logical reversibility of computation. IBM journal of Research and Development, 17(6):525–532.
Search in Google Scholar Back to article
Cristopher Moore and James P Crutchfield (2000). Quantum automata and quantum grammars. Theoretical Computer Science, 237(1-2):275–306.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Edward Farhi and Sam Gutmann (1998). Quantum computation and decision trees. Physical Review A, 58(2):915.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Martin Lukac and Marek Perkowski (2007). Inductive learning of quantum behaviors. Facta universitatis-series: Electronics and Energetics, 20(3):561–586.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Andris Ambainis and John Watrous (2002). Two-way finite automata with quantum and classical states. Theoretical Computer Science, 287(1):299–311.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
K Chakrabarty and JP Hayes. Balanced boolean functions (1998). IEE Proceedings-Computers and Digital Techniques, 145(1):52–62.
Search in Google Scholar Back to article
JE Hopcroft (2001). Introduction to automata theory, languages, and computation.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Colin De La Higuera (2005). A bibliographical study of grammatical inference. Pattern recognition, 38(9):1332–1348.
Search in Google Scholar Back to article
Dana Angluin (1987). Learning regular sets from queries and counterexamples. Information and computation, 75(2):87–106.
Search in Google Scholar Back to article
John F Wakerly (2008). Digital Design: Principles and Practices, 4/E. Pearson Education India.
Search in Google Scholar Back to article
Oleg B Lupanov (1963). A comparison of two types of finite automata. Problemy kibernetiki, 9:321–326.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Amandeep Singh Bhatia and Ajay Kumar (2019). Quantum finite automata: survey, status and research directions. arXiv preprint arXiv:1901.07992.
Search in Google Scholar Back to article
Paulo Mateus, Daowen Qiu, and LvzhouLi (2012). On the complexity of minimizing probabilistic and quantum automata. Information and Computation, 218:36–53.
Search in Google Scholar Back to article
Yuchen Huang and Marek Perkowski (2023). One hot encoding synthesis of quantum automata from flowcharts. Journal of Quantum Information Science, 13(3):156–176.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Martin Lukac and Marek Perkowski (2010). Evolutionary logic synthesis of quantum finite state machines for sequence detection. New Achievements in Evolutionary Computation, page 77.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Alan Mishchenko and Marek Perkowski (2002). Logic synthesis of reversible wave cascades.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Ed Younis, Koushik Sen, Katherine Yelick, and Costin Iancu (2020). Qfast: Quantum synthesis using a hierarchical continuous circuit space. arXiv preprint arXiv:2003.04462.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Thomas Fösel, Murphy Yuezhen Niu, Florian Marquardt, and Li Li (2021). Quantum circuit optimization with deep reinforcement learning. arXiv preprint arXiv:2103.07585.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Mathias Soeken, Martin Roetteler, Nathan Wiebe, and Giovanni De Micheli (2017). Logic synthesis for quantum computing. arXi vpreprint arXiv:1706.02721.
Search in Google Scholar Back to article
Dmitri Maslov (2005). Reversible logic synthesis benchmarks page. https://reversiblebenchmarks.github.io/.
Search in Google Scholar Back to article
Barry C Sanders (2025). Superconducting quantum computing beyond 100 qubits. Physics, 18:45.
Search in Google Scholar Back to article

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

Abstract

Paradigm

My account