Why is the fastest quantum time complexity of unstructured search O(sqrt(n))?

Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers. Stack Overflow for Teams is now called Stack Internal. Bring the best of human thought and AI automation together at your work. Bring the best of human thought and AI automation together at your work. Learn more Stack InternalKnowledge at workBring the best of human thought and AI automation together at your work.Recently, I have watched video on 3Blue1Brown about Grover's algorithm. He give an example that:To find a secret number in the range from 0 to n−1, you can query a hidden function that returns “true” only for the correct number and “false” for all othersIn conclusion, i have some questions:Wikipedia cites the 1997 paper "Grover's quantum searching algorithm is optimal" by Zalka, for the proof of optimality. That paper says it's improving on the 1996 paper "Tight bounds on quantum searching" by Boyer et al.That's where I'd start if I wanted to understand the bound. If you've only seen a couple popularization videos then you may need to start by learning the basics of quantum computing, like how to calculate the effect of a gate on a state or what the mathematical definition of fidelity is, so that you can understand the explanations.Note there are quantum algorithms with much bigger speedups than Grover. For example, Shor's algorithm. Those other algorithms just don't apply to the unstructured search problem that Grover solves.Thanks for contributing an answer to Quantum Computing Stack Exchange!But avoid …Use MathJax to format equations. MathJax reference.To learn more, see our tips on writing great answers.Required, but never shown By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy. Start asking to get answersFind the answer to your question by asking.Explore related questionsSee similar questions with these tags.To subscribe to this RSS feed, copy and paste this URL into your RSS reader. Site design / logo © 2025 Stack Exchange Inc; user contributions licensed under CC BY-SA . rev 2025.11.24.37235