Home /  Quantum Algorithms and Complexity

Workshop

Quantum Algorithms and Complexity September 23, 2002 - September 27, 2002
Registration Deadline: September 27, 2002 about 22 years ago
To apply for Funding you must register by: June 23, 2002 over 22 years ago
Parent Program:
Organizers Richard Cleve, Peter Shor, and Umesh Vazirani
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
Keywords and Mathematics Subject Classification (MSC)
Primary Mathematics Subject Classification No Primary AMS MSC
Secondary Mathematics Subject Classification No Secondary AMS MSC
Schedule, Notes/Handouts & Videos
Show Schedule, Notes/Handouts & Videos
Show All Collapse
Sep 23, 2002
Monday
08:00 AM - 05:00 PM
  Computation and Entanglement
Richard Jozsa
08:00 AM - 05:00 PM
  Decoherence in quantum walks
Vivien Kendon
08:00 AM - 05:00 PM
  Both Toffoli and C-NOT need little help to do universal quantum computing
Yaoyun Shi
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 (New York University, Courant Institute)
Sep 25, 2002
Wednesday
09:30 AM - 10:30 AM
  Quantum sampling, SZK and Markov chains: A different framework for quantum algorithms
Dorit Aharonov (The Hebrew University of Jerusalem)
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