Алгоритм квантового счета - Quantum counting algorithm

Алгоритм квантового счета это квантовый алгоритм для эффективного подсчета количества решений для заданной поисковой задачи. Алгоритм основан на алгоритм квантовой оценки фазы и дальше Алгоритм поиска Гровера.

Проблемы подсчета распространены в различных областях, таких как статистическая оценка, статистическая физика, создание сетей и т. Д. квантовые вычисления, способность выполнять квантовый подсчет эффективно необходима для использования алгоритма поиска Гровера (поскольку для выполнения алгоритма поиска Гровера необходимо знать, сколько существует решений). Более того, этот алгоритм решает квантовую проблему существования (а именно, определение того, является ли любой решение существует) как частный случай.

Алгоритм был разработан Жиль Брассар, Питер Хёйер и Ален Тапп в 1998 году.

Проблема

Рассмотрим конечное множество ${ Displaystyle {0,1 } ^ {п}}$ размера ${ displaystyle N = 2 ^ {n}}$ и набор ${ displaystyle B}$ "решений" (то есть подмножества ${ Displaystyle {0,1 } ^ {п}}$ ). Определять:

{ displaystyle { begin {cases} f: left {0,1 right } ^ {n} to {0,1 } f (x) = { begin {cases} 1 & x в B 0 & x notin B end {case}} end {case}}}

Другими словами, ${ displaystyle f}$ это индикаторная функция из ${ displaystyle B}$ .

Подсчитайте количество решений ${ displaystyle M = left vert f ^ {- 1} (1) right vert = vert B vert}$ .^[1]

Классическое решение

Без каких-либо предварительных знаний о наборе решений ${ displaystyle B}$ (или структура функции ${ displaystyle f}$ ) классическое детерминированное решение не может работать лучше, чем ${ displaystyle Omega (N)}$ , потому что все ${ displaystyle N}$ элементы ${ Displaystyle {0,1 } ^ {п}}$ должны быть проверены (рассмотрим случай, когда последний проверяемый элемент является решением).

Алгоритм

Схема квантового счета

Настраивать

Вход состоит из двух регистры (а именно две части): верхняя ${ displaystyle p}$ кубиты составляют первая регистрация, а нижний ${ displaystyle n}$ кубиты второй регистр.

Создать суперпозицию

Начальное состояние системы ${ displaystyle | 0 rangle ^ { otimes p} | 0 rangle ^ { otimes n}}$ . После применения нескольких бит Операция ворот Адамара на каждом из регистров в отдельности состояние первая регистрация является

{ displaystyle { frac {1} {2 ^ {p / 2}}} (| 0 rangle + | 1 rangle) ^ { otimes p}}

и состояние второй регистр является

{ displaystyle { frac {1} {2 ^ {n / 2}}} (| 0 rangle + | 1 rangle) ^ { otimes n} = { frac {1} { sqrt {N}} } sum _ {x = 0} ^ {N-1} | x rangle}

равный суперпозиция состояние в расчетной базе.

Оператор Гровера

Потому что размер помещения ${ displaystyle left vert {0,1 } ^ {n} right vert = 2 ^ {n} = N}$ а количество решений ${ Displaystyle влево верт Б вправо верт = М}$ , мы можем определить нормализованные состояния:^[2]^:252

{ displaystyle | alpha rangle = { frac {1} { sqrt {NM}}} sum _ {x notin B} {| x rangle}, qquad { text {and}} qquad | beta rangle = { frac {1} { sqrt {M}}} sum _ {x in B} {| x rangle}.}.

Обратите внимание, что

{ displaystyle { sqrt { frac {NM} {N}}} | alpha rangle + { sqrt { frac {M} {N}}} | beta rangle = { frac {1} { sqrt {N}}} sum _ {x = 0} ^ {N-1} {| x rangle},}

что состояние второй регистр после преобразования Адамара.

Геометрическая визуализация алгоритма Гровера показывает, что в двумерном пространстве, натянутом на ${ displaystyle | alpha rangle}$ и ${ displaystyle | beta rangle}$ , оператор Гровера является вращение против часовой стрелки; следовательно, его можно выразить как

{ Displaystyle G = { begin {bmatrix} cos theta & - sin theta sin theta & cos theta end {bmatrix}}}

в ортонормированный базис ${ Displaystyle {| alpha rangle, | beta rangle }}$ .^[2]^:252^[3]^:149

От свойства матриц вращения мы знаем это ${ displaystyle G}$ это унитарная матрица с двумя собственные значения ${ Displaystyle е ^ { пм я тета}}$ .^[2]^:253

