NP-hard problems are not in BQP
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916435741114368 |
|---|---|
| author | Czerwinski, Reiner |
| author_facet | Czerwinski, Reiner |
| contents | Grover's algorithm can solve NP-complete problems on quantum computers faster than all the known algorithms on classical computers. However, Grover's algorithm still needs exponential time. Due to the BBBV theorem, Grover's algorithm is optimal for searches in the domain of a function, when the function is used as a black box.
We analyze the NP-complete set \[\{ (\langle M \rangle, 1^n, 1^t ) \mid \text{ TM }M\text{ accepts an }x\in\{0,1\}^n\text{ within }t\text{ steps}\}.\] If $t$ is large enough, then M accepts each word in $L(M)$ with length $n$ within $t$ steps. So, one can use methods from computability theory to show that black box searching is the fastest way to find a solution. Therefore, Grover's algorithm is optimal for NP-complete problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_05624 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | NP-hard problems are not in BQP Czerwinski, Reiner Computational Complexity 03D15, 03D60, 68Q12, 68Q15, 81P68 F.1.3; F.2.2 Grover's algorithm can solve NP-complete problems on quantum computers faster than all the known algorithms on classical computers. However, Grover's algorithm still needs exponential time. Due to the BBBV theorem, Grover's algorithm is optimal for searches in the domain of a function, when the function is used as a black box. We analyze the NP-complete set \[\{ (\langle M \rangle, 1^n, 1^t ) \mid \text{ TM }M\text{ accepts an }x\in\{0,1\}^n\text{ within }t\text{ steps}\}.\] If $t$ is large enough, then M accepts each word in $L(M)$ with length $n$ within $t$ steps. So, one can use methods from computability theory to show that black box searching is the fastest way to find a solution. Therefore, Grover's algorithm is optimal for NP-complete problems. |
| title | NP-hard problems are not in BQP |
| topic | Computational Complexity 03D15, 03D60, 68Q12, 68Q15, 81P68 F.1.3; F.2.2 |
| url | https://arxiv.org/abs/2311.05624 |