تقرير
Quantum divide and conquer
| العنوان: | Quantum divide and conquer |
|---|---|
| المؤلفون: | Childs, Andrew M., Kothari, Robin, Kovacs-Deak, Matt, Sundaram, Aarthi, Wang, Daochen |
| سنة النشر: | 2022 |
| المجموعة: | Computer Science Quantum Physics |
| مصطلحات موضوعية: | Quantum Physics, Computer Science - Data Structures and Algorithms |
| الوصف: | The divide-and-conquer framework, used extensively in classical algorithm design, recursively breaks a problem of size $n$ into smaller subproblems (say, $a$ copies of size $n/b$ each), along with some auxiliary work of cost $C^{\textrm{aux}}(n)$, to give a recurrence relation $$C(n) \leq a \, C(n/b) + C^{\textrm{aux}}(n)$$ for the classical complexity $C(n)$. We describe a quantum divide-and-conquer framework that, in certain cases, yields an analogous recurrence relation $$C_Q(n) \leq \sqrt{a} \, C_Q(n/b) + O(C^{\textrm{aux}}_Q(n))$$ that characterizes 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. Comment: 24 pages, 8 figures |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2210.06419 |
| رقم الأكسشن: | edsarx.2210.06419 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |