# Is it possible to compute a matrix inverse for an arbitrary matrix within a subroutine?

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?

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.
• 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$? May 4, 2022 at 18:19
• But you say that $A$ and $B$ are "known". So $M$ is known. Thus, why not implement $-M$ directly? (what is $k$?) May 5, 2022 at 5:50
• $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$. May 5, 2022 at 23:33