- 1.A. Ambainis. The complexity of probabilistic versus deterministic finite automata. Proceedings of the International Symposium on Algorithms and Computation (ISAAC'96), Lecture Notes in Computer Science 1178, 1996, pp. 233-239. Google ScholarDigital Library
- 2.A. Ambainis and R. Freivalds. 1-way quantum finite automata: strengths, weaknesses and generalizations. Proceedings of the 39th IEEE Conference on Foundations of Computer Science, 1998, pp. 332-341. Google ScholarDigital Library
- 3.C. Bennett, E. Bernstein, G. Brassaxd and U. Vazirani. Strengths and weaknesses of quantum computing. SIAM Journal on Computing 26(5), 1997, pp. 1510- 1523. Google ScholarDigital Library
- 4.E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM Journal on Computing 26(5), 1997, pp. 1411-1473. Google ScholarDigital Library
- 5.I.L. Chuang. Personal communication, I997.Google Scholar
- 6.G.D. Cohen. A nonconstructive upper bound on covering radius. IEEE Transactions on Information Theory IT-29(3), 1983, pp. 352-353.Google ScholarCross Ref
- 7.T.M. Cover and J.A. Thomas. Elements of information theory. Wiley, New York, 1991. Google ScholarDigital Library
- 8.R. Freivalds. On the growth of the number of states in result of determinization of probabilistic finite automata. Automatic Control and Computer Sciences 13(3)~ 1982, pp. 39-42.Google Scholar
- 9.A.S. Kholevo. Some estimates of the information transmitted by quantum communication channels. Problems o! Information Transmission 9, 1973.Google Scholar
- 10.A. K ondacs and J. Watrous. On the power of quantum finite state automata. Proceedings o! the 38th IEEE Conference on Foundations of Uomputer Science, 1997, pp. 66-75. Google ScholarDigital Library
- 11.C. Moore and J. Crutchfield. Quantum automata and quantum grammars.Santa-Fe Institute Working Paper 97-07-062, 1997. Also available at ht tp://xxx, lanl. gov/archly e/quant-ph/970703 :t. Google ScholarDigital Library
- 12.M.O. Rabin. Probabilistic automata. Information and Control 6~ 1963, pp. 230-245.Google Scholar
- 13.U. Vazirani. On the power of quantum computation. Philosophical Transactions oj~ the Royal Society of London, Series A 356, 1998, pp. 1759-1768.Google Scholar
- 14.J. Watrous. Relationships between quantum and classical space-bounded complexity classes. Proceedings o.f the I 3th IEEE Con}erence on Computational Complexity, 1998, pp. 210-227. Google ScholarDigital Library
Index Terms
- Dense quantum coding and a lower bound for 1-way quantum automata
Recommendations
Dense quantum coding and quantum finite automata
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 ...
Characterizations of 1-Way Quantum Finite Automata
The 2-way quantum finite automaton introduced by Kondacs and Watrous [ Proceedings of the 38 th Annual Symposium on Foundations of Computer Science , 1997, IEEE Computer Society, pp. 66--75] can accept nonregular languages with bounded error in ...
Comments