Matrix Inversion is BQP-complete proof in HHL and the probability of measuring $T+1 \leq t \leq 2T$

Question

I am continuing to try and fully understand the argument why Matrix inversion is BQP-complete according to the proof given in the HHL paper here, and I have hit another snag.

In this question here, I got clarification about the operator $U$ so-defined, where eventually we get for $A = I - U^{-1/T}$.

$A^{-1} = \sum_{k \geq 0} U^k e^{-k/T}$ where $U^{3T} = I$. The author then writes

This (applying $A^{-1}$) can be interpreted as applying $U^t$ for $t$ a geometrically-distributed random variable. [...]

I'm not sure why this statement is true.

From what I understand, $U$ is an operator that operates on two registers, one of size $3T$ where $T$ is the number of gates, and the other register of size $n$ initialized to $|0 \rangle ^{\otimes n}$. $A^{-1}$ is a matrix consisting of a convergent series of powers of $U$ where the coefficients are exponentials. As $k \rightarrow \infty$, the powers of $U$ are divided by such large exponentials that they vanish. I have reasoned why $A^{-1}$ is given by this sum since by left/right multiplying it by $A$ we get a telescoping series where the only value of $k$ that doesn't vanish is $k=0$.

The point of all this is that if we apply $U^t$ for $T+1 \leq t \leq 2T$, then we will be left with a state $|t+1 \rangle U_1 \ldots U_T |0 \rangle ^{\otimes n}$, where the second register will correspond to applying the $T$ gates to our initial state. I do not understand the portion of this argument consisting of interpreting the application of $A^{-1}$ as a geometric random variable.

Moreover the author/s state that measuring $t$ in the range $T+1 \leq t \leq 2T$ occurs with probability $\frac {e^{-2}}{1+e^{-2}+e^{-4}}$, and I am not sure how they got this. Any hints appreciated in order to understand this computation.

Edit: Working on this I find that the probability of measuring $T+1 \leq t \leq 2T$ should be something like :

$(\sum_{k=T+1}^{2T}(\sum_{j=0}^{\infty}e^{-(k+3j)/T}) )/ (\sum_{n=0}^{\infty}e^{-n/T}) = (\sum_{k=T+1}^{2T}e^{-k/T}(\frac{1}{1-e^{-3/T}}))/(\frac{1}{1-e^{-1/T}}) = (\frac{1}{1-e^{-3/T}})/(\frac{1}{1-e^{-1/T}}) \sum_{j=0}^{T-1} e^{-(j+T+1)/T} = (\frac{1}{1-e^{-3/T}})/(\frac{1}{1-e^{-1/T}}) e^{-(T+1)/T}(\frac{1 - e^{-1}}{1-e^{-1/T}})$

Thanks!

Answer 1

I tend to find the bit about the geometric random variable a bit misleading. What they're trying to say is that if you apply $A^{-1}$ to $|1\rangle|\psi\rangle$ and you measure the first register, you'll get the answer $t$ with a probability that goes like $e^{-t/T}$ (approximately, assuming large $T$), and that's a geometric distribution.

Now, I think the calculation they actually perform is the following: (the wording suggests it's an exactly calculation, but I don't believe it is) The probability of getting answer $t$ is, to leading order, $e^{-2t/T}$. Hence, the probability of getting an answer $t$ in the range $T+1$ to $2T$ is $$ \frac{\sum_{t=T+1}^{2T}e^{-2t/T}}{\sum_{t=1}^{3T}e^{-2t/T}} $$ where I have renormalised over all the possible outputs. If we do this as a sum over a geometric progression, you get the answer $$ \frac{e^{-2}(1-e^{-2})}{1-e^{-6}}. $$ The numerator and denominator have a common factor of $1-e^{-2}$ leaving the answer $$ \frac{e^{-2}}{1+e^{-2}+e^{-4}}, $$ as required.