BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//TYPO3/NONSGML Calendarize//EN
BEGIN:VEVENT
UID:calendarize-eqsi-colloquium-andrew-childs
DTSTAMP:20230328T124827Z
DTSTART:20230515T210000Z
DTEND:20230515T210000Z
SUMMARY:EQSI Colloquium: Andrew Childs
DESCRIPTION:The second EQSI Colloquium will take place on Tuesday\, May 16\, 17:00 CET with a talk "Quantum divide and conquer" by Andrew M. Childs.\nJoin us on Zoom: Link: https://zoom.us/j/91734351612?pwd=K2ZKNnE3d2h6TTBUYUZqS2xjYVVwdz09 (Meeting ID: 917 4657 5742 - Passcode: 170827) Abstract The divide-and-conquer framework\, used extensively in classical algorithm design\, recursively breaks a problem into smaller subproblems\, along with some auxiliary work\, to give a recurrence relation for the classical complexity. We describe a quantum divide-and-conquer framework that\, in certain cases\, yields quantumspeedup through an analogous recurrence relation for the quantum query complexity. We apply this framework to obtain near-optimal quantum query complexities for various string problems\, such as (i) recognizing regular languages\; (ii) decision versions of String Rotation and String Suffix\; and natural parameterized versions of (iii) Longest Increasing Subsequence and (iv) Longest Common Subsequence. Based on joint work with Robin Kothari\, Matt Kovacs-Deak\, Aarthi Sundaram\, and Daochen Wang (arXiv:2210.06419). Talk schedule: Tuesday\, March 21\, 2023 5pm CET (EQSI Colloquium): Ashley Montanaro (Phasecraft and University of Bristol)\, Near-term quantum algorithms for optimization (Watch on Youtube). Monday\, April 17\, 2023\, 5pm CET (EQSI Seminar): Freek Witteveen (University of Copenhagen)\, The minimal canonical form of a tensor network Tuesday\, May 16\, 2023\, 5pm CET (EQSI Colloquium): Andrew Childs (University of Maryland)\, TBA Monday\, June 19\, 2023\, 5pm CET (EQSI Seminar): Speaker and title TBA\nRecordings of the EQSI Colloquium talks will be available on the EQSI Youtube channel.
X-ALT-DESC;FMTTYPE=text/html:The second EQSI Colloquium will take place on Tuesday\, May 16\, 17:00 CET with a talk "Quantum divide and conquer" by Andrew M. Childs.
\nJoin us on Zoom:
Link: \;https://zoom.us/j/91734351612?pwd=K2ZKNnE3d2h6TTBUYUZqS2xjYVVwdz09
(Meeting ID: 917 4657 5742 - Passcode: 170827)
Abstract
The divide-and-conquer framework\, used extensively in classical algorithm design\, recursively breaks a problem into smaller subproblems\, along with some auxiliary work\, to give a recurrence relation for the classical complexity. We describe a quantum divide-and-conquer framework that\, in certain cases\, yields quantumspeedup through an analogous recurrence relation for the quantum query complexity. We apply this framework to obtain near-optimal quantum query complexities for various string problems\, such as (i) recognizing regular languages\; (ii) decision versions of String Rotation and String Suffix\; and natural parameterized versions of (iii) Longest Increasing Subsequence and (iv) Longest Common Subsequence.
Based on joint work with Robin Kothari\, Matt Kovacs-Deak\, Aarthi Sundaram\, and Daochen Wang (arXiv:2210.06419).
Talk schedule:
Tuesday\, March 21\, 2023 5pm CET (EQSI Colloquium): Ashley Montanaro (Phasecraft and University of Bristol)\, Near-term quantum algorithms for optimization (Watch on Youtube).
Monday\, April 17\, 2023\, 5pm CET (EQSI Seminar): Freek Witteveen (University of Copenhagen)\, The minimal canonical form of a tensor network
Tuesday\, May 16\, 2023\, 5pm CET (EQSI Colloquium): Andrew Childs (University of Maryland)\, TBA
Monday\, June 19\, 2023\, 5pm CET (EQSI Seminar): Speaker and title TBA
\nRecordings of the EQSI Colloquium talks will be available on the EQSI Youtube channel.
LOCATION:
END:VEVENT
END:VCALENDAR