Поиск квантовых прогулок

В контексте квантовых вычислений поиск квантового обхода — это квантовый алгоритм поиска отмеченного узла в графе. ^{[ 1 ]}

Концепция квантового блуждания вдохновлена классическими случайными блужданиями , в которых блуждающий случайным образом перемещается по графу или решетке . В классическом случайном блуждании положение пешехода можно описать с помощью распределения вероятностей по различным узлам графа. С другой стороны, в квантовом блуждании ходок представлен квантовым состоянием , которое может находиться в суперпозиции нескольких мест одновременно. ^{[ 1 ]}

Алгоритмы поиска, основанные на квантовых блужданиях, потенциально могут найти применение в различных областях, включая оптимизацию , машинное обучение , криптографию и сетевой анализ . ^{[ 2 ]} Эффективность и вероятность успеха поиска квантового блуждания сильно зависят от структуры пространства поиска . В общем, алгоритмы поиска квантового блуждания предлагают асимптотическое квадратичное ускорение, аналогичное ускорению алгоритма Гровера . ^{[ 3 ]}^{[ 4 ]}

Одна из первых работ по применению квантового блуждания к задачам поиска была предложена Нилом Шенви , Джулией Кемпе и К. Биргиттой Уэйли . ^{[ 5 ]}

Классическое описание проблемы

Учитывая пространство поиска $X$ и подмножество $M\subseteq X$ который содержит отмеченные элементы, алгоритм вероятностного поиска отбирает элемент $x\in X$ равномерно случайным образом на каждом шаге, пока не найдет отмеченный элемент из $M$ . Если мы определим $\epsilon =|M|/|N|$ как доля отмеченных элементов, подобную процедуру необходимо повторить $O(1/\epsilon )$ раз, чтобы найти отмеченный элемент. ^{[ 6 ]}

Если мы располагаем информацией о структуре $X$ мы можем смоделировать это как график $G(V,E)$ , где каждая вершина $V=\{v_{1},\dots ,v_{n}\}$ представляет выборку из пространства поиска с $|X|=n$ , а края представляют собой условную вероятность выборки следующего элемента, начиная с текущей выборки. ^{[ 6 ]}

Выполняем поиск, начиная со случайной вершины $v_{1}$ и, если оно не принадлежит $M$ , мы берем следующую вершину $v_{2}$ среди тех, кто связан с $v_{1}$ . Эта процедура известна как поиск случайного блуждания. Чтобы вероятность была близка к $1$ чтобы найти отмеченный узел, нужно асимптотически взять $O(1/\epsilon \delta )$ шагов на графике, где параметр $\delta$ - спектральная щель, связанная со стохастической матрицей $P$ графика. ^{[ 7 ]}

Чтобы оценить вычислительные затраты алгоритма случайного блуждания, обычно процедуру делят на три подэтапа, такие как настройка, проверка и обновление, и анализируют их стоимость. ^{[ 6 ]}

Настраивать

Стоимость установки $S$ относится к инициализации стационарного распределения по вершинам графа. ^{[ 6 ]}

Обновлять

Стоимость обновления $U$ — это стоимость моделирования перехода на графике в соответствии с вероятностью перехода, определенной в $P$ . ^{[ 6 ]}

Проверять

Стоимость чека $C$ — стоимость проверки принадлежности текущего элемента множеству $M$ . ^{[ 6 ]}

Общая стоимость алгоритма поиска случайным блужданием равна $S+{\frac {1}{\epsilon }}{\biggl (}{\frac {1}{\delta }}U+C{\biggr )}$ . Жадный вариант алгоритма, где проверка производится после каждого шага на графе , имеет сложность $S+{\frac {1}{\epsilon \delta }}{\biggl (}U+C{\biggr )}$ . Наличие члена спектральной щели $\delta$ в формулировке стоимости можно рассматривать как минимальное количество шагов, которое должен выполнить ходок, чтобы достичь стационарного распределения. Эта величина также известна как время смешивания . ^{[ 8 ]}

Описание алгоритма

