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

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!

• @MarkS edited thanks. – IntegrateThis Aug 4 '19 at 1:04
• Have you tried simplifying your final formula using identities for the sum of a geometric progression? – DaftWullie Aug 5 '19 at 5:44
• @DaftWullie I have been but I'm getting some rather messy equations. I will keep updating this post as I try further thanks. – IntegrateThis Aug 5 '19 at 6:01

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.