1
$\begingroup$

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?

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.