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

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

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

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

Проблема

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

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

Другими словами, $f$ – индикаторная функция $B$ .

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

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

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

Алгоритм

Настраивать

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

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

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

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

и состояние регистра второго

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

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

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

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

|\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}}

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

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

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

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

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

Анализ

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

\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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

Ссылки

^ Брассар, Жиль; Хойер, Питер; Тапп, Ален (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: местоположение ( ссылка )
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Чуанг, Майкл А. Нильсен и Исаак Л. (2001). Квантовые вычисления и квантовая информация (Отв. ред.). Кембридж [ua]: Cambridge Univ. Нажимать. ISBN 978-0521635035 .
^ Jump up to: ^а ^б ^с Бененти, Гильяно; Стрини, Джулио Казати, Джулиано (2004). Принципы квантовых вычислений и информации (перепечатано под ред.). Нью-Джерси [ua]: World Scientific. ISBN 978-9812388582 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Умный.; Экерт, А.; Маккиавелло, К.; Моска, М. (8 января 1998 г.). «Возвращение к квантовым алгоритмам». Труды Королевского общества A: Математические, физические и технические науки . 454 (1969): 339–354. arXiv : Quant-ph/9708016 . Бибкод : 1998RSPSA.454..339C . дои : 10.1098/rspa.1998.0164 . S2CID 16128238 .
^ Jump up to: ^а ^б ^с Имре, Шандор; Балаж, Ференц (январь 2005 г.). Квантовые вычисления и коммуникации – инженерный подход . Уайли. ISBN 978-0470869024 .
^ Элгейли, Сара; Имре, Шандор (2021). «Ограниченная квантовая оптимизация для управления распределением ресурсов». Международный журнал передовых компьютерных наук и приложений . 12 (8).
^ Имре, Шандор (2007). «Квантовое тестирование существования и его применение для поиска экстремальных значений в несортированных базах данных». Транзакции IEEE на компьютерах . 56 (5): 706–710. дои : 10.1109/TC.2007.1032 . S2CID 29588344 .

[brassard-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: местоположение ( ссылка )

[nielchuan-2] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Чуанг, Майкл А. Нильсен и Исаак Л. (2001). Квантовые вычисления и квантовая информация (Отв. ред.). Кембридж [ua]: Cambridge Univ. Нажимать. ISBN 978-0521635035 .

[benet-3] Jump up to: ^а ^б ^с Бененти, Гильяно; Стрини, Джулио Казати, Джулиано (2004). Принципы квантовых вычислений и информации (перепечатано под ред.). Нью-Джерси [ua]: World Scientific. ISBN 978-9812388582 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )

[ekert-4] Умный.; Экерт, А.; Маккиавелло, К.; Моска, М. (8 января 1998 г.). «Возвращение к квантовым алгоритмам». Труды Королевского общества A: Математические, физические и технические науки . 454 (1969): 339–354. arXiv : Quant-ph/9708016 . Бибкод : 1998RSPSA.454..339C . дои : 10.1098/rspa.1998.0164 . S2CID 16128238 .

[imres1-5] Jump up to: ^а ^б ^с Имре, Шандор; Балаж, Ференц (январь 2005 г.). Квантовые вычисления и коммуникации – инженерный подход . Уайли. ISBN 978-0470869024 .

[imres2-6] Элгейли, Сара; Имре, Шандор (2021). «Ограниченная квантовая оптимизация для управления распределением ресурсов». Международный журнал передовых компьютерных наук и приложений . 12 (8).

[imres3-7] Имре, Шандор (2007). «Квантовое тестирование существования и его применение для поиска экстремальных значений в несортированных базах данных». Транзакции IEEE на компьютерах . 56 (5): 706–710. дои : 10.1109/TC.2007.1032 . S2CID 29588344 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]