Reimplement Add bloq using idiomatic Qualtran constructions

[shab5]

The current Add bloq takes too long and/or crashes on decomposition. We should reimplement using this algorithm with this PR as a starting point.

[daxfohl]

I'm pretty sure the problem is here:

Qualtran/qualtran/bloqs/arithmetic/addition.py

Line 162 in a49abdc

yield from self._left_building_block(inp, out, anc, depth + 1)

Qualtran/qualtran/bloqs/arithmetic/addition.py

Line 175 in a49abdc

yield from self._right_building_block(inp, out, anc, depth - 1)

Python doesn't have tail-call optimization, so this is just going to push every recursive call onto the stack. Obviously with large bitcount adders, this will overflow.

Moreover, I'm pretty sure this would exhibit quadratic time complexity, due to the yield from at the end. I'm pretty sure yield from adds some constant overhead for each thing that is yielded. So at the top of the call stack (assuming you get there without overflowing), it yields one item, then the next layer down yields its own thing plus re-yields the top thing, then the third layer yields its own thing plus the two things from the top two layers, etc., so you end up with (n*(n+1)/2) total yield operations (times some constant for this particular case since each layer adds more than one thing).

So if you get rid of the recursion and instead use a for loop that appends to a list, I think that would vastly improve the decomposition performance, without having to migrate to a completely different algorithm.

(I'd actually recommend against using generators in general except in cases you truly need to support infinite streams. They're tempting because they let you support partial computation "for free", but IME they end up getting in the way when you're trying to debug something and all you have is a thunk, or when you forget and try to iterate it twice and it's empty the second time but it takes you a half hour to realize what happened, or when you have to keep calling list(some_generator()) and wish it just returned a list in the first place, not to mention the runtime overhead it adds, and subtleties like the one we're dealing with here. I wouldn't expect anywhere in decomposition land to only want the first N elements of a decomposition, so I'd probably push for changing the decomposition interface to return a sequence instead.)

cc @mpharrigan

[mpharrigan]

Right. I don't think Python recursion is the appropriate way of constructing this circuit. It's pretty easy to conceive of it imperatively.

I think @shab5 opened this because he wanted to take a stab at it

[shab5]

Right. I don't think Python recursion is the appropriate way of constructing this circuit. It's pretty easy to conceive of it imperatively.

I think @shab5 opened this because he wanted to take a stab at it

Yes. I would like to take this on. Though it's probably not going to be until after the next release of the web app.