On the Physical Basis for the Incomparability of NP and BQP

Abstract

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.