An Explanation of Shor's Quantum Factoring Algorithm
algassert.com
algassert.com
This article contains the sentence, "A good predictor for whether you even slightly understood that last sentence is whether or not your mind just got blown hard." It blew my mind, but mostly because I'm just amazed that there are people who are capable of engineering this kind of chaos into something useful. Not sure if that's what he meant.
I would really like to get a handle on all this, but I'm thinking now that I would have to retire to do so.
I'm tired of people trying to find or make shortcuts to advanced topics. If you want to truly understanding something, put in the work. Shor's actual paper for this is only 25 pages. You need a strong background in advanced linear algebra and quantum theory to understand it. If you don't know quantum theory and linear algebra, you are fundamentally incapable of understanding Shor's algorithm. It's like trying to understand how compound interest works in finance without understanding what multiplication is. There's no point, you shouldn't even try. It's wasted time, and anyone who says otherwise is missing the point.
If you're serious about wanting to understand advanced topics, put in the damn work. Stop trying to find or make shortcuts. Shortcuts only produce a bunch of know-it-all armchair scientists that think they understand something just because they read a blog post about it. People spend their entire lives studying these topics. Are you so presumptuous?
Don't get me wrong, analogies and novel perspectives can be invaluable learning tools. But they can never be a substitute for the fundamentals, only supplement them.
Anyway, I apologize for the rant. The author is clearly interested in QI and has put a lot of effort into his articles. That is to be applauded. But I caution anyone reading this, or any other article on QI, to be aware of the fact that he or she is reading a shortcut and should not believe that he or she has actually understood Shor's algorithm.
This is a pedantic comment that isn't useful for anyone. I do research in an intersection of these fields (photonics, statistical learning, and optimization theory) and I often find myself expending a lot of effort reading a paper in a field that's just outside of that reach. Reading this isn't "trying to find a shortcut," yeah I can put in the work to understand Shor's algorithm[0] from the original paper, or I can read a post with the bigger ideas and then go through a formal proof on a textbook on the original if I'm actively interested, instead of spending 5-10 hours of my time reading through the paper, understanding the complete notation and then filling in all of the missing steps that appear in such texts just to find out that it's not that interesting to me, in general.
Posts like these are the reason I've learned about fields I didn't know about before---sometimes they've also been the reason I've realized some of my work has analogues in different fields than my own.
Don't just put other people down for the sake of doing it; if people read this and pretend they're experts on the topic, then, like being an 'armchair expert' in any other topic, it'll be evident from a single conversation with them. Apart from that: who gives a damn?
-----
[0] This is a poor personal example since part of my undergrad focus was quantum information theory, but take the general case, here.
Also, a subject's complexity is no excuse to not try and explain it in an accessible way. I find it far-fetched that someone would read a blog post on QC and then assume they're a specialist; and if they do it's not the author's fault. Articles like this help present the field to non-specialists, it allows people to have a basic understanding of Shor's without having to go through years of education/training.
Finally, saying "these kind of articles are ultimately "popular science"" makes me question whether you actually put in the work to read this.
In any case, the main reason why I think of this article as "popular science" is because it fails to even attempt to explain quantum fourier transforms in layman's terms. The author even admits that such an explanation is beyond the scope of the article and instead uses the analogy of audio signal processing to draw an analogy between audio signals and QFT, hand-waving at some connection between the two solely by virtue of the fact that both use Fourier transforms. I am sorry, but I have seen this cliche way too many times--that quantum physics and music/audio are somehow intertwined and can be used as analogies for each other, just because of the fact that both can be described as waves? In the end, the most essential part is left unexplained, and only a vague analogy with a more familiar system (audio) is drawn, leaving only an imprint of false understanding. Popular science.
Since QFT is a prerequisite for quantum factoring, in my opinion this article does not explain a thing. Sure, people may become more interested in QI after reading this article, but in that case, let's be honest about what this article is: an advertisement, not an explanation. Show me a macroscopic system that exhibits true wave-particle duality and can be used as an analogy for quantum systems, then I'll take it seriously.
With the "true" in that sentence, we might be dealing with some moving goalposts, but this[0] is a well-known classical system which behaves similarly to a Bohmian description of QM and also exhibits interference, etc, on double-slit experiments.
-----
If you genuinely understand a topic, you can produce an explanation anywhere an between, and achieve any compromise between hand-wavy and substantive explanation. And anything that bridges the gap will make the next level of rigor easier.
>Don't get me wrong, analogies and novel perspectives can be invaluable learning tools. But they can never be a substitute for the fundamentals, only supplement them.
You're disagreeing that the dynamics communicated by the intermediate paper can accomplish any relevant (thing that can be called) understanding because it's not "the fundamentals". In contrast, I insist that there are "blurrier" models that communicate something substantive without going all the way to the academic model.
Propagation of false or incomplete ideas is more harmful than no communication at all (IMO).
It's no use to talk of all "intermediate" papers in general, as they are all different. Some are wildly successful at what you describe. I'm only talking about this one.
I don't claim that this one succeeds at being a good intermediate paper, only that you shouldn't dismiss all such articles in preference for the ultra-rigorous one, as your original comment was suggesting.
If you think this one is failing to convey the key insights and/or worsens someone's understanding, then I would agree you should raise and elaborate on that point.
- How quadratic residues can factor a modulus.
- How to take a signal with peaks at k/P and derive P from a single sample.
- The general flow of modular-exponentiation to period-finding to quadratic residues to factoring.
But that's all mostly classical stuff that programmers would be expected to be able to follow in full detail. You're right that there is no focus on the fundamentals behind the QFT. Instead, there's a focus on concrete "if you do this, you get that" examples with links to a simulator to back up those assertions.
Some people learn best by starting with fundamentals. Others learn best by starting with examples. Most do a bit of both. It's inaccurate to call something "pop science" because it did some concrete-example-first explanation. Pop science articles don't have fundamentals or concrete examples. They just make joke analogies to Doctor Who or whatever and call it a day.