Abstract
The main purpose of this paper is to show that we can ex- ploit the difference in the probability calculation between quantum and probabilistic computations to claim the difference in their space efficien- cies. It is shown that, for each n, there is a finite language L which contains sentences of length up to O(n c+1) such that: (i) There is a one- way quantum finite automaton (qfa) of O(n c+4) states which recognizes L. (ii) However, if we try to simulate this qfa by a probabilistic finite au tomaton (pfa) using the same algorithm, then it needs Ω(n 2c+4) states. It should be noted that we do not prove real lower bounds for pfa’s but show that if pfa’s and qfa’s use exactly the same algorithm, then qfa’s need much less states.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
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, 332–341, 1998.
F. Ablayev and A. Gainutdinova, “On the Lower Bounds for One-Way Quantum Automata”, Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science, 132–140, 2000.
M. Amano and K. Iwama, “Undecidability on Quantum Finite Automata”, Proceedings of the 31st ACM Symposium on Theory of Computing, 368–375, 1999.
A. Ambainis, A. Nayak, A. Ta-Shma and U. Vazirani, “Dense quantum coding and a lower bound for 1-way quantum automata”, Proceedings of the 31st ACM Symposium on Theory of Computing, 376–383, 1999.
L. Grover, “A fast quantum mechanical algorithm for database search,” Proceedings of the 28th ACM Symposium on Theory of Computing, 212–219, 1996.
E. Kushilevitz and N. Nisan, “Communication Complexity”, Cambridge University Press, 1997.
A. Kondacs and J. Watrous, “On the power of quantum finite state automata,” Proceedings of the 38th IEEE Conference on Foundations of Computer Science, 66–75, 1997.
A. Nayak, “Optimal lower bounds for quantum automata and random access codes”, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 369–376, 1999.
Author information
Authors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Amano, M., Iwama, K., Raymond, R. (2002). Exploiting the Difference in Probability Calculation between Quantum and Probabilistic Computations. In: Unconventional Models of Computation. UMC 2002. Lecture Notes in Computer Science, vol 2509. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45833-6_9
Download citation
DOI: https://doi.org/10.1007/3-540-45833-6_9
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44311-7
Online ISBN: 978-3-540-45833-3
eBook Packages: Springer Book Archive