Proving the Power of Postselection

• Autorzy: Yakaryılmaz A. , Say A. C. C.
• Języki publikacji: EN

Abstrakty

EN

It is a widely believed, though unproven, conjecture that the capability of postselection increases the language recognition power of both probabilistic and quantum polynomial-time computers. It is also unknown whether polynomial-time quantum machines with postselection are more powerful than their probabilistic counterparts with the same resource restrictions. We approach these problems by imposing additional constraints on the resources to be used by the computer, and are able to prove for the first time that postselection does augment the computational power of both classical and quantum computers, and that quantum does outperform probabilistic in this context, under simultaneous time and space bounds in a certain range. We also look at postselected versions of space-bounded classes, as well as those corresponding to error-free and one-sided error recognition, and provide classical characterizations. It is shown that NL would equal RL if the randomized machines had the postselection capability.

Słowa kluczowe

EN

postselection; quantum Turing machines; probabilistic Turing machines; space-bounded; computation; one-sided error; zero error

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 123, nr 1
• Strony: 107--134
• Opis fizyczny: Bibliogr. 47 poz., tab.

Twórcy

autor

Yakaryılmaz A.

• Faculty of Computing University of Latvia Raina bulv. 19, Rıga, LV-1586, Latvia

autor

Say A. C. C.

• Department of Computer Engineering Bogazici University Bebek 34342 ˙Istanbul, Turkey

Bibliografia

