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

Квантовый алгоритм подсчета решений задач поиска

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

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

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

Проблема

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

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

Другими словами, – индикаторная функция . ${\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\}^{n}}$

Алгоритм

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

Настраивать

Вход состоит из двух регистров (а именно, двух частей): верхние кубиты составляют первый регистр , а нижние кубиты — второй регистр . ${\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] : 252.} ${\displaystyle \left\vert \{0,1\}^{n}\right\vert =2^{n}=N}$ ${\displaystyle \left\vert B\right\vert =M}$

${\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 }.}$

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

${\displaystyle {\sqrt {\frac {N-M}{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}}}$

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

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

Оценка значения θ

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

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

Анализ

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

${\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}}\right)-\sin ^{2}\left({\frac {\theta }{2}}\right)\right\vert }$

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

Использование

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

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

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

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

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

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

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

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

Проблема существования квантов — это особый случай квантового подсчета, когда мы не хотим вычислять значение , а хотим только знать, так оно или нет. ^{[5] : 147} ${\displaystyle M}$ ${\displaystyle M\neq 0}$

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

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

Проблема тестирования квантовых отношений

Тестирование квантовых отношений . является расширением проверки квантового существования, оно решает, можно ли найти в базе данных хотя бы одну запись, которая соответствует определенному эталонному значению. ^[6] Например, возвращает YES, если база данных содержит какое-либо значение больше 5, в противном случае возвращается NO. Тестирование квантовых отношений в сочетании с классическим логарифмическим поиском образует эффективный алгоритм квантового поиска минимумов и максимумов. ^{[5] : 152  [7]} ${\displaystyle QRT(value,relation)}$ ${\displaystyle QRT(5,>)}$

Смотрите также

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

Рекомендации

1. Брассар, Жиль; Хойер, Питер; Тапп, Ален (13–17 июля 1998 г.). Автоматы, языки и программирование (изд. 25-го Международного коллоквиума). ICALP'98 Ольборг, Дания: Springer Berlin Heidelberg. стр. 820–831. arXiv : Quant-ph/9805082 . дои : 10.1007/BFb0055105. ISBN 978-3-540-64781-2. S2CID  14147978.{{cite book}}: CS1 maint: location (link)
2. Chuang, Майкл А. Нильсен и Исаак Л. (2001). Квантовые вычисления и квантовая информация (Отв. ред.). Кембридж [ua]: Cambridge Univ. Нажимать. ISBN 978-0521635035.
3. Бененти, Гильяно; Стрини, Джулио Казати, Джулиано (2004). Принципы квантовых вычислений и информации (перепечатано под ред.). Нью-Джерси [ua]: World Scientific. ISBN 978-9812388582.{{cite book}}: CS1 maint: multiple names: authors list (link)
4. Клив, Р.; Экерт, А.; Маккиавелло, К.; Моска, М. (8 января 1998 г.). «Возвращение к квантовым алгоритмам». Труды Королевского общества A: Математические, физические и технические науки . 454 (1969): 339–354. arXiv : Quant-ph/9708016 . Бибкод : 1998RSPSA.454..339C. дои : 10.1098/rspa.1998.0164. S2CID  16128238.
5. Имре, Сандор; Балаж, Ференц (январь 2005 г.). Квантовые вычисления и коммуникации – инженерный подход . Уайли. ISBN 978-0470869024.
6. Элгейли, Сара; Имре, Шандор (2021). «Ограниченная квантовая оптимизация для управления распределением ресурсов». Международный журнал передовых компьютерных наук и приложений . 12 (8).
7. Имре, Шандор (2007). «Квантовое тестирование существования и его применение для поиска экстремальных значений в несортированных базах данных». Транзакции IEEE на компьютерах . 56 (5): 706–710. дои : 10.1109/TC.2007.1032. S2CID  29588344.