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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.