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

Quantum Finite Automaton Using Ternary Rotation Quantum Gates and Chrestenson Family Quantum Gates

Yuchen Huang, Marek Perkowski, Xiaoyu Song, John M. Acken

Author affiliations
  • Yuchen Huang1
  • Marek Perkowski1
  • Xiaoyu Song1
  • John M. Acken1
  1. Department of Electrical and Computer Engineering, Portland State University, Portland, OR, USA

pp. 57-70 · 10.2478/qic-2025-0003

Read PDF View on Reference Global
On this page

Abstract

Quantum automata can solve certain problems with a smaller state space than classical automata. We developed a quantum finite automaton using ternary rotation quantum gates and the Chrestenson family of ternary quantum gates. The main idea of this paper is to show how to combine rotation ternary quantum circuit-based Quantum Finite Automaton and quantum reversible circuit-based Deterministic Finite Automaton to build a more powerful machine. The combined machine can enable more complex language and pattern recognition. The developed quantum finite automaton and resulting combined machine can be used for robotics applications such as language, gesture, and motion recognition.
Open accessCC BY-NC-ND 4.0

Keywords

  • quantum finite automaton
  • ternary
  • quantum gates
  • rotation quantum gates
  • Chrestenson family quantum gates

Suggested citation

Yuchen Huang, Marek Perkowski, Xiaoyu Song, John M. Acken (2025). Quantum Finite Automaton Using Ternary Rotation Quantum Gates and Chrestenson Family Quantum Gates. Quantum Information & Computation, 25(1), 57-70. https://doi.org/10.2478/qic-2025-0003

Download BibTeX

