The DOI matches its Crossref record; 18 of the 18 references it cites were found in a registry or an index.
Dense quantum coding and quantum finite automata
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Elements of Information Theory
Cover, T. M., & Thomas, J. A. (2001) · Wiley eBooks · doi:10.1002/0471200611 · Cited by 36,808
Quantum Computation and Quantum Information
Nielsen, M. A., Chuang, I., & Grover, L. K. (2002) · American Journal of Physics · doi:10.1119/1.1463744 · Cited by 21,895
Quantum Theory: Concepts and Methods
Peres, A., & Ballentine, L. E. (1995) · American Journal of Physics · doi:10.1119/1.17946 · Cited by 2,561
Wehrl, A. (1978) · Reviews of Modern Physics · doi:10.1103/revmodphys.50.221 · Cited by 1,963
Quantum Theory: Concepts and Methods
(2002) · doi:10.1007/0-306-47120-5 · Cited by 1,029
Quantum Theory: Concepts and Methods
Peres, A., & Mayer, M. E. (1994) · Physics Today · doi:10.1063/1.2808757 · Cited by 672
Elements of Information Theory, Wiley Series in Telecommunications
Cover, T. M., & Allen, T. (1991) · Cited by 623
Quantum circuits with mixed states
Aharonov, D., Kitaev, A., & Nisan, N. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276708 · Cited by 428
Quantum automata and quantum grammars
Moore, C., & Crutchfield, J. P. (2000) · Theoretical Computer Science · doi:10.1016/s0304-3975(98)00191-1 · Cited by 406
Quantum vs. classical communication and computation
Buhrman, H., Cleve, R., & Wigderson, A. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276713 · Cited by 389
Cited by
The Theory of Quantum Information
Watrous, J. (2018) · doi:10.1017/9781316848142 · Cited by 1,325
Index Coding With Side Information
Bar-Yossef, Z., Birk, Y., Jayram, T. S., & Kol, T. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2103753 · Cited by 498
Guest Column: A Survey of Quantum Learning Theory
Arunachalam, S., & de Wolf, R. (2017) · ACM SIGACT News · doi:10.1145/3106700.3106710 · Cited by 152
Quantum communication for wireless wide-area networks
Cheng, S.-T., Wang, C.-Y., & Tao, M.-H. (2005) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2005.851157 · Cited by 109
Certifiable quantum dice: or, true random number generation secure against quantum adversaries
Vazirani, U., & Vidick, T. (2012) · Proceedings of the forty-fourth annual ACM symposium on Theory of computing · doi:10.1145/2213977.2213984 · Cited by 80
“in the analysis of random access codes [1].”
BackgroundSelf-citation
Metadata
- Authors
- Ambainis, A., Nayak, A., Ta-Shma, A., & Vazirani, U.
- Venue
- Journal of the ACM
- Published
- 2002-07
- Volume
- 49
- Issue
- 4
- Pages
- 496-511
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W2116921087
- Cited by
- 258
- References
- 18
- FWCI
- 4.35
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Dense quantum coding and quantum finite automata. https://app.cochat.ai/papers/10.1145/581771.581773
- The paper
- Ambainis, A., Nayak, A., Ta-Shma, A., & Vazirani, U. (2002). Dense quantum coding and quantum finite automata. Journal of the ACM. https://doi.org/10.1145/581771.581773
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.