4
$\begingroup$

I am researching how to speedup optimization problems using quantum algorithms. Many such algoritms use the Euclidean norm of a vector. Hence, I tried to find a quantum algorithm that speedups the calculation of the Euclidean Norm, but with no success.

Are you aware of any quantum algorithms for calculating the norm of the vector? If so, can you please provide a reference (Scientific paper, book) for that algorithm?

Thank you in advance!

Improve this question
$\endgroup$
2
  • $\begingroup$ Could you be more specific about the type of optimization problem for example QAOA. If we have details about the algorithm more can be said about quantum speedup if any. $\endgroup$
    – Bram
    Aug 17, 2019 at 17:59
  • $\begingroup$ Basically, I am looking at BFGS. I am trying to optimize the multiplication $ A \mathbf{x} $, where A is a symmetric and positive definite matrix and x is a vector. Classically, this takes $O(n^2)$. There is a paper by C. Shao (arXiv preprint arXiv:1803.01601 , 2018) that talks about optimizing matrix multiplication in a quantum computer. I almost succeeded in optimizing this, but there is still a pesky $n^2$ coming from computing the norm of the rows of $A$. This is where I need to optimize the 2-norm. $\endgroup$
    – Cezar98
    Aug 19, 2019 at 12:13

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.