TE
科技回声
首页24小时热榜最新最佳问答展示工作
GitHubTwitter
首页

科技回声

基于 Next.js 构建的科技新闻平台,提供全球科技新闻和讨论内容。

GitHubTwitter

首页

首页最新最佳问答展示工作

资源链接

HackerNews API原版 HackerNewsNext.js

© 2025 科技回声. 版权所有。

Shor, I’ll do it (2007)

308 点作者 monort将近 3 年前

12 条评论

FartyMcFarter将近 3 年前
I don&#x27;t fully understand all the details, but even I can tell that this algorithm is beautiful.<p>Mixing together the concepts of modular sequences, periods, and Fourier transforms, plus doing this fast with computers that barely exist in order to find factors or numbers is just an amazing construction.<p>There&#x27;s a video featuring Peter Shor about the invention of this algorithm: <a href="https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=6qD9XElTpCE" rel="nofollow">https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=6qD9XElTpCE</a>
jstanley将近 3 年前
&gt; if you think about quantum computing in terms of “parallel universes” (and whether you do or don’t is up to you)<p>But if you <i>do</i> think of it that way, why not just pick a random number using some quantum process, classically test whether or not it&#x27;s a divisor of the number you&#x27;re trying to factor, and kill yourself if it&#x27;s not? In every universe where you survive (which, for sake of argument, are the only ones you care about) you find a factor on the first try.
评论 #32295590 未加载
评论 #32297301 未加载
评论 #32295100 未加载
评论 #32295066 未加载
评论 #32296563 未加载
评论 #32300773 未加载
评论 #32295300 未加载
评论 #32298196 未加载
评论 #32298095 未加载
评论 #32295569 未加载
评论 #32297250 未加载
评论 #32296057 未加载
ryan-duve将近 3 年前
If the part about the tack on the board under the clocks wasn&#x27;t clear, and you&#x27;re a visual learner, this video from 3Blue1Brown about the [classic] Fourier Transform might help clarify the relationship to periodicity:<p><a href="https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=spUNpyF58BY" rel="nofollow">https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=spUNpyF58BY</a>
eliben将近 3 年前
I like how there&#x27;s a comment by Peter Shor commending Scott on the article :-) Knowing Scott&#x27;s blog, this is likely legit
omoikane将近 3 年前
Near the bit that describes &quot;repeated squaring&quot;, there is this formula (note the &quot;http&quot;): <a href="http:&#x2F;&#x2F;www.scottaaronson.com&#x2F;cgi-bin&#x2F;mimetex.cgi?x^r%20=%203^{14}%20=%203^{2^3+2^2+2^1}%20=%203^{2^3}%20\cdot%203^{2^2}%20\cdot%203^{2^1}%20=%20((3^2)^2)^2%20\cdot%20(3^2)^2%20\cdot%203^2" rel="nofollow">http:&#x2F;&#x2F;www.scottaaronson.com&#x2F;cgi-bin&#x2F;mimetex.cgi?x^r%20=%203...</a><p>Firefox doesn&#x27;t want to load that due to mixed content (https page loading http), and also doesn&#x27;t want to follow the 301 redirect to the https version. Chrome appears to follow the 301 redirect (or maybe lazy-images.js does something different) such that the page renders properly.
H8crilA将近 3 年前
How does one implement the QFT? The same way as one would do FFT, but with quantum gates? I.e. taking O(n*log(n)) gates with two inputs and two outputs? I&#x27;m imagining that there&#x27;s some sort of a vector of quantum (complex) amplitudes left after the exponentiation that needs to be transformed.
评论 #32295750 未加载
评论 #32297985 未加载
Eddy_Viscosity2将近 3 年前
This was pretty good, though I would still like to know &#x27;how&#x27; the quantum computer gets all those amplitude (and how many are needed) to interfere with each other to get the answer.
评论 #32297706 未加载
评论 #32298193 未加载
评论 #32295501 未加载
georgehm将近 3 年前
&gt; And once we knew (p-1)(q-1), we could then use some more little tricks to recover p and q, the prime factors we wanted.<p>I am curious to know about these tricks to recover p, q. Does anyone know?
评论 #32298851 未加载
walnutclosefarm将近 3 年前
Congratulations to Scott Aaronson for the must lucide explanation of Shor&#x27;s algorithm for the merely mathematically literate, ever!
Sniffnoy将近 3 年前
(2007)
benreesman将近 3 年前
Sidebar: I absolutely adore Scott &quot;I don&#x27;t give a fuck anymore&quot; Aaronson.<p>My personal aspirations to this kind of biting wit are futile and vain, but my admiration for it is even greater and some people can bring it off with style to spare, and ever since that uh, thing, Scott is just playing the ten minute guitar solo.<p>Into to Number Theory with periodicity and modular math might be stretching &quot;nothing more than arithmetic&quot; a bit, but fuck it, this is the best accessible discussion of Shor I&#x27;ve ever read and if there&#x27;s any justice in the multiverse it will become the go-to link on the topic, which will mean that 10^500 laypeople will roll their eyes at the next 10^500 &quot;quantum computers are the next step after digital computers&quot; Aeon fluff pieces floating by.
评论 #32296484 未加载
评论 #32297806 未加载
评论 #32299020 未加载
mikotodomo将近 3 年前
Wow. That such high end technical content is hosted on Wordpress really shows how battle tested and reliable it is.
评论 #32298947 未加载
评论 #32298989 未加载