7
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ I've updated the Wikipedia article. $\endgroup$ Mar 11 at 19:07
  • 1
    $\begingroup$ Welcome to our community !!! $\endgroup$ Mar 12 at 21:26

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

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

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