Extensively Not P-Bi-Immune promiseBQP-Complete Languages
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917703488372736 |
|---|---|
| author | Jackson, Andrew |
| author_facet | Jackson, Andrew |
| contents | In this paper, I first establish -- via methods other than the Gottesman-Knill theorem -- the existence of an infinite set of instances of simulating a quantum circuit to decide a decision problem that can be simulated classically. I then examine under what restrictions on quantum circuits the existence of infinitely many classically simulable instances persists. There turns out to be a vast number of such restrictions, and any combination of those found can be applied at the same time without eliminating the infinite set of classically simulable instances. Further analysis of the tools used in this then shows there exists a language that every (promise) BQP language is one-one reducible to. This language is also not P-bi-immune under very many promises. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_16764 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Extensively Not P-Bi-Immune promiseBQP-Complete Languages Jackson, Andrew Computational Complexity Quantum Physics In this paper, I first establish -- via methods other than the Gottesman-Knill theorem -- the existence of an infinite set of instances of simulating a quantum circuit to decide a decision problem that can be simulated classically. I then examine under what restrictions on quantum circuits the existence of infinitely many classically simulable instances persists. There turns out to be a vast number of such restrictions, and any combination of those found can be applied at the same time without eliminating the infinite set of classically simulable instances. Further analysis of the tools used in this then shows there exists a language that every (promise) BQP language is one-one reducible to. This language is also not P-bi-immune under very many promises. |
| title | Extensively Not P-Bi-Immune promiseBQP-Complete Languages |
| topic | Computational Complexity Quantum Physics |
| url | https://arxiv.org/abs/2406.16764 |