Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы

Пусть функция Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №1 - открытая онлайн библиотека имеет однобитовую область определения и однобитовое множество значений. Нетрудно видеть, что таких функций всего четыре. Две из них постоянны:

1. Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №2 - открытая онлайн библиотека , Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №3 - открытая онлайн библиотека , 2. Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №4 - открытая онлайн библиотека , Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №5 - открытая онлайн библиотека

Две другие функции переменны:

3. Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №2 - открытая онлайн библиотека , Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №7 - открытая онлайн библиотека , 4. Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №4 - открытая онлайн библиотека , Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №3 - открытая онлайн библиотека

Квантовая реализация функции Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №10 - открытая онлайн библиотека состоит в том, что двухкубитовое состояние Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №11 - открытая онлайн библиотека преобразуется в состояние Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №12 - открытая онлайн библиотека , т.е.

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №13 - открытая онлайн библиотека

Здесь символ Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №14 - открытая онлайн библиотека означает сложение по модулю 2.

В частности, если во втором кубите исходно записан ноль ( Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №15 - открытая онлайн библиотека ), то функция Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №10 - открытая онлайн библиотека задает следующее преобразование:

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №17 - открытая онлайн библиотека

Графическое представление для квантового вычисления функции Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №10 - открытая онлайн библиотека показано на рисунке.

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №19 - открытая онлайн библиотека

Рис.5.1 Схема квантового вычисления функции Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №10 - открытая онлайн библиотека

Рассмотрим для примера четвертую из представленных выше функций: Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №4 - открытая онлайн библиотека , Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №3 - открытая онлайн библиотека . Нетрудно видеть, что рассматриваемая функция задает следующее преобразование:

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №23 - открытая онлайн библиотека

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №24 - открытая онлайн библиотека

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №25 - открытая онлайн библиотека

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №26 - открытая онлайн библиотека

Задача 5.4 Покажите, что введенное определение квантовой реализации функции задает унитарное преобразование входного состояния в выходное. Найдите соответствующие унитарные матрицы для каждой из четырех представленных выше функций.

Принцип суперпозиции позволяет подавать на вход схемы квантового вычисления функций не только определенное базисное состояние Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №27 - открытая онлайн библиотека , но и произвольную суперпозицию таких состояний. Эта возможность обеспечивает так называемый квантовый параллелизм, которой означает, что (в определенном смысле) квантовый алгоритм позволяет вычислять функцию Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №10 - открытая онлайн библиотека для многих значений аргумента Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №27 - открытая онлайн библиотека одновременно. Квантовый параллелизм, таким образом, обеспечивает принципиально важное преимущество квантовых схем вычислений над классическими. Заметим, в то же время, что результаты квантовых параллельных вычислений не могут быть непосредственно экстрагированы из квантовой системы из-за неизбежной редукции квантового состояния при измерениях.

Задача 5.5 Докажите справедливость результата, представленного на следующем рисунке.

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №30 - открытая онлайн библиотека

Рис. 5.2 Демонстрация квантового параллелизма для функции с однокубитовой областью определения.

Результаты, полученные в задаче, являются простейшей демонстрацией свойства квантового параллелизма. Благодаря действию элемента Адамара Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №31 - открытая онлайн библиотека на первый кубит, на вход вычислителя функции Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №32 - открытая онлайн библиотека поступает суперпозиция состояний Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №33 - открытая онлайн библиотека . В итоге, выходное состояние системы представляет собой суперпозицию результатов вычислений при значениях аргумента Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №34 - открытая онлайн библиотека и Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №35 - открытая онлайн библиотека .

Представленный результат может быть обобщен на вычисление функции Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №10 - открытая онлайн библиотека с Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №37 - открытая онлайн библиотека - битовой областью определения и Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №38 - открытая онлайн библиотека - битовым множеством значений. Квантовая реализация функции Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №10 - открытая онлайн библиотека в этом случае определяется тем же преобразованием Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №13 - открытая онлайн библиотека , где символ Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №14 - открытая онлайн библиотека означает сложение по модулю 2, но теперь Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №27 - открытая онлайн библиотека - не один кубит, а Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №37 - открытая онлайн библиотека - кубитовый регистр данных.

