Suppose we have $n$ (large) dimensional vector space and I want to orthogonalize $n$ linearly independent vectors using the Gram-Schmidt orthogonalization process. Is there some time-bound on how quickly a quantum computer can complete this process? Or is there any best known quantum algorithm for this?

  • 2
    $\begingroup$ It is pretty efficient classically. (This also gives a bound.) $\endgroup$ Jun 14 '21 at 21:03
  • 1
    $\begingroup$ Is there a specific reason why you think quantum computers could be faster than classical ones? $\endgroup$
    – fqq
    Jun 14 '21 at 22:42
  • $\begingroup$ Seeing Norbert's answer, I looked up its classical complexity. Link: stackoverflow.com/questions/27986225/… $\endgroup$ Jun 14 '21 at 23:55
  • 1
    $\begingroup$ @fqq I was thinking $n$ to be around $2^50$ or something, I don't have any knowledge on how fast classical computers can do this, but this is a pretty big dimension. So I thought maybe quantum computer can manage such large dimensions. $\endgroup$
    – IamKnull
    Jun 15 '21 at 3:34
  • 1
    $\begingroup$ The issue is that if you want exactly the Gram-Schmidt output, the output vectors are necessarily defined in a very linear way, one after the other. So it feels very unlikely that you could find something faster (obviously this is not a rigorous statement). $\endgroup$
    – DaftWullie
    Jun 15 '21 at 7:04

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.