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}})$


  • $\begingroup$ @MarkS edited thanks. $\endgroup$ Aug 4 '19 at 1:04
  • $\begingroup$ Have you tried simplifying your final formula using identities for the sum of a geometric progression? $\endgroup$
    – DaftWullie
    Aug 5 '19 at 5:44
  • $\begingroup$ @DaftWullie I have been but I'm getting some rather messy equations. I will keep updating this post as I try further thanks. $\endgroup$ 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.