• [1] Aanderra, S. O.: On k-tape versus (k-1)-tape real time computation, SIAM AMS Proceedings (R. M. Karp, Ed.), 7 (Complexity of Computation), 1974.
• [2] Aaronson, S.: Quantum computing, postselection, and probabilistic polynomial-time, Proceedings of the Royal Society A, 461(2063), 2005, 3473–3482.
• [3] Adleman, L. M., DeMarrais, J., Huang, M.-D. A.: Quantum computability, SIAM Journal on Computing, 26(5), 1997, 1524–1540.
• [4] Alt, H., Geffert, V., Mehlhorn, K.: A lower bound for the nondeterministic space complexity of context-free recognition, Information Processing Letters, 42(1), 1992, 25–27.
• [5] Ambainis, A.,Watrous, J.: Two–way finite automata with quantum and classical states, Theoretical Computer Science, 287(1), 2002, 299–311.
• [6] Bernstein, E., Vazirani, U.: Quantum complexity theory, SIAM Journal on Computing, 26(5), 1997, 1411–1473.
• [7] Blondel, V. D., Jeandel, E., Koiran, P., Portier, N.: Decidable and undecidable problems about quantum automata, SIAM Journal on Computing, 34(6), 2005, 1464–1473.
• [8] Bozapalidis, S.: Extending stochastic and quantum functions, Theory of Computing Systems, 36(2), 2003, 183–197.
• [9] Bruda, S. D.: Parallel Real-Time Complexity Theory, Ph.D. Thesis, Queen’s University at Kingston, 2002.
• [10] Brun, T. A., Wilde, M. M.: Perfect state distinguishability and computational speedups with postselected closed timelike curves, Foundations of Physics, 42, 2012, 341–361.
• [11] Bruss, A. R., Meyer, A. R.: On time-space classes and their relation to the theory of real addition, Theoretical Computer Science, 11(1), May 1980, 59–69.
• [12] Diehl, S., van Melkebeek, D.: Time-space lower bounds for the polynomial-time hierarchy on randomized machines, SIAM Journal on Computing, 36(3), 2006, 563–594.
• [13] Dwork, C., Stockmeyer, L.: A time complexity gap for two-way probabilistic finite-state automata, SIAM Journal on Computing, 19(6), 1990, 1011–1123.
• [14] Fliess, M.: Automates stochastiques et séries rationnelles non commutatives, Automata, Languages, and Programming, 1972, 397–411.
• [15] Fliess, M.: Propriétés booléennes des langages stochastiques, Mathematical Systems Theory, 7(4), 1974, 353–359.
• [16] Fortnow, L., Santhanam, R.: Recent work on hierarchies for semantic classes, ACM SIGACT News, 37(3), 2006, 36–54.
• [17] Freivalds, R.: Space and reversal complexity of probabilistic one-way Turing machines, Annals of Discrete Mathematics, 24, 1985, 39–50.
• [18] Freivalds, R., Karpinski, M.: Lower space bounds for randomized computation, ICALP’94: Proceedings of the 21st International Colloquium on Automata, Languages and Programming, 1994, 580–592.
• [19] Freivalds, R., Yakaryılmaz, A., Say, A. C. C.: A new family of nonstochastic languages, Information Processing Letters, 110(10), 2010, 410–413.
• [20] Gill, J.: Computational complexity of probabilistic Turing machines, SIAM Journal on Computing, 6(4), 1977, 675–695.
• [21] Goldreich, O.: Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008.
• [22] Jeandel, E.: Topological automata, Theory of Computing Systems, 40(4), 2007, 397–407.
• [23] Kan¸eps, J.: Stochasticity of the languages acceptable by two-way finite probabilistic automata, Discrete Mathematics and Applications, 1, 1991, 405–421.
• [24] Kondacs, A., Watrous, J.: On the power of quantum finite state automata, FOCS’97: Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997, 66–75.
• [25] Lāce, L., Scegulnaja-Dubrovska, O., Freivalds, R.: Languages recognizable by quantum finite automata with cut-point 0, SOFSEM’09: Proceedings of the 35th International Conference on Current Trends in Theory and Practice of Computer Science, 2, 2009, 35–46.
• [26] Lapiņš, J.: On nonstochastic languages obtained as the union and intersection of stochastic languages, Avtom. Vychisl. Tekh., (4), 1974, 6–13, (Russian).
• [27] van Melkebeek, D., Watson, T.: A quantum time-space lower bound for the counting hierarchy, Electronic Colloquium on Computational Complexity (ECCC), 15(017), 2008, Available at http://eccc.hpi-web.de/ecccreports/2008/TR08-017/index.html.
• [28] Nielsen, M. A., Chuang, I. L.: Quantum Computation and Quantum Information, Cambridge University Press, 2000.
• [29] Rabin, M. O.: Probabilistic automata, Information and Control, 6, 1963, 230–243.
• [30] Rabin, M. O.: Real time computation, Israel Journal of Mathematics, 1(4), 1963, 203–211.
• [31] Saks, M.: Randomization and derandomization in space-bounded computation, Proceedings of the 11th Annual IEEE Conference on Computational Complexity, 1996, 128–149.
• [32] Scegulnaja-Dubrovska, O., Freivalds, R.: A context-free language not recognizable by postselection finite quantum automata, Randomized and quantum computation (R. Freivalds, Ed.), 2010, 35–48, Satellite workshop of MFCS and CSL 2010.
• [33] Scegulnaja-Dubrovska, O., L¯ace, L., Freivalds, R.: Postselection finite quantum automata, Unconventional Computation, 6079 of LNCS, 2010, 115–126.
• [34] Shor, P. W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Journal on Computing, 26(5), 1997, 1484–1509.
• [35] Sipser, M.: Introduction to the Theory of Computation, 2nd edition, Thomson Course Technology, United States of America, 2006.
• [36] Turakainen, P.: Discrete Mathematics, vol. 7 of Banach Center Publications, chapter Rational stochastic automata in formal language theory, PWN-Polish Scientific Publishers, Warsaw, 1982, 31–44.
• [37] Žák, S.: A Turing machine time hierarchy, Theoretical Computer Science, 26(3), 1983, 327–333.
• [38] Watrous, J.: Space-bounded quantum complexity, Journal of Computer and System Sciences, 59(2), 1999, 281–326.
• [39] Watrous, J.: On the complexity of simulating space-bounded quantum computations, Computational Complexity, 12(1-2), 2003, 48–84.
• [40] Watrous, J.: Quantum computational complexity, in: Encyclopedia of Complexity and Systems Science (R. A. Meyers, Ed.), Springer, 2009, 7174–7201.
• [41] Yakaryılmaz, A., Say, A. C. C.: Languages recognized by nondeterministic quantum finite automata, Quantum Information and Computation, 10(9&10), 2010, 747–770.
• [42] Yakaryılmaz, A., Say, A. C. C.: Probabilistic and quantum finite automata with postselection, Randomized and quantum computation (R. Freivalds, Ed.), 2010, Satellite workshop of MFCS and CSL 2010.
• [43] Yakaryılmaz, A., Say, A. C. C.: Succinctness of two-way probabilistic and quantum finite automata, Discrete Mathematics and Theoretical Computer Science, 12(2), 2010, 19–40.
• [44] Yakaryılmaz, A., Say, A. C. C.: Probabilistic and quantum finite qutomata with postselection, Technical report, 2011, arXiv:1102.0666.
• [45] Yakaryılmaz, A., Say, A. C. C.: Unbounded-error quantum computation with small space bounds, Information and Computation, 209(6), 2011, 873–892.
• [46] Yamakami, T., Yao, A. C.-C.: NQPC = co-C=P, Information Processing Letters, 71(2), 1999, 63–69.
• [47] Yao, A. C.-C.: Quantum circuit complexity, SFCS’93: Proceedings of the 1993 IEEE 34th Annual Symposium on Foundations of Computer Science, 1993, 352–361.