Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ACM Symposium on Theory of Computing (STOC)

Undecidability on quantum finite automata

Masami Amano, Kazuo Iwama

Published May 1, 1999• 55 citations
Publisher

Abstract

Article Undecidability on quantum finite automata Share on Authors: Masami Amano School of Informatics, Kyoto University, Kyata 606-8501, Japan School of Informatics, Kyoto University, Kyata 606-8501, JapanView Profile , Kazuo Iwama School of Informatics, Kyoto University, Kyata 606-8501, Japan School of Informatics, Kyoto University, Kyata 606-8501, JapanView Profile Authors Info & Claims STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of ComputingMay 1999 Pages 368–375https://doi.org/10.1145/301250.301344Online:01 May 1999Publication History 23citation442DownloadsMetricsTotal Citations23Total Downloads442Last 12 Months14Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

DOI
10.1145/301250.301344

Related papers

QUANTUM FINITE AUTOMATA

Jozef Gruska, Roland Vollmar

Various quantum versions of the most basic models of the classical finite automata have already been introduced and various modes of their computations have already started to be investigated. In this paper we overview basic models, approaches, techniques and results in this promising area of quantum automata that is expected to play an important role also in theoretical computer science. We also summarize some open problems and research directions to pursue in this area.

International Colloquium on Words, Languages and Combinatorics•Jul 1, 2003•0 citations

Quantum bit escrow

Dorit Aharonov, Amnon Ta‐Shma, Umesh V. Vazirani +1 more

Article Free Access Share on Quantum bit escrow Authors: Dorit Aharonov University of California, Berkeley, CA University of California, Berkeley, CAView Profile , Amnon Ta-Shma University of California, Berkeley, CA University of California, Berkeley, CAView Profile , Umesh V. Vazirani University of California, Berkeley, CA University of California, Berkeley, CAView Profile , Andrew C. Yao Princeton University, Princeton, NJ Princeton University, Princeton, NJView Profile Authors Info & Claims STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computingMay 2000 Pages 705–714https://doi.org/10.1145/335305.335404Published:01 May 2000Publication History 46citation619DownloadsMetricsTotal Citations46Total Downloads619Last 12 Months56Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

ACM Symposium on Theory of Computing (STOC)•May 1, 2000•108 citations

Secure computation with honest-looking parties (extended abstract): what if nobody is truly honest?

Ran Canetti, Rafail Ostrovsky

Article Free Access Share on Secure computation with honest-looking parties (extended abstract): what if nobody is truly honest? Authors: Ran Canetti IBM T.J. Watson Research Center IBM T.J. Watson Research CenterView Profile , Rafail Ostrovsky Bell Communications Research, MCC-1C365B, 445 South Street, Morristown, New Jersey Bell Communications Research, MCC-1C365B, 445 South Street, Morristown, New JerseyView Profile Authors Info & Claims STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of ComputingMay 1999Pages 255–264https://doi.org/10.1145/301250.301313Published:01 May 1999Publication History 15citation383DownloadsMetricsTotal Citations15Total Downloads383Last 12 Months19Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

ACM Symposium on Theory of Computing (STOC)•May 1, 1999•19 citations

Automata and Quantum Computing

Andris Ambainis, Abuzer Yakaryılmaz

Quantum computing is a new model of computation, based on quantum physics. Quantum computers can be exponentially faster than conventional computers for problems such as factoring. Besides full-scale quantum computers, more restricted models such as quantum versions of finite automata have been studied. In this paper, we survey various models of quantum finite automata and their properties. We also provide some open questions and new directions for researchers. Keywords: quantum finite automata, probabilistic finite automata, nondeterminism, bounded error, unbounded error, state complexity, decidability and undecidability, computational complexity

arXiv:1507.01988•Jul 7, 2015•57 citations

Automata and quantum computing

Andris Ambainis, Abuzer Yakaryılmaz

Quantum computing is a new model of computation, based on quantum physics. Quantum computers can be exponentially faster than conventional computers for problems such as factoring. Besides full-scale quantum computers, more restricted models such as quantum versions of finite automata have been studied. In this paper, we survey various models of quantum finite automata and their properties. We also provide some open questions and new directions for researchers. Keywords: quantum finite automata, probabilistic finite automata, nondeterminism, bounded error, unbounded error, state complexity, decidability and undecidability, computational complexity

