[krastanov]

The magnitude of an "amplitude" is basis dependent. A basis is a human invention, an arbitrary choice made by the human to describe nature. The choice of basis is not fundamental. So just choose a basis in which there are no vanishingly small amplitudes and your worry is addressed.

[tromp]

Any implementation of Shor will need vanishingly small amplitudes, as it forms a superposition of 2^256 classical states.

[krastanov]

This is completely missing the point. There is nothing fundamental to an amplitude. The amplitudes are this small because you have chosen to work in a basis in which they are small. Go to the Hadamard basis and the amplitude value is exactly 1. After all, the initial state of Shor's algorithm (the superposition of all classical bitstrings) is the perfectly factorizable, completely not entangled state |+++++++>

[tromp]

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.

[krastanov]

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.

[oh_my_goodness]

When the amplitude has norm 1, there is only one nonzero amplitude. Changing basis does not affect the number of basis functions.

[krastanov]

> When the amplitude has norm 1, there is only one nonzero amplitude.

Yes, that is exactly the point. The example statevector you guys are talking about can (tautologically) be written in a basis in which only one of its amplitudes is nonzero.

Let's call |ψ⟩ the initial state of the Shor algorithm, i.e. the superposition of all classical bitstrings.

|ψ⟩ = |00..00⟩ + |00..01⟩ + |00..10⟩ + .. + |11..11⟩

That state is factorizable, i.e. it is *completely* unentangled. In the X basis (a.k.a. the Hadamard basis) it can be written as

|ψ⟩ = |00..00⟩ + |00..01⟩ + |00..10⟩ + .. + |11..11⟩ = |++..++⟩

You can see that even from the preparation circuit of the Shor algorithm. It is just single-qubit Hadamard gates -- there are no entangling gates. Preparing this state is a triviality and in optical systems we have been able to prepare it for decades. Shining a wide laser pulse on a CD basically prepares exactly that state.

> Changing basis does not affect the number of basis functions.

I do not know what "number of basis functions" means. If you are referring to "non zero entries in the column-vector representation of the state in a given basis", then of course it changes. Here is a trivial example: take the x-y plane and take the unit vector along x. It has one non-zero coefficient. Now express the same vector in a basis rotated at 45deg. It has two non-zero coefficients in that basis.

---

Generally speaking, any physical argument that is valid only in a single basis is automatically a weak argument, because physics is not basis dependent. It is just that some bases make deriving results easier.

Preparing a state that is a superposition of all possible states of the "computational basis" is something we have been able to do since before people started talking seriously about quantum computers.

[oh_my_goodness]

Sounds like we agree on how basis vectors work. But you’re talking about the initial state, and I’m talking about the output. Finding a basis that makes the output an eigenvector isn’t trivial. Take Grover’s algorithm. You have to iterate to approximate that eigenvector. Small errors in the amplitudes can prevent convergence. When you have 2^256 components, amplitudes are divided down by around 2^128.

Even preparing the initial state that accurately is only trivial on paper.

[krastanov]

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

[oh_my_goodness]

1/sqrt(N)