tag:blogger.com,1999:blog-3722233.post4482978010782675334..comments2023-09-28T12:45:24.391-05:00Comments on Computational Complexity: BQP not in the Polynomial-Time Hierarchy in Relativized WorldsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-6562092248783827542020-04-26T10:25:58.286-05:002020-04-26T10:25:58.286-05:00If you think of PH as languages defined by bounded...If you think of PH as languages defined by bounded-alternation polynomial-time machines, then you get PH^A by just letting these machines access A as an oracle. It's not the case in general that P^(PH,A) = PH^A.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-38326476216103503032020-04-26T08:56:44.899-05:002020-04-26T08:56:44.899-05:00I am looking for a way to understand (and explain ...I am looking for a way to understand (and explain to students) this theorem in an easiest way. Ok, BQP^A is easy: this is the set of languages recognised by quantum computer which can also ask extra questions in the form "does x belong to set A"? P^A would be easy as well - same definition without the word "quantum". Similarly, we can easily define P^(PH,A) - standard computer with 2 oracles. But what is PH^A? Same definition with "low-depth alternating circuits" instead "quantum computer"? Too complicated! So, my questions are: Is P^PH = PH ? Is, for any oracle A, P^(PH,A) = PH^A? Is the Theorem we are discussing here is equivalent to the statement that there exists an oracle A such that BQP^A is not a subset of P^(PH,A)? Bogdanhttps://www.blogger.com/profile/17336734862701615202noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32374153261416129162018-08-08T13:37:10.786-05:002018-08-08T13:37:10.786-05:00What do you think about BH What do you think about BH Anonymoushttps://www.blogger.com/profile/01840630817168068131noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57540246101922406862018-06-05T09:54:01.393-05:002018-06-05T09:54:01.393-05:00wasn't this problem featured in a recent episo...wasn't this problem featured in a recent episode of rick and morty? tarski undefinabilityhttps://www.blogger.com/profile/11663853074421729634noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78127803575415500272018-06-03T03:42:26.492-05:002018-06-03T03:42:26.492-05:00Hi Lance,
Thank you for your wonderful post. You...Hi Lance, <br /><br />Thank you for your wonderful post. You ask how many alternation can we handle? The answer is that using Theorem 7.4, our lower bound would still hold for any f(n) = o(n/log(n)) alternations.<br /><br />Best, Avishay.<br />Anonymoushttps://www.blogger.com/profile/13716182434847416237noreply@blogger.com