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

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

doi:10.2478/qic-2025-0003

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.

References

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.
Search in Google Scholar Back to article
R.P. Feynman (1982) “Simulating physics with computers”. International Journal of Theoretical Physics, 21, 467–488.
Search in Google Scholar Back to article
D.S. Abrams, and S. Lloyd (1997) “Simulation of many-body Fermi systems on a universal quantum computer”. Physical Review Letters, 79, 2586.
Search in Google Scholar Back to article
A. Aspuru-Guzik, A.D. Dutoi, P.J. Love and M. Head-Gordon (2005) “Simulated quantum computation of molecular energies”. Science, 309, 1704–1707.
Search in Google Scholar Back to article
T.D. Ladd et al. (2010) “Quantum computers”. Nature, 464, 45–53.
Search in Google Scholar Back to article
D.W. Lu et al. (2017) “Enhancing quantum control by bootstrapping a quantum processor of 12 qubits”. npj Quantum Information, 3, 45.
Search in Google Scholar Back to article
J.M. Gambetta, J.M. Chow and M. Steffen (2017) “Building logical qubits in a superconducting quantum computing system”. npj Quantum Information, 3, 2.
Search in Google Scholar Back to article
C. Figgatt et al. (2017) “Complete 3-qubit Grover search on a programmable quantum computer”. Nature Communications, 8, 1918.
Search in Google Scholar Back to article
T.F. Watson et al. (2018) “A programmable two-qubit quantum processor in silicon”. Nature, 555, 633–637.
Search in Google Scholar Back to article
X. Qiang et al. (2018) “Large-scale silicon quantum photonics implementing arbitrary two-qubit processing”. Nature Photonics, 12, 534–539.
Search in Google Scholar Back to article
S. Debnath et al. (2016) “Demonstration of a small programmable quantum computer with atomic qubits”. Nature, 536, 63–66.
Search in Google Scholar Back to article
L.M.K. Vandersypen et al. (2001) “Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance”. Nature, 414, 883–887.
Search in Google Scholar Back to article
P. Walther et al. (2005) “Experimental one-way quantum computing”. Nature, 434, 169–176.
Search in Google Scholar Back to article
X.D. Cai, et al. (2013) “Experimental quantum computing to solve systems of linear equations”. Physical Review Letters, 110, 230501.
Search in Google Scholar Back to article
Z. Li, X. Liu, N. Xu, and J. Du (2015) “Experimental realization of a quantum support vector machine”. Physical Review Letters, 114, 140504.
Search in Google Scholar Back to article
H. Wang, et al. (2017) “High-efficiency multiphoton boson sampling”. Nature Photonics, 11, 361–365.
Search in Google Scholar Back to article
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.009
Search in Google Scholar Back to article
K. Culik II and J. Kari (1993) “Image compression using weighted finite automata”. Computer Graphics, 17, 305–313.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
C. Moore and J.P. Crutchfield (2000) “Quantum automata and quantum grammars”. Theoretical Computer Science, 237, 275–306.
Search in Google Scholar Back to article
A. Ambainis (2016) “Superlinear advantage for exact quantum algorithms”. SIAM Journal on Computing, 45, 617–631.
Search in Google Scholar Back to article
M. Lukac and M. Perkowski (2008) “Quantum finite state machines as sequential quantum circuits.” Proceeding of ISMVL 2009, 160–165.
Search in Google Scholar Back to article
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-x
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Nondeterministic finite automaton - Wikipedia
Search in Google Scholar Back to article
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.133009
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
M. Perkowski (2007, May) “Quantum robots. Now or never?” in Invited Talk at the 5th National Conference on Informatics. Gdansk, Poland.
Search in Google Scholar Back to article
A. Al-Rabadi, M. Perkowski, L. Casperson and X. Song (2002) “Multiple-valued quantum logic”. Quantum, 10, 2.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article

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

Abstract

Paradigm

My account