Может ли квантовый компьютер легко определить время смешивания группы кубиков Рубика?

Чиновники в кубических турнирах Рубика использовали два разных способа борьбы с кубом. В настоящее время они ломаются куб друг от друга и снова собрать cubies в случайном порядке из куба группы Рубика . Ранее они применяли случайную последовательность ходов Singmaster .G г ⟨ U , D , F , B , L , R $\pi\in G$$G$$g$$\langle U,D, F, B, L, R\rangle$

Однако длина слова - количество случайных ходов, необходимых для полного скремблирования куба, так что каждая из перестановок примерно одинаково вероятна - в настоящее время неизвестна, но должна быть по меньшей мере , 20 . Эту длину t можно назвать временем перемешивания случайного блуждания на графе Кэли группы кубиков Рубика, порожденной движениями Сингмастера \ langle U, D, F, B, L, R \ rangle .$t$$g$$\Vert G\Vert=43,252,003,274,489,856,000$ $20$$t$$\langle U,D, F, B, L, R\rangle$

Будет ли квантовый компьютер иметь какие-либо преимущества для определения времени перемешивания $t$ группы кубиков Рубика?

Я думаю, что у нас может быть какая-то умная последовательность действий Адамара, чтобы создать регистр $\vert A \rangle$ как равномерную суперпозицию для всех $\Vert G\Vert$ таких конфигураций; таким образом, применение любой последовательности ходов Singmaster к $\vert A \rangle$ не меняет $\vert A \rangle$ .

Если у нас есть предположение относительно времени смешивания , мы также можем создать еще один регистр в качестве равномерной суперпозиции всех слов Singmaster длины и условно применить каждое такое слово к разрешенному состоянию. , мы надеемся получить состояние таким образом, чтобы при измерении каждая из конфигураций с равной вероятностью была измерена. Если , то мы не будем ходить по графу Кэли группы достаточно долго, и если мы будем измерять$t'$$t$$\vert B \rangle$$t'$$\vert A'\rangle$$\vert B\rangle \vert A\rangle$$\vert A \rangle$$\Vert G \Vert$$t'\lt t$$G$$\vert A \rangle$конфигурации, которые «ближе» к разрешенному состоянию, были бы более вероятными. Некоторые умные фурье-подобные преобразования в могут измерить, насколько равномерно распределен .$\vert B \rangle$$\vert A \rangle$

Мне кажется, что квантовый компьютер хорош в этом. Например, если не был равномерно смешан всеми словами в , то некоторые конфигурации более вероятны, чем другие, например, является более "постоянным"; тогда как , если была полностью смешаны все из прогулок, а затем более «сбалансированный». Но мое предположение о квантовых алгоритмах и цепях Маркова недостаточно сильное, чтобы продвинуться далеко вперед.$\vert A \rangle$$\vert B\rangle$$\vert A \rangle$$\vert A \rangle$ $\vert A \rangle$

РЕДАКТИРОВАТЬ

Сравните этот вопрос с проблемой проверки квантового узла.

При проверке квантового узла торговцу дается квантовая монета как состояние всех узлов, которые имеют определенный инвариант. Чтобы проверить квантовую монету, она применяет марковскую цепочку для перехода к себе (если это действительная монета.) Она должна применить эту марковскую цепочку и измерить результат не менее раз, но в противном случае она имеет нет способа построить самостоятельно (чтобы она не могла подделать монету). Поэтому, если ей дали действительную монету, ей дали состояние, которое она не могла произвести самостоятельно , вместе с цепью Маркова как матрица , и она предположительно знает время перемешивания$\vert K \rangle$$M$$\vert K \rangle$$t$$\vert K \rangle$$M$$t$; она должна проверить, что является действительным.$\vert K \rangle$

В данном вопросе, вероятно, довольно просто сгенерировать всех перестановок кубиков Рубика. Квантовый контур, соответствующий цепочке Маркова, называемой , движений Singmaster, также, вероятно, довольно легко построить. Однако время перемешивания неизвестно, и это единственное, что нужно определить.$\vert RC \rangle$$S$$t$

Это интересный вопрос, который лучше, чем большинство "есть ли квантовый алгоритм для х?" вопросов. Я не знаю существующего квантового алгоритма. Позвольте мне описать то, что я считаю типичной первой попыткой, и почему это не удается. В конце я опишу пару вещей, которые могут привести к некоторым улучшениям.

Первая попытка по алгоритму

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

