Difference between revisions of "Journal Club Winter 2011"

From Quantum Computing Theory Group
Jump to: navigation, search
(Papers)
 
(7 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
Journal Club Winter 2011
 
Journal Club Winter 2011
 +
 +
Other journal club pages: [[Journal Club Autumn 2010|Autumn 2010]], [[Journal Club Spring 2011|Spring 2011]]
  
 
==People==
 
==People==
Line 15: Line 17:
 
==Organization==
 
==Organization==
  
Topic Chosen: Quantum Random Walks
+
;Topic Chosen
 +
: Quantum Random Walks
  
Main ideas:
+
;Main ideas:
  
Theory
+
:Theory
  
Quantum Annealing
+
:Quantum Annealing
  
Quantum-Quantum Metropolis Algorithm
+
:Quantum-Quantum Metropolis Algorithm
  
Universality of Quantum Walks
+
:Universality of Quantum Walks
  
Relationship between continuous and quantum walks
+
:Relationship between continuous and quantum walks
  
 
==Schedule==
 
==Schedule==
Line 52: Line 55:
 
|Jan 27
 
|Jan 27
 
|-
 
|-
|Quantum Metropolis Algorithms
+
|Quantum Metropolis Sampling
 +
|Punya
 +
|Feb 3
 +
|-
 +
|Quantum Quantum Metropolis Algorithm
 
|Alex
 
|Alex
|Feb 3
+
|Feb 10
 
|-
 
|-
|Universality of Quantum Walks
+
|Universality of Quantum Walks(1)
 
| Isaac
 
| Isaac
|Feb 10
+
|Feb 24
 
|-
 
|-
 
|Universality of Quantum Walks (2)
 
|Universality of Quantum Walks (2)
 
| Isaac
 
| Isaac
|Feb 24
+
|Mar 3
 
|-
 
|-
 
|Relationship between continuous and discrete
 
|Relationship between continuous and discrete
 
|Paul  
 
|Paul  
|Mar 3
+
|Mar 10
 
|-
 
|-
 
|
 
|
Line 73: Line 80:
 
|-
 
|-
 
|}
 
|}
 +
 
==Papers==
 
==Papers==
  
;'''Theory'''
+
; Theory (What it means to be a quantum walk)
 +
 
 +
:(1997) Farhi, Gutmann; Quantum Computation and Decision Trees, http://arxiv.org/abs/quant-ph/9706062
 +
 
 +
:(1998) Watrous; Quantum simulations of classical random walks and undirected graph connectivity, http://arxiv.org/abs/cs/9812012
 +
 
 +
:(2002) Childs et al; Exponential algorithmic speedup by quantum walk, http://arxiv.org/abs/quant-ph/9706062
 +
 
 +
:(2003) Kempe: Quantum Random Walks - An Introductory Overview, http://www.cs.tau.ac.il/~kempe/papers/23contemp.pdf, http://arxiv.org/abs/quant-ph/0303081
 +
 
 +
:(2004) Szegedy; Quantum Speed-up of Markov Chain Based Algorithms, http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1366222
 +
 
 +
:(2006) Magniez et al; Search via Quantum Walk, http://arxiv.org/abs/quant-ph/0608026
 +
 
 +
:(2008) Magniez et al; On the hitting times of quantum versus random walks, http://arxiv.org/abs/0808.0084
 +
 
 +
:(2010) Krovi, Magniez, et al.; Finding is as Easy as Detecting for Quantum Walks http://arxiv.org/abs/1002.2419
 +
 
 +
 
 +
 
 +
; Scattering off graphs (NAND tree and Universal QC with quantum walks)
 +
 
 +
: (2007) Farhi; A Quantum Algorithm for the Hamiltonian NAND Tree, http://arxiv.org/abs/quant-ph/0702144
 +
 
 +
: (2008) Childs; Universal Computation by Quantum Walk, http://arxiv.org/abs/0806.1972
 +
 
 +
: (2010) Ambainis; Quantum algorithms for formula evaluation, http://arxiv.org/abs/1006.3651
 +
 
 +
 
 +
; Quantum-Quantum Metropolis Algorithm
 +
 
 +
: (2009) Quantum Metropolis Sampling http://arxiv.org/abs/0911.3635
 +
 
 +
: (2010) A Quantum-Quantum Metropolis Algorithm, http://arxiv.org/abs/1011.1468
 +
 
 +
 
 +
; Quantum Simulated Annealing
 +
 
 +
: (2008) Somma et al; Quantum Simulations of Classical Annealing Processes, http://arxiv.org/abs/0804.1571
  
:(2003) Kempe: Quantum Random Walks - An Introductory Overview, (arXiv:quant-ph/0303081v1)
 
  
:(2004) Szegedy: Quantum Speed-up of Markov Chain Based Algorithms
+
; Relationship between Discrete and Continuous QW and new simulation technique
  
:(2010) Krovi, Magniez, et al. Finding is as Easy as Detecting for Quantum Walks (arXiv:1002.2419v1)
+
: (2008) Childs; On the relationship between continuous- and discrete-time quantum walk, http://arxiv.org/abs/0810.0312

Latest revision as of 19:12, 6 April 2011

Journal Club Winter 2011

Other journal club pages: Autumn 2010, Spring 2011

People

Organizer(1): Kamil Michnicki (kpm3@u.washington.edu)

Organizer(2): Lukas Svec (svecl@u.washington.edu)

Faculty Advisor: Dave Bacon (dabacon@cs.washington.edu)

Place

Thursday 12:00 in Computer Science, CSE 403.

Organization

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

Schedule

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

Papers

Theory (What it means to be a quantum walk)
(1997) Farhi, Gutmann; Quantum Computation and Decision Trees, http://arxiv.org/abs/quant-ph/9706062
(1998) Watrous; Quantum simulations of classical random walks and undirected graph connectivity, http://arxiv.org/abs/cs/9812012
(2002) Childs et al; Exponential algorithmic speedup by quantum walk, http://arxiv.org/abs/quant-ph/9706062
(2003) Kempe: Quantum Random Walks - An Introductory Overview, http://www.cs.tau.ac.il/~kempe/papers/23contemp.pdf, http://arxiv.org/abs/quant-ph/0303081
(2004) Szegedy; Quantum Speed-up of Markov Chain Based Algorithms, http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1366222
(2006) Magniez et al; Search via Quantum Walk, http://arxiv.org/abs/quant-ph/0608026
(2008) Magniez et al; On the hitting times of quantum versus random walks, http://arxiv.org/abs/0808.0084
(2010) Krovi, Magniez, et al.; Finding is as Easy as Detecting for Quantum Walks http://arxiv.org/abs/1002.2419


Scattering off graphs (NAND tree and Universal QC with quantum walks)
(2007) Farhi; A Quantum Algorithm for the Hamiltonian NAND Tree, http://arxiv.org/abs/quant-ph/0702144
(2008) Childs; Universal Computation by Quantum Walk, http://arxiv.org/abs/0806.1972
(2010) Ambainis; Quantum algorithms for formula evaluation, http://arxiv.org/abs/1006.3651


Quantum-Quantum Metropolis Algorithm
(2009) Quantum Metropolis Sampling http://arxiv.org/abs/0911.3635
(2010) A Quantum-Quantum Metropolis Algorithm, http://arxiv.org/abs/1011.1468


Quantum Simulated Annealing
(2008) Somma et al; Quantum Simulations of Classical Annealing Processes, http://arxiv.org/abs/0804.1571


Relationship between Discrete and Continuous QW and new simulation technique
(2008) Childs; On the relationship between continuous- and discrete-time quantum walk, http://arxiv.org/abs/0810.0312