Алгоритм поиска квантового блуждания был впервые предложен Магниесом и др., ^{[ 7 ]} также известен как алгоритм MNRS и основан на формулировке квантового блуждания, предложенной Марио Сегеди . Обход выполняется по направленным ребрам графа, поэтому для представления квантового состояния, связанного с пространством поиска, нам нужны два квантовых регистра. $|i\rangle |j\rangle$ , которые соответствуют ребру из $v_{i}$ к $v_{j}$ . Чтобы легко понять, как он работает, алгоритм можно объяснить через его геометрическую интерпретацию. Сначала мы определяем $|p_{i}\rangle =\sum _{j}{\sqrt {P_{ij}}}|j\rangle$ как равномерная суперпозиция над соседями $|i\rangle$ . Мы дополнительно определяем суперпозицию отмеченных и неотмеченных состояний, часто называемых хорошими и плохими состояниями, как

$|G\rangle ={\frac {1}{\sqrt {|M|}}}\sum _{i\in M}|i\rangle |p_{i}\rangle$ и $|B\rangle ={\frac {1}{\sqrt {X-|M|}}}\sum _{i\not \in M}|i\rangle |p_{i}\rangle$

где $M$ – множество отмеченных элементов. Равномерная суперпозиция по всем краям $U$ можно рассматривать как сочетание хороших и плохих состояний.

$|U\rangle ={\frac {1}{\sqrt {X}}}\sum _{i\in X}|i\rangle |p_{i}\rangle =\sin(\theta )|G\rangle +\cos(\theta )|B\rangle$ с $\theta =\arcsin({\sqrt {\epsilon }})$ . ^{[ 9 ]}

Алгоритм состоит из следующих шагов:

Инициализируйте квантовое состояние с помощью $|U\rangle$ Обычно это делается с помощью какой-либо процедуры подготовки состояния.
Повторите для $O(1/{\sqrt {\epsilon }})$ $O(1/{\sqrt {\epsilon }})$ :
- Выполните отражение через $|B\rangle$
- Выполните отражение через $|U\rangle$
Измерьте первый квантовый регистр и проверьте, отмечен ли он

Поскольку способ поиска отмеченного элемента алгоритмом основан на методе усиления амплитуды , ^{[ 10 ]} доказательство правильности аналогично доказательству алгоритма Гровера (который также можно рассматривать как частный случай квантового блуждания по полносвязному графу). Два отражения через $|U\rangle$ и $|B\rangle$ демонстрируют эффект перемещения квантового состояния в сторону хорошего состояния. После $k$ применения отражений состояние можно записать как $\sin((2k+1)\theta )|G\rangle +\cos((2k+1)\theta )|B\rangle$ и, установив $k\thickapprox {\frac {\pi }{4\theta }}=O(1/{\sqrt {\epsilon }})$ у нас есть это $\sin((2k+1)\theta )\thickapprox 1$ что с высокой вероятностью дает хорошее состояние. ^{[ 9 ]}

Первое размышление

Первое отражение проверяет, отмечена ли текущая вершина, и применяет фазовый сдвиг, равный $-1$ если это так. Это обычная процедура во многих квантовых алгоритмах, основанных на усилении амплитуды, и ее можно реализовать с помощью функции квантового оракула , проверяющей условие $|i\rangle \in M$ . ^{[ 9 ]}

Второе отражение

Второе отражение реализуется с помощью квантовой оценки фазы блуждания . с помощью оператора $W$ который должен отражать структуру исследуемого нами графа. Оператор обхода можно определить как $W=ref({\mathcal {B}})ref({\mathcal {A}})$ где $ref({\mathcal {B}})$ и $ref({\mathcal {A}})$ два отражения через подпространства ${\mathcal {A}}=span\{|i\rangle ,|p_{i}\rangle \}$ и ${\mathcal {B}}=span\{|p_{j}\rangle ,|j\rangle \}$ . ^{[ 9 ]} Поскольку собственные значения $W$ находятся в форме $e^{\pm 2i\theta }$ и оператор имеет единственное собственное значение, равное $1$ соответствующий $|U\rangle$ данный $\theta =0$ , мы можем выполнить оценку фазы с точностью $O(1/{\sqrt {\delta }})$ найти единственное собственное значение. Точность отражения зависит от количества кубитов, используемых для оценки фазы. ^{[ 9 ]}

