Материал конференции: "XIV международный научный семинар "Дискретная математика и ее приложения" имени академика О.Б. Лупанова (20-25 июня 2022 г., Москва)"
Авторы:Зиятдинов М.Т.
Нижняя оценка квантовой запросной сложности поразрядной сортировки
Аннотация:
В классическом случае для сортировки N элементов требуется O(N log N) попарных сравнений. Столько же сравнений требуется и в квантовом случае. Но для поразрядной сортировки использование квантовых вычислений позволяет добиться преимущества над классическими: вместо O(NL) операций для сортировки N элементов из L символов в квантовом случае требуется O(N sqrt{L / log N}) операций, что совпадает с известной верхней оценкой с точностью до логарифмических множителей.
