Suppose I want solve a lower diagonal linear system of equations given in block form by

$ \left( {\begin{array}{cccc} I & 0 & \cdots & 0 &0\\ M & I & \cdots & 0 & 0\\ \vdots & \vdots & \ddots & \ddots & \vdots\\ 0 & 0 & \cdots & M & I\\ \end{array} } \right) \left( {\begin{array}{cccc} \bf{h_{0}}\\ \bf{h_{1}}\\ \vdots\\ \bf{h_{n-1}}\\ \end{array} } \right) = \left( {\begin{array}{cccc} \bf{h_{in}}\\ 0\\ \vdots\\ 0\\ \end{array} } \right) $

where $M=BA^{-1}-I$ for known matrices $A$ and $B$. $I$ is the identity matrix, and $\bf{h_{in}}$ is a known initial condition vector.

My question is, is it possible to compute $A^{-1}$ within the quantum subroutine and then use it to setup and solve (using HHL) the above linear system of equations? If so, what methods would you use to do this?


1 Answer 1


I suspect this problem is better solved in a different way. Just start multiplying out your conditions. You'll find a lovely recursive relationship $$ h_0=h_{in},\qquad h_k=-Mh_{k-1}=h_{k-1}-BA^{-1}h_{k-1}=(-1)^kM^kh_{in} $$ So, you don't actually need to calculate $A^{-1}$. Instead, you need to calculate the effect of $A^{-1}$ when it acts on a state, and you can use HHL for that.

How do you create the addition of terms? Let's imagine we have a state $|h_{k-1}\rangle$. Introduce an ancilla in the $|+\rangle$ state. Implement your action $BA^{-1}$ controlled off that ancilla, so you have $$ |0\rangle|h_{k-1}\rangle+|1\rangle(BA^{-1}|h_{k-1}\rangle). $$ Now apply a Hadamard to the ancilla $$ |0\rangle(|h_{k-1}\rangle+BA^{-1}|h_{k-1}\rangle)+|1\rangle|h_k\rangle. $$ So, if you measure the ancilla and find it in the $|1\rangle$ state, you're done. Although you could repeat until success, I imagine you'd gain more benefit from a strategy such as amplitude amplification. You could also experiment with deferring that step until you've recursively done the calculation on all $n$ vectors and only amplify the final term. This improves one of the multiplicative terms in the scaling from $2^n$ to $2^{n/2}$, but it certainly doesn't get you to an efficient solution.

I find it hard to believe that you can achieve anything better than classically calculating $M$ and hence $h_n$. Although that may depend upon what you want to do with the output.

  • $\begingroup$ I deleted my previous comment because I realized it was wrong. If we consider the case where $n=2$, then $h_2 = M^{2}h_{in} = ((BA^{-1})^2 - 2BA^{-1} + I)h_{in}$. My question is, is there a way to add these terms within the quantum routine that is also scalable with $k$? $\endgroup$ May 4, 2022 at 18:19
  • 1
    $\begingroup$ But you say that $A$ and $B$ are "known". So $M$ is known. Thus, why not implement $-M$ directly? (what is $k$?) $\endgroup$
    – DaftWullie
    May 5, 2022 at 5:50
  • $\begingroup$ $A$ and $B$ are known but not $A^{-1}$, which is required to calculate $M$. I would like to use HHL as a subroutine to calculate $A^{-1}$. I would then like to use $A^{-1}$ in your recursive equation, however, there is the obstacle of having a large number of terms for large $n$. The only way that I know of to add the terms would be to calculate them separately on a quantum computer, read them out, and then add them on a classical computer. This likely destroys any quantum advantage that I hope to gain. Is there a different way that you know of to add these terms? $k$ should have been $n$. $\endgroup$ May 5, 2022 at 23:33

Your Answer

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

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