Course Announcement

Ben Reichardt, ben.reichardt@usc, 213-740-7229, EEB 528 M 12-1:40pm, W 1-1:40pm

Announcements

(RSS feed)
Final project

The final project will consist of an expository paper and a 20-minute presentation to the class on a recent topic related to quantum algorithms. You may work in groups of up to two. Please let me know your topic choice by this Friday, and discuss it with me.

Here are some suggested topics. (Note that I have pointed to the arXiv preprint versions; older papers often have journal versions that might be better...)

- Hidden subgroup problem (HSP): Connection between dihedral group HSP and lattice cryptography problems [Regev 2009; also Peikert 2009 or the survey "Lattice-based cryptography" by Micciancio & Regev 2009]
- Generalized hidden shift problem [Childs & van Dam quant-ph/0507190]
- Quantum algorithm for searching an ordered list [Farhi, Goldstone, Gutmann & Sipser quant-ph/9901059, Childs, Landahl & Parrilo quant-ph/0608161, Childs & Lee 0708.3396]
- Quantum search on bounded-error inputs [Hoyer, Mosca & de Wolf quant-ph/0304052]
- Quantum algorithm for evaluating tensor networks [Arad & Landau 0805.0040]
- Quantum query complexity and semidefinite programming [Barnum, Saks & Szegedy 2003]
- Quantum algorithms for hidden nonlinear structures [Childs, Schulman & Vazirani, 0705.2784]
- Nested quantum walks with quantum data structures [Jeffery, Kothari & Magniez 1210.1199]
- Improved quantum query algorithms for triangle finding and associativity testing [Lee, Magniez & Santha 1210.1014]
- Universal computation by quantum walks [Childs 0806.1972, Childs, Gosset & Webb 1205.3782]
- Quantum algorithms for spatial search [Tulsi 0801.0497, Ambainis et al. 1112.3337]
- Quantum adiabatic optimization algorithm [Farhi et al. 1208.3757]
- Exponential speedup for glued trees traversal [Childs, Cleve, Deotto, Farhi, Gutmann & Spielman quant-ph/0209131]
- Quantum algorithms for classical lattice models [De las Cuevas, Dur, Van den Nest & Martin-Delgado 1104.2517]
- On the hitting times of quantum versus random walks [Magniez, Nayak, Richter & Santha 0808.0083]
- The need for structure in quantum speedups [Aaronson & Ambainis 0911.0996]
- Quantum query complexity of combinatorial group testing [Ambainis & Montanaro 1210.1148]
- Quantum algorithms for graph problems [Durr, Heiligman, Hoyer & Mhalla quant-ph/0401091]
- Multiplicative adversary method for lower-bounding quantum query complexity [Spalek quant-ph/0703237, Magnin & Roland 1209.2713]
- Hamiltonian complexity:
- More ideas:
- Quantum simulation...
- Hidden subgroup problems...
- See the Quantum Algorithm Zoo