✨Biến đổi Fourier lượng tử

Biến đổi Fourier lượng tử là một phép biến đổi tuyến tính trên các qubit (đơn vị cơ bản của thông tin lượng tử), phép biến đổi này tương tự như biến đổi Fourier rời rạc. Biến đổi Fourier lượng tử là một trong những thuật toán lượng tử quan trọng nhất, nó thường là một phần của các thuật toán lượng tử khác, đặc biệt là thuật toán Shor để phân tích thừa số nguyên tố và tính toán các logarit rời rạc.

Biến đổi Fourier lượng tử dựa trên thuật toán biến đổi Fourier nhanh của James Cooley và John Tukey. Nó có thể được thực hiện hiệu quả trên máy tính lượng tử, bởi nó có thể triệt tiêu các thành phần bằng cách nhân với các ma trận unita (áp dụng toán tử $\backslash hat\{U\}^\{(QFT)\}$). Biến đổi Fourier lượng tử có thể được cài đặt và thực hiện trên một mạch lượng tử.

Định nghĩa

Biến đổi Fourier rời rạc "cổ điển" được định nghĩa như sau:

Dãy của N số phức:$x\_0,\; x$1,..., x{N-1} được biến đổi thành chuỗi của N số phức $y\_0,\; y$1,..., y{N-1} bởi công thức sau đây:

:$y$k = \sum{l=0}^{N-1} e^{-\frac{2 \pi i}{N} k l} x_l \quad \quad k = 0, 1, \dots, N-1 \quad \quad \quad \quad(1)

với e là cơ số của lôgarit tự nhiên, $i\backslash ,$ là đơn vị ảo ($i^2=-1$), và $\backslash pi$ là số pi.

