کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874017 | 686415 | 2015 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
ترجمه فارسی عنوان
قدرت سیستم های اثبات تعاملی با تایید کننده ها توسط ماشین های اتوماتیک نیمه کوانتومی دوطرفه مدل شده است
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper we explore the power of AM for the case that verifiers are two-way finite automata with quantum and classical states (2QCFA) - introduced by Ambainis and Watrous in 2002 - and the communications are classical. It is of interest to consider AM with such “semi-quantum” verifiers because they use only limited quantum resources. Our main result is that such Quantum Arthur-Merlin proof systems (QAM(2QCFA)) with polynomial expected running time are more powerful than the models in which the verifiers are two-way probabilistic finite automata (AM(2PFA)) with polynomial expected running time. Moreover, we prove that there is a language which can be recognized by an exponential expected running time QAM(2QCFA), but cannot be recognized by any AM(2PFA), and that the NP-complete language Lknapsack can also be recognized by a QAM(2QCFA) working only on quantum pure states using unitary operators.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 241, April 2015, Pages 197-214
Journal: Information and Computation - Volume 241, April 2015, Pages 197-214
نویسندگان
Shenggen Zheng, Daowen Qiu, Jozef Gruska,