Задача 5.6Докажите справедливость результата, представленного на рисунке.

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №44 - открытая онлайн библиотека

Рис.5.3 Демонстрация квантового параллелизма для функции с Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №37 - открытая онлайн библиотека -кубитовой областью определения.

Указание к задаче: воспользуйтесь результатами задачи 4.10.

Здесь обозначение Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №46 - открытая онлайн библиотека символизирует Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №37 - открытая онлайн библиотека - кубитовый провод (регистр запроса). Каждый кубит рассматриваемого провода подвергается преобразованию Адамара Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №31 - открытая онлайн библиотека , что обеспечивается тензорным произведением Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №49 - открытая онлайн библиотека . Область определения функции Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №10 - открытая онлайн библиотека задана Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №51 - открытая онлайн библиотека базисными состояниями Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №52 - открытая онлайн библиотека . Множество значений функции Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №10 - открытая онлайн библиотека определяется всего двумя состояниями Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №54 - открытая онлайн библиотека и Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №55 - открытая онлайн библиотека . Квантовый параллелизм обеспечивает одновременное вычисление функции в Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №51 - открытая онлайн библиотека точках от Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №34 - открытая онлайн библиотека до Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №58 - открытая онлайн библиотека .

Алгоритм Дойча описывается квантовой схемой, приведенной на рисунке.

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №59 - открытая онлайн библиотека

Рис.5.4 Квантовая схема для алгоритма Дойча

Задача 5.7Покажите, что состояние на выходе схемы Дойча есть:

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №60 - открытая онлайн библиотека ,

когда функция постоянна, т.е. Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №61 - открытая онлайн библиотека

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №62 - открытая онлайн библиотека ,

когда функция переменна, т.е. Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №63 - открытая онлайн библиотека

Указание к задаче: покажите, что действие оператора Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №32 - открытая онлайн библиотека на состояние Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №65 - открытая онлайн библиотека приводит к состоянию Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №66 - открытая онлайн библиотека

Произведем измерение первого кубита выходного состояния Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №67 - открытая онлайн библиотека , полученного в представленной выше задаче. В результате измерения с достоверностью получится Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №54 - открытая онлайн библиотека , если функция постоянна и Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №55 - открытая онлайн библиотека , если функция переменна. Полученный результат весьма поучителен: посредством одного- единственного вычисления мы смогли идентифицировать определенное глобальное свойство функции (ее постоянство или переменность). При классическом рассмотрении задачи нам, очевидно, потребовалось бы два вычисления для решения той же самой задачи.

Заметим, что схема Дойча не ставит цели восстановить неизвестную функцию целиком: она ориентирована только на идентификацию рассматриваемого глобального свойства неизвестной функции.

Можно констатировать, что в алгоритме Дойча двухбитовая неопределенность, соответствующая четырем возможным функциям Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №70 - открытая онлайн библиотека , снижается до однобитовой неопределенности, соответствующей только двум возможным функциям Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №70 - открытая онлайн библиотека . Измерение на выходе схемы Дойча позволяет отличить пару функций (1,2) от пары (3,4). Очевидно, что для того, чтобы отличить пару (1,3) от пары (2,4), достаточно измерить Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №72 - открытая онлайн библиотека . Аналогично, что для того, чтобы отличить пару (1,4) от пары (2,3), достаточно измерить Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №73 - открытая онлайн библиотека . Два последних алгоритма аналогичны в классическом и квантовом случае. Возникает резонный вопрос: почему нет аналога алгоритму Дойча в классической теории информации? Дело в том, что в действительности нет двух раздельных теорий информации (классической и квантовой). Существует только одна последовательная теория информации- это квантовая информатика. Классическая теория информации- есть «урезанная» версия квантовой (в классической теории бит может находиться только в состояниях Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №54 - открытая онлайн библиотека или Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №55 - открытая онлайн библиотека , но не их суперпозиции). Такое «урезание», как мы видим уже на примере алгоритма Дойча, делает теорию логически менее привлекательной, менее последовательной и фактически неполной. Напомним, что точно в таком же отношении друг к другу находятся классическая и квантовая теории вероятностей. Это неслучайно: ведь любое количественное определение информации (например, определение Шеннона) базируется на статистических соображениях.

