SnowyField
Quantum ComputingComputer ScienceComplex Numbers

Xây dựng Fourier Transform cho máy tính lượng tử

Giới thiệu về Fourier Transform và ý nghĩa của nó trong cơ học lượng tử và điện toán lượng tử. Tìm hiểu về 3 thuật toán Deutsch-Jozsa, Bernstein–Vazirani và Quantum Fourier Transform.

Thursday, October 3, 2024
16030 words-81 min read-––– views
Xây dựng Fourier Transform cho máy tính lượng tử

Fourier Transform luôn là phép toán đẹp nhất và ấn tượng nhất đối với mình. Điều đầu tiên sau khi mình đọc vài chương sách về quantum computing là nghĩ ngay đến độ sexy của em toán này khi áp dụng trên máy tính lượng tử, và đó cũng là động lực để mình để viết bài viết này. Ứng dụng máy tính lượng tử trong việc thực hiện Fourier Transform sẽ khá thú vị và đẹp mắt, đây là một case study hoàn hảo cho quantum computing.

Bài viết này sẽ warm-up với thuật toán Deutsch-Jozsa, nhằm hiểu một số khái niệm cơ bản về quantum computing, Hadamard, Oracle và Phase Kickback. Sau đó mở rộng với thuật toán Bernstein–Vazirani, một bài toán tương tự nhưng phức tạp hơn. Tiếp đến là sơ lược về Fourier Transform và đôi điều về ý nghĩa của nó trong vật lý. Cuối cùng là Quantum Fourier Transform, một trong những thuật toán quan trọng nhất trong quantum computing, kèm theo một số khái niệm cần thiết.

Các lý thuyết cơ bản về quantum computing sẽ bị bỏ qua trong bài viết này, bù lại phần toán học sẽ được giải thích và chứng minh một cách chi tiết và chặt chẽ.

Thuật toán Deutsch-Jozsa

Giới thiệu về Deutsch-Jozsa

Đây là thuật toán được phát triển từ thuật toán Deutsch (1985) trong việc xác định xem một hàm là hàm hằng hay cân bằng với input là 11 bit duy nhất, và được giải quyết bằng 11 truy vấn trên máy tính lượng tử, thay vì 22 truy vấn như máy tính truyền thống. Thuật toán Deutsch-Jozsa mở rộng vấn đề này cho nn input nhưng vẫn chỉ cần 11 truy vấn.

Cho hàm f:{0,1}n↦{0,1}f: \{0, 1\}^n \mapsto \{0, 1\}, nhận đầu vào là một chuỗi bit có độ dài nn và trả về 11 bit. Số tham số có thể nhận được là số cặp của tích descartes ∣{0,1}n∣=2n|\{0, 1\}^n| = 2^n. Mục tiêu của thuật toán Deutsch-Jozsa là xác định xem hàm ff là hàm hằng (constant function) hay hàm cân bằng (balanced function).

Định nghĩa rằng một hàm hằng là một hàm mà giá trị trả về luôn giống nhau cho mọi input.

fcon:{0,1}n↦{0,1}=c,c∈{0,1}\begin{align} f_{con}: \{0, 1\}^n \mapsto \{0, 1\} = c & , & c \in \{0, 1\} \end{align}

Trong đó, một hàm cân bằng là một hàm mà giá trị trả về khác nhau cho một nửa input và giống nhau cho nửa còn lại.

fbal:{0,1}n↦{0,1},∣f−1(0)∣=∣f−1(1)∣=2n−1\begin{align} f_{bal}: \{0, 1\}^n \mapsto \{0, 1\} & , & |f^-1(0)| = |f^-1 (1)| = 2^{n-1} \end{align}

Hàm cân bằng là một trong những "tiêu chí quan trọng nhất đối với các hàm Boolean trong cryptography". Nếu một hàm Boolean không cân bằng, nó sẽ có độ lệch (trong thống kê), khiến mã dễ bị phân tích và tấn công (cụ thể là correlation attack).1

Để kiểm tra một hàm là hàm hằng hay cân bằng, phương pháp cổ điển có độ phức tạp O(2n)O(2^n), cụ thể là phải truy vấn 2n−1+12^{n-1} + 1 lần trong trường hợp xấu nhất, đây là trường hợp mà toàn bộ một nửa đầu vào 2n−12^{n-1} trả về cùng một giá trị và phải xác định bằng cách kiểm tra thêm 11 lần nữa.

Trong khi đó, máy tính lượng tử chỉ cần 11 lần truy vấn duy nhất bằng thuật toán Deutsch-Jozsa, nhờ vào Oracle và Phase Kickback, hai tiền đề quan trọng cho việc xây dựng Quantum Fourier Transform.

Ý tưởng của Deutsch-Jozsa

Thuật toán Deutsch-Jozsa dưới dạng cổng (source: Qiskit.org)

Thuật toán Deutsch-Jozsa dưới dạng cổng (source: Qiskit.org)

Để có thể xác định hàm ff chỉ bằng một truy vấn duy nhất, thuật toán thay vì kiểm tra từng đầu vào một cách tuần tự như trong phương pháp cổ điển, Deutsch-Jozsa tận dụng tính chất đặc biệt của hiện tượng chồng chập lượng tử (quantum superposition) để kiểm tra tất cả các đầu vào cùng một lúc bằng cách sử dụng cổng Hadamard.

Toàn bộ trạng thái chồng chập của hệ thống sẽ được đưa vào một Oracle (hay còn gọi là Black-box) để thực thi hàm ff. Quá trình này sẽ điều chỉnh các pha của qubit, hiện tượng này gọi là Phase Kickback.
Đây là một kĩ thuật cực kì quan trọng, Phrase Kickback sẽ tác động lên qubit đang ở trạng thái chồng chập dựa trên Oracle cho trước. Ở đây, nếu ff là hàm cân bằng, Oracle sẽ đảo ngược pha của một nửa các qubit.

Sau cùng, nếu ff là hàm hằng, tất cả các trạng thái sẽ cùng pha, khi giao thoa sẽ cộng hưởng và khiến cho biên độ (xác suất đo được) đạt đến 100%100\%.
Ngược lại, nếu ff là hàm cân bằng, một nửa các trạng thái sẽ ngược pha, khi giao thoa sẽ triệt tiêu và khiến cho biên độ (xác suất đo được) trở thành 0%0\%.

Cổng Hadamard và Oracle sẽ được làm rõ về mặt toán học ở phần dưới.

Xây dựng thuật toán Deutsch-Jozsa

Cho nn qubit có trạng thái ban đầu ∣0⟩\ket{0} và 11 qubit ∣−⟩\ket{-} dùng làm ancilla. Trạng thái ban đầu của hệ thống là:

∣ψ0⟩=∣0⟩⊗n⊗∣−⟩\begin{align} \ket{\psi_0} = \ket{0}^{\otimes n} \otimes \ket{-} \end{align}

Cần lưu ý rằng ⊗\otimes là tích tensor (tensor product), trong quantum computing nó đại diện cho việc kết hợp các qubit thành một hệ thống lớn hơn. Việc tích tensor sẽ không làm cho các qubit bị vướng víu (entangled), chúng chỉ có khả năng bị vướng víu khi chúng ta áp dụng các cổng kiểm soát (controlled gate).

Từ giờ chúng ta sẽ rút gọn tích tensor ∣x⟩⊗∣y⟩\ket{x} \otimes \ket{y} thành ∣x⟩∣y⟩\ket{x}\ket{y}, và tích vô hướng ⟨x∣⋅∣y⟩\bra{x} \cdot \ket{y} thành ⟨xy⟩\braket{xy}.

Giai đoạn 1: Áp dụng cổng Hadamard lần 1

Cổng Hadamard có tác dụng có tác dụng chuyển đổi một qubit từ trạng thái cơ bản sang trạng thái chồng chập bằng cách thực hiện một phép quay π\pi quanh (x^+z^)/2(\hat{x} + \hat{z})/\sqrt{2}.

H=[121212−12]\begin{align} \textbf{H} = \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{bmatrix} \end{align}

Ví dụ:

H∣0⟩=12∣0⟩+12∣1⟩=∣+⟩H∣1⟩=12∣0⟩−12∣1⟩=∣−⟩\begin{align} \textbf{H}\ket{0} = \frac{1}{\sqrt{2}}\ket{0} + \frac{1}{\sqrt{2}}\ket{1} = \ket{+} \\ \textbf{H}\ket{1} = \frac{1}{\sqrt{2}}\ket{0} - \frac{1}{\sqrt{2}}\ket{1} = \ket{-} \end{align}

Trước tiên ta xem xét:

