Logo

Mathematical Sciences Research Institute

Home » Quantum Algorithms and Complexity

Workshop

Quantum Algorithms and Complexity September 23, 2002 - September 27, 2002
Registration Deadline: September 27, 2002 over 11 years ago
To apply for Funding you must register by: June 23, 2002 almost 12 years ago
Parent Program: Quantum Computation
Organizers Richard Cleve, Peter Shor, and Umesh Vazirani
Speaker(s) No Speakers Assigned Yet.
Description

REGISTRATION IS CLOSED To be held at the Banff Conference Centre in Banff (Alberta), Canada This workshop will include models for quantum computation, quantum algorithms (including quantum fourier transforms, period finding, hidden subgroup problems), quantum complexity theory (including quantum complexity classes, quantum lower-bounds, quantum communication complexity, quantum NP-completeness and quantum interactive proofs), Fault-tolerance (including quantum error-correction, concatenation codes, decoherence-free subspaces). Please note that the number of participants for this workshop, including those who are self-funded, will be limited due to space constraints at the Banff Centre. At this time very few openings remain. REGISTRATION IS CLOSED Group photo of participants


Schedule
Show All Collapse
Sep 23, 2002
Monday
09:20 AM - 09:30 AM
  Welcome
Loa Nowina-Sapinski
09:30 AM - 10:30 AM
  Polynomial-time quantum algorithms for Pell's Equation and the principal ideal problem
Sean Hallgren
10:30 AM - 11:00 AM
  Morning Coffee Break
11:00 AM - 11:30 AM
  An efficient quantum algorithm for the hidden translation problem
Miklos Santha
11:30 AM - 05:15 PM
  Lunch and informal meetings
05:15 PM - 06:00 PM
  Afternoon Coffee Break
06:00 PM - 07:00 PM
  TBA
John Watrous (University of Waterloo)
Sep 24, 2002
Tuesday
09:30 AM - 10:30 AM
  Quantum lower bounds you haven't seen before
Scott Aaronson
10:30 AM - 11:00 AM
  Morning Coffee Break
11:00 AM - 11:30 AM
  Review of lower bounds for the collision problem
Yaoyun Shi
11:30 AM - 05:15 PM
  Lunch and informal meetings
05:15 PM - 06:00 PM
  Afternoon Coffee Break
06:00 PM - 07:00 PM
  Quantum computation and lattice problems
Oded Regev
Sep 25, 2002
Wednesday
09:30 AM - 10:30 AM
  Quantum sampling, SZK and Markov chains: A different framework for quantum algorithms
Dorit Aharonov (Hebrew University)
10:30 AM - 11:00 AM
  Morning Coffee Break
11:00 AM - 11:30 AM
  Efficient quantum algorithms for estimating Gauss sums (with Gadiel Seroussi)
Willem van Dam
Sep 26, 2002
Thursday
09:30 AM - 10:30 AM
  Quantum decision trees and semidefinite programming
Mario Szegedy
10:30 AM - 11:00 AM
  Morning Coffee Break
11:00 AM - 11:45 AM
  Quantum computing and locally decodable codes
Ronald de Wolf
11:45 AM - 05:15 PM
  Lunch and informal meetings
05:15 PM - 06:00 PM
  Afternoon Coffee Break
06:00 PM - 07:00 PM
  Quantum communication complexity of set disjointness
Andris Ambainis
Sep 27, 2002
Friday
09:30 AM - 10:15 AM
  Digitizing quantum correlations
Dave Bacon
10:15 AM - 10:45 AM
  Morning Coffee Break
10:45 AM - 11:30 AM
  Combinatorics and quantum nonlocality
Harry Buhrman (University of Amsterdam)
11:30 AM - 05:15 PM
  Lunch and informal meetings
05:15 PM - 06:00 PM
  Afternoon Coffee Break
06:00 PM - 07:00 PM
  Quantum computation without entanglement
Tal Mor