Оказывается, что задача Дойча допускает простое обобщение на многокубитовый случай. Рассмотрим функцию Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №10 - открытая онлайн библиотека с Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №37 - открытая онлайн библиотека - битовой областью определения и Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №38 - открытая онлайн библиотека - битовым множеством значений. Теперь переменная Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №79 - открытая онлайн библиотека может принимать Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №80 - открытая онлайн библиотека различных значений Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №81 - открытая онлайн библиотека , где Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №82 - открытая онлайн библиотека . Предположим, что нам заранее известно, что функция Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №10 - открытая онлайн библиотека может быть только одного из двух типов: постоянная функция или так называемая сбалансированная функция. Для постоянной функции Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №84 - открытая онлайн библиотека . Если функция сбалансирована, то Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №85 - открытая онлайн библиотека для некоторых Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №79 - открытая онлайн библиотека и Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №87 - открытая онлайн библиотека для остальных значений аргумента, причем значения Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №85 - открытая онлайн библиотека и Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №87 - открытая онлайн библиотека встречаются одинаково часто (в этом и заключается сбалансированность). Пусть, например, имеется функция Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №10 - открытая онлайн библиотека с 10-ти битовой областью определения. Тогда для некоторых 512 значений Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №91 - открытая онлайн библиотека получим Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №85 - открытая онлайн библиотека , а для остальных 512 значений Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №79 - открытая онлайн библиотека получим Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №87 - открытая онлайн библиотека . Задача Дойча- Джозсы состоит в том, чтобы отличить постоянную функцию от сбалансированной.

Алгоритм Дойча- Джозсы является непосредственным обобщением алгоритма Дойча на случай многокубитовых систем. Он описывается следующей квантовой схемой, приведенной на рисунке.

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №95 - открытая онлайн библиотека

Рис. 5.5 Квантовая схема алгоритма Дойча- Джозсы

Задача 5.8Покажите, что на вход вычислителя Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №32 - открытая онлайн библиотека в схеме Дойча- Джозсы поступает состояние Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №97 - открытая онлайн библиотека .

Задача 5.9 Покажите, что на выходе вычислителя Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №32 - открытая онлайн библиотека в схеме Дойча- Джозсы возникает состояние

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №99 - открытая онлайн библиотека

Задача 5.10Убедитесь, что действие оператора Адамара Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №31 - открытая онлайн библиотека на базисные состояния Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №101 - открытая онлайн библиотека отдельного кубита описывается формулой: Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №102 - открытая онлайн библиотека . Покажите, что непосредственно из указанной формулы следует ее Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №37 - открытая онлайн библиотека - кубитовое обобщение: действие оператора Уолша- Адамара Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №104 - открытая онлайн библиотека на базисные состояния Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №37 - открытая онлайн библиотека - кубитового регистра Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №52 - открытая онлайн библиотека описывается формулой:

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №107 - открытая онлайн библиотека .

Здесь Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №108 - открытая онлайн библиотека и Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №109 - открытая онлайн библиотека - запись номеров состояний в двоичном представлении, Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №91 - открытая онлайн библиотека и Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №111 - открытая онлайн библиотека представляют собой Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №37 - открытая онлайн библиотека - компонентные строки из нолей и единиц, Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №113 - открытая онлайн библиотека - скалярное произведение соответствующих строк.

Непосредственно из результатов представленных выше задач следует, что на выходе схемы Уолша- Адамара возникает следующее Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №114 - открытая онлайн библиотека - кубитовое состояние:

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №115 - открытая онлайн библиотека

Проведем теперь измерение первых Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №37 - открытая онлайн библиотека кубитов (регистра запроса). Амплитуда вероятности найти регистр запроса в состоянии Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №117 - открытая онлайн библиотека , очевидно, есть:

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №118 - открытая онлайн библиотека .

