BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Drupal iCal API//EN
X-WR-CALNAME:Events items teaser
X-WR-TIMEZONE:America/Toronto
BEGIN:VTIMEZONE
TZID:America/Toronto
X-LIC-LOCATION:America/Toronto
BEGIN:DAYLIGHT
TZNAME:EDT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
DTSTART:20220313T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20211107T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:69e5853c0dc51
DTSTART;TZID=America/Toronto:20221006T150000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20221006T160000
URL:https://uwaterloo.ca/institute-for-quantum-computing/events/multidimens
 ional-quantum-walks-application-k-distinctness
LOCATION:QNC - Quantum Nano Centre 1201 200 University Avenue West Waterloo
  ON N2L 3G1 Canada
SUMMARY:Multidimensional Quantum Walks\, with Application to k-Distinctness
CLASS:PUBLIC
DESCRIPTION:STACEY JEFFEREY - QUSOFT\n\nWhile the quantum query complexity 
 of k-distinctness is known to be\nO(n^{3/4−1/4(2k−1)}) for any constan
 t k≥4\, the best previous\nupper bound on the time complexity was ~O(n^{
 1−1/k}). We give a new\nupper bound of ~O(n^{3/4−1/4(2k−1)}) on the 
 time complexity\,\nmatching the query complexity up to polylogarithmic fac
 tors. In order\nto achieve this upper bound\, we give a new technique for 
 designing\nquantum walk search algorithms\, which is an extension of the e
 lectric\nnetwork framework. We also show how to solve the welded trees pro
 blem\nin O(n) queries and O(n^2) time using this new technique\, showing t
 hat\nthe new quantum walk framework can achieve exponential speedups.
DTSTAMP:20260420T014532Z
END:VEVENT
END:VCALENDAR