Article

Free access

Undecidability on quantum finite automata

Authors:

Masami Amano,

Kazuo IwamaAuthors Info & Claims

STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of Computing

Pages 368 - 375

https://doi.org/10.1145/301250.301344

Published: 01 May 1999 Publication History

PDF eReader

References

[1]

A. Ambainis and R. Freivalds, "l-way quantum finite automata: strengths, weaknesses and generalizations,'' Proceedings of the 39th IEEE Conference on Foundations of Computer Science (to appear), 1998.

Digital Library

Google Scholar

[2]

C. Dwork and L. Stockmeyer, "On the power of 2- way probabilistic finite automata," Proceedings of the 30th IEEE Conference on Foundations of Computer Science, 480-485, 1989.

Google Scholar

[3]

R. Freivalds, "Probabi}istic two-way machines," LNC$, 188, 33-45, 1981.

Digital Library

Google Scholar

[4]

L. Grover, "A fast quantum mechanical algorithm for database search," Proceedings of the ~Sth A CM Symposium on Theory of Computing~ 212-219, 1996.

Digital Library

Google Scholar

[5]

J. Hopcroft and J. Ullman, An Introduction to Automata Theory, Languages and Computation, Addison- Wesley, 1979.

Digital Library

Google Scholar

[6]

J. Hopcroft and J. Ullman, "Deterministic stack automata and the quotient operator," JCSS, 2:1, 1-12, t 968.

Digital Library

Google Scholar

[7]

A. Kondacs and J. Watrous, "On the power of quantum finite state automata," Proceedings of the 38th IEEE Conference on Foundations o.f Computer Science, 66-75, 1997.

Digital Library

Google Scholar

[8]

M. Minsky, Computation: Finite and infinite machines, Prentice~HaJl~ 1966.

Digital Library

Google Scholar

[9]

P. Shot, "Algorithms for quantum computation: discrete logarithms and factoring," Proceedings o} the 35th IEEE Symposium on Foundations of Computer Science, 124-134, 1994.

Google Scholar

Cited By

View all

Dai S(2023)Quaternionic quantum automataInternational Journal of Quantum Information10.1142/S021974992350017X21:04Online publication date: 20-Mar-2023
https://doi.org/10.1142/S021974992350017X
Bhatia AKumar A(2019)On the power of two-way multihead quantum finite automataRAIRO - Theoretical Informatics and Applications10.1051/ita/2018020Online publication date: 15-Jan-2019
https://doi.org/10.1051/ita/2018020
Nakanishi MYakaryılmaz A(2015)Classical and Quantum Counter Automata on Promise ProblemsImplementation and Application of Automata10.1007/978-3-319-22360-5_19(224-237)Online publication date: 28-Jul-2015
https://doi.org/10.1007/978-3-319-22360-5_19
Show More Cited By

Index Terms

Undecidability on quantum finite automata
1. Theory of computation
  1. Formal languages and automata theory
  2. Models of computation
    1. Computability

Recommendations

Quantum Finite Multitape Automata
SOFSEM '99: Proceedings of the 26th Conference on Current Trends in Theory and Practice of Informatics on Theory and Practice of Informatics

Quantum finite automata were introduced by C. Moore, J. P. Crutchfield [4], and by A. Kondacs and J. Watrous [3]. This notion is not a generalization of the deterministic finite automata. Moreover, in [3] it was proved that not all regular languages can ...
On the power of quantum finite state automata
FOCS '97: Proceedings of the 38th Annual Symposium on Foundations of Computer Science

In this paper, we introduce 1-way and 2-way quantum finite state automata (1qfa's and 2qfa's), which are the quantum analogues of deterministic, nondeterministic and probabilistic 1-way and 2-way finite state automata. We prove the following facts ...
Characterizations of 1-Way Quantum Finite Automata

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of Computing

May 1999

790 pages

ISBN:1581130678

DOI:10.1145/301250

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1999

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC99

Sponsor:

SIGACT

STOC99: ACM Symposium on Theory of Computing

May 1 - 4, 1999

Georgia, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
505
Total Downloads

Downloads (Last 12 months)24
Downloads (Last 6 weeks)8

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Dai S(2023)Quaternionic quantum automataInternational Journal of Quantum Information10.1142/S021974992350017X21:04Online publication date: 20-Mar-2023
https://doi.org/10.1142/S021974992350017X
Bhatia AKumar A(2019)On the power of two-way multihead quantum finite automataRAIRO - Theoretical Informatics and Applications10.1051/ita/2018020Online publication date: 15-Jan-2019
https://doi.org/10.1051/ita/2018020
Nakanishi MYakaryılmaz A(2015)Classical and Quantum Counter Automata on Promise ProblemsImplementation and Application of Automata10.1007/978-3-319-22360-5_19(224-237)Online publication date: 28-Jul-2015
https://doi.org/10.1007/978-3-319-22360-5_19
Reinhardt KYakaryılmaz A(2014)The Minimum Amount of Useful Space: New Results and New DirectionsDevelopments in Language Theory10.1007/978-3-319-09698-8_28(315-326)Online publication date: 2014
https://doi.org/10.1007/978-3-319-09698-8_28
Tani SKobayashi HMatsumoto K(2012)Exact Quantum Algorithms for the Leader Election ProblemACM Transactions on Computation Theory10.1145/2141938.21419394:1(1-24)Online publication date: 1-Mar-2012
https://dl.acm.org/doi/10.1145/2141938.2141939
Li LQiu DZou XLi LWu LMateus P(2012)Characterizations of one-way general quantum finite automataTheoretical Computer Science10.1016/j.tcs.2011.10.021419(73-91)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.1016/j.tcs.2011.10.021
Lin T(2012)Another approach to the equivalence of measure-many one-way quantum finite automata and its applicationJournal of Computer and System Sciences10.1016/j.jcss.2012.01.00478:3(807-821)Online publication date: 1-May-2012
https://dl.acm.org/doi/10.1016/j.jcss.2012.01.004
Qiu DLi LZou XMateus PGruska J(2011)Multi-letter quantum finite automata: decidability of the equivalence and minimization of statesActa Informatica10.1007/s00236-011-0139-648:5-6(271-290)Online publication date: 1-Aug-2011
https://dl.acm.org/doi/10.1007/s00236-011-0139-6
Nakanishi M(2010)On the Weakness of One-Way Quantum Pushdown AutomataProceedings of the 2010 Fourth International Conference on Quantum, Nano and Micro Technologies10.1109/ICQNM.2010.22(83-87)Online publication date: 10-Feb-2010
https://dl.acm.org/doi/10.1109/ICQNM.2010.22
Qiu DYu S(2009)Hierarchy and equivalence of multi-letter quantum finite automataTheoretical Computer Science10.1016/j.tcs.2009.03.040410:30-32(3006-3017)Online publication date: 1-Aug-2009
https://dl.acm.org/doi/10.1016/j.tcs.2009.03.040
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Quantum Finite Multitape Automata

On the power of quantum finite state automata

Characterizations of 1-Way Quantum Finite Automata