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.

REFERENCES

• 1: Dorit Aharonov , Alexei Kitaev , Noam Nisan, Quantum circuits with mixed states, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.20-30, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276708]
• 2: Andris Ambainis , Rusins Freivalds, 1-way quantum finite automata: strengths, weaknesses and generalizations, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.332, November 08-11, 1998
• 3: Andris Ambainis , Ashwin Nayak , Ammon Ta-Shma , Umesh Vazirani, Dense quantum coding and a lower bound for 1-way quantum automata, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.376-383, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301347]
• 4: Bennett, C., Brassard, G., Breidbart, S., and Wiesner, S. 1982. Quantum cryptography, or unforgeable subway tokens. In Advances in Cryptology: Proceedings of Crypto'82 (1983). D. Chaum, R. L. Rivest, and A. T. Sherman, Eds. Plenum Press, New York, NY, pp. 267--275.
• 5: Harry Buhrman , Richard Cleve , Avi Wigderson, Quantum vs. classical communication and computation, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.63-68, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276713]
• 6: Harry Buhrman , Ronald de Wolf, Communication Complexity Lower Bounds by Polynomials, Proceedings of the 16th Annual Conference on Computational Complexity, p.120, June 18-21, 2001
• 7: Chuang, I. 1997. Personal communication.
• 8: Cohen, G., Honkala, I., Litsyn, S., and Lobstein, A. 1997. Covering Codes. North-Holland Mathematical Library, vol. 54. Elsevier, Amsterdam, The Netherlands.
• 9: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 10: Holevo, A. 1973. Some estimates of the information transmitted by quantum communication channels. Probl. Inform. Trans. 9, 3, 177--183.
• 11: Hartmut Klauck , Ashwin Nayak , Amnon Ta-Shma , David Zuckerman, Interaction in quantum communication and the complexity of set disjointness, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.124-133, July 2001, Hersonissos, Greece [doi>10.1145/380752.380786]
• 12: A. Kondacs , J. Watrous, On the power of quantum finite state automata, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.66, October 19-22, 1997
• 13: Cristopher Moore , James P. Crutchfield, Quantum automata and quantum grammars, Theoretical Computer Science, v.237 n.1-2, p.275-306, April 28, 2000 [doi>10.1016/S0304-3975(98)00191-1]
• 14: Ashwin V. Nayak , Umesh Vazirani, Lower bounds for quantum computation and communication, 1999
• 15: Ashwin Nayak, Optimal Lower Bounds for Quantum Automata and Random Access Codes, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.369, October 17-18, 1999
• 16: Nielsen, M., and Chuang, I. 2000. Quantum Computation and Quantum Information. Cambridge University Press, Cambridge, England, Chapter 7.7, pp. 324--343.
• 17: Peres, A. 1995. Quantum Theory: Concepts and Methods. Kluwer Academic Publishers, Norwell, Mass.
• 18: Preskill, J. 1998. Lecture notes. Available online at http://www.theory.caltech.edu/people/preskill/ph229/.
• 19: Wehrl, A. 1978. General properties of entropy. Rev. Mod. Phys. 50, 2, 221--260.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded)

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Theory, Verification

Keywords:
Automaton size, communication complexity, encoding, finite automata, quantum communication, quantum computation