EMS Press eBooks•Sep 13, 2021•40 citations

Quantum computation and quantum communication: theory and experiments Author of book: Mladen Pavicic

George Hacken

review-article Share on Quantum computation and quantum communication: theory and experiments Author of book: Mladen Pavicic Author: George Hacken View Profile Authors Info & Claims ACM SIGACT NewsVolume 40Issue 4December 2009 pp 10–14https://doi.org/10.1145/1711475.1711478Published:25 January 2010Publication History 0citation172DownloadsMetricsTotal Citations0Total Downloads172Last 12 Months4Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

ACM SIGACT News•Jan 25, 2010•0 citations
Article Undecidability on quantum finite automata Share on Authors: Masami Amano School of Informatics, Kyoto University, Kyata 606-8501, Japan School of Informatics, Kyoto University, Kyata 606-8501, JapanView Profile , Kazuo Iwama School of Informatics, Kyoto University, Kyata 606-8501, Japan School of Informatics, Kyoto University, Kyata 606-8501, JapanView Profile Authors Info & Claims STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of ComputingMay 1999 Pages 368–375https://doi.org/10.1145/301250.301344Online:01 May 1999Publication History 23citation442DownloadsMetricsTotal Citations23Total Downloads442Last 12 Months14Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access
Article Free Access Share on Quantum bit escrow Authors: Dorit Aharonov University of California, Berkeley, CA University of California, Berkeley, CAView Profile , Amnon Ta-Shma University of California, Berkeley, CA University of California, Berkeley, CAView Profile , Umesh V. Vazirani University of California, Berkeley, CA University of California, Berkeley, CAView Profile , Andrew C. Yao Princeton University, Princeton, NJ Princeton University, Princeton, NJView Profile Authors Info & Claims STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computingMay 2000 Pages 705–714https://doi.org/10.1145/335305.335404Published:01 May 2000Publication History 46citation619DownloadsMetricsTotal Citations46Total Downloads619Last 12 Months56Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF
Article Free Access Share on Secure computation with honest-looking parties (extended abstract): what if nobody is truly honest? Authors: Ran Canetti IBM T.J. Watson Research Center IBM T.J. Watson Research CenterView Profile , Rafail Ostrovsky Bell Communications Research, MCC-1C365B, 445 South Street, Morristown, New Jersey Bell Communications Research, MCC-1C365B, 445 South Street, Morristown, New JerseyView Profile Authors Info & Claims STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of ComputingMay 1999Pages 255–264https://doi.org/10.1145/301250.301313Published:01 May 1999Publication History 15citation383DownloadsMetricsTotal Citations15Total Downloads383Last 12 Months19Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF
Quantum computing is a new model of computation, based on quantum physics. Quantum computers can be exponentially faster than conventional computers for problems such as factoring. Besides full-scale quantum computers, more restricted models such as quantum versions of finite automata have been studied. In this paper, we survey various models of quantum finite automata and their properties. We also provide some open questions and new directions for researchers. Keywords: quantum finite automata, probabilistic finite automata, nondeterminism, bounded error, unbounded error, state complexity, decidability and undecidability, computational complexity
Quantum computing is a new model of computation, based on quantum physics. Quantum computers can be exponentially faster than conventional computers for problems such as factoring. Besides full-scale quantum computers, more restricted models such as quantum versions of finite automata have been studied. In this paper, we survey various models of quantum finite automata and their properties. We also provide some open questions and new directions for researchers. Keywords: quantum finite automata, probabilistic finite automata, nondeterminism, bounded error, unbounded error, state complexity, decidability and undecidability, computational complexity
review-article Share on Quantum computation and quantum communication: theory and experiments Author of book: Mladen Pavicic Author: George Hacken View Profile Authors Info & Claims ACM SIGACT NewsVolume 40Issue 4December 2009 pp 10–14https://doi.org/10.1145/1711475.1711478Published:25 January 2010Publication History 0citation172DownloadsMetricsTotal Citations0Total Downloads172Last 12 Months4Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access