Вычисление функции в кубитовом регистре

Пусть задана функция f(x), преобразующая n-разрядное число x в m-разрядное число f(x). Для описания функции можно построить таблицу

В квантовом компьютере достаточно лишь один раз выполнить преобразование f(х) исходного регистра, где содержатся все n-разрядные числа x и функция готова. Для ее записи нужно иметь n+m ячеек памяти.

6

Идея квантовых вычислений

•Принципквантовых вычисленийзаключен в увеличениимодулякомплексных амплитуд │λx0│тех состояний│x0,f(x0)>, которые хотелосьбы получить в результате считывания.

•Процессвычисления – последовательность унитарных преобразований ненаблюдаемогосостояниярегистра.

8

Задачи, решаемыес помощьюквантового компьютера

•Проверка является либулева функция константой– алгоритм Дойча-Джоза.

• Задача поиска решенияуравнения f (x) =1 , где функцияпринимает значения(0,1) – алгоритм Гровера.

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

•Задача факторизациичисла – алгоритм Шора.

9

Алгоритм Дойча (алгоритм)параллельных вычислений

• Рассмотрим булеву функцию от одной

•Первые две функции –функции константы, 3 и 4 функции не константы. Чтобы определить тип функции, нужно в классической системе сделать два запроса на вычисления. При квантовых вычислениях – только один.

10