Сложность

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

S: стоимость инициализации суперпозиции $|U\rangle$
U: стоимость выполнения шага на графике в суперпозиции, т.е. при отражении через $|U\rangle$
C: стоимость реализации квантового оракула, т.е. отражения через $|B\rangle$

Полная стоимость поиска квантового блуждания равна $S+{\frac {1}{\sqrt {\epsilon }}}{\biggl (}{\frac {1}{\sqrt {\delta }}}U+C{\biggr )}$ , что приводит к квадратичному ускорению по сравнению с классической версией. По сравнению с алгоритмом Гровера квантовые блуждания становятся выгодными при наличии больших структур данных, связанных с каждым квантовым состоянием, поскольку в первом случае они полностью перестраиваются на каждой итерации, тогда как при блужданиях они лишь частично обновляются на каждом шаге. ^{[ 11 ]}

Пример гиперкуба

Это пример того, как применить поиск квантового блуждания к графу гиперкуба . ^{[ 12 ]}

Хотя в исходном описании используются квантовые блуждания Сегеди, в этом примере мы показываем использование искусственного квантового блуждания, поскольку оно более интуитивно понятно. В любом случае обе формализации оказываются эквивалентными при конкретных предположениях. ^{[ 13 ]}

Пространство поиска – это $n$ -гиперкуб с $n=4$ , оно имеет $|V|=2^{4}$ вершин и имеет степень, равную $4$ . Каждый узел $v_{i}$ может быть помечено двоичной строкой $4$ биты и два узла соединены ребром, если их расстояние Хэмминга равно $1$ . Чтобы настроить поиск квантового блуждания, нам нужен регистр монет размерности ${\mathcal {H}}^{n}$ для кодирования всех возможных направлений, которые может выбрать ходок, и вершинного регистра измерения ${\mathcal {H}}^{2^{n}}$ для представления вершин. ^{[ 12 ]}

Вычислительная основа $|d\rangle |v\rangle$ с $\{d\in D=\{00,01,10,11\},v\in V=\{0000,0001,\dots ,1111\}\}$ .

Прогулку выполняют два оператора:

Монетный оператор $C$ используется для создания суперпозиции возможных направлений
Оператор смены $S$ используется для совершения шага на графике в одном направлении

Таким образом, оператор обхода $W=SC$ . ^{[ 12 ]}

В случае графа гиперкуба мы можем использовать тот факт, что двоичное кодирование вершин различается всего на один бит для любой пары соседних узлов, чтобы построить эффективный оператор сдвига. Оператор сдвига можно записать так:

$S=\sum _{d=1}^{n}\sum _{v=1}^{n}|d\rangle |v\oplus e_{d}\rangle \langle d|\langle v|$

где $e_{d}$ это $d$ -базис гиперкуба ( если $n=4$ основой являются $\{0001,0010,0100,1000\}$ ). Для монеты есть несколько вариантов, таких как монета Гровера или монета Фурье . Можно выбрать монету Гровера, которая будет иметь равную суперпозицию по всем направлениям. ^{[ 12 ]}

Алгоритм работает следующим образом:

Повторите для $O(1/{\sqrt {\epsilon }})$ $O(1/{\sqrt {\epsilon }})$
- Инициализируйте регистр счета для фазы суперпозиции.
- Выполните оценку фазы на $W$ с $O(1/{\sqrt {\delta }})$ точность
- Отметьте вспомогательный кубит, если предполагаемая фаза равна ${\tilde {\theta }}=0$
- Невычислить вспомогательную структуру данных
Измерьте регистр вершин

Оператор сдвига является ключевым фактором реализации эффективного квантового блуждания, в то время как для некоторых семейств графов, таких как тороиды и решетки, сдвиг известен, для нерегулярного графа разработка эффективного оператора сдвига все еще остается открытой задачей. . ^{[ 14 ]}

Приложения

