4551
правка
Квантование цепей Маркова: различия между версиями
Перейти к навигации
Перейти к поиску
Квантование цепей Маркова (посмотреть исходный код)
Версия от 17:09, 15 октября 2022
, 15 октября 2022→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Квантовые блуждания == Постановка задачи == '''Пространствен…») |
Irina (обсуждение | вклад) |
||
| Строка 5: | Строка 5: | ||
'''Пространственный поиск и процессы блуждания''' | '''Пространственный поиск и процессы блуждания''' | ||
''Пространственный поиск'' посредством ''квантового блуждания'' представляет собой поиск в базе данных с дополнительным ограничением, заключающимся в том, что перемещение по пространству поиска происходит путем квантового блуждания, подчиняющегося некоторой структуре локальности (решетка, гиперкуб и т .д.). Квантовые блуждания являются аналогами классических случайных блужданий на графах. Сложность пространственного поиска с помощью квантового блуждания определяется главным образом ''квантовым временем достижения цели'' [9] данного блуждания. | |||
Пусть S, |S| = N, – конечное множество ''состояний'', и пусть <math>P = (p_{x, y})_{x, y \in S}</math> – ''матрица вероятностей перехода'' для ''цепи Маркова'' на S, также обозначаемая P. Предположим, что подмножество состояний <math>M \subseteq S</math> ''помечено''. Задача состоит в том, чтобы найти помеченное состояние, учитывая, что <math>M \ne \empty</math> (''версия с поиском''), или определить, является ли M непустым (''версия с принятием решений''). Если возможные перемещения <math>x \to y</math> (т. е. те, при которых <math>p_{x, y} \ne 0)</math> образуют ребра (ориентированного) графа G, то говорится, что блуждание имеет ''структуру локальности'' G. | |||
Пусть S, |S| = N, – конечное множество состояний, и пусть P = ( | |||
| Строка 30: | Строка 29: | ||
Квантовая схема X = XmXm-\ 1.. X1, с «проводами» (обычно их два), которые переносят CS и управляющие биты. Каждый элемент Xi является либо WP-вентилем, либо OM- вентилем, либо управляемой версией одного из них. X применяется к начальному состоянию фо. Стоимость последовательности равна сумме стоимостей отдельных операторов. Вероятность наблюдения – это вероятность того, что после измерения конечного состояния, фт, в стандартном базисе, один из проводов выводит элемент из М. Если вероятность наблюдения равна q, необходимо повторить процедуру 1/pq раз, используя усиление по амплитуде (версия с поиском). В версии с принятием решений можно отличить М от М0, если \Хфо - Х'фо\ > 0:1, где Х возникает из ОМ, а Х0 из ОМ0. | Квантовая схема X = XmXm-\ 1.. X1, с «проводами» (обычно их два), которые переносят CS и управляющие биты. Каждый элемент Xi является либо WP-вентилем, либо OM- вентилем, либо управляемой версией одного из них. X применяется к начальному состоянию фо. Стоимость последовательности равна сумме стоимостей отдельных операторов. Вероятность наблюдения – это вероятность того, что после измерения конечного состояния, фт, в стандартном базисе, один из проводов выводит элемент из М. Если вероятность наблюдения равна q, необходимо повторить процедуру 1/pq раз, используя усиление по амплитуде (версия с поиском). В версии с принятием решений можно отличить М от М0, если \Хфо - Х'фо\ > 0:1, где Х возникает из ОМ, а Х0 из ОМ0. | ||
== Основные результаты == | == Основные результаты == | ||