5
$\begingroup$

I am studying how to speed-up the BFGS method using quantum computing techniques.

I have used a method of speeding up the gradient of the function, but it sacrifices the precision value of the gradient. More specifically, the gradient is calculated using $O(\sqrt{n} / \epsilon)$ function calls, where $n$ is the dimension. $\epsilon$ is a precision parameter that assures $ | \tilde \nabla f - \nabla f | < \epsilon$. So, if it is possible for the error to be strictly lower than $ \frac{1}{\sqrt{n}}$ (say $ \frac{1}{\sqrt[3]{n}}$) that would be perfect.

So, my question is, how precise does the gradient need to be in order for BFGS to work properly?

Edit: I have tried to do an analysis myself in the meantime and I have got an error for the k-th iteration supposing all the previous iterations are completely accurate. $$||B_k^{-1} (\tilde{\nabla f} - \nabla f)|| \le \frac{\epsilon}{\lambda_k} $$, where $B_k$ is the k-th approximation of the Hessian and $\lambda_k$ is the smallest eigenvalue of $B_k$.

The only question remains how he smallest eigenvalue of the approximation changes with the number of iterations.

$\endgroup$
  • $\begingroup$ How are you implementing quantum algorithms? Something like Q#? $\endgroup$ – Zach Favakeh Aug 21 at 15:43
  • $\begingroup$ Great question, in my opinion. In a way, that probably is asking for the conditioning of the BFGS. I would be also very interested to see what kind of ideas are there for this piece. $\endgroup$ – Anton Menshov Aug 21 at 16:08
  • $\begingroup$ I am not implementing the quantum algorithm on any language. I am just doing a theoretical analysis of its complexity. $\endgroup$ – Cezar98 Aug 22 at 14:30
  • 1
    $\begingroup$ might be relevant $\endgroup$ – Anton Menshov Aug 23 at 1:42
  • $\begingroup$ Thank you for the link. I have looked at that question, but unfortunately, it assumes no error to the process. But, I believe it shows that if the error is small enough, then convergence is assured. In the meantime, I have tried to get an upper bound of the error after one iteration. $\endgroup$ – Cezar98 Aug 23 at 13:14

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.