Implementation of a non QFT based adder

[Kharazitd]

Feature details

Hello. I would like to add a method to the Adder subroutine that implements the adder without using the QFT. It is based on incrementer circuits, and constructs the adder by stringing together incrementers and decrementers to efficiently(?) add or subtract a constant (modulo 2**(number of wires)) from any input bit string. I do not know what is the best way to add such a feature. My initial thoughts would be to add an kwarg to the Adder function which toggles the method. The reason why this would be nice is that if the number of wires is large, implementing the phase adder will require implementing very precise controlled rotations, which may incur a large overhead in practical settings. As I am using this method to construct LCUs, something else that I noticed is that I generally get a dense block encoded matrix (albeit with relatively small values on the matrix elements that should be exactly 0) from using QFT based adder in the block encoded matrix. With this approach, those entries are exactly zero.

The currently implemented construction will require O(n^2) Toffoli gates when the MultiControlledX gates are compiled down, but can be improved to O(n) Toffoli gates if one were to implement the incrementer found on Gidney's blog by employing an additional ancilla qubit. I have not yet implemented this optimized O(n)-scaling version of the adder just yet, but that is my next goal. I figure it is good to just do one thing at a time. Perhaps once I implement this version it could be toggled with a different kwarg?

Would this be a useful addition to the repository?

I will add my current Python code that demonstrates the method with Pennylane, which I attach as increment_code.txt. I have done some basic testing, and the method seems to work for all of the cases I have tried, so I don't think there any obvious bugs in the code. There may also be room for improvement in terms of how the adder by a non-unit constant is implemented. The way it is currently implemented (which just represents the addition constant as a sequence of increments and decrements by powers of two) was the only way I could see how to construct it without just iterating the inc(dec)rementer by the constant. I would be very happy to discuss any ideas people have on how this part, or any other portion of the implementation, can be improved.

Thanks for your time.

[increment_code.txt](

increment_code.txt

)

Implementation

I have made some comments in the initial post that describe some ideas for implementation methods, and have included an example code showing the method.

How important would you say this feature is?

1: Not important. Would be nice to have.

Additional information

No response

[KetpuntoG]

Hi @Kharazitd! This is something we are interested in, thank you for opening the issue 😄

As you propose, it makes sense to add a kwargs (by default “qft” so as not to modify the UI) that determines the decomposition to use. On the other hand, although the use of auxiliary qubits significantly reduces the complexity, I would suggest leaving the decomposition with the multicontrols and not using auxiliary qubits. These simplifications can be made at a later stage

Regarding the code you send, I like it but you can optimize it a bit 😉 Get the binary expression of the number you want to add, does the position of the “1 ”s tell you anything? (edit: I just see you mentioned that! :))

Finally, to make this technique fit with the UI, it would be great if you could work with any modulus, not just powers of 2. My intuition tells me that you can use the same strategy we followed with the QFT based on figure 2 of this paper.

Do you agree with what I say? Feel free to ask any questions/suggestion 💪

[Kharazitd]

Thanks for the feedback @KetpuntoG . I will definitely work on the case for when we desire to do addition modulo not a power of 2.

In the edit when you say that I mentioned that, do you mean that I have implemented already the suggested optimization? I agree that there is definitely room to optimize the adder by a non-unit, but I am just wanting to confirm if your suggestion is different than the currently implemented approach. Something I would like to know is if the addition by constant can be implemented with O(n) multi-control gates using a better approach than the one I employ. In my current approach, I believe the number of independent increments scales with min(num_set_bits, num_unset_bits + 1) <= ceil(n/2) in the binary decomposition of the addition constant. I should also note that in the current approach, addition by a non-negative constant power of 2, say j only requires doing the incrementer circuit on the n-j high bits of the register, so it's more efficient to "overshoot" than "undershoot" in the representation of the addition constant as a signed summation of powers of 2.

Also, I've currently implemented the decrementer by conjugating with "X" gates on the wires that the adder is acting on. It would be equivalent to also replace all the controls on 1 with controls on 0, is there any preference between these two approaches?

[KetpuntoG]

What I mean is that instead of using the closest_power_of_2 function iteratively, it might be easier to simply express the number in binary :) The 1s will give you the same information

As for the implementation, I had in mind the same idea as you, but while looking through the literature, I came across a recent paper that shows some very promising results: https://arxiv.org/pdf/2501.07060

