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

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

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

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  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

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>
                        
                    
IIIF logo 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

Comment

Related Items