Shor's Quantum Factoring Algorithm (2017) | Hacker News Reader

Shor's Quantum Factoring Algorithm (2017)

algassert.com

53 pointssjcsjc8 comments

Another explanation (that I’m fond of) is in Shor, I’ll do it : https://www.scottaaronson.com/blog/?p=208

> I’ve been talking a lot recently about how quantum algorithms don’t work. But last week JR Minkel, an editor at Scientific American, asked me to write a brief essay about how quantum algorithms do work, which he could then link to from SciAm‘s website.”OK!” I replied, momentarily forgetting about the 10^10^5000 quantum algorithm tutorials that are already on the web. So, here’s the task I’ve set for myself: to explain Shor’s algorithm without using a single ket sign, or for that matter any math beyond arithmetic.

Clicking through to the post about Grover's Algorithm[1] is the mental model of all the quantum stuff that works best for me: "Like probability theory, but over the complex numbers".

[1]http://twistedoakstudios.com/blog/Post2644_grovers-quantum-s...

> "Like probability theory, but over the complex numbers".

I'm a probability novice. How would this work? Are we talking vector fields representing multidimensional probabilities? Or just probabilities that happen to depend on more than one variable?

Just that if you have a quantum system, such as a qubit consisting of the |0> state and |1> state with a combination over the two (called a superposition) represented by a|0> + b|1> then a and b can be complex. This is in contrast to classical mechanics where, for example, pr(heads) and pr(tails) must both be real.

It's only once it comes to actually making a measurement that you need to get real again.

Probabilities are also always real in quantum mechanics.

It's statistics but instead of operations preserving the 1-norm (item weights [probabilities] add up to 1) they preserve the 2-norm (squared item weights [amplitudes] add up to 1). Instead of using stochastic matrices you use unitary matrices. Everything else about quantum computing follows (...with sufficient elbow grease).

Really a well written summary! A good, but not overwhelming, about of depth.

Damn, this must be old. It has a Code Monkey reference. That's some dusty lore.

Reply on news.ycombinator.com