Comment by krastanov
2 days ago
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 |+++++++>
When the amplitude has norm 1, there is only one nonzero amplitude. Changing basis does not affect the number of basis functions.
> 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.
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.
3 replies →
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.