Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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} $?
$\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.
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}$.
