Quantum automata and quantum grammars. (English) Zbl 0939.68037
Summary: To study quantum computation, it might be helpful to generalize structures from language and automata theory to the quantum case. To that end, we propose quantum versions of finite-state and push-down automata, and regular and context-free grammars. We find analogs of several classical theorems, including pumping lemmas, closure properties, rational and algebraic generating functions, and Greibach normal form. We also show that there are quantum context-free languages that are not context-free, so \(\text{QCFL}\neq \text{CFL}\).
MSC:
| 68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |
| 81P68 | Quantum computation |
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
| 68Q42 | Grammars and rewriting systems |
References:
| [1] | Adleman, L. M., Molecular computation of solutions to combinatorial problems, Science, 266, 1021-1023 (1994) |
| [2] | P. Benioff, Quantum mechanical Hamiltonian models of Turing machines that dissipate no energy, Phys. Rev. Lett. 48 (1982) 1581-1585 and J. Statist. Phys. 29 (1982) 515-546.; P. Benioff, Quantum mechanical Hamiltonian models of Turing machines that dissipate no energy, Phys. Rev. Lett. 48 (1982) 1581-1585 and J. Statist. Phys. 29 (1982) 515-546. · Zbl 0514.68055 |
| [3] | J. Berstel, Transductions and Context-Free Languages, Teubner Studienbücher, Berlin, 1978.; J. Berstel, Transductions and Context-Free Languages, Teubner Studienbücher, Berlin, 1978. |
| [4] | Blum, L.; Shub, M.; Smale, S., On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bull. Amer. Math. Soc., 21, 1-46 (1989) · Zbl 0681.03020 |
| [5] | R. Bukharaev, On the representability of events in probabilistic automata, Probab. Meth. Cybernet. V Kazan (1967) 7-20 (Russian).; R. Bukharaev, On the representability of events in probabilistic automata, Probab. Meth. Cybernet. V Kazan (1967) 7-20 (Russian). |
| [6] | Cherubini, A.; Citrini, C.; Reghizzi, S. C.; Mandrioli, D., QRT FIFO automata, breadth-first grammars and their relations, Theoret. Comput. Sci., 85, 171-203 (1991) · Zbl 0745.68069 |
| [7] | Cirac, J. I.; Zoller, P., Quantum computations with cold trapped ions, Phys. Rev. Lett., 74, 4091-4094 (1995) |
| [8] | Crutchfield, J. P., The calculi of emergence: computation, dynamics, and induction, Physica D, 75, 11-54 (1994) · Zbl 0860.68046 |
| [9] | Crutchfield, J. P.; Mitchell, M., The evolution of emergent computation, Proc. Natl. Acad. Sci., 92, 10742-10746 (1995) · Zbl 0960.68639 |
| [10] | Deutsch, D., Quantum theory, the Church-Turing principle and the universal quantum computer, Proc. R. Soc. London Ser. A, 400, 97-117 (1985) · Zbl 0900.81019 |
| [11] | C. Dürr, M. Santha, A decision procedure for unitary linear quantum cellular automata, Proc. 37th Symp. on Foundations of Computer Science, 1996, pp. 38-45.; C. Dürr, M. Santha, A decision procedure for unitary linear quantum cellular automata, Proc. 37th Symp. on Foundations of Computer Science, 1996, pp. 38-45. |
| [12] | C.A. Ellis, Probabilistic languages and automata, Ph.D. Thesis, University of Illinois, Urbana, 1969.; C.A. Ellis, Probabilistic languages and automata, Ph.D. Thesis, University of Illinois, Urbana, 1969. |
| [13] | Flajolet, P., Analytic models and ambiguity of context-free languages, Theoret. Comput. Sci., 49, 283-309 (1987) · Zbl 0612.68069 |
| [14] | Gershenfeld, N. A.; Chuang, I. L., Bulk spin-resonance quantum computation, Science, 275, 350-356 (1997) · Zbl 1226.81047 |
| [15] | Giles, R., Reconstruction of gauge potentials from Wilson loops, Phys. Rev. D, 24, 8, 2160-2168 (1981) |
| [16] | Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley: Addison-Wesley New York · Zbl 0196.01701 |
| [17] | A. Kondacs, J. Watrous, On the power of quantum finite state automata, Proc. 38th Symp. on Foundations of Computer Science, 1997, To appear.; A. Kondacs, J. Watrous, On the power of quantum finite state automata, Proc. 38th Symp. on Foundations of Computer Science, 1997, To appear. |
| [18] | W. Kuich, A. Salomaa, Semirings, Automata, Languages, EATCS Monographs on Theoretical Computer Science, vol. 5. Springer, Berlin, 1986.; W. Kuich, A. Salomaa, Semirings, Automata, Languages, EATCS Monographs on Theoretical Computer Science, vol. 5. Springer, Berlin, 1986. · Zbl 0582.68002 |
| [19] | Lloyd, S., A potentially realizable quantum computer, Science, 261, 1569-1571 (1993) |
| [20] | I. Macarie, Closure properties of stochastic languages, University of Rochester Computer Science Technical Report 441, 1993.; I. Macarie, Closure properties of stochastic languages, University of Rochester Computer Science Technical Report 441, 1993. |
| [21] | C. Moore, Unpredictability and undecidability in dynamical systems, Phys. Rev. Lett. 64 (1990) 2354-2357 and Nonlinearity 4 (1991) 199-230.; C. Moore, Unpredictability and undecidability in dynamical systems, Phys. Rev. Lett. 64 (1990) 2354-2357 and Nonlinearity 4 (1991) 199-230. · Zbl 1050.37510 |
| [22] | Moore, C., Dynamical recognizers: real-time language recognition by analog computers, Theoret. Comput. Sci., 201, 99-136 (1998) · Zbl 0902.68098 |
| [23] | Paz, A., Introduction to Probabilistic Automata (1971), Academic Press: Academic Press New York · Zbl 0234.94055 |
| [24] | Rabin, M. O., Probabilistic automata, Inform. Control, 6, 230-245 (1963) · Zbl 0182.33602 |
| [25] | El Rodento Diablo, personal communication.; El Rodento Diablo, personal communication. |
| [26] | Rosenberg, A. L., Real-time definable languages, J. ACM, 14, 645-662 (1967) · Zbl 0153.00902 |
| [27] | Sakakibara, Y.; Brown, M.; Hughey, R.; Mian, I. S.; Sjolander, K.; Underwood, R. C.; Haussler, D., Recent methods for RNA modeling using stochastic context-free grammars, (Crochemore, M.; Gusfield, D., Combinatorial Pattern Matching, 5th Annual Symp. (1994), Springer: Springer Berlin), 289-306 |
| [28] | Searls, D. B., The linguistics of DNA, Am. Scientist, 80, 579-591 (1992) |
| [29] | P.W. Shor, Algorithms for quantum computation: discrete logarithms and factoring, Proc. 35th Symp. on Foundations of Computer Science, 1994, pp. 124-134.; P.W. Shor, Algorithms for quantum computation: discrete logarithms and factoring, Proc. 35th Symp. on Foundations of Computer Science, 1994, pp. 124-134. |
| [30] | P.W. Shor, Fault-tolerant quantum computation, Proc. 37th Symp. on Foundations of Computer Science, 1996, pp. 56-65.; P.W. Shor, Fault-tolerant quantum computation, Proc. 37th Symp. on Foundations of Computer Science, 1996, pp. 56-65. |
| [31] | Siegelmann, H.; Sontag, E. D., Analog computation via neural networks, Theoret. Comput. Sci., 131, 331-360 (1994) · Zbl 0822.68029 |
| [32] | Siegelmann, H.; Sontag, E. D.; Giles, L., The complexity of language recognition by neural networks, (van Leeuwen, J., Algorithms, Software, Architecture (1992), North-Holland: North-Holland Amsterdam), 329-335 |
| [33] | Steane, A. M., Active stabilization, quantum computation, and quantum state synthesis, Phys. Rev. Lett., 78, 2252-2255 (1997) |
| [34] | Townsend, J. S., A Modern Approach to Quantum Mechanics (1992), McGraw-Hill: McGraw-Hill New york |
| [35] | Turakainen, P., On stochastic languages, Inform. Control, 12, 304-313 (1968) · Zbl 0214.02101 |
| [36] | D.R. Upper, Theory and algorithms for hidden Markov models, and generalized hidden Markov models, Ph.D. Thesis, Mathematics Department, University of California, Berkeley, 1997.; D.R. Upper, Theory and algorithms for hidden Markov models, and generalized hidden Markov models, Ph.D. Thesis, Mathematics Department, University of California, Berkeley, 1997. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
