1
$\begingroup$

BQP : (bounded-error quantum polynomial time) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.

Question : We know that $\mathsf{P}$ and $\mathsf{NP}$ classes are defined on Turing model of computation where as $\mathsf{BQP}$ is defined over quantum model of computation. When there model of computation are different how we can say that $\mathsf{P} \subseteq \mathsf{BQP} $?

$\endgroup$

2 Answers 2

3
$\begingroup$

$\mathsf{P}$ and $\mathsf{BQP}$ are classes of languages, not algorithms. Namely, a language belongs to $\mathsf{P}$ if there exists a Turing machine that decides it in polynomial time, and to $\mathsf{BQP}$ if there exists a quantum Turing machine that decides it in polynomial time with up to $1/3$ two-sided error.

Although their definitions invoke different computational models, both $\mathsf{P}$ and $\mathsf{BQP}$ are sets of languages, we compare them as we would compare any other pair of sets.

$\endgroup$
3
$\begingroup$

BQP is simply a set of languages, i.e. $\mathsf{BQP}\subseteq 2^{\Sigma^*}$, and in that sense it can be compared with any other set of languages, such as $\mathsf{P, NP}$. It doesn't matter how those sets are defined, as we can always ask whether they are comparable under the inclusion relation.

You can ask why does it make sense to compare classes obtained from different models of computation (e.g. uniform polynomial size quantum circuits vs polynomial time Turing machines). The idea is to try and capture the notion of "efficiently computable" relative to each model. If you agree that efficiency in quantum/classic computation is captured by BQP and P, then the question "can quantum computers solve more problems efficiently" translates to whether or not $\mathsf{P\subsetneq BQP}$.

$\endgroup$
2
  • $\begingroup$ Is it due to Turing church thesis that we can compare classes obtained from different models of computation? $\endgroup$
    – Complexity
    Nov 19, 2017 at 16:15
  • 1
    $\begingroup$ It is because we want to, and because we can. The first paragraph shows why we can, and the second shows why we want to. $\endgroup$
    – Ariel
    Nov 19, 2017 at 16:27

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.