!"#$! NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 Avoid FQPT: Change Problem Hamiltonian 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 Avoid FQPT: Change Problem Hamiltonian 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 Avoid FQPT: Change Problem Hamiltonian 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 Avoid FQPT: Change Problem Hamiltonian 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∈ISi = X , where Si ∩ Sj = ∅ for i 6= j ∈ I? Example 4 3 5 54 32 3 5 41 21 5 1 2 4321 S S5 S7 3S X: S1 S2 S6 4 4 / 50 !"#$! NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 Avoid FQPT: Change Problem Hamiltonian 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∈ISi = X , where Si ∩ Sj = ∅ for i 6= j ∈ I? Example 4 3 5 54 32 3 5 41 21 5 1 2 4321 S S5 S7 3S X: S1 S2 S6 4 5 / 50 !"#$! NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 Avoid FQPT: Change Problem Hamiltonian 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∈ISi = X , where Si ∩ Sj = ∅ for i 6= j ∈ I? Example 4 3 5 54 32 3 5 41 21 5 1 2 4321 S S5 S7 3S X: S1 S2 S6 4 6 / 50 !"#$! NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 Avoid FQPT: Change Problem Hamiltonian 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∈ISi = X , where Si ∩ Sj = ∅ for i 6= j ∈ I? Example 4 3 5 54 32 3 5 41 21 5 1 2 4321 S S5 S7 3S X: S1 S2 S6 4 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 Avoid FQPT: Change Problem Hamiltonian 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 6∈ E(G) Example 4 3 5 54 32 3 5 41 21 5 1 2 4321 S S5 S7 3S X: S1 S2 S6 4 8 / 50 !"#$! NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 Avoid FQPT: Change Problem Hamiltonian 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 Avoid FQPT: Change Problem Hamiltonian 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 Avoid FQPT: Change Problem Hamiltonian 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 4 3 5 54 32 3 5 41 21 5 1 2 4321 S S5 S7 3S X: S1 S2 S6 4 Associate each set Si with a binary variable xi (Si ↔ xi ) For each element ci ∈ X , let Si1 ,Si2 , Si3 be the three sets that consistof ci . Define the corresponding clause Ci = xi1 ∨ xi2 ∨ xi3 . (ci ↔ Ci ) 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 Avoid FQPT: Change Problem Hamiltonian 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 4 3 5 54 32 3 5 41 21 5 1 2 4321 S S5 S7 3S X: S1 S2 S6 4 Associate each set Si with a binary variable xi (Si ↔ xi ) For each element ci ∈ X , let Si1 ,Si2 , Si3 be the three sets that consistof ci . Define the corresponding clause Ci = xi1 ∨ xi2 ∨ xi3 . (ci ↔ Ci ) 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 Avoid FQPT: Change Problem Hamiltonian 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 Avoid FQPT: Change Problem Hamiltonian 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} 4 3 5 54 32 3 5 41 21 5 1 2 4321 S S5 S7 3S X: S1 S2 S6 4 14 / 50 !"#$! NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 Avoid FQPT: Change Problem Hamiltonian 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} 4 3 5 54 32 3 5 41 21 5 1 2 4321 S S5 S7 3S X: S1 S2 S6 4 15 / 50 !"#$! NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 Avoid FQPT: Change Problem Hamiltonian 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 Avoid FQPT: Change Problem Hamiltonian 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 Initial Hamiltonian: H(0) = Hinit ground state known (easy to construct) 2 Problem Hamiltonian: H(T ) = Hproblem ground state encodes the answer to the desired optimization problem 3 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 Avoid FQPT: Change Problem Hamiltonian 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 Initial Hamiltonian: H(0) = Hinit ground state known (easy to construct) 2 Problem Hamiltonian: H(T ) = Hproblem ground state encodes the answer to the desired optimization problem 3 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 Avoid FQPT: Change Problem Hamiltonian Example 1 Initial Hamiltonian: Hinit = −(σx1 + σx2 + σx3 ) 2 Evoluation Path : s(t) = tT 3 Problem Hamiltonian: Hproblem = 5σz1 + 10σz2 + σz3 + 7σz1σz2 + 7σz2σz3 E(s1, s2, s3) = 5s1 + 10s2 + s3 + 7s1s2 + 7s2s3, spin si ∈ {−1,+1} state energy 101 -18 100 -14 010 -10 001 -6 000 -2 110 6 011 14 111 30 |ψ(0)〉 = 18 ∑ xi∈{0,1} |x1x2x3〉 |ψ(T )〉 = |101〉 19 / 50 !"#$! NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 Avoid FQPT: Change Problem Hamiltonian Example 1 Initial Hamiltonian: Hinit = −(σx1 + σx2 + σx3 ) 2 Evoluation Path : s(t) = tT 3 Problem Hamiltonian: Hproblem = 5σz1 + 10σz2 + σz3 + 7σz1σz2 + 7σz2σz3 E(s1, s2, s3) = 5s1 + 10s2 + s3 + 7s1s2 + 7s2s3, spin si ∈ {−1,+1} state energy 101 -18 100 -14 010 -10 001 -6 000 -2 110 6 011 14 111 30 |ψ(0)〉 = 18 ∑ xi∈{0,1} |x1x2x3〉 |ψ(T )〉 = |101〉 20 / 50 !"#$! NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 Avoid FQPT: Change Problem Hamiltonian Decomposed State Evolution Visualization (DeSEV) Decompose ground state: |ψ(s)〉 = ∑ x∈{0,1}n αx (s)|x〉, ∑ x∈{0,1}n |αx (s)|2 = 1 111(30) 011(14) 110(6) 000(−2) 001(−6) 010(−10) 100(−14) 101(−18) 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 state(energy) time 21 / 50 !"#$! NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 Avoid FQPT: Change Problem Hamiltonian Adiabatic Running Time (ART) Adiabatic Theorem For s(t) = t/T . If T is “large” enough: T = O ( poly(n) g2min ) where minimum spectral gap gmin = min0≤t≤T(E1(t)− E0(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: ART(H) = max0≤s≤1 |〈E1(s)| dH ds |E0(s)〉| g2min max 0≤s≤1 ||H(s)|| 22 / 50 !"#$! NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 Avoid FQPT: Change Problem Hamiltonian Throughout this talk, we fix the initital Hamiltonian and evolution path, and vary the problem Hamiltonian: 1 Initial Hamiltonian: Hinit = −∑i∈V(G) σxi 2 Evoluation Path : s(t) = tT 3 Problem Hamiltonian 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 Avoid FQPT: Change Problem Hamiltonian 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 Avoid FQPT: Change Problem Hamiltonian Given an instance of EC3: Ψ(x1, . . . , xn) = C1 ∧ . . . ∧ Cm Algorithm 1: Clause-violation based problem Hamiltonian HA: HA = ∑ i∈V(GEC) Biσzi + ∑ ij∈E(GEC) Iijσzi σzj (1) Bi : #clauses that contains variable xi Iij : #clauses that contains both xi and xj (was called Jij = 12(Jij + Jji)) Algorithm 2: MIS-reduction based problem Hamiltonian HC : HC = ∑ i∈V(GEC) ∑ j∈nbr(i) Jij − 2Bi σzi + ∑ ij∈E(GEC) Jijσzi σzj (2) 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 Avoid FQPT: Change Problem Hamiltonian Given an instance of EC3: Ψ(x1, . . . , xn) = C1 ∧ . . . ∧ Cm Algorithm 1: Clause-violation based problem Hamiltonian HA: HA = ∑ i∈V(GEC) Biσzi + ∑ ij∈E(GEC) Iijσzi σzj (1) Bi : #clauses that contains variable xi Iij : #clauses that contains both xi and xj (was called Jij = 12(Jij + Jji)) Algorithm 2: MIS-reduction based problem Hamiltonian HC : HC = ∑ i∈V(GEC) ∑ j∈nbr(i) Jij − 2Bi σzi + ∑ ij∈E(GEC) Jijσzi σzj (2) 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 Avoid FQPT: Change Problem Hamiltonian Given an instance of EC3: Ψ(x1, . . . , xn) = C1 ∧ . . . ∧ Cm Algorithm 1: Clause-violation based problem Hamiltonian HA: HA = ∑ i∈V(GEC) Biσzi + ∑ ij∈E(GEC) Iijσzi σzj (1) Bi : #clauses that contains variable xi Iij : #clauses that contains both xi and xj (was called Jij = 12(Jij + Jji)) Algorithm 2: MIS-reduction based problem Hamiltonian HC : HC = ∑ i∈V(GEC) ∑ j∈nbr(i) Jij − 2Bi σzi + ∑ ij∈E(GEC) Jijσzi σzj (2) 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 Avoid FQPT: Change Problem Hamiltonian Given an instance of EC3: Ψ(x1, . . . , xn) = C1 ∧ . . . ∧ Cm Algorithm 1: Clause-violation based problem Hamiltonian HA: HA = ∑ i∈V(GEC) Biσzi + ∑ ij∈E(GEC) Iijσzi σzj (1) Bi : #clauses that contains variable xi Iij : #clauses that contains both xi and xj (was called Jij = 12(Jij + Jji)) Algorithm 2: MIS-reduction based problem Hamiltonian HC : HC = ∑ i∈V(GEC) ∑ j∈nbr(i) Jij − 2Bi σzi + ∑ ij∈E(GEC) Jijσzi σzj (2) 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 Avoid FQPT: Change Problem Hamiltonian Algorithm 1: Altshuler et al. Energy function: EΨ(x1, . . . , xn) = m∑ i=1 (xi1 + xi2 + xi3 − 1)2 penalizes each violating clause Ci = xi1 ∨ xi2 ∨ xi3 HA = ∑ i∈V(GEC) Biσzi + ∑ ij∈E(GEC) Iijσzi σzj 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 Avoid FQPT: Change Problem Hamiltonian 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 6∈ E(G) Example 1 2 3 645 30 / 50 !"#$! NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 Avoid FQPT: Change Problem Hamiltonian Quadratic Pseudo-boolean Function For i ∈ V(G), associate it with a binary variable xi ∈ {0, 1}. Define Y(x1, . . . , xn) = ∑ i∈V(G) xi − ∑ ij∈E(G) Jijxixj Jij – penalty for the edge ij Example: for Jij = 2 Y(1, 0, 0, 0, 0, 1) = 2 Y(1, 1, 0, 0, 0, 1) = 1 + 1− 2 + 1 = 1 Y(1, 0, 0, 1, 1, 1) = 4 1 2 3 645 31 / 50 !"#$! NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 Avoid FQPT: Change Problem Hamiltonian Quadratic Pseudo-boolean Function For i ∈ V(G), associate it with a binary variable xi ∈ {0, 1}. Define Y(x1, . . . , xn) = ∑ i∈V(G) xi − ∑ ij∈E(G) Jijxixj Jij – penalty for the edge ij Example: for Jij = 2 Y(1, 0, 0, 0, 0, 1) = 2 Y(1, 1, 0, 0, 0, 1) = 1 + 1− 2 + 1 = 1 Y(1, 0, 0, 1, 1, 1) = 4 1 2 3 645 32 / 50 !"#$! NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 Avoid FQPT: Change Problem Hamiltonian Quadratic Pseudo-boolean Function For i ∈ V(G), associate it with a binary variable xi ∈ {0, 1}. Define Y(x1, . . . , xn) = ∑ i∈V(G) xi − ∑ ij∈E(G) Jijxixj Jij – penalty for the edge ij Example: for Jij = 2 Y(1, 0, 0, 0, 0, 1) = 2 Y(1, 1, 0, 0, 0, 1) = 1 + 1− 2 + 1 = 1 Y(1, 0, 0, 1, 1, 1) = 4 1 2 3 645 33 / 50 !"#$! NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 Avoid FQPT: Change Problem Hamiltonian Quadratic Pseudo-boolean Function For i ∈ V(G), associate it with a binary variable xi ∈ {0, 1}. Define Y(x1, . . . , xn) = ∑ i∈V(G) xi − ∑ ij∈E(G) Jijxixj . Theorem If Jij > 1 for all ij ∈ E(G), then |mis(G)| = maxY(x1, . . . , xn). and mis(G) = {i ∈ V(G) : x∗i = 1}, where (x∗1 , . . . , x∗n ) = argmax(x1,...,xn)∈{0,1}nY(x1, . . . , xn). 34 / 50 !"#$! NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 Avoid FQPT: Change Problem Hamiltonian Quadratic Pseudo-boolean Function For i ∈ V(G), associate it with a binary variable xi ∈ {0, 1}. Define Y(x1, . . . , xn) = ∑ i∈V(G) xi − ∑ ij∈E(G) Jijxixj . Theorem If Jij > 1 for all ij ∈ E(G), then |mis(G)| = maxY(x1, . . . , xn). and mis(G) = {i ∈ V(G) : x∗i = 1}, where (x∗1 , . . . , x∗n ) = argmax(x1,...,xn)∈{0,1}nY(x1, . . . , xn). 35 / 50 !"#$! NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 Avoid FQPT: Change Problem Hamiltonian Quadratic Pseudo-boolean Function For i ∈ V(G), associate it with a binary variable xi ∈ {0, 1}. Define Y(x1, . . . , xn) = ∑ i∈V(G) xi − ∑ ij∈E(G) Jijxixj . Theorem If Jij > 1 for all ij ∈ E(G), then |mis(G)| = maxY(x1, . . . , xn). and mis(G) = {i ∈ V(G) : x∗i = 1}, where (x∗1 , . . . , x∗n ) = argmax(x1,...,xn)∈{0,1}nY(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 Avoid FQPT: Change Problem Hamiltonian Theorem If Jij > min{Bi ,Bj} for all ij ∈ E(G), then the maximum value of Y(x1, . . . , xn) = ∑ i∈V(G) Bixi − ∑ ij∈E(G) Jijxixj (3) is the total weight of the MIS, and mis(G) = {i ∈ V(G) : x∗i = 1}, where (x∗1 , . . . , x∗n ) = arg max(x1,...,xn)∈{0,1}n Y(x1, . . . , xn). Change variables: xi = 1+si2 (xi = 0⇔ si = −1, xi = 1⇔ si = +1) Min E(s1, . . . , sn) = ∑ i∈V(G) ( ∑ j∈nbr(i) Jij − 2Bi)si + ∑ ij∈E(G) Jijsisj H = ∑ i∈V(G) ∑ j∈nbr(i) Jij − 2Bi σzi + ∑ ij∈E(G) Jijσzi σzj 37 / 50 !"#$! NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 Avoid FQPT: Change Problem Hamiltonian Theorem If Jij > min{Bi ,Bj} for all ij ∈ E(G), then the maximum value of Y(x1, . . . , xn) = ∑ i∈V(G) Bixi − ∑ ij∈E(G) Jijxixj (3) is the total weight of the MIS, and mis(G) = {i ∈ V(G) : x∗i = 1}, where (x∗1 , . . . , x∗n ) = arg max(x1,...,xn)∈{0,1}n Y(x1, . . . , xn). Change variables: xi = 1+si2 (xi = 0⇔ si = −1, xi = 1⇔ si = +1) Min E(s1, . . . , sn) = ∑ i∈V(G) ( ∑ j∈nbr(i) Jij − 2Bi)si + ∑ ij∈E(G) Jijsisj H = ∑ i∈V(G) ∑ j∈nbr(i) Jij − 2Bi σzi + ∑ ij∈E(G) Jijσzi σzj 38 / 50 !"#$! NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 Avoid FQPT: Change Problem Hamiltonian Theorem If Jij > min{Bi ,Bj} for all ij ∈ E(G), then the maximum value of Y(x1, . . . , xn) = ∑ i∈V(G) Bixi − ∑ ij∈E(G) Jijxixj (3) is the total weight of the MIS, and mis(G) = {i ∈ V(G) : x∗i = 1}, where (x∗1 , . . . , x∗n ) = arg max(x1,...,xn)∈{0,1}n Y(x1, . . . , xn). Change variables: xi = 1+si2 (xi = 0⇔ si = −1, xi = 1⇔ si = +1) Min E(s1, . . . , sn) = ∑ i∈V(G) ( ∑ j∈nbr(i) Jij − 2Bi)si + ∑ ij∈E(G) Jijsisj H = ∑ i∈V(G) ∑ j∈nbr(i) Jij − 2Bi σzi + ∑ ij∈E(G) Jijσzi σzj 39 / 50 !"#$! NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 Avoid FQPT: Change Problem Hamiltonian Comparison: Algorithm 1 vs. Algorithm 2 Algorithm 1: HA = ∑ i∈V(GEC) Biσzi + ∑ ij∈E(GEC) Iijσzi σzj Algorithm 2: HC = ∑ i∈V(GEC) ∑ j∈nbr(i) Jij − 2Bi σzi + ∑ ij∈E(GEC) Jijσzi σzj where Jij > min{Bi ,Bj} Recall: 2Bi = ∑ j∈nbr(i) Iij Write Jij = 2Iij + Dij , for Dij > min{Bi ,Bj} − 2Iij HC = 2HA + ∑ i∈V(GEC) ∑ j∈nbr(i) Dijσzi + ∑ ij∈E(GEC) Dijσzi σzj Does it matter if we choose different Dij? 40 / 50 !"#$! NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 Avoid FQPT: Change Problem Hamiltonian Comparison: Algorithm 1 vs. Algorithm 2 Algorithm 1: HA = ∑ i∈V(GEC) Biσzi + ∑ ij∈E(GEC) Iijσzi σzj Algorithm 2: HC = ∑ i∈V(GEC) ∑ j∈nbr(i) Jij − 2Bi σzi + ∑ ij∈E(GEC) Jijσzi σzj where Jij > min{Bi ,Bj} Recall: 2Bi = ∑ j∈nbr(i) Iij Write Jij = 2Iij + Dij , for Dij > min{Bi ,Bj} − 2Iij HC = 2HA + ∑ i∈V(GEC) ∑ j∈nbr(i) Dijσzi + ∑ ij∈E(GEC) Dijσzi σzj Does it matter if we choose different Dij? 41 / 50 !"#$! NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 Avoid FQPT: Change Problem Hamiltonian Comparison: Algorithm 1 vs. Algorithm 2 Algorithm 1: HA = ∑ i∈V(GEC) Biσzi + ∑ ij∈E(GEC) Iijσzi σzj Algorithm 2: HC = ∑ i∈V(GEC) ∑ j∈nbr(i) Jij − 2Bi σzi + ∑ ij∈E(GEC) Jijσzi σzj where Jij > min{Bi ,Bj} Recall: 2Bi = ∑ j∈nbr(i) Iij Write Jij = 2Iij + Dij , for Dij > min{Bi ,Bj} − 2Iij HC = 2HA + ∑ i∈V(GEC) ∑ j∈nbr(i) Dijσzi + ∑ ij∈E(GEC) Dijσzi σzj Does it matter if we choose different Dij? 42 / 50 !"#$! NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 Avoid FQPT: Change Problem Hamiltonian 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. “E 412 is given by a sum of θ(N) random terms with zero mean” no longer applies here as Jij are not random. Example (2nd order correction) using HA: E (2)x = − ∑n i=1 1/Bi using HC : E (2)x = − ∑ {i :xi=0} 1 Bi − ∑ {j∈nbr(i):xj=1} Jij + ∑ {i :xi=1} 1 Bi – depend on the connectivity of the graph, and the non-random choice of Jij 43 / 50 !"#$! NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 Avoid FQPT: Change Problem Hamiltonian 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. “E 412 is given by a sum of θ(N) random terms with zero mean” no longer applies here as Jij are not random. Example (2nd order correction) using HA: E (2)x = − ∑n i=1 1/Bi using HC : E (2)x = − ∑ {i :xi=0} 1 Bi − ∑ {j∈nbr(i):xj=1} Jij + ∑ {i :xi=1} 1 Bi – depend on the connectivity of the graph, and the non-random choice of Jij 44 / 50 !"#$! NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 Avoid FQPT: Change Problem Hamiltonian 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 Avoid FQPT: Change Problem Hamiltonian 15-Vertex CK Graph 12 10 11 15 13 14 6 53 42 1 9 7 8 (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 independent set of size 6, while VB , consisting of g(= 3) groups of r(= 3) triangles: {7, 8, 9}, {10, 11, 12}, and {13, 14, 15}, forms 33 independent sets of size 3. The graph is connected as follows. The 6 vertices in VA are divided into 3 groups: {1, 2}, {3, 4}, and {5, 6}. The vertices in each group are adjacent to vertices in two groups of three triangles in VB (as illustrated by different colors). (b) The drawing of the graph with 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, VA = {•, •, •, •, •, •, }, forms the MIS of weight 6; while {",","} is a maximal independent set of weight 3wB(< 6). Notation on represent the computational states. For a computational state |x1x2 . . . xn〉 where xi ∈ {0, 1}, we adopt the zero position representation, namely, represent it by |i1i2 . . . ik〉 where xj = 0 if and only if j = it for some t. That is, we represent |000000111111111〉 (the solution state) by |123456〉. Further, we use a • to denote a vertex in VA, a" for a vertex in VB . That is, the solution state is now represented by | • • • • • •〉, while |"""〉, corresponding to a local maximal independent set of weight 3wB with one vertex from each triangle. Maximum vsMinimum. The maximum of MIS corresponds to the minimum of the Ising energy. For explana- tion purpose, instead of referring to the energy values of the Ising Hamiltonian, we will refer to the values of MIS given by the pseudo-boolean function Y in Eq.(1) by “(-)energy”, where “(-)” is to indicate the reverse ordering. Example. The (-)energy of | ••••••〉 is 6; while |"""−"〉 is 4wB−J , where"−" represents two connected vertices from VB , e.g. vertex 7 and 8 in Figure 1. See Figure 2 for the DESEV of the the ground state of the adiabatic algorithm with H1 in Eq.(4) as the problem Hamiltonian for wB = 1.5 and 1.8. 4.2 FQPT and Perturbation Estimation To gain better understanding, we vary the weights of vertices: fix wA = 1, while varying wB from 1 to 1.9 with a step size of 0.1. That is, we fix the global maximum independent set, while increasing the weight of the local 6 VA = {1, . . . , 6} : •, wA = 1 B = {7, . . . , 15}: 4, 1 ≤ wB < 2 The correspondi g Hamiltonian: H1 ∑ i∈VA (6J − 2)σzi + ∑ i∈VB (6J − 2wB)σzi + J ∑ ij∈E(G) σzi σ z j Here we fix Jij = J = 2 > wB for all ij ∈ E(G). 46 / 50 !"#$! NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 Avoid FQPT: Change Problem Hamiltonian 15-Vertex CK Graph 12 10 11 15 13 14 6 53 42 1 9 7 8 (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 independent set of size 6, while VB , consisting of g(= 3) groups of r(= 3) triangles: {7, 8, 9}, {10, 11, 12}, and {13, 14, 15}, forms 33 independent sets of size 3. The graph is connected as follows. The 6 vertices in VA are divided into 3 groups: {1, 2}, {3, 4}, and {5, 6}. The vertices in each group are adjacent to vertices in two groups of three triangles in VB (as illustrated by different colors). (b) The drawing of the graph with 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, VA = {•, •, •, •, •, •, }, forms the MIS of weight 6; while {",","} is a maximal independent set of weight 3wB(< 6). Notation on represent the computational states. For a computational state |x1x2 . . . xn〉 where xi ∈ {0, 1}, we adopt the zero position representation, namely, represent it by |i1i2 . . . ik〉 where xj = 0 if and only if j = it for some t. That is, we represent |000000111111111〉 (the solution state) by |123456〉. Further, we use a • to denote a vertex in VA, a" for a vertex in VB . That is, the solution state is now represented by | • • • • • •〉, while |"""〉, corresponding to a local maximal independent set of weight 3wB with one vertex from each triangle. Maximum vsMinimum. The maximum of MIS corresponds to the minimum of the Ising energy. For explana- tion purpose, instead of referring to the energy values of the Ising Hamiltonian, we will refer to the values of MIS given by the pseudo-boolean function Y in Eq.(1) by “(-)energy”, where “(-)” is to indicate the reverse ordering. Example. The (-)energy of | ••••••〉 is 6; while |"""−"〉 is 4wB−J , where"−" represents two connected vertices from VB , e.g. vertex 7 and 8 in Figure 1. See Figure 2 for the DESEV of the the ground state of the adiabatic algorithm with H1 in Eq.(4) as the problem Hamiltonian for wB = 1.5 and 1.8. 4.2 FQPT and Perturbation Estimation To gain better understanding, we vary the weights of vertices: fix wA = 1, while varying wB from 1 to 1.9 with a step size of 0.1. That is, we fix the global maximum independent set, while increasing the weight of the local 6 VA = {1, . . . , 6} : •, wA = 1 B = {7, . . . , 15}: 4, 1 ≤ wB < 2 The correspondi g Hamiltonian: H1 ∑ i∈VA (6J − 2)σzi + ∑ i∈VB (6J − 2wB)σzi + J ∑ ij∈E(G) σzi σ z j Here we fix Jij = J = 2 > wB for all ij ∈ E(G). 47 / 50 !"#$! NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 Avoid FQPT: Change Problem Hamiltonian FQPT (Zoom:s = 0.627 . . . 0.628) 3.84 4.8 5 5.2 5.46 0 0.2 0.4 0.6 0.8 1 0 0.5 1 (−)energy First Excited State time s Γ 3.84 4.8 5 5.2 5.46 0 0.2 0.4 0.6 0.8 1 0 0.5 1 (−)energy Ground State time s Γ 3.8 4 4.8 5 5.2 5.4 6 0.627 0.6272 0.6274 0.6276 0.6278 0.628 0 0.2 0.4 0.6 0.8 1 (−)energy First Excited State time s Γ 3.8 4 4.8 5 5.2 5.4 6 0.627 0.6272 0.6274 0.6276 0.6278 0.628 0 0.2 0.4 0.6 0.8 1 (−)energy Ground State time s Γ s∗ = 0.6276, gmin = 1.04× 10−5 48 / 50 !"#$! NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 Avoid FQPT: Change Problem Hamiltonian Change Parameter... Avoid FQPT: gmin = 10−5 → 10−1 J = 2 J = 20 3.84 4.8 5 5.2 5.46 0 0.2 0.4 0.6 0.8 1 0 0.5 1 (−)energy First Excited State time s Γ 3.84 4.8 5 5.2 5.46 0 0.2 0.4 0.6 0.8 1 0 0.5 1 (−)energy Ground State time s Γ 3/k 3.6/k 3.8/k4/k 5/k 5.4/k 6/k 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 (−)energy First Excited State time s Γ 3/k 3.6/k 3.8/k4/k 5/k 5.4/k 6/k 0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 (−)energy Ground State time s Γ s∗ = 0.627637, gmin = 1.04× 10−5 s∗ = 0.667731, gmin = 0.145 J = 2 | • • • ••〉 + |44−44−4〉 |444−4〉 |444〉 | • • • • • •〉 J = 20 | • • • •〉 | • • • ••〉 |444〉 | • • • • • •〉 49 / 50 !"#$! NP-Complete Problems: Exact Cover, MIS, Positive 1-in-3SAT Adiabatic Quantum Algorithm Two Adiabatic Algorithms for EC3 Avoid FQPT: Change Problem Hamiltonian 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 2010-07-23
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
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 Summer School on Quantum Information (10th : 2010 : Vancouver, B.C.) |
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 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}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.59370.1-0103157/manifest