Русская Википедия:Квантовое преобразование Фурье

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Квантовое преобразование Фурье (сокр. КПФ) — линейное преобразование квантовых битов (кубитов), являющееся квантовым аналогом дискретного преобразования Фурье (ДПФ). КПФ входит во множество квантовых алгоритмов, в особенности в алгоритм Шора разложения числа на множители и вычисления дискретного логарифма, в квантовый алгоритм оценки фазы для нахождения собственных чисел унитарного оператора и алгоритмы для нахождения скрытой подгруппы.

Квантовое преобразование Фурье эффективно исполняется на квантовых компьютерах путём специального разложения матрицы в произведение более простых унитарных матриц. С помощью такого разложения, дискретное преобразование Фурье на <math>2^n</math> входных амплитудах может быть осуществлено квантовой сетью, состоящей из <math>O(n^2)</math> вентилей Адамара и контролируемых квантовых вентилей, где <math>n</math> — число кубитов. По сравнению с классическим ДПФ, использующим <math>O(n2^n)</math> элементов памяти (<math>n</math> — количество бит), что экспоненциально больше, чем <math>O(n^2)</math> квантовых вентилей КПФ.

Наилучшие из известных алгоритмов квантового преобразования Фурье (по состоянию на конец 2000) задействуют только <math>O(n\log n)</math> вентилей для достижения желаемого приближения результатаШаблон:Sfn.

Определение

Квантовое преобразование Фурье — классическое дискретное преобразование Фурье, применённое к вектору амплитуд квантовых состояний. Обычно рассматривают такие вектора, имеющие длину <math>N := 2^n</math>. Классическое преобразование Фурье действует на вектор <math> (x_0, x_1, \ldots , x_{N-1}) \in \mathbb{C}^N</math> и отображает его в вектор <math> (y_0, y_1, \ldots , y_{N-1}) \in \mathbb{C}^N</math> по формуле:

<math>y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j \omega_n^{-jk}, \quad k=0,1,2, \ldots ,N-1, </math>

где <math>\omega_n= e^{\frac{2 \pi i}{N}}</math> — N^ый корень из единицы.

Аналогично, КПФ действует на квантовое состояние <math>|x\rangle = \sum_{i=0}^{N-1} x_i |i\rangle</math> и отображает его в квантовое состояние <math>\sum_{i=0}^{N-1} y_i |i\rangle</math> по формуле:

<math>y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j \omega_n^{jk}, \quad k=0,1,2, \ldots ,N-1, </math>

где <math>\omega_n</math> та же, что и раньше. Так как <math>\omega_n</math> — вращение, обратное преобразование Фурье производится аналогично

<math>y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j \omega_n^{-jk} </math>

Если <math>x</math> — базисное квантовое состояние, квантовое преобразование Фурье может быть представлено в виде отображенияШаблон:Sfn:

<math>QFT(|x\rangle) = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} \omega_n^{jx} |j\rangle</math>.

КПФ может эквивалентно рассматриваться как унитарная матрица (чем являются квантовые вентили), действующая на векторы квантовых состояний. Такая матрица <math>F_N</math> имеет не произвольный, а строго определённый вид

<math>

F_N = \frac{1}{\sqrt{N}} \begin{bmatrix} 1&1&1&1&\cdots &1 \\ 1&\omega_n&\omega_n^2&\omega_n^3&\cdots&\omega_n^{N-1} \\ 1&\omega_n^2&\omega_n^4&\omega_n^6&\cdots&\omega_n^{2(N-1)}\\ 1&\omega_n^3&\omega_n^6&\omega_n^9&\cdots&\omega_n^{3(N-1)}\\ \vdots&\vdots&\vdots&\vdots&&\vdots\\ 1&\omega_n^{N-1}&\omega_n^{2(N-1)}&\omega_n^{3(N-1)}&\cdots&\omega_n^{(N-1)(N-1)} \end{bmatrix} </math>.

Поскольку <math>N:=2^n</math> и <math>\omega_n := e^{\frac{2 \pi i}{2^n}}</math> — простейший (наименьшая по модулю экспоненциальная часть) N-й корень из единицы, для случая <math>N=4=2^2</math> и фазы <math>\omega_2 = i</math> получаем матрицу преобразования

<math>

