Comment by krastanov
2 days ago
The initial state was the example given. It is fair to then point out the consecutive states though. A few points still hold:
- I am not saying that you have to find a basis in which your amplitudes are not small, I am saying that such a basis always exists. So any argument about "small amplitudes would potentially cause problems" probably does not hold, because there is no physical reality to "an amplitude" or "a basis" -- these are all arbitrary choices and the laws of physics do not change if you pick a different basis.
- In classical probability we are not worried about vanishingly small probabilities in probability distributions that we achieve all the time. Take a one-time pad of n bits. Its stochastic state vector in the natural basis is filled with exponentially small entries 1/2^n. We create one-time pads all the time and nature does not seem to mind.
- Most textbooks that include Shor's algorithm also include proof that you do not need precise gates. Shor's algorithm (or the quantum Fourier transform more specifically) converges even if you have finite absolute precision of the various gates.
- Preparing the initial state to extremely high precision in an optical quantum computer is trivial and it has been trivial for decades. There isn't really much "quantum" to it.
- It is fair to be worried about the numerical stability of a quantum algorithm. Shor's algorithm happens to be stable as mentioned above. But the original point by OP was that physics itself might "break" -- I am arguing against that original point. Physics, of course, might break, and that would be very exciting, but that particular way of it breaking is very improbable (because of the rest of the points posted above).
I don’t think we can discuss precision usefully without numbers. We seem to agree on the word “finite” but that covers a lot of ground. “High” precision in rotating an optical polarization to exactly 45 degrees is maybe 60 dB, +- 0.0001% of the probability. That means the amplitudes are matched within 0.1%. 0.1% is fine for two qubits with 4 states. It might work for 8 qubits (256 states). For 256 qubits, no.
Gah, I wrote the wrong thing. If each probability is 50% +- 10^{-6} then the amplitudes are matched to within around 2 times 10^{-6}.
But when N>2 this gets tougher rapidly.
If we add 10^12 complex amplitudes and each one is off by one part in 10^{-6}, we could easily have serious problems with the accuracy of the sum. And 10^12 amplitudes is "only" around 40 qubits.