Недавно я прочитал о «квантовом богосорте» в некоторых вики. Основная идея заключается в том, что, подобно bogosort, мы просто перетасовываем наш массив и надеемся, что он отсортирован «случайно», и повторяем попытку при сбое.

Разница в том, что теперь у нас есть « магический квант», поэтому мы можем просто попробовать все перестановки одновременно в «параллельных вселенных» и «уничтожить все плохие вселенные», где сортировка плохая.

Теперь, очевидно, это не работает. Квант - это физика, а не магия. Основные проблемы

1. «Параллельные вселенные» - это просто интерпретация квантовых эффектов, а не то, что использует квантовые вычисления. Я имею в виду, что мы могли бы использовать здесь жесткие числа, интерпретация только запутает вопросы здесь, я думаю.

2. «Уничтожение всех плохих вселенных» немного похоже на исправление ошибок кубитов, очень сложная проблема в квантовых вычислениях.

3. Бого рода остается глупым. Если мы можем ускорить сортировку с помощью кванта, почему бы не использовать хороший алгоритм сортировки ? (Но нам нужна случайность, протестует мой сосед! Да, но разве вы не можете придумать лучший классический алгоритм, основанный на случайности ?)

Хотя этот алгоритм по большей части является шуткой, он может быть «образовательной шуткой», подобно «классическому» богосорту, поскольку разница между наилучшим, наихудшим и средним сложностями для рандомизированных алгоритмов здесь проста и очень понятна. (для записи, лучший случай$\Theta(n)$Нам очень повезло, но мы все равно должны проверить, что наш ответ правильный, сканируя массив, ожидаемое время просто ужасно (IIRC, пропорционально количеству перестановок, поэтому ) и в худшем случае мы никогда не закончим)$O(n!)$

Итак, что мы можем узнать из «квантового богосорта»? В частности, существуют ли реальные квантовые алгоритмы, которые похожи, или это теоретическая или практическая невозможность? Кроме того, проводилось ли исследование «алгоритмов квантовой сортировки»? Если нет, то почему?

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: квантовый богосорт является алгоритмом шутки

Позвольте мне вкратце изложить алгоритм:

• Шаг 1: Используя алгоритм квантовой рандомизации, рандомизируйте список / массив так, чтобы не было возможности узнать, в каком порядке находится список, пока он не будет наблюдаться. Это разделит вселенную на$O(N!)$вселенные; однако, разделение не имеет никакой стоимости, поскольку это происходит постоянно в любом случае.

• Шаг 2: Проверьте, отсортирован ли список. Если нет, уничтожьте вселенную (пренебрегая реальной физической возможностью).

Теперь все оставшиеся юниверсы содержат списки / массивы, которые отсортированы.

В худшем случае сложность :$O(N)$

(мы рассматриваем только те вселенные, которые могут наблюдать, что список отсортирован)

Сложность среднего / лучшего случая :$O(1)$

Одна из основных проблем этого алгоритма - это огромная вероятность увеличения количества ошибок, о которых Ник Джонсон упоминает здесь :

Однако этот алгоритм имеет гораздо большую проблему. Предположим, что один из 10 миллиардов раз вы ошибочно заключите, что список отсортирован, а если нет. Есть 20! способы сортировки списка из 20 элементов. После сортировки оставшимися юниверсами будет та, в которой список был отсортирован правильно, и 2,4 миллиона юниверсов, в которых алгоритм ошибочно завершил список, были отсортированы правильно. Итак, у вас есть алгоритм для массового увеличения частоты ошибок на части оборудования.

«Параллельные вселенные» - это очень упрощенная интерпретация квантовых эффектов , а не то, что использует квантовые вычисления.

Не совсем уверен, что вы подразумеваете под «сильно упрощенной интерпретацией квантовых эффектов». Источники ( это и это ), которые я нашел в интернете относительно квантовой богосорты , прямо не упоминают, что они используют альтернативную интерпретацию QM, то есть интерпретацию Эверетта, о которой вы, возможно, думаете. На самом деле я даже не уверен, как склеить интерпретацию Эверетта и квантовый богосорт (используя пост-отбор, как прокомментировали некоторые люди). В любом случае, просто как примечание: в основной космологии широко распространено мнение, что существует более одной вселенной, и для них даже есть классификации, называемые четырьмя уровнями Макса Тегмарка и Брайана Грина.Циклические теории . Прочитайте статью Wiki на Multiverse для более подробной информации.

«Уничтожение всех плохих вселенных» напоминает исправление ошибок кубитов, очень сложная проблема в квантовых вычислениях.

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

Бого-род остается глупым. Если мы можем ускорить сортировку с помощью кванта, почему бы не использовать хороший алгоритм сортировки? (Но нам нужна случайность, протестует мой сосед! Да, но разве вы не можете придумать лучший классический алгоритм, основанный на случайности?)

Да, это действительно глупо . Похоже, это началось как "образовательная шутка", как вы сказали. Я пытался найти источник такого рода или соответствующие научные статьи, но не смог найти ни одного. Тем не менее, даже классический bogosort глуп в том смысле, что его считают одним из самых неэффективных алгоритмов сортировки. Тем не менее, это было исследовано, исключительно из образовательного интереса.

В частности, существуют ли реальные квантовые алгоритмы, которые похожи, или это теоретическая или практическая невозможность?

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

Кроме того, проводилось ли исследование «алгоритмов квантовой сортировки»? Если нет, то почему?

Там действительно было исследование "квантовой сортировки". Но проблема с такими алгоритмами сортировки заключается в том, что любой алгоритм квантовой сортировки, основанный на сравнении, может занять как минимум$\Omega (N\log N)$шаги, которые уже достижимы классическими алгоритмами. Таким образом, для этой задачи квантовые компьютеры не лучше классических. Однако в ограниченных в пространстве видах квантовые алгоритмы превосходят свои классические аналоги. Это и это две соответствующие статьи.