Đặt $\backslash omega\; =\; e^\{\backslash frac\{2\; \backslash pi\; i\}\{N$, ta được:

$y\_k\; =\; \backslash frac\{1\}\{\backslash sqrt\{N\; \backslash sum\_\{j=0\}^\{N-1\}\; x\_j\; \backslash omega^\{jk\}$

Như vậy, ta có thể xây dựng phép biến đổi Fourier thành ma trận unita $F\_N$ như sau:

:

Tương tự với "cổ điển", ta dùng các vector biểu diễn trạng thái lượng tử rồi áp dụng toán tử $\backslash hat\{U\}^\{(QFT)\}$, hay nói cách khác là áp dụng ma trận trên.

Khi áp dụng cho một xâu n-qubit, ta được:

$\backslash hat\{U\}^\{(QFT)\}\; |b\_\{n-1\}\; b\_\{n-2\}...b\_0\; \backslash rangle\; =\; \backslash frac\{1\}\{\backslash sqrt\{2^\{n\}\; \backslash \{|0\; \backslash rangle\; \backslash \; +\; \backslash \; e^\{2\; \backslash pi\; i\; [.\; b\_0]\}\; \backslash \; |1\; \backslash rangle\; \backslash \}\; \backslash \; \backslash \{|0\; \backslash rangle\; \backslash \; +\; \backslash \; e^\{2\; \backslash pi\; i\; [.\; b\_1\; b\_0]\}\; \backslash \; |1\; \backslash rangle\; \backslash \}\; \backslash \; \backslash \{|0\; \backslash rangle\; \backslash \; +\; \backslash \; e^\{2\; \backslash pi\; i\; [.\; b\_\{n-1\}\; b\_\{n-2\}...\; b\_0]\}\; \backslash \; |1\; \backslash rangle\; \backslash \}\; \backslash quad\; \backslash quad\; \backslash quad\; \backslash quad(2)$

Tính chất

Tính đối xứng

Xét với biến đổi Fourier "cổ điển":

Đặt 2 vector $x^T\; =\; (x\_0,x$1,...,x{N-1}) và $y^T\; =\; (y\_0,y$1,...,y{N-1}).Chúng ta có thể viết lại công thức $(1)$ như sau:

$y\; =\; U^\{(FT)\}\; x$

Với $U^\{(FT)\}$ là ma trận biến đổi tuyến tính của ma trận có các phần tử là:

$U\_\{kl\}^\{(FT)\}=\backslash frac\{1\}\{\backslash sqrt\{N\; e^\{\backslash frac\{2\; \backslash pi\; i\; k\; l\}\{N\; \backslash quad\; \backslash quad\; k,l\; =\; 0,\; 1,\; \backslash dots,\; N-1\; \backslash quad\; \backslash quad\; \backslash quad\; \backslash quad\; (3)$

Từ công thức $(3)$, ta suy ra:

$U\_\{kl\}^\{(FT)\}\; =\; U\_\{lk\}^\{(FT)\}$

Hay nói cách khác, $U^\{(FT)\}$ là ma trận đối xứng.

Tương tự, ở biến đổi Fourier lượng tử, ta xét trạng thái $|l\backslash rangle$.

Sử dụng toán tử $\backslash hat\{U\}^\{(QFT)\}$ tác động và trạng thái $|l\backslash rangle$, biến đổi sang trạng thái $|k\backslash rangle$.

$\backslash hat\{U\}^\{(QFT)\}\; |k\backslash rangle\; =\; \backslash frac\{1\}\{\backslash sqrt\{N\; \backslash sum\_\{l=0\}^\{N-1\}\; e^\{\backslash frac\{2\; \backslash pi\; i\; k\; l\}\{N\; |l\backslash rangle$

Từ đó, ta thấy các phần tử ma trận của toán tử $\backslash hat\{U\}^\{(QFT)\}$ là:

$U\_\{lk\}^\{(QFT)\}\; =\; \backslash langle\; l|\; \backslash hat\{U\}^\{(QFT)\}\; |k\; \backslash rangle\; =\; \backslash frac\{1\}\{\backslash sqrt\{N\; e^\{\backslash frac\{2\; \backslash pi\; i\; k\; l\}\{N\; =\; U\_\{lk\}^\{(FT)\}\; =\; U\_\{kl\}^\{(FT)\}\; =\; U\_\{kl\}^\{(QFT)\}$

Như vậy, $\backslash hat\{U\}^\{(QFT)\}$ cũng đối xứng.

Unita

Để chứng minh tính unita của biến đổi Fourier lượng tử, ta cần biết đến hai công thức sau:

Đầu tiên, ta cần biết đến tổng hình học:

$S\; =\; 1\; +\; q\; +\; q^2\; +\; q^3\; +...\; +\; q^\{N-1\}\; =\; \backslash sum\_\{l=0\}^\{N-1\}\; q^l\; =\; \backslash frac\{1-q^\{N\{1-q\}\; \backslash quad\; \backslash quad\; \backslash quad\; \backslash quad\; (4)$

Tiếp theo là:

Chứng minh công thức này như sau:

: 1) Xét $M\; =\; 0$

::$T\; =\; \backslash frac\{1\}\{N\}\; \backslash sum${l = 0}^{N-1} e^{0} = \frac{1}{N} \sum{l = 0}^{N-1} 1 = \frac{1}{N} N = 1

: 2) Xét , áp dụng công thức của tổng hình học

::$T\; =\; \backslash frac\{1\}\{N\}\; \backslash sum${l = 0}^{N-1} e^{\frac{2 \pi i M l}{N = \frac{1}{N} \sum{l = 0}^{N-1} [e^{\frac{2 \pi i l M }{N]^l = \frac{1}{N} \frac{1 - e^{2 \pi i M{1 - e^{\frac{2 \pi i M}{N} = 0

Do $e^\{2\; \backslash pi\; i\; M\}\; =\; 1$ và $1\; -\; e^\{\backslash frac\{2\; \backslash pi\; i\; M\}\{N\; \backslash ne\; 0$ với

Áp dụng 2 công thức $(4)$ và $(5)$, ta có:

$[U^\{(FT)\; \backslash dagger\}\; U^\{(FT)\}]\_\{mn\}\; =\; \backslash sum\_\{l=0\}^\{N-1\}\; U^\{(FT)^*\}\_\{lm\}\; U^\{(FT)\}\_\{ln\}$

::$=\; \backslash sum${l=0}^{N-1} \frac{1}{\sqrt{N e^{- \frac{2 \pi i l m}{N e^{\frac{2 \pi i l n}{N = \frac{1}{N} \sum{l=0}^{N-1} e^{\frac{2 \pi i (n - m) l}{N = \delta_{mn}

Như vậy ta đã chứng minh biến đổi Fourier lượng tử có tính Unita

==Ví dụ

Sơ đồ mạch lượng tử

khung|phải|Mạch lượng tử cho biến đổi Fourier lượng tử trên n qubits Như đã nói ở trên, biến đổi Fourier lượng tử là một thuật toán lượng tử nên có thể được cài đặt và thực hiện nhờ một mạch lượng tử.

Với một hệ cơ sở trực chuẩn là các vector:

::$|0\backslash rangle,\; |1\backslash rangle,...,\; |2^n\; -\; 1\backslash rangle$

Ta có thể biểu diễn một số x dưới dạng sau:

$|\; x\; \backslash rangle\; =\; |\; x\_1,\; x\_2,...,\; x\_n\; \backslash rangle\; =\; |\; x\_1\; \backslash rangle\; |\; x\_2\; \backslash rangle...\; |\; x\_n\; \backslash rangle$

với $x\; =\; x\_1\; 2^\{n-1\}\; +\; x\_2\; 2^\{n-2\}\; +...\; +\; x\_n\; 2^0\backslash quad$

Theo công thức $(2)$, thì ta thực hiện biến đổi Fourier lượng tử như sau:

:$|x\_1,\; x\_2,...,\; x\_n\; \backslash rangle\; \backslash mapsto\; \backslash frac\{1\}\{\backslash sqrt\{2^\{n\}\; \backslash \; \backslash left(|0\backslash rangle\; +\; e^\{2\; \backslash pi\; i\; \backslash ,\; [0.x$n] }|1\rangle\right) \left(|0\rangle + e^{2 \pi i \, [0.x{n-1} x_n] }|1\rangle\right)... \left(|0\rangle + e^{2 \pi i \, [0.x_1 x_2 \ldots x_n] }|1\rangle\right)

Như vậy, biến đổi Fourier rời rạc trên trạng thái lượng tử của n qubit (để biểu diễn số $N$) có thể thực hiện dễ dàng nhờ mạch lượng tử bên. Trên thực tế, mỗi qubit đơn có thể được thực hiện hiệu quả dựa vào cổng Hadamard và cổng điều khiển xoay pha. Tổng số lượng cổng sử dụng là $1\; +\; 2\; +...\; +\; n\; =\; n(n+1)/2\; =\; O(n^2)$ cổng.

Độ phức tạp

Như các ví dụ trên và mạch lượng tử tổng quát, ta dễ thấy để triệt tiêu các thành phần, các phép biến đổi Fourier rời rạc được thực hiện qua $O(n^2)$ cổng Hadamard và các cổng điều khiển xoay pha $R\_^\{k$, với $n$ là số lượng qubit cần biến đổi, $k\; =\; 0,1,...,n-1$. Trong khi đó, phép biến đổi Fourier rời rạc "cổ điển" cần dùng $O(n2^n)$ (với $n$ là số lượng bit cần biến đổi). Đây là độ phức tạp thuật toán trong thời gian đa thức. Tuy nhiên, biến đổi Fourier lượng tử áp dụng trên một trạng thái lượng tử còn biến đổi Fourier rời rạc "cổ điển" lại áp dụng trên một vector, nên không phải tất cả công việc sử dụng biến đổi Fourier rời rạc "cổ điển" có thể tận dụng mức độ tăng độ phức tạp cấp số nhân này.

Ngày nay, trường hợp tốt nhất của thuật toán biến đổi Fourier lượng tử, chỉ sử dụng $O(n\; \backslash log\; n)$ cổng lượng tử, đã đạt được hiệu quả tốt.

Ứng dụng

Biến đổi Fourier lượng tử là một thuật toán lượng tử quan trọng, nó thường là một phần của các thuật toán lượng tử khác, đặc biệt là thuật toán Shor để phân tích thừa số nguyên tố và tính toán các logarit rời rạc, thuật toán dự đoán pha lượng tử để ước tính giá trị riêng của các toán tử unita, và các thuật toán về vấn đề phân nhóm ẩn.