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

arXiv:quant-ph/9904093 · Annual Symposium on Foundations of Computer Science

Optimal lower bounds for quantum automata and random access codes

Ashwin Nayak

Published Jan 20, 2003• 307 citations
arXivHTMLPDF

Abstract

Consider the finite regular language L/sub n/={w0|w/spl isin/{0,1}*,|w|/spl les/n}. A. Ambainis et al. (1999) showed that while this language is accepted by a deterministic finite automaton of size O(n), any one-way quantum finite automaton (QFA) for it has size 2/sup /spl Omega/(n/logn)/. This was based on the fact that the evolution of a QFA is required to be reversible. When arbitrary intermediate measurements are allowed, this intuition breaks down. Nonetheless, we show a 2/sup /spl Omega/(n)/ lower bound for such QFA for L/sub n/, thus also improving the previous bound. The improved bound is obtained from simple entropy arguments based on A.S. Holevo's (1973) theorem. This method also allows us to obtain an asymptotically optimal (1-H(p))n bound for the dense quantum codes (random access codes) introduced by A. Ambainis et al. We then turn to Holevo's theorem, and show that in typical situations, it may be replaced by a tighter and more transparent in-probability bound.

DOI
10.1109/sffcs.1999.814608

Related papers

On the space efficiency of one way quantum finite automata

Andris Ambainis, Ashwin Nayak, Umesh V. Vazirani

We exhibit a family {L_n} of finite regular languages such that any 1-way quantum finite automaton (QFA) accepting L_n with probability 1/2 + epsilon (for any constant epsilon > 0) must have 2^{Omega(n/log n)} states. On the other hand, each language L_n can be recognized by a deterministic finite automaton (DFA) of size O(n). This is in immediate contrast to the recent result of Ambainis and Freivalds which shows that for some regular languages, 1-way QFAs can be exponentially more space-efficient as compared to DFAs.

•Apr 21, 1998•2 citations

On the power of quantum finite state automata

A. Kondacs, John Watrous

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 regarding 2qfa's. 1. For any /spl epsiv/>0, there is a 2qfa M which recognizes the non-regular language L={a/sup m/b/sup m/|m/spl ges/1} with (one-sided) error bounded by E, and which halts in linear time. Specifically, M accepts any string in L with probability 1 and rejects any string not in L with probability at least 1-/spl epsiv/. 2. For every regular language L, there is a reversible (and hence quantum) 2-way finite state automaton which recognizes L and which runs in linear time. In fact, it is possible to define 2qfar's which recognize the non-context-free language {a/sup m/b/sup m/c/sup m/|m/spl ges/1}, based on the same technique used for 1. Consequently, the class of languages recognized by linear time, bounded error 2qfa's properly includes the regular languages. Since it is known that 2-way deterministic, nondeterministic and polynomial expected time, bounded error probabilistic finite automata can recognize only regular languages, it follows that 2qfa's are strictly more powerful than these "classical" models. In the case of 1-way automata, the situation is reversed. We prove that the class of languages recognizable by bounded error 1qfa's is properly contained in the class of regular languages.

Annual Symposium on Foundations of Computer Science•Nov 22, 2002•371 citations

Dense Quantum Coding and a Lower Bound for 1-way Quantum Automata

Andris Ambainis, Nayak, Ashwin, Ta-Shma, Amnon +1 more

We consider the possibility of encoding m classical bits into much fewer n quantum bits so that an arbitrary bit from the original m bits can be recovered with a good probability, and we show that non-trivial quantum encodings exist that have no classical counterparts. On the other hand, we show that quantum encodings cannot be much more succint as compared to classical encodings, and we provide a lower bound on such quantum encodings. Finally, using this lower bound, we prove an exponential lower bound on the size of 1-way quantum finite automata for a family of languages accepted by linear sized deterministic finite automata.

arXiv:quant-ph/9804043•Apr 18, 1998•55 citations

Dense quantum coding and a lower bound for 1-way quantum automata

Andris Ambainis, Ashwin Nayak, Amnon Ta‐Shma +1 more

We consider the possibility of encoding m classical bits into much fewer n quantum bits so that an arbitrary bit from the original m bits can be recovered with a good probability, and we show that non-trivial quantum encodings exist that have no classical counterparts.On the other hand, we show that quantum encodings cannot be much more succint as compared to classical encodings, and we provide a lower bound on such quantum encodings.Finally, using this lower bound, we prove an exponential lower bound an the size of l-way quantum linite automata for a family of languages accepted by linear sized deterministic linite automata.

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

1-way quantum finite automata: strengths, weaknesses and generalizations

Andris Ambainis, Rūsiņš Freivalds

We study 1-way quantum finite automata (QFAs). First, we compare them with their classical counterparts. We show that, if an automaton is required to give the correct answer with a large probability (greater than 7/9), then any 1-way QFAs can be simulated by a 1-way reversible automaton. However, quantum automata giving the correct answer with smaller probabilities are more powerful than reversible automata. Second, we show that 1-way QFAs can be very space-efficient. We construct a 1-way QFA that is exponentially smaller than any equivalent classical (even randomized) finite automaton. We think that this construction may be useful for design of other space-efficient quantum algorithms. Third, we consider several generalizations of 1-way QFAs. Here, our goal is to find a model which is more powerful than 1-way QFAs keeping the quantum part as simple as possible.

