11
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ I think because FACTORING lies in FBQP. I know that anything in FBQP is also in BQP, but it don't seems right that factoring (which is a function problem) is complete for class of decision problems (i.e. BQP). Because I don't see in the literature any function problem that is complete for a decision class of problems (see complete problems for classes such as NP, PSPACE, PH, etc., all complete problems are decision problems). $\endgroup$
    – YOUSEFY
    Jun 16, 2022 at 19:32
  • $\begingroup$ Thanks, that's reasonable to ask about, but it's also my understanding that it's straightforward to convert FACTORING to a decision problem, and then I can ask why that decision version of FACTORING is unlikely to be complete for BQP. For example, one "decision" variant of FACTORING would be to decide whether $N$ has a prime factor between two given bounds $L$ and $U$ (given as binary strings). My question then would be, can we convert this decision problem to one that's BQP-complete? I might consider editing the question to emphasize this decision variant. $\endgroup$ Jun 16, 2022 at 20:43

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ thanks! I find the second paragraph quite insightful to me. I just read the Y. SHI(2003) paper. I think the conjecture of the non-collapsibility of the Fourier hierarchy implies P and BPP are distinct classes. Quite the opposite of what people 'believe', i.e., P=BPP (conjecture). $\endgroup$ Mar 24 at 17:50
  • 1
    $\begingroup$ As far as I know, P = BPP (which everyone believes) does not imply that FH collapses. The Complexity Zoo is a bit confusing on one point: It gives only the classical decision problem reduction of FH rather than what you could think of full FH, as a class of unitary operators. If two terms in the classical simplication of a quantum complexity hierarchy are equal, it does not imply that the whole hierarchy collapses. $\endgroup$ Mar 25 at 21:51
  • $\begingroup$ Point taken. Now, I see why P=BPP doesn't imply a total collapse of FH. $\endgroup$ Mar 26 at 9:37
  • 1
    $\begingroup$ @Manish, for the same reasons as most people believe P=BPP, I think most people believe AM=NP, and yet we always talk about graph non-isomorphism (which has the famous AM protocol using hash functions) as being in the second level of the Polynomial Hierarchy. $\endgroup$ Mar 27 at 16:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.