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

Fractional scaling of quantum walks on percolation lattices Kendon, Viv Jul 25, 2010

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
59370-Kendon_qwperc.pdf [ 1.67MB ]
59370-WS Jul 25 Kendon.mp4 [ 101.72MB ]
Metadata
JSON: 59370-1.0103159.json
JSON-LD: 59370-1.0103159-ld.json
RDF/XML (Pretty): 59370-1.0103159-rdf.xml
RDF/JSON: 59370-1.0103159-rdf.json
Turtle: 59370-1.0103159-turtle.txt
N-Triples: 59370-1.0103159-rdf-ntriples.txt
Original Record: 59370-1.0103159-source.json
Full Text
59370-1.0103159-fulltext.txt
Citation
59370-1.0103159.ris

Full Text

Fractional scaling of quantum Walks on Percolation Lattices Viv Kendon Talk for QAMF 2010, UBC Vancouver preprint: ArXiv:1006.1283 Quantum Information School of Physics & Astronomy University of Leeds Leeds LS2 9JT V.Kendon@leeds.ac.uk ...with contributions from PhD students: Neil Lovett and Katie Barr Project students: 2008: Joe Bailey Paul Knott Godfrey Leung 2009: Sally Cooper Matt Everitt Matt Trevers 2010: Rob Heath Matt Everitt Daniel Fry (PK,SC,MT) Royal Society University Research Fellowship (VK); Summer bursary (JB) July 24, 2010 quantum walks on percolation lattices Overview 1. Introduction & motivation (quantum walks; percolation lattices) 2. Quantum walks on line with gaps (and simple tunnelling model) 3. 2D percolation lattice (fractional scaling) 4. Summary and outlook (what’s next)                                                                                                                                                                 + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + 2/19 July 24, 2010 quantum walks on percolation lattices Classical Random Walk on a Line         −9 −8 −7 −6 −5 −4 −3 −2 −1 1 2 3 4 5 6 7 8 90 Recipe: 1. Start at the origin 2. Toss a fair coin, result is heads or tails 3. Move one unit: right for heads, left for tails 4. Repeat steps 2. and 3. T times 5. Measure position of walker, −T ≤  ≤ T Repeat steps 1. to 5. many times −→ prob. dist. P(, T), binomial standard deviation 〈2〉1/2 = p T + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + 3/19 July 24, 2010 quantum walks on percolation lattices Quantum Walk on a Line −9 −8 −7 −6 −5 −4 −3 −2 −1 1 2 3 4 5 6 8 90 7 Recipe: 1. Start at the origin 2. Toss a qubit (quantum coin) H|0〉 −→ (|0〉+ |1〉)/ p 2 H|1〉 −→ (|0〉 − |1〉)/ p 2 3. Move left and right according to qubit state S|,0〉 −→ |− 1,0〉 S|,1〉 −→ |+ 1,1〉 4. Repeat steps 2. and 3. T times 5. measure position of walker, −T ≤  ≤ T Repeat steps 1. to 5. many times −→ prob. dist. P(, T)... + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + 4/19 July 24, 2010 quantum walks on percolation lattices Quantum vs Classical on a Line -100 -80 -60 -40 -20 0 20 40 60 80 100 position (x) 0 0.02 0.04 0.06 0.08 pr ob ab ili ty  P (x) Analytical solution: Nayak Vishwanath quant-ph/0010117 and Ambainis Bach Nayak Vishwanath Watrous STOC’01 pp60-69 2001 quantum spread ∝ T compared with classical p T + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + 5/19 July 24, 2010 quantum walks on percolation lattices Decoherence model for quantum walks Markovian noise, rate of decoherence: p per unit time – independent of any previous decoherence events. Discrete time quantum walk (S = shift, C = coin toss): ρ(t + 1) = (1− p)SCρ(t)C†S† + p ∑  PSCρ(t)C †S†P †  Continuous time quantum walk (hopping rate γ per unit time): dρ(t) dt = −γ[A,ρ]− pρ+ p ∑  PρP †  −→ effect is to reduce size of off-diagonal elements of ρ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + 6/19 July 24, 2010 quantum walks on percolation lattices Interpolate quantum ↔ classical Add decoherence (measure with prob p at each step): -100 -80 -60 -40 -20 0 20 40 60 80 100 position (x) 0 0.02 0.04 0.06 0.08 pr ob ab ili ty  d ist rib ut io n P( x) p=0 p=0.01 p=0.02 p=0.03 p=0.05 p=0.1 p=0.2 p=0.3 p=0.4 p=0.6 p=0.8 p=1 Top hat distribution for just the right amount of noise! [quant-ph/0209005] + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + 7/19 July 24, 2010 quantum walks on percolation lattices Beyond the line Can “quantum walk” on any graph structure: a cycle:             ...or lattices: (110) (100) (011) (101) (010) (111) (000) (001) ...or grids: (b)(a) need larger coin: one dimension per edge quant-ph/0304204, quant-ph/0504042 + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + 8/19 July 24, 2010 quantum walks on percolation lattices Motivation: Role of symmetry in quantum speed up? • nice properties of quantum walks appear on structures with high symmetry... • evidence that the symmetry is required: – properties disappear when symmetry breaks... • look at less regular systems: choose percolation lattices • well studied, simple, wide range of applications • non-trivial phase transition with high upper critical dimension • disordered but not so random there is no structure + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + 9/19 July 24, 2010 quantum walks on percolation lattices Percolation lattices: • Two types: bond (edge) and site (vertex) • bond or site is present in lattice with probability p • phase transition at pc = 0.5 (bond) or pc = 0.5927... (site) in 2D lattices • p < pc: connected structures small p > pc: connections link most of lattice, “one giant cluster”, conductivity > 0 • line (1D): no (non-trivial) phase transition: single missing bond breaks line into two large structures... Nonetheless, start with 1D, can still learn something useful. + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + 10/19 July 24, 2010 quantum walks on percolation lattices Percolation on a line Gaps on a line prevent both classical and quantum walkers from proceeding. -8000 -6000 -4000 -2000 0 2000 4000 6000 8000 Position on line 10-5 10-4 10-3 10-2 10-1 100 Pr ob ab ili ty  (l og  sc ale ) p = 1.0 p = 0.75 p = 0.5 p = 0.25 p = 0.0 – if gaps change location at each time step: [Romanelli et al quant-ph/0405120] walk still gets through... effect of gaps is like decoherence, spreading returns to classical scaling – bit with larger prefactor + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + 11/19 July 24, 2010 quantum walks on percolation lattices Percolation on a line – with tunnelling alternative: add a simple model of quantum tunnelling: – unbiased coin for edges present (η = 0.25 below) – biased coin allows hopping over missing edges with small probability η regularly placed gaps equivalent to study by Linden and Sharam arXiv:0906.3692v1 quantum behaviour but widely different spreading rates -80 -60 -40 -20 0 20 40 60 80 10-5 10-4 10-3 10-2 10-1 100 -800 -600 -400 -200 0 200 400 600 800 10-5 10-4 10-3 10-2 10-1 100 Pr ob ab ili ty  (l og  sc ale ) -8000 -6000 -4000 -2000 0 2000 4000 6000 8000 Position on line 10-5 10-4 10-3 10-2 10-1 100 p = 1.0 p = 0.75 p = 0.5 p = 0.25 p = 0.0 + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + 12/19 July 24, 2010 quantum walks on percolation lattices Quantum walk on 2D lattice x (lattice units) −40 −20 0 20 40 y ( lat tice  un its) −40 −20 0 20 40 P 0.000 0.002 0.004 0.006 x (lattice units) −40 −20 0 20 40 y ( lat tice  un its) −40 −20 0 20 40 P 0.0 0.1 0.2 0.3 0.4 0.5 • one initial state gives good spreading [Tregenna,Flanagan,Maile,VK, NJP 5 83 (2003)] • rest give central peak, but intermediate spreading – this is worst case + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + 13/19 July 24, 2010 quantum walks on percolation lattices Quantum walk on 2D percolation lattice 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 percolation probability p 1 10 100 av er ag e di sta nc e << r> >  (l att ice  un its ) 10 20 30 40 60 80 100 120 140 bond site pc = 0.5927 p c  = 0.5 • size in key is number of time steps • calculate 〈r〉 for single percolation lattice, then • average over many (5000) random percolation lattices • log-linear plot: values of 〈〈r〉〉 below 1 not important Note finite size effects: 10 −→ 100 peel off below pc + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + 14/19 July 24, 2010 quantum walks on percolation lattices Vary initial state: bond site 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 percolation probability p 0 5 10 15 20 25 30 35 < < r> > , s d(< r> ), l att ice  un its <<r>> 60 max sd(<r>) 60 max <<r>> 60 ran sd(<r>) 60 ran <<r>> 60 min sd(<r>) 60 min 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 percolation probability p 0 5 10 15 20 25 30 35 < < r> > , s d(< r> ), l att ice  un its <<r>> 60 max sd(<r>) 60 max <<r>> 60 ran sd(<r>) 60 ran <<r>> 60 min sd(<r>) 60 min max and min correspond to initial states ran is random phases in max state sd(〈r〉) is variability of 〈r〉 over percolation lattices – higher for site percolation + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + 15/19 July 24, 2010 quantum walks on percolation lattices Look at scaling of spreading 10 20 30 40 50 60 80 100 140 number of steps 0.1 1 10 100 av er ag e di sta nc e (la ttic e u nit s) p = 0.2 0.24 0.28 0.32 0.36 p = 0.4 0.44 0.48 0.52 0.56 p = 0.6 0.64 0.68 0.72 0.76 p = 0.8 0.84 0.88 0.92 0.96 p = 1.0 - log-log plot: slope gives scaling 〈〈r〉〉 ∼ Tα noting finite size effects... use range 100 −→ 140 to fit for scaling + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + 16/19 July 24, 2010 quantum walks on percolation lattices Fractional scaling: fit data in range 100 −→ 140 to 〈〈r〉〉 ∼ Tα 0.4 0.5 0.6 0.7 0.8 0.9 1 percolation probability p 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 ex po ne nt  a bond, max bond, ran phase bond, min site, max site, ran phase site, min 0.8 0.85 0.9 0.95 1 cut off at 100 cut off at 80 cut off at 60 pc < p < 0.85 smooth rise 0 < α < 0.5 0.85<p<1.0 steep rise 0.5 < α ≤ 1 (inset tests finite size convergence using lower cut off for fits) + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + 17/19 July 24, 2010 quantum walks on percolation lattices Compare classical scaling: – would be nice to know how classical random walk on percolation lattice scales... 0.4 0.5 0.6 0.7 0.8 0.9 1 percolation probability p 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 ex po ne nt  a bond, ran phase site, ran phase bond, classical site, classical same as before (without inset) with classical added... same parameters for fitting, 100 −→ 140 still significant finite size effects... – faster quantum spreading! – need classical random walk ∼ 900 steps to sample at same rate? + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + 18/19 July 24, 2010 quantum walks on percolation lattices Summary – ArXiv:1006.1283 • classical simulation of quantum walk on 1- and 2-dimensional percolation lattices • 1D the missing edges induce decoherence at large times • 2D shows fractional scaling 0 < α ≤ 1 for pc < p ≤ 1 • comparison of classical scaling hindered by finite size effects on tractable lattice sizes! • timescales ® 103: quantum still dominates? Further work: • use percolation lattices to explore properties of quantum walk search algorithm • can classical simulations of quantum walks do better for analysing percolation lattices?! • transport, scaling exponents...quantum methods to calculate them? −9 −8 −7 −6 −5 −4 −3 −2 −1 1 2 3 4 5 6 8 90 7 + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + 19/19

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

Comment

Related Items