دانلود ترجمه مقاله حل موضوع NP Complet و الگوریتم جدید کوآنتومی

  بخشی از ترجمه:  

در این مقاله ما به بازبینی یک الگوریتم کمیتی(کوانتم) برای حل مسائل NP-Complete و با پیچیدگی زمانی چند جمله ای پرداخته ایم. این پژوهش تقریباٌ ده سال است که در یک سری مقاله توسط پروفسور Igor Volovich ارائه شده است. مقدمه حدود بیست سال قبل من در شهر رم با پروفسور Igor Volovich ملاقات کردم. از آن زمان، ما با همدیگر بر ر روی فیزیک های اطلاعات کوانتم و ریاضی مشغول پژوهش بوده ایم. وی برای ادراک اساس خلقت، دارای چشمانی باز و ذهنی انعطاف پذیر است، و از این رو وی را میتوان یکی از فیزیک دانان ریاضی مهم در عصر حاضر مطرح کرد. من معمولاٌ از کار کردن با وی لذت میبرم. مهمترین کار مشارکتی ما با هم، پیدا کردن الگوریتمی به منظور حل مسئله ی NPC بوده است، که در این مقاله بازبینی شده است. هر مسئله ای که بتوان آنرا در زمان چند جمله ای و به وسیله ی یک ماشین تورینگ غیر قطعی حل کرد، میتوان به صورت چند جمله ای آنرا به یک مسئله ی NPC تبدیل کرد[١]. ، صرف نظر از اینکه یک الگوریتمی برای حل این مسئله در زمانی چند جمله ای برای بیش از سی سال وجود داشته است یا خیر، چنین مسائلی شناخته شده نیستند.

  بخشی از مقاله انگلیسی:  

