Quantum lower bound for sorting
Shi, Yaoyun
Original · EN
We prove that Ω(n log(n)) comparisons are necessary for any quantum algorithm that sorts n numbers with high success probability and uses only comparisons. If no error is allowed, at least 0.110nlog₂(n) - 0.067n + O(1) comparisons must be made. The previous known lower bound is Ω(n).
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.