5 ms·

Shor's Quantum Factoring Algorithm (2017)

53 points by sjcsjc 6y ago

osamagirl69 6y ago
Really a well written summary! A good, but not overwhelming, about of depth.
shagie 6y ago
Another explanation (that I’m fond of) is in Shor, I’ll do it : https://www.scottaaronson.com/blog/?p=208 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.
andreareina 6y ago
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-search-algorithm http://twistedoakstudios.com/blog/Post2644_grovers-quantum-s...
- all2 6y ago
  > "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?
  - kirrent 6y ago
    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.
    - Y_Y 6y ago
      Probabilities are also always real in quantum mechanics.
  - Strilanc 6y ago
    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).
gregoronio 6y ago
Damn, this must be old. It has a Code Monkey reference. That's some dusty lore.

53 points by sjcsjc 6y ago

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

Another explanation (that I’m fond of) is in Shor, I’ll do it : https://www.scottaaronson.com/blog/?p=208 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.

andreareina 6y ago

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-search-algorithm http://twistedoakstudios.com/blog/Post2644_grovers-quantum-s...

all2 6y ago
> "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?
- kirrent 6y ago
  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.
  - Y_Y 6y ago
    Probabilities are also always real in quantum mechanics.
- Strilanc 6y ago
  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).

gregoronio 6y ago

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