Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2303.00217 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911831497375744 |
|---|---|
| author | Anderson, Noel T. Chung, Jay-U Kimmel, Shelby Koh, Da-Yeon Ye, Xiaohan |
| author_facet | Anderson, Noel T. Chung, Jay-U Kimmel, Shelby Koh, Da-Yeon Ye, Xiaohan |
| contents | 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]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_00217 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Improved Quantum Query Complexity on Easier Inputs Anderson, Noel T. Chung, Jay-U Kimmel, Shelby Koh, Da-Yeon Ye, Xiaohan Quantum Physics 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]. |
| title | Improved Quantum Query Complexity on Easier Inputs |
| topic | Quantum Physics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2303.00217 |