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

Journal of the ACM

Dense quantum coding and quantum finite automata

Andris Ambainis, Ashwin Nayak, Amnon Ta‐Shma, Umesh V. Vazirani

Published Jul 1, 2002• 258 citations
Publisher

Abstract

We consider the possibility of encoding m classical bits into many fewer n quantum bits (qubits) so that an arbitrary bit from the original m bits can be recovered with good probability. We show that nontrivial quantum codes exist that have no classical counterparts. On the other hand, we show that quantum encoding cannot save more than a logarithmic additive factor over the best classical encoding. The proof is based on an entropy coalescence principle that is obtained by viewing Holevo's theorem from a new perspective.In the existing implementations of quantum computing, qubits are a very expensive resource. Moreover, it is difficult to reinitialize existing bits during the computation. In particular, reinitialization is impossible in NMR quantum computing, which is perhaps the most advanced implementation of quantum computing at the moment. This motivates the study of quantum computation with restricted memory and no reinitialization, that is, of quantum finite automata. It was known that there are languages that are recognized by quantum finite automata with sizes exponentially smaller than those of corresponding classical automata. Here, we apply our technique to show the surprising result that there are languages for which quantum finite automata take exponentially more states than those of corresponding classical automata.

DOI
10.1145/581771.581773

Related papers

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•3 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•132 citations

Lower bounds for quantum computation and communication

Ashwin Nayak, Umesh V. Vazirani

The description of the state of an n-bit quantum system requires 2n-1 complex numbers. This exponentially large information capacity of quantum states has been exploited in recent results showing both exponential speed-up, and exponential savings in communication costs in solving certain problems using quantum computers. In this dissertation, we establish limitations on the ways in which the exponentially many degrees of freedom hidden in quantum states may be accessed. More specifically, we give tight bounds for random access codes, which allow us to encode classical information using quantum bits such that only a small portion of the encoded information may be recovered via a measurement. This also sheds light on the power of computing with a finite number of quantum bits—using these techniques, we show an exponential size lower bound for quantum finite automata for a problem which can be solved on a linear size classical automaton. We then consider the complexity of solving certain problems in the quantum black-box model, an information theoretic model that has been a rich source of insights into the nature of quantum computation. We derive nearly optimal lower bounds for several problems in this model, including that of approximating the median. We also give new, optimal algorithms for approximate medians and other order statistics.

•Jan 1, 1999•14 citations

Optimal lower bounds for quantum automata and random access codes

Ashwin Nayak

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.

arXiv:quant-ph/9904093•Annual Symposium on Foundations of Computer Science•Jan 20, 2003•274 citations

One-way quantum finite automata together with classical states

Daowen Qiu, Paulo Mateus, Xiangfu Zou +1 more

We show that there are quantum devices that accept all regular languages and that are exponentially more concise than deterministic finite automata (DFA). For this purpose, we introduce a new computing model of {\it one-way quantum finite automata} (1QFA), namely, {\it one-way quantum finite automata together with classical states} (1QFAC), which extends naturally both measure-only 1QFA and DFA and whose state complexity is upper-bounded by both. The original contributions of the paper are the following. First, we show that the set of languages accepted by 1QFAC with bounded error consists precisely of all regular languages. Second, we prove that 1QFAC are at most exponentially more concise than DFA. Third, we show that the previous bound is tight for families of regular languages that are not recognized by measure-once (RMO), measure-many (RMM) and multi-letter 1QFA. % More concretely we exhibit regular languages $L^0(m)$ for $m$ prime such that: (i) $L^0(m)$ cannot be recognized by measure-once, measure-many and multi-letter 1QFA; (ii) the minimal DFA that accepts $L^0(m)$ has $O(m)$ states; (iii) there is a 1QFAC with constant classical states and $O(\log(m))$ quantum basis that accepts $L^0(m)$. Fourth, we give a polynomial-time algorithm for determining whether any two 1QFAC are equivalent. Finally, we show that state minimization of 1QFAC is decidable within EXPSPACE. We conclude the paper by posing some open problems.

arXiv:0909.1428•Sep 8, 2009•4 citations

Automata with Quantum and Classical Resources

Masaki Nakanishi

