EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

On the Physical Basis for the Incomparability of NP and BQP

Vivek Kumar, Maheshwari Prasad Singh, Srikanth Radhakrishna

Quanta · 2025

DOI: 10.12743/quanta.91 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Quanta, 2025. Verfasst von Vivek Kumar und 2 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref). Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

What does it mean for the physically motivated computational complexity class $\mathcal{BQP}$ and the logically motivated class $\mathcal{NP}$ to be incomparable, from a physical perspective? Although it is unlikely that quantum computers can solve $\mathcal{NP}$-complete problems in polynomial time, yet it may be instructive to see how a physical theory (denoted $\Theta^{(\mathcal{NP})}$ or $\Theta^{(\mathcal{PSPACE})}$) for which $\mathcal{NP}$ or even $\mathcal{PSPACE}$, respectively, constitutes an efficient model of computation, would compare with quantum theory. The present work explores this question, after briefly reviewing some complexity results indicative of the incomparability of $\mathcal{BQP}$ and $\mathcal{NP}$. We argue that theories $\Theta^{(\mathcal{NP})}$ or $\Theta^{(\mathcal{PSPACE})}$ effectively feature degrees of nonlinearity. Thus, the linearity of quantum theory prevents complete problems in these complexity classes to be efficiently solvable on a quantum computer. On the other hand, the exponentiality of quantum theory endows quantum computers with a certain strength going beyond $\mathcal{NP}$ or even $\mathcal{PH}$. Thus the contrasting roles of the empowerment provided by quantum mechanical exponentiality and the limitation imposed by quantum mechanical linearity seem to be at the heart of the incomparability of the classes $\mathcal{BQP}$ and $\mathcal{NP}$. Quanta 2025; 14: 38–47.

Zitieren

APA

Kumar, V., Singh, M. P., & Radhakrishna, S. (2025). On the Physical Basis for the Incomparability of NP and BQP. Quanta. https://doi.org/10.12743/quanta.91

Vancouver

Kumar V, Singh MP, Radhakrishna S. On the Physical Basis for the Incomparability of NP and BQP. Quanta. 2025. doi:10.12743/quanta.91

BibTeX
@article{Kumar2025,
  author = {Kumar, Vivek and Singh, Maheshwari Prasad and Radhakrishna, Srikanth},
  title = {On the Physical Basis for the Incomparability of NP and BQP},
  journal = {Quanta},
  year = {2025},
  doi = {10.12743/quanta.91}
}
Kostenlos starten →