×

Superiority of exact quantum automata for promise problems. (English) Zbl 1237.68082

Summary: In this note we present an infinite family of promise problems which can be solved exactly by just tuning transition amplitudes of a two-state quantum finite automaton operating in realtime mode, whereas the size of the corresponding classical automata grows without bound.

MSC:

68Q12 Quantum algorithms and complexity in the theory of computing
68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] A. Ambainis, R. Freivalds, 1-way quantum finite automata: strengths, weaknesses and generalizations, in: FOCSʼ98: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998, pp. 332-341.; A. Ambainis, R. Freivalds, 1-way quantum finite automata: strengths, weaknesses and generalizations, in: FOCSʼ98: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998, pp. 332-341.
[2] R. Beals, H. Buhrman, R. Cleve, M. Mosca, R. de Wolf, Quantum lower bounds by polynomials, in: FOCSʼ98: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998, pp. 352-361.; R. Beals, H. Buhrman, R. Cleve, M. Mosca, R. de Wolf, Quantum lower bounds by polynomials, in: FOCSʼ98: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998, pp. 352-361. · Zbl 1127.68404
[3] Bernstein, E.; Vazirani, U., Quantum complexity theory, SIAM Journal on Computing, 26, 5, 1411-1473 (1997) · Zbl 0895.68042
[4] Bertoni, A.; Mereghetti, C.; Palano, B., Quantum computing: 1-way quantum automata, (Ésik, Z.; Fülöp, Z., Developments in Language Theory. Developments in Language Theory, Lecture Notes in Computer Science, vol. 2710 (2003)), 1-20 · Zbl 1037.68058
[5] G. Brassard, P. Hoyer, An exact quantum polynomial-time algorithm for Simonʼs problem, in: ISTCSʼ97: Proceedings of the Fifth Israel Symposium on the Theory of Computing Systems, 1997, pp. 12-23.; G. Brassard, P. Hoyer, An exact quantum polynomial-time algorithm for Simonʼs problem, in: ISTCSʼ97: Proceedings of the Fifth Israel Symposium on the Theory of Computing Systems, 1997, pp. 12-23.
[6] H. Buhrman, R. Cleve, R. de Wolf, C. Zalka, Bounds for small-error and zero-error quantum algorithms, in: FOCSʼ99: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999, pp. 358-359.; H. Buhrman, R. Cleve, R. de Wolf, C. Zalka, Bounds for small-error and zero-error quantum algorithms, in: FOCSʼ99: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999, pp. 358-359.
[7] Buhrman, H.; de Wolf, R., Quantum zero-error algorithms cannot be composed, Information Processing Letters, 87, 79-84 (2003) · Zbl 1175.68182
[8] M.P. Ciamarra, Quantum reversibility and a new model of quantum automaton, in: FCTʼ01: Proceedings of the 13th International Symposium on Fundamentals of Computation Theory, 2001, pp. 376-379.; M.P. Ciamarra, Quantum reversibility and a new model of quantum automaton, in: FCTʼ01: Proceedings of the 13th International Symposium on Fundamentals of Computation Theory, 2001, pp. 376-379. · Zbl 0999.68512
[9] R. Freivalds, K. Iwama, Quantum queries on permutations with a promise, in: CIAAʼ09: Proceedings of the 14th International Conference on Implementation and Application of Automata, 2009, pp. 208-216.; R. Freivalds, K. Iwama, Quantum queries on permutations with a promise, in: CIAAʼ09: Proceedings of the 14th International Conference on Implementation and Application of Automata, 2009, pp. 208-216. · Zbl 1248.68199
[10] Hirvensalo, M., Quantum automata with open time evolution, International Journal of Natural Computing Research, 1, 1, 70-85 (2010)
[11] H. Klauck, On quantum and probabilistic communication: Las Vegas and one-way protocols, in: STOCʼ00: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pp. 644-651.; H. Klauck, On quantum and probabilistic communication: Las Vegas and one-way protocols, in: STOCʼ00: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pp. 644-651. · Zbl 1296.68058
[12] A. Kondacs, J. Watrous, On the power of quantum finite state automata, in: FOCSʼ97: Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997, pp. 66-75.; A. Kondacs, J. Watrous, On the power of quantum finite state automata, in: FOCSʼ97: Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997, pp. 66-75.
[13] Moore, C.; Crutchfield, J. P., Quantum automata and quantum grammars, Theoretical Computer Science, 237, 1-2, 275-306 (2000) · Zbl 0939.68037
[14] Murakami, Y.; Nakanishi, M.; Yamashita, S.; Watanabe, K., Quantum versus classical pushdown automata in exact computation, IPSJ Digital Courier, 1, 426-435 (2005)
[15] Watrous, J., Quantum computational complexity, (Meyers, R. A., Encyclopedia of Complexity and Systems Science (2009), Springer), 7174-7201
[16] Yakaryılmaz, A.; Freivalds, R.; Say, A. C.C.; Agadzanyan, R., Quantum computation with devices whose contents are never read, (Unconventional Computation. Unconventional Computation, Lecture Notes in Computer Science, vol. 6079 (2010)), 164-174 · Zbl 1286.68148
[17] Yakaryılmaz, A.; Say, A. C.C., Unbounded-error quantum computation with small space bounds, Information and Computation, 209, 6, 873-892 (2011) · Zbl 1221.68092
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.