Abstract
This paper develops a theory of quantum automata and their slightly more general versions, q-automata. Quantum languages and η-quantum languages, 0≤η<1, are studied. Functions that can be realized as probability maps for q-automata are characterized. Quantum grammars are discussed and it is shown that quantum languages are precisely those languages that are induced by a quantum grammar. A quantum pumping lemma is employed to show that there are regular languages that are not η-quantum, 0≤η<1.
Similar content being viewed by others
REFERENCES
L. Adelman, J. DeMarrais, and M. Huang, SIAM J. Comput. 26, 1524–1540 (1997).
A. Barenco, C. Bennett, R. Cleve, D. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. Smolin, and H. Weinfurter, Phys. Rev.A 52, 3457–3467 (1995).
P. Benioff, Int. J. Stat. Phys. 29, 515–546 (1982).
P. Benioff, Phys. Rev. Lett. 48, 1581–1585 (1982).
C. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, SIAM J. Comput. 26, 1510–1523 (1997).
E. Bernstein and U. Vazirani, SIAM J. Comput. 26, 1411–1473 (1997).
A. Berthiawme and G. Brassard, J. Mod. Optics 41, 2521–2535 (1994).
J. Chuang, R. LaFlamme, P. Shor, and W. Zurek, Science Dec. 8, 1633–1635 (1995).
D. Deutsch, Proc. Roy. Soc. London Ser.A 400, 97–117 (1985).
D. Deutsch, Proc. Roy. Soc. London Ser.A 425, 73–90 (1989).
D. Deutsch and R. Jozsa, Proc. Roy. Soc. London Ser.A 439, 553–558 (1992).
D. DiVincenzo, Phys. Rev.A 51, 1015–1022 (1995).
R. Feynman, Int. J. Theor. Phys. 21, 467–488 (1982).
R. Feynman, Found. Phys. 16, 507–531 (1986).
A. Gleason, J. Rat. Mech. Anal. 6, 885–893 (1957).
A. Kondacs and J. Watrous, Proceedings, 38th Symposium on Foundations of Computer Science (1997).
C. Moore and J. Crutchfield, Theor. Comp. Sci. (in press).
G. Palma, K. Suominen, and A. Ekert, Proc. Roy. Soc. London Ser.A 452, 567–584 (1996).
A. Paz, Introduction to Probabilistic Automata (Academic, New York, 1971).
P. Shor, Phys. Rev.A 52, 2493–2496 (1995).
P. Shor, SIAM J. Comput. 26, 1484–1509 (1997).
D. Simon, SIAM J. Comput. 26, 1474–1483 (1997).
A. Steane, Phys. Rev. Lett. 78, 2252–2255 (1997).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Gudder, S. Basic Properties of Quantum Automata. Foundations of Physics 30, 301–319 (2000). https://doi.org/10.1023/A:1003649201735
Issue Date:
DOI: https://doi.org/10.1023/A:1003649201735