tag:blogger.com,1999:blog-3722233.post696393720401284311..comments2024-08-02T19:37:12.269-05:00Comments on Computational Complexity: Measuring Quantum ProgressLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-49637441528139262642023-10-15T21:54:51.775-05:002023-10-15T21:54:51.775-05:00I wonder if busting RSA is as important as everyon...I wonder if busting RSA is as important as everyone claims?<br /><br />My understanding is that there were quatum-safe encryption protocols even before Shor, that more have been designed since, and that there is an implementation of at least one ready to use should a QC that can factor big numbers actually appear.<br /><br />I suppose stored files that were encrypted with RSA or the like will be problematic once such a QC becomes available, but not new translactions. System managers will have to install the new software and re-encrypt their password files, and, as with every security update, some will be slow to do so, causing problems.<br /><br />But, I submit, we need something other than breaking RSA to sell quantum computing...<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35230276302975231292023-10-15T16:50:49.667-05:002023-10-15T16:50:49.667-05:00Regarding property 2 of factoring: Subexponential ...Regarding property 2 of factoring: Subexponential integer factoring algorithms have been known for almost 50 years. See [Crandall and Pomerance 2005 - Prime numbers, a computational perspective 2ed], chapters 6 and 7.<br /><br />Quoting Crandall and Pomerance: "The quadratic sieve and number field sieve are direct descendants of the continued fraction factoring method of Brillhart and Morrison [1975], which was the first subexponential factoring algorithm on the scene." Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-899138317050665352023-10-13T16:56:31.114-05:002023-10-13T16:56:31.114-05:00I agree.
"It doesn't mean factoring is t...I agree.<br /><br />"It doesn't mean factoring is the wrong measure of the success of physical quantum computers, we're just not ready to do so."<br /><br />It is the right measure and "21" reveals how much PR nonsense quantum is doing to get money thrown at it.<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-85475846249965459902023-10-13T15:24:17.512-05:002023-10-13T15:24:17.512-05:00Maybe Regev's recent improvement of Shor's...Maybe Regev's recent improvement of Shor's circuit could lead to progress? (arxiv: 2308.06572)Mahdihttps://www.blogger.com/profile/12382401759237060260noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57995324343031754402023-10-13T06:32:46.418-05:002023-10-13T06:32:46.418-05:00This is a "hard" measure of progress in ...This is a "hard" measure of progress in quantum computing. It can't be hyped! Do you think billions of dollars will pour into quantum computing if hard measures are used to judge potential and progress?Anonymousnoreply@blogger.com