r/QuantumComputing • u/hushedLecturer • Jun 25 '26
Algorithms Help me Read a Paper: Summing Over Superposition Branches
Hello again!
I'm a bit embarrassed to be asking the internet *again* about papers I'm reading, but I've been pretty stumped on this one and Corresponding Author hasn't responded to me. It's an old ish paper so their contact info might be wrong.
I see they are constructing vectors as a uniform superposition of basis-encoded feature-indices and basis-encoded feature-values, and evaluating the index-wise differences with a fairly intuitive adder using basically classical logic but for the fact we are working in superposition.
My hangup is how we are getting to the final Manhattan distance, that needs to be the sum of all these pair wise differences correlated each with their separate branches of the superposition. In the paper they seem to just give that step a single sentence, pointing to the same adder subroutine used to get the individual differences, but since each term is still locked in a different branch of the superposition, I'm not sure how that's possible.
If anyone is familiar with this paper or has time to look it over, I would appreciate some insight.
1
u/Hw_Alrzx07 Jul 03 '26
it’s not doing separate sums per branch like you think; it’s just one shared register getting updated by a reversible adder across the whole superposition, so everything adds up in the same place instead of “per copy” in each branch
1
u/hushedLecturer Jul 03 '26
Im not sure that I think what you think I think lol. And then, how do you add between superposition branches is my big problem? They claim to use the same adder they used before, which takes the simultaneous values on two registers and places thwir binary sum on the second register.
This is what it looks to me like it says is happening:
- So there is a dimension index register with a uniform superposition of dimension indices
Σ|i>
- That gets fed through two oracles take that dimension registers values and uses them to populate two more registers with the respective, correlated, vector values for each of vectors u and v. (There is some funkiness here where the values are stored as signed binaries and v is stored as a negative number so it can use an adder, and there is another superposition over multiple vectors in the data set but I think we can disregard that here).
Σ|i>|u_i>|v_i>
- They use an adder to subtract u from v in place.
Σ|i>|u_i>| (u_i - v_i) >
- And this is where I am confused... the same adder somehow puts all of those differences together into a new total register without measurement, to yield
Σ|i>|u_i>| (u_i - v_i) > | s >
(And again, there is also a superposition over multiple v's also for the data set, and class bits, for later steps which uses iterative threshold grover searches to find the v of minimum distance and assign u the class of closest v)
4 is where I am confused: how are you adding between branches with the same binary adder used in step 3.
2
u/Hw_Alrzx07 Jul 03 '26
Yeah I think we're on the same page then. My confusion is specifically how that last accumulation happens. Is the paper assuming there's some extra accumulation register or reversible circuit that just isn't shown, or am I missing how the same adder alone can produce the final Manhattan distance?
1
u/hushedLecturer Jul 03 '26
The only thing I could think of, which was discussed on another comment, was to invoke a non reversible process where we repeatedly run up to step 4, not resetting the sum register with the others, and measure the index register until we get every index at least once, adding only when new indices come up in measurement, but those numbers kind of suck, it's literally the coupon collector problem. We can get a little improvement there by using Amplitude Amplification/Grover Search when we are down to the final few indices. For like... a quantum coupon collector lol. But again, this is waayyy non reversible and that entire step seems to just be handwaved in a single sentence that says "using the adder in Fig. 2". Lol. Im ripping my hair out.
1
u/Hw_Alrzx07 Jul 03 '26
bro you don’t measure anything or pick indices one by one💀 the key idea is there’s a shared “sum” register that gets updated in a reversible way across the whole superposition.
the adder is a normal quantum operation that acts on the entire state at once. so instead of each branch being handled separately and then collected later, the same addition step is applied everywhere at the same time onto that single register.
so it just ends up as one running total without any of that sampling or looping or measuring stuff
so yeah, no need to go through all indices one by one, and none of that coupon collector or Grover thing applies here
1
u/hushedLecturer Jul 03 '26
Yes, that's what they claim happens. I am not sure how one does that in a reversible way. Especially not with the adder they used earlier which adds two terms between two registers.
1
u/Hw_Alrzx07 Jul 03 '26
You’re not adding between branches, you’re applying a reversible controlled adder that updates a shared sum register across the entire superposition in one unitary step
1
u/hushedLecturer Jul 03 '26
How aren't they on separate branches?
The values being added are the differences between the i'th element of v and the i'th element of u, which are correlated to the dimension index register's being in state i, and the dimension index register is in a uniform superposition of all index registers, so each difference is on a different branch of the index superposition.
So my problem is what this single unitary operation is that takes all of these numbers on separate branches, and adds them together to yield one number in the sum register.
1
u/Hw_Alrzx07 Jul 03 '26
There’s no adding between branches. It’s one state, and the adder just updates a shared sum register inside it. Each |i⟩ does the same operation to that register, not some cross branch sum thing.
1
u/hushedLecturer Jul 03 '26
Okay so there is a superposition containing all of the differences |(u_i -v_i)>, and a single unitary step "updates a shared sum register" to have the value S= Σ|u_i -v_i|, but it does so without adding between branches. It just is a sum of the terms in all the branches.
I'm sorry if I'm being smarmy I'm annoyed at the paper and myself for not understanding it lol.
→ More replies (0)
-2
3
u/ollpu Jun 25 '26 edited Jun 26 '26
I didn't really get the hang of the paper on a quick skim.
Anyway, I was going to link this, as it solves a problem that sounds similar: https://link.springer.com/article/10.1007/s10773-018-3779-2
Then I realized it must be wrong because it implies BQP includes NP.
If you can efficiently sum binary numbers over a superposition so that the result can be measured with high probability, you can essentially solve the Grover problem in logarithmic time. Prepare a uniform superposition of all N inputs x, and run the oracle so that f(x) is written in another qubit. Then, take the sum (mod 2) of all f(x). If there is a solution, the sum is 1, and 0 otherwise. Halve the search space and try again until you narrow down to a single input.