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. •. . .
- 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:
https://iiif.library.ubc.ca/presentation/dsp.59370.1-0103155/manifest