# Fastest way to solve Gram Schmidt orthogonalization in quantum computer

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?

• It is pretty efficient classically. (This also gives a bound.) Jun 14 '21 at 21:03
• Is there a specific reason why you think quantum computers could be faster than classical ones?
– fqq
Jun 14 '21 at 22:42
• Seeing Norbert's answer, I looked up its classical complexity. Link: stackoverflow.com/questions/27986225/… Jun 14 '21 at 23:55
• @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. Jun 15 '21 at 3:34
• 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). Jun 15 '21 at 7:04