Comment by tromp
2 days ago
The initial state of Shor's algorithm just has the n-bit number to be factored. From there it creates the superposition in the next n steps.
Forget the talk about amplitudes. What I find hard to believe is that nature will let us compute reliably with hundreds of entangled qubits.
Shor's algorithm does not start with the qubits storing anything related to the n-bit number to be factored. The n-bit number is encoded *only* in the XOR-oracle for the multiplication function.
Shor's algorithm starts with the qubits in a superposition of all possible bitstrings. That is the only place we have exponentially small amplitudes at the start (in a particular choice of a basis), and there is no entanglement in that state to begin with.
We do get interesting entangled states after the oracle step, that is true. And it is fair to have a vague sense that entanglement is weird. I just want to be clear that your last point (forgetting about amplitudes, and focusing on the weirdness of entangled qubits) is a gut feeling, not something based in the mathematics that has proven to be a correct description of nature over many orders of magnitude.
Of course, it would be great if it turns out that quantum mechanics is wrong in some parameter regime -- that would be the most exciting thing in Physics in a century. There is just not much hope it is wrong in this particular way.