# Exponential Grover iterations in Quantum Counting

In a quantum counting circuit such as the one below:

     ┌────┐                        ┌───────┐
t_0: ┤0   ├───────────────────■────┤0      ├
│    │                   │    │       │
t_1: ┤1 H ├───────────■───────┼────┤1 iqft ├
│    │           │       │    │       │
t_2: ┤2   ├───■───────┼───────┼────┤2      ├
├────┤┌──┴───┐┌──┴───┐┌──┴───┐└───────┘
n_0: ┤0   ├┤0     ├┤0     ├┤0     ├─────────
│    ││      ││      ││      │
n_1: ┤1   ├┤1     ├┤1     ├┤1     ├─────────
│    ││      ││      ││      │
n_2: ┤2   ├┤2     ├┤2     ├┤2     ├─────────
│  H ││  G^1 ││  G^2 ││  G^4 │
n_3: ┤3   ├┤3     ├┤3     ├┤3     ├─────────
│    ││      ││      ││      │
n_4: ┤4   ├┤4     ├┤4     ├┤4     ├─────────
│    ││      ││      ││      │
n_5: ┤5   ├┤5     ├┤5     ├┤5     ├─────────
└────┘└──────┘└──────┘└──────┘


there are an exponentially increasing amount of Grover iterations required as the amount of counting qubits t increases. This seems really problematic if we want to determine precise measurements of M, since Nielsen and Chuang give:

$$|\Delta M| < \left ( \sqrt{2MN} + \frac{N}{2^{m+1}}\right ) 2^{-m}$$

Setting $$<$$ to $$=$$ and solving for $$m$$ gives

$$m = \log_2 \left(\frac{\sqrt{NM}+\sqrt{N(M+\Delta M)}}{\sqrt{2}\Delta M}\right)$$

and the amount of counting qubits required are:

$$t \equiv m + \lceil log_2(2+1/(2e)) \rceil$$

Thus if we have problems with a large $$N$$ and a low desired accuracy $$\Delta M$$, $$t$$ can quickly become relatively large. However, as we get $$t$$ to be in the 10s, 20s, 30s or above we start to get a lot of Grover iterations required, the total amount being

$$\sum_{i=1}^{t-1} 2^i$$

which can quickly become uncontrollable.

How does one reconcile this? Is quantum counting simply not suitable for these types of search problems?