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. •. . .
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- Canadian Summer School on Quantum Information (CSSQI) (10th : 2010) /
- Adiabatic Quantum Optimization and Anderson Localization
Open Collections
Canadian Summer School on Quantum Information (CSSQI) (10th : 2010)
Adiabatic Quantum Optimization and Anderson Localization Altshuler, Boris Jul 23, 2010
Page Metadata
Item Metadata
Title | Adiabatic Quantum Optimization and Anderson Localization |
Creator |
Altshuler, Boris |
Contributor | University of British Columbia. Department of Physics and Astronomy Workshop on Quantum Algorithms, Computational Models and Foundations of Quantum Mechanics Pacific Institute for the Mathematical Sciences |
Date Issued | 2010-07-23 |
Description | Understanding NP-complete problems is a central topic in computer science. This is why adiabatic quantum optimization has attracted so much attention, as it provided a new approach to tackle NP-complete problems using a quantum computer. The efficiency of this approach is limited by small spectral gaps between the ground and excited states of the quantum computer's Hamiltonian. We will discuss the statistics of the gaps using the borrowed from the theory of quantum disordered systems. It turns out that due to a phenomenon similar to Anderson localization exponentially small gaps appear close to the end of the adiabatic algorithm for large random instances of NP-complete problems. We will present the quantitative analysis of the small spectral gaps and discuss possible consequence of this phenomenon on the adiabatic optimization paradigm. |
Genre |
Presentation |
Type |
Text Still Image Sound Moving Image |
Language | eng |
Date Available | 2010-11-22 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0103155 |
URI | http://hdl.handle.net/2429/30065 |
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 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
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.59370.1-0103155/manifest