References (34)

  1. P.W. Shor (1994) “Algorithms for quantum computation: Discrete logarithms and factoring”, in Proceedings of 35th Annual Symposium Foundations of Computer Science. Santa Fe, NM: IEEE, 124–134.DOI: 10.1109/SFCS.1994.365700Google Scholar
  2. R.P. Feynman (1982) “Simulating physics with computers”. International Journal of Theoretical Physics, 21, 467–488.DOI: 10.1007/BF02650179Google Scholar
  3. D.S. Abrams, and S. Lloyd (1997) “Simulation of many-body Fermi systems on a universal quantum computer”. Physical Review Letters, 79, 2586.DOI: 10.1103/PhysRevLett.79.2586Google Scholar
  4. A. Aspuru-Guzik, A.D. Dutoi, P.J. Love and M. Head-Gordon (2005) “Simulated quantum computation of molecular energies”. Science, 309, 1704–1707.DOI: 10.1126/science.1113479Google Scholar
  5. T.D. Ladd et al. (2010) “Quantum computers”. Nature, 464, 45–53.DOI: 10.1038/nature08812Google Scholar
  6. D.W. Lu et al. (2017) “Enhancing quantum control by bootstrapping a quantum processor of 12 qubits”. npj Quantum Information, 3, 45.DOI: 10.1038/s41534-017-0045-zGoogle Scholar
  7. J.M. Gambetta, J.M. Chow and M. Steffen (2017) “Building logical qubits in a superconducting quantum computing system”. npj Quantum Information, 3, 2.DOI: 10.1038/s41534-016-0004-0Google Scholar
  8. C. Figgatt et al. (2017) “Complete 3-qubit Grover search on a programmable quantum computer”. Nature Communications, 8, 1918.DOI: 10.1038/s41467-017-01904-7Google Scholar
  9. T.F. Watson et al. (2018) “A programmable two-qubit quantum processor in silicon”. Nature, 555, 633–637.DOI: 10.1038/nature25766Google Scholar
  10. X. Qiang et al. (2018) “Large-scale silicon quantum photonics implementing arbitrary two-qubit processing”. Nature Photonics, 12, 534–539.DOI: 10.1038/s41566-018-0236-yGoogle Scholar
  11. S. Debnath et al. (2016) “Demonstration of a small programmable quantum computer with atomic qubits”. Nature, 536, 63–66.DOI: 10.1038/nature18648Google Scholar
  12. L.M.K. Vandersypen et al. (2001) “Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance”. Nature, 414, 883–887.DOI: 10.1038/414883aGoogle Scholar
  13. P. Walther et al. (2005) “Experimental one-way quantum computing”. Nature, 434, 169–176.DOI: 10.1038/nature03347Google Scholar
  14. X.D. Cai, et al. (2013) “Experimental quantum computing to solve systems of linear equations”. Physical Review Letters, 110, 230501.DOI: 10.1103/PhysRevLett.110.230501Google Scholar
  15. Z. Li, X. Liu, N. Xu, and J. Du (2015) “Experimental realization of a quantum support vector machine”. Physical Review Letters, 114, 140504.DOI: 10.1103/PhysRevLett.114.140504Google Scholar
  16. H. Wang, et al. (2017) “High-efficiency multiphoton boson sampling”. Nature Photonics, 11, 361–365.DOI: 10.1038/nphoton.2017.63Google Scholar
  17. M. Ying (2010) “Quantum computation, quantum theory and AI”. Journal of Artificial Intelligence, 174: 2, 162–176. https://doi.org/10.1016/j.artint.2009.11.009DOI: 10.1016/j.artint.2009.11.009Google Scholar
  18. K. Culik II and J. Kari (1993) “Image compression using weighted finite automata”. Computer Graphics, 17, 305–313.DOI: 10.1016/0097-8493(93)90079-OGoogle Scholar
  19. A. Kondacs and J. Watrous (1997) “On the power of quantum finite state automata”, in Proceedings on 38th Annual Symposium Foundations of Computer Science. IEEE: Miami Beach, FL, 66–75.DOI: 10.1109/SFCS.1997.646094Google Scholar
  20. C. Moore and J.P. Crutchfield (2000) “Quantum automata and quantum grammars”. Theoretical Computer Science, 237, 275–306.DOI: 10.1016/S0304-3975(98)00191-1Google Scholar
  21. A. Ambainis (2016) “Superlinear advantage for exact quantum algorithms”. SIAM Journal on Computing, 45, 617–631.DOI: 10.1137/130939043Google Scholar
  22. M. Lukac and M. Perkowski (2008) “Quantum finite state machines as sequential quantum circuits.” Proceeding of ISMVL 2009, 160–165.Google Scholar
  23. Y. Tian, T. Feng, M. Luo, S. Zheng and Xiaoqi Zhou. (2019) “Experimental demonstration of quantum finite automaton”. Nature Partner Journals, Quantum Information, published in partnership with the University of New South Wales. npj Quantum Information (2019) 5, 56. https://doi.org/10.1038/s41534-019-0163-xDOI: 10.1038/s41534-019-0163-xGoogle Scholar
  24. J.H. Bae, Ch-B. Bae, G.B. Lee, D.H. Kim, M. Perkowski, M.H.A. Khan (2007) Minimization of Ternary and Mixed Binary-Ternary Permutative Quantum Circuits. Report KAIST University, Korea.Google Scholar
  25. Nondeterministic finite automaton - WikipediaGoogle Scholar
  26. Y. Huang, M. Perkowski (2023) “One hot encoding synthesis of quantum automata from flowcharts”. Journal of Quantum Information Science, 13: 3, 156–176. https://doi.org/10.4236/jqis.2023.133009DOI: 10.4236/jqis.2023.133009Google Scholar
  27. J. Gruska, D.W. Qiu and S.G. Zheng (2015) “Potential of quantum finite automata with exact acceptance”. International Journal of Foundations of Computer Science, 26, 381–398.DOI: 10.1142/S0129054115500215Google Scholar
  28. M. Perkowski (2007, May) “Quantum robots. Now or never?” in Invited Talk at the 5th National Conference on Informatics. Gdansk, Poland.Google Scholar
  29. A. Al-Rabadi, M. Perkowski, L. Casperson and X. Song (2002) “Multiple-valued quantum logic”. Quantum, 10, 2.Google Scholar
  30. M. Khan, M. Perkowski and P. Kerntopf (2003) “Multi-output galois field sum of products synthesis with new quantum cascades”, in Proc. 33rd ISMVL, Tokyo, 16–19 May 2003, IEEE.Google Scholar
  31. T. Roy, Z. Li, E. Kapit, and D.I. Schuster (2023) “Two-Qutrit quantum algorithms on a programmable superconducting processor”. Physical Review Applied, 19, 064024.DOI: 10.1103/PhysRevApplied.19.064024Google Scholar
  32. R. Deng, Y. Huang, M. Perkowski (2021) “Quantum motions and emotions for a humanoid robot actor”, in Proceedings of the 2021 IEEE 51st International Symposium on Multiple-Valued Logic, Nur-sultan, May 25–27, 2021, 207–214. https://doi.org/10.1109/ISMVL51352.2021.00043.DOI: 10.1109/ISMVL51352.2021.00043Google Scholar
  33. D. Said (2023) “Quantum computing and machine learning for cybersecurity: Distributed denial of service (DDos) attack detection on smart micro-grid”. Energies, 16: 8, 3572. https://doi.org/10.3390/en16083572.DOI: 10.3390/en16083572Google Scholar
  34. D. Said, M. Bagaa, A. Qukaira and A. Lakhssassi (2024) “Quantum entropy and reinforcement learning for distributed denial of service attack detection in smart grid”. IEEE Access, 12, 129858–129869. https://doi.org/10.1109/ACCESS.2024.3441931.DOI: 10.1109/ACCESS.2024.3441931Google Scholar