Does "quantum registers with $n$ qubits are able to hold $2^n$ values and therefore scale exponentially" actually hold that straightforwardly?

Question

A lot of people claim that quantum provides exponential speedup whereas classical computers scale linearly. I have seen examples (such as Shor's algorithm and Simon's) that I believe, but the layman's explanation appears to boil down to "quantum registers with n qubits are able to hold $2^n$ values." To me, this sounds a lot like having a SIMD (Single Instruction Multiple Data) CPU where I can load two times $2^n$ variables, and
a) get the correct outcomes, and only these outcomes
b) trace back which answer is to which questions

When trying to do this in quantum computing, I think this is definitely not the case. Let me try to evaluate this with an example:
Say I have two 2-qubit registers , and I want to add two sets of values (2+1 and 1+2):
$a|10\rangle + b|01\rangle$
$a|01\rangle + b|10\rangle$
where a denotes values in register a, and b denotes values in register b. Aka a and b are not scalars

If we now look at the cubits, we see that all are once 0, and once 1. This implies a superposition of all qubits in our input. If we now were to do an addition on the two registers that both hold 2 qubits in superposition, and repeat this experiment sufficient enough times to create a probability distribution, I believe we would end up with a probability distribution for all outcomes as follows:
$P(0) = 1/16 $
$P(1) = 2/16 $
$P(2) = 3/16 $
$P(3) = 4/16 $
$P(4) = 3/16 $
$P(5) = 2/16 $
$P(6) = 1/16 $

If we look at what we wanted to calculate, 2+1 and 1+2, we see that both our answers (two times the answer 3) are indeed present in the set of outcomes. However,
a) there are a lot of other answers
b) we can not trace which answer corresponds to 2+1, and which to 1+2

So my questions:
a) Is it correct that for the addition of two sets of randomly chosen variables, we are not guaranteed to see exponential scaling (unless we want to add all values 0 to 2^n with themselves)
b) Is it correct that, when doing simple classical addition, we loose track of the mapping from input to output

And as a bonus, does the following hold:
When performing the computation as above, the usability would be the same (or worse, as the mapping from input to output is lost) as a lookup table with the same number of input values, as when we have two registers in superposition, we will always receive the same output distribution

Answer 1

Does “quantum registers with n qubits are able to hold $2^n$ values and therefore scale exponentially” actually hold that straightforwardly?

No, it doesn't. That's the popularised explanation of where quantum computers get their speed-up, but it's far more nuanced than that.

To illustrate this, imagine you have a function $f:x\in\{0,1\}^n\mapsto y\in\{0,1\}^m$. Sure, in quantum you can produce the state $$ |\Psi\rangle=\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}|x\rangle|f(x)\rangle $$ so, in some sense,the function $f$ has been evaluated at every $x$. But what answers can you get? What you certainly cannot read out is every different value of $f(x)$: when you measure (assuming projective measurements) you get a maximum of 1 bit of information for every measurement, $n+m$ bits. But there are $2^n$ inputs, each with $m$ bits to learn, so you need to be able to determine $m2^n$. This is not really any better than doing things classically (in a sense, it's a bit worse because a single measurement will pick an $x$ at random, but classically you'd normally only get the $m$ bits of information from the final outcome).

The real power of quantum computation comes from doing something clever with that state $|\Psi\rangle$. This usually relies on some special properties that you know about $f(x)$, such as "it has a global property which is parametrised by $k$. Find $k$.". For example, in the Deutsch-Jozsa algorithm, the structure is that either all $f(x)$ are the same, or there's a perfect 50:50 split between answers (Here, $k$ is one bit of information). That sort of comparison between different function evaluations in a classical domain obviously needs lots of different function evaluations, whereas in the quantum domain, sometimes one can perform the right measurement that compares different parts of the superposition and gives you the right information out.

Answer 2

I'm going to answer in two parts:

Regarding your example with addition, a quantum adder has been discussed in the question How do I add 1+1 using a quantum computer. They're a bit involved and I'm not sure if I exactly follow your line of thinking for your questions following your example, but hopefully that link explains a bit about how a quantum computer would handle addition.

With regards to your more general question about quantum speedups, the important thing isn't that quantum computers can hold up to $2^n$ values in $n$ qubits, as that is also true in a classical computer. The important thing is that they can hold all these $2^n$ values at once. A lot of quantum algorithms start by taking a register of $n$ qubits all in state $|0\rangle$ and applying a Hadamard transform to all bits. This leads to the register being in the state

$$|\psi\rangle = \displaystyle\sum_{i=0}^{2^n-1}|i\rangle$$

Which can be fed into an algorithm and have it work on each piece simultaneously. If you look at this explanation of Grover's Algorithm you can see this at work. By plugging in this uniformly distributed $|\psi\rangle$ into a circuit which picks out a specific element, one can isolate that element without having to cycle through each of the possible $2^n$ values for $|i\rangle$ individually. Although Grover's algorithm isn't an exponential speedup, the same sort of structure holds for more complex algorithms as well.

Hopefully that helps!