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).


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$.


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'<T-1$ 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.


1 Answer 1


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.

  • $\begingroup$ 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}$? $\endgroup$ Jun 27, 2019 at 19:11
  • $\begingroup$ Those U with an apparently large index are only relevant for t=2T to 3T, so all those actually do is undo the previous U_t so that by t=3T, you’re back to the start. $\endgroup$
    – DaftWullie
    Jun 27, 2019 at 19:16

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.