New Quantum Algorithm Solving the NP Complete Problem

ABSTRACT

We review the quantum chaos algorithm solving the NP-complete problems in polynomial time. This work has been done in the series of papers with Professor Igor Volovich for nearly ten years .

INTRODUCTION

I met Professor Igor Volovich nearly 20 years ago in Roma, Italy. Since then we discussed and worked  together on quantum information and mathematical physics. He has open eye and flexible mind to catch the essence of existence, so he is one of the most important mathematical physicists in our time. I could always enjoy working together with him. Our most important joint work is to find the algorithm solving the NP- complete (NPC) problem, as reviewed in this paper. Any problem that can be solved in polynomial time by a nondeterministic Turing machine is polynomially transformed to an NPC problem . These NPC problems are not known whether there exists an algorithm to solve this problem in a polynomial time for more than thirty years. Among the NP-complete problems, there are famous problems such as the knapsack problem, the travelling salesman problem, the integer programming problem, the subgraph isomorphism problem, the satisfiability (SAT) problem that have been studied for several decades, for which all known algorithms do not have polynomial running time in the length of the input. These NP-complete problems are known to be equivalent, and it has been considered that such problems are very difficult and probably need exponential time to solve them. In the series of papers  we found the algorithms to solve the NPC problems in polynomial time. In this paper we review the essence of these works done with I. Volovich. It is widely believed that quantum computers are more efficient than classical computers. In particular, Shor  gave a quantum  algorithm to solve the factoring problem in polynomial time which is not NP-complete but NP-intermediate. Ohya and Volovich  proposed a new method of quantum computation including a chaotic dynamics  (amplifier). Our quantum algorithm succeeded to solve the SAT problem in a polynomial time. It was first shown in  that the SAT problem can be solved in polynomial time by using a quantum computing under the assumption that a special superposition of two orthogonal vectors can be physically detected.

چکیده

ما الگوریتم کوانتومی هرج و مرج را حل مسئله NP کامل در زمان چند جمله ای. این کار را در مجموعه مقالات با پروفسور ایگور Volovich تقریبا ده سال انجام شده است.

مقدمه

پروفسور ایگور ولویویچ نزدیک 20 سال پیش در رم ایتالیا ملاقات کرد. از آن به بعد ما درباره ی اطلاعات کوانتومی و فیزیک ریاضی بحث و گفت و گو کردیم. او چشم باز و ذهن انعطاف پذیر برای جوهر وجود دارد، بنابراین او یکی از مهمترین فیزیکدانان ریاضی در زمان ما است. من همیشه می توانستم با او کار کنم. مهم ترین کار مشترک ما پیدا کردن الگوریتم حل NP-کامل (NPC) مشکل، به عنوان بررسی شده در این مقاله. هر مشکل که می تواند در زمان چند جمله ای توسط یک ماشین تورینگ غیرمتمرکز حل شود، به صورت چندجملهای به یک مشکل NPC تبدیل می شود. این مشکلات NPC شناخته شده نیست که آیا یک الگوریتم برای حل این مشکل در یک زمان چندجملهای برای بیش از سی سال وجود دارد. از جمله مشکلات NP کامل، مشکلات معروف مانند مشکل حلقه بسته شدن، مشکل فروشنده فروشنده، مشکل برنامه نویسی عدد صحیح، مسئله ایسومورفیسم زیرگراف، مشکل رضایتمندی (SAT) که برای چندین دهه مورد مطالعه قرار گرفته است، که همه آنها شناخته شده اند الگوریتم ها زمان اجرای چند جملهای در طول ورودی را ندارند. این مسائل NP-complete معادل هستند و در نظر گرفته شده است که چنین مشکلات بسیار دشوار است و احتمالا نیاز به زمان دقیق برای حل آنها است. در مجموعه مقالات ما الگوریتم هایی برای حل مشکلات NPC در زمان چندجملهای یافتیم. در این مقاله، ماهیت این آثار با I. Volovich بررسی شده است. به طور گسترده ای معتقد است که رایانه های کوانتومی کارآمدتر از رایانه های کلاسیک هستند. به طور خاص، Shor یک الگوریتم کوانتومی برای حل مسئله فاکتور در زمان چندجملهای ارائه کرد که NP-complete نیست اما NP-midmediate. اوایا و ولویچ روش جدیدی از محاسبات کوانتومی شامل یک پویایی هرج و مرج (تقویت کننده) را پیشنهاد دادند. الگوریتم کوانتومی ما موفق به حل مشکل SAT در زمان چندجملهای شده است. در ابتدا نشان داده شد که با استفاده از یک محاسبات کوانتومی، می توان مشکل در SAT را در زمان چند جمله ای حل کرد. فرض این است که یک بردار ویژه دو بردار متعامد می تواند به لحاظ جسمی شناسایی شود.

Year: 2012

Publisher : ELSEVIER

By : M. Ohya

File Information: English Language/ 5 Page / size: 475 KB

Download

سال : 1391

ناشر : ELSEVIER

کاری از : آقای اوهیا

اطلاعات فایل : زبان انگلیسی / 5 صفحه / حجم : KB 475

لینک دانلود