# Showing that Matrix Inversion is BQP-complete - HHL Algorithm

I am trying to understand an argument that Matrix Inversion is BQP-complete for certain conditions on the matrix. This is explained here on page 39 (this paper is a primer to the HHL algorithm and gives some more detailed calculations, more detail about assumptions for people new to the subject).

Definition:

An algorithm solves matrix inversion if it has:

Input: An $$O(1)$$-sparse matrix hermitian $$A$$ of dimension $$N$$ specified using an oracle or via a $$\mathrm{poly}(\log N)$$-time algorithm that returns the non-zero elements of a row. The singular values of $$A$$ lie between $$\frac{1} {\kappa}$$ and 1, where $$\kappa$$ is the ration between the largest eigenvalue and the smallest eigenvalue of $$A$$.

Output:

A bit that equals one with probability $$\langle x | M |x \rangle \pm \epsilon$$ where $$M = |0 \rangle \langle 0 | \otimes I^{N/2}$$ corresponds to measuring the first qubit and $$|x \rangle$$ is a normalised state proportional to $$A^{-1} |b \rangle$$ for $$|b \rangle = |0 \rangle$$.

Let $$C$$ be a quantum circuit acting on $$n = logN$$ qubits which applies $$T$$ two-qubit gates $$U_1, \cdots U_T$$. The initial state is given by $$|0 \rangle^{\otimes n}$$, and the answer will be determined by measuring the first qubit of the final state. Adjoin an ancilla register of dimension $$3T$$ and define a unitary operation: $$U = \sum_{t-1}^{T}|t+1 \rangle \langle t| \otimes U_t + |t+T+1 \rangle \langle t+T| \otimes I$$$$+ |t+2T+1 \bmod 3T \rangle\langle t+2T| \otimes U^{\dagger}_{3T+1-t}.$$

The author then writes: "This operator has been chosen such that for $$T+1 \leq t \leq 2T$$, applying $$U^t$$ to the state $$|1 \rangle |\psi \rangle$$ yields the output state $$|t+1 \rangle \otimes U_t \cdots U_1 |\psi \rangle$$. We can see this as the first $$T+1$$ applications of $$U$$ return $$|T+2 \rangle \otimes U_T \cdots U_1 |\psi \rangle$$ . We see from the second term of the definition for $$U$$ that for the next $$t' applications, the action on the $$|\psi \rangle$$ register remains unchanged, while the ancillary variable is merely being incremented."

This last statement is quite a mouthful as the expression is very complicated. I am having difficulty seeing why this is true and any insights would be much appreciated.

Define the states $$|\psi_t\rangle=\left\{\begin{array}{cc} |t\rangle\otimes(U_{t-1}U_{t-2}\ldots U_1|\psi\rangle) & t=1,2,\ldots T \\ |t\rangle\otimes(U_{T}U_{T-1}\ldots U_1|\psi\rangle) & t=T+1,T+2,\ldots 2T \\ |t\rangle\otimes(U_{3T+1-t}U_{3T-t}\ldots U_1|\psi\rangle) & t=2T+1,2T+2,\ldots 3T \end{array}\right.$$ Now let $$U=\frac{2}{T}\sum_{t=1}^{T}|t+1\rangle\langle t|\otimes U_t+|t+T+1\rangle\langle t+T|\otimes I+|t+2T+1\text{ mod }3T\rangle\langle t + 2T|\otimes U^\dagger_{3T+1-t}.$$ You can verify that $$U|\psi_t\rangle=|\psi_{t+1}\rangle$$ for $$t=1,2,\ldots 3T-1$$ and $$U|\psi_{3T}\rangle=|\psi_1\rangle.$$ So, basically, $$U$$ acts as a cyclic permutation through the states $$\{|\psi_t\rangle\}$$. Act $$U$$ $$k$$ times, (i.e. apply $$U^k$$) and you go from any $$|\psi_t\rangle$$ to $$|\psi_{t+k}\rangle$$.
Now, if you start in $$|\psi_1\rangle$$ and enact any $$U^k$$ for $$k=T,T+1,\ldots 2T-1$$, you get an outcome for which the second register is the same, $$U_{T}U_{T-1}\ldots U_1|\psi\rangle.$$ This idea is hence that the $$U_1$$, $$U_2$$ etc can be thought of as the individual unitaries of an arbitrary quantum computation of $$T$$ steps, and that this state is the overall output of the computation.
The paper then goes on to talk about implementing $$A=I-Ue^{-1/T},$$ and it's $$A^{-1}$$ you're trying to calculate. Using a Taylor expansion, this would be $$A^{-1}=\sum_tU^te^{-t/T}$$ So, this includes $$t=T$$ to $$2T-1$$ with high (enough) probability, meaning that the act of the inversion effectively gives us the outcome of a quantum computation. If it can calculate the act of any quantum computer, the computation is at least as hard as the hardest thing a quantum computer can calculate, so the computation is BQP-hard. Since it can be completed on a quantum computer, the calculation is in BQP, and hence the overall classification is BQP-complete.
• One thing that is confusing me is that there are $T$ gates being acted on, but in the definition of $U$ there is reference to $U^{\dagger}_{3T+1-t}$, but if $t=1$, it seems now there is some gate $U_{3T}$? – IntegrateThis Jun 27 '19 at 19:11