Quantum automata have been studied as simple quantum computation models. They can be considered models of small (or restricted)quantum computers. In this paper, we give descriptions of several kinds of quantum automata and show their power in comparison to their classical counterparts. We also give descriptions of quantum automata that have additional classical computational resources. Introducing classical computational resources can enhance the power of quantum automata, since this approach relaxes such restrictions as reversible state transitions.

IPSJ Digital Courier•Jan 1, 2005•0 citations
We consider the possibility of encoding m classical bits into many fewer n quantum bits (qubits) so that an arbitrary bit from the original m bits can be recovered with good probability. We show that nontrivial quantum codes exist that have no classical counterparts. On the other hand, we show that quantum encoding cannot save more than a logarithmic additive factor over the best classical encoding. The proof is based on an entropy coalescence principle that is obtained by viewing Holevo's theorem from a new perspective.In the existing implementations of quantum computing, qubits are a very expensive resource. Moreover, it is difficult to reinitialize existing bits during the computation. In particular, reinitialization is impossible in NMR quantum computing, which is perhaps the most advanced implementation of quantum computing at the moment. This motivates the study of quantum computation with restricted memory and no reinitialization, that is, of quantum finite automata. It was known that there are languages that are recognized by quantum finite automata with sizes exponentially smaller than those of corresponding classical automata. Here, we apply our technique to show the surprising result that there are languages for which quantum finite automata take exponentially more states than those of corresponding classical 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 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.
The description of the state of an n-bit quantum system requires 2n-1 complex numbers. This exponentially large information capacity of quantum states has been exploited in recent results showing both exponential speed-up, and exponential savings in communication costs in solving certain problems using quantum computers. In this dissertation, we establish limitations on the ways in which the exponentially many degrees of freedom hidden in quantum states may be accessed. More specifically, we give tight bounds for random access codes, which allow us to encode classical information using quantum bits such that only a small portion of the encoded information may be recovered via a measurement. This also sheds light on the power of computing with a finite number of quantum bits—using these techniques, we show an exponential size lower bound for quantum finite automata for a problem which can be solved on a linear size classical automaton. We then consider the complexity of solving certain problems in the quantum black-box model, an information theoretic model that has been a rich source of insights into the nature of quantum computation. We derive nearly optimal lower bounds for several problems in this model, including that of approximating the median. We also give new, optimal algorithms for approximate medians and other order statistics.
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 show that there are quantum devices that accept all regular languages and that are exponentially more concise than deterministic finite automata (DFA). For this purpose, we introduce a new computing model of {\it one-way quantum finite automata} (1QFA), namely, {\it one-way quantum finite automata together with classical states} (1QFAC), which extends naturally both measure-only 1QFA and DFA and whose state complexity is upper-bounded by both. The original contributions of the paper are the following. First, we show that the set of languages accepted by 1QFAC with bounded error consists precisely of all regular languages. Second, we prove that 1QFAC are at most exponentially more concise than DFA. Third, we show that the previous bound is tight for families of regular languages that are not recognized by measure-once (RMO), measure-many (RMM) and multi-letter 1QFA. % More concretely we exhibit regular languages L0(m)L^0(m)L0(m) for mmm prime such that: (i) L0(m)L^0(m)L0(m) cannot be recognized by measure-once, measure-many and multi-letter 1QFA; (ii) the minimal DFA that accepts L0(m)L^0(m)L0(m) has O(m)O(m)O(m) states; (iii) there is a 1QFAC with constant classical states and O(log⁡(m))O(\log(m))O(log(m)) quantum basis that accepts L0(m)L^0(m)L0(m). Fourth, we give a polynomial-time algorithm for determining whether any two 1QFAC are equivalent. Finally, we show that state minimization of 1QFAC is decidable within EXPSPACE. We conclude the paper by posing some open problems.
Quantum automata have been studied as simple quantum computation models. They can be considered models of small (or restricted)quantum computers. In this paper, we give descriptions of several kinds of quantum automata and show their power in comparison to their classical counterparts. We also give descriptions of quantum automata that have additional classical computational resources. Introducing classical computational resources can enhance the power of quantum automata, since this approach relaxes such restrictions as reversible state transitions.