Skip to main content
added 188 characters in body
Source Link
Egretta.Thula
  • 11.8k
  • 1
  • 13
  • 34

From Footnote 1 in the paper you mentioned in your comment (Oracle Separation of BQP and PH by Raz and Tal)

In our entire discussion of black-box complexity classes, we consider complexity classes of promise problems, rather than decision problems. Nevertheless, separations of classes of promise problems in the black-box model imply oracle separations of the corresponding classes of decision problems in the “real” world

The footnote then refers to Aaronson's paper BQP and the polynomial hierarchy which says:

We should clarify that there are two questions here: whether $\mathsf{BQP} \subseteq \mathsf{PH}$ and whether $\mathsf{PromiseBQP} \subseteq \mathsf{PromisePH}$. In the unrelativized world, it is entirely possible that quantum computers can solve promise problems outside the polynomial hierarchy, but that all languages in $\mathsf{BQP}$ are nevertheless in $\mathsf{PH}$. However, for the specific purpose of constructing an oracle $A$ such that $\mathsf{BQP}^A \not \subset \mathsf{PH}^A$, the two questions are equivalent, basically because one can always “offload” a promise into the construction of the oracle $A$.

Then he givesgave a proof for this claim.

You can find a related discussion in the comments under this blogpost: https://scottaaronson.blog/?p=451 (comments #21-23)

From Footnote 1 in the paper you mentioned in your comment (Oracle Separation of BQP and PH by Raz and Tal)

In our entire discussion of black-box complexity classes, we consider complexity classes of promise problems, rather than decision problems. Nevertheless, separations of classes of promise problems in the black-box model imply oracle separations of the corresponding classes of decision problems in the “real” world

The footnote then refers to Aaronson's paper BQP and the polynomial hierarchy which says:

We should clarify that there are two questions here: whether $\mathsf{BQP} \subseteq \mathsf{PH}$ and whether $\mathsf{PromiseBQP} \subseteq \mathsf{PromisePH}$. In the unrelativized world, it is entirely possible that quantum computers can solve promise problems outside the polynomial hierarchy, but that all languages in $\mathsf{BQP}$ are nevertheless in $\mathsf{PH}$. However, for the specific purpose of constructing an oracle $A$ such that $\mathsf{BQP}^A \not \subset \mathsf{PH}^A$, the two questions are equivalent, basically because one can always “offload” a promise into the construction of the oracle $A$.

Then he gives a proof for this claim.

From Footnote 1 in the paper you mentioned in your comment (Oracle Separation of BQP and PH by Raz and Tal)

In our entire discussion of black-box complexity classes, we consider complexity classes of promise problems, rather than decision problems. Nevertheless, separations of classes of promise problems in the black-box model imply oracle separations of the corresponding classes of decision problems in the “real” world

The footnote then refers to Aaronson's paper BQP and the polynomial hierarchy which says:

We should clarify that there are two questions here: whether $\mathsf{BQP} \subseteq \mathsf{PH}$ and whether $\mathsf{PromiseBQP} \subseteq \mathsf{PromisePH}$. In the unrelativized world, it is entirely possible that quantum computers can solve promise problems outside the polynomial hierarchy, but that all languages in $\mathsf{BQP}$ are nevertheless in $\mathsf{PH}$. However, for the specific purpose of constructing an oracle $A$ such that $\mathsf{BQP}^A \not \subset \mathsf{PH}^A$, the two questions are equivalent, basically because one can always “offload” a promise into the construction of the oracle $A$.

Then he gave a proof for this claim.

You can find a related discussion in the comments under this blogpost: https://scottaaronson.blog/?p=451 (comments #21-23)

Source Link
Egretta.Thula
  • 11.8k
  • 1
  • 13
  • 34

From Footnote 1 in the paper you mentioned in your comment (Oracle Separation of BQP and PH by Raz and Tal)

In our entire discussion of black-box complexity classes, we consider complexity classes of promise problems, rather than decision problems. Nevertheless, separations of classes of promise problems in the black-box model imply oracle separations of the corresponding classes of decision problems in the “real” world

The footnote then refers to Aaronson's paper BQP and the polynomial hierarchy which says:

We should clarify that there are two questions here: whether $\mathsf{BQP} \subseteq \mathsf{PH}$ and whether $\mathsf{PromiseBQP} \subseteq \mathsf{PromisePH}$. In the unrelativized world, it is entirely possible that quantum computers can solve promise problems outside the polynomial hierarchy, but that all languages in $\mathsf{BQP}$ are nevertheless in $\mathsf{PH}$. However, for the specific purpose of constructing an oracle $A$ such that $\mathsf{BQP}^A \not \subset \mathsf{PH}^A$, the two questions are equivalent, basically because one can always “offload” a promise into the construction of the oracle $A$.

Then he gives a proof for this claim.