I haven’t had the chance to dive into it yet, but it looks interesting! Would you like to take a look and share your thoughts?

[Kharazitd]

I might be missing something very obvious here, but are you suggesting to just apply the power of two increment corresponding to the location of each set bit in the binary representation of the addition constant? This is sufficient, but I don't think its as efficient as the method I am currently employing, at least in terms of the number of gates in the quantum circuit. I'm often quite guilty of premature optimization, so the following could be just that. An example of this optimization is say incrementing by 0111, where we could implement the addition by 7 by first incrementing by 1000 followed by a decrement by 0001 which requires fewer multi control X gates than doing the three increments indicated by the bitstring. This effect is more pronounced as there are more set bits. For example, incrementing by the constant corresponding to a bitstring of n set bits would require ~n^2 multi-controlled X gates, whereas the equivalent operation of decrementing by 1 requires only n-2 multi-controlled X gates. The reason why I wrote the closest_power_of_2 function was because I was (and am) struggling to find the right operations in the binary representation to determine the most efficient way to decompose the integer into the shortest (signed) summation over powers of 2. Are you aware of a simple method to do that kind of decomposition by just working in the binary representation? Is this optimization necessary? It should be doable, but it's not obvious to me how to do this just yet. It's also likely there's just a simple way to do this in the binary representation that I'm just not seeing and you are. If that's the case, I would definitely appreciate some help on how to do so.

I also have a question regarding addition modulo L > 1 not a power of 2. If we are working with an n qubit system register, and add a work wire to flag if we have overflowed to a bitstring who's value is larger than L, it seems we would need to do ~ 2^n - L n qubit controlled X gates to correctly flag an overflow (i.e. we need to check if we're in any of the states corresponding to values larger than L). Is that correct? This seems quite excessive, is there any way we can avoid that overhead, or do we just have to accept it? I am tempted to see if comparators might be able to avoid this kind of overhead, but going down that route feels rabbit holey. Am I right to think that we would then need to add (or subtract) multiples of L to the system register, controlled on the flag qubit being in the overflow state, and perform the overflow check after each application? Am I even thinking about how to do the non-power of 2 modular addition circuit in the correct way?

With respect to the posted arxiv link, that paper does indeed seem very interesting. I have only given it a cursory read through at this time, but does seem to achieve the desired goal of O(n) Toffoli gates for arbitrary addition constant, albeit using n-3 ancilla qubits. It somewhat bothers me that the increment by 1 can be done with O(n) Toffoli gates (with larger constant factor), with only a single ancilla, but that addition by an arbitrary constant seems to require many more ancilla to achieve a similar gate complexity. I don't really understand why the latter needs the additional ancilla qubit overhead to achieve the same bound. There may very well be a good reason for this, but I just don't see it yet!

Hope the questions aren't too basic! I greatly appreciate the help already provided.

[KetpuntoG]

Oh, I see. That seems like a very smart strategy. To make sure I understand, the problem can be reduced to:
Given a number to be added, $k$ , we can transform it into adding $2^m - (2^m - k)$ , with the idea that this might be more efficient. In fact, it may be even more efficient to continue recursively and, instead of subtracting $(2^m - k) $, subtract $2^p - (2^p - ((2^m - k)))$ . I would say that a simple approach could be to check whether the number of ones in $k$ is strictly greater than the number of ones in $(2^m - k)$, and do the same in the following stages. If that is the case, we decompose the addition in the two new terms.

Regarding modular addition with L not being a power of two, there’s no need to check all states! :) The algorithm works as follows:
• We start with a base state $|x\rangle$ and add $k$ , resulting in $|x + k\rangle$ .
• Next, we subtract $L$ , giving us $|x + k - L\rangle$ .
• If $L$ is greater than $x + k$ , the first auxiliary qubit flips to $1$ (note that in Fig. 2, there is an auxiliary qubit initialized in $|0\rangle$ at the top of the circuit).
• Therefore, if this auxiliary qubit takes the value $|1\rangle$ , we add L back, since $|x + k\rangle$ was the correct result.
• If this qubit remains in state $|0\rangle$ , then great! We already have our result, as $|x + k - L\rangle$ is less than $L$ . (We assume that $x$ and $k$ are initially $&lt; L$ ).

Regarding the paper, it might be better to keep it in mind but not focus on it too much. The decomposition you described earlier seems appropriate, efficient and fits our UI better. Do you think that make sense? 😄