4511
правок
Квантовый алгоритм поиска треугольников: различия между версиями
Перейти к навигации
Перейти к поиску
Квантовый алгоритм поиска треугольников (посмотреть исходный код)
Версия от 19:48, 6 апреля 2016
, 6 апреля 2016→Нотация и ограничения
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Нотация и ограничения == | == Нотация и ограничения == | ||
Алгоритм квантового запроса | ''Алгоритм квантового запроса'' <math>Q_f : | \psi_0 \rangle \mapsto | \psi_f \rangle \;</math> вычисляет свойство P функции f при помощи отображения исходного состояния <math>| \psi_0 \rangle = | 0 \rangle | 0 \rangle | 0 \rangle \;</math> (в котором регистры запроса, ответа и рабочего пространства очищены) на конечное состояние j fi = Qfj 0i, применяя последовательность Qf = Uk Of (7^-1 Of ■ ■■ U1 Oj Щ унитарных операторов на комплексном векторном пространстве, натянутом на все возможные базисные состояния jxi j aijzi. Унитарные операторы могут быть двух типов: запросы оракула О f. |x)|e)|z) i-> |х)|аф/(х))|г:), приносящие информацию о f, и шаги без запросов Uk, не зависящие от f. Сложность квантовых запросов P равна минимальному числу запросов оракула, требующихся квантовому алгоритму для вычисления P с вероятностью не менее 2/3. | ||
| Строка 19: | Строка 19: | ||
Классические результаты | Классические результаты | ||
Классический показатель сложности рандомизированных запросов определяется подобно сложности квантовых запросов, с той разницей, что операторы Uk являются стохастическими, а не унитарными; в частности, это означает, что запросы оракула могут выполняться в соответствии с классическим распределением, а не с квантовыми суперпозициями. Легко увидеть, что сложность рандомизированных запросов для задачи поиска треугольников (в версиях с поиском и принятием решений) составляет 0(и2). | Классический показатель сложности рандомизированных запросов определяется подобно сложности квантовых запросов, с той разницей, что операторы Uk являются стохастическими, а не унитарными; в частности, это означает, что запросы оракула могут выполняться в соответствии с классическим распределением, а не с квантовыми суперпозициями. Легко увидеть, что сложность рандомизированных запросов для задачи поиска треугольников (в версиях с поиском и принятием решений) составляет 0(и2). | ||
== Основные результаты == | == Основные результаты == | ||