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.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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
On the power of quantum finite state automata
Kondacs, A., & Watrous, J. (2002) · Proceedings 38th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1997.646094 · Cited by 346
Optimal lower bounds for quantum automata and random access codes
Nayak, A. (2003) · 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039) · doi:10.1109/sffcs.1999.814608 · Cited by 275
Self-citation1-way quantum finite automata: strengths, weaknesses and generalizations
Ambainis, A., & Freivalds, R. (2002) · Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280) · doi:10.1109/sfcs.1998.743469 · Cited by 220
Self-citationQuantum Cryptography, or Unforgeable Subway Tokens
Bennett, C. H., Brassard, G., Breidbart, S., & Wiesner, S. (1983) · Advances in Cryptology · doi:10.1007/978-1-4757-0602-4_26 · Cited by 192
Dense quantum coding and a lower bound for 1-way quantum automata
Ambainis, A., Nayak, A., Ta‐Shma, A., & Vazirani, U. V. (1999) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/301250.301347 · Cited by 149
Self-citationCommunication complexity lower bounds by polynomials
Buhrman, H., & de Wolf, R. (2002) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2001.933879 · Cited by 132
Interaction in quantum communication and the complexity of set disjointness
Klauck, H., Nayak, A., Ta‐Shma, A., & Zuckerman, D. (2001) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/380752.380786 · Cited by 61
Self-citationLower bounds for quantum computation and communication
Nayak, A., & Vazirani, U. V. (1999) · Cited by 20
Self-citation
Cited by
The Theory of Quantum Information
Watrous, J. (2018) · doi:10.1017/9781316848142 · Cited by 1,325
Information causality as a physical principle
Pawłowski, M., Paterek, T., Kaszlikowski, D., Scarani, V., Winter, A., & Żukowski, M. (2009) · Nature · doi:10.1038/nature08400 · Cited by 775
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
Shadow Tomography of Quantum States
Aaronson, S. (2020) · SIAM Journal on Computing · doi:10.1137/18m120275x · Cited by 315
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
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
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.