[МУЗЫКА] [МУЗЫКА] Задача Саймона. Как обычно в этом модуле у нас есть функция f, спрятанная в черном ящике. На этот раз она отображает n бит в n бит. И нам известно про функцию f, что существует единственное такое число a, такое, что f(x) = f(y) только в том случае, в том и только в том случае, когда x = y ⊕ a. И, как и водится в такого рода задачах, надо узнать число a. В классическом случае это задача сложная. Нам может потребоваться O от 2 в степени n вызовов оракула, прежде чем мы найдем число a. В квантовом случае задача проще. Алгоритм выглядит следующим образом. У нас есть два регистра. Мы подаем на них n кубитные нули. К верхнему регистру, регистру аргументов, применяем n кубитное преобразование Адамара. После этого осуществляем вызов нашего оракула. После этого мы меряем второй регистр. И применяем n кубитное преобразование Адамара к первому регистру. После чего меряем его. Давайте посмотрим, что нам даст выполнение этой схемы. Итак, два регистра с n нулями |0⟩n |0⟩n. Преобразование Адамара к старшему регистру, к регистру аргументов, даст нам по нашей формуле для преобразования Адамара такую сумму. [БЕЗ_ЗВУКА] Второй регистр мы не трогали, после чего мы применяем оператор qf, который поместит значение f(x) в каждом члене этой суммы в зависимости от параметра x. [БЕЗ_ЗВУКА] [БЕЗ_ЗВУКА] [БЕЗ_ЗВУКА] Ну, а таких иксов, для которых мы имеем одинаковые f(x), на самом деле два: x и x ⊕ a. Поэтому я могу объединить эти два икса в скобки, вынеся f(x). [БЕЗ_ЗВУКА] [БЕЗ_ЗВУКА] [БЕЗ_ЗВУКА] И по схеме у нас сейчас идет измерение второго регистра. После того как мы померяем второй регистр, мы получим какое-то значение, конкретное значение f(x) от какого-то конкретного x, назовем его x'. То есть здесь у нас останется f(x'). А во входном регистре у нас останется x' + x' + a. И к этому входному регистру мы будем применять преобразование Адамара. Давайте мы его выпишем. [БЕЗ_ЗВУКА] К этому нам надо применить преобразование Адамара. Давайте по очереди к первому, ко второму. [БЕЗ_ЗВУКА] [БЕЗ_ЗВУКА] [БЕЗ_ЗВУКА] [БЕЗ_ЗВУКА] [БЕЗ_ЗВУКА] Так, и надо аккуратно выписать коэффициенты. Тут будет 1 / 2 в степени n + 1 / 2 везде. Давайте объединим эти суммы, поскольку счетчики у них одинаковые. [БЕЗ_ЗВУКА] [БЕЗ_ЗВУКА] [БЕЗ_ЗВУКА] [БЕЗ_ЗВУКА] [БЕЗ_ЗВУКА] [БЕЗ_ЗВУКА] Давайте посмотрим на степень этой (−1). Просто раскроем скобки. Это (−1) в степени x' • y ⊕ a • y. Пусть у нас a • y ≠ 0. Тогда степени этих (−1) в этой сумме будут разные, и коэффициент при таком |y> будет равен нулю. Соответственно, в этой нашей сумме после преобразования Адамара и до измерения останутся только игреки, такие что a • y = 0. Это, конечно, не дает нам за одно измерение получение числа a. Нам нужно n линейно независимых игреков, чтобы получить число a, решив систему уравнений. Но тем не менее вместо сложности экспоненциальной от числа n мы получаем O (n) вызовов оракула для получения n разных линейно независимых уравнений такого вида. Итак, в этом модуле мы с вами разобрали четыре квантовых алгоритма, рассмотрели простейший прототип квантового компьютера и познакомились с общей структурой квантового алгоритма, в котором сначала нужно подготовить суперпозицию всех возможных состояний, применить интересующую нас функцию и после этого каким-то образом подготовить наше состояние к такому виду, чтобы результат измерения ответил на заданный нами вопрос. В принципе, для базового знакомства с материалом курса этого достаточно. Тех же, кому интересно решение реальных практических задач с помощью квантового компьютера, я жду на следующей неделе.
