4
$\begingroup$

This question is inherently somewhat subjective, but here goes.

BQP is (roughly) defined to be the set of decision problems that can be efficiently solved by a quantum computer. PromiseBQP is (roughly) defined to be the set of promise problems that can be efficiently solved by a quantum computer. Annoying, the "difference ... is often ignored in the literature. ... When people talk about 'BQP' they often mean the promise-problem version (PromiseBQP)".

Which definition better captures our non-rigorous intuition for the set of "problems" (a deliberately vague term) that can be efficiently solved by a quantum computer?

Obviously, both the concept of a decision problem and the concept of a promise problems are extreme idealizations of the colloquial sense of the term "problem" that we would care about if we are thinking about the capabilities of an actual, physical quantum computer. (E.g. any actual computer is memory-bounded and can only solve instances of an abstract "problem" up to a certain size, rather than the full "problem" itself.) But for the purpose of building intuition, which idealization better captures the qualitative aspects of the "problems" that an actual quantum computer programmer would care about?

My intuition would be that BQP is the more "realistic" complexity class, since you could sneak in a challenging computation (that would be infeasible in practice) "through the backdoor" of the promise. But I'm not sure about that.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ If you don't get any traction here after a while I'd recommend posting at cstheory.stackechange.com. But as another comment, if I wanted to know the energy of a state that I can easily construct adiabatically for a given Hamiltonian $\mathcal H$, then I would use the Promise-BQP phase estimation algorithm, with the "promise" being that the accuracy is only as good as inverse-polynomial in the number of qubits in my phase-estimation algorithm. The "promise" is used to define the gap in the accuracy. $\endgroup$
    – Mark Spinelli
    Jun 21 at 13:29
  • 1
    $\begingroup$ Also even classically, if I wanted to know the area of a strange, odd-shaped surface I could use Monte Carlo simulation to estimate its volume up to some additive error - I am solving a Promise-BPP problem with Monte Carlo simulation, with the promise being that the error in my area estimate is not too small. I could make this error closer and closer to $0$, but by doing so I might no longer be in BPP, as I'd need more and more samples to better estimate its area. I would certainly call Monte Carlo sim solving a "problem" in the colloquial sense. $\endgroup$
    – Mark Spinelli
    Jun 21 at 14:52
  • $\begingroup$ I think I see your concern. If the promise becomes too small, then you could solve harder and harder problems. Gharibian and Le Gall show that a problem with a large promise gap is in BPP, but the same problem with a smaller gap is PromiseBQP-complete. That same problem with an exponential precision may be harder still. $\endgroup$
    – Mark Spinelli
    Jun 22 at 2:27

1 Answer 1

Reset to default
4
$\begingroup$

Working with promise problems gives us many advantages. According to the 2006 survey on promise problems by Goldreich[1]:

  • Promise problems are actually more natural than language recognition problems, and the latter are preferred mainly for sake of technical convenience.

  • Promise problems provide a framework to represent natural concepts that cannot be represented in terms of language-recognition problems and enable several appealing results:

    • The study of the complexity of problems with unique solution must be formally cast in terms of promise problems (ex. $\text{unique-SAT}$)
    • The study of the hardness of approximation problems may be formally cast in terms of promise problems (ex. gap problems)
    • Promise problem allow to introduce complete problems for classes that are not known to have complete languages.
    • Promise problems were used to indicate separations between certain computational devices with certain resource bounds.

The question, however, is whether we lose something important when working with promise problems. And the answer is yes. Sometimes promise problems do not have the same structural consequences as analogous results regarding language recognition. For example, the existence of an $\text{NP}$-hard promise problem in $\text{NP} \cap \text{coNP}$ does not seem to have any structural consequences, whereas an analogous result for a language recognition problem implies that $\text{NP} = \text{coNP}$[1].

Watrous in his paper "Quantum Computational Complexity" (2008) stated that:

"Although complexity theory has traditionally focused on languages rather than promise problems, little is lost and much is gained in shifting one’s focus to promise problems."[2]

Improve this answer
$\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.