量子有限自动机等价性判定研究
|
摘要
量子计算是一门交叉于数学、物理与计算机科学的前沿学科,具有令人期待的发展前景.量子计算的研究主要分为对量子计算模型、量子计算复杂性和量子算法的研究.目前,广泛引起学者兴趣的量子计算模型主要有量子图灵机(quantum Turing machines)、量子电路(quantum circuit)和量子有限自动机(quantum finite automata)特别地,量子有限自动机可被看作是基于量子力学原理的最为简单的计算模型.目前,有多种不同的量子有限自动机被学者提出,这些量子有限自动机在更好地理解量子计算方面扮演着不可或缺的角色.
在经典计算领域,有限自动机等价性判定是一个基本且重要的问题,它实质上是对有限自动机的分类问题.基于这种观点,对各种量子有限自动机进行分类在量子计算研究中有同等的地位.本文主要研究两种类型的量子有限自动机等价性问题,主要有以下工作：
·研究了测量多次的单向量子有限自动机(MM-1QFA)等价性问题,从MM-1QFA的标准字函数出发,构造了另一个与之等价的字函数.通过这个字函数,证明了定义在相同字母表上的两个MM-1QFAs等价当且仅当它们是n2/1+n2/2-1-等价,中n1和n2是所讨论的两个MM-1QFAs的状态数目；
·研究了多字符量子有限自动机(multi-letter QFA)的等价性问题.改进了现有的结论,即：将多字符量子有限自动机等价判定的上界(n1+n2)4+k-1(在字母表为∑={σ}的情形)二次方优地改进到(n1+n2)2+k-1；然后讨论了在字母表为一般情形下(即∑={σ1,σ2,…,σm},2≤m<∞),多字符量子有限自动机等价问题,证明了存在一个正整数z,使得两个多字符量子有限自动机等价当且仅当它们满足z-等价.
Quantum computing is a research field at the current frontiers of computing, which halfway between mathematics, physics and computer science. Quantum fi-nite automata can be viewed as the simplest theoretical models based on quantum mechanism. The aim of studing quantum finite automata is to explore the power of quantum computation and the characterizations of quantum computation fully. Thus far, variant quantum finite automata have been proposed. Studying of such quantum finite automata pay an indispensable role in further understanding quan-tum computation. In the theory of classical computation, determining the equiva-lence of finite automata is a foundational and important issue. In essentialness, it is concerned with the classification of finite automata. Base on this point of view, the classification of various kinds of quantum finite automata takes on the same position. Concerning these,we make the following contribution.
●Starting from the standard word function of MM-1QFAs, we construct a new word function which equivalent to the standard one, then we show that two MM-1QFAs over the same input alphabet are equivalent if and only if they are n12+n22-1-equivalent, where n1 and n2 are the numbers of states of the two MM-1QFAs, respectively;
●We then investigated the equivalence issue of multi-letter quantum finite au-tomata (multi-letter QFA). To be specific, in the case that the input alphabet has one element, i.e.,∑={σ}, we show that two multi-letter QFAs are equiv-alent if and only if they are (n1+n2)2+κ-1-equivalent; Then, we show that there exists an integer z such that two multi-letter QFAs are equivalent if and only if they are z-equivalent.
在经典计算领域,有限自动机等价性判定是一个基本且重要的问题,它实质上是对有限自动机的分类问题.基于这种观点,对各种量子有限自动机进行分类在量子计算研究中有同等的地位.本文主要研究两种类型的量子有限自动机等价性问题,主要有以下工作：
·研究了测量多次的单向量子有限自动机(MM-1QFA)等价性问题,从MM-1QFA的标准字函数出发,构造了另一个与之等价的字函数.通过这个字函数,证明了定义在相同字母表上的两个MM-1QFAs等价当且仅当它们是n2/1+n2/2-1-等价,中n1和n2是所讨论的两个MM-1QFAs的状态数目；
·研究了多字符量子有限自动机(multi-letter QFA)的等价性问题.改进了现有的结论,即：将多字符量子有限自动机等价判定的上界(n1+n2)4+k-1(在字母表为∑={σ}的情形)二次方优地改进到(n1+n2)2+k-1；然后讨论了在字母表为一般情形下(即∑={σ1,σ2,…,σm},2≤m<∞),多字符量子有限自动机等价问题,证明了存在一个正整数z,使得两个多字符量子有限自动机等价当且仅当它们满足z-等价.
Quantum computing is a research field at the current frontiers of computing, which halfway between mathematics, physics and computer science. Quantum fi-nite automata can be viewed as the simplest theoretical models based on quantum mechanism. The aim of studing quantum finite automata is to explore the power of quantum computation and the characterizations of quantum computation fully. Thus far, variant quantum finite automata have been proposed. Studying of such quantum finite automata pay an indispensable role in further understanding quan-tum computation. In the theory of classical computation, determining the equiva-lence of finite automata is a foundational and important issue. In essentialness, it is concerned with the classification of finite automata. Base on this point of view, the classification of various kinds of quantum finite automata takes on the same position. Concerning these,we make the following contribution.
●Starting from the standard word function of MM-1QFAs, we construct a new word function which equivalent to the standard one, then we show that two MM-1QFAs over the same input alphabet are equivalent if and only if they are n12+n22-1-equivalent, where n1 and n2 are the numbers of states of the two MM-1QFAs, respectively;
●We then investigated the equivalence issue of multi-letter quantum finite au-tomata (multi-letter QFA). To be specific, in the case that the input alphabet has one element, i.e.,∑={σ}, we show that two multi-letter QFAs are equiv-alent if and only if they are (n1+n2)2+κ-1-equivalent; Then, we show that there exists an integer z such that two multi-letter QFAs are equivalent if and only if they are z-equivalent.
引文
[1]E. Bernstein, U. Vazirani. Quantum Complexity theory. SIAM Journal on Computing, 26(5):1411-1473,1997.
[2]D. Deutsch. Quantum computational networks. Proceedings of the Royal Society of London. Volume A425 (1989),73-90.
[3]A. C. Yao. Quantum circuit complexity. In Proceedings of the 34th IEEE Symposium on Foundations of Computer Science (FOCS).1993, pp.352-361.
[4]C. Moore, J. P. Crutchfield. Quantum automata and quantum grammars. Theoretical Computer Science 237,2000,275-306.
[5]A. Kondacs, J. Watrous. On the power of quantum finite state automata. In Proceed-ings of the 38th Annual Symposium on Foundations of Computer Science (FOCS), 1997,66-75.
[6]H. Barendregt, E. Barendsen. Introduction to Lambda Calculus, ftp:// ftp.cs.kun.nl/pub/CompMath.Found/lambda.pdf
[7]A. Church. An unsolvable problem of elementary number theory. American Journal of Mathematics,58 (1936), pp.345-363.
[8]A. M. Turing. On computable numbers, with an application to the Entscheidungs-problem. Proceedings of the London Mathematical Society,42 (1936), pp.230-265.
[9]A. M. Turing. Computability and λ-Definability. Journal of Symbolic Logic.2 (1937), pp.153-163.
[10]Feynman R. P. Simulting physics with computers. Journal of Statistical Physics,1982, 21 (6-7), pp.467-488.
[11]Ji Zhengfeng. Quantum entanglement and quantum distinguishability. Ph.D disserta-tion, Tsinghua University,2007.
[12]D. Deutsh. Quantum theory, the Church-Turing principle and the universalquantum computer. Proceedings of the Royal Society London A,400:1985, pp.97-117.
[13]D. eutsch. Quantum computational networks. Proceedings of the Royal Society of London A,425:1989,pp.73-90.
[14]R. Raussendorf, H. J. Briegel. A one-way quantum computer. Physical Review Letters, 2001,86 (22), pp.5188-5191.
[15]R. Raussendorf, D. E. Browne, H. J. Briegel. Measurement-based quantum com-putation on cluster states. Physcial Review A (Atomic, Molecular, and Optical Physics),2003,68(2):022312.
[16]C. Moore, J. P. Crutchfield. Quantum automata and quantum grammars, Theoretical Computer Science,237(2000),pp.275-306.
[17]A. Kondacs, J. Watrous. On the power of finite state automata. Proceedings of the 38th IEEE Annual Symposium on Foundations of Computer Science (FOCS),1997, pp.66-75.
[18]P. W. Shor. Algorithms for quantum computation:Discrete Log and Factoring. Pro-ceedings of International Journal of Theoretical Physics, Los Alamitos, California: IEEE Computer Society Press,1994, pp.124-133.
[19]L. K. Grover. A fast quantum mechanical algorithm for database search. Proceedings of 28th Annual ACM Symposium on Theory of Computing (STOC),1996, pp.212-219.
[20]L. K. Grover. Quantum mechanics helps in searching for a needle in a haystack. Physical Review Letters,1997,79(2), pp.325-328.
[21]D. Aharonov, A. Ambainis et al. Quantum walks on graphs. Proceedings of the 33th ACM Symposium on theory of Computing(STOC). ACM press,2001, pp.50-59.
[22]A. Ambainis. Quantum walk algorithm for element distinctness, Proceedings of the 15th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, New York,2004. pp.22-31.
[23]E. Bernstein, U. Vazirani. Quantum complexity theory. Proceedings of 25th Annual ACM Symposium on Theory of Computing(STOC),1993,pp.11-20.
[24]J. Gruska. Quantum computing. McGraw-Hill,London,1999.
[25]M.O. Rabin, D. Scott. Finite Automata and Their Decision Problems, IBM Jour-nal.april,1959, pp.114-125.
[26]J. E. Hopcroft, J. D. Ullman. Introduction to automata theory, languages, and com-putation, Addision-Wesley, New York,1979.
[27]A. Brodsky, N. Pippenger. Characterizations of 1-way quantum finite automata. SIAM Journal on computing,31,2002, pp.1456-1478.
[28]A. Ambainis, R. Freivalds. One-way quantum finite automata:strengths, weakness and generalizations. Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS),1998, pp.332-341.
[29]A. Bertoni, C. Mereghetti et al. Quantum computing:1-way quantum automata. Pro-ceedings of the 9th International conference on developments in language theory (DLT'2003).volume 2710 of Lecture Notes in Computer Science,springer,2003, pp.1-20.
[30]C. Mereghetti, B. Palano. Quantum finite automata with control language. Theoretical Informatics and Applications,40(2),2006, pp.315-332.
[31]Lvzhou Li, Daowen Qiu. Determining the equivalence for one-way quantum finite automata. Theoretical Computer Science 403 (2008),42-51.
[32]Daowen Qiu, Sheng Yu. Hierarchy and equivalence of multi-letter quantum finite automata. Theoretical Computer Science 410 (2009),30006-3017.
[33]Lvzhou Li, Daowen Qiu. Determination of equivalence between quantum sequential machines, Theoretical Computer Science 358 (2006) 65-74.
[34]J. Gruska. Descriptional complexity issue in quantum computing, Journal of Au-tomata,Languages and combinatorics 5(3),2000,pp.191-218.
[35]J. W. Carlyle, Reduced forms for stochastic sequential machines, Journal of Mathe-matical Analysis and Applications,7(1963) 167-175.
[36]A. Belovs, A. Rosmanis,J. Smotrovs. Multi-letter reversible and quantum finite au-tomata, Proceedings of the 13th International Conference on Developments in Lan-guage Theory, DLT'2007, Harrachov, Czech Republic, Lecture Notes in Computer Science, vol.4588, Springer, Berlin,2007, pp.60-71.
[37]S. Lang, Algebra, Springer-Verlag, New York,2002.
[38]N. Jacobson, Lectures in Abstract Algebra,vol.Ⅱ, Springer-Verlag, New York,1953.
[39]R. A. Horn, C. R. Johnson. Matrix Analysis. Cambridge university press, Cambridge, 1986.
[40]M. A. Nielsen, I. L. Chuang. Quantum computation and quantum information, Cam-bridge university press, Cambridge,2002.
[41]E. L. Post. Finite combinatory processes-formulation, Journal of Symbolic Logic.1(3), 1936, pp.103-105.
[42]J. E. Hopcroft, J. D. Ullman. Introduction to automata theory, languages, and com-putation, Addision-Wesley, New York,1979.
[43]M. A. Arbib. Theories of abstract automata, Prentice-Hall, Englewood cliffs,1969.
[44]T. L. Booth. Sequential machines and automata theory, J.Wiley, New York,1967.
[45]S. Eilenberg. Automata, Languages, and Machines, vol.A, Academic Press, New York,1974.
[46]C. H. Papadimitriou. Computational complexity, Addison Wesley,1994.
[47]A. Paz. Introduction to probabilistic automata, Academic Press, New York,1971.
[48]Tianrong Lin. Discussion of the equivalence between multi-letter quantum finite au-tomata, submitted to Acta of fujian normal university.
[2]D. Deutsch. Quantum computational networks. Proceedings of the Royal Society of London. Volume A425 (1989),73-90.
[3]A. C. Yao. Quantum circuit complexity. In Proceedings of the 34th IEEE Symposium on Foundations of Computer Science (FOCS).1993, pp.352-361.
[4]C. Moore, J. P. Crutchfield. Quantum automata and quantum grammars. Theoretical Computer Science 237,2000,275-306.
[5]A. Kondacs, J. Watrous. On the power of quantum finite state automata. In Proceed-ings of the 38th Annual Symposium on Foundations of Computer Science (FOCS), 1997,66-75.
[6]H. Barendregt, E. Barendsen. Introduction to Lambda Calculus, ftp:// ftp.cs.kun.nl/pub/CompMath.Found/lambda.pdf
[7]A. Church. An unsolvable problem of elementary number theory. American Journal of Mathematics,58 (1936), pp.345-363.
[8]A. M. Turing. On computable numbers, with an application to the Entscheidungs-problem. Proceedings of the London Mathematical Society,42 (1936), pp.230-265.
[9]A. M. Turing. Computability and λ-Definability. Journal of Symbolic Logic.2 (1937), pp.153-163.
[10]Feynman R. P. Simulting physics with computers. Journal of Statistical Physics,1982, 21 (6-7), pp.467-488.
[11]Ji Zhengfeng. Quantum entanglement and quantum distinguishability. Ph.D disserta-tion, Tsinghua University,2007.
[12]D. Deutsh. Quantum theory, the Church-Turing principle and the universalquantum computer. Proceedings of the Royal Society London A,400:1985, pp.97-117.
[13]D. eutsch. Quantum computational networks. Proceedings of the Royal Society of London A,425:1989,pp.73-90.
[14]R. Raussendorf, H. J. Briegel. A one-way quantum computer. Physical Review Letters, 2001,86 (22), pp.5188-5191.
[15]R. Raussendorf, D. E. Browne, H. J. Briegel. Measurement-based quantum com-putation on cluster states. Physcial Review A (Atomic, Molecular, and Optical Physics),2003,68(2):022312.
[16]C. Moore, J. P. Crutchfield. Quantum automata and quantum grammars, Theoretical Computer Science,237(2000),pp.275-306.
[17]A. Kondacs, J. Watrous. On the power of finite state automata. Proceedings of the 38th IEEE Annual Symposium on Foundations of Computer Science (FOCS),1997, pp.66-75.
[18]P. W. Shor. Algorithms for quantum computation:Discrete Log and Factoring. Pro-ceedings of International Journal of Theoretical Physics, Los Alamitos, California: IEEE Computer Society Press,1994, pp.124-133.
[19]L. K. Grover. A fast quantum mechanical algorithm for database search. Proceedings of 28th Annual ACM Symposium on Theory of Computing (STOC),1996, pp.212-219.
[20]L. K. Grover. Quantum mechanics helps in searching for a needle in a haystack. Physical Review Letters,1997,79(2), pp.325-328.
[21]D. Aharonov, A. Ambainis et al. Quantum walks on graphs. Proceedings of the 33th ACM Symposium on theory of Computing(STOC). ACM press,2001, pp.50-59.
[22]A. Ambainis. Quantum walk algorithm for element distinctness, Proceedings of the 15th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, New York,2004. pp.22-31.
[23]E. Bernstein, U. Vazirani. Quantum complexity theory. Proceedings of 25th Annual ACM Symposium on Theory of Computing(STOC),1993,pp.11-20.
[24]J. Gruska. Quantum computing. McGraw-Hill,London,1999.
[25]M.O. Rabin, D. Scott. Finite Automata and Their Decision Problems, IBM Jour-nal.april,1959, pp.114-125.
[26]J. E. Hopcroft, J. D. Ullman. Introduction to automata theory, languages, and com-putation, Addision-Wesley, New York,1979.
[27]A. Brodsky, N. Pippenger. Characterizations of 1-way quantum finite automata. SIAM Journal on computing,31,2002, pp.1456-1478.
[28]A. Ambainis, R. Freivalds. One-way quantum finite automata:strengths, weakness and generalizations. Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS),1998, pp.332-341.
[29]A. Bertoni, C. Mereghetti et al. Quantum computing:1-way quantum automata. Pro-ceedings of the 9th International conference on developments in language theory (DLT'2003).volume 2710 of Lecture Notes in Computer Science,springer,2003, pp.1-20.
[30]C. Mereghetti, B. Palano. Quantum finite automata with control language. Theoretical Informatics and Applications,40(2),2006, pp.315-332.
[31]Lvzhou Li, Daowen Qiu. Determining the equivalence for one-way quantum finite automata. Theoretical Computer Science 403 (2008),42-51.
[32]Daowen Qiu, Sheng Yu. Hierarchy and equivalence of multi-letter quantum finite automata. Theoretical Computer Science 410 (2009),30006-3017.
[33]Lvzhou Li, Daowen Qiu. Determination of equivalence between quantum sequential machines, Theoretical Computer Science 358 (2006) 65-74.
[34]J. Gruska. Descriptional complexity issue in quantum computing, Journal of Au-tomata,Languages and combinatorics 5(3),2000,pp.191-218.
[35]J. W. Carlyle, Reduced forms for stochastic sequential machines, Journal of Mathe-matical Analysis and Applications,7(1963) 167-175.
[36]A. Belovs, A. Rosmanis,J. Smotrovs. Multi-letter reversible and quantum finite au-tomata, Proceedings of the 13th International Conference on Developments in Lan-guage Theory, DLT'2007, Harrachov, Czech Republic, Lecture Notes in Computer Science, vol.4588, Springer, Berlin,2007, pp.60-71.
[37]S. Lang, Algebra, Springer-Verlag, New York,2002.
[38]N. Jacobson, Lectures in Abstract Algebra,vol.Ⅱ, Springer-Verlag, New York,1953.
[39]R. A. Horn, C. R. Johnson. Matrix Analysis. Cambridge university press, Cambridge, 1986.
[40]M. A. Nielsen, I. L. Chuang. Quantum computation and quantum information, Cam-bridge university press, Cambridge,2002.
[41]E. L. Post. Finite combinatory processes-formulation, Journal of Symbolic Logic.1(3), 1936, pp.103-105.
[42]J. E. Hopcroft, J. D. Ullman. Introduction to automata theory, languages, and com-putation, Addision-Wesley, New York,1979.
[43]M. A. Arbib. Theories of abstract automata, Prentice-Hall, Englewood cliffs,1969.
[44]T. L. Booth. Sequential machines and automata theory, J.Wiley, New York,1967.
[45]S. Eilenberg. Automata, Languages, and Machines, vol.A, Academic Press, New York,1974.
[46]C. H. Papadimitriou. Computational complexity, Addison Wesley,1994.
[47]A. Paz. Introduction to probabilistic automata, Academic Press, New York,1971.
[48]Tianrong Lin. Discussion of the equivalence between multi-letter quantum finite au-tomata, submitted to Acta of fujian normal university.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |