Conference material: "Academician O.B. Lupanov XIV International Scientific Seminar "Discrete Mathematics and Its Applications" (20-25 June 2022, Moscow)"
Authors:Ziyatdinov M.T.
Lower bound of quantum request complexity of radix sort
Abstract:
In the classical case, sorting N elements requires O(N log N) pairwise comparisons. So many comparisons required and in the quantum case. But for radix sort use quantum computing allows you to gain an advantage over classical: instead of O(NL) operations to sort N elements from L symbols in the quantum case requires O(N sqrt{L / log N}) operations, which coincides with the well-known upper bound with up to logarithmic factors.
