Любой алгоритм квантовой сортировки, основанный на сравнении, потребует не менее Ω(п log п) шаги что уже достижимо классическими алгоритмами. Таким образом, для этой задачи квантовые компьютеры ничем не лучше классических.