# What is stopping FACTORING from being BQP-complete?

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?

• 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). Commented Jun 16, 2022 at 19:32
• 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. Commented Jun 16, 2022 at 20:43