# The relationship between matrix inversion, the HHL algorithm, and the unlikely scenario that $BQP = PSPACE$

I am studying the quantum computing algorithm presented in the paper Quantum algorithm for linear systems of equations}.

Without going through all the details, the HHL algorithm is able to apply an inverted matrix to a normalized vector prepared in a quantum state in time complexity $$\tilde{O}(\log(N)s^2\kappa^2/\epsilon)$$, i.e. in order to solve $$A |x \rangle = |b \rangle$$, it computes an estimate $$|x \rangle = A^{-1} | b \rangle$$ where

$$N$$ is the dimension of the matrix

$$s$$ i the sparsity of the matrix

$$\kappa$$ is the condition number of the matrix

$$\epsilon$$ is the desired error bound

In an argument for the optimality of the algorithm the authors construct a reduction from a general quantum circuit to a matrix inversion problem with a proof (page 4).

Now here is where I get confused, the authors write:

The reduction from a general quantum circuit to a matrix inversion problem also implies that our algorithm cannot be substantially improved (under standard assumptions). If the run-time could be made polylogarithmic in $$\kappa$$, then any problem solvable on $$n$$ qubits could be solved in poly(n) time (i.e. $$BQP=PSPACE$$), a highly unlikely possibility

Why does this imply that $$BQP = PSPACE$$? Any insights much appreciated.

Edit: later in the paper there is a bit more info that might help..

Recall that the $$TQBF$$ (totally quantified Boolean formula satisfiability) problem is $$PSPACE$$-complete, meaning that any k-bit problem instance for any language in $$PSPACE$$ can be reduced to a $$TQBF$$ problem of length $$n = poly(k)$$. The formula can be solved in time $$T ≤ 2^{2n}/18$$, by exhaustive enumeration over the variables.

I would be happy to provide any additional info that one feels is missing from this question.