Тогда я собираюсь сделать регистры Ancilla, к . Каждый из них имеет тот же размер, что и количество возможных ходов Singmaster, и готовится как единая суперпозиция для всех возможных базовых элементов. Затем для каждого мы применяем управляемый унитар из к где регистр указывает, какое движение Singmaster применяется к .$t$$A_1$$A_t$$i=1,\ldots t$$A_i$$RC$$A_i$$RC$

После всего этого, если мы просто посмотрим на , он должен быть в максимально смешанном состоянии, если микширование произошло так, как хотелось бы. Проблема в том, как проверить, является ли этот вывод максимально смешанным состоянием. Есть полезные методы, такие как этот , но какой точности мы требуем (то есть, сколько повторений?). Думаю, нам понадобится около .$RC$$|A|^t$

На самом деле, такой способ работы так же плох, как и классический: вы можете заменить начальное состояние каждого из на и это не изменит результат , Но на самом деле это все равно, что делать случайный выбор каждый раз и многократно запускать проверку правильности распределения выходных данных.$A_i$$\mathbb{I}/2^{|A_i|}$

Возможные улучшения

• Работая, как я описал, матрица выходной плотности (на ) должна быть диагональной. Это означает, что равномерное наложение по всем базисным состояниям является собственным состоянием тогда и только тогда, когда система максимально перемешана. Я хотел бы объединить это наблюдение с некоторым усилением амплитуды, чтобы получить небольшое ускорение. Обратите внимание, что очень быстро создает разницу от если состояние не является собственным вектором.$\rho$$RC$$|u\rangle$$\rho^k|u\rangle$$|u\rangle$

• Кроме того, вам, вероятно, нужно сделать что-то более умное с вспомогательными регистрами. Есть некоторая надежда, что это возможно, потому что в кубик Рубика встроено много групповой структуры. Одна вещь , которую вы можете попробовать, чтобы увидеть , можно ли заменить все регистры Ancilla с одного регистра, применяются Hadmard ворота на каждом кубита регистра между каждым раундом контролируемым унитарным. Возможно, все, что это делает, - это экономия эффективности с точки зрения количества кубитов по сравнению с моим первоначальным предложением. Это может даже не сделать этого.$t$

Работает ли кто-то из них напрямую, я не знаю. Тем не менее, я думаю, что ключевые принципы состоят в том, чтобы найти некоторую полезную групповую структуру и найти способ применения амплитудного усиления.

Вы могли бы найти полезным прочитать об унитарных проектах . Это, безусловно, отличная проблема от того, о чем мы говорим здесь, но некоторые технические инструменты могут быть полезны. Грубо говоря, идея состоит в том, что набор унитарных является дизайном, если случайное применение этих унитарных единиц позволяет имитировать действительно случайный унитарный (взятый из меры Хаара) выходных функций которые при расширении с использованием ряд Тейлора, с точностью до степени . Примерная связь здесь является то , что если взять унитарные , представляющую последовательность Singmaster двигается как , было бы достаточно , если этот набор был 2-дизайном (если вы получаете$\{U\}$$t$$f$$t$$t$$\{U\}$$\text{Tr}(\rho^2)$ правильно, все готово).

(CW, чтобы избежать повторений от самостоятельного ответа)

Для двух сторон может существовать интерактивный способ сузить значение , следуя ответу @ DaftWullie и комментариям @Steven Sagona. Мой формализм беден, но я надеюсь, что идея проходит через ...$t$

Например, назовите обе стороны Алисой и Бобом. Стороны должны сотрудничать и вести себя честно согласно протоколу.

Алиса знает, как подготовить два состояния: и . Здесь - это равномерная суперпозиция для всех комбинаций кубиков Рубика, а - это другое состояние обезьяны с таким же количеством кубитов (например, состояние, соответствующее решенному кубику Рубика, или равномерная суперпозиция над большой подгруппой группы ). Боб знает, как применить матрицу к квантовому состоянию, где соответствует единственному шагу всех ходов Singmaster (с необходимыми вспомогательными элементами).| 1 ⟩ | 0 ⟩ | 1 ⟩ О М $\vert A_0 \rangle$$\vert A_1 \rangle$$\vert A_0\rangle$$\vert A_1\rangle$$G$$M$$M$

Алиса и Боб хотят показать, что время смешивания группы кубиков Рубика при ходах Singmaster не больше . Алиса и Боб повторяют следующие раз.р $t$$r$$s$