Пусть функция Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №10 - открытая онлайн библиотека постоянна, т.е. Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №120 - открытая онлайн библиотека . В этом случае все Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №51 - открытая онлайн библиотека слагаемых в рассматриваемой сумме одинаковы (происходит их конструктивная интерференция), в итоге суммарная амплитуда вероятности оказывается равной Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №122 - открытая онлайн библиотека или Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №123 - открытая онлайн библиотека , а соответствующая вероятность равной единице. Таким образом, если неизвестная функция Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №10 - открытая онлайн библиотека постоянна, то все Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №37 - открытая онлайн библиотека кубитов регистра запроса с достоверностью оказываются в состоянии Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №54 - открытая онлайн библиотека .

Пусть теперь неизвестная функция Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №10 - открытая онлайн библиотека переменна и сбалансирована. Сбалансированность означает, что для половины из Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №51 - открытая онлайн библиотека возможных значений аргумента Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №79 - открытая онлайн библиотека функция равна нулю ( Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №85 - открытая онлайн библиотека ), а для другой половины возможных значений аргумента Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №79 - открытая онлайн библиотека - единице ( Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №87 - открытая онлайн библиотека ). В этом случае в сумме Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №133 - открытая онлайн библиотека положительные и отрицательные слагаемые полностью скомпенсируют друг друга (деструктивная интерференция). Теперь суммарная амплитуда и соответствующая вероятность окажутся равными нулю. Таким образом, если неизвестная функция Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №10 - открытая онлайн библиотека сбалансирована, то регистр запроса никогда не будет обнаружен в состоянии Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №135 - открытая онлайн библиотека . Другими словами, хотя бы один из Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №37 - открытая онлайн библиотека кубитов регистра запроса окажется при измерении в состоянии Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №55 - открытая онлайн библиотека .

Мы видим, что алгоритм Дойча- Джозсы позволяет с достоверностью отличить постоянную функцию от сбалансированной посредством одного- единственного обращения к вычислителю Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №32 - открытая онлайн библиотека .

Задача 5.11Покажите, что при классическом рассмотрении задачи Дойча- Джозсы для того, чтобы с достоверностью отличить постоянную функцию от сбалансированной может потребоваться до Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №139 - открытая онлайн библиотека обращений к устройству, производящему вычисление функции Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №10 - открытая онлайн библиотека .

Результат представленной задачи показывает, что алгоритм Дойча- Джозсы обеспечивает квантовому компьютеру экспоненциальное преимущество в скорости по сравнению с классическим компьютером.

Это преимущество, однако, имеет место только для идеальной задачи абсолютно безошибочной классификации. В реальных задачах нам, как правило, достаточно ограничиться правдоподобным ответом, который является правильным лишь с вероятностью, очень близкой к единице. Кроме того, получать абсолютно достоверные ответы на вопросы при помощи вычислений невозможно и по чисто техническим причинам, поскольку преобразование данных в компьютере (классическом или квантовом) неизбежно сталкивается с возможными технологическими ошибками, шумами и сбоями. Если же мы ограничиваемся правдоподобными (с вероятностью, близкой к единице) ответами, то в задаче Дойча- Джозсы пропадает экспоненциальное преимущество квантового алгоритма по сравнению с классическим вероятностным алгоритмом. Последний заключается в том, что на вход классического вычислителя функции Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №10 - открытая онлайн библиотека подается последовательность случайных чисел Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №142 - открытая онлайн библиотека объема Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №143 - открытая онлайн библиотека и по результатам Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №144 - открытая онлайн библиотека вырабатывается правдоподобный ответ на вопрос о виде функции (постоянная она или сбалансированная).

Задача 5.12 Пусть задача Дойча- Джозсы решается на классическом вероятностном компьютере, причем допускается некоторая малая вероятность Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №145 - открытая онлайн библиотека ошибки (когда сбалансированная функция принимается за постоянную). Какой объем Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №143 - открытая онлайн библиотека последовательности случайных чисел следует взять?

