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) Cook – Levin theorem (1971): SAT problem is NP complete Computational Complexity Classes Quantum algorithms for NP complete problems ? Circuit quantum computer - no good ideas Adiabatic quantum computer - promising 4 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. Adiabatic quantum optimization • Total time T (slower is better) • Gap ∆(t) (larger gap is better) Slowly varying → system stays at the ground state ( )Ĥ t Probability of excitation depends on: Probability to stay in the ground state 2 min T ∆ ∝ Problem: Find minimum of a function  f(x) 1.Choose initial Hamiltonian H0 with known ground state 2. Change Hamiltonian to HP “matching” f(x) T large enough  ⇒ measuring reveals the minimum ( ) 00 ˆ 0ˆ ˆ ˆ1 ˆp p H tt tH t H H T T H t T = = − + =  =  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. Adiabatic quantum optimization How powerful is it? • It is quantum! Unstructured search in time      (cf Grover) • It is universal for quantum computation [vanDam-Mosca-Vazirani'01,Roland-Cerf'02] [Aharonov et al.'05] Good, but what about NP-complete problems? • Numerical simulations: promising scaling 8How powerful is it? • It is quantum! Unstructured search in time      (cf Grover) • It is universal for quantum computation [vanDam-Mosca-Vazirani'01,Roland-Cerf'02] [Aharonov et al.'05] • But exponentially small gap • for specifically designed hard instances [Znidaric-Horvat'06,Farhi et al.'08] [vanDam-Vazirani'03,Reichardt'04] But maybe typical gaps are only polynomial? 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] • for bad choice of initial Hamiltonian 1 in 3 SAT = exact cover problem 1,2,...,i N= 1iσ = ±bitslaterals Ising spins 1,2,..., 1 , ,c c c c M i j k N = ≤ ≤ { }, ,c c ci j kclausesN M Clause c is satisfied if one of the three spins is down and other two are up or or Otherwise the clause is not satisfied Task: to satisfy all M clauses Definition , 11 1, c c ci j k σ σ σ= − = = 1 1, , 1 c c ci j k σ σ σ= = =− 1, , 11 c c ci j k σ σ σ= = −= 1,2,...,i N= 1iσ = ±bitslaterals Ising spins 1,2,...,c M= { }, ,c c ci j kclausesN M Clause c is satisfied if one of the three spins is down and other two are up. Otherwise the clause is not satisfied Task: to satisfy all M clauses Important: We will considering ensemble of randomly selected clauses, not some families of artificially designed instances 1 in 3 SAT = exact cover 3 (EC3) problem 1,2,...,i N= 1iσ = ±bitslaterals Ising spins 1,2,...,c M= { }, ,c c ci j kclausesN M Clause c is satisfied if one of the three spins is down and other two are up. Otherwise the clause is not satisfied Task: to satisfy all M clauses Size of the problem: , , MN M N α→∞ →∞ → α No solutions Few solutionsMany solutions cα sα0 Clusters of the solutions 1 in 3 SAT = exact cover 3 (EC3) problem Easy Hard Very hard 1,2,...,i N= 1iσ = ±bitslaterals Ising spins 1,2,...,c M= { }, ,c c ci j kclausesN M , , MN M N α→∞ →∞ → clustering threshold satisfiability threshold c α sα 0.546 < 0.644sα < α No solutions Few solutionsMany solutions cα sα0 Clusters of the solutions Easy Hard Very hard J. Raymond, A. Sportiello, & L. Zdeborova, Physical Review E 76, 011101 (2007). ( )2 , 1, 1 1, , 1 1 0 1, 1, 1 1 1 c c c c c c c c c c c c i j k i j k i j k i j k σ σ σ σ σ σ σ σ σ σ σ σ  = = =   = = = ⇔ + + − =   = = − − = −  ( )2 1 1 1 4 4 4 2 c c c M N i j k iji p i i j c i i j JM BH σ σ σ σ σ σ = = ≠ + + − = = − +∑ ∑ ∑ Otherwise ( )21 0c c ci j kσ σ σ+ + − > Solutions      and only solutions are zero energy ground states of the Hamiltonian { }iσ Bi – number of clauses, which involve spin i Jij – number of clauses, where both i and j participate ( ) { }( ) 2 1 1 0 1 1 4 4 4 2 ˆˆ ˆ c c c M N i j k iji p i i j c i i j N x i i i JM BH H σ σ σ σ σ σ σ σ = = ≠ = + + − = = − + = ∑ ∑ ∑ ∑ Adiabatic Algorithm for EC3 Recipe: 1.Construct the Hamiltonian 2.Slowly change adiabatic parameter s from 0 to 1 { }( ) { }( ) ( ) { }( )0ˆ ˆˆ ˆ ˆ 1zs i p i iH sH s Hσ σ σ= + −  { }( ) { }( ) { }( )0 1ˆ ˆˆ ˆ ˆ ;zi p i i s T tH H H s tλ σ σ λ σ λ − − = + = =   ∞0 λ ( ) { }( ) 2 0 1 1 1 ˆ ˆ ˆ 1 ˆˆˆ ˆ ˆ ˆ; 4 4 4 2 c c c z z zM N N i j k ijz z z xi p i i j i i c i i j i JM BH H σ σ σ σ σ σ σ σ = = ≠ = + + − = = − + =∑ ∑ ∑ ∑ { }( ) { }( ) { }( )0 1ˆ ˆˆ ˆ ˆ ;zi p i i sH H H sλ σ σ λ σ λ − = + =   Ising model (determined on a graph ) in a random parallel and a uniform perpendicular field λ Adiabatic Algorithm for EC3 determines a site of N-dimensional hypercube ( ) { }( )2 0 1 1 1 ˆˆ ˆˆ ˆ ˆ ˆ ˆ ˆ ˆ1 ; c c c M N N z z z z z z x p i j k i i ij i j i i c i i j i H B J Hσ σ σ σ σ σ σ σ = = ≠ = = + + − = + =∑ ∑ ∑ ∑ { }( ) { }( ) { }( )0 1ˆ ˆˆ ˆ ˆ ;zi p i i sH H H sλ σ σ λ σ λ − = + =   Another way of thinking: { }iσ { }( )p iH σ onsite energy { }( )0 1 ˆˆ ˆ ˆ ˆ ˆ N x x i i i Hλ σ λ σ σ σ σ+ − = = = +∑ hoping between nearest neighbors Adiabatic Algorithm for exact cover 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− − ( )1, 1, 1− − 1ε = 1ε = 1ε = 1ε = 4ε = determines a site of N-dimensional hypercube ( ) { }( )2 0 1 1 1 ˆˆ ˆˆ ˆ ˆ ˆ ˆ ˆ ˆ1 ; c c c M N N z z z z z z x p i j k i i ij i j i i c i i j i H B J Hσ σ σ σ σ σ σ σ = = ≠ = = + + − = + =∑ ∑ ∑ ∑ { }( ) { }( ) { }( )0 1ˆ ˆˆ ˆ ˆ ;zi p i i sH H H sλ σ σ λ σ λ − = + =   Another way of thinking: { }iσ { }( )p iH σ onsite energy { }( )0 1 ˆˆ ˆ ˆ ˆ ˆ N x x i i i Hλ σ λ σ σ σ σ+ − = = = +∑ hoping between nearest neighbors Adiabatic Algorithm for exact cover Anderson model for Localization on N-dimensional cube Anderson Model • Lattice - tight binding model • Onsite energies  εi - random • Hopping matrix elements Iijj i Iij Iij ={ I   i and j are nearest neighbors0 otherwise-W < εi <Wuniformly distributed I < Ic I > Ic Insulator All eigenstates are localized Localization length ζloc Metal There appear states extended all over the whole system Anderson  Transition extended localized 0 ˆ ˆ ˆH H V= + Conventional Anderson Model Basis: ,i i ∑= i i iiH ε0ˆ ∑ = = .., ˆ nnji jiIV Hamiltonian: •one “particle”, •one level per site, •onsite disorder •nearest neighbor hoping labels sites ( ) { }( )2 0 1 1 1 ˆˆ ˆˆ ˆ ˆ ˆ ˆ ˆ ˆ1 ; c c c M N N z z z z z z x p i j k i i ij i j i i c i i j i H B J Hσ σ σ σ σ σ σ σ = = ≠ = = + + − = + =∑ ∑ ∑ ∑ Adiabatic Quantum Algorithm for 1 in 3 SAT { }( ) { }( ) { }( )0 1ˆ ˆˆ ˆ ˆ ;zi p i i sH H H sλ σ σ λ σ λ − = + =   Anderson Model on N-dimensional cube Usually: # of dimensions system linear size d const→ L →∞ Here: # of dimensions system linear size d N= →∞ 1L = 6-dimensional cube 9-dimensional cube ∞0 λ extendedlocalized cλ { }( ) { }( ) { }( )0ˆ ˆˆ ˆ ˆ zi p i iH H Hλ σ σ λ σ= +  Disorder W Zharekeschev & Kramer. Exact diagonalization of the Anderson model 1~ λ− Avoided crossing gaps •extended large •localized small Significant amplitude Exponentially small amplitude Adiabatic transition: 1. Extended states – can be performed quickly 2. Localized states – need exponentially long time Otherwise – nonadiabatic Landau-Zienner transition λ λ< λ λ>  Localized states Exponentially long tunneling times Exponentially small anticrossing gaps localized extended 1) Anderson localization would imply As the size of the problem N increases 2) Anti-crossings between solutions and not-solutions – as long as   exceeds we haveFor The algorithm fails (stuck in a local minimum) Our result: λ en er gy λ∗cλ ( )1 logc Nλ = Ω λ ( ) 1 8CNλ −∗ ≈ ( ) 18cN Cλ − > cλ λ∗ < { }( ) { }( ) { }( )0ˆ ˆˆ ˆ ˆ zi p i iH H Hλ σ σ λ σ= +  2 1 Eδ 1 0 E λ 3. Let us add one more clause, which is satisfied by    but not by  1 0 When           the gaps decrease even quicker than exponentially N →∞ 2. For α is close to αs there typically are several  solutions separated by distances        .  Consider two. 1. Hamiltonian             is integrable: it commutes with all    . Its states thus can be degenerated. These degeneracies should split at finite λ since            is non-integrable { }( )ˆ ˆ zp iH σ ˆ ziσ { }( )ˆˆ iHλ σ ( )O N 10 E λ 0⇒ 1⇒ { }( ) { }( ) { }( )0ˆ ˆˆ ˆ ˆ zi p i iH H Hλ σ σ λ σ= +  When           the gaps decrease even quicker than exponentially N →∞ 3. Let us add one more clause, which is satisfied by    but not by  1 0 1. Hamiltonian             is integrable: it commutes with all    . Its states thus can be degenerated. These degeneracies should be split by finite λ in non-integrable 2. For α is close to αs there typically are several  solutions separated by distances        .  Consider two. { }( )ˆ ˆ zp iH σ ˆ ziσ { }( )ˆˆ iHλ σ 2 1 ( )O N 2 1 1 0 E λ 0⇒ 1⇒ 2 1 Eδ 1 0 E λ Q1: Is the splitting       big enough for      to remain the ground state at largeEδ 0λ ? Q2: How big would be the anticrossing gap? ( ) ( )2k k k E N C αα λ λ= ∑ Q1: Is the splitting       big enough for      to remain the ground state at largeEδ 0λ ? Perturbation theory in λ N M const N α →∞ → = } ( )E Nα λ ∝ Cluster expansion:  ~N terms of order 1 1.     is exactly the same for all                 states, i.e. for all solutions. In the leading order ( ) 1C α ( )0 0Eα λ = = 4Eδ λ∝ 2. In each order of the perturbation theory     a sum of        terms with random signs. Eδ ( )O N In the leading order in λ 4E Nδ λ∝ ( ) 2 4 64 6 4 6 , ... , ,... E N N δ λ λ δ λ δ δ δ   = + +  ∝ 4δ 6δ Numerical Simulations ( ) ( ) 1 81E CNδ λ λ −≥ ⇒ ≥ In the leading order in λ 4E Nδ λ∝ Q1: Is the splitting big enough for    to remain the ground state at finite Eδ 0 λ ? Q1.1: How big is the interval in    , where perturbation theory is validλ ? { }( ) { }( ) { }( )0 ˆˆ ˆ ˆ ˆ z i p i i H H H λ σ σ λ σ = +   Q1.1: How big is the interval in    , where perturbation theory is validλ ? A1.1:1.Perturbation theory = locator expansion works as long as          -Anderson localization !cλ λ< Cayley tree Anderson model W,I K – branching # # lnc WI K K = ≈Q1.1: How big is the interval in    , where perturbation theory is validλ ? 2.N-dimensional cube Cayley tree with brunching number K=N. no loopsalmost no loops 3. Abou-Chacra, Anderson, Thouless;  PRL, 1973 1# ln lnc c WI O K K N λ  = ⇒ =     first extended state appears A1.1:1.Perturbation theory = locator expansion works as long as          -Anderson localization !cλ λ< 1# ln lnc c WI O K K N λ  = ⇒ =     first extended state appears, i.e. it is a strong underestimation ( )1 81lnc O O NNλ λ − ∗  = >> =    Important: Perturbation theory is valid starting with  λ λ∗>> A1.1:1.Perturbation theory = locator expansion works as long as          -Anderson localization !cλ λ< Q2:How big is the anticrossing gap ? ( ) # # 1 8 ~ ~ exp # ln ~ # N NE E N N e N δ λ δ λ − −   ⇒ − <<    Adiabatic quantum computer badly fails at large enough N 4~ 10N N ∗>cλ λ< Existing classical algorithms for solving 1 in 3 SAT problem work for  ( ) 33 4 10N < ÷ × The arguments are robust: { }( )p iH σ onsite energy { }( )0 ˆˆ iH σ hoping between the neighboring sites of the hypercube N-dimensional hypercube }Correct for any Adiabatic optimization scheme for any problem This is not necessary ! For Anderson Localization it is sufficient that 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 { }( )0 ˆˆ iH σ 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: • For a typical solution • However the minimum over S0 solutions • # of states with energy 1 is • Energy difference between the true ground state and the E=1 state at finite λ is ( )0 ~ exp 0sS N α αη η → −→ ( )2 8~E E Nλ− ( )2 8 8 2min 0~ log ~E E N S Nλ ηλ− 1 0~S NS ( )1 4 1 2min min ~ 1 logE E O Nλ η−− − + ( ) 1 4 1 8log Nλ η−∗> ( ) 1 4 1 8log Nλ η−∗> Formally small in the                limit, but … , 1N η→∞ << 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 However the exponentially small gap requires only that λ is small ( ) 1 4 1 8log Nλ η−∗> Formally small in the                limit, but … , 1N η→∞ << 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               we return to more or less previous estimation. log 0T N → However the exponentially small gap requires only that λ is small Conclusion Original idea of adiabatic quantum computation will not work Hopes •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:
https://iiif.library.ubc.ca/presentation/dsp.59370.1-0103155/manifest

Comment

Related Items