Квантовый алгоритм для числа Бога

Божье число является худшим случаем Божьего алгоритма, который

понятие, возникающее в обсуждении способов решения головоломки кубика Рубика, но которое также может быть применено к другим комбинаторным головоломкам и математическим играм. Это относится к любому алгоритму, который дает решение, имеющее наименьшее количество возможных ходов, идея состоит в том, что всезнающее существо будет знать оптимальный шаг из любой данной конфигурации.

Для вычисления числа Бога, равного 20, потребовалось «35 CPU-лет простоя (классического) компьютерного времени».

Какое ускорение может быть достигнуто с помощью квантового подхода?

Мы можем думать о кубе кубика рубика граф Кэли $\Gamma=(V,E)$ с каждым (цветным) краем $E$ будучи одним из движений Singmaster $\langle U,U^{2},U^{3}=U^{-1},D,D^{2},D^{3},\cdots\rangle$ и каждая вершина $V$ будучи одним из $43252003274489856000\approx 4.3e{19}$ различные конфигурации $3\times 3\times 3$ кубики.

Диаметр графа самый длинный путь , короткий в графике. Классический алгоритм определения диаметра полиномиален по$\vert V \vert$; см., например, этот ответ с родственного сайта.

Как упомянуто выше, число Бога (связано с) этим диаметром; чтобы узнать самый длинный кратчайший путь между вершинами для графа Кэли на группе, достаточно знать, на сколько шагов от разрешенного состояния один. Мы знаем, благодаря Рокицки, Коциембе, Дэвидсону и Детриджу, что число Бога$20$, Алгоритмы, которые они выполняли, были полиномиальными в$\vert V\vert$например, полином в $4.3e{19}$,

Квантовый алгоритм Хайлигмана для диаметра графа, упомянутый в комментариях, обеспечивает ускорение по Гроверу по сравнению с алгоритмами Джикстры с «общей квантовой стоимостью $O(|V|^{9/4})$«Однако я считаю, что Хейлигман кодирует граф так же, как классический алгоритм; $O(|V|)$кубитов. Очевидно, что если$|V|=4.3e{19}$ тогда это не поможет.

Вместо этого, другой способ кодировать кубик Рубика, как намекалось в других вопросах, это, конечно, подготовить единую суперпозицию по всем$4.3e{19}$состояния. Это только занимает$\log 4.3e{19}$ кубитов.

Квантовые алгоритмы хорошо говорят о «собственных значениях», «собственных векторах» и «собственных состояниях». Применение всех движений Singmaster к единой суперпозиции всех$4.3e{19}$штат не меняет государство; т.е. равномерная суперпозиция является собственным состоянием цепи Маркова на графе Кэли.

Существуют зависимости между диаметром графа и собственными значениями / собственными векторами соответствующей матрицы смежности / лапласиана, особенно спектральной щелью, расстоянием между двумя самыми большими собственными значениями ($\lambda_1-\lambda_2$). Быстрый поиск в Google по «диаметру собственного значения» производит это ; Я рекомендую изучить подобные поиски Google.

Спектральные промежутки - это как раз то , что ограничивает адиабатический алгоритм . Таким образом, возможно, зная, как быстро должен работать адиабатический алгоритм, чтобы эволюционировать из однородного суперпозиции в решенное состояние для различных подгрупп / подпространств группы кубиков Рубика, можно оценить спектральный разрыв и использовать его для ограничения числа Бога. Но я быстро выхожу из своей лиги и сомневаюсь, что чувство точности достижимо.