Canadian Summer School on Quantum Information (CSSQI) (10th : 2010)

Adiabatic Quantum Optimization and Anderson Localization Altshuler, Boris 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 Altshuler.mp4 [ 165.79MB ]
59370-Altshuler_talk.pdf [ 1.69MB ]
Metadata
JSON: 59370-1.0103155.json
JSON-LD: 59370-1.0103155-ld.json
RDF/XML (Pretty): 59370-1.0103155-rdf.xml
RDF/JSON: 59370-1.0103155-rdf.json
Turtle: 59370-1.0103155-turtle.txt
N-Triples: 59370-1.0103155-rdf-ntriples.txt
Original Record: 59370-1.0103155-source.json
Full Text
59370-1.0103155-fulltext.txt
Citation
59370-1.0103155.ris

Full Text

Adiabatic quantum optimization and Anderson localization Boris Altshuler  Columbia University  Hari Krovi, Jérémie Roland NEC Laboratories America  Outline 1. Introduction: Adiabatic optimization for NP-complete problems 2. Exact Cover 3 problem 3. Anderson Localization on the hypercube 4. Small gaps in the Adiabatic approach to EC3 5. Exponentially large number of solutions (Knysh and Smelyanskiy, 2010)  Computational Complexity Classes Cook – Levin theorem (1971): SAT problem is NP complete Quantum algorithms for NP complete problems ?  Circuit quantum computer - no good ideas Adiabatic quantum computer - promising  4  Adiabatic quantum optimization Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. “Quantum computation by adiabatic evolution”, 2000. arXiv:quant-ph/0001106. Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan, Andrew Lundgren, and Daniel Preda. “A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem”. Science, 292:472–475, 2001.  Slowly varying Hˆ ( t )  → system stays at the ground state  Probability of excitation depends on: 2 ∆ Probability to stay ∝ min in the ground state T  • Total time T (slower is better) • Gap ∆(t) (larger gap is better)  Adiabatic quantum optimization Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. “Quantum computation by adiabatic evolution”, 2000. arXiv:quant-ph/0001106. Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan, Andrew Lundgren, and Daniel Preda. “A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem”. Science, 292:472–475, 2001.  Problem:  Find minimum of a function f(x)  1.Choose initial Hamiltonian ground state 2. Change Hamiltonian to  t  1 Hˆ ( t ) =−   T  T  H0 with known  HP “matching” f(x)  Hˆ 0 t = 0 t ˆ  ˆ  H0 + H p = T Hˆ p t = T   large enough ⇒ measuring reveals the minimum  How powerful is it? • It is quantum! Unstructured search in time  (cf Grover)  [vanDam-Mosca-Vazirani'01,Roland-Cerf'02]  • It is universal for quantum computation  [Aharonov et al.'05]  Good, but what about NP-complete problems? • Numerical simulations: promising scaling  How powerful is it? • It is quantum! Unstructured search in time  (cf Grover)  [vanDam-Mosca-Vazirani'01,Roland-Cerf'02]  • It is universal for quantum computation  [Aharonov et al.'05]  Good, but what about NP-complete problems? • Numerical simulations: promising scaling [Farhi et al.'00,Hogg'03,Banyuls et al.'04,Young et al.'08]  • But exponentially small gap • for bad choice of initial Hamiltonian • for specifically designed hard instances  [Znidaric-Horvat'06,Farhi et al.'08] [vanDam-Vazirani'03,Reichardt'04]  But maybe typical gaps are only polynomial? 8  1 in 3 SAT = exact cover problem  M clauses {ic , jc , kc }  σ = ±1  bits i laterals i = 1, 2, ..., N Ising spins  N  Definition Clause c is satisfied  c = 1, 2, ..., M 1 ≤ ic , jc , kc ≤ N  , σ j 1,= σ i = −1= σk 1 c  or  c  c  if one of the three σ i 1= , σ j −1= , σk 1 spins is down and = or other two are up = σ i 1,= σ j 1, σ k = −1 c  c  c  c  Otherwise the clause is not satisfied  Task:  to satisfy all  M  clauses  c  c  1 in 3 SAT = exact cover 3 (EC3) problem bits σ i = ±1 {ic , jc , kc }  laterals i = 1, 2, ..., N M clauses NIsing c = 1, 2, ..., M spins Clause c is satisfied if one of the three spins is down and other two are up. Otherwise the clause is not satisfied  Important:  Task:  to satisfy all  M  clauses  We will considering ensemble of randomly selected clauses, not some families of artificially designed instances  1 in 3 SAT = exact cover 3 (EC3) problem bits σ i = ±1 {ic , jc , kc }  laterals i = 1, 2, ..., N M clauses NIsing c = 1, 2, ..., M spins Clause c is satisfied if one of the three spins is down and other two are up. Otherwise the clause is not satisfied Size of the problem: Many solutions  0  Easy  to satisfy all  M  clauses  M N → ∞, M → ∞, →α N  Clusters of the solutions  αc  Task:  Hard  Few solutions Very hard  αs  No solutions  α  σ = ±1  bits i laterals i = 1, 2, ..., N Ising spins  N  i , j , k { } c c c clauses M  c = 1, 2, ..., M  M N → ∞, M → ∞, →α N Many solutions  0  Easy  Clusters of the solutions  αc  Hard  Few solutions Very hard  αs  No solutions  α  satisfiability α c clustering α 0.546 < α s < 0.644 threshold s threshold J. Raymond, A. Sportiello, & L. Zdeborova, Physical Review E 76, 011101 (2007).  = σ ic −1= σ kc 1 , σ jc 1,=   σ ic = 1, σ jc = −1, σ kc = 1 ⇔   σ ic 1,= σ jc 1, σ kc = −1 =  (σ  ic  )  2  + σ jc + σ kc − 1 = 0  (  )  2  Otherwise σ ic + σ jc + σ kc − 1 > 0 Solutions {σ i } and only solutions are zero energy ground states of the Hamiltonian  σ ( = M  Hp  ∑  c 1 =  ic  )  + σ jc + σ kc − 1 4  2  J ij M N Bi =− ∑ σ i + ∑ σ iσ j 4 i1 4 i≠ j 2 =  Bi – number of clauses, which involve spin i Jij – number of clauses, where both i and j participate  Adiabatic Algorithm for EC3 Recipe: 1.Construct the Hamiltonian ˆ ˆ z ˆ ˆ H= σi sH p {σˆ i } + (1 − s ) H 0 σ i s  ({ })  (  )  2.Slowly change adiabatic parameter  σ ( = M  Hp  ∑  ic  )  + σ jc + σ kc − 1  J ij M N Bi =− ∑ σ i + ∑ σ iσ j 4 i1 4 i≠ j 2 =  ({ }) ˆ ˆ ˆ ˆ H ({σ }) = H ({σˆ }) + λ H ({σ }) ;  Hˆ 0  λ  ˆ σ  s from 0 to 1  2  4  c 1  ({ })  N  i  = ∑ σˆ ix i =1  i  p  0  z i  0  λ  i  1− s T − t λ= = s t  ∞  Adiabatic Algorithm for EC3 σˆ + σˆ + σˆ − 1) J ( M B = =− σˆ + σˆ σˆ ; Hˆ M  Hp  ∑  z ic  z jc  z kc  4 c= 1  ({ } )  ˆ ˆ Hλ σ i  2  N  ∑4  ∑2  ij z z i i i= i≠ j 1 i  4  ({ } ) + λ H ({ } )  z ˆ H p σˆ i =  0  ˆ σ  i  z j  0  ({ })  σˆ  i  N  x ˆ = σ ∑ i  i= 1  1− s ; λ= s  Ising model (determined on a graph ) in a random parallel and a uniform perpendicular field λ  Adiabatic Algorithm for exact cover ∑ (σˆ M  Hˆ= p  ) ∑ B σˆ + ∑ J σˆ σˆ 2  + σˆ + σˆ − 1=  z z z ic jc kc 1 c=  ({ } )  ˆ ˆ Hλ σ i  N  z z z i i ij i j 1 i= i≠ j  ;  ({ } ) + λ H ({ } )  z ˆ H p σˆ i =  0  ˆ σ  i  Hˆ 0  ({ } )   σˆ i =  N  x ˆ σ ∑ i  1 i=  1− s ; λ= s  Another way of thinking:  {σ } determines a site of N-dimensional hypercube i  { }) ( onsite energy H p σi  λ Hˆ 0  ({ } )  N ˆ x ˆ σ i = λ ∑σ i i =1  + − x ˆ ˆ ˆ σ= σ + σ  hoping between nearest neighbors  The simplest example: 3 qubits 1 clause  }  ⇒ 3d cube, 3 solutions  (1,1,1)  ( −1,1,1)  ( −1, −1,1)  ε =1  (1, −1,1)  ε =1  ( −1,1, −1) ε = 1 ( −1, −1, −1) ε =4  (1,1, −1) (1, −1, −1) ε =1  Adiabatic Algorithm for exact cover ∑ (σˆ M  Hˆ= p  ) ∑ B σˆ + ∑ J σˆ σˆ 2  + σˆ + σˆ − 1=  z z z ic jc kc 1 c=  ({ } )  ˆ ˆ Hλ σ i  N  z z z i i ij i j 1 i= i≠ j  ;  ({ } ) + λ H ({ } )  z ˆ H p σˆ i =  0  ˆ σ  i  Hˆ 0  ({ } )   σˆ i =  N  x ˆ σ ∑ i  1 i=  1− s ; λ= s  Another way of thinking:  {σ } determines a site of N-dimensional hypercube i  { }) ( onsite energy H p σi  λ Hˆ 0  ({ } )  N ˆ x ˆ σ i = λ ∑σ i  + − x ˆ ˆ ˆ σ= σ + σ  i =1  hoping between nearest neighbors  Anderson model for Localization on  N-dimensional cube  Anderson Model  • Lattice - tight binding model • Onsite energies  j  i  Iij  -W < εi <W uniformly distributed  εi - random  • Hopping matrix elements Iij  {  Iij =  I i and j are nearest neighbors  0  otherwise  Anderson Transition  I < Ic Insulator All eigenstates are localized Localization length ζ loc  I > Ic  Metal  There appear states extended all over the whole system  extended  localized  Conventional Anderson Model •one “particle”, •one level per site, •onsite disorder •nearest neighbor hoping labels Basis: sites  i , i  Hamiltonian:  ˆ Hˆ + Vˆ H = 0 Hˆ 0 = ∑ ε i i i i  Vˆ =  ∑I i  i , j = n.n.  j  Adiabatic Quantum Algorithm for 1 in 3 SAT Hˆ= p  ∑ (σˆ M  ) ∑ B σˆ + ∑ J σˆ σˆ 2  + σˆ + σˆ − 1=  z z z ic jc kc 1 c=  ({ } )  ˆ ˆ Hλ σ i  N  z z z i i ij i j 1 i= i≠ j  ;  ({ } ) + λ H ({ } )  z ˆ H p σˆ i =  0  ˆ σ  i  Hˆ 0  ({ } )   σˆ i =  N  x ˆ σ ∑ i  1 i=  1− s ; λ= s  Anderson Model on N-dimensional cube Usually: # of dimensions d → const system linear size L → ∞  Here:  # of dimensions d= N → ∞ system linear size L = 1  6-dimensional cube  9-dimensional cube  ({ })  (  )  ({ })    z ˆ ˆ σ ˆ {σˆ } + λ H σˆ H = H i p i i 0 λ  λ  0  ∞  λc localized  extended  Zharekeschev & Kramer.  Exact diagonalization of the Anderson model  Disorder Avoided crossing gaps  W ~λ  •extended •localized  −1  large small  Adiabatic transition: 1. Extended states – can be performed quickly Significant amplitude  λ > λ  2. Localized states – need exponentially long time Exponentially small amplitude  Otherwise – nonadiabatic Landau-Zienner transition  λ < λ  Localized states  Exponentially long tunneling times  Exponentially small anticrossing gaps  localized  extended  energy  Our result:  λc  λ  λ∗  As the size of the problem N increases 1) Anderson localization would imply λc = Ω (1 log N ) 2) Anti-crossings between solutions and −1 8 not-solutions – as long as λ exceeds λ∗ ≈ ( CN )  (  )  8 −1 c  For N > Cλ  we have  λ∗ < λc  The algorithm fails (stuck in a local minimum)  When N → ∞ the gaps decrease even quicker than exponentially  ({ } )  ({ } ) + λ H ({ } )  ˆ ˆ ˆ σˆ z = H σ H λ i p i  0  ˆ σ  ({ })σˆis integrable:  z ˆ ˆ H σ 1. Hamiltonian p i  z i.  it commutes with all Its states thus can be degenerated. These degeneracies should split at finite ˆ ˆ λ since H λ σ i is non-integrable  ({ } )  2. For α is close to αs there typically are several solutions separated by distances O ( N ) . Consider two. 3. Let us add one more clause, which is satisfied by 1 but not by 0  i  E  2 1  λ 1  δE 0  When N → ∞ the gaps decrease even quicker than exponentially  ({ } )  ({ } ) + λ H ({ } )  ˆ ˆ ˆ σˆ z = H σ H λ i p i  ({ } )  0  ˆ σ  1. Hamiltonian Hˆ p σˆ iz is integrable: z it commutes with all σˆ i . Its states thus can be degenerated. These 2 degeneracies should be split by ˆ 1 ˆ finite λ in non-integrable H λ σ i  ({ } )  2. For α is close to αs there typically are several solutions separated by distances O N . Consider two.  ( )  3. Let us add one more clause, which is satisfied by 1 but not by 0  i  E  λ 1 ⇒ 0 0 ⇒1  E  E  2 1  λ  2 1  λ 1 ⇒ 0  1  δE  0 ⇒1  0  Q1:  Is the splitting δ E big enough for remain the ground state at large λ  Q2:  How big would be the anticrossing gap  0  to  ?  ?  Q1:  Is the splitting δ E big enough for remain the ground state at large λ  }  to  ?  Eα ( λ ) = N ∑ λ Ck  Perturbation theory in λ  N →∞ M const →α = N  0  2k  (α )  k  Eα ( λ ) ∝ N  Cluster expansion: ~N terms of order 1  0= ) 0 states, 4 i.e. for all solutions. In the leading order δ E ∝ λ  α) ( 1.C1 is exactly the same for all Eα  ( λ=  2. In each order of the perturbation theory δ E a sum of O N terms with random signs.  ( )  In the leading order in λ  δE ∝λ  4  N  δ E ( λ , N )  = λ 4δ 4 + λ 6δ 6 + ... δ 4 , δ 6 ,... ∝ N 2  δ4  δ6  Numerical Simulations  Q1:  Is the splitting δ E big enough for 0 to remain the ground state at finite λ  In the leading order in λ  δE ∝λ  4  N  Q1.1:  ?  ({ } )  ˆ ˆ Hλ σ i  ({ } ) ˆ + λ H ({σ } )  = Hˆ p σˆ iz 0  i  δ E ( λ ) ≥ 1 ⇒ λ ≥ ( CN )  How big is the interval in λ , where perturbation theory is valid  −1 8  ?  Q1.1: A1.1:  How big is the interval in λ , where perturbation theory is valid  ?  1.Perturbation theory = locator expansion works as long as λ < λ -Anderson localization ! c  Cayley tree  Anderson model W,I K – branching #  W Ic = # K ln K  Q1.1: A1.1:  How big is the interval in λ , where perturbation theory is valid  ?  1.Perturbation theory = locator expansion works as long as λ < λ -Anderson localization ! c  2.N-dimensional cube  ≈  almost no loops  Cayley tree with brunching number K=N. no loops  3. Abou-Chacra, Anderson, Thouless; PRL, 1973  W Ic # = K ln K   1  first extended λc O  ⇒=  state appears ln N    A1.1:  1.Perturbation theory = locator expansion works as long as λ < λ -Anderson localization !  W Ic # = K ln K  c  ⇒   1  λc O  =   ln N   first extended state appears, i.e. it is a strong underestimation   1  −1 8 Important: λc O  = =  >> λ∗ O ( N )  ln N  Perturbation theory is valid starting with  λ >> λ∗  Q2:  How big is the anticrossing gap  ?  δE ~ λ  −# N ⇒ − << δ E ~ exp # N ln N e ( )   −1 8 λ ~ # N  #N  Adiabatic quantum computer badly fails at large enough N  λ < λc  ∗  N > N ~ 10  Existing classical algorithms for solving 1 3 in 3 SAT problem work for N < 3 ÷ 4 × 10  (  )  4  The arguments are robust: N-dimensional  hypercube  ({ }) onsite energy  H p σi  ({ })  ˆ ˆ H0 σi  }  Correct for any Adiabatic optimization scheme for any problem  hoping between the neighboring sites of This is not necessary the hypercube  For Anderson Localization it is sufficient that ˆ ˆ H 0 σ i is local, i.e. contains only products of finite number of spins. Under this condition the arguments are valid for any adiabatic path in the Hamiltonian space  ({ })  !  Sergey Knysh and Vadim Smelyanskiy “On the relevance of avoided crossings away from quantum critical point to the complexity of quantum adiabatic algorithm”, arXiv:1005.3011v1[quant-ph] •Away from αs the number of solutions is exponential: S0 ~ exp (η N ) η  →0 α →α − • For a typical solution  (E − E  )  s  2  ~ λ8N  • However the minimum over S0 solutions  (E  min − E  )  2  ~ λ 8 N log S0 ~ ηλ 8 N 2  • # of states with energy 1 is S1 ~ NS0  λ ∗> ( log N )  • Energy difference between the true ground state and the E=1 state at 1 4 −1 2 finite λ is Emin − E min ~ −1 + O λ η log N  (  )  −1 4  η1 8  λ ∗> ( log N )  −1 4  η1 8  Formally small in the N → ∞, η << 1 limit, but … However the exponentially small gap requires only that λ is small  Moreover: 1.Under reasonable restrictions on the allowed  sequences a typical sequence in the ensemble can have few solutions or even a unique one and be at the same time hard to solve. Zdeborova & Mezard, 2008, Krzakala & Zdeborova,2009 Zdeborova to be published  λ ∗> ( log N )  −1 4  η1 8  Formally small in the N → ∞, η << 1 limit, but … However the exponentially small gap requires only that λ is small  Moreover: 2. Upper bound: given the evolution time T the state of the system would be a linear combination of low energy eigenstates separated by more than log T. Number of “attempts” is thus ~T rather than exp(ηN). Provided that log T N → 0 we return to more or less previous estimation.  Conclusion Hopes  Original idea of adiabatic quantum computation will not work  •Sampling different trajectories? Farhi, Goldstone, Gosset, Gutmann, Meyer, & Shor, arXiv:1004.5127  •Maybe the delocalized ground state  at finite λ contains information that can speed up the classical algorithm? •Large number of the solutions? •Probability to find a solution.  •. . .  

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-0103155/manifest

Comment

Related Items