Скачать или смотреть Quantum Divide and Conquer | Qiskit Seminar Series with Andrew Childs

Qiskit Seminar Series with Andrew Childs
Quantum Divide and Conquer

Your formal invite to weekly Qiskit videos ► https://ibm.biz/q-subscribe

Speaker: Andrew Childs
Host: Zlatko Minev, PhD.

QSim 2023: https://qsimconference.org/
Andrew's Slides: https://www.cs.umd.edu/~amchilds/talk...

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 quantum speedup 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).

Bio:

Andrew Childs, co-director of QuICS, is a professor in the Department of Computer Science and the Institute for Advanced Computer Studies (UMIACS). He is also the director of the NSF Quantum Leap Challenge Institute for Robust Quantum Simulation.

Childs's research interests are in the theory of quantum information processing, especially quantum algorithms. He has explored the computational power of quantum walk, providing an example of exponential speedup, demonstrating computational universality, and constructing algorithms for problems including search and formula evaluation. Childs has also developed fast quantum algorithms for simulating Hamiltonian dynamics. His other areas of interest include quantum query complexity and quantum algorithms for algebraic problems.

Before coming to UMD, Childs was a DuBridge Postdoctoral Scholar at Caltech from 2004-2007 and a faculty member in Combinatorics & Optimization and the Institute for Quantum Computing at the University of Waterloo from 2007-2014. Childs received his doctorate in physics from MIT in 2004.