×

Topology, formal languages and quantum information. (English) Zbl 1205.81051

Summary: The paper provides a critical overview of the basic conceptual tools and algorithms of quantum information theory underlying the construction of quantum invariants of links and 3-manifolds as well as of their connections with algorithms and algorithmic complexity questions that arise in geometry and quantum gravity models. Moreover, it argues that such quantum information manipulation tools may allow us to explore much wider fields than mere computation, reaching beyond its boundaries to touch the very roots of the universal structure of formal languages. The paper addresses just a few among the many technical details necessary to pursue the general argument, its main aim being to show how a complex blend of notions coming from formal language theory, finite group theory, and quantum information theory do indeed lead to a novel perspective in the science of languages. The quantum algorithm on which the whole structure discussed is grounded is the quantum automaton recently designed (Marzuoli, Rasetti, Garnerone) to construct an efficient additive approximation of link and 3-manifold topological invariants in the framework of \(\text{SU}(2)\) Chern-Simons-Witten topological quantum field theory at finite values of the coupling constant \(k\). The model of computation adopted in it is the \(q\)-deformed spin network model viewed as a quantum recognizer, where each basic unitary transition function can be efficiently processed by a standard quantum circuit.

MSC:

81P45 Quantum information, communication, networks (quantum-theoretic aspects)
68Q12 Quantum algorithms and complexity in the theory of computing
57M27 Invariants of knots and \(3\)-manifolds (MSC2010)
58K65 Topological invariants on manifolds
68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Guhr T., Müller-Groeling A., Weidenmüller H.A. (1998) Phys. Rep. 299: 189 · doi:10.1016/S0370-1573(97)00088-4
[2] Gutzwiller M.C. (1990) ’Chaos in Classical and Quantum Mechanics’. Springer, New York · Zbl 0727.70029
[3] Montgomery, H. L. (1973) in ’Analytic Number Theory’, Proceedings of the Symposium on Pure Mathematics (Amer. Math. Soc., Providence, RI), Vol. 24, p. 181 · Zbl 0257.10027
[4] Odlyzko, A. M. (1987) Math. Comp. 48, p. 273
[5] Kriecherbauer, T., Marklof, J. and Soshnikov, A. (2001) PNAS, vol. 98 – no. 19, p. 10531
[6] Nielsen M.A., Chuang I.L. (2000) ’Quantum Computation and Quantum Information’. Cambridge University Press, Cambridge · Zbl 1049.81015
[7] Garnerone S., Marzuoli A., Rasetti M. (2007) J. Phys. A: Math. Theor. 40: 3047 · Zbl 1110.81157 · doi:10.1088/1751-8113/40/12/S10
[8] Garnerone S., Marzuoli A., Rasetti M. (2007) Quant. Inform. Comp. 7: 479
[9] Ponzano, G. and Regge, T. (1968) in Bloch, F. et al (Eds.) ’Spectroscopic and Group Theoretical Methods in Physics’, NorthHolland: Amsterdam
[10] Penrose R. (1971) in Bastin, T. (Ed.) ’Quantum Theory and Beyond’. Cambridge University Press, Cambridge · Zbl 0938.82521
[11] Freedman, M.H., Kitaev, A. and Wang, Z. (2002) Commun. Math. Phys. 227, p. 587; Freedman, M.H., Kitaev, A., Larsen, M. and Wang, Z. (2002) Bull. Amer. Math. Soc. 40, p. 31
[12] Jones V.F.R. (1985) Bull. Amer. Math. Soc. 12: 103 · Zbl 0564.57006 · doi:10.1090/S0273-0979-1985-15304-2
[13] Witten E. (1989) Commun. Math. Phys. 121: 351 · Zbl 0667.57005 · doi:10.1007/BF01217730
[14] Garnerone, S., Marzuoli, A. and Rasetti, M. (2009) Adv. Theor. Math. Phys. in press; [arXiv:quant-ph/0703037]
[15] Chomsky, N. (1956) IRE Transactions on Information Theory 2, p. 113
[16] Epstein, D.B.A., Cannon, J.W., Holt, D.F., Levy, S., Patterson, M.S. and Thurston, W. (1992) ’Word processing in groups’, Jones and Bartlett: Boston · Zbl 0764.20017
[17] Rasetti, M. and Marletto, C. (2009) in Licata, I. and Sakaji, A. (Eds.) ’The Nature Description in Quantum Field Theory: Open Problems and Epistemological Perspective’, Springer Verlag: New York · Zbl 1233.81025
[18] Arnowitt, R., Deser, S. and Misner, C.W. (1962) in Witten, L. (Ed.) ’Gravitation: an Introduction to Current Research’, Wiley: New York
[19] Wheeler, J.A. (1968) in DeWitt, C.M. and Wheeler, J.A. (Eds.) ’Battelle Rencontres’ W.A. Benjamin: New York
[20] Weinberg S. (1995) ’The Quantum Theory of Fields’ Vol. 1: Foundations. Cambridge University Press, Cambridge · Zbl 0865.92026
[21] Hartle J.B., Hawking S.W. (1983) Phys. Rev. D 28: 2960 · Zbl 1370.83118 · doi:10.1103/PhysRevD.28.2960
[22] Regge T. (1961) Nuovo Cimento 19: 558 · doi:10.1007/BF02733251
[23] Yang C.N., Mills R. (1954) Phys. Rev. 96: 191 · Zbl 1378.81075 · doi:10.1103/PhysRev.96.191
[24] Jackiw R. (1980) Rev. Mod. Phys. 52: 661 · doi:10.1103/RevModPhys.52.661
[25] Eguchi T., Gilkey P.B., Hanson A.J. (1980) Phys. Rep. 66: 213 · doi:10.1016/0370-1573(80)90130-1
[26] Atiyah, M.F. ’Topological quantum field theories’, (1989) Publ. Math. IHES 68, p. 175 · Zbl 0692.53053
[27] Quinn, F. (1995) in Freed, D.S. et al. (Eds.) ’Geometry and Quantum Field Theory’ Amer. Math. Soc.: Providence, RI · Zbl 0901.18002
[28] Carlip, S. (1998) ’Quantum Gravity in 2 + 1 dimensions’ Cambridge University Press: Cambridge · Zbl 0919.53024
[29] Zanardi, P. and Rasetti, M. (1999) Phys. Lett. A 264, p. 94 ; Pachos, J., Zanardi, P. and Rasetti, M. (2000) Phys. Rev. A 61, p. 010305(R)
[30] Dennis E., Kitaev A.Yu., Landahl A., Preskill J. (2002) J. Math. Phys. 43: 4452 · Zbl 1060.94045 · doi:10.1063/1.1499754
[31] Kitaev, A.Yu. (2003) Annals Phys. 303, p. 2;
[32] Marzuoli, A. and Rasetti, M. (2002) Phys. Lett. A 306, p. 79; Marzuoli, A. and Rasetti, M. (2005) Ann. Phys. 318, p. 345 · Zbl 1162.81328
[33] Biedenharn, L.C. and Louck, J.D. (1981) ’Angular Momentum in Quantum Physics, Theory and Applications’, Encyclopedia of Mathematics and its Applications Vol. 8, Rota, GC. (Ed.), AddisonWesley Publ. Co.: Reading MA Biedenharn, L.C. and Louck, J.D. (1981) ’The RacahWigner Algebra in Quantum Theory’, Encyclopedia of Mathematics and its Applications Vol. 9 Rota, GC. (Ed.), AddisonWesley Publ. Co.: Reading MA · Zbl 0474.00023
[34] Feynman R. (1982) Int. J. Theor. Phys. 21: 467 · doi:10.1007/BF02650179
[35] Battaglia D., Rasetti M. (2003) Phys. Lett. A 313: 8 · Zbl 1024.37050 · doi:10.1016/S0375-9601(03)00679-0
[36] Hopcroft J.E., Ullman J.D. (1979) ’Introduction to Automata Theory, Languages and Computation’. AddisonWesley, Reading MA · Zbl 0426.68001
[37] Moore C., Crutchfield J.P. (2000) Theor. Comput. Sci. 37: 275 · Zbl 0939.68037 · doi:10.1016/S0304-3975(98)00191-1
[38] Kondacs, A., and Watrous, J. (1997) Proc. Ann. Symp. Found. Comput. Sci. 1997, p. 66; Ambainis, A. and Watrous, J. (2002) Theoret. Comput. Sci. 287, p. 299
[39] Kassel C. (1995) ’Quantum Groups’, Graduate Texts in Math. 155. Springer- Verlag, New York · Zbl 0808.17003
[40] Wiesner, K. and Crutchfield, J.P. (2008) Physica D 237, Vol. 9, p. 1173
[41] Kaul R.K. (1994) Commun. Math. Phys. 162: 289 · Zbl 0832.57006 · doi:10.1007/BF02102019
[42] Reshetikhin N., Turaev V.G. (1991) Invent. Math. 103: 547 · Zbl 0725.57007 · doi:10.1007/BF01239527
[43] Kirby R., Melvin P. (1991) Invent. Math. 105: 473 · Zbl 0745.57006 · doi:10.1007/BF01232277
[44] Lickorish W.B.R. (1997) ’Introduction to Knot theory’. Springer, New York · Zbl 0886.57001
[45] Ramadevi P., Govindarajan T.R., Kaul R.K. (1994) Mod. Phys. Lett. A 9: 3205 · Zbl 1015.57500 · doi:10.1142/S0217732394003026
[46] Bordewich M., Freedman M., Lovasz L., Welsh D. (2005) Combinatorics, Probability and Computing 14: 737 · Zbl 1089.68040 · doi:10.1017/S0963548305007005
[47] Birman, J.S. (1974) ’Braids, Links and Mapping Class Groups’ Princeton Univ. Press: Princeton NJ
[48] Garnerone S., Marzuoli A., Rasetti M. (2006) Laser Phys. 16: 1582 · doi:10.1134/S1054660X06110120
[49] Witten E. (1989) Nucl. Phys. B 322: 629 · doi:10.1016/0550-3213(89)90232-0
[50] Chomsky, N. (1971) ’Language and Mind’ Harcourt, Brace & Jovanovich: New York; Chomsky, N. (1975) ’Reflections on language’ Pantheon Books: New York
[51] Chomsky, N. (1986) ’Knowledge of Language’ Praeger: New York; Chomsky, N. (1988) ’Language and the Problems of Knowledge’ MIT Press: Cambridge MA; Quine, W.V.O. (1970) Sinth’ese 21, p. 386 · Zbl 0113.32701
[52] Chomsky, N. (1965) ’Aspects of the Theory of Syntax’ MIT Press: Cambridge MA; Goodman, N. (1969) in S. Hook (Ed.) ’Language and Philosophy’ New York University Press: New York
[53] Thurston W.P. (1997) ’ThreeDimensional Geometry and Topology’ Vol. 1. Princeton University Press, Princeton · Zbl 0873.57001
[54] Ginsburg, S. (1966) ’The Mathematical Theory of Context-Free Languages’ McGraw- Hill: New York; Gilman, R.H. (1996) Discrete Math. Theoret. Comput. Sci. 25, p. 27
[55] Baumslag G., Gersten S.M., Shapiro M., Short H. (1991) Journal of Pure and Applied Algebra 76: 229 · Zbl 0749.20006 · doi:10.1016/0022-4049(91)90139-S
[56] Aho A.V. (1968) J. Assoc. Comp. Math 15: 647
[57] Bridson, M.R. (1993) Geometric and Functional Analysis 3, p. 263 Rees, S. (1999) in Geometry & Topology Monographs, Vol. 1: The Epstein birthday schrift, p. 493
[58] Dehornoy P. (2005) Journal of Pure and Applied Algebra 203: 1 · Zbl 1150.20016 · doi:10.1016/j.jpaa.2005.02.012
[59] Conway J.H., Curtis R.T., Norton S.P., Parker R.A., Wilson R.A. (1985) ’Atlas of Finite Groups: Maximal Subgroups and Ordinary Characters for Simple Groups’. Clarendon Press, Oxford · Zbl 0568.20001
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.