Оценка стоимости ${ displaystyle theta}$

С этого момента мы следуем алгоритм квантовой оценки фазы схема: применяем контролируемый Гровер операции, за которыми следуют обратные квантовое преобразование Фурье; и согласно анализ, мы найдем лучшее ${ displaystyle p}$ -битовое приближение к настоящий номер ${ displaystyle theta}$ (принадлежащие собственным значениям ${ displaystyle e ^ { pm я theta}}$ оператора Гровера) с вероятностью выше ${ displaystyle { frac {4} { pi ^ {2}}}}$ .^[4]^:348^[3]^:157

Обратите внимание, что второй регистр фактически находится в суперпозиция из собственные векторы оператора Гровера (в то время как в исходном алгоритме квантовой оценки фазы второй регистр является необходимым собственным вектором). Это означает, что с некоторой вероятностью мы приближаем ${ displaystyle theta}$ , и с некоторой вероятностью приближаем ${ displaystyle 2 pi - theta}$ ; эти два приближения эквивалентны.^[2]^:224–225

Анализ

Предполагая, что размер ${ displaystyle N}$ пространства как минимум в два раза больше числа решений (а именно, если предположить, что ${ Displaystyle M leq { tfrac {N} {2}}}$ ) результат анализа алгоритма Гровера:^[2]^:254

{ displaystyle sin { frac { theta} {2}} = { sqrt { frac {M} {N}}}.}

Таким образом, если мы найдем ${ displaystyle theta}$ , мы также можем найти значение ${ displaystyle M}$ (потому что ${ displaystyle N}$ известен).

Ошибка

{ displaystyle { frac { vert Delta M vert} {N}} = left vert sin ^ {2} left ({ frac { theta + Delta theta} {2}} справа) - sin ^ {2} left ({ frac { theta} {2}} right) right vert}

определяется погрешностью в оценке значения ${ displaystyle theta}$ . Алгоритм квантовой оценки фазы с высокой вероятностью находит лучший ${ displaystyle p}$ -битовое приближение ${ displaystyle theta}$ ; это означает, что если ${ displaystyle p}$ достаточно большой, у нас будет ${ displaystyle Delta theta приблизительно 0}$ , следовательно ${ displaystyle vert Delta M vert приблизительно 0}$ .^[2]^:263

Использует

Алгоритм поиска Гровера изначально неизвестного числа решений

В алгоритме поиска Гровера количество итераций, которые необходимо выполнить, равно ${ displaystyle { frac { pi} {4}} { sqrt { frac {N} {M}}}}$ .^[2]^:254 ^[3]^:150

Таким образом, если ${ displaystyle N}$ известно и ${ displaystyle M}$ вычисляется алгоритмом квантового подсчета, количество итераций для алгоритма Гровера вычисляется легко.

Ускорение NP-полных задач

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

Примером NP-полной задачи является Проблема гамильтонова цикла, что является проблемой определения того, график ${ Displaystyle G = (V, E)}$ имеет Гамильтонов цикл.

Простым решением проблемы гамильтонова цикла является проверка для каждого порядка вершин ${ displaystyle G}$ , будь то гамильтонов цикл или нет. Перебор всех возможных порядков вершин графа может быть выполнен с помощью квантового подсчета, за которым следует алгоритм Гровера, достигая ускорения квадратного корня, аналогичного алгоритму Гровера.^[2]^:264 Этот подход находит гамильтонов цикл (если он существует); для определения, существует ли гамильтонов цикл, достаточно самого алгоритма квантового счета (и даже алгоритма квантового существования, описанного ниже).

Квантовая проблема существования

Проблема квантового существования - это частный случай квантового счета, когда мы не хотим вычислять значение ${ displaystyle M}$ , но мы только хотим знать, ${ displaystyle M neq 0}$ или нет. Тривиальное решение этой проблемы - прямое использование алгоритма квантового счета: алгоритм дает ${ displaystyle M}$ , поэтому, проверив, ${ displaystyle M neq 0}$ мы получаем ответ на проблему существования. Этот подход включает в себя некоторую служебную информацию, потому что нас не интересует ценность ${ displaystyle M}$ .

Использование установки с небольшим количеством кубитов в верхнем регистре не даст точной оценки значения ${ displaystyle theta}$ , но этого будет достаточно, чтобы определить, ${ displaystyle M}$ равно нулю или нет.^[2]^:263

Алгоритм квантового счета - Quantum counting algorithm

Содержание