[МУЗЫКА] [МУЗЫКА] Разберем еще несколько простых задач, которые позволят нам сформировать представление о том, что такое типичный квантовый алгоритм. Итак, задача Дойча-Джозы. В некоторых учебниках переводят как Дойча-Йожи. [БЕЗ СЛОВ] У нас есть функция f, которая отображает n-битную строку в 1 бит. И нам известно, что функция f — либо константа, либо количество x, на которых f дает 0, равно количеству x, [БЕЗ СЛОВ] на которых f дает 1. То есть функция либо константа, либо в таком вот смысле сбалансирована. В классическом случае наихудший вариант для нас это если f — константа. Да, вопрос к задаче звучит: является ли f константой? И если она действительно является константой, то для того чтобы достоверно доказать это, нам потребуется вот столько вызовов оракула — обращений к черному ящику. Ну, мы опять посмотрим, помогут ли нам квантовые вычисления сделать это лучше. Квантовый алгоритм выглядит почти так же, как для задачи Дойча. То есть, на самом деле, совершенно так же. [БЕЗ СЛОВ] [БЕЗ СЛОВ] Только входной регистр у нас уже состоит из n кубит, ну а здесь у нас по-прежнему 1 кубит. Таким образом, преобразование Адамара здесь n-кубитное, ну и здесь оно тоже n-кубитное. И, как вы видите, оператор оракула опять вызывается один раз. Давайте посмотрим. Итак, у нас есть такое состояние, которое после действия оператора Адамара превращается по формуле, которую мы доказывали в прошлый раз, в такую вот сумму. [БЕЗ СЛОВ] [БЕЗ СЛОВ] [БЕЗ СЛОВ] И на эту сумму мы должны подействовать нашим оператором Uf. [БЕЗ СЛОВ] [БЕЗ СЛОВ] [БЕЗ СЛОВ] [БЕЗ СЛОВ] [БЕЗ СЛОВ] [БЕЗ СЛОВ] Мы помним, как оператор Uf действует на слагаемые такого вида. Он просто домножает их на −1 в степени f(x). Теперь нас будет интересовать содержание первого вот этого регистра. Давайте его выпишем. Давайте его выпишем для двух случаев: пусть f равно константе. Тогда −1 в степени f(x) мы можем вынести из под знака суммы. Получится −1 в степени f(x). 2 в степени n/2. ∑ по x от 0 это 2 в степени (n − 1) x, что, как мы помним, равно преобразованию Адамара от такого вот вектора, состоящего полностью из 0. И, соответственно, еще раз применив преобразование Адамара, мы получим просто этот вектор. Вектор, состоящий из n нулей, то есть кодируемый строкой из n нулей. И второй случай, когда f сбалансирована, [БЕЗ СЛОВ] −1 в степени f(x) мы уже вынести не можем, но мы можем разбить эту сумму на две суммы. ∑ по x таким, что f(x) = 0. Когда f(x) = 0, −1 в степени f(x) = 1, и тут у нас просто будут x. Еще у нас будет ∑ по x таким, что f(x) = 1, и −1 в степени 1 = −1, и поэтому здесь мы пишем «−». Получается разность таких сумм, причем количество членов в этих суммах равно. И когда мы будем применять преобразование Адамара, для любого х, когда мы применяем преобразование Адамара, мы будем получать строку вида 0 в степени n. То есть там будут какие-то еще строки, будет 2 в степени (n − 1) строк такого вида плюс какие-то еще строки, и здесь тоже будет 2 в степени (n − 1) строк, и это 0 в степени n + что-то еще. И вот эти вот строки 0 в степени n вычтутся друг из друга. То есть в нашей окончательной сумме после преобразования Адамара не останется строк вида 0 в степени n, то есть строк, кодируемых n-нулями. И таким образом, когда f сбалансирована, мы не сможем в результате измерения получить строку такого вида. Поэтому, когда мы применили эту схему и провели измерение, если мы получаем строку вида n-нулей, то мы знаем, что f у нас — константа. Если получаем какую-то любую другую строку, то мы понимаем, что f — сбалансирована, опять же за одно применение квантового оракула.
