Каково современное состояние в алгоритмах квантовой сортировки?

В результате превосходного ответа на мой вопрос о квантовой bogosort мне стало интересно, каково современное состояние квантовых алгоритмов сортировки.

Чтобы быть точным, сортировка здесь определяется как следующая проблема:

Учитывая массив $A$ целых чисел (не стесняйтесь выбирать ваше представление $A$ , но будьте осторожны с этим, я думаю, что это уже нетривиально!) Размера $n$ , мы хотим преобразовать этот массив в массив $A_s$ так, чтобы массивы 'являются перестановками друг друга, и $A_s$ сортируется, т.е. $A_s[i]\leq A_s[j]$ для всех $i\leq j$ .

Что известно об этом? Есть ли границы сложности или гипотезы для определенных моделей? Существуют ли практические алгоритмы? Можно ли бить классическую сортировку (даже ведро или десятичную рода в их собственной игре ? (Т.е. в тех случаях , когда они работают хорошо?))

$\Omega(N\log N)$$\Omega(\log N)$

Есть более новый результат от Роберта Билса, Стивена Бриерли, Оливера Грея, Арама Харроу, Сэмюэля Кутина, Ноа Линдена, Дана Шепарда, Марка Стэтера. Они представлены в Таблице 2 Эффективного Распределенного Кванта. Вычисляя результаты для пузырьковой сортировки и вставки, это в основном для «сетевой сортировки», но они дали больше ссылок на сортировку.

Краткое и очень краткое описание статьи может быть таким: Мы можем сказать, что статья показывает, как решить несколько проблем, таких как доступ к квантовой памяти без потери суперпозиции (и они дают стоимость для нее). Также в статье представлена ​​проблема сортировки сети, делающей это квантово (одна из проблем - обратимость операций). Мне нравится статья, потому что она поднимает несколько проблем, и авторы дали решение некоторых проблем. Я думаю, что это трудно попытаться подвести итог, я действительно рекомендую прочитать.

Я надеюсь, что я помог.