1. Алиса подбрасывает монету и предоставляет Бобу| Я$i\in\{0,1\}$$\vert A_i \rangle$
2. Боб повторяет раз, чтобы применить к , и каждый раз измеряет проектор.м | Я$r$$M$$\vert A_i \rangle$
3. Если проектор для каждого из итераций, то Боб говорит , что . Если проектор не , по крайней мере , одной из итераций, то Боб говорит , что Алиса это .r i = 0 1 r i = $1$$r$$i=0$$1$$r$$i=1$

Если , то каждый из Боба итераций на шаге 2 не изменяется - потому что по определению является собственным матрицы Боба, и матрица Боба просто переставляет состояния между собой. Если , то состояние обезьяны является не является собственным проектором Боба, и вероятность того, что не будет измеряться быстро растет с . $i=0$$r$$\vert A_0\rangle$$\vert A_0 \rangle$$i=1$$\vert A_1 \rangle$$1$$r$

Таким образом, если Боб точно предсказал для итераций, вероятность успеха растет экспоненциально с , а Боба достаточно велика, чтобы отличить правильное состояние кубика Рубика от состояния обезьяны.$i$$s$$s$$r$

Я не знаю, как далеко должен быть от . Я также не знаю, можно ли удалить взаимодействие.$\vert A_1\rangle$$\vert A_0\rangle$

Изначально давайте рассмотрим некоторые регистры и операторы.

1. Регистр , который кодирует суперпозиции состояний куба (например, перестановка куба );$\vert A\rangle$$G$
2. Оператор , который действует на для отображения всех 0 0 ket на равномерную суперпозицию по всем состояниям ;$U$$\vert A\rangle$$\vert 00\cdots 0\rangle$$\Vert G\Vert$
3. Регистр , который кодирует суперпозиции набора ходов Singmaster, которые должны быть применены к данной позиции (например, суперпозиции слов Singmaster ходы длины );$\vert B\rangle=\vert b_1\rangle\vert b_2\rangle\cdots\vert b_k\rangle$$k$
4. Операторы и , которые действуют на для отображения всех 0 0 ket на равномерную суперпозицию всех слов сингмастерских ходов длины (и наоборот); и$V$$V^{-1}$$\vert B\rangle$$\vert 00\cdots 0\rangle$$18^k$$k$
5. (Управляемый) оператор , который применяет Singmaster-перемещение к заданной позиции куба.$W$$b$

Если находится в равномерной суперпозиции по всем элементам , то находится в собственном состоянии , и повторные применения не будут отброшены назад, чтобы повлиять на .$\vert A\rangle$$G$$\vert A\rangle$$W$$W$$\vert B\rangle$

То есть должен возвращать в вышеупомянутой схеме к нулям ket .$V^{-1}$$\vert B\rangle$$\vert 00\cdots 0\rangle$

Однако , как отмечает @DaftWullie, если не находится в собственном государстве, то разница между и нарастает очень быстро - я считаю, скорость, с которой Нарастание этой разницы зависит именно от свойств смешения интересующего оператора.$\vert u\rangle$| у ⟩ р к | у ⟩$\vert u \rangle$$\rho^k \vert u\rangle$

Таким образом, если мы сможем подготовить состояние , которое возмущено из равномерного распределения, так что не является собственным состоянием, то повторные применения быстро создадут разницу, и не может быть нулевым кетом.$\vert A\rangle$| ⟩ Вт V - 1 | B ⟩$\vert A\rangle$$W$ $V^{-1}\vert B\rangle$

Если бы у нас была функция действующая на и ответный кубит который определяет, скажем, некоторый хэш позиция кубика Рубика меньше некоторого порога , и мы используем этот для управления вращением , тогда я считаю, что в приведенная выше схема не будет читать кет со всеми нулями, и вместо этого, скорее всего, будет отклоняться от кета со всеми нулями в зависимости только от и времени смешивания группы кубиков Рубика с набором генерации Singmaster.$F$$\vert A\rangle$$\vert C\rangle$$\{0,1\}^{\log_2 \Vert G\Vert}\mapsto (0,1)$$\delta$$F$$\vert A\rangle$V - 1 | B ⟩ δ$V^{-1}\vert B\rangle$$\delta$

То есть, я ожидаю, что измерение в приведенной выше схеме будет читать или что-то подобное, где индекс первого зависит исключительно от времени смешивания и порога .$\vert B\rangle$$\vert 00000\cdots000101101\rangle$1 δ$1$$\delta$