A Caltech Library Service

Dense Quantum Coding and Quantum Finite Automata

Ambainis, Andris and Nayak, Ashwin and Ta-Shma, Amnon and Vazirani, Umesh (2002) Dense Quantum Coding and Quantum Finite Automata. Journal of the ACM, 49 (4). pp. 496-511. ISSN 0004-5411. doi:10.1145/581771.581773.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Nayak, Ashwin0000-0002-3924-0875
Additional Information:© 2002 ACM. RECEIVED JULY 2000; REVISED MAY 2002; ACCEPTED MAY 2002. A. Ambainis was supported by the Berkeley Fellowship for Graduate Studies and, in part, by NSF grant CCR-9800024; A. Nayak and U. Vazirani were supported by JSEP grant FDP 49620-97-1-0220-03-98 and NSF grant CCR-9800024. We would like to thank Ike Chuang for showing us the 3-into-1 quantum encoding; Dorit Aharonov, Ike Chuang, Michael Nielsen, Steven Rudich, and Avi Wigderson for many interesting discussions; and the anonymous referees for their helpful comments.
Funding AgencyGrant Number
Berkeley Fellowship for Graduate StudiesUNSPECIFIED
Joint Science Education Project (JSEP)FDP 49620-97-1-0220-03-98
Issue or Number:4
Record Number:CaltechAUTHORS:20160419-112812430
Persistent URL:
Official Citation:Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, and Umesh Vazirani. 2002. Dense quantum coding and quantum finite automata. J. ACM 49, 4 (July 2002), 496-511. DOI=
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:66276
Deposited By: Kristin Buxton
Deposited On:19 Apr 2016 20:20
Last Modified:10 Nov 2021 23:55

Repository Staff Only: item control page