An overview of quantum computation models: quantum automata

Abstract

Quantum automata, as theoretical models of quantum computers, include quantum finite automata (QFA), quantum sequential machines (QSM), quantum pushdown automata (QPDA), quantum Turing machines (QTM), quantum cellular automata (QCA), and the others, for example, automata theory based on quantum logic (orthomodular lattice-valued automata). In this paper, we try to outline a basic progress in the research on these models, focusing on QFA, QSM, QPDA, QTM, and orthomodular lattice-valued automata. Also, other models closely relative to them are mentioned. In particular, based on the existing results in the literature, we finally address a number of problems to be studied in future.

References

1. Gruska J QuantumComputingLondonMcGraw-Hill 1999
2. Nielsen M A Chuang I L Quantum Computation and QuantumInformationCambridgeCambridge University Press 2000
3. Bennett C Logicalreversibility of computationIBM Journalof Research and Development 1973 17525532
4. Benioff P Thecomputer as a physical system: a microscopic quantum mechanical Hamiltonianmodel of computers as represented by Turing machinesJournal of Statistical Physics 1980 22563591. doi:10.1007/BF01011339
5. Feynman R P Simulatingphysics with computersInternational Journalof Theoretical Physics 1982 21467488. doi:10.1007/BF02650179
6. Deutsch D Quantumtheory, the Church-Turing principle and the universal quantum computerProceedings of the Royal Society of London A 1985 40097117
7. Yao A C Quantumcircuit complexityIn: Proceedings of the34th IEEE Symposium on Foundations of Computer scienceIEEE Computer Society Press 1993 352361
8. Shor P W Algorithmfor quantum computation: Discrete logarithms and factoringIn: Proceedings of the37th IEEE Annuual Symposiumon Foundations of Computer scienceIEEE Computer Society Press 1994 124134
9. Grover L A fastquantum mechanical algorithms for datdbase searchIn: Proceedings of the 28th Annual ACM Symposium on the Theory of ComputingNew YorkACM 1996 212219
10. Hopcroft J E Ullman J D Introduction to Automata Theory,Languages, and ComputationNew YorkAddision-Wesley 1979
11. Moore C Crutchfield J P Quantum automata and quantumgrammarsTheoretical Computer Science 2000 237275306Also see arXiv: quant-ph/9707031,1997. doi: 10.1016/S0304‐3975(98)00191‐1
12. Kondacs A Watrous J On the power of finite stateautomataIn: Proceedings of the 38th IEEEAnnual Symposium on Foundations of Computer ScienceIEEE Computer Society Press 1997 6675
13. Ambainis A Freivalds R One-way quantum finite automata:strengths, weaknesses and generalizationsIn: Proceedings of the 39th Annual Symposium on Foundations of ComputerSciencePalo Alfo, CaliforniaIEEE Computer Society Press 1998 332341also see arXiv:quant-ph/9802062, 1998
14. Nayak A Optimallower bounds for quantum automata and random access codesIn: Proceedings of the 40th Annual Symposium on Foundationsof Computer ScienceIEEE Computer Society 1999 124133
15. Ambainis A Nayak A Ta-Shma A et al.Dense quantum coding and quantum automataJournal of the ACM 2002 49(4)496511. doi:10.1145/581771.581773
16. Ambainis A Beaudry M Golovkins M et al.Algebraic results on quantum automataTheory of Computing Systems 2006 391654188. doi:10.1007/s00224‐005‐1263‐x
17. Amano M Iwama K Undecidability on quantum finiteautomataIn: Proceedings of the 31st AnnualACM Symposium on Theory of ComputingAtlanta, GeorgiaACM Computer SocietyPress 1999 368375
18. Ambainis A Watrous J Two-way finite automata withquantum and classical statesTheoreticalComputer Science 2002 287299311. doi:10.1016/S0304‐3975(02)00138‐X
19. Bertoni A Carpentieri M Analogies and differences betweenquantum and stochastic automataTheoreticalComputer Science 2001 2626981. doi:10.1016/S0304‐3975(00)00154‐7
20. Bertoni A Carpentieri M Regular Languages acceptedby quantum automataInformation and Computation 2001 165174182. doi:10.1006/inco.2000.2911
21. Blondel V D Jeandel E Koiran P et al.Decidable and undecidable problems about quantumautomataSIAM Journal on Computing 2005 34(6)14641473. doi:10.1137/S0097539703425861
22. Bertoni A Mereghetti C Palano B Quantum computing: 1-way quantum automataIn: Proceedings of the 9th International Conference on Developments inLanguage Theory (DLT'2003), Lecture Notes in Computer Science 2003 2710120
23. Brodsky A Pippenger N Characterizations of 1-wayquantum finite automataSIAM Journal onComputing 2002 3114561478also seequant-ph/9903014,1999. doi: 10.1137/S0097539799353443
24. Ambainis A Kikusts A Valdats M On the class of languages recognizable by 1-way quantumfinite automataIn: Proceedings of the 18thAnnual Symposium on Theoretical Aspects of Computer Science, LectureNotes in Computer Science 2001 2010305316
25. Qiu D W Characterizationsof quantum automataJournal of Software 2003 14(1)915 (in Chinese)
26. Qiu D W Ying M S Characterizations of quantumautomataTheoretical Computer Science 2004 312479489. doi:10.1016/j.tcs.2003.08.007
27. Qiu D W Someobservations on two-way finite automata with quantum and classicalstatessee quant-ph/0701187 2007
28. Li L Z Qiu D W Determining the equivalencefor one-way quantum finite automataSee quant-ph/0703087v2,2007 Theoretical Computer Science (in press)
29. Gudder S QuantumcomputersInternational Journal of TheoreticalPhysics 2000 3921512177. doi:10.1023/A:1003692611402
30. Qiu D W Characterizationof sequential quantum machinesInternationalJournal of Theoretical Physics 2002 41811822. doi:10.1023/A:1015731405826
31. Li L Z Qiu D W Determination of equivalencebetween quantum sequential machinesTheoreticalComputer Science 2006 3586574. doi:10.1016/j.tcs.2006.03.001
32. Golovkins M Quantumpushdown automataIn: Proceedings of the27th Conference on Current Trends in Theory and Practice of Informatics.Lecture Notes in Computer Science 2000 1963336346
33. Nakanishi M Onthe power of one-sided error quantum pushdown automata with classicalstack operationsIn: Proceedings of the10th Annual International Computing and Combinatorics Conference (COCOON2004). Lecture Notes in Computer Science 2004 3106179187
34. Bernstein E Vazirani U Quantum complexity theorySIAM Journal on Computing 1997 26(5)14111473. doi:10.1137/S0097539796300921
35. Nishimura H Ozawa M Computational complexity ofuniform quantum circuit families and quantum Turing machinesTheoretical Computer Science 2002 276147181. doi:10.1016/S0304‐3975(01)00111‐6
36. Watrous J Space-boundedquantum complexityJournal of Computer andSystem Sciences 1999 59(2)281326. doi:10.1006/jcss.1999.1655
37. Hirvensalo M Onquantum computationPhD thesis Turku Centerfor Computer Science 1997
38. Qiu D W Simulationsof quantum Turing machines by quantum multi-stack machinesIn: Computability in Europe (CIE2008), Athens, Greece,June 15– 20, 2008also see arXiv: quant-ph/0501176 2005
39. Müller M Stronglyuniversal quantum Turing machines and invariance of Kolmogorov complexityIEEE Transactions on InformationTheory 2008 54(2)763780. doi:10.1109/TIT.2007.913263
40. Watrous J Onone-dimensional cellular automataIn: Proceedingsof the 36th IEEE Annual Symposium on Foundations of Computer Science 1995 528537
41. Dürr C Santha M A decision procedure for unitarylinear quantum cellular automataSIAM Journalon Computing 2002 31(4)10761089. doi:10.1137/S0097539797327702
42. Ying M S Automatatheory based on quantum logic IInternationalJournal of Theoretical Physics 2000 39981991
43. Ying M S Automatatheory based on quantum logic IIInternationalJournal of Theoretical Physics 2000 3925452557. doi:10.1023/A:1026453524064
44. Qiu D W Automataand grammar theory based on quantum logicJournal of Software 2003 14(1)2327(in Chinese)
45. Qiu D W Automatatheory based on quantum logic: Some characterizationsInformation and Compututation 2004 190179195. doi:10.1016/j.ic.2003.11.003
46. Lu R Q Zheng H Lattices of quantum automataInternational Journal of Theoretical Physics 2003 4214251449. doi:10.1023/A:1025775827938
47. Cheng W Wang J Grammar theory based on quantumlogicInternational Journal of TheoreticalPhysics 2003 4216771691. doi:10.1023/A:1026135502749
48. Ying M S Atheory of computation based on quantum logic (I)Theoretical Computer Science 2005 344134207. doi:10.1016/j.tcs.2005.04.001
49. Qiu D W Automatatheory based on quantum logic: reversibilities and pushdown automataTheoretical Computer Science 2007 3863856. doi:10.1016/j.tcs.2007.05.026
50. Qiu D W Noteson automata theory based on quantum logicScience in China (Series F: Information Sciences) 2007 50(2)154169. doi:10.1007/s11432‐007‐0020‐y
51. Rabin M O ProbabilisticautomataInformation and Control 1963 6230244. doi:10.1016/S0019‐9958(63)90290‐0
52. Paz A Introductionto Probabilistic AutomataNew YorkAcademic Press 1971
53. Li L Z Qiu D W A polynomial-time algorithmfor the equivalence between quantum sequential machinessee arXiv: quant-ph/0604085 2006
54. Tonder A V Alambda calculus for quantum computationSIAM Journal on Computing 2004 33(5)11091135. doi:10.1137/S0097539703432165
55. Gudder S Quantumautomata: An overviewInternational Journalof Theoretical Physics 1999 3822612282. doi:10.1023/A:1026663432352
56. Koshiba T Polynomial-timealgorithms for the equivalence for one-way quantum finite automataIn: Proceedings of the 12th International Symposiumon Algorithms and Computation (ISAAC'2001), Christchurch, New Zealand,Lecture Notes in Computer Science 2001 2223268278
57. Ambainis A Bonner R Freivalds R et al.Probabilities to accept languages by quantum finiteautomataIn: Proceedings of COCOON'99, LectureNotes in Computer Science 1999 1627174183
58. Ambainisa A Kikusts A Exact results for acceptingprobabilities of quantum automataTheoreticalComputer Science 2003 295325. doi:10.1016/S0304‐3975(02)00393‐6
59. Kikusts A A small1-way quantum finite automatonsee arXiv: quant-ph/9810065 1998
60. Ablayev F Gainutdinova A On the Lower Bounds for One-WayQuantum AutomataIn: Proceedings of 25thInternational Symposium on Mathematical Foundations of Computer Science(MFCS'2000), Lecture Notes in Computer Science 2000 1893132140
61. Bertoni A Mereghetti C Palano B Lower Bounds on the Size of Quantum Automata AcceptingUnary LanguagesIn: Proceedings of 8th ItalianConference on Theoretical Computer Science (ICTCS'2003), Lecture Notesin Computer Science 2003 28418696
62. Bertoni A Mereghetti C Palano B Small size quantum automata recognizing some regular languagesTheoretical Computer Science 2005 340394407. doi:10.1016/j.tcs.2005.03.032
63. Mereghetti C Palano B Upper Bounds on the Size ofOne-Way Quantum Finite AutomataIn: Proceedingsof the 7th Italian Conference on Theoretical Computer Science (ICTCS'2001),Lecture Notes in Computer Science 2001 2202123135
64. Mereghetti C Palano B On the size of one-way quantumfinite automata with periodic behaviorsTheoretical Informatics and Applications 2002 36277291. doi:10.1051/ita:2002014
65. Mereghetti C Palano B Quantum automata for some multiperiodiclanguagesTheoretical Computer Science 2007 387177186
66. Paschen K Quantumfinite automata using ancilla qubitsUniversityof Karlsruhe, Technical Report May 2000
67. Freivalds R Probabilistictwo-way machinesIn: Proceedings of theInternational Symposium on Mathematical Foundations of Computer Science,Lecture Notes in Computer Science 1981 1883345
68. Greenberg A Weiss A A lower bound for probabilisticalgorithms for finite state machinesJournalof Computer and System Sciences 1986 33(1)88105. doi:10.1016/0022‐0000(86)90045‐0
69. Dwork C Stockmeyer L A time-complexity gap for two-wayprobabilistic finite state automataSIAMJournal on Computing 1990 1910111023. doi:10.1137/0219069
70. Kaneps J Freivalds R Running time to recognize nonregularlanguages by 2-way probabilistic automataIn: Proceedings of the 18th International Colloquium on Automata, Languagesand Programming. Lecture Notes in Computer Science 1991 510174185
71. Dwork C Stockmeyer L Finite state verifier I: thepower of interactionJournal of the ACM 1992 39(4)800828. doi:10.1145/146585.146599
72. Birkhoff G von Neumann J The logic of quantum mechanicsAnnals of Mathematics 1936 37823843. doi:10.2307/1968621
73. Pták P Pulmannová S OrthomodularStructures as Quantum LogicsDordrechtKluwer 1991
74. Qiu D W Automatatheory based on complete residuated lattice-valued logicScience in China (Series F: Information Sciences) 2001 44(6)419429
75. Qiu D W Automatatheory based on complete residuated lattice-valued logic (II)Science in China (Series F: Information Sciences) 2002 45(6)442452
76. Ledda A Konig M Paoli F et al.MV-algebras and quantum computationStudia Logica 2006 82245270. doi:10.1007/s11225‐006‐7202‐2
77. Deutsch D Quantumcomputational networksProceedings of theRoyal Society of London Series A 1989 4007390
78. Adleman L DeMarrais J Huang H Quantum computabilitySIAM Journalon Computing 1997 26(5)15241540. doi:10.1137/S0097539795293639
79. Bennett C Bernstein E Brassard G et al.Strengths and weaknesses of quantum computationSIAM Journal on Computing 1997 26(5)15101523. doi:10.1137/S0097539796300933
80. Cleve R AnIntroduction to Quantum Complexity TheoryarXiv: quantph/9906111v1 1999
81. Fortnow L Rogers J Complexity limitations on quantumcomputationJournal of Computer and SystemSciences 1999 59(2)240252. doi:10.1006/jcss.1999.1651
82. Fortnow L Onecomplexity theorists view of quantum computingTheoretical Computer Science 2003 292597610. doi:10.1016/S0304‐3975(01)00377‐2
83. Simon D Onthe power of quantum computationSIAM Journalon Computing 1997 26(5)14741483. doi:10.1137/S0097539796298637
84. Spakowski H Thakur M Tripathi R Quantum and classical complexity classes: Separations,collapses, and closure propertiesInformationand Computation 2005 200(1)134. doi:10.1016/j.ic.2004.10.009
85. Yu S RegularLanguagesIn: Rozenberg GSalomaa AHandbook of Formal LanguagesBerlinSpring-Verlag 1998 41110
86. Nishimura H Yamakami T An application of quantum finiteautomata to interactive proof systemsIn: Proceedings of the 9th International Conference on Implementationand Application of Automata. Lecture Notes in Computer ScienceBerlinSpringer 2004 3317225236