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