11

Classical complexity theory makes much of the study of so-called intermediate problems - that is, problems that are in $\mathsf{NP}$ but are nonetheless not known to be in $\mathsf{P}$ and further not expected to be $\mathsf{NP}$-complete.

Commonly discussed examples of likely intermediate problems include, e.g., GRAPH-ISOMORPHISM and FACTORING. One reason why GRAPH-ISOMORPHISM and FACTORING are both thought to be of intermediate complexity is that neither are known to have an algorithm in $\mathsf{BPP}$, while both are known to be in $\mathsf{coNP}$ (or rather, $\mathsf{coAM}$ in the case of GRAPH-ISOMPORPHISM) - thus if, for example, FACTORING/GRAPH-ISOMPORPHISM were $\mathsf{NP}$-complete, then one would have the conclusion that $\mathsf{NP=coNP}$/the polynomial-time hierarchy $\mathsf{PH}$ collapse, both of which are believed to be unlikely.

Turning now to the $\mathsf{BQP}$ complexity class, noting the fact that FACTORING is both in $\mathsf{NP}$ with witnesses being the factors, and in $\mathsf{BQP}$ by Shor's algorithm, a conclusion is that FACTORING is not likely to be (promise) $\mathsf{BQP}$-complete. If FACTORING were complete for $\mathsf{BQP}$ then, for example, $\mathsf{BQP}\subseteq\mathsf{NP}$, which may be ruled out by the recent breakthrough of Raz and Tal.

Thus it may be natural to ask:

What is stopping FACTORING from being complete for $\mathsf{BQP}$?

GRAPH-ISOMORPHISM can be generalized/altered to SUBGRAPH-ISOMORPHISM, which is $\mathsf{NP}$-complete. Can FACTORING be generalized or altered in any way such that it is complete for $\mathsf{BQP}$, in much the same way that SUBGRAPH-ISOMORPHISM generalizes GRAPH-ISOMORPHISM to be $\mathsf{NP}$-complete?

Mark Spinelli
  • 15,378
  • 3
  • 26
  • 83

1 Answers1

4

At a rigorous level, nothing is necessarily stopping any of these things, because no one can even prove that P≠PSPACE. If P=PSPACE, then every problem in P is BQP-complete as well as NP-complete, PSPACE-complete, etc. So, any statement of the sort that you are looking for has to rest on conjectures about the structure of complexity classes.

In fact, there is a quantum hierarchy which addresses the complexity of factoring, and which is (very) loosely analogous to the classical polynomial hierarchy. Namely, the Fourier hierarchy. Factoring is in the second level of the Fourier hierarchy using the Shor-Kitaev algorithm. As the Complexity Zoo says, it is an open problem to find an oracle that makes FH infinite. (As far as I know, it is still open.) Nonetheless, I would be very surprised if FH collapses.

Greg Kuperberg
  • 1,506
  • 11
  • 16