F_4 = \frac{1}{2} \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{bmatrix} </math>.

Свойства

Унитарность

Файл:2-Qubit QFT.gif

Симуляция квантовой цепи, состоящей из двух кубитов с использованием Q-Kit

Большинство свойств КПФ следует из того, что данное преобразование унитарно. Этот факт легко проверяется путём умножения матриц <math>FF^{\dagger}=F^{\dagger}F=I</math>, где <math>F^\dagger</math> — эрмитово-сопряжённая матрица к <math>F</math>.

Из унитарных свойств следует, что обратное к КПФ преобразование имеет матрицу, эрмитово-сопряжённую к матрице преобразования Фурье, поэтому <math>F^{-1}=F^{\dagger}</math>. Если существует эффективная квантовая сеть, осуществляющая КПФ, то эта же сеть может быть запущена в обратную сторону для проведения обратного квантового преобразования Фурье. А это значит, что оба преобразования могут работать эффективно на квантовом компьютере.

Симуляции квантовых сетей двух возможных вариантов 2-кубитового КПФ, использующего <math>F</math> и <math>F^{-1}</math>, показаны для демонстрации идентичного результата (используется Q-Kit).

Построение сетей

Квантовые вентили, используемые в сетях КПФ — вентиль Адамара и вентиль с контролируемой фазой. В терминах матриц

<math>H := \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}, \quad

R_m := \begin{pmatrix} 1 & 0 \\ 0 & \omega_m \end{pmatrix},</math> где <math>\omega_m := e^{\frac{2 \pi i}{2^m}}</math> — <math>2^m</math>-й корень из единицы.

Файл:Q fourier nqubits.png

Квантовая сеть КПФ с n кубитами (инвертированный порядок выходных кубитов). Использует понятие двоичного разложения, введённое ниже.

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

Сеть КПФ можно построить для любого числа входных амплитуд N; однако, это проще всего сделать в случае <math>N = 2^n</math>. Тогда получается Ортонормированная система из векторов

<math> |0\rangle, \ldots , |2^n - 1\rangle. </math>

Базисные состояния перечисляют все возможные состояния кубитов:

<math> | x \rangle = | x_1 x_2 \ldots x_n \rangle = | x_1 \rangle \otimes | x_2 \rangle \otimes \cdots \otimes | x_n \rangle</math>

где, по правилу тензорного суммирования <math>\otimes</math>, <math>|x_j\rangle</math> означает, что кубит <math>j</math> находится в состоянии <math>x_j</math>, с <math>x_j</math> 0 либо 1. По соглашению, индекс базисного состояния <math>x</math> указывает на возможные состояния этого кубита, то есть является двоичным разложением:

<math> x = x_1 2^{n-1} + x_2 2^{n-2} +\cdots + x_n 2^0.\quad </math>

Также удобно использовать дробную двоичную нотацию:

<math> [0. x_1 \ldots x_m] = \sum_{k = 1}^m x_k 2^{-k}.</math>

Например, <math>[0.x_1] = \frac{x_1}{2}</math> и <math>[0.x_1 x_2] = \frac{x_1}{2}+\frac{x_2}{2^2}.</math>

Используя эти обозначения, КПФ записывается коротко:

<math>QFT(|x_1 x_2 \ldots x_n \rangle) = \frac{1}{\sqrt{N}} \ \left(|0\rangle + e^{2 \pi i \, [0.x_n] }|1\rangle\right) \otimes \left(|0\rangle + e^{2 \pi i \, [0.x_{n-1} x_n] }|1\rangle\right) \otimes \cdots \otimes \left(|0\rangle + e^{2 \pi i \, [0.x_1 x_2 \ldots x_n] }|1\rangle\right)</math>

или

<math>QFT(|x_1 x_2 \ldots x_n \rangle)= \frac{1}{\sqrt{N}} \ \left(|0\rangle + \omega_1^x |1\rangle\right) \otimes \left(|0\rangle + \omega_2^x|1\rangle\right) \otimes \cdots \otimes \left(|0\rangle + \omega_n^x|1\rangle\right).</math>

Краткость налицо, представив двоичное разложение обратно в виде суммы

