A quantum computing primer for DE Shaw by Scott Aaronson today.
He opened with my 120-year Moore’s Law abstraction slide (which updates the Ray Kurzweil original with the latest processors). Some choice quotes:
A quantum computer could challenge the Church-Turing thesis itself, and that could be as important in physics as discovering the Higgs Boson or gravitational waves. And it has practical applications too. That’s a bonus.
Quantum mechanics is probability theory with minus signs.
Quantum mechanics is very simple once you take the physics out of it. Quantum information theory is a level below physics. It’s the operating system that the rest of physics runs on. General relativity has not loaded yet.
Superposition is something qubits like to do in private.
I have high confidence in the possibility of a quantum speedup. With quantum simulation, we may see a speedup before we have a full programmable universal quantum computer.
For an exponential quantum speedup you have to choreograph an interference pattern that boosts the amplitude of the right answer.
In 1994, Shor proved that factoring integers is in BQP (Bounded Quantum Polynomial time). You can find periods of periodic functions that repeat with very long periods. This works for discrete logarithms and breaks all public key crypto including elliptic curve.
Factoring integers is like period-finding, a Fourier transform on large vectors. A Fourier transform creates a kind of interference pattern, constructive when in sync with the period and destructive out of sync.
In 1995 Grover showed that if you do a unstructured search of a giant list with a quantum computer, you can get a sqrt-n speedup but not more than that.
If you want a fast quantum algorithm for NP-complete problems, you need to take advantage of structure somehow, versus brute-force search.
D-Wave’s quantum annealing is a non-zero temperature version of the adiabatic algorithm.
I want a quantum computer to disprove people who say it’s impossible.
Leave a Reply