4
$\begingroup$

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.

$\endgroup$

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.