tag:blogger.com,1999:blog-3722233.post1096889632414067693..comments2024-03-18T23:13:09.570-05:00Comments on Computational Complexity: What comes first theory or practice? Its Complicated!Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-43179146956090127712019-11-02T14:20:17.554-05:002019-11-02T14:20:17.554-05:00The first implementation of quantum crypto is actu...The first implementation of quantum crypto is actually pretty interesting. It was put together on a shoestring by Charlie Bennett and John Smolin, and you could decode the secret key by <i>listening</i>. See <a href="https://dl.acm.org/citation.cfm?id=1014626" rel="nofollow"> this paper</a>. But it made physicists start paying attention. Peter Shorhttps://www.blogger.com/profile/13823970640202949073noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89960128074321470382019-10-07T21:19:23.596-05:002019-10-07T21:19:23.596-05:00I don't think coding up a proof for P(c) reall...I don't think coding up a proof for P(c) really counts as "practice".<br /><br />Oh, and the theory of quantum crypto came well before anyone thought of implementing it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44722811632391527262019-10-07T14:38:46.874-05:002019-10-07T14:38:46.874-05:00My reading of the first occurrence of quantum supr...My reading of the first occurrence of quantum supremacy (<a href="https://arxiv.org/abs/1203.5813" rel="nofollow">arXiv:1203.5813</a>) is as an IRL thing. I think most quantum computer scientists have given up on the goal of (unconditionally) separating BQP and P (using decision problems) since Bernstein and Vazirani (<a href="https://doi.org/10.1145/167088.167097" rel="nofollow">10.1145/167088.167097</a>) showed that BQP is in P^#P back in 1993.<br /><br />An interesting direction is to separate BQP from P using a <em>classical</em> cryptographic assumption (not like factoring is hard, but like indistinguishability obfuscation exists.) See <a href="https://arxiv.org/abs/1909.10503" rel="nofollow">arXiv:1909.10503</a> for more details on this conjecture.Sankethhttps://www.blogger.com/profile/11580913467433367094noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86566988965437086232019-10-07T09:50:12.372-05:002019-10-07T09:50:12.372-05:00Apparently, Quantum Supremacy was coined by John P...Apparently, Quantum Supremacy was coined by John Preskill, cf. https://www.quantamagazine.org/john-preskill-explains-quantum-supremacy-20191002/B.noreply@blogger.com