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?