# Non-commutative quantum counting with aggregate constant work per increment

Classically, it's very easy to create an incrementing function that can perform up to $n$ increments with $O(n)$ work:

class Counter:
def __init__(self):
self.bits = []
def increment(self):
for i in range(len(self.bits)):
self.bits[i] = !self.bits[i]
if self.bits[i]:
return  # SHORT CIRCUIT
self.bits.append(True)


Although any given increment may take $O(n)$ work individually, it must also create a situation where the following increments are cheap due to short-circuiting.

When working with qubits, the above approach doesn't work. The short-circuiting test would require a measurement, and various parts of the superposition would have to short-circuit at different times.

With that in mind, consider the following circuit. It keeps applying some unspecified and possibly varying operation to a qubit then doing a conditional increment:

Each increment here is being done naively, so each of the $n$ increments requires $O(\lg n)$ gates and the overall circuit has $O(n \lg n)$ cost. Even though, within each component of the superposition, most of that work is wasted on most increments. Classically we would only need $O(n)$ gates total.

Is there some way to optimize the circuit down to $O(n)$ gates, without depending on the details of $U$?

My initial idea for this problem was to store all the controlled outcomes separately, then merge them pairwise until they were all in a single counter. That would be $O(n)$ aggregate work as desired. But for it to work identically to the original circuit you need to uncompute all the sub-counters used during merging, and the uncomputing doesn't seem to work when the counted values don't commute (e.g. if $U = H$).