۱٫ 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 [1]. 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 [6–۹, ۱۱, ۱۳, ۱۶] 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 [2] gave a quantum algorithm to solve the factoring problem in polynomial time which is not NP-complete but NP-intermediate. Ohya and Volovich [6, 7] 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 [8] 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. However, the problem one has to overcome there is that the desired output of computations could be a very small and one needs to amplify it to a reasonable large quantity so as to detect it. For this purpose, we proposed that the amplification in chaotic dynamics plays a constructive role in computations [6, 7]. Chaos and quantum decoherence are considered normally as the degrading effects which lead to an unwelcome increase of the error rate with the input size. However, in our case, it is not so. Our algorithm is constructive [10, 13] and uses the chaotic dynamics only as an amplifier of a certain amplitude. In Section 2, the SAT problem is explained. The quntum part of our algorithm is briefly reviewed in Section 3, and the part of amplification process by means of a chaos dynamics is discussed in Section 4. In the last section, we discuss further results on our algorithm [15, 16] and some application of ours to solve other problems such as factoring and searching problems [17–۲۰]. ∗The text was submitted by the author in English. **E-mail: mohy33321@yahoo.co.jp 161 162 OHYA 2. SAT PROBLEM For a given set X ≡ {x1, ··· , xn}, an element xk and its negation xk (k = 1, 2, ··· , n) are called literals and the set of all such literals is denoted by X = {x1, x1, ··· , xn, xn}. An element C ∈ F(X ), the set of all subsets of X , is called a clause. We take a truth assignment to all variables xk. If one can assign the truth value to at least one element of C, then C is called satisfiable. When C is satisfiable, the truth value t(C) of C is regarded as true, otherwise, that of C is false. Take the truth values as true ”۱”, false ”۰”. Then C is satisfiable iff t(C)=1. Let L = {0, 1} be a Boolean lattice with usual join ∨ and meet ∧; ε ∨ ε := max{ε, ε }, ε ∧ ε := min{ε, ε }, and t(x) be the truth value of a literal x in X. Namely, t is a Boolean homomorphism from X to {0, 1} with the property: t(x) ∨ t(x)=1 , ∀x ∈ X . Then the truth value of a clause C is written as t(C) ≡ ∨x∈Ct(x). Further the set C of all clauses Cj (j = 1, 2, ··· m) is called satisfiable iff the meet of all truth values of Cj is 1; t(C) ≡ ∧m j=1t(Cj )=1. Thus the SAT problem is written as follows: Definition 6. SAT Problem: Given a set X ≡ {x1, ··· , xn} and a set C = {C1, C2, ··· , Cm} of clauses, determine whether C is satisfiable or not. That is, this problem is to ask whether there exists a truth assignment t to make C satisfiable. 3. QUANTUM ALGORITHM Let 0 and 1 of the Boolean lattice L be denoted by the vectors |0 ≡ ⎛ ⎝ ۱ ۰ ⎞ ⎠ and |1 ≡ ⎛ ⎝ ۰ ۱ ⎞ ⎠ in the Hilbert space C2, respectively. That is, the vector |0 corresponds to falseness and |1 does to truth. An element x ∈ X can be denoted by 0 or 1, so by |0 or |1. In order to describe a clause C with at most n length by a quantum state, we need the n-tuple tensor product Hilbert space H≡⊗n 1C2. For instance, in the case of n = 2, given C = {x1, x2} with an assignment x1 = 0 and x2 = 1, then the corresponding quantum state vector is |0⊗|۱, so that the quantum state vector describing C is generally written by |C = |x1⊗|x2∈H with xk = 0 or 1 (k=1,2). The quantum computation is performed by a unitary gate constructed from several fundamental gates such as Not gate, Controlled-Not gate, Controlled-Controlled Not gate [11]. Once X ≡ {x1, ··· , xn} and C = {C1, C2, ··· , Cm} are given, the SAT is to find the vector |t(C)≡∧m j=1 ∨x∈Cj t(x), where t(x) is |0 or |1 when x = 0 or 1, respectively, and t(x) ∧ t(y) ≡ t(x ∧ y), t(x) ∨ t(y) ≡ t(x ∨ y). We consider the quantum algorithm for the SAT problem. Since we have n variables xk (k = 1, ··· , n) and a quantum computation produces some dust bits, the assignments of the n variables and the l dusts are represented by n qubits and l qubits, respectively, in the Hilbert space ⊗n 1C2⊗l 1C2. Moreover the resulting state vector |t(C) should be added in the last qubit, so that the total Hilbert space is H≡⊗n 1 C2 ⊗l 1 C2 ⊗ C2. p-ADIC NUMBERS, ULTRAMETRIC ANALYSIS AND APPLICATIONS Vol. 4 No. 2 2012 NEW QUANTUM ALGORITHM 163 Let us start the quantum computation of SAT problem from an initial vector |v0≡⊗n 1 |0 ⊗l 1 |0⊗|۰ when C is composed of n Boolean variables x1, ··· , xn. We apply the discrete Fourier transformation denoted by Ut ≡ ⊗n 1 √ ۱ ۲ ⎛ ⎝ ۱ ۱ ۱ −۱ ⎞ ⎠ to the part of the Boolean variables of the vector |v0, then the resulting state vector becomes |v ≡  Ut ⊗l 1 I  |v0 = ۱ √۲n ⊗n 1 (|0 + |۱) ⊗l 1 |0⊗|۰, where I is the identity matrix in C2. This vector can be written as |v = ۱ √۲n  ۱ x1,··· ,xn=0 ⊗n j=1 |xj  ⊗l 1 |0⊗|۰. Now, we perform the quantum computation to check the satisfiability, which will be done by a unitary operator Ut properly constructed by unitary gates. Then after the computation by Ut, the vector |v goes to |vt ≡ Ut |v = ۱ √۲n  ۱ x1,··· ,xn=0 Ut ⊗n j=1 |xj  ⊗l 1 |0⊗|۰ = ۱ √۲n  ۱ x1,··· ,xn=0 ⊗n j=1 |xj  ⊗l i=1 |yi⊗|t(x1, ··· , xn), where t(x1, ··· , xn) ≡ t(C) because C contains x1, ··· xn, and |yi are the dust bits produced by the computation. Note that the unitary operator Ut is concretely constructed [10, 11, 13]. The final step to check the satisfiability of C is to apply the projection E ≡ ⊗n+l 1 I ⊗ |۱ ۱| to the state |vt, mathematically equivalent, to compute the value vt| E |vt. If the vector E |vt exists or the value vt| E |vt is not 0, then we conclude that C is satisfiable. The value of vt| E |vt is r/2n with an integer r less than 2n, which is the probability to find the result t(x)=1, and it is often very small and is difficult to be detected even when it is not zero, so that we desire to have some way to amplify this value, if it is not zero. Let us simplify our notations. After the step (ii) the quantum computer will be in the state |vf  = ۱ − q2 |ϕ۰⊗|۰ + q |ϕ۱⊗|۱, where |ϕ۱ and |ϕ۰ are normalized n + l qubit states and q = r/2n. Effectively our problem is reduced to the following 1 qubit problem. We have the state |ψ = ۱ − q2 |0 + q |1 and we want to distinguish between the cases q = 0 and q > 0 (small positive number). In order to amplify the no-zero q, we proposed to combine quantum computer with a chaotic dynamics amplifier. Such a quantum chaos computer is a new model of computations and we demonstrated that the amplification is possible in the polynomial time [6, 7, 11].