tag:blogger.com,1999:blog-3722233.post4794823229628622346..comments2022-12-05T18:19:09.447-06:00Comments on Computational Complexity: Almost Famous Quantum Polynomial TimeLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3722233.post-51945451703159613972018-04-03T16:30:45.278-05:002018-04-03T16:30:45.278-05:00I can easily prove that the (promise) decision pro...I can easily prove that the (promise) decision problem languages of BQLOG is in P (just simulate the system then check if the probability to accept is above 2/3). But AFBQP is not yet provably equal to P^BQLOG since it gets the actual probabilistic output of the quantum subsystem. This means that it can use the quantum sub-system to generate random bits. This makes it equal to BPP. So I think that you have some minor errors in your April fools post.Trev_litehttps://www.blogger.com/profile/07756053258694303637noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57843801080074274742018-04-01T12:26:25.790-05:002018-04-01T12:26:25.790-05:00I think that these earlier results of Alagna, show...I think that these earlier results of Alagna, showing the distinction between left and right-handedness may be of interest <br />https://www.youtube.com/watch?v=1KZa6RypYO8 <br />https://www.youtube.com/watch?v=Owp0FxRCkc0<br />CSProfhttps://www.blogger.com/profile/07212822875614144307noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83264208382825144342018-04-01T11:22:20.056-05:002018-04-01T11:22:20.056-05:00This is probably obvious but why can't you sim...This is probably obvious but why can't you simulate this model on a classical Turing machine (with polynomial overhead)?Sankethhttps://www.blogger.com/profile/11580913467433367094noreply@blogger.com