Journal Club Winter 2011

From Quantum Computing Theory Group
Jump to: navigation, search

Journal Club Winter 2011

Other journal club pages: Autumn 2010, Spring 2011


Organizer(1): Kamil Michnicki (

Organizer(2): Lukas Svec (

Faculty Advisor: Dave Bacon (


Thursday 12:00 in Computer Science, CSE 403.


Topic Chosen
Quantum Random Walks
Main ideas
Quantum Annealing
Quantum-Quantum Metropolis Algorithm
Universality of Quantum Walks
Relationship between continuous and quantum walks


Subject Speaker Date
Organization and classical random walks Lukas Jan 7
Pre-2004 Quantum Walks Lukas Jan 14
Post-2004 Quantum Walks (Szegedy Walk) Lukas Jan 21
Quantum Annealing Kamil Jan 27
Quantum Metropolis Sampling Punya Feb 3
Quantum Quantum Metropolis Algorithm Alex Feb 10
Universality of Quantum Walks(1) Isaac Feb 24
Universality of Quantum Walks (2) Isaac Mar 3
Relationship between continuous and discrete Paul Mar 10


Theory (What it means to be a quantum walk)
(1997) Farhi, Gutmann; Quantum Computation and Decision Trees,
(1998) Watrous; Quantum simulations of classical random walks and undirected graph connectivity,
(2002) Childs et al; Exponential algorithmic speedup by quantum walk,
(2003) Kempe: Quantum Random Walks - An Introductory Overview,,
(2004) Szegedy; Quantum Speed-up of Markov Chain Based Algorithms,
(2006) Magniez et al; Search via Quantum Walk,
(2008) Magniez et al; On the hitting times of quantum versus random walks,
(2010) Krovi, Magniez, et al.; Finding is as Easy as Detecting for Quantum Walks

Scattering off graphs (NAND tree and Universal QC with quantum walks)
(2007) Farhi; A Quantum Algorithm for the Hamiltonian NAND Tree,
(2008) Childs; Universal Computation by Quantum Walk,
(2010) Ambainis; Quantum algorithms for formula evaluation,

Quantum-Quantum Metropolis Algorithm
(2009) Quantum Metropolis Sampling
(2010) A Quantum-Quantum Metropolis Algorithm,

Quantum Simulated Annealing
(2008) Somma et al; Quantum Simulations of Classical Annealing Processes,

Relationship between Discrete and Continuous QW and new simulation technique
(2008) Childs; On the relationship between continuous- and discrete-time quantum walk,