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 ∑ PSCρ(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
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- Canadian Summer School on Quantum Information (CSSQI) (10th : 2010) /
- Fractional scaling of quantum walks on percolation...
Open Collections
Canadian Summer School on Quantum Information (CSSQI) (10th : 2010)
Fractional scaling of quantum walks on percolation lattices Kendon, Viv Jul 25, 2010
Page Metadata
Item Metadata
Title | Fractional scaling of quantum walks on percolation lattices |
Creator |
Kendon, Viv |
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 Summer School on Quantum Information (10th : 2010 : Vancouver, B.C.) |
Date Issued | 2010-07-25 |
Description | Quantum walks have been used as simple models of quantum transport phenomena, applicable to systems as diverse as spin chains and bio-molecules. Here we investigate the properties of quantum walks on percolation lattices, disordered structures appropriate for modelling biological and experimentally realistic systems. Both bond (edge) and site percolation have similar definitions: with independent randomly chosen probability p the bond or site is present in the lattice. In two and higher dimensions, percolation lattices exhibit a phase transition from a set of small disconnected regions to a more highly connected structure ("one giant cluster"). On 2D Cartesian lattices, the critical probability pc = 0.5 (bond) and pc = 0.5927... (site). Below pc, the quantum walk will not be able to spread. Approaching pc from above, the spreading slows down completely, as the number of long-distance connected paths reduces to zero. For p = 1, the lattice is fully connected, and the standard quantum walk spreading applies (linear in T). In between, we find the quantum walks show fractional scaling of the spreading, i.e., proportional to T to the power alpha (0.5 < alpha < 1). Our (numerical) results are skewed by finite size effects: the increase in alpha from zero begins before p = pc. It then flattens toward the classical random walk spreading rate of alpha = 0.5 around p = 0.85, followed by a steep rise to the quantum value of alpha = 1 at p = 1. At this stage, we do not have enough data to predict the large T behaviour, but think the steep rise will becomes a "step" function at p = 1 as T -> infinity. The randomness in the percolation lattice would thus act as decoherence in the large T limit. However, such a limit could only be approached for quite large values of T, and from the point of view of models for disordered systems on smaller scales (tens of sites), the faster-than-classical fractional scaling is very much the dominant feature. |
Subject |
quantum walks percolation lattices disordered systems |
Genre |
Presentation |
Type |
Text Still Image Sound Moving Image |
Language | eng |
Date Available | 2016-11-22 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0103159 |
URI | http://hdl.handle.net/2429/30071 |
Affiliation |
Non UBC |
Peer Review Status | Unreviewed |
Scholarly Level | Researcher |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
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
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-0103159/manifest