تقرير
Improved Quantum Query Complexity on Easier Inputs
| العنوان: | Improved Quantum Query Complexity on Easier Inputs |
|---|---|
| المؤلفون: | Anderson, Noel T., Chung, Jay-U, Kimmel, Shelby, Koh, Da-Yeon, Ye, Xiaohan |
| المصدر: | Quantum 8, 1309 (2024) |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science Quantum Physics |
| مصطلحات موضوعية: | Quantum Physics, Computer Science - Data Structures and Algorithms |
| الوصف: | Quantum span program algorithms for function evaluation sometimes have reduced query complexity when promised that the input has a certain structure. We design a modified span program algorithm to show these improvements persist even without a promise ahead of time, and we extend this approach to the more general problem of state conversion. As an application, we prove exponential and superpolynomial quantum advantages in average query complexity for several search problems, generalizing Montanaro's Search with Advice [Montanaro, TQC 2010]. Comment: v2) New explicit description and analysis of distributions leading to average quantum advantages, accepted to Quantum. v1) 35 pages, 2 figures. This article supersedes arXiv/2012.01276 (expanded author list, new application, improved algorithm) |
| نوع الوثيقة: | Working Paper |
| DOI: | 10.22331/q-2024-04-08-1309 |
| URL الوصول: | http://arxiv.org/abs/2303.00217 |
| رقم الأكسشن: | edsarx.2303.00217 |
| قاعدة البيانات: | arXiv |
| DOI: | 10.22331/q-2024-04-08-1309 |
|---|