Given N bits on a reversible computer, I want to compute their Hamming weight (into a binary register) while using a minimal number of FullAdder circuits (takes 3 bits, outputs their sum as 2 bits) and while minimizing work space.
For reference, this is what a reversible FullAdder looks like:
The important thing to notice is that you need an ancilla bit to hold the carry output, and this ancilla bit sticks around until you uncompute the FullAdder. There tends to be a tradeoff between the amount of uncomputation work you do and the maximum number of ancilla you have at any time (see: Pebble Games).
I'm looking for strategies that have interesting tradeoffs between the maximum number of ancillae and the number of FullAdder computations/uncomputations performed, in the context of popcounting a bunch of bits.
Here are three example strategies:
If you simply iteratively merge bits using FullAdders until you're left with a binary register, without ever doing any uncomputation, you compute the total weight using a linear number of FullAdders and ancillae (specifically, between N-lg(N) and N of each).
Divide the input into $\sqrt{N}$ groups of size $\sqrt{N}$. Prepare a result register with $\lg N$ bits. For each group: compute the group's weight using strategy #1, add the group's weight into the result register, then uncompute the group. This uses $\sqrt N + \lg N$ ancillae, but increases the number of FullAdder computations and uncomputations from $N$ to $4N$.
Same as strategy #2, except instead of falling back to strategy #1 when computing the group totals you recurse using the same method. This increases the FullAdder applications to $O(N (\lg N) (\lg \lg N))$, but reduces the ancilla usage to $2 \lg N$.
I am especially interested in whether or not it is possible to reduce the ancilla usage without increasing the number of FullAdder applications by such a large amount. The underlying context is quantum computation, where error corrected FullAdders are billions of times more expensive than classical ones, so I care about the constant factors.