Алгоритм Дойча-Джозы
В 1985 году Дэвид Дойч предложил алгоритм, который демонстрировал принципиальную возможность квантового ускорения. Позже, вместе с Ричардом Джозой, он обобщил этот результат на случай многих кубитов. Так появился алгоритм Дойча-Джозы — один из самых простых и одновременно самых показательных квантовых алгоритмов.
Постановка задачи: есть булева функция f, которая на вход принимает строку из n битов и выдаёт один бит (0 или 1).
Нам заранее известно, что функция либо постоянная (всегда возвращает 0 или всегда 1), либо сбалансированная (ровно на половине входов возвращает 0, на половине — 1). Требуется определить, к какому типу относится функция.
Классический компьютер решает эту задачу за экспоненциальное время (ассимтотика O(2^n)). Квантовый алгоритм Дойча-Джозы решает ту же задачу за один-единственный вызов.
Алгоритм Дойча-Джозы использует квантовую суперпозицию: все 2^n входных состояний подготавливаются одновременно, и оракул применяется ко всей суперпозиции за один раз. Фазовый сдвиг, который оракул добавляет к каждому состоянию в зависимости от значения функции, приводит к тому, что информация о глобальном свойстве функции (постоянство или сбалансированность) оказывается закодированной в амплитудах состояний.
Затем с помощью преобразования Адамара и одного измерения эта информация извлекается. Если функция постоянная, измерение с гарантией даст нулевой результат; если сбалансированная — любой ненулевой. Таким образом, задача решается всего за один вызов функции.
Алгоритм Дойча-Джозы, предложенный в 1992 году, — это первый квантовый алгоритм, доказавший, что квантовые вычисления могут быть быстрее классических не просто на проценты, а на целые классы сложности.