Следующие приложения основаны на квантовом блуждании по графу Джонсона. $J(n,k)$ . ^{[ 15 ]}

Отличимость элемента

Дана функция $f$ определено на $\{n\}$ , он просит найти два разных элемента $i,j\in \{n\}$ такой, что $f(i)=f(j)$ если существует такая пара. ^{[ 16 ]}

Проверка продукта матрицы

Учитывая три $n\times n$ матрицы $A,B$ и $C$ , задача просит проверить, если $AB=C$ или иным образом найти индексы $i,j$ такой, что $(AB)_{i,j}\neq C_{i,j}$ . ^{[ 6 ]}

Треугольник

Треугольник — это полный подграф на трех вершинах , входящий в неориентированный граф. $G$ . Учитывая смежную матрицу графа, задача состоит в том, чтобы найти треугольник, если он есть. ^{[ 6 ]}

См. также

Ссылки

^ Перейти обратно: ^а ^б Португалия, Ренато, изд. (2013). Квантовые блуждания и алгоритмы поиска . Квантовая наука и технология. Нью-Йорк Гейдельберг: Спрингер. стр. 17–37. ISBN 978-1-4614-6335-1 .
^ Кадиан, Каруна; Гарвал, Сунита; Кумар, Аджай (01 августа 2021 г.). «Квантовое блуждание и области его применения: систематический обзор» . Обзор компьютерных наук . 41 : 100419. doi : 10.1016/j.cosrev.2021.100419 . ISSN 1574-0137 . S2CID 238207718 .
^ Гровер, Лов К. (1 июля 1996 г.). «Быстрый квантовомеханический алгоритм поиска в базе данных» . Материалы двадцать восьмого ежегодного симпозиума ACM по теории вычислений - STOC '96 . Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 212–219. дои : 10.1145/237814.237866 . ISBN 978-0-89791-785-8 . S2CID 207198067 .
^ Сантос, Ракелин AM (26 августа 2016 г.). «Квантовое блуждание Сегеди с запросами» . Квантовая обработка информации . 15 (11): 4461–4475. arXiv : 1603.05473 . Бибкод : 2016QuIP...15.4461S . дои : 10.1007/s11128-016-1427-4 . ISSN 1570-0755 . S2CID 254989663 .
^ Шенви, Нил; Кемпе, Джулия; Уэйли, К. Биргитта (23 мая 2003 г.). «Алгоритм квантового поиска случайным блужданием». Физический обзор А. 67 (5): 052307. arXiv : quant-ph/0210064 . Бибкод : 2003PhRvA..67e2307S . дои : 10.1103/PhysRevA.67.052307 . ISSN 1050-2947 . S2CID 8688989 .
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час Санта, Миклос (2008), Агравал, Маниндра; Ду, Динчжу; Дуань, Чжэньхуа; Ли, Ангшэн (ред.), «Алгоритмы поиска на основе квантового блуждания» , «Теория и приложения моделей вычислений» , Конспекты лекций по информатике, том. 4978, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 31–46, arXiv : 0808.0059 , doi : 10.1007/978-3-540-79228-4_3 , ISBN 978-3-540-79227-7 , S2CID 47163843 , получено 5 июля 2023 г.
^ Перейти обратно: ^а ^б Манье, Фредерик; Наяк, Эшвин; Роланд, Джереми; Санта, Миклош (11 июня 2007 г.). «Поиск с помощью квантовой прогулки» . Материалы тридцать девятого ежегодного симпозиума ACM по теории вычислений . СТОК '07. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 575–584. дои : 10.1145/1250790.1250874 . ISBN 978-1-59593-631-8 . S2CID 1918990 .
^ Левин, Дэвид Ашер; Перес, Юваль (2017). Цепи Маркова и времена смешивания . Элизабет Л. Уилмер, Джеймс Г. Пропп, Дэвид Брюс Уилсон, Американское математическое общество (второе изд.). Провиденс, Род-Айленд: Американское математическое общество. стр. 8–15. ISBN 978-1-4704-2962-1 .
^ Перейти обратно: ^а ^б ^с ^д ^и де Вольф, Рональд (2019). «Квантовые вычисления: конспект лекций». arXiv : 1907.09415 [ квант-ph ].
^ Брассар, Жиль; Хойер, Питер; Моска, Мишель; Тэпп, Ален (2002), «Квантовое усиление и оценка амплитуды», Квантовые вычисления и информация , Современная математика, том. 305, стр. 53–74, arXiv : quant-ph/0005055 , doi : 10.1090/conm/305/05215 , ISBN 9780821821404 , S2CID 54753
^ Жак, Самуэль (01 мая 2019 г.). Модели квантовой стоимости для криптоанализа изогений (магистерская диссертация). Университет Ватерлоо. стр. 67-68.
^ Перейти обратно: ^а ^б ^с ^д «Алгоритм квантового поиска» . Learn.qiskit.org . Проверено 5 июля 2023 г.
^ Вонг, Томас Г. (2017). «Эквивалентность квантовых блужданий Сегеди и придуманных им». Квантовая обработка информации . 16 (9): 215. arXiv : 1611.02238 . Бибкод : 2017QuIP...16..215W . дои : 10.1007/s11128-017-1667-y . ISSN 1570-0755 . S2CID 254985379 .
^ Дуглас, БЛ; Ван, JB (2007). «Эффективная реализация квантовых схем квантовых блужданий». arXiv : 0706.0304 [ квант-ph ].
^ Агонг, Луи Энтони; Амарра, Кармен; Кофман, Джон С.; Герман, Ари Дж.; Терада, Тайё С. (01 января 2018 г.). «Об обхвате и диаметре обобщенных графов Джонсона» . Дискретная математика . 341 (1): 138–142. arXiv : 2304.02864 . дои : 10.1016/j.disc.2017.08.022 . ISSN 0012-365X . S2CID 257985351 .
^ Амбайнис, Андрис (2007). «Алгоритм квантового блуждания для различения элементов» . SIAM Journal по вычислительной технике . 37 (1): 210–239. CiteSeerX 10.1.1.251.5460 . дои : 10.1137/S0097539705447311 . ISSN 0097-5397 .