Алгоритм Дойча- Джозсы относится к так называемым квантовым вычислениям с оракулом (прорицателем). Роль оракула здесь играет вычислительное устройство Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №32 - открытая онлайн библиотека . Фактически это устройство представляет собой черный ящик, содержание которого неизвестно и несущественно в данной задаче. Все что мы знаем- это то, что оракул обеспечивает выполнение унитарного преобразования Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №32 - открытая онлайн библиотека , где Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №70 - открытая онлайн библиотека - постоянная или сбалансированная функция. Любое устройство Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №32 - открытая онлайн библиотека - это, конечно, некоторый квантовый код (алгоритм), который обеспечивает выполнение заданного преобразования. Мы можем считать, что синтаксически рассматриваемый код настолько сложен, что мы не в состоянии понять какую функцию он вычисляет (постоянную или сбалансированную). Не имея возможности понять код, мы используем его как черный ящик в квантовой схеме, при этом вопрос о постоянстве или сбалансированности неизвестной функции Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №70 - открытая онлайн библиотека решается экспериментально посредством алгоритма Дойча – Джозсы. Заметим, однако, что такая постановка задачи несколько искусственна.

Главное значение алгоритмов Дойча и Дойча- Джозсы методическое: они раскрывают сущность квантового параллелизма и демонстрируют возможности квантовых вычислений.

5.4. Квантовое преобразование Фурье.

Пусть имеется система из Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №37 - открытая онлайн библиотека кубитов. Ее состояние представляет собой вектор в гильбертовом пространстве размерности Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №82 - открытая онлайн библиотека . Базисные состояния квантовой системы есть Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №154 - открытая онлайн библиотека , где Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №155 - открытая онлайн библиотека

Квантовое преобразование Фурье задается следующим унитарным преобразованием базисных состояний:

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №156 - открытая онлайн библиотека

Преобразование Фурье базисных функций определяет соответствующее преобразование вектора состояния

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №157 - открытая онлайн библиотека

Здесь

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №158 - открытая онлайн библиотека

Последняя формула представляет собой преобразование Фурье комплексных амплитуд вероятности. Результат в точности соответствует так называемому классическому дискретному преобразованию Фурье, примененному к столбцу комплексных чисел Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №159 - открытая онлайн библиотека , где Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №160 - открытая онлайн библиотека (см. например [70]).

Обратное преобразование Фурье для амплитуд вероятности есть

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №161 - открытая онлайн библиотека

Квантовое преобразование Фурье принципиально отличается от аналогичного дискретного преобразования Фурье классического сигнала (несмотря на тождество соответствующих формул). Дело в том, что в квантовой информатике мы имеем дело со специфическим «сигналом», который образован амплитудами вероятности (а не электрическими или механическими напряжениями как в классическом случае). В отличии от классического сигнала, квантовый «сигнал» нельзя измерить никаким «осциллографом» (при измерении квантовое состояние редуцируется в одно из базисных состояний). В то же время, в квантовой информатике мы можем оперировать векторами данных экспоненциально большой размерности (например при Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №162 - открытая онлайн библиотека ).

Для простоты изложения остановимся более подробно на трехкубитовом преобразовании Фурье ( Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №163 - открытая онлайн библиотека , Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №164 - открытая онлайн библиотека ).

Например, базисное состояние Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №165 - открытая онлайн библиотека будет претерпевать следующее изменение

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №166 - открытая онлайн библиотека

Квантовое преобразование Фурье может быть построено на основе элементов Адамара и контролируемого преобразования фазы.

Пусть Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №167 - открытая онлайн библиотека - следующее однокубитовое преобразование фазы:

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №168 - открытая онлайн библиотека

На рисунке 5.6 изображен двухкубитовый элемент, осуществляющий контролируемое фазовое преобразование. Управляемый кубит (нижний) подвергается преобразованию Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №167 - открытая онлайн библиотека , если управляющий кубит (верхний) находится в состоянии Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №55 - открытая онлайн библиотека

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №171 - открытая онлайн библиотека

Рис. 5.6 Двухкубитовый элемент, осуществляющий управляемое фазовое преобразование.

На рисунке 5.7 представлена квантовая цепь, обеспечивающая трехкубитовое преобразование Фурье

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №172 - открытая онлайн библиотека

