Counting reversibly using few FullAdders and little work space

Question

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:

1. 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).

2. 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$.

3. 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.

Answer 1

Here is a construction with $3N + O(\lg N)$ adder computations/uncomputations and $2 \lg(N)$ ancilla usage.

• Divide the input into $N/\lg N$ groups of size $\lg N$.
• Allocate a result register of size $\lg N$.
• For each group $g$:
  • Use the naive strategy to compute $g$'s weight using $\lg N$ adder computations and space.
  • Add the weight into the result register using $\lg N$ adder computations and uncomputations.
  • Uncompute $g$'s weight using $\lg N$ adder uncomputations.
• The result register now contains the total weight.

The inner loop uses $3 \lg N$ adders, and runs $N / \lg N$ times, for a total of $3N$ adders. Half of the $2 \lg N$ ancilla bits are for the result register, and the other half are for the group weight computations.

Basically, using groups of size $\lg N$ instead of $\sqrt{N}$ gives an exponential improvement in space usage but only a constant factor loss in adders.