<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">1. sep. 2021 kl. 21:12 skrev John Levine <<a href="mailto:johnl@iecc.com" class="">johnl@iecc.com</a>>:<div><blockquote type="cite" class=""><div class=""><span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class="">Some calculations are amenable to quantum methods, some aren't.</span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""></div></blockquote></div><div class=""><br class=""></div><div class="">Just the usual standard comments:</div><div class=""><br class=""></div><div class="">* Any classical algorithm can in some sense be run on a quantum computer. You probably don’t want to, but that’s beside the point.</div><div class="">* Some specific problems have a very large quantum speedup. Examples include factoring and d.log. Unfortunately.</div><div class="">* There are very generic algorithms that provide «small» quantum speedup for many problems, for some values of «small» (perhaps surprisingly big values, depending on what value you expect «small» to have). Examples include breaking block ciphers. Which is why we have AES-256. I believe there are similar results for finding hash preimages etc.</div><div class="">* Some problems seem not to have a very large quantum speedup. Examples include many lattice-based problems, some isogeny-based problems, etc.</div><div class="">* There are many interesting results in this area. I am no expert.</div><div class=""><br class=""></div><div class="">As for reversible computations, anything you do with quantum computers must in some sense be reversible, apparently because of quantum physics, but that’s less of an obstacle to computation than you might think. In particular, there’s no problem computing SHA-x on a superposition, if you have a sufficiently large quantum computer.</div><br class=""><div class="">
<span class="Apple-style-span" style="border-collapse: separate; font-variant-ligatures: normal; font-variant-east-asian: normal; font-variant-position: normal; line-height: normal; border-spacing: 0px; -webkit-text-decorations-in-effect: none;"><div class="">-- </div><div class="">Kristian Gjøsteen</div></span>
</div>
<br class=""></body></html>