#StackBounty: #complexity-theory #quantum-computing The relationship between matrix inversion, the HHL algorithm, and the unlikely scen…

Bounty: 50

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^2kappa^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.


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.