4
$\begingroup$

This is conserning the optimal dependency on condition number for Quantum linear system problem (QLSP).

For solving QLSP, the HHL (algorithm) paper mentions any polylog($\kappa$) quantum algorihm would imply $BPP=PSPACE$. This means polylog($\kappa$) quantum algorithm is extremely unlikely. See page-3; paragraph 2 on the right side; Link.

I went through an improved algorithm by Child-Kothari-Somma (CKS). Which mentions any sublinear algorithm in $\kappa$ is unlikely. OR, linear dependency on $\kappa$ is optimal. See page-4; last paragraph; link. It cites HHL paper as reference.

I find CKS's statemnet quite stronger. Because, $\kappa^{1/2}$ dependency is also sublinear, thus excluded.

My query is:

What is the best known lower bound on condition number?

How to make sense of $\Omega(\kappa)$ mentioned in CKS paper?

$\endgroup$

1 Answer 1

3
$\begingroup$

What is the best known lower bound on condition number?

Costa et. la.[1] use the discrete adiabatic theorem to develop a quantum algorithm for solving linear systems with complexity strictly linear in $\kappa$, matching the lower bound.

How to make sense of $\Omega(\kappa)$ mentioned in CKS paper?

CKS paper refers to HHL as the source of this fact. Actually, you can find it just after excluding the possibility of $\mathrm{polylog}(\kappa)$ quantum algorithm,

"Even improving our $\kappa$ dependence to $\kappa^{1 - \delta}$ for $\delta \gt 0$ would allow any time-$T$ quantum algorithm to be simulated in time $o(T)$; iterating this would again imply that $\mathrm{BQP}=\mathrm{PSPACE}$."

$\endgroup$

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.