Дальнейшее чтение

Нильсен, Майкл А.; Чуанг, Исаак Л. (2010). Квантовые вычисления и квантовая информация (изд. к 10-летию). Кембридж: Издательство Кембриджского университета. ISBN 978-1-107-00217-3 .
Лоулер, Грегори Ф.; Лимич, Влада (2010). Случайное блуждание: современное введение . Кембриджские исследования по высшей математике. Кембридж: Издательство Кембриджского университета. дои : 10.1017/cbo9780511750854 . ISBN 978-0-521-51918-2 .
Хидари, Джек Д. (2019). Квантовые вычисления: прикладной подход . Чам, Швейцария: Springer. ISBN 978-3-030-23921-3 .

Внешние ссылки

[:3-1] Перейти обратно: ^а ^б Португалия, Ренато, изд. (2013). Квантовые блуждания и алгоритмы поиска . Квантовая наука и технология. Нью-Йорк Гейдельберг: Спрингер. стр. 17–37. ISBN 978-1-4614-6335-1 .

[2] Кадиан, Каруна; Гарвал, Сунита; Кумар, Аджай (01 августа 2021 г.). «Квантовое блуждание и области его применения: систематический обзор» . Обзор компьютерных наук . 41 : 100419. doi : 10.1016/j.cosrev.2021.100419 . ISSN 1574-0137 . S2CID 238207718 .

[3] Гровер, Лов К. (1 июля 1996 г.). «Быстрый квантовомеханический алгоритм поиска в базе данных» . Материалы двадцать восьмого ежегодного симпозиума ACM по теории вычислений - STOC '96 . Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 212–219. дои : 10.1145/237814.237866 . ISBN 978-0-89791-785-8 . S2CID 207198067 .

[4] Сантос, Ракелин AM (26 августа 2016 г.). «Квантовое блуждание Сегеди с запросами» . Квантовая обработка информации . 15 (11): 4461–4475. arXiv : 1603.05473 . Бибкод : 2016QuIP...15.4461S . дои : 10.1007/s11128-016-1427-4 . ISSN 1570-0755 . S2CID 254989663 .

