Is APPROX-QCIRCUIT-PROB a BQP-complete problem?

Question

I've read contradictory information: on the Wikipedia page for BQP, it is written without proof that "APPROX-QCIRCUIT-PROB is a BQP-complete problem", while I have read elsewhere (don't remember) that "it is usually assumed that are no BQP-complete problems". There is a chapter in the 'Handbook of Natural Computing' entitled "BQP-complete problems" but it contains no BQP-complete problems, only PromiseBQP-complete problems.

So is APPROX-QCIRCUIT-PROB a BQP-complete problem? If not, shouldn't the page be corrected? is it a PromiseBQP-complete problem?

There is a similar question about Hamiltonian simulation where there are answers stating that it is BQP-complete and others that it is not, but only PromiseBQP-complete, so the clarification probably would be useful there too. What is promised exactly?

Answer 1

In BQP-Complete Problems by Zhang (2012)

Like many [...] "semantic" complexity classes, BQP is not known to contain complete problems.What people usually study for completeness, in such a scenario, is the class containing the promise problems, that is, those decision problems for which the union of Yes and No input instances is not necessarily the whole set of $\{0,1\}$ strings."

Janzing and Wocjan in their paper "A Simple PromiseBQP-complete Matrix Problem" (2007) stated that:

Certain complexity theoretic issues related to BQP are often blurred in the literature; therefore some clarifications seem to be in order. BQP is a class of languages. But in the literature, when people talk about BQP they often mean the promise-problem version (PromiseBQP). Exactly like with BPP and AM, BQP itself is not known to have complete problems, but PromiseBQP has complete promise problems, and that is adequate for most purposes.

You may find the discussion here about semantic complexity classes helpful.

Answer 2

Just to further @Egretta.Thula's answer, a portion of the Wikipedia article on the APPROX-QCIRCUIT-PROB mentions $\alpha$ and $\beta$ and stated:

Note that the problem does not specify the behavior if an instance is not covered by these two cases. (Emphasis added).

Here, i.e., the promise gap is $\alpha-\beta$ between the probabilities of measuring $|1\rangle$ in the first qubit of the circuit.

But, as Janzing and Wocjan mention, the distinction is often elided over - especially when speaking about (promise) QMA-complete problems, which have a rich tradition in the literature as well.

It's perhaps (marginally) interesting that Janzing and Wocjan's initial arXiv version of their paper didn't note the distinction between PromiseBQP and BQP - but, when published in the Theory of Computing, made sure to clarify this point. The arXiv version of the HHL paper doesn't mention the point about the PromiseBQP complexity class either, although they show that their algorithm is complete only for PromiseBQP as well.