H⊗n∣0⟩⊗n=(H∣0⟩)⊗n=(12∣0⟩+12∣1⟩)⊗n=12n(∣0⟩+∣1⟩)⊗n=12n∑x∈{0,1}n∣x⟩\begin{align} \textbf{H}^{\otimes n}\ket{0}^{\otimes n} &= \left(\textbf{H}\ket{0}\right)^{\otimes n} \notag \\ &= \left(\frac{1}{\sqrt{2}}\ket{0} + \frac{1}{\sqrt{2}}\ket{1}\right)^{\otimes n} \tag*{\text{xem lại (5)}} \\ &= \frac{1}{\sqrt{2^n}}\bigg(\ket{0} + \ket{1}\bigg)^{\otimes n} \notag \\ &= \frac{1}{\sqrt{2^n}}\sum_{x \in \{0, 1\}^n}\ket{x} \end{align}

Ở dấu bằng cuối cùng, người đọc có thể tự chứng minh bằng quy nạp.

Do đó, trạng thái ở giai đoạn này là:

∣ψ1⟩=H⊗n∣ψ0⟩=H⊗n∣0⟩⊗n∣−⟩=(12n∑x∈{0,1}n∣x⟩)∣−⟩=12n∑x∈{0,1}n∣x⟩∣−⟩\begin{align} \ket{\psi_1} &= \textbf{H}^{\otimes n}\ket{\psi_0} \notag \\ &= \textbf{H}^{\otimes n}\ket{0}^{\otimes n} \ket{-} \notag \\ &= \left(\frac{1}{\sqrt{2^n}}\sum_{x \in \{0, 1\}^n}\ket{x} \right) \ket{-} \tag*{\text{xem lại (7)}} \\ &= \frac{1}{\sqrt{2^n}}\sum_{x \in \{0, 1\}^n}\ket{x} \ket{-} \end{align}

Giai đoạn 2: Sử dụng Oracle

Oracle, hay còn gọi là Black-box (Hộp đen), được kí hiệu là Of\textbf{O}_f, là một cổng giúp hàm ff có thể khả nghịch (invertible) trong không gian trạng thái. Có hai lí do không thể sử dụng trực tiếp hàm ff mà phải thông qua Oracle:

  1. Vì hàm f:{0,1}n↦{0,1}mf: \{0, 1\}^n \mapsto \{0, 1\}^m và đôi khi n≠mn \neq m (như trong bài toán này đầu vào là nn và đầu ra là 11). Một ma trận n×mn \times m chắc chắn không khả nghịch, nếu một cổng lượng tử có số lượng input và output khác nhau sẽ vi phạm nguyên lý bảo toàn hạt lượng tử vì các hạt không thể bị mất đi hay nhân bản. Cụ thể hơn, các cổng lượng tử phải là unitary matrix, gồm các điều kiện sau: square (vuông), complex (phức) và orthonormal (trực chuẩn).
  2. Ngay cả khi n=mn = m, ma trận vẫn có thể không khả nghịch. Nếu tồn tại x≠yx \neq y sao cho f(x)=f(y)f(x) = f(y), khi đó O∣x⟩=O∣y⟩\textbf{O}\ket{x} = \textbf{O}\ket{y} trong khi O†O∣x⟩≠O†O∣y⟩\textbf{O}^\dagger\textbf{O}\ket{x} \neq \textbf{O}^\dagger\textbf{O}\ket{y}. Điều này có nghĩa là không thể áp dụng phép chuyển vị liên hợp (conjugate transpose) lên O\textbf{O}, hay nói cách khác, O†=O−1\textbf{O}^\dagger = \textbf{O}^{-1} không tồn tại.

Điều này có thể giải quyết bằng cách bổ sung vào một lượng mm các ancilla qubit (hay còn gọi là register) để giữ kết quả của hàm ff.

Of∣x⟩∣y⟩=∣x⟩∣y⊕f(x)⟩∀x∈{0,1}n,y∈{0,1}m\begin{align} \textbf{O}_f\ket{x}\ket{y} = \ket{x}\ket{y \oplus f(x)} && \forall x \in \{0, 1\}^n , y \in \{0, 1\}^m \end{align}

Trong bài toán này, vì số lượng output là 11, ta có thể sử dụng 11 qubit có trạng thái ∣−⟩\ket{-} làm ancilla.