[5] Шенви, Нил; Кемпе, Джулия; Уэйли, К. Биргитта (23 мая 2003 г.). «Алгоритм квантового поиска случайным блужданием». Физический обзор А. 67 (5): 052307. arXiv : quant-ph/0210064 . Бибкод : 2003PhRvA..67e2307S . дои : 10.1103/PhysRevA.67.052307 . ISSN 1050-2947 . S2CID 8688989 .

[:0-6] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час Санта, Миклос (2008), Агравал, Маниндра; Ду, Динчжу; Дуань, Чжэньхуа; Ли, Ангшэн (ред.), «Алгоритмы поиска на основе квантового блуждания» , «Теория и приложения моделей вычислений» , Конспекты лекций по информатике, том. 4978, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 31–46, arXiv : 0808.0059 , doi : 10.1007/978-3-540-79228-4_3 , ISBN 978-3-540-79227-7 , S2CID 47163843 , получено 5 июля 2023 г.

[:1-7] Перейти обратно: ^а ^б Манье, Фредерик; Наяк, Эшвин; Роланд, Джереми; Санта, Миклош (11 июня 2007 г.). «Поиск с помощью квантовой прогулки» . Материалы тридцать девятого ежегодного симпозиума ACM по теории вычислений . СТОК '07. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 575–584. дои : 10.1145/1250790.1250874 . ISBN 978-1-59593-631-8 . S2CID 1918990 .

[8] Левин, Дэвид Ашер; Перес, Юваль (2017). Цепи Маркова и времена смешивания . Элизабет Л. Уилмер, Джеймс Г. Пропп, Дэвид Брюс Уилсон, Американское математическое общество (второе изд.). Провиденс, Род-Айленд: Американское математическое общество. стр. 8–15. ISBN 978-1-4704-2962-1 .

[:2-9] Перейти обратно: ^а ^б ^с ^д ^и де Вольф, Рональд (2019). «Квантовые вычисления: конспект лекций». arXiv : 1907.09415 [ квант-ph ].

[10] Брассар, Жиль; Хойер, Питер; Моска, Мишель; Тэпп, Ален (2002), «Квантовое усиление и оценка амплитуды», Квантовые вычисления и информация , Современная математика, том. 305, стр. 53–74, arXiv : quant-ph/0005055 , doi : 10.1090/conm/305/05215 , ISBN 9780821821404 , S2CID 54753

[11] Жак, Самуэль (01 мая 2019 г.). Модели квантовой стоимости для криптоанализа изогений (магистерская диссертация). Университет Ватерлоо. стр. 67-68.

[:4-12] Перейти обратно: ^а ^б ^с ^д «Алгоритм квантового поиска» . Learn.qiskit.org . Проверено 5 июля 2023 г.

[13] Вонг, Томас Г. (2017). «Эквивалентность квантовых блужданий Сегеди и придуманных им». Квантовая обработка информации . 16 (9): 215. arXiv : 1611.02238 . Бибкод : 2017QuIP...16..215W . дои : 10.1007/s11128-017-1667-y . ISSN 1570-0755 . S2CID 254985379 .

[14] Дуглас, БЛ; Ван, JB (2007). «Эффективная реализация квантовых схем квантовых блужданий». arXiv : 0706.0304 [ квант-ph ].

[15] Агонг, Луи Энтони; Амарра, Кармен; Кофман, Джон С.; Герман, Ари Дж.; Терада, Тайё С. (01 января 2018 г.). «Об обхвате и диаметре обобщенных графов Джонсона» . Дискретная математика . 341 (1): 138–142. arXiv : 2304.02864 . дои : 10.1016/j.disc.2017.08.022 . ISSN 0012-365X . S2CID 257985351 .

[16] Амбайнис, Андрис (2007). «Алгоритм квантового блуждания для различения элементов» . SIAM Journal по вычислительной технике . 37 (1): 210–239. CiteSeerX 10.1.1.251.5460 . дои : 10.1137/S0097539705447311 . ISSN 0097-5397 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]