Рис. 5.7 Квантовая цепь для трехкубитового преобразования Фурье

Задача 5.13Пусть на вход трехкубитовой квантовой схемы, изображенной на представленном выше рисунке, подается состояние Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №173 - открытая онлайн библиотека . Покажите, что на выходе квантовой схемы будет состояние:

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №174 - открытая онлайн библиотека

Решите ту же задачу для других входных состояний Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №154 - открытая онлайн библиотека Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №176 - открытая онлайн библиотека .

Решение задачи свидетельствует о том, что квантовая схема на рисунке действительно дает трехкубитовое преобразование Фурье с одной существенной оговоркой. Легко видеть, что для того, чтобы результат был правильный, на выходе схемы порядок следования кубитов должен быть обращен. Другими словами, двоичное представление состояний на выходе следует читать не слева направо, а справа налево: например Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №177 - открытая онлайн библиотека означает состояние Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №55 - открытая онлайн библиотека и т.д.

Конечно, на выходе схемы можно ввести дополнительные операции обмена состояниями кубитов, но с практической точки зрения это нецелесообразно (лучше договориться об инверсии порядка нумерации кубитов).

Представленная выше трехкубитовая схема допускает простое обобщение на произвольное число кубитов.

Общий алгоритм квантового преобразования Фурье может быть реализован с помощью схемы, изображенной на рисунке.

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №179 - открытая онлайн библиотека

Рис. 5.8 Квантовая цепь для Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №37 - открытая онлайн библиотека - кубитового преобразования Фурье

Подсчитаем число операций, необходимых для осуществления квантового преобразования Фурье. Из схемы видно, что с первым (верхним) кубитом можно связать Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №37 - открытая онлайн библиотека преобразований (преобразование Адамара и Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №182 - открытая онлайн библиотека фазовое преобразование), аналогично со вторым (сверху) кубитом можно связать Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №182 - открытая онлайн библиотека преобразование и т.д. Полное число преобразований, равное сумме арифметической прогрессии, есть Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №184 - открытая онлайн библиотека . Таким образом, число операций, необходимых для осуществления квантового преобразования Фурье, есть величина порядка Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №185 - открытая онлайн библиотека . Отметим, что самые быстрые классические алгоритмы выполняют преобразование Фурье за порядка Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №186 - открытая онлайн библиотека операций (так называемое быстрое преобразование Фурье). Таким образом, квантовый алгоритм имеет экспоненциальное преимущество по сравнению со своим классическим аналогом.

Пример. Пусть имеется 1000- кубитовое состояние ( Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №187 - открытая онлайн библиотека ). Ему отвечает вектор состояния, описывающийся Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №188 - открытая онлайн библиотека комплексными числами. Для осуществления классического быстрого преобразования потребуется проделать порядка Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №189 - открытая онлайн библиотека операций. В то же время, квантовое преобразование над рассматриваемым вектором осуществляется примерно за Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №190 - открытая онлайн библиотека операций.

Таким образом, экспоненциальное преимущество квантового алгоритма по сравнению с классическим позволит на квантовом компьютере ставить и решать задачи, которые никогда не будут решены на классическом компьютере.

Нахождение периода функции

Задача определения периода функции является важным примером применения квантового преобразования Фурье.

Предположим, что имеется периодическая функция Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №10 - открытая онлайн библиотека с периодом Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №192 - открытая онлайн библиотека . Это означает, что для всех Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №79 - открытая онлайн библиотека выполняется тождество:

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №194 - открытая онлайн библиотека

В последней формуле под операцией сложения подразумевается сложение по модулю Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №195 - открытая онлайн библиотека . Предположим дополнительно, что все значения функции Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №10 - открытая онлайн библиотека на одном периоде различны. Очевидно, что функция может быть в точности периодической только в том случае, когда Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №195 - открытая онлайн библиотека делится на Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №192 - открытая онлайн библиотека без остатка, т.е. если Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №199 - открытая онлайн библиотека - целое число.

