Andris Ambainis
 Personal   Research   Teaching 
 Interests   Projects   Papers   Talks 

Research talks


Selected invited talks


  • “New developments in Quantum Algorithms”. Mathematical Foundations of Computer Science (MFCS), Brno, Czech Republic, August 2010.
  • “Quantum Lovasz local lemma”, Heilbronn Quantum Algorithms Day, Bristol, UK, May 2010.
  • “Quantum algorithms for formula evaluation”. NATO Advanced Research Workshop “Quantum Cryptography and Computing: Theory and Implementation”, Gdansk, Poland, September 2009.
  • “Quantum algorithms with polynomial speedups”. Workshop on Federal Vision for Quantum Information Science, Vienna, VA, USA, April 2009.
  • “Quantum and classical query complexities are polynomially related for all symmetric functions”. Workshop on Quantum Algorithms and Complexity Theory (WQACT), Singapore, November 2008.
  • “Quantum algorithm for evaluating Boolean formulas”. International Conference on Quantum Optics and Quantum Information (ICQO), Vilnius, Lithuania, September 2008.
  • “Quantum finite automata”. School on Algebraic Theory of Automata (SATA), Lisbon, Portugal, September 2008.
  • “Quantum random walks and quantum algorithms”. Classical and Quantum Information Theory (CQIT), Santa Fe, NM, USA, March 2008.
  • „Quantum random Walks - new method for designing quantum algorithms”. Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), Novy Smokovec, Slovakia, January 2008.
  • „An O(N1/2+o(1)) time algorithm for evaluating Boolean formulas on a quantum computer”, 11th workshop on Quantum Information Processing (QIP), Deli, India, December 2007.
  • “Quantum coin flipping”. Fields Institute workshop on Quantum Cryptography and Computing, Toronto, Canada, October 2006.
  • “Quantum lower bounds” (2 lectures). Canadian Summer School on Quantum Information, Calgary, Canada, August 2006.
  • “From random walks to quantum walks“ (2 lectures), Interdisciplinary workshop on Evolution in Networks, Blaubeuren, Germany, April 2006.
  • “New quantum lower bound method and applications“, Poincare Institute, Paris, France, February 2006.
  • “A new quantum lower bound method, with applications to strong direct product theorems”, 9th workshop on Quantum Information Processing (QIP), Paris, France, January 2006.
  • “Multiparty quantum coin flipping”, Workshop on classical and quantum information security, Caltech, USA, December 2005.
  • “Limiting distributions of quantum Markov chains”, CWI, Amsterdam, Netherlands, September 2005.
  • “Quantum algorithms and quantum adiabatic theorem”. Canadian Mathematical Society Summer Meeting, Mathematics of Quantum Information Section, Waterloo, Canada, June 2005.
  • “Adiabatic theorem and adiabatic quantum algorithms”. Technical University of Lisbon, Portugal, April 2005.
  • “Quantum lower bounds”. Institute for Defense Analysis-Center for Communication Research, Princeton, USA, June 2004.
  • “Quantum algorithms: decade after Shor”. ACM Symposium on Theory of Computation (STOC), Chicago, USA, June 2004.
  • “Quantum walks and their applications to quantum algorithms”, Carnegie Mellon University, Pittsburg, USA, May 2004.
  • “Quantum random walk algorithms”, Massachusets Institute of Technology, Cambridge, USA, March 2004.
  • “Quantum walks and their applications to quantum algorithms”, Rutgers University, New Brunswick, USA, March 2004.
  • “Quantum walk algorithms: element distinctness and spatial search”, 2004 Gordon Research Conference on Quantum Information Science, Ventura, USA, February 2004.
  • “Quantum walk algorithms: element distinctness and spatial search”, 7th workshop on Quantum Information Processing (QIP), Waterloo, Canada, January 2004.
  • “Quantum walks and a new quantum algorithm for element distinctness”, 3rd ERATO conference on quantum information and computation (EQIS), Kyoto, Japan, September 2003.
  • “Solving element distinctness by quantum walk”, Perimeter Institute, Waterloo, Canada, June 2003.
  • “Short course on quantum computing” (3 lectures), Helsinki University of Technology, Helsinki, Finland, November 2002.
  • “Quantum communication complexity of set disjointness”, Workshop on Quantum Algorithms and Complexity, Banff, Canada, September 2002.
  • “Quantum random walks”, 5th workshop on Quantum Information Processing (QIP), New York, USA, January 2002.
  • “Quantum coin flipping”, IBM T. Watson Research center, Yorktown Heights, USA, December 2001.
  • “Generating quantum states and quantum communication complexity” , California Institute of Technology (Caltech), Pasadena, USA, November 2001.
  • “Quantum search: algorithms and lower bounds”, 3rd PhD Euroconference on Foundations of Formal Sciences, Vienna, Austria, September 2001.
  • “Quantum lower bounds: adversary method” and “Quantum coin flipping”. Summer school on Quantum Information Processing, Montreal, Canada, July 2001.
  • “Limits of quantum computing”, Cornell University, Ithaca, USA, April 2001.
  • “Limits of quantum computing”, Massachusets Institute of Technology, Cambridge, USA, April 2001.
  • “Quantum computing with highly mixed states”, IBM Almaden Research Center, San Jose, USA, March 2001.
  • “Lower bounds on quantum computing”, California Institute of Technology (Caltech), Pasadena, USA, March 2001.
  • “Quantum coin flipping”, 4th workshop on Quantum Information Processing (QIP), Amsterdam, Netherlands, January 2001.
  • “Quantum communication protocols”, California Institute of Technology (Caltech), Pasadena, USA, November 2000.
  • “Quantum lower bounds by quantum arguments”, Mathematics of Quantum Computation, Berkeley, USA, February 2000.
  • “Quantum lower bounds by quantum arguments”, Stanford University, Palo Alto, USA, February 2000.
  • “Quantum lower bounds by quantum arguments”, 3rd workshop on Quantum Information Processing (QIP), Montreal, Canada, December 1999.
  • “Quantum communication complexity of sampling”, 2nd workshop on Algorithms in Quantum Information Processing (AQIP), Chicago, USA, January 1999.
  • “Randomization in learning theory”, Workshop on Randomized Algorithms, Brno, Czech Republic, August 1998.