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$).
Non-commutative quantum counting with aggregate constant work per increment
quantum computing