<math>QFT(|x_1 x_2 \ldots x_n \rangle) = \frac{1}{\sqrt{N}} \sum_{k=0}^{2^n-1}e^{2 \pi i k [0.x_1 x_2 \ldots x_n]} |k\rangle </math>

<math>= \frac{1}{\sqrt{N}} \sum_{\{k_0, k_1,... k_{n-1}\} \in \{0,1\}^n} e^{2 \pi i \sum_{j=1}^{n} k_{n-j} 2^{j-1} [0.x_1 x_2 \ldots x_n]} |k_0 k_1 \ldots k_{n-1}\rangle</math>

<math>= \frac{1}{\sqrt{N}} \sum_{\{k_0, k_1,... k_{n-1}\} \in \{0,1\}^n} \prod_{j=1}^{n} e^{2 \pi i k_{n-j} [0.x_j x_{j+1} \ldots x_n]} |k_0 k_1 \ldots k_{n-1}\rangle</math>

<math>= \frac{1}{\sqrt{N}} (|0\rangle + e^{2 \pi i [0.x_n]}|1\rangle) \sum_{\{k_1,... k_{n-1}\} \in \{0,1\}^{n-1}} \prod_{j=1}^{n-1} e^{2 \pi i k_{n-j} [0.x_j x_{j+1} \ldots x_n]} |k_1 \ldots k_{n-1}\rangle</math>

<math>= \frac{1}{\sqrt{N}} \prod_{j=1}^{n} (|0\rangle + e^{2 \pi i [0.x_j x_{j+1} \ldots x_n]}|1\rangle)</math>

Видно, что выходной кубит 1 находится в суперпозиции состояний <math>|0\rangle</math> и <math>e^{2 \pi i \, [0.x_1...x_n] }|1\rangle</math>, кубит 2 — в суперпозиции <math>|0\rangle</math> и <math>e^{2 \pi i \, [0.x_2...x_n] }|1\rangle</math> и т. д. для остальных кубитов (см. схему-рисунок выше).

Другими словами, ДПФ, операция над n кубитами, может быть разложена в тензорное произведение n однокубитных операций, Действительно, каждая из таких однокубитных операций эффективным образом реализуется на вентилях с контролируемой фазой и вентилях Адамара. Первый кубит <math>|x_1\rangle</math> потребует один вентиль Адамара и (n-1) вентилей с контролируемой фазой, второй <math>|x_2\rangle</math> потребует два вентиля Адамара и (n-2) вентилей с контролируемой фазой, и так далее (см. схему выше). В итоге потребуется <math>n + (n-1) + \cdots + 1 = n(n+1)/2 = O(n^2)</math> вентилей, что квадратично полиномиально по отношению к количеству кубитов.

Пример

Рассмотрим квантовое преобразование Фурье на трёх кубитах. Математически оно записывается

<math>QFT: |x\rangle \mapsto \frac{1}{\sqrt{2^3}} \sum_{k=0}^{2^3-1} \omega_3^{xk} |k\rangle, </math>

где <math>\omega_3</math> — простейший восьмой корень из единицы, удовлетворяющий <math>\omega_3^8=\left(e^{\frac{2\pi i}{2^3}}\right)^8=1</math> (поскольку <math>N = 2^3 = 8</math>).

Для сокращения, установим <math>\omega := \omega_3</math>, тогда матричное представление КПФ на трёх кубитах

<math>