arXiv:quant-ph/9802062•Annual Symposium on Foundations of Computer Science•Nov 27, 2002•250 citations

A small 1-way quantum finite automaton

Arnolds Ķikusts

We study 1-way quantum finite automata (QFAs) and compare them with their classical counterparts. We show that 1-way QFAs can be very space efficient. We construct a 1-way QFAs that are quadratically smaller than any equivalent deterministic finite automata and give the correct answer with a large probability by recognizing the languages in a two letter alphabet "the number of the letters a and the number of the letters b are divisible by n".

arXiv:quant-ph/9810065•Oct 22, 1998•12 citations
Consider the finite regular language L/sub n/={w0|w/spl isin/{0,1}*,|w|/spl les/n}. A. Ambainis et al. (1999) showed that while this language is accepted by a deterministic finite automaton of size O(n), any one-way quantum finite automaton (QFA) for it has size 2/sup /spl Omega/(n/logn)/. This was based on the fact that the evolution of a QFA is required to be reversible. When arbitrary intermediate measurements are allowed, this intuition breaks down. Nonetheless, we show a 2/sup /spl Omega/(n)/ lower bound for such QFA for L/sub n/, thus also improving the previous bound. The improved bound is obtained from simple entropy arguments based on A.S. Holevo's (1973) theorem. This method also allows us to obtain an asymptotically optimal (1-H(p))n bound for the dense quantum codes (random access codes) introduced by A. Ambainis et al. We then turn to Holevo's theorem, and show that in typical situations, it may be replaced by a tighter and more transparent in-probability bound.
We exhibit a family {L_n} of finite regular languages such that any 1-way quantum finite automaton (QFA) accepting L_n with probability 1/2 + epsilon (for any constant epsilon > 0) must have 2^{Omega(n/log n)} states. On the other hand, each language L_n can be recognized by a deterministic finite automaton (DFA) of size O(n). This is in immediate contrast to the recent result of Ambainis and Freivalds which shows that for some regular languages, 1-way QFAs can be exponentially more space-efficient as compared to DFAs.
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 regarding 2qfa's. 1. For any /spl epsiv/>0, there is a 2qfa M which recognizes the non-regular language L={a/sup m/b/sup m/|m/spl ges/1} with (one-sided) error bounded by E, and which halts in linear time. Specifically, M accepts any string in L with probability 1 and rejects any string not in L with probability at least 1-/spl epsiv/. 2. For every regular language L, there is a reversible (and hence quantum) 2-way finite state automaton which recognizes L and which runs in linear time. In fact, it is possible to define 2qfar's which recognize the non-context-free language {a/sup m/b/sup m/c/sup m/|m/spl ges/1}, based on the same technique used for 1. Consequently, the class of languages recognized by linear time, bounded error 2qfa's properly includes the regular languages. Since it is known that 2-way deterministic, nondeterministic and polynomial expected time, bounded error probabilistic finite automata can recognize only regular languages, it follows that 2qfa's are strictly more powerful than these "classical" models. In the case of 1-way automata, the situation is reversed. We prove that the class of languages recognizable by bounded error 1qfa's is properly contained in the class of regular languages.
We consider the possibility of encoding m classical bits into much fewer n quantum bits so that an arbitrary bit from the original m bits can be recovered with a good probability, and we show that non-trivial quantum encodings exist that have no classical counterparts. On the other hand, we show that quantum encodings cannot be much more succint as compared to classical encodings, and we provide a lower bound on such quantum encodings. Finally, using this lower bound, we prove an exponential lower bound on the size of 1-way quantum finite automata for a family of languages accepted by linear sized deterministic finite automata.
We consider the possibility of encoding m classical bits into much fewer n quantum bits so that an arbitrary bit from the original m bits can be recovered with a good probability, and we show that non-trivial quantum encodings exist that have no classical counterparts.On the other hand, we show that quantum encodings cannot be much more succint as compared to classical encodings, and we provide a lower bound on such quantum encodings.Finally, using this lower bound, we prove an exponential lower bound an the size of l-way quantum linite automata for a family of languages accepted by linear sized deterministic linite automata.
We study 1-way quantum finite automata (QFAs). First, we compare them with their classical counterparts. We show that, if an automaton is required to give the correct answer with a large probability (greater than 7/9), then any 1-way QFAs can be simulated by a 1-way reversible automaton. However, quantum automata giving the correct answer with smaller probabilities are more powerful than reversible automata. Second, we show that 1-way QFAs can be very space-efficient. We construct a 1-way QFA that is exponentially smaller than any equivalent classical (even randomized) finite automaton. We think that this construction may be useful for design of other space-efficient quantum algorithms. Third, we consider several generalizations of 1-way QFAs. Here, our goal is to find a model which is more powerful than 1-way QFAs keeping the quantum part as simple as possible.