Of∣x⟩∣−⟩=Of12(∣x⟩∣0⟩−∣x⟩∣1⟩)=12(Of∣x⟩∣0⟩−Of∣x⟩∣1⟩)=12(∣x⟩∣f(x)⟩−∣x⟩f(x)‾)={12(∣x⟩∣0⟩−∣x⟩∣1⟩)neˆˊu f(x)=012(∣x⟩∣1⟩−∣x⟩∣0⟩)neˆˊu f(x)=1=(−1)f(x)12(∣x⟩∣0⟩−∣x⟩∣1⟩)=(−1)f(x)∣x⟩∣−⟩\begin{align} \textbf{O}_f\ket{x}\ket{-} &= \textbf{O}_f\frac{1}{\sqrt{2}}\bigg(\ket{x}\ket{0} - \ket{x}\ket{1}\bigg) \notag \\ &= \frac{1}{\sqrt{2}}\bigg(\textbf{O}_f\ket{x}\ket{0} - \textbf{O}_f\ket{x}\ket{1}\bigg) \notag \\ &= \frac{1}{\sqrt{2}}\bigg(\ket{x}\ket{f(x)} - \ket{x}\overline{f(x)}\bigg) \notag \\ &= \begin{cases} \frac{1}{\sqrt{2}}\big(\ket{x}\ket{0} - \ket{x}\ket{1}\big) & \text{nếu } f(x) = 0 \\ \frac{1}{\sqrt{2}}\big(\ket{x}\ket{1} - \ket{x}\ket{0}\big) & \text{nếu } f(x) = 1 \end{cases} \notag \\ &= (-1)^{f(x)}\frac{1}{\sqrt{2}}\bigg(\ket{x}\ket{0} - \ket{x}\ket{1}\bigg) \notag \\ &= (-1)^{f(x)}\ket{x}\ket{-} \end{align}

Do đó, với đầu vào là 2 qubit ∣x⟩\ket{x} và ∣−⟩\ket{-}, cổng Of\textbf{O}_f sẽ cho ra 2 qubit (−1)f(x)∣x⟩(-1)^{f(x)}\ket{x} và ∣−⟩\ket{-}. Chúng ta có thể bỏ qubit ∣−⟩\ket{-} đi vì không còn cần thiết.

Quay trở lại bài toán, sau khi áp dụng Oracle, trạng thái ở giai đoạn này là:

∣ψ2⟩=Of∣ψ1⟩=Of12n∑x∈{0,1}n∣x⟩∣−⟩=12n∑x∈{0,1}nOf∣x⟩∣−⟩=12n∑x∈{0,1}n(−1)f(x)∣x⟩∣−⟩=12n∑x∈{0,1}n(−1)f(x)∣x⟩\begin{align} \ket{\psi_2} &= \textbf{O}_f\ket{\psi_1} \notag \\ &= \textbf{O}_f\frac{1}{\sqrt{2^n}}\sum_{x \in \{0, 1\}^n}\ket{x} \ket{-} \notag \\ &= \frac{1}{\sqrt{2^n}}\sum_{x \in \{0, 1\}^n}\textbf{O}_f\ket{x} \ket{-} \notag \\ &= \frac{1}{\sqrt{2^n}}\sum_{x \in \{0, 1\}^n}(-1)^{f(x)}\ket{x} \ket{-} \tag*{\text{xem lại (10)}} \\ &= \frac{1}{\sqrt{2^n}}\sum_{x \in \{0, 1\}^n}(-1)^{f(x)}\ket{x} \end{align}

Giai đoạn 3: Áp dụng cổng Hadamard lần 2

Đan xen cổng Hadamard là một kĩ thuật rất phổ biến trong quantum computing, sau khi chuyển đổi trạng thái cơ bản sang trạng thái chồng chập và tận dụng tính chất của nó để thực hiện các phép tính một cách song song, có thể áp dụng cổng một lần nữa để hoàn nguyên về trạng thái cơ bản, tránh hiện tượng chồng chập khi đo.

Trước tiên ta xem xét:

H⊗n∣x⟩=⨂i=1nH∣xi⟩=⨂i=1n12(∣0⟩+(−1)xi∣1⟩)=12n∑y∈{0,1}n(−1)x⋅y∣y⟩\begin{align} \textbf{H}^{\otimes n}\ket{x} &= \bigotimes_{i=1}^{n}\textbf{H}\ket{x_i} \notag \\ &= \bigotimes_{i=1}^{n}\frac{1}{\sqrt{2}}\bigg(\ket{0} + (-1)^{x_i}\ket{1}\bigg) \notag \\ &= \frac{1}{\sqrt{2^n}}\sum_{y \in \{0, 1\}^n}(-1)^{x \cdot y}\ket{y} \end{align}

Ở dấu bằng cuối cùng, người đọc có thể tự chứng minh bằng quy nạp.

Trạng thái ở giai đoạn này là:

∣ψ3⟩=H⊗n∣ψ2⟩=H⊗n12n∑x∈{0,1}n(−1)f(x)∣x⟩=12n∑x∈{0,1}n(−1)f(x)H⊗n∣x⟩=12n∑x∈{0,1}n(−1)f(x)(12n∑y∈{0,1}n(−1)x⋅y∣y⟩)=12n∑y∈{0,1}n∑x∈{0,1}n(−1)f(x)+x⋅y∣y⟩\begin{align} \ket{\psi_3} &= \textbf{H}^{\otimes n}\ket{\psi_2} \notag \\ &= \textbf{H}^{\otimes n}\frac{1}{\sqrt{2^n}}\sum_{x \in \{0, 1\}^n}(-1)^{f(x)}\ket{x} \notag \\ &= \frac{1}{\sqrt{2^n}}\sum_{x \in \{0, 1\}^n}(-1)^{f(x)}\textbf{H}^{\otimes n}\ket{x} \notag \\ &= \frac{1}{\sqrt{2^n}}\sum_{x \in \{0, 1\}^n}(-1)^{f(x)}\bigg(\frac{1}{\sqrt{2^n}}\sum_{y \in \{0, 1\}^n}(-1)^{x \cdot y}\ket{y} \bigg) \tag*{\text{xem lại (12)}} \\ &= \frac{1}{2^n}\sum_{y \in \{0, 1\}^n}\sum_{x \in \{0, 1\}^n}(-1)^{f(x) + x \cdot y}\ket{y} \\ \end{align}

Giai đoạn 4: Đo trạng thái

Trước tiên chúng ta phân tích xác suất của trạng thái ∣0⟩⊗n\ket{0}^{\otimes n}. Giả sử ∣y⟩=∣0⟩⊗n\ket{y} = \ket{0}^{\otimes n}.

12n∑x∈{0,1}n(−1)f(x)+x⋅y=12n∑x∈{0,1}n(−1)f(x)+x⋅0=12n∑x∈{0,1}n(−1)f(x)\begin{align} \frac{1}{2^n}\sum_{x \in \{0, 1\}^n}(-1)^{f(x) + x \cdot y} &= \frac{1}{2^n}\sum_{x \in \{0, 1\}^n}(-1)^{f(x) + x \cdot 0} \notag \\ &= \frac{1}{2^n}\sum_{x \in \{0, 1\}^n}(-1)^{f(x)} \\ \end{align}

Ở đây sẽ có 2 trường hợp.

  1. Nếu ff là hàm cân bằng, các giá trị của (−1)f(x)(-1)^{f(x)} sẽ bằng ±1\pm 1 một cách đan xen và triệt tiêu nhau, dẫn đến tổng bằng 00.
12n∑x∈{0,1}n(−1)f(x)=0\begin{align} \frac{1}{2^n}\sum_{x \in \{0, 1\}^n}(-1)^{f(x)} = 0 \end{align}
  1. Nếu ff là hàm hằng, các giá trị của (−1)f(x)(-1)^{f(x)} sẽ chỉ bằng +1+1 hoặc −1-1, và tổng đến ∣{0,1}n∣=2n|\{0, 1\}^n| = 2^n lần sẽ bằng ±2n\pm 2^n, triệt tiêu với hệ số phía trước.
{12n∑x∈{0,1}n(−1)f(x)=1neˆˊu f(x)=0∀x12n∑x∈{0,1}n(−1)f(x)=−1neˆˊu f(x)=1∀x\begin{align} \begin{cases} \frac{1}{2^n}\sum_{x \in \{0, 1\}^n}(-1)^{f(x)} = 1 & \text{nếu } f(x) = 0 & \forall x \\ \frac{1}{2^n}\sum_{x \in \{0, 1\}^n}(-1)^{f(x)} = -1 & \text{nếu } f(x) = 1 & \forall x \end{cases} \end{align}

Do đó:

Pr(measure ∣0⟩⊗n)=∣12n∑x∈{0,1}n(−1)f(x)∣2={1neˆˊu fcon0neˆˊu fbal\begin{align} \text{Pr}\big(\text{measure } \ket{0}^{\otimes n}\big) &= \bigg|\frac{1}{2^n}\sum_{x \in \{0, 1\}^n}(-1)^{f(x)}\bigg|^2 \notag \\ &= \begin{cases} 1 & \text{nếu } f_{con} \\ 0 & \text{nếu } f_{bal} \end{cases} \end{align}

Vì vậy, ta chỉ cần đo trạng thái ∣ψ3⟩\ket{\psi_3} để xác định hàm ff là hàm hằng hay hàm cân bằng. Nếu đo được ∣0⟩⊗n\ket{0}^{\otimes n} thì hàm ff là hàm hằng, còn nếu đo được bất kì giá trị nào khác, hàm ff là hàm cân bằng.

Mở rộng: Thuật toán Bernstein–Vazirani

Thuật toán Bernstein–Vazirani (1992) giải quyết vấn đề tương tự như thuật toán Deutsch-Jozsa, nhưng mở rộng hơn, cho hàm f:{0,1}n↦{0,1}f: \{0, 1\}^n \mapsto \{0, 1\}. Để giải quyết độ phức tạp của hidden shift nổi tiếng, có ứng dụng quan trọng trong cryptography và error correction.

Trong bài toán hidden shift, một hàm ff được xác định bởi phép XOR 2 chuỗi bit xx và ss với nn độ dài. Mục tiêu là xác định chuỗi ss trong hàm ff như sau:

f(x)=x⊕s=∑i=0n−1si⊕xi=∑i=0n−1si⋅xi( mod  2)\begin{align} f(x) &= x \oplus s \notag \\ &= \sum_{i=0}^{n-1}s_i \oplus x_i \notag \\ &= \sum_{i=0}^{n-1}s_i \cdot x_i &(\bmod{\text{ 2}}) \end{align}

Tất nhiên, với máy tính thông thường, thuật toán tối ưu nhất là O(n)O(n), thử từng input x=2ix = 2^i vào hàm ff.

f(00…01)=sn−1⋅0+sn−2⋅0+…+s1⋅0+s0⋅1=s0( mod  2)f(00…10)=sn−1⋅0+sn−2⋅0+…+s1⋅1+s0⋅0=s1( mod  2)⋮f(10…00)=sn−1⋅1+sn−2⋅0+…+s1⋅0+s0⋅0=sn−1( mod  2)\begin{align} f(00\ldots01) &= s_{n-1}\cdot 0 + s_{n-2}\cdot 0 + \ldots + s_1\cdot 0 + s_0\cdot 1 = s_0 &(\bmod{\text{ 2}})\notag \\ f(00\ldots10) &= s_{n-1}\cdot 0 + s_{n-2}\cdot 0 + \ldots + s_1\cdot 1 + s_0\cdot 0 = s_1 &(\bmod{\text{ 2}})\notag \\ &\vdots \notag \\ f(10\ldots00) &= s_{n-1}\cdot 1 + s_{n-2}\cdot 0 + \ldots + s_1\cdot 0 + s_0\cdot 0 = s_{n-1} &(\bmod{\text{ 2}}) \end{align}

Hay tổng quát hơn:

s=∑i=0n−1f(2i)⋅2i=s0⋅20+s1⋅21+…+sn−1⋅2n−1\begin{align} s &= \sum_{i=0}^{n-1}f(2^i) \cdot 2^i \notag \\ &= s_0 \cdot 2^0 + s_1 \cdot 2^1 + \ldots + s_{n-1} \cdot 2^{n-1} \end{align}

Tuy nhiên, với máy tính lượng tử, chỉ cần 11 truy vấn bằng thuật toán Bernstein–Vazirani.

Thuật toán Bernstein–Vazirani dưới dạng cổng, hoàn toàn tương tự với Deutsch-Jozsa (source: Qiskit.org)

Thuật toán Bernstein–Vazirani dưới dạng cổng, hoàn toàn tương tự với Deutsch-Jozsa (source: Qiskit.org)

Thuật toán Bernstein–Vazirani hoàn toàn tương tự thuật toán Deutsch-Jozsa, chỉ khác ở giai đoạn 3, sau khi áp dụng Oracle, hàm ff sẽ được biến đổi theo cách khác.

∣ψ3⟩=12n∑y∈{0,1}n∑x∈{0,1}n(−1)f(x)+x⋅y∣y⟩=12n∑y∈{0,1}n∑x∈{0,1}n(−1)x⋅s+x⋅y∣y⟩=12n∑y∈{0,1}n∑x∈{0,1}n(−1)x(s⊕y)∣y⟩\begin{align} \ket{\psi_3} &= \frac{1}{2^n}\sum_{y \in \{0, 1\}^n}\sum_{x \in \{0, 1\}^n}(-1)^{f(x) + x \cdot y}\ket{y} \notag \\ &= \frac{1}{2^n}\sum_{y \in \{0, 1\}^n}\sum_{x \in \{0, 1\}^n}(-1)^{x \cdot s + x \cdot y}\ket{y} \notag \\ &= \frac{1}{2^n}\sum_{y \in \{0, 1\}^n}\sum_{x \in \{0, 1\}^n}(-1)^{x (s \oplus y)}\ket{y} \end{align}

Lúc này, chúng ta sẽ phân tích xác suất của trạng thái ∣s⟩\ket{s}. Giả sử ∣y⟩=∣s⟩\ket{y} = \ket{s}.

12n∑x∈{0,1}n(−1)x(s⊕y)=12n∑x∈{0,1}n(−1)x(s⊕s)=12n∑x∈{0,1}n(−1)x⋅0\begin{align} \frac{1}{2^n}\sum_{x \in \{0, 1\}^n}(-1)^{x (s \oplus y)} &= \frac{1}{2^n}\sum_{x \in \{0, 1\}^n}(-1)^{x (s \oplus s)} \notag \\ &= \frac{1}{2^n}\sum_{x \in \{0, 1\}^n}(-1)^{x \cdot 0} \end{align}

Vì phép XOR khi áp dụng lên chính nó sẽ bằng 00, các giá trị của (−1)x⋅0(-1)^{x \cdot 0} sẽ bằng 1, và tổng đến ∣{0,1}n∣=2n|\{0, 1\}^n| = 2^n lần sẽ bằng 2n2^n, triệt tiêu với hệ số phía trước.

12n∑x∈{0,1}n(−1)x(s⊕s)=1\begin{align} \frac{1}{2^n}\sum_{x \in \{0, 1\}^n}(-1)^{x (s \oplus s)} &= 1 \end{align}

Do đó:

Pr(measure ∣s⟩)=∣12n∑x∈{0,1}n(−1)f(x)∣2=1\begin{align} \text{Pr}\big(\text{measure } \ket{s}\big) &= \bigg|\frac{1}{2^n}\sum_{x \in \{0, 1\}^n}(-1)^{f(x)}\bigg|^2 \notag \\ &= 1 \end{align}

Vì vậy, ta chỉ cần đo trạng thái của ∣ψ3⟩\ket{\psi_3} và đó chính là chuỗi ss cần tìm.

Sơ lược về Fourier Transform

Fourier Transform

Fourier Transform là một trong những phép toán quan trọng nhất trong toán học, giúp chuyển đổi một tín hiệu từ miền thời gian tt sang miền tần số ω\omega và có vai trò quan trọng trong hầu hết các lĩnh vực khoa học. Các thuật toán quantum computing cũng sử dụng Quantum Fourier Transform rất nhiều, đơn cử như thuật toán Shor nổi tiếng đã áp dụng Quantum Fourier Transform để tìm ra chu kỳ của hàm tuần hoàn f(x)=axmod  Nf(x) = a^x \mod N trong thời gian đa thức.

Việc hình dung được Fourier Transform có thể giúp giải thích được rất nhiều hiện tượng lượng tử nói riêng và các mối quan hệ nói chung.

Các lý thuyết về không-thời gian (space-time), như Special Relativity (Thuyết tương đối Hẹp) của Albert Einstein có nhiều mối liên hệ mật thiết đối với phép Fourier Transform. Lí do là vì chúng ta đang quan sát một không gian phụ thuộc vào thời gian, rất nhiều tính chất và đặc trưng đã bị loại bỏ, Fourier Transform có thể tìm thấy và lí giải được nhiều hiện tượng nhờ vào việc chuyển đổi sang một miền tương đối hơn 2.

Tuy nhiên chúng ta sẽ tập trung về mặt cơ học lượng tử, ở đây có một mối quan hệ tương tự là vị trí-động lượng (position-momentum) được nêu trong Uncertainty Principle (Nguyên lý Bất định) của Heisenberg. Uncertainty Principle ngụ ý rằng khi áp dụng Fourier Transform lên hàm vị trí ψ(x)\psi(x), ta thu được hàm động lượng ψ(p)\psi(p), điều này có thể được xem như sự phân bố của ψ(x)\psi(x) và ψ(p)\psi(p) có mối quan hệ nghịch đảo (đây là tính chất cơ bản của Fourier Transform).

Mối quan hệ nghịch đảo trong Fourier Transform có thể được hiểu rằng một nốt (âm thanh) sắc nét ở một tần số duy nhất sẽ kéo theo một hàm tuần hoàn sin⁡\sin vô hạn và không xác định. Ngược lại, nếu âm thanh quá ngắn, tần số sẽ không thể được xác định chính xác và kéo theo phổ trải rộng vô hạn. Vì vậy để xác định chính xác (các) tần số của một âm thanh, âm thanh đó phải đủ dài để (các) phổ có "thời gian" hội tụ về (các) tần số riêng biệt và rõ ràng.

Tương tự với Uncertainty Principle, mối quan hệ nghịch đảo này cho thấy nếu một hạt có vị trí càng chính xác thì động lượng của hạt sẽ không chắc chắn và ngược lại.

  • Nếu hàm vị trí ψ(x)\psi(x) thu hẹp (tập trung quanh một điểm), thì hạt có vị trí rất xác định (hàm hẹp trong miền không gian). Nhưng chuyển đổi qua Fourier Transform, hàm động lượng ψ(p)\psi(p) sẽ trở nên trải rộng. Tức là động lượng của hạt sẽ rất bất định (độ rộng lớn trong miền động lượng). Điều này tuân theo Uncertainty Principle: Biết vị trí càng chính xác, động lượng càng không chính xác.
  • Ngược lại, nếu hàm vị trí ψ(x)\psi(x) trải rộng (không có sự hội tụ rõ ràng), thì hạt có vị trí rất bất định (hàm rộng trong miền không gian). Nhưng khi chuyển đổi qua Fourier Transform, hàm động lượng ψ(p)\psi(p) sẽ trở nên tập trung. Tức là động lượng của hạt sẽ rất xác định (độ rộng nhỏ trong miền động lượng). Điều này cũng tuân theo Uncertainty Principle: Biết động lượng càng chính xác, vị trí càng bất định.

Ngoài không-thời gian và vị trí-động lượng. Fourier Transform f(x)↔f^(ξ)f(x) \leftrightarrow \hat{f}(\xi) còn có thể áp dụng cho rất nhiều mối quan hệ khác miễn chúng là các đại lượng liên hợp (conjugate variables). Thậm chí còn có thể xác định hình dạng và cấu trúc của hạt nhân nguyên tử bằng mối quan hệ giữa phân bổ không gian - phân bổ động lượng (spatial distribution - momentum distribution) 3 4.

f:R↦C→FFf^:R↦C\begin{align} f: \mathbb{R} \mapsto \mathbb{C} \xrightarrow{\text{FF}} \hat{f}: \mathbb{R} \mapsto \mathbb{C} \end{align}

Nói một cách khác Fourier Transform giúp chúng ta phân tích một sóng đã được giao thoa thành các thành phần cơ bản (tần số). Ngược lại Inverse Fourier Transform (IFF) giúp chúng ta tổ hợp các thành phần cơ bản để tạo ra một sóng giao thoa.

Fourier Transform và Inverse Fourier Transform trên miền liên tục được định nghĩa như sau:

f^(ω)=∫−∞∞f(t)e−2πiωtdtf(t)=∫−∞∞f^(ω)e2πiωtdω\begin{align} \hat{f}(\omega) = \int_{-\infty}^{\infty}f(t)e^{-2\pi i \omega t}dt \\ f(t) = \int_{-\infty}^{\infty}\hat{f}(\omega)e^{2\pi i \omega t}d\omega \end{align}

Discrete Fourier Transform

Trong khi đó, Discrete Fourier Transform (DFT) x↦x^\textbf{x} \mapsto \hat{\textbf{x}} là phiên bản rời rạc của Fourier Transform. Được áp dụng nhiều hơn trong thực tế để bỏ qua độ phức tạp lớn của Fourier Transform.

x:CN→DFTx^:CN\begin{align} \textbf{x}: \mathbb{C}^N \xrightarrow{\text{DFT}} \hat{\textbf{x}}: \mathbb{C}^N \end{align}

Discrete Fourier Transform và Inverse Discrete Fourier Transform trên chuỗi số hữu hạn x0,x1,…,xN−1x_0, x_1, \ldots, x_{N-1} được định nghĩa như sau:

x^k=∑n=0N−1xne−2πi(knN)xn=1N∑k=0N−1x^ke2πi(knN)\begin{align} \hat{\textbf{x}}_k = \sum_{n=0}^{N-1}\textbf{x}_ne^{-2\pi i \big(\frac{kn}{N}\big)} \\ \textbf{x}_n = \frac{1}{N}\sum_{k=0}^{N-1}\hat{\textbf{x}}_ke^{2\pi i \big(\frac{kn}{N}\big)} \end{align}

Qua đó, ta có thể nhận thấy rằng x^\hat{\textbf{x}} và x\textbf{x} là các biến đổi tuyến tính của nhau (phép nhân ma trận) thông qua ma trận FN\textbf{F}_N sao cho:

x^=FNxx=FN−1x^\begin{align} \hat{\textbf{x}} = \textbf{F}_N\textbf{x} \\ \textbf{x} = \textbf{F}_N^{-1}\hat{\textbf{x}} \end{align}

FN\textbf{F}_N là một unitary matrix với các phần tử được xác định qua ω=e−2πi/N\omega = e^{-2\pi i/N} như sau:

FN=1N[111…11ωω2…ωN−11ω2ω4…ω2(N−1)⋮⋮⋮⋱⋮1ωN−1ω2(N−1)…ω(N−1)(N−1)]\begin{align} \textbf{F}_N = \frac{1}{\sqrt{N}}\begin{bmatrix} 1 & 1 & 1 & \ldots & 1 \\ 1 & \omega & \omega^2 & \ldots & \omega^{N-1} \\ 1 & \omega^2 & \omega^4 & \ldots & \omega^{2(N-1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega^{N-1} & \omega^{2(N-1)} & \ldots & \omega^{(N-1)(N-1)} \end{bmatrix} \end{align}

Người đọc có thể tự chứng minh FN\textbf{F}_N là unitary matrix bằng cách kiểm tra FN†FN=FNFN†=I\textbf{F}_N^\dagger\textbf{F}_N = \textbf{F}_N\textbf{F}_N^\dagger = \textbf{I}.

Do đó, một thuật toán Discrete Fourier Transform thông thường có độ phức tạp O(N2)O(N^2).

Fast Fourier Transform

Fast Fourier Transform (FFT) có độ phức tạp O(Nlog⁡N)O(N\log N), vượt trội hơn theo hàm mũ so với Discrete Fourier Transform O(N2)O(N^2). Discrete Fourier Transform có NN phần tử và mỗi phần tử có NN pha, Fast Fourier Transform tận dụng tính chất primitive root của ω\omega để làm giảm số lần thao tác với pha từ NN xuống còn log⁡N\log N cho mỗi phần tử.

Chi tiết về Fast Fourier Transform có thể được xem lại qua bài viết Ứng dụng Fast Fourier Transform trong phép nhân số nguyên lớn.

Quantum Fourier Transform

Giới thiệu về QFT

Quantum Fourier Transform (QFT) có độ phức tạp là O(log⁡2N)O(\log^2 N), vượt trội hơn theo hàm mũ đối với Fast Fourier Transform O(Nlog⁡N)O(N\log N). Trên máy tính truyền thống, một chuỗi nhị phân độ dài N=2nN = 2^n sẽ được biểu diễn bằng 2n2^n bit 00 và 11. Máy tính lượng tử có thể biểu diễn chuỗi nhị phân này chỉ bằng nn qubit. Đó là lí do tại sao thực tế Quantum Fourier Transform vẫn có độ phức tạp là O(n2)O(n^2) tuy nhiên n=log⁡Nn = \log N.

Để hiểu tại sao máy tính lượng tử chỉ cần nn qubit cho 2n2^n phần tử, chúng ta có thể nhớ lại rằng để mô phỏng được nn qubit chúng ta sẽ cần tới 2n2^n bit vì đây là số lượng trạng thái có thể có. Vì mỗi trạng thái sẽ có một pha (và biên độ) tương ứng nên chúng ta sẽ lưu trữ được 2n2^n pha.

Một so sánh thú vị là một số nguyên không dấu (unsigned integer) 256256 bit có thể biểu diễn được một con số (xấp xỉ) số luợng nguyên tử trong vũ trụ (2256−12^{256} - 1) và máy tính lượng tử chỉ cần 88 qubit để làm điều đó (28=2562^8 = 256). Và tất nhiên nếu chúng ta có thể biến mỗi một nguyên tử thành một bit, thì toàn bộ vũ trụ cũng chỉ mô phỏng được 256256 qubit.

Ý tưởng của QFT

Thuật toán Quantum Fourier Transform dưới dạng cổng (source: Hamza Jaffali @ Medium.com)

Thuật toán Quantum Fourier Transform dưới dạng cổng (source: Hamza Jaffali @ Medium.com)

Pha là một thành phần tối quan trọng trong quantum computing. Một trạng thái qubit ngoài việc có thể chồng chập giữa ∣0⟩\ket{0} và ∣1⟩\ket{1} còn có thể xoay quanh z^\hat{z} mà vẫn giữ trạng thái chồng chập với biên độ không đổi. Điều khó nhất đối với một thuật toán lượng tử là truy vết được kết quả mong muốn sau khi thực hiện các phép tính song song.

Ở bài toán Deutsch-Jozsa hay Bernstein–Vazirani, Phase Kickback thông qua (−1)f(x)(-1)^{f(x)} đã cho ra hai pha ngược nhau là 00 và π\pi. Quantum Fourier Transform không chỉ sử dụng hai pha như trên mà là tất cả pha có thể có, tương ứng với độ dài của chuỗi bit.

Hãy quay lại công thức Discrete Fourier Transform:

x^k=∑n=0N−1xne−2πi(knN)\begin{align} \hat{\textbf{x}}_k = \sum_{n=0}^{N-1}\textbf{x}_ne^{-2\pi i \big(\frac{kn}{N}\big)} \end{align}

Chúng ta có thể thấy rằng x^k\hat{\textbf{x}}_k là tích vô hướng giữa x\textbf{x} và wk\textbf{w}_k thể hiện độ mạnh của thành phần (tần số) trong chuỗi. Việc tích luỹ (tích vô hướng) các pha này sẽ được thực hiện qua cổng Controlled Phase Shift. Cụm từ "Controlled" ở mang ý nghĩa rằng sẽ có nhiều hơn 22 qubit tương tác với nhau (gồm các controller và một target).

Xây dựng công thức QFT

Vì Quantum Fourier Transform được xây dựng dựa trên Discrete Fourier Transform, chúng ta có thể xây dựng lại toàn bộ công thức từ đây bằng một chút biến đổi.

Cho Quantum Fourier Transform ∣k⟩↦∣j⟩\ket{k} \mapsto \ket{j}, trước tiên ta xem xét biểu diễn nhị phân chuỗi bit của jj và kk:

j=jn−1jn−2…j1=jn−1⋅2n−1+jn−2⋅2n−2+…+j0⋅20=∑l=0n−1jl⋅2lk=kn−1kn−2…k1=kn−1⋅2n−1+kn−2⋅2n−2+…+k0⋅20=∑l=0n−1kl⋅2l\begin{align} j &= j_{n-1}j_{n-2}\ldots j_1 \notag \\ &= j_{n-1} \cdot 2^{n-1} + j_{n-2} \cdot 2^{n-2} + \ldots + j_0 \cdot 2^0 \notag \\ &= \sum_{l=0}^{n-1}j_l \cdot 2^{l}\\ k &= k_{n-1}k_{n-2}\ldots k_1 \notag \\ &= k_{n-1} \cdot 2^{n-1} + k_{n-2} \cdot 2^{n-2} + \ldots + k_0 \cdot 2^0 \notag \\ &= \sum_{l=0}^{n-1}k_l \cdot 2^{l} \end{align}

Mở rộng thêm chút nữa, khi chia cho 2l2^l (hoặc trong lập trình gọi là shift sang phải ll bit), ta sẽ được một phần nguyên và một phần thập phân (của số nhị phân):

j2l=(jn−1jn−2…j0)⋅2−l=(jn−1jn−2…jl⋅2l+jl−1jl−2…j0)⋅2−l=J+(jl−1jl−2…j0)⋅2−l=J+jl−1⋅2−1+jl−2⋅2−2+…+j0⋅2−l=J+0.jl−1jl−2…j0\begin{align} \frac{j}{2^{l}} &= (j_{n-1} j_{n-2} \ldots j_0) \cdot 2^{-l} \notag \\ &= (j_{n-1} j_{n-2} \ldots j_{l} \cdot 2^l + j_{l-1}j_{l-2} \ldots j_0)\cdot 2^{-l} \notag \\ &= J + ( j_{l-1}j_{l-2} \ldots j_0)\cdot 2^{-l} \notag \\ &= J + j_{l-1} \cdot 2^{-1} + j_{l-2} \cdot 2^{-2} + \ldots + j_0 \cdot 2^{-l} \notag \\ &= J + 0.j_{l-1}j_{l-2}\ldots j_0 \end{align}

Ta có thể bỏ qua phần nguyên JJ khi luỹ thừa cùng với e2πie^{2\pi i} bằng công thức Euler:

e2πi(j2l)=e2πiJ+2πi0.jl−1jl−2…j0=e2πiJ⋅e2πi0.jl−1jl−2…j0=(cos(2π)+isin⁡(2π))J⋅e2πi0.jl−1jl−2…j0=(1+i0)J⋅e2πi0.jl−1jl−2…j0=1J⋅e2πi0.jl−1jl−2…j0=e2πi0.jl−1jl−2…j0\begin{align} e^{2\pi i\big(\frac{j}{2^l}\big)} &= e^{2\pi i J + 2\pi i 0.j_{l-1}j_{l-2}\ldots j_0} \tag*{\text{xem lại (37)}} \\ &= e^{2\pi i J} \cdot e^{2\pi i 0.j_{l-1}j_{l-2}\ldots j_0} \notag \\ &= \big(cos(2\pi) + i\sin(2\pi)\big)^J \cdot e^{2\pi i 0.j_{l-1}j_{l-2}\ldots j_0} \notag \\ &= \big(1 + i0\big)^J \cdot e^{2\pi i 0.j_{l-1}j_{l-2}\ldots j_0} \notag \\ &= 1^J \cdot e^{2\pi i 0.j_{l-1}j_{l-2}\ldots j_0} \notag \\ &= e^{2\pi i 0.j_{l-1}j_{l-2}\ldots j_0} \end{align}

Từ đây ta đã có đủ cơ sở để thực hiện biến đổi công thức Discrete Fourier Transform:

∣j⟩=12n∑k=02n−1e2πi(k2n)∣k⟩=12n∑k0=01∑k1=01…∑kn−1=01e2πij(kn−1kn−2…k02n)∣kn−1kn−2…k0⟩=12n∑k1=01∑k2=01…∑kn=01e2πij(∑l=0n−1kl⋅2l2n)∣kn−1kn−2…k0⟩=12n∑k1=01∑k2=01…∑kn=01e2πij∑l=0n−1(kl2n−l)(∣kn−1⟩⊗∣kn−2⟩⊗…⊗∣k0⟩)=12n∑k1=01∑k2=01…∑kn=01(e2πij(kn−121)∣kn−1⟩⊗e2πij(kn−222)∣kn−2⟩⊗⋯⊗e2πij(k02n)∣k0⟩)=12n∑k1=01∑k2=01…∑kn=01(⨂l=n−10e2πij(kl2n−l)∣kl⟩)=12n⨂l=n−10(∑kl=01e2πij(kl2n−l)∣kl⟩)=12n⨂l=n−10(∣0⟩+e2πi(j2n−l)∣1⟩)=12n(∣0⟩+e2πi(j21)∣1⟩)⊗(∣0⟩+e2πi(j22)∣1⟩)⊗…⊗(∣0⟩+e2πi(j2n)∣1⟩)=12n(∣0⟩+e2πi(0.j0)∣1⟩)(∣0⟩+e2πi(0.j1j0)∣1⟩)…(∣0⟩+e2πi(0.jn−1jn−2⋯j0)∣1⟩)=12(∣0⟩+e2πi(0.j0)∣1⟩)12(∣0⟩+e2πi(0.j1j0)∣1⟩)…12(∣0⟩+e2πi(0.jn−1jn−2⋯j0)∣1⟩)\begin{align} \ket{j} &= \frac{1}{\sqrt{2^n}}\sum_{k=0}^{2^n-1}e^{2\pi i \big(\frac{k}{2^n}\big)}\ket{k} \notag \\ &= \frac{1}{\sqrt{2^n}}\sum_{k_{0}=0}^{1}\sum_{k_{1}=0}^{1}\ldots\sum_{k_{n-1}=0}^{1}e^{2\pi i j\big(\frac{k_{n-1}k_{n-2}\ldots k_0}{2^n}\big)}\ket{k_{n-1}k_{n-2}\ldots k_0} \notag \\ &= \frac{1}{\sqrt{2^n}}\sum_{k_1=0}^{1}\sum_{k_2=0}^{1}\ldots\sum_{k_n=0}^{1}e^{2\pi i j\big(\frac{\sum_{l=0}^{n-1}k_l \cdot 2^l}{2^n}\big)}\ket{k_{n-1}k_{n-2}\ldots k_0} \tag*{\text{xem lại (36)}} \\ &= \frac{1}{\sqrt{2^n}}\sum_{k_1=0}^{1}\sum_{k_2=0}^{1}\ldots\sum_{k_n=0}^{1}e^{2\pi i j\sum_{l=0}^{n-1}\big(\frac{k_l}{2^{n-l}}\big)}\bigg(\ket{k_{n-1}}\otimes\ket{k_{n-2}}\otimes\ldots \otimes\ket{k_0} \bigg) \notag \\ &= \frac{1}{\sqrt{2^n}}\sum_{k_1=0}^{1}\sum_{k_2=0}^{1}\ldots\sum_{k_n=0}^{1}\bigg(e^{2\pi i j\big(\frac{k_{n-1}}{2^1}\big)}\ket{k_{n-1}}\otimes e^{2\pi i j\big(\frac{k_{n-2}}{2^2}\big)}\ket{k_{n-2}} \otimes\cdots\otimes e^{2\pi i j\big(\frac{k_0}{2^n}\big)}\ket{k_0}\bigg) \notag \\ &= \frac{1}{\sqrt{2^n}}\sum_{k_1=0}^{1}\sum_{k_2=0}^{1}\ldots\sum_{k_n=0}^{1}\bigg(\bigotimes_{l=n-1}^{0}e^{2\pi ij\big(\frac{k_l}{2^{n-l}}\big)}\ket{k_l}\bigg) \notag \\ &= \frac{1}{\sqrt{2^n}}\bigotimes_{l=n-1}^{0}\bigg(\sum_{k_l=0}^{1}e^{2\pi i j\big(\frac{k_l}{2^{n-l}}\big)}\ket{k_l} \bigg) \notag \\ &= \frac{1}{\sqrt{2^n}}\bigotimes_{l=n-1}^{0}\bigg(\ket{0} + e^{2\pi i \big(\frac{j}{2^{n-l}}\big)}\ket{1} \bigg) \notag \\ &= \frac{1}{\sqrt{2^n}}\bigg(\ket{0} + e^{2\pi i \big(\frac{j}{2^1}\big)}\ket{1}\bigg)\otimes\bigg(\ket{0} + e^{2\pi i \big(\frac{j}{2^2}\big)}\ket{1}\bigg)\otimes\ldots\otimes\bigg(\ket{0} + e^{2\pi i \big(\frac{j}{2^{n}}\big)}\ket{1}\bigg) \notag \\ &= \frac{1}{\sqrt{2^n}}\bigg(\ket{0} + e^{2\pi i(0.j_{0})}\ket{1}\bigg)\bigg(\ket{0} + e^{2\pi i(0.j_1j_0)}\ket{1}\bigg)\ldots\bigg(\ket{0} + e^{2\pi i(0.j_{n-1}j_{n-2}\cdots j_0)}\ket{1}\bigg) \tag*{\text{xem lại (38)}} \\ &= \frac{1}{\sqrt{2}}\bigg(\ket{0} + e^{2\pi i(0.j_{0})}\ket{1}\bigg)\frac{1}{\sqrt{2}}\bigg(\ket{0} + e^{2\pi i(0.j_1j_0)}\ket{1}\bigg)\ldots\frac{1}{\sqrt{2}}\bigg(\ket{0} + e^{2\pi i(0.j_{n-1}j_{n-2}\cdots j_0)}\ket{1}\bigg) \\ \end{align}

Nhắc lại:

0.jl−1jl−2⋯j0=jl−12+jl−222+⋯+j02l\begin{align} 0.j_{l-1}j_{l-2}\cdots j_0 = \frac{j_{l-1}}{2} + \frac{j_{l-2}}{2^2} + \cdots + \frac{j_0}{2^{l}} \end{align}

Vậy trạng thái của qubit ll sẽ là:

∣jl⟩=12(∣0⟩+e2πi(0.jn−l−1jn−l−2…j0)∣1⟩)=12(∣0⟩+e2πi(jn−l−12+jn−l−24+…+j02n−l)∣1⟩)=12(∣0⟩+e2πi(jn−l−12)e2πi(jn−l−24)…e2πi(j02n−l)∣1⟩)\begin{align} \ket{j_{l}} &= \frac{1}{\sqrt{2}}\bigg(\ket{0} + e^{2\pi i(0.j_{n-l-1} j_{n-l-2} \ldots j_0)}\ket{1}\bigg) \notag \\ &= \frac{1}{\sqrt{2}}\bigg(\ket{0} + e^{2\pi i\big(\frac{j_{n-l-1}}{2} + \frac{j_{n-l-2}}{4} + \ldots + \frac{j_0}{2^{n-l}}\big)}\ket{1}\bigg) \notag \\ &= \frac{1}{\sqrt{2}}\bigg(\ket{0} + e^{2\pi i\big(\frac{j_{n-l-1}}{2}\big)} e^{2\pi i\big(\frac{j_{n-l-2}}{4}\big)} \ldots e^{2\pi i\big(\frac{j_0}{2^{n-l}}\big)}\ket{1}\bigg) \\ \end{align}

Phần chứng minh khá dài và khó theo dõi nhưng sẽ rất hữu ích để có một trực giác tốt về Quantum Fourier Transform (và những phần như này sẽ không tìm được trên bất kì tài liệu nào khác). Cho những ai lười đọc đống kí tự trên, chúng ta có thể xem qua ví dụ sau:

∣jn−1⟩=12(∣0⟩+e2πi(j02)∣1⟩)∣jn−2⟩=12(∣0⟩+e2πi(j12)e2πi(j04)∣1⟩)∣jn−3⟩=12(∣0⟩+e2πi(j22)e2πi(j14)e2πi(j08)∣1⟩)⋯∣j1⟩=12(∣0⟩+e2πi(jn−22)e2πi(jn−34)…e2πi(j02n−2)∣1⟩)∣j0⟩=12(∣0⟩+e2πi(jn−12)e2πi(jn−24)…e2πi(j02n−1)∣1⟩)\begin{align} \ket{j_{n-1}} &= \frac{1}{\sqrt{2}}\bigg(\ket{0} + e^{2\pi i\big(\frac{j_0}{2}\big)} \ket{1}\bigg) \\ \ket{j_{n-2}} &= \frac{1}{\sqrt{2}}\bigg(\ket{0} + e^{2\pi i\big(\frac{j_1}{2}\big)} e^{2\pi i\big(\frac{j_0}{4}\big)} \ket{1}\bigg) \\ \ket{j_{n-3}} &= \frac{1}{\sqrt{2}}\bigg(\ket{0} + e^{2\pi i\big(\frac{j_2}{2}\big)} e^{2\pi i\big(\frac{j_1}{4}\big)} e^{2\pi i\big(\frac{j_0}{8}\big)} \ket{1}\bigg) \\ &\cdots \notag \\ \ket{j_1} &= \frac{1}{\sqrt{2}}\bigg(\ket{0} + e^{2\pi i\big(\frac{j_{n-2}}{2}\big)} e^{2\pi i\big(\frac{j_{n-3}}{4}\big)} \ldots e^{2\pi i\big(\frac{j_0}{2^{n-2}}\big)}\ket{1}\bigg) \\ \ket{j_0} &= \frac{1}{\sqrt{2}}\bigg(\ket{0} + e^{2\pi i\big(\frac{j_{n-1}}{2}\big)} e^{2\pi i\big(\frac{j_{n-2}}{4}\big)} \ldots e^{2\pi i\big(\frac{j_0}{2^{n-1}}\big)}\ket{1}\bigg) \\ \end{align}

Từ đây chúng ta có thể hình dung được rằng, Quantum Fourier Transform gồm n−1n-1 qubit ∣+⟩\ket{+}, mỗi qubit có pha là 2πi(jk2l)2\pi i\big(\frac{j_k}{2^l}\big) tương ứng với bit jkj_k của nhị phân jj.

Xây dựng thuật toán QFT

Giai đoạn 1: Áp dụng cổng Hadamard

Trước tiên, chúng ta nhận thấy trạng thái ∣jl⟩\ket{j_l} rất giống với trạng thái của qubit sau khi áp dụng cổng Hadamard.

H∣0⟩=12(∣0⟩+∣1⟩)H∣1⟩=12(∣0⟩−∣1⟩)\begin{align} \textbf{H}\ket{0} &= \frac{1}{\sqrt{2}}\bigg(\ket{0} + \ket{1}\bigg) \\ \textbf{H}\ket{1} &= \frac{1}{\sqrt{2}}\bigg(\ket{0} - \ket{1}\bigg) \end{align}

Tuy nhiên ta không thể biết trạng thái ∣jl⟩\ket{j_l} là ∣0⟩\ket{0} hay ∣1⟩\ket{1} nên ta có thể biểu diễn dưới dạng Phase Kickback.

H∣jl⟩=12(∣0⟩+(−1)jl∣1⟩)\begin{align} \textbf{H}\ket{j_l} &= \frac{1}{\sqrt{2}}\bigg(\ket{0} + (-1)^{j_l}\ket{1}\bigg) \\ \end{align}

Do đó, trạng thái của ∣jl⟩\ket{j_l} ở giai đoạn 1 sẽ là:

∣ψ1(l)⟩=H∣jl⟩=12(∣0⟩+(−1)jl∣1⟩)=12(∣0⟩+e(2πi2)jl∣1⟩)=12(∣0⟩+e2πi(jl2)∣1⟩)\begin{align} \ket{\psi_1^{(l)}} &= \textbf{H}\ket{j_l} \notag \\ &= \frac{1}{\sqrt{2}}\bigg(\ket{0} + (-1)^{j_l}\ket{1}\bigg) \notag \\ &= \frac{1}{\sqrt{2}}\bigg(\ket{0} + e^{\big(\frac{2\pi i}{2}\big)j_l}\ket{1}\bigg) \notag \\ &= \frac{1}{\sqrt{2}}\bigg(\ket{0} + e^{2\pi i \big(\frac{j_l}{2}\big)}\ket{1}\bigg) \end{align}

Giai đoạn 2: Áp dụng cổng Controlled Phase Shift

Tuy nhiên chúng ta vẫn còn thiếu biên độ e2πi(jk2l)e^{2\pi i \big(\frac{j_k}{2^l}\big)}, hoá ra jk2l\frac{j_k}{2^l} chính là pha của trạng thái qubit ∣jk⟩\ket{j_k}. Chúng ta cần một cổng nào đó có thể thay đổi pha đối với trạng thái cơ bản ∣1⟩\ket{1}, và đây chính là công dụng của cổng Phase Shift (Dịch Pha).

Rk=[100e2πi(12k)]\begin{align} \textbf{R}_k = \begin{bmatrix} 1 & 0 \\ 0 & e^{2\pi i\big(\frac{1}{2^k}\big)} \end{bmatrix} \end{align}

Ví dụ:

Rk∣0⟩=∣0⟩Rk∣1⟩=e2πi(12k)∣1⟩\begin{align} \textbf{R}_k \ket{0} &= \ket{0} \\ \textbf{R}_k \ket{1} &= e^{2\pi i\big(\frac{1}{2^k}\big)}\ket{1} \end{align}

Cổng Phase Shift sẽ không thay đổi pha nếu trạng thái là ∣0⟩\ket{0} và thay đổi một pha θ=2πi(12k)\theta = 2\pi i\big(\frac{1}{2^k}\big) quanh z^\hat{z} nếu trạng thái là ∣1⟩\ket{1}. Những cổng logic như này sẽ được gọi là cổng có điều kiện (controlled gate) với một target và các controller.

Giải thích theo nghĩa hình học, eiθ=cos⁡θ+isin⁡θe^{i\theta} = \cos\theta + i\sin\theta là trị riêng (eigenvalue) và trạng thái ∣1⟩\ket{1} là vector riêng (eigenvector) của ma trận Rk\textbf{R}_k. Nhắc lại đại số tuyến tính, các vector riêng là các hướng thể hiện sự biến đổi không gian của ma trận so với không gian ban đầu, các trị riêng tương ứng thể hiện mức độ ảnh hưởng của từng vector riêng đó. Do đó, một ma trận xoay sẽ có phương trình đặc trưng (characteristic equation) vô nghiệm (tức là có nghiệm phức) vì các số phức biểu diễn góc xoay.

Do đó, trạng thái của qubit ∣jl⟩\ket{j_l} sau khi áp dụng cổng Phase Shift sẽ là:

Rk∣jl⟩=12(∣0⟩+e2πi(jl2k)∣1⟩)\begin{align} \textbf{R}_k\ket{j_l} &= \frac{1}{\sqrt{2}}\bigg(\ket{0} + e^{2\pi i \big(\frac{j_l}{2^k}\big)}\ket{1}\bigg) \end{align}

Tuy nhiên như vậy vẫn chưa đủ, vì ta thấy rằng qubit ∣jl⟩\ket{j_l} phụ thuộc vào pha của toàn bộ các qubit jl−1jl−2…j0j_{l-1}j_{l-2}\ldots j_0. Hay nói cách khác, pha của qubit ∣jl⟩\ket{j_l} bị điều khiển (controlled) bởi các qubit trước nó. Chúng ta đến với cổng Controlled Phase Shift (Dịch Pha Có Điều kiện).

Cổng này sẽ thay đổi pha của qubit ∣jtarget⟩\ket{j_\text{target}} nếu qubit ∣jcontroller⟩\ket{j_\text{controller}} là ∣1⟩\ket{1}, còn nếu qubit ∣jcontroller⟩\ket{j_\text{controller}} là ∣0⟩\ket{0} thì qubit ∣jtarget⟩\ket{j_\text{target}} sẽ không thay đổi. Cổng Controlled Phase Shift URk\textbf{UR}_k có dạng:

URk=[100001000010000e2πi(12k)]\begin{align} \textbf{UR}_k = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & e^{2\pi i\big(\frac{1}{2^k}\big)} \end{bmatrix} \end{align}

Ví dụ:

URk∣00⟩=∣00⟩URk∣01⟩=∣01⟩URk∣10⟩=∣10⟩URk∣11⟩=e2πi(12k)∣11⟩\begin{align} \textbf{UR}_k \ket{00} &= \ket{00} \\ \textbf{UR}_k \ket{01} &= \ket{01} \\ \textbf{UR}_k \ket{10} &= \ket{10} \\ \textbf{UR}_k \ket{11} &= e^{2\pi i\big(\frac{1}{2^k}\big)}\ket{11} \end{align}

Chúng ta có thể biểu diễn dưới dạng Phase Kickback:

URk∣+⟩∣jl⟩=12(∣0⟩+e2πi(12k)jl∣1⟩)∣jl⟩=12(∣0⟩+e2πi(jl2k)∣1⟩)∣jl⟩\begin{align} \textbf{UR}_k\ket{+}\ket{j_l} &= \frac{1}{\sqrt{2}}\bigg(\ket{0} + e^{2\pi i\big(\frac{1}{2^k}\big)j_l}\ket{1}\bigg)\ket{j_l} \notag \\ &= \frac{1}{\sqrt{2}}\bigg(\ket{0} + e^{2\pi i \big(\frac{j_l}{2^k}\big)}\ket{1}\bigg)\ket{j_l} \end{align}

Vì ∣jl⟩\ket{j_l} không đổi, và để gọn hơn, chúng ta sẽ kí hiệu như sau:

Rk(jl)∣+⟩=12(∣0⟩+e2πi(jl2k)∣1⟩)\begin{align} \textbf{R}_{k}^{(j_l)}\ket{+} &= \frac{1}{\sqrt{2}}\bigg(\ket{0} + e^{2\pi i \big(\frac{j_l}{2^k}\big)}\ket{1}\bigg) \end{align}

Do đó, trạng thái của ∣jl⟩\ket{j_l} ở giai đoạn 2 sẽ là:

∣ψ2(l)⟩=R2(jl−1)R3(jl−2)…Rl+1(j0)∣ψ1(l)⟩=R2(jl−1)R3(jl−2)…Rl+1(j0)12(∣0⟩+e2πi(jl2)∣1⟩)=12(∣0⟩+e2πi(jl−14)e2πi(jl−28)…e2πi(j02l+1)e2πi(jl2)∣1⟩)=12(∣0⟩+e2πi(jl2)e2πi(jl−14)e2πi(jl−28)…e2πi(j02l+1)∣1⟩)\begin{align} \ket{\psi_2^{(l)}} &= \textbf{R}_{2}^{(j_{l-1})}\textbf{R}_{3}^{(j_{l-2})}\ldots\textbf{R}_{l+1}^{(j_0)}\ket{\psi_1^{(l)}} \notag \\ &= \textbf{R}_{2}^{(j_{l-1})}\textbf{R}_{3}^{(j_{l-2})}\ldots\textbf{R}_{l+1}^{(j_0)}\frac{1}{\sqrt{2}}\bigg(\ket{0} + e^{2\pi i \big(\frac{j_l}{2}\big)}\ket{1}\bigg) \notag \\ &= \frac{1}{\sqrt{2}}\bigg(\ket{0} + e^{2\pi i \big(\frac{j_{l-1}}{4}\big)}e^{2\pi i \big(\frac{j_{l-2}}{8}\big)}\ldots e^{2\pi i \big(\frac{j_0}{2^{l+1}}\big)}e^{2\pi i \big(\frac{j_l}{2}\big)}\ket{1}\bigg) \notag \\ &= \frac{1}{\sqrt{2}}\bigg(\ket{0} + e^{2\pi i\big(\frac{j_{l}}{2}\big)} e^{2\pi i\big(\frac{j_{l-1}}{4}\big)} e^{2\pi i \big(\frac{j_{l-2}}{8}\big)}\ldots e^{2\pi i\big(\frac{j_0}{2^{l+1}}\big)}\ket{1}\bigg) \end{align}

Giai đoạn 3: Áp dụng cổng Swap

Chúng ta hãy thử xác định trạng thái ∣jn−l−1⟩\ket{j_{n-l-1}} dựa trên (41)(41):

∣jn−l−1⟩=12(∣0⟩+e2πi(jn−(n−l−1)−12)e2πi(jn−(n−l−1)−24)…e2πi(j02n−(n−l−1))∣1⟩)=12(∣0⟩+e2πi(jl2)e2πi(jl−14)e2πi(jl−28)…e2πi(j02l+1)∣1⟩)\begin{align} \ket{j_{n-l-1}} &= \frac{1}{\sqrt{2}}\bigg(\ket{0} + e^{2\pi i\big(\frac{j_{n-(n-l-1)-1}}{2}\big)} e^{2\pi i\big(\frac{j_{n-(n-l-1)-2}}{4}\big)} \ldots e^{2\pi i\big(\frac{j_0}{2^{n-(n-l-1)}}\big)}\ket{1}\bigg) \notag \\ &= \frac{1}{\sqrt{2}}\bigg(\ket{0} + e^{2\pi i\big(\frac{j_{l}}{2}\big)} e^{2\pi i\big(\frac{j_{l-1}}{4}\big)} e^{2\pi i\big(\frac{j_{l-2}}{8}\big)} \ldots e^{2\pi i\big(\frac{j_0}{2^{l+1}}\big)}\ket{1}\bigg) \\ \end{align}

Hoá ra ∣jn−l−1⟩\ket{j_{n-l-1}} (kết quả sau khi áp dụng Quantum Fourier Transform) lại chính là trạng thái ∣ψ2(l)⟩\ket{\psi_2^{(l)}} vừa tính được. Điều này rất dễ nhận ra nếu chúng ta nhìn lại công thức Quantum Fourier Transform mà chúng ta đã xây dựng ở trên.

  • Pha của qubit đầu tiên ∣jn−1⟩\ket{j_{n-1}} phụ thuộc vào j0j_{0}.
  • Pha của qubit thứ hai ∣jn−2⟩\ket{j_{n-2}} phụ thuộc vào j0j_{0} và j1j_{1}.
  • ...
  • Pha của qubit cuối cùng ∣j0⟩\ket{j_0} phụ thuộc vào tất cả các bit trước đó.

Vì vậy, chúng ta có thể thấy j0j_0 vừa là controller của tất cả các qubit vừa là target của các qubit trước đó. Bằng cách thay đổi thứ tự, ta có được:

  • Pha của qubit đầu tiên ∣jn−1⟩\ket{j_{n-1}} phụ thuộc vào tất cả các bit sau nó.
  • Pha của qubit thứ hai ∣jn−2⟩\ket{j_{n-2}} phụ thuộc vào tất cả các bit sau nó.
  • ...
  • Pha của qubit cuối cùng ∣j0⟩\ket{j_0} không phụ thuộc vào bất kì bit nào.

Do đó, trạng thái của qubit ∣jl⟩\ket{j_l} ở giai đoạn 3 sẽ là:

∣ψ3(l)⟩=∣ψ2(n−l−1)⟩\begin{align} \ket{\psi_3^{(l)}} &= \ket{\psi_2^{(n-l-1)}} \\ \end{align}

Footnotes

  1. Non-linearly Balanced Boolean Functions and Their Propagation Characteristics, Springer ↩

  2. Lorentz Invariance and Special Relativity, University of Florida ↩

  3. Nuclear Size and Shape, University of Southampton ↩

  4. Atomic Form Factor, Wikipedia ↩