F_{2^3} = \frac{1}{\sqrt{2^3}} \begin{bmatrix} 1&1&1&1&1&1&1&1 \\ 1&\omega&\omega^2&\omega^3&\omega^4&\omega^5&\omega^6&\omega^7 \\ 1&\omega^2&\omega^4&\omega^6&\omega^8&\omega^{10}&\omega^{12}&\omega^{14} \\ 1&\omega^3&\omega^6&\omega^9&\omega^{12}&\omega^{15}&\omega^{18}&\omega^{21} \\ 1&\omega^4&\omega^8&\omega^{12}&\omega^{16}&\omega^{20}&\omega^{24}&\omega^{28} \\ 1&\omega^5&\omega^{10}&\omega^{15}&\omega^{20}&\omega^{25}&\omega^{30}&\omega^{35} \\ 1&\omega^6&\omega^{12}&\omega^{18}&\omega^{24}&\omega^{30}&\omega^{36}&\omega^{42} \\ 1&\omega^7&\omega^{14}&\omega^{21}&\omega^{28}&\omega^{35}&\omega^{42}&\omega^{49} \\ \end{bmatrix} = \frac{1}{\sqrt{2^3}} \begin{bmatrix} 1&1&1&1&1&1&1&1 \\ 1&\omega&\omega^2&\omega^3&\omega^4&\omega^5&\omega^6&\omega^7 \\ 1&\omega^2&\omega^4&\omega^6&1&\omega^2&\omega^4&\omega^6 \\ 1&\omega^3&\omega^6&\omega&\omega^4&\omega^7&\omega^2&\omega^5 \\ 1&\omega^4&1&\omega^4&1&\omega^4&1&\omega^4 \\ 1&\omega^5&\omega^2&\omega^7&\omega^4&\omega&\omega^6&\omega^3 \\ 1&\omega^6&\omega^4&\omega^2&1&\omega^6&\omega^4&\omega^2 \\ 1&\omega^7&\omega^6&\omega^5&\omega^4&\omega^3&\omega^2&\omega \\ \end{bmatrix}. </math> Это можно упростить, заметив <math>\omega^4=-1</math>, <math>\omega^2=i</math>, <math>\omega^6=-i</math>, <math>\omega^5=-\omega</math>, <math>\omega^3=i\omega</math> и <math>\omega^7=-i\omega</math>.

3-кубитное квантовое преобразование Фурье перепишется в виде

<math>QFT(|x_1, x_2, x_3 \rangle ) = \frac{1}{\sqrt{2^3}} \ \left(|0\rangle + e^{2 \pi i \, [0.x_3] }|1\rangle\right) \otimes \left(|0\rangle + e^{2 \pi i \, [0.x_2 x_3] }|1\rangle\right) \otimes \left(|0\rangle + e^{2 \pi i \, [0.x_1 x_2 x_3] }|1\rangle\right)</math>

или

<math>QFT(|x_1, x_2, x_3 \rangle ) = \frac{1}{\sqrt{2^3}} \ \left(|0\rangle + \omega_1^x |1\rangle\right) \otimes \left(|0\rangle + \omega_2^x |1\rangle\right) \otimes \left(|0\rangle + \omega_3^x|1\rangle\right).</math>

Для использования сети составим разложение КПФ в обратном порядке, а именно

<math>|x_1, x_2, x_3 \rangle \longmapsto \frac{1}{\sqrt{2^3}} \ \left(|0\rangle + \omega_3^x |1\rangle\right) \otimes \left(|0\rangle + \omega_2^x |1\rangle\right) \otimes \left(|0\rangle + \omega_1^x|1\rangle\right).</math>

На рисунке ниже представлена сеть для <math>n:=3</math> (с обратным порядком выходных кубитов по отношению к прямому КПФ).

Файл:Q fourier 3qubits.png

КПФ для 3 кубитов (инвертированный порядок выходных кубитов)

Файл:Quantum circuit simulations of 3-qubit QFT.gif

Возможная реализация 3-кубитной сети КПФ в Q-Kit

Как подсчитано выше, используется <math>n(n+1)/2=6</math> вентилей, что соответствует <math>n=3</math>.

Кроме того, следующие сети осуществляют 1-, 2- и 3-кубитное КПФ: Схема и симуляция 1-, 2- и 3-кубитного КПФ Шаблон:Wayback

Рисунок демонстрирует два различных исполнения 3-кубитного КПФ, которые эквивалентны.

См. также

• Преобразование Фурье

Литература

• К. Р. Партасарати, Lectures on Quantum Computation and Quantum Error Correcting Codes (Indian Statistical Institute, Delhi Center, June 2001)
• Прескилл, Джон, Lecture Notes for Physics 229: Quantum Information and Computation (CIT, September 1998)
• Шаблон:Source
• Шаблон:Source

Ссылки

• Wolfram Demonstration Project: Quantum Circuit Implementing Grover’s Search Algorithm Шаблон:Wayback
• Wolfram Demonstration Project: Quantum Circuit Implementing Quantum Fourier Transform Шаблон:Wayback
• Q-Kit: Graphical Quantum Circuit Simulator Шаблон:Wayback
• Quirk online life quantum fourier transform Шаблон:Wayback