Алгоритм квантового счета

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

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

Алгоритм был разработан Жилем Брассаром , Питером Хёйером и Аленом Таппом в 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}$

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

Классическое решение [ править ]

Без каких-либо предварительных знаний о наборе решений (или структуре функции ) классическое детерминированное решение не может работать лучше, чем , потому что все элементы должны быть проверены (рассмотрим случай, когда последний проверяемый элемент является решением) . ${\ 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}

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

Оператор Гровера [ править ]

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

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

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

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

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

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

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

в ортонормированном базисе . ^[2]^:²⁵²^[3]^:¹⁴⁹ $\{|\alpha \rangle ,|\beta \rangle \}$

Из свойств матриц вращения мы знаем, что это унитарная матрица с двумя собственными значениями . ^[2]^:²⁵³ $G$ $e^{\pm i\theta }$

Оценка стоимости $\theta$ [ править ]

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

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

Анализ [ править ]

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

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

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

Ошибка

{\frac {\vert \Delta M\vert }{N}}=\left\vert \sin ^{2}\left({\frac {\theta +\Delta \theta }{2}}\right)-\sin ^{2}\left({\frac {\theta }{2}}\right)\right\vert

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

Использует [ редактировать ]

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

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

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

Ускорение NP-полных задач [ править ]

Алгоритм квантового подсчета может использоваться для ускорения решения NP-полных задач .

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

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

Проблема квантового существования [ править ]

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

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

См. Также [ править ]

Алгоритм квантовой оценки фазы
Алгоритм Гровера
Проблема подсчета (сложность)

Ссылки [ править ]

^ Брассар, Жиль; Хойер, Питер; Тэпп, Ален (13–17 июля 1998 г.). Автоматы, языки и программирование (изд. 25-го международного коллоквиума). ICALP'98 Ольборг, Дания: Springer Berlin Heidelberg. С. 820–831. arXiv : квант-ph / 9805082 . DOI : 10.1007 / BFb0055105 . ISBN 978-3-540-64781-2.CS1 maint: location (link)
^ a b c d e f g h i Чуанг, Майкл А. Нильсен и Исаак Л. (2001). Квантовые вычисления и квантовая информация (Ред. Ред.). Кембридж [ua]: Cambridge Univ. Нажмите. ISBN 978-0521635035.
^ a b c Бененти, Гильяно; Стрини, Джулио Касати, Джулиано (2004). Принципы квантовых вычислений и информации (перепечатано. Ред.). Нью-Джерси [ua]: World Scientific. ISBN 978-9812388582.
^ Cleve, R .; Ekert, A .; Macchiavello, C .; Моска, М. (8 января 1998 г.). "Квантовые алгоритмы снова". Труды Королевского общества A: математические, физические и инженерные науки . 454 (1969). arXiv : квант-ph / 9708016 . Bibcode : 1998RSPSA.454..339C . DOI : 10,1098 / rspa.1998.0164 .

[brassard-1] Брассар, Жиль; Хойер, Питер; Тэпп, Ален (13–17 июля 1998 г.). Автоматы, языки и программирование (изд. 25-го международного коллоквиума). ICALP'98 Ольборг, Дания: Springer Berlin Heidelberg. С. 820–831. arXiv : квант-ph / 9805082 . DOI : 10.1007 / BFb0055105 . ISBN 978-3-540-64781-2.CS1 maint: location (link)

[nielchuan-2] ^ a b c d e f g h i Чуанг, Майкл А. Нильсен и Исаак Л. (2001). Квантовые вычисления и квантовая информация (Ред. Ред.). Кембридж [ua]: Cambridge Univ. Нажмите. ISBN 978-0521635035.

[benet-3] Бененти, Гильяно; Стрини, Джулио Касати, Джулиано (2004). Принципы квантовых вычислений и информации (перепечатано. Ред.). Нью-Джерси [ua]: World Scientific. ISBN 978-9812388582.

[ekert-4] Cleve, R .; Ekert, A .; Macchiavello, C .; Моска, М. (8 января 1998 г.). "Квантовые алгоритмы снова". Труды Королевского общества A: математические, физические и инженерные науки . 454 (1969). arXiv : квант-ph / 9708016 . Bibcode : 1998RSPSA.454..339C . DOI : 10,1098 / rspa.1998.0164 .

[1]