> 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".
> "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?
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).
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.
> 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.