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 Quantum Information School of Physics & Astronomy University of Leeds Leeds LS2 9JT V.Kendon@leeds.ac.uk  Viv Kendon Talk for QAMF 2010, UBC Vancouver preprint: ArXiv:1006.1283 ...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  Royal Society University Research Fellowship (VK); Summer bursary (JB)  (PK,SC,MT)  quantum walks on percolation lattices  July 24, 2010  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) 11111111 00000000 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111  11111111 00000000 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111  11111111 00000000 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111  11111111 00000000 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111  11111111 00000000 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111  11111111 00000000 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111  11111111 00000000 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111  11111111 00000000 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111  11111111 00000000 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111  ++++++++++++++++++++++++++++++  11111111 00000000 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111 00000000 11111111  2/19  July 24, 2010  quantum walks on percolation lattices  Classical Random Walk on a Line 11111 00000 00000 11111 00000 11111 00000 11111 −9 −8 −7 −6 −5 −4 −3 −2 −1  0 1  2  3  4  5  6  7  8  9  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 =  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 0  1  2  3  4  5  6  7  8  9  Recipe: 1. Start at the origin 2. Toss a qubit (quantum coin)  H|0〉 −→ (|0〉 + |1〉)/ 2 H|1〉 −→ (|0〉 − |1〉)/ 2  3. Move left and right according to qubit state 4. Repeat steps 2. and 3. T times  S|, 0〉 −→ | − 1, 0〉 S|, 1〉 −→ | + 1, 1〉  5. measure position of walker, −T ≤  ≤ T Repeat steps 1. to 5. many times −→ prob. dist. P(, T)... ++++++++++++++++++++++++++++++  4/19  quantum walks on percolation lattices  July 24, 2010  Quantum vs Classical on a Line  probability P(x)  0.08  Analytical solution: Nayak  0.06  Vishwanath quant-ph/0010117  0.04  and Ambainis  0.02  Bach Nayak  0 -100 -80  Vishwanath Watrous  -60  -40  -20 0 20 position (x)  40  60  80  100  STOC’01 pp60-69 2001  quantum spread ∝ T compared with classical  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  quantum walks on percolation lattices  July 24, 2010  Interpolate quantum ↔ classical Add decoherence (measure with prob p at each step):  probability distribution P(x)  0.08 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  0.06  0.04  0.02  0 -100  -80  -60  -40  -20  0  20  40  60  80  100  position (x)  Top hat distribution for just the right amount of noise!  [quant-ph/0209005]  ++++++++++++++++++++++++++++++  7/19  quantum walks on percolation lattices  July 24, 2010  Beyond the line Can “quantum walk” on any graph structure: (110) (010)  a cycle:  11111 00000 00000 11111 00000 11111 00000 11111 00000 11111 00000 11111  (111) (011)  (100) (000)  ...or lattices: ...or grids:  (a)  (101) (001)  (b)  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  quantum walks on percolation lattices  July 24, 2010  Percolation on a line Gaps on a line prevent both classical and quantum walkers from proceeding. 0  Probability (log scale)  10  p = 1.0 p = 0.75 p = 0.5 p = 0.25 p = 0.0  -1  10  -2  10  – if gaps change location at each time step: [Romanelli et al  -3  10  quant-ph/0405120]  walk still gets through...  -4  10  -5  10  -8000  -6000  -4000  -2000  0  2000  4000  6000  8000  Position on line  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: (η = 0.25 below)  – unbiased coin for edges present – 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  Probability (log scale)  0  10 -1 10 -2 10 -3 10 -4 10 -5 10 0-80 10 -1 10 -2 10 -3 10 -4 10 -5 10 -800 0 10 -1 10 -2 10 -3 10 -4 10 -5 10 -8000  -60  -40  -20  0  20  p = 1.0 p = 0.75 p =40 0.5 p = 0.25 p = 0.0  -600  -400  -200  0  200  400  600  800  -6000  -4000  -2000  0  2000  4000  6000  8000  60  80  Position on line  ++++++++++++++++++++++++++++++  12/19  quantum walks on percolation lattices  July 24, 2010  Quantum walk on 2D lattice  0.5 0.006 −40  0.4  −40  0.3 P  20  x (l  atti  0 ce u  20  nits  )  −20  −20  0.1 0.0  0  atti ce  ) y (l  atti ce u  0  nits  0.000 40  0.2  40  y (l  P  −20 0.002  20 20  0 x (l atti ce uni ts  )  −40  −20  40  • one initial state gives good spreading  uni ts)  0.004  −40  40  [Tregenna,Flanagan,Maile,VK, NJP 5 83 (2003)]  • rest give central peak, but intermediate spreading – this is worst case  ++++++++++++++++++++++++++++++  13/19  quantum walks on percolation lattices  July 24, 2010  Quantum walk on 2D percolation lattice average distance <<r>> (lattice units)  100  10 20 30 40 60 80 100 120 140  10  • size in key is number of time steps  pc = 0.5  • calculate 〈r〉 for single percolation lattice, then • average over many (5000) random percolation lattices  bond  • log-linear plot: values of 〈〈r〉〉 below 1 not important  1  site 0  0.1  0.2  0.3  0.4  0.5  pc = 0.5927  0.6  0.7  0.8  0.9  1  percolation probability p  Note finite size effects: 10 −→ 100 peel off below pc ++++++++++++++++++++++++++++++  14/19  quantum walks on percolation lattices  July 24, 2010  Vary initial state: bond  site 35  <<r>> 60 max sd(<r>) 60 max <<r>> 60 ran sd(<r>) 60 ran <<r>> 60 min sd(<r>) 60 min  30  25  20  <<r>>, sd(<r>), lattice units  <<r>>, sd(<r>), lattice units  35  15  10  25  20  15  10  5  5  0 0.2  <<r>> 60 max sd(<r>) 60 max <<r>> 60 ran sd(<r>) 60 ran <<r>> 60 min sd(<r>) 60 min  30  0.3  0.4  0.5  0.6  0.7  percolation probability p  0.8  0.9  1  0 0.2  0.3  0.4  0.5  0.6  0.7  0.8  0.9  percolation probability p  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  1  quantum walks on percolation lattices  July 24, 2010  Look at scaling of spreading  average distance (lattice units)  100  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  10  1  0.1 10  20  30  40  50  60  80  100  - log-log plot: slope gives scaling 〈〈r〉〉 ∼ T α  140  number of steps  noting finite size effects... use range 100 −→ 140 to fit for scaling  ++++++++++++++++++++++++++++++  16/19  quantum walks on percolation lattices  July 24, 2010  Fractional scaling: fit data in range 100 −→ 140 to 〈〈r〉〉 ∼ T α 1 cut off at 100 cut off at 80 cut off at 60  0.9 0.8  exponent a  0.7 0.6  pc < p < 0.85 smooth rise 0 < α < 0.5 0.85<p<1.0 steep rise 0.5 < α ≤ 1  0.5 0.4  0.8  0.85  0.9  0.95  1  bond, max bond, ran phase bond, min site, max site, ran phase site, min  0.3 0.2 0.1 0  0.4  0.5  0.6  0.7  0.8  0.9  1  percolation probability p (inset tests finite size convergence using lower cut off for fits)  ++++++++++++++++++++++++++++++  17/19  quantum walks on percolation lattices  July 24, 2010  Compare classical scaling: – would be nice to know how classical random walk on percolation lattice scales... 1 0.9 0.8  same as before (without inset) with classical added... same parameters for fitting, 100 −→ 140 still significant finite size effects...  exponent a  0.7 0.6 0.5 0.4  bond, ran phase site, ran phase bond, classical site, classical  0.3 0.2 0.1 0  0.4  0.5  0.6  0.7  0.8  0.9  1  percolation probability p – 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 0  1  2  3  4  5  6  ++++++++++++++++++++++++++++++  7  8  9  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:
http://iiif.library.ubc.ca/presentation/dsp.59370.1-0103159/manifest

Comment

Related Items