Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2411.02369 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911226840219648 |
|---|---|
| author | Karamchedu, Chaitanya Fox, Matthew Gottesman, Daniel |
| author_facet | Karamchedu, Chaitanya Fox, Matthew Gottesman, Daniel |
| contents | Assuming the polynomial hierarchy is infinite, we prove a sufficient condition for determining if uniform and polynomial size quantum circuits over a non-universal gate set are not efficiently classically simulable in the weak multiplicative sense. Our criterion exploits the fact that subgroups of $\mathrm{SL}(2;\mathbb{C})$ are essentially either discrete or dense in $\mathrm{SL}(2;\mathbb{C})$. Using our criterion, we give a new proof that both instantaneous quantum polynomial (IQP) circuits and conjugated Clifford circuits (CCCs) afford a quantum advantage. We also prove that both commuting CCCs and CCCs over various fragments of the Clifford group afford a quantum advantage, which settles two questions of Bouland, Fitzsimons, and Koh. Our results imply that circuits over just $(U^\dagger \otimes U^\dagger) \mathrm{CZ} (U \otimes U)$ afford a quantum advantage for almost all $U \in \mathrm{U}(2)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_02369 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Criterion for Post-Selected Quantum Advantage Karamchedu, Chaitanya Fox, Matthew Gottesman, Daniel Quantum Physics Computational Complexity Assuming the polynomial hierarchy is infinite, we prove a sufficient condition for determining if uniform and polynomial size quantum circuits over a non-universal gate set are not efficiently classically simulable in the weak multiplicative sense. Our criterion exploits the fact that subgroups of $\mathrm{SL}(2;\mathbb{C})$ are essentially either discrete or dense in $\mathrm{SL}(2;\mathbb{C})$. Using our criterion, we give a new proof that both instantaneous quantum polynomial (IQP) circuits and conjugated Clifford circuits (CCCs) afford a quantum advantage. We also prove that both commuting CCCs and CCCs over various fragments of the Clifford group afford a quantum advantage, which settles two questions of Bouland, Fitzsimons, and Koh. Our results imply that circuits over just $(U^\dagger \otimes U^\dagger) \mathrm{CZ} (U \otimes U)$ afford a quantum advantage for almost all $U \in \mathrm{U}(2)$. |
| title | A Criterion for Post-Selected Quantum Advantage |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2411.02369 |