NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Adiabatic Quantum Algorithms for the NP-Complete MIS, Exact Cover and 3SAT Problems Vicky Choi Department of Computer Science Virginia Tech Falls Church, VA July 23, 2010 !"#$! 1 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Outline 1 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT 2 Adiabatic Quantum Algorithm 3 Two Adiabatic Algorithms for EC3 Clause-violation based MIS-based 4 Avoid FQPT: Change Problem Hamiltonian !"#$! 2 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Outline 1 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT 2 Adiabatic Quantum Algorithm 3 Two Adiabatic Algorithms for EC3 Clause-violation based MIS-based 4 Avoid FQPT: Change Problem Hamiltonian !"#$! 3 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Exact Cover Input: A set of m elements, X = {c1 , c2 , . . . , cm }, a family of n subsets of X , S = {S1 , S2 , . . . , Sn }, where Si ⊂ X Question: Is there an exact cover of X ? That is, is there a subset I ⊆ {1, . . . , n} such that ∪i∈I Si = X , where Si ∩ Sj = ∅ for i = j ∈ I? Example X: 1 2 3 4 5 S1 1 2 4 S3 1 S6 4 3 1 2 3 5 2 S7 4 5 5 S5 3 S2 S4 !"#$! 4 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Exact Cover Input: A set of m elements, X = {c1 , c2 , . . . , cm }, a family of n subsets of X , S = {S1 , S2 , . . . , Sn }, where Si ⊂ X Question: Is there an exact cover of X ? That is, is there a subset I ⊆ {1, . . . , n} such that ∪i∈I Si = X , where Si ∩ Sj = ∅ for i = j ∈ I? Example X: 1 2 3 4 5 S1 1 2 4 S3 1 S6 4 3 1 2 3 5 2 S7 4 5 5 S5 3 S2 S4 !"#$! 5 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Exact Cover Input: A set of m elements, X = {c1 , c2 , . . . , cm }, a family of n subsets of X , S = {S1 , S2 , . . . , Sn }, where Si ⊂ X Question: Is there an exact cover of X ? That is, is there a subset I ⊆ {1, . . . , n} such that ∪i∈I Si = X , where Si ∩ Sj = ∅ for i = j ∈ I? Example X: 1 2 3 4 5 S1 1 2 4 S3 1 S6 4 3 1 2 3 5 2 S7 4 5 5 S5 3 S2 S4 !"#$! 6 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Exact Cover Input: A set of m elements, X = {c1 , c2 , . . . , cm }, a family of n subsets of X , S = {S1 , S2 , . . . , Sn }, where Si ⊂ X Question: Is there an exact cover of X ? That is, is there a subset I ⊆ {1, . . . , n} such that ∪i∈I Si = X , where Si ∩ Sj = ∅ for i = j ∈ I? Example X: 1 2 3 4 5 S1 1 2 4 S3 1 S6 4 3 1 2 3 5 2 S7 4 5 5 S5 3 S2 S4 Maximum-weight Independent Set(MIS) Problem !"#$! 7 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Maximum-weight Independent Set Problem Input: A graph G(= (V(G), E(G))), Bi is the weight of vertex i ∈ V(G) Output: A subset S ⊆ V(G) such that S is independent and the total weight of S (= i∈S Bi ) is maximized. independent: for i, j ∈ mis(G), ij ∈ E(G) Example X: 1 2 3 4 5 S1 1 2 4 S3 1 S6 4 3 4 5 1 2 3 5 2 S7 5 S5 3 S2 S4 !"#$! 8 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Positive 1-in-3SAT Input: A 3CNF boolean formula Ψ(x1 , . . . , xn ) = C1 ∧ . . . ∧ Cm , n variables xi ∈ {0, 1} and m clauses Ck Question: Is there an assignment such that there is exactly one variable in each clause is true? Example Ψ(x1 , . . . , x7 ) = C1 ∧ C2 ∧ C3 ∧ C4 ∧ C5 C1 = x1 ∨ x2 ∨ x3 , C2 = x1 ∨ x2 ∨ x4 , C3 = x3 ∨ x4 ∨ x5 C4 = x1 ∨ x3 ∨ x6 , C5 = x2 ∨ x6 ∨ x7 !"#$! 9 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Positive 1-in-3SAT Input: A 3CNF boolean formula Ψ(x1 , . . . , xn ) = C1 ∧ . . . ∧ Cm , n variables xi ∈ {0, 1} and m clauses Ck Question: Is there an assignment such that there is exactly one variable in each clause is true? Example Ψ(x1 , . . . , x7 ) = C1 ∧ C2 ∧ C3 ∧ C4 ∧ C5 C1 = x1 ∨ x2 ∨ x3 , C2 = x1 ∨ x2 ∨ x4 , C3 = x3 ∨ x4 ∨ x5 C4 = x1 ∨ x3 ∨ x6 , C5 = x2 ∨ x6 ∨ x7 x1 = x5 = x7 = 1 !"#$! 10 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A EC3: A Special Case of Exact Cover Recall: Exact Cover Input: A set of m elements, X = {c1 , c2 , . . . , cm }, a family of n subsets of X , S = {S1 , S2 , . . . , Sn }, where Si ⊂ X Question: Is there an exact cover of X ? EC3: each element ci ∈ X appears exactly in three subsets Example X: 1 2 3 4 5 Associate each set Si with a binary variable xi (Si ↔ xi ) S1 1 2 For each element ci ∈ X , let Si1 , Si2 , Si3 be the three sets that consist of ci . Define the corresponding clause Ci = xi1 ∨ xi2 ∨ xi3 . (ci ↔ Ci ) 4 S3 1 S6 4 3 1 2 3 5 2 S7 4 5 5 3 S2 S4 S5 c1 appears in S1 , S2 , S3 C1 = x1 ∨ x2 ∨ x3 !"#$! 11 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A EC3: A Special Case of Exact Cover Recall: Exact Cover Input: A set of m elements, X = {c1 , c2 , . . . , cm }, a family of n subsets of X , S = {S1 , S2 , . . . , Sn }, where Si ⊂ X Question: Is there an exact cover of X ? EC3: each element ci ∈ X appears exactly in three subsets Example X: 1 2 3 4 5 Associate each set Si with a binary variable xi (Si ↔ xi ) S1 1 2 For each element ci ∈ X , let Si1 , Si2 , Si3 be the three sets that consist of ci . Define the corresponding clause Ci = xi1 ∨ xi2 ∨ xi3 . (ci ↔ Ci ) 4 S3 1 S6 4 3 1 2 3 5 2 S7 4 5 5 3 S2 S4 S5 c1 appears in S1 , S2 , S3 C1 = x1 ∨ x2 ∨ x3 !"#$! 12 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Example (Positive 1-in-3SAT ≤P EC3 ≤P MIS) Ψ(x1 , . . . , x7 ) = C1 ∧ C2 ∧ C3 ∧ C4 ∧ C5 where C1 = x1 ∨ x2 ∨ x3 , C2 = x1 ∨ x2 ∨ x4 , C3 = x3 ∨ x4 ∨ x5 C4 = x1 ∨ x3 ∨ x6 , C5 = x2 ∨ x6 ∨ x7 For each variable xi , let Si be the set consisting of all clauses in which xi appears: e.g. S1 = {C1 , C2 , C4 } !"#$! 13 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Example (Positive 1-in-3SAT ≤P EC3 ≤P MIS) Ψ(x1 , . . . , x7 ) = C1 ∧ C2 ∧ C3 ∧ C4 ∧ C5 where C1 = x1 ∨ x2 ∨ x3 , C2 = x1 ∨ x2 ∨ x4 , C3 = x3 ∨ x4 ∨ x5 C4 = x1 ∨ x3 ∨ x6 , C5 = x2 ∨ x6 ∨ x7 For each variable xi , let Si be the set consisting of all clauses in which xi appears: e.g. S1 = {C1 , C2 , C4 } X: 1 2 3 4 5 S1 1 2 4 S3 1 S6 4 3 1 2 3 5 2 S7 4 5 5 S5 3 S2 S4 !"#$! 14 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Example (Positive 1-in-3SAT ≤P EC3 ≤P MIS) Ψ(x1 , . . . , x7 ) = C1 ∧ C2 ∧ C3 ∧ C4 ∧ C5 where C1 = x1 ∨ x2 ∨ x3 , C2 = x1 ∨ x2 ∨ x4 , C3 = x3 ∨ x4 ∨ x5 C4 = x1 ∨ x3 ∨ x6 , C5 = x2 ∨ x6 ∨ x7 For each variable xi , let Si be the set consisting of all clauses in which xi appears: e.g. S1 = {C1 , C2 , C4 } X: 1 2 3 4 5 S1 1 2 4 S3 1 S6 4 3 1 2 3 5 2 S7 4 5 5 S5 3 S2 S4 !"#$! 15 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Outline 1 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT 2 Adiabatic Quantum Algorithm 3 Two Adiabatic Algorithms for EC3 Clause-violation based MIS-based 4 Avoid FQPT: Change Problem Hamiltonian !"#$! 16 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Adiabatic Quantum Algorithm System Hamiltonian: H(t) = (1 − s(t))Hinit + s(t)Hproblem for t ∈ [0, T ], s(0) = 0, s(T ) = 1. 1 2 3 Initial Hamiltonian: H(0) = Hinit ground state known (easy to construct) Problem Hamiltonian: H(T ) = Hproblem ground state encodes the answer to the desired optimization problem Evolution path: s : [0, T ] −→ [0, 1], e.g., s(t) = Tt T : running time of the algorithm !"#$! 17 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Adiabatic Quantum Algorithm System Hamiltonian: H(t) = (1 − s(t))Hinit + s(t)Hproblem for t ∈ [0, T ], s(0) = 0, s(T ) = 1. 1 2 3 Initial Hamiltonian: H(0) = Hinit ground state known (easy to construct) Problem Hamiltonian: H(T ) = Hproblem ground state encodes the answer to the desired optimization problem Evolution path: s : [0, T ] −→ [0, 1], e.g., s(t) = Tt T : running time of the algorithm !"#$! 18 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Example 1 Initial Hamiltonian: Hinit = −(σ1x + σ2x + σ3x ) 2 Evoluation Path : s(t) = 3 Problem Hamiltonian: Hproblem = 5σ1z + 10σ2z + σ3z + 7σ1z σ2z + 7σ2z σ3z t T E(s1 , s2 , s3 ) = 5s1 + 10s2 + s3 + 7s1 s2 + 7s2 s3 , spin si ∈ {−1, +1} energy state 101 -18 100 -14 010 -10 001 -6 000 -2 110 6 011 14 111 30 |ψ(0) = 81 xi ∈{0,1} |x1 x2 x3 |ψ(T ) = |101 !"#$! 19 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Example 1 Initial Hamiltonian: Hinit = −(σ1x + σ2x + σ3x ) 2 Evoluation Path : s(t) = 3 Problem Hamiltonian: Hproblem = 5σ1z + 10σ2z + σ3z + 7σ1z σ2z + 7σ2z σ3z t T E(s1 , s2 , s3 ) = 5s1 + 10s2 + s3 + 7s1 s2 + 7s2 s3 , spin si ∈ {−1, +1} energy state 101 -18 100 -14 010 -10 001 -6 000 -2 110 6 011 14 111 30 |ψ(0) = 18 xi ∈{0,1} |x1 x2 x3 |ψ(T ) = |101 !"#$! 20 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Decomposed State Evolution Visualization (DeSEV) Decompose ground state: |ψ(s) = |αx (s)|2 = 1 αx (s)|x , x ∈{0,1}n x ∈{0,1}n 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 time 0.9 1 101(−18) 100(−14) 010(−10) 001(−6) 000(−2) 110(6) 011(14) state(energy) 111(30) !"#$! 21 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Adiabatic Running Time (ART) Adiabatic Theorem For s(t) = t/T . If T is “large” enough: T =O poly(n) 2 gmin where minimum spectral gap gmin = min (E1 (t) − E0 (t)), 0≤t≤T E0 (t) < E1 (t) < ... are the energy levels of H(t). Then the system remains “close” to the ground state of H(t). “Traditional” version: max0≤s≤1 | E1 (s)| dH ds |E0 (s) | ART(H) = max ||H(s)|| 2 0≤s≤1 gmin !"#$! 22 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Throughout this talk, we fix the initital Hamiltonian and evolution path, and vary the problem Hamiltonian: 1 Initial Hamiltonian: Hinit = − 2 Evoluation Path : s(t) = 3 Problem Hamiltonian x i∈V(G) σi t T Different problem Hamiltonians ⇒ different adiabatic algorithms for the same problem. !"#$! 23 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Outline 1 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT 2 Adiabatic Quantum Algorithm 3 Two Adiabatic Algorithms for EC3 Clause-violation based MIS-based 4 Avoid FQPT: Change Problem Hamiltonian !"#$! 24 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Given an instance of EC3: Ψ(x1 , . . . , xn ) = C1 ∧ . . . ∧ Cm Algorithm 1: Clause-violation based problem Hamiltonian HA : Bi σiz + HA = i∈V(GEC ) Iij σiz σjz (1) ij∈E(GEC ) Bi : #clauses that contains variable xi Iij : #clauses that contains both xi and xj (was called Jij = 21 (Jij + Jji )) Algorithm 2: MIS-reduction based problem Hamiltonian HC : HC = Jij − 2Bi σiz + i∈V(GEC ) j∈nbr(i) Jij σiz σjz (2) ij∈E(GEC ) where Jij > min{Bi , Bj }. Question: ART(Algorithm 1) ⇒ ART(Algorithm 2)? !"#$! 25 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Given an instance of EC3: Ψ(x1 , . . . , xn ) = C1 ∧ . . . ∧ Cm Algorithm 1: Clause-violation based problem Hamiltonian HA : Bi σiz + HA = i∈V(GEC ) Iij σiz σjz (1) ij∈E(GEC ) Bi : #clauses that contains variable xi Iij : #clauses that contains both xi and xj (was called Jij = 21 (Jij + Jji )) Algorithm 2: MIS-reduction based problem Hamiltonian HC : HC = Jij − 2Bi σiz + i∈V(GEC ) j∈nbr(i) Jij σiz σjz (2) ij∈E(GEC ) where Jij > min{Bi , Bj }. Question: ART(Algorithm 1) ⇒ ART(Algorithm 2)? !"#$! 26 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Given an instance of EC3: Ψ(x1 , . . . , xn ) = C1 ∧ . . . ∧ Cm Algorithm 1: Clause-violation based problem Hamiltonian HA : Bi σiz + HA = i∈V(GEC ) Iij σiz σjz (1) ij∈E(GEC ) Bi : #clauses that contains variable xi Iij : #clauses that contains both xi and xj (was called Jij = 21 (Jij + Jji )) Algorithm 2: MIS-reduction based problem Hamiltonian HC : HC = Jij − 2Bi σiz + i∈V(GEC ) j∈nbr(i) Jij σiz σjz (2) ij∈E(GEC ) where Jij > min{Bi , Bj }. Question: ART(Algorithm 1) ⇒ ART(Algorithm 2)? !"#$! 27 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Given an instance of EC3: Ψ(x1 , . . . , xn ) = C1 ∧ . . . ∧ Cm Algorithm 1: Clause-violation based problem Hamiltonian HA : Bi σiz + HA = i∈V(GEC ) Iij σiz σjz (1) ij∈E(GEC ) Bi : #clauses that contains variable xi Iij : #clauses that contains both xi and xj (was called Jij = 21 (Jij + Jji )) Algorithm 2: MIS-reduction based problem Hamiltonian HC : HC = Jij − 2Bi σiz + i∈V(GEC ) j∈nbr(i) Jij σiz σjz (2) ij∈E(GEC ) where Jij > min{Bi , Bj }. Question: ART(Algorithm 1) ⇒ ART(Algorithm 2)? !"#$! 28 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Algorithm 1: Altshuler et al. Energy function: m (xi1 + xi2 + xi3 − 1)2 EΨ (x1 , . . . , xn ) = i=1 penalizes each violating clause Ci = xi1 ∨ xi2 ∨ xi3 Bi σiz + HA = i∈V(GEC ) Iij σiz σjz ij∈E(GEC ) Bi : #clauses that contains variable xi Iij : #clauses that contains both xi and xj “While our argument immediately implies that a particular quantum adiabatic algorithm for EC3 will fail, it is important to note that it also applies to more general cases. In particular, it does not rely on the specific form of the problem Hamiltonian, but rather on its general statistical properties, so that it should extend to other !"#$! NP-complete problems such as 3-SAT. ” 29 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Algorithm 2: MIS-based Recall: Maximum Independent Set (unweighted) Problem Input: a graph G, V(G) = {1, 2, . . . , n}, Output: mis(G) ⊆ V(G), independent, |mis(G)| is maximized independent: for i, j ∈ mis(G), ij ∈ E(G) Example 1 2 5 3 4 6 !"#$! 30 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Quadratic Pseudo-boolean Function For i ∈ V(G), associate it with a binary variable xi ∈ {0, 1}. Define Y(x1 , . . . , xn ) = xi − i∈V(G) Jij xi xj ij∈E(G) Jij – penalty for the edge ij Example: for Jij = 2 Y(1, 0, 0, 0, 0, 1) = 2 1 Y(1, 1, 0, 0, 0, 1) = 1 + 1 − 2 + 1 = 1 2 3 Y(1, 0, 0, 1, 1, 1) = 4 5 4 6 !"#$! 31 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Quadratic Pseudo-boolean Function For i ∈ V(G), associate it with a binary variable xi ∈ {0, 1}. Define Y(x1 , . . . , xn ) = xi − i∈V(G) Jij xi xj ij∈E(G) Jij – penalty for the edge ij Example: for Jij = 2 Y(1, 0, 0, 0, 0, 1) = 2 1 Y(1, 1, 0, 0, 0, 1) = 1 + 1 − 2 + 1 = 1 2 3 Y(1, 0, 0, 1, 1, 1) = 4 5 4 6 !"#$! 32 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Quadratic Pseudo-boolean Function For i ∈ V(G), associate it with a binary variable xi ∈ {0, 1}. Define Y(x1 , . . . , xn ) = xi − i∈V(G) Jij xi xj ij∈E(G) Jij – penalty for the edge ij Example: for Jij = 2 Y(1, 0, 0, 0, 0, 1) = 2 1 Y(1, 1, 0, 0, 0, 1) = 1 + 1 − 2 + 1 = 1 2 3 Y(1, 0, 0, 1, 1, 1) = 4 5 4 6 !"#$! 33 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Quadratic Pseudo-boolean Function For i ∈ V(G), associate it with a binary variable xi ∈ {0, 1}. Define Y(x1 , . . . , xn ) = xi − i∈V(G) Jij xi xj . ij∈E(G) Theorem If Jij > 1 for all ij ∈ E(G), then |mis(G)| = max Y(x1 , . . . , xn ). and mis(G) = {i ∈ V(G) : xi∗ = 1}, where (x1∗ , . . . , xn∗ ) = argmax(x1 ,...,xn )∈{0,1}n Y(x1 , . . . , xn ). !"#$! 34 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Quadratic Pseudo-boolean Function For i ∈ V(G), associate it with a binary variable xi ∈ {0, 1}. Define Y(x1 , . . . , xn ) = xi − i∈V(G) Jij xi xj . ij∈E(G) Theorem If Jij > 1 for all ij ∈ E(G), then |mis(G)| = max Y(x1 , . . . , xn ). and mis(G) = {i ∈ V(G) : xi∗ = 1}, where (x1∗ , . . . , xn∗ ) = argmax(x1 ,...,xn )∈{0,1}n Y(x1 , . . . , xn ). !"#$! 35 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Quadratic Pseudo-boolean Function For i ∈ V(G), associate it with a binary variable xi ∈ {0, 1}. Define Y(x1 , . . . , xn ) = xi − i∈V(G) Jij xi xj . ij∈E(G) Theorem If Jij > 1 for all ij ∈ E(G), then |mis(G)| = max Y(x1 , . . . , xn ). and mis(G) = {i ∈ V(G) : xi∗ = 1}, where (x1∗ , . . . , xn∗ ) = argmax(x1 ,...,xn )∈{0,1}n Y(x1 , . . . , xn ). Generalize to weighted MIS problem !"#$! 36 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Theorem If Jij > min{Bi , Bj } for all ij ∈ E(G), then the maximum value of Y(x1 , . . . , xn ) = Bi xi − i∈V(G) Jij xi xj (3) ij∈E(G) is the total weight of the MIS, and mis(G) = {i ∈ V(G) : xi∗ = 1}, where (x1∗ , . . . , xn∗ ) = arg max(x1 ,...,xn )∈{0,1}n Y(x1 , . . . , xn ). Change variables: xi = 1+si 2 Min E(s1 , . . . , sn ) = (xi = 0 ⇔ si = −1, xi = 1 ⇔ si = +1) ( Jij − 2Bi )si + i∈V(G) j∈nbr(i) H= i∈V(G) j∈nbr(i) Jij si sj ij∈E(G) Jij − 2Bi σiz + Jij σiz σjz ij∈E(G) !"#$! 37 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Theorem If Jij > min{Bi , Bj } for all ij ∈ E(G), then the maximum value of Y(x1 , . . . , xn ) = Bi xi − i∈V(G) Jij xi xj (3) ij∈E(G) is the total weight of the MIS, and mis(G) = {i ∈ V(G) : xi∗ = 1}, where (x1∗ , . . . , xn∗ ) = arg max(x1 ,...,xn )∈{0,1}n Y(x1 , . . . , xn ). Change variables: xi = 1+si 2 Min E(s1 , . . . , sn ) = (xi = 0 ⇔ si = −1, xi = 1 ⇔ si = +1) ( Jij − 2Bi )si + i∈V(G) j∈nbr(i) H= i∈V(G) j∈nbr(i) Jij si sj ij∈E(G) Jij − 2Bi σiz + Jij σiz σjz ij∈E(G) !"#$! 38 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Theorem If Jij > min{Bi , Bj } for all ij ∈ E(G), then the maximum value of Y(x1 , . . . , xn ) = Bi xi − i∈V(G) Jij xi xj (3) ij∈E(G) is the total weight of the MIS, and mis(G) = {i ∈ V(G) : xi∗ = 1}, where (x1∗ , . . . , xn∗ ) = arg max(x1 ,...,xn )∈{0,1}n Y(x1 , . . . , xn ). Change variables: xi = 1+si 2 Min E(s1 , . . . , sn ) = (xi = 0 ⇔ si = −1, xi = 1 ⇔ si = +1) ( Jij − 2Bi )si + i∈V(G) j∈nbr(i) H= i∈V(G) j∈nbr(i) Jij si sj ij∈E(G) Jij − 2Bi σiz + Jij σiz σjz ij∈E(G) !"#$! 39 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Comparison: Algorithm 1 vs. Algorithm 2 Algorithm 1: Bi σiz + HA = i∈V(GEC ) Iij σiz σjz ij∈E(GEC ) Algorithm 2: HC = i∈V(GEC ) Jij − 2Bi σiz + j∈nbr(i) Jij σiz σjz ij∈E(GEC ) where Jij > min{Bi , Bj } Recall: 2Bi = j∈nbr(i) Iij Write Jij = 2Iij + Dij , for Dij > min{Bi , Bj } − 2Iij Dij σiz + HC = 2HA + i∈V(GEC ) j∈nbr(i) Does it matter if we choose different Dij ? Dij σiz σjz ij∈E(GEC ) !"#$! 40 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Comparison: Algorithm 1 vs. Algorithm 2 Algorithm 1: Bi σiz + HA = i∈V(GEC ) Iij σiz σjz ij∈E(GEC ) Algorithm 2: HC = i∈V(GEC ) Jij − 2Bi σiz + j∈nbr(i) Jij σiz σjz ij∈E(GEC ) where Jij > min{Bi , Bj } Recall: 2Bi = j∈nbr(i) Iij Write Jij = 2Iij + Dij , for Dij > min{Bi , Bj } − 2Iij Dij σiz + HC = 2HA + i∈V(GEC ) j∈nbr(i) Does it matter if we choose different Dij ? Dij σiz σjz ij∈E(GEC ) !"#$! 41 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Comparison: Algorithm 1 vs. Algorithm 2 Algorithm 1: Bi σiz + HA = i∈V(GEC ) Iij σiz σjz ij∈E(GEC ) Algorithm 2: HC = i∈V(GEC ) Jij − 2Bi σiz + j∈nbr(i) Jij σiz σjz ij∈E(GEC ) where Jij > min{Bi , Bj } Recall: 2Bi = j∈nbr(i) Iij Write Jij = 2Iij + Dij , for Dij > min{Bi , Bj } − 2Iij Dij σiz + HC = 2HA + i∈V(GEC ) j∈nbr(i) Does it matter if we choose different Dij ? Dij σiz σjz ij∈E(GEC ) !"#$! 42 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Computing spectral gap by perturbation Require computing the energy difference E12 (s) – depends on the energy function of the problem Hamiltonian. While the energy function for HA only depends on Bi and Iij , the energy function for HC also depends on Jij whose values have a range to choose. 4 is given by a sum of θ(N) random terms with zero “E12 mean” no longer applies here as Jij are not random. Example (2nd order correction) (2) using HA : Ex using HC : =− n i=1 1/Bi 1 Ex(2) = − {i:xi =0} Bi − {j∈nbr (i):xj =1} Jij + {i:xi =1} – depend on the connectivity of the graph, and the non-random choice of Jij 1 Bi !"#$! 43 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Computing spectral gap by perturbation Require computing the energy difference E12 (s) – depends on the energy function of the problem Hamiltonian. While the energy function for HA only depends on Bi and Iij , the energy function for HC also depends on Jij whose values have a range to choose. 4 is given by a sum of θ(N) random terms with zero “E12 mean” no longer applies here as Jij are not random. Example (2nd order correction) (2) using HA : Ex using HC : =− n i=1 1/Bi 1 Ex(2) = − {i:xi =0} Bi − {j∈nbr (i):xj =1} Jij + {i:xi =1} – depend on the connectivity of the graph, and the non-random choice of Jij 1 Bi !"#$! 44 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Outline 1 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT 2 Adiabatic Quantum Algorithm 3 Two Adiabatic Algorithms for EC3 Clause-violation based MIS-based 4 Avoid FQPT: Change Problem Hamiltonian !"#$! 45 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A 15-Vertex CK Graph 7 8 10 9 11 13 12 14 1 3 5 2 4 6 15 (a) (b) Figure 1: (a) A CK graph for r = 3 and g = 3. The graph consists of 15 vertices: VA = {1, . . . , 6} forms an set of size 6, while V , consisting of g(= 3) groups of r(= 3) triangles: {7, 8, 9}, {10, 11, 12}, Vindependent A = {1, . . . , 6} : •, BwA = 1 and {13, 14, 15}, forms 33 independent sets of size 3. The graph is connected as follows. The 6 vertices in VVABare=divided {7, .into . . 3, 15}: ≤4},wand 2 The vertices in each group are adjacent to vertices groups: {1, ,2},1{3, {5, 6}. B < in two groups of three triangles in VB (as illustrated by different colors). (b) The drawing of the graph with The corresponding Hamiltonian: explicit connections. The weight of a vertex in VA (VB resp.) is wA (wB resp.). We set wA = 1, and consider 1 ≤ wB < 2. For explanation purpose, we represent a vertex in VA by a •, and a vertex in VB by a . Therefore, z MIS of weight 6; while { , , z } is a maximal independent •, •, }, HVA1 =={•, •, •, •,(6J −forms 2)σthe (6J − 2wB )σi + J σiz σjz set of weight i + 3wB (< 6). i∈VA i∈VB ij∈E(G) !"#$! Notation on represent the computational states. For a computational state |x1 x2 . . . xn where xi ∈ {0, 1}, Here we weadopt fixtheJzero J =representation, 2 > wB for all ij ∈ E(G). ij =position namely, represent it by |i i . . . i where x = 0 if and only if j = i 1 2 k j t 50 for some t. That is, we represent |000000111111111 (the solution state) by |123456 . Further, we use 46 a •/ to NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A 15-Vertex CK Graph 7 8 10 9 11 13 12 14 1 3 5 2 4 6 15 (a) (b) Figure 1: (a) A CK graph for r = 3 and g = 3. The graph consists of 15 vertices: VA = {1, . . . , 6} forms an set of size 6, while V , consisting of g(= 3) groups of r(= 3) triangles: {7, 8, 9}, {10, 11, 12}, Vindependent A = {1, . . . , 6} : •, BwA = 1 and {13, 14, 15}, forms 33 independent sets of size 3. The graph is connected as follows. The 6 vertices in VVABare=divided {7, .into . . 3, 15}: ≤4},wand 2 The vertices in each group are adjacent to vertices groups: {1, ,2},1{3, {5, 6}. B < in two groups of three triangles in VB (as illustrated by different colors). (b) The drawing of the graph with The corresponding Hamiltonian: explicit connections. The weight of a vertex in VA (VB resp.) is wA (wB resp.). We set wA = 1, and consider 1 ≤ wB < 2. For explanation purpose, we represent a vertex in VA by a •, and a vertex in VB by a . Therefore, z MIS of weight 6; while { , , z } is a maximal independent •, •, }, HVA1 =={•, •, •, •,(6J −forms 2)σthe (6J − 2wB )σi + J σiz σjz set of weight i + 3wB (< 6). i∈VA i∈VB ij∈E(G) !"#$! Notation on represent the computational states. For a computational state |x1 x2 . . . xn where xi ∈ {0, 1}, Here we weadopt fixtheJzero J =representation, 2 > wB for all ij ∈ E(G). ij =position namely, represent it by |i i . . . i where x = 0 if and only if j = i 1 2 k j t 50 for some t. That is, we represent |000000111111111 (the solution state) by |123456 . Further, we use 47 a •/ to NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A FQPT (Zoom:s = 0.627 . . . 0.628) First Excited State First Excited State 1 1 0.8 Γ Γ 0.6 0.5 0.4 0.2 0 0 0.627 0 0.6272 0.2 0.6274 0.4 0.6276 0.6 0.8 1 time s 5.46 5.2 4.85 3.84 0.6278 0.628 time s 3.8 4 4.8 5 5.2 5.4 6 (−)energy (−)energy Ground State Ground State 1 1 0.6 Γ Γ 0.8 0.5 0.4 0.2 0 0 0 0.627 0.2 0.6272 0.4 0.6 0.8 time s 1 6 5.25.4 4.85 3.84 (−)energy s ∗ = 0.6276, gmin = 1.04 × 10−5 0.6274 0.6276 0.6278 0.628 time s 3.8 4 4.8 5 5.2 5.4 6 (−)energy !"#$! 48 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Change Parameter... Avoid FQPT: gmin = 10−5 → 10−1 J =2 J = 20 First Excited State First Excited State 1 0.8 1 Γ Γ 0.6 0.4 0.5 0.2 0 0 0 0.2 0 0.2 0.4 0.4 0.6 0.6 6 5.25.4 4.85 3.84 0.8 1 time s 0.8 1 3/k time s 4/k 3.8/k 3.6/k 5/k 6/k 5.4/k (−)energy (−)energy Ground State Ground State 1 1 0.6 Γ Γ 0.8 0.5 0.4 0.2 0 0 0 0 0.2 0.2 0.4 0.6 0.8 4.85 3.84 1 time s 0.4 6 5.25.4 0.6 0.8 1 (−)energy time s 3/k 4/k 3.8/k 3.6/k 5/k 6/k 5.4/k (−)energy s ∗ = 0.627637, gmin = 1.04 × 10−5 J =2 | • • • •• + | J = 20 |•••• − − | − | • • • •• s ∗ = 0.667731, gmin = 0.145 | |•••••• | |•••••• !"#$! 49 / 50 NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 A Acknowledgements Students in my AQC class: Siyuan Han Peter Young David Kirkpatrick David Sankoff D-Wave Systems Inc. Robert Rausendorff and his group members !"#$! 50 / 50
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- Canadian Summer School on Quantum Information (CSSQI) (10th : 2010) /
- Adiabatic Quantum Algorithms for the NP-Complete MIS,...
Open Collections
Canadian Summer School on Quantum Information (CSSQI) (10th : 2010)
Adiabatic Quantum Algorithms for the NP-Complete MIS, Exact Cover and 3SAT Problems Choi, Vicky Jul 23, 2010
Page Metadata
Item Metadata
Title | Adiabatic Quantum Algorithms for the NP-Complete MIS, Exact Cover and 3SAT Problems |
Creator |
Choi, Vicky |
Contributor | University of British Columbia. Department of Physics and Astronomy Workshop on Quantum Algorithms, Computational Models and Foundations of Quantum Mechanics Pacific Institute for the Mathematical Sciences |
Date Issued | 2010-07-23 |
Description | The problem Hamiltonian of the adiabatic quantum algorithm for the maximum-weight independent set problem (MIS) that is based on the reduction to the Ising problem (as described in [Choi08]) has flexible parameters. We show that by choosing the parameters appropriately in the problem Hamiltonian (without changing the problem to be solved) for MIS on CK graphs, we can prevent the first order quantum phase transition and significantly change the minimum spectral gap. We raise the basic question about what the appropriate formulation of adiabatic running time should be. We also describe adiabatic quantum algorithms for Exact Cover and 3SAT in which the problem Hamiltonians are based on the reduction to MIS. We point out that the argument in Altshuler et al.(arXiv:0908.2782 [quant-ph]) that their adiabatic quantum algorithm failed with high probability for randomly generated instances of Exact Cover does not carry over to this new algorithm. |
Subject |
Adiabatic Quantum Algorithm NP-complete Maximum Independent Set Exact Cover 3SAT |
Genre |
Presentation |
Type |
Text Still Image Sound Moving Image |
Language | eng |
Date Available | 2016-11-22 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0103157 |
URI | http://hdl.handle.net/2429/30067 |
Affiliation |
Non UBC |
Peer Review Status | Unreviewed |
Scholarly Level | Faculty |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 59370-WS Jul 23 Choi.mp4 [ 73.83MB ]
- 59370-Choi_QAMF.pdf [ 2.75MB ]
- Metadata
- JSON: 59370-1.0103157.json
- JSON-LD: 59370-1.0103157-ld.json
- RDF/XML (Pretty): 59370-1.0103157-rdf.xml
- RDF/JSON: 59370-1.0103157-rdf.json
- Turtle: 59370-1.0103157-turtle.txt
- N-Triples: 59370-1.0103157-rdf-ntriples.txt
- Original Record: 59370-1.0103157-source.json
- Full Text
- 59370-1.0103157-fulltext.txt
- Citation
- 59370-1.0103157.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.59370.1-0103157/manifest