В качестве начального состояния возьмем следующую однородную суперпозицию (квантовая схема для получения такого состояния представлена в задаче 5.3.3):

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №200 - открытая онлайн библиотека

Проведем измерение второго регистра (регистра функции). Предположим, что при этом мы получим некоторое значение функции Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №201 - открытая онлайн библиотека . Пусть Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №202 - открытая онлайн библиотека - одно из значений аргумента, при котором Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №203 - открытая онлайн библиотека . В результате редукции вектора состояния в суперпозиции «выживут» только слагаемые, отвечающие Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №204 - открытая онлайн библиотека , где Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №205 - открытая онлайн библиотека , поскольку только для них Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №206 - открытая онлайн библиотека . В результате первый регистр (отвечающий аргументу Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №79 - открытая онлайн библиотека ) перейдет в следующее квантовое состояние:

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №208 - открытая онлайн библиотека

Выполним теперь квантовое преобразование Фурье над полученным состоянием. Согласно определению, каждое отдельно взятое базисное состояние будет подвергнуто следующему преобразованию:

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №209 - открытая онлайн библиотека

Суперпозиция, представляющая состояние Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №210 - открытая онлайн библиотека , в результате квантового преобразования Фурье примет вид:

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №211 - открытая онлайн библиотека

Задача 5.14Пусть Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №212 - открытая онлайн библиотека , где Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №213 - открытая онлайн библиотека и Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №214 - открытая онлайн библиотека . Покажите, что Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №215 - открытая онлайн библиотека , если Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №216 - открытая онлайн библиотека , где Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №217 - открытая онлайн библиотека и Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №218 - открытая онлайн библиотека при всех остальных значениях Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №219 - открытая онлайн библиотека .

Результаты представленной выше задачи показывают, что выходное состояние регистра может быть записано в виде:

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №220 - открытая онлайн библиотека

Последний шаг процедуры – это измерение полученного состояния. Мы видим, что с равной вероятностью возможно любое из Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №192 - открытая онлайн библиотека состояний Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №222 - открытая онлайн библиотека , где Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №217 - открытая онлайн библиотека .

Пусть Природа «выбрала» некоторое Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №224 - открытая онлайн библиотека и в результате измерения возникло состояние Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №225 - открытая онлайн библиотека . Тогда, имеем следующее тождество для четырех целых чисел:

Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №226 - открытая онлайн библиотека

Здесь Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №227 - открытая онлайн библиотека и Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №195 - открытая онлайн библиотека доступные исследователю числа, в то время как Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №224 - открытая онлайн библиотека и Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №192 - открытая онлайн библиотека - числа, неизвестные ему. Наша цель- определить Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №192 - открытая онлайн библиотека . Полученное тождество показывает, что исследователь не может гарантированно определить Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №192 - открытая онлайн библиотека при однократном выполнении процедуры. Чтобы его поиски оказались продуктивны, ему следует уповать на то, что «выбранное» Природой число Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №224 - открытая онлайн библиотека и период Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №192 - открытая онлайн библиотека окажутся взаимно простыми (т.е. не будут иметь общих делителей, кроме единицы). Тогда, приведя дробь Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №235 - открытая онлайн библиотека к несократимой, он сможет восстановить Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №224 - открытая онлайн библиотека и Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №192 - открытая онлайн библиотека . В этом случае нам удастся с помощью одного уравнения (7) найти два неизвестных целых числа. Если же исследователю не повезет и Природа «выберет» такое Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №224 - открытая онлайн библиотека , что дробь Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №239 - открытая онлайн библиотека окажется сократимой, то вместо истинного периода Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №192 - открытая онлайн библиотека он получит меньшее значение.

Приведем пример. Пусть Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №241 - открытая онлайн библиотека - заранее известное число. Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №242 - открытая онлайн библиотека - период, неизвестный исследователю. Природа может «выбрать» любое Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №224 - открытая онлайн библиотека от 0 до 63. Пусть, например, она «выбрала» Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №244 - открытая онлайн библиотека . Тогда исследователь получит Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №245 - открытая онлайн библиотека . Сократив дробь Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №246 - открытая онлайн библиотека до Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №247 - открытая онлайн библиотека , исследователь правильно определит, что Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №244 - открытая онлайн библиотека и Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №242 - открытая онлайн библиотека . Пусть теперь, Природа «выбрала» Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №250 - открытая онлайн библиотека . Этот выбор неудачен для исследователя, поскольку числа 12 и 64 имеют общий делитель, равный 4. Теперь Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №251 - открытая онлайн библиотека . Сократив дробь Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №252 - открытая онлайн библиотека до Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №253 - открытая онлайн библиотека , исследователь может сделать неправильный вывод, будто бы Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №254 - открытая онлайн библиотека и Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №255 - открытая онлайн библиотека . Для того, чтобы с высокой вероятностью получить правильный ответ, исследователь будет вынужден повторять описанную процедуру многократно. Тогда, очевидно, в качестве ответа ему следует взять период, отвечающий наибольшему из возможных значений (максимальный знаменатель в дроби Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №235 - открытая онлайн библиотека после ее сокращения).

Оценим, сколько раз исследователь должен проделать описанную выше процедуру, чтобы определить неизвестный период Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №192 - открытая онлайн библиотека с высокой гарантией. Для этого нужно оценить вероятность того, что «выбранное» Природой число Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №224 - открытая онлайн библиотека окажется взаимно простым с Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №192 - открытая онлайн библиотека . Известно, что при больших Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №192 - открытая онлайн библиотека количество простых чисел, не превышающих Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №192 - открытая онлайн библиотека можно оценить как Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №262 - открытая онлайн библиотека . Отсюда следует, что вероятность удачи при отдельном испытании больше или порядка Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №263 - открытая онлайн библиотека . Таким образом, если исследователь повторит процедуру Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №264 - открытая онлайн библиотека раз, то с высокой гарантией, он сможет найти неизвестный период. Например, если Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №265 - открытая онлайн библиотека , то потребуется всего порядка 1000 испытаний (в оценках такого рода мы не делаем различия между натуральным и двоичным логарифмами).

Резюмируем полученный результат. Квантовый алгоритм нахождения периода функций требует всего Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №266 - открытая онлайн библиотека операций (для квантового преобразования Фурье требуется Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №267 - открытая онлайн библиотека операций и Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №264 - открытая онлайн библиотека операций требуется для описанной выше процедуры угадывания). Рассматриваемый алгоритм является полиномиальным по числу кубитов и, соответственно, по количеству знаков в числе Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №269 - открытая онлайн библиотека (поскольку число шагов алгоритма определяется полиномом третьей степени).

Для экспоненциально больших Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №269 - открытая онлайн библиотека полиномиальный квантовый алгоритм обладает радикальным преимуществом по сравнению с любыми известными классическими алгоритмами. Важный пример использования отмеченного преимущества рассмотрен в следующем разделе.

Факторизация чисел

Алгоритм нахождения периода функции, рассмотренный выше, может быть с успехом применен для разложения заданного целого числа на множители. Эта задача решается с помощью алгоритма, придуманного П. Шором в 1994 г.

В настоящее время алгоритм Шора- самый знаменитый из известных квантовых алгоритмов. Он позволяет за Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №266 - открытая онлайн библиотека шагов осуществить разложение целого числа Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №195 - открытая онлайн библиотека на множители и, таким образом, является алгоритмом полиномиальной сложности. Заметим, что аналогичный классический полиномиальный алгоритм неизвестен.

Пусть Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №195 - открытая онлайн библиотека - целое нечетное число (при четном Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №195 - открытая онлайн библиотека имеем тривиальное решение задачи). Нам требуется разложить данное число на простые множители или показать, что оно простое.

Выберем случайно число Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №275 - открытая онлайн библиотека . Вычислим наибольший общий делитель (НОД) чисел Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозсы - №276 - открытая онлайн библиотека и

Рекомендуемые статьи

Информационнокибернетическая модель К. Дойча

Информационно-кибернетическая модель К. Дойча

Модель политической системы К.Дойча

Алгоритм Дойча

Информационно-кибернетическая модель К. Дойча

Без Дойча, просто продолжение темы)

Информационно-кибернетическая модель К. Дойча