کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
428521 686790 2014 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Parallelization of entanglement-resistant multi-prover interactive proofs
ترجمه فارسی عنوان
تقسیم اثبات های تعاملی چند ضلعی مقاوم در برابر انسداد
کلمات کلیدی
پیچیدگی محاسباتی، محاسبات کوانتومی، اثبات تعاملی، غیرقابل کوانتومی کوانتومی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی


• We study classical multi-prover interactive proofs which are sound also against entangled provers.
• Such interactive proofs have been studied widely in quantum complexity theory.
• We prove such interactive proofs can be parallelized to two rounds by adding one prover.

Multi-prover interactive proof systems are said to be entanglement-resistant if the soundness holds even when provers are allowed to share an arbitrary quantum state before the interaction starts. This letter proves that every entanglement-resistant multi-prover interactive proof system can be parallelized to two rounds without ruining its entanglement resistance at the expense of adding one prover.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 114, Issue 10, October 2014, Pages 579–583
نویسندگان
,