Tính toán lượng tử/Thuật toán lượng tử

Trong phần này một số thuật toán sử dụng các phép tính toán và đo đạc lượng tử, để giải quyết một số bài toán nhất định, sẽ được trình bày.

Viễn tải lượng tử

Giả định một người tên A có trong tay một qubit, gọi là q1, ở trạng thái $|\Psi \rangle$ . Người A muốn gửi cho người B, ở một vị trí cách xa người A, toàn bộ qubit q1, hoặc toàn bộ thông tin về q1.

Thực tế, người A không thể thu được thông tin đầy đủ về q1, vì nếu người A thực hiện phép đo, để thu thông tin, trên q1 thì trạng thái của q1 sẽ bị sụp đổ về một trong các trạng thái riêng của phép đo. Do người A không có được thông tin đầy đủ về q1, người A cũng không thể gửi thông tin này cho người B. Trong cơ học lượng tử, định lý không nhân bản nói rằng không thể nhân bản một hệ vật lý thành nhiều bản mới giống hệt mà không gây ra phá hủy hệ vật lý ban đầu.

Cách cổ điển để thực hiện yêu cầu của bài toán là di chuyển qubit từ A đến B. Tốc độ di chuyển này nhỏ hơn tốc độ ánh sáng. Có một phương án khác thực hiện với tốc độ nhanh hơn, tiệm cận đến tốc độ ánh sáng. Phương án này được gọi là viễn tải lượng tử.

Bước 1: Chuẩn bị sẵn từ trước một cặp hai qubit, gọi là q2 và q3, đang ở trong trạng thái vướng víu lượng tử, chẳng hạn ở 1 trong 4 trạng thái Bell, rồi để q2 tại A và q3 tại B.
Bước 2: Tại A, với cặp qubit q1 và qubit q2, thực hiện một phép đo Bell, khiến cho trạng thái của cặp q1 và q2 sụp đổ về 1 trong 4 trạng thái Bell. Kết quả đo thu được là 1 trong 4 trạng thái Bell, có thể được mã hóa bởi một con số, từ 1 đến 4. Cặp q1 và q2 tại A, sau phép đo, sẽ không cần dùng đến nữa.
Bước 3: Thông tin về kết quả đo, là số nguyên trong khoảng từ 1 đến 4, được gửi từ A đến B theo con đường cổ điển. Việc gửi thông tin này có tốc độ nhanh nhất là tốc độ ánh sáng.
Bước 4: Tại B, thực hiện 1 trong 4 phép biến đổi trạng thái trên qubit q3, tùy thuộc vào kết quả đo nhận được từ A, để thu lại được trạng thái của q3 chính là trạng thái $|\Psi \rangle$ của q1 ban đầu.

Mạch lượng tử thể hiện thuật toán viễn tải lượng tử

Ví dụ, tại bước 1, cặp q1 và q2 ở trạng thái Bell thứ nhất:

|\beta _{00}\rangle ={\frac {1}{\sqrt {2}}}(|00\rangle +|11\rangle )

Khi đó, phép biến đổi, P, ở bước 4 sẽ là một hàm của kết quả đo ở bước 2, như sau:

P(|\beta _{00}\rangle )=P({\frac {1}{\sqrt {2}}}(|00\rangle +|11\rangle ))={\begin{bmatrix}1&0\\0&1\end{bmatrix}}={\mbox{không làm gì}}

P(|\beta _{01}\rangle )=P({\frac {1}{\sqrt {2}}}(|00\rangle -|11\rangle ))={\begin{bmatrix}1&0\\0&-1\end{bmatrix}}=Z

P(|\beta _{10}\rangle )=P({\frac {1}{\sqrt {2}}}(|01\rangle +|10\rangle ))={\begin{bmatrix}0&1\\1&0\end{bmatrix}}=X={\mbox{NOT}}

P(|\beta _{11}\rangle )=P({\frac {1}{\sqrt {2}}}(|01\rangle -|10\rangle ))={\begin{bmatrix}0&-1\\1&0\end{bmatrix}}=-iY

Mạch lượng tử thể hiện thuật toán viễn tải lượng tử trong ví dụ trên ở hình bên phải.

Tìm kiếm Grover

Trong tính toán cổ điển, cho một bảng gồm 2 cột và N dòng, cột thứ nhất là số thứ tự, cột thứ hai là các giá trị nhất định, bài toán tìm kiếm có thể phát biểu là với một giá trị x cho trước, tìm thứ tự i của dòng mà chứa giá trị x này. Bài toán này có độ phức tạp là O(N).

Trong tính toán lượng tử, để thể hiện N dòng trong bảng, sử dụng không gian véctơ N chiều của các trạng thái lượng tử, mỗi dòng trong bảng ứng với một véctơ cơ sở của không gian này.

{\mbox{dong 1}}=|1\rangle ={\begin{bmatrix}1\\0\\...\\0\end{bmatrix}}

,

{\mbox{dong 2}}=|2\rangle ={\begin{bmatrix}0\\1\\...\\0\end{bmatrix}}

, ...,

{\mbox{dong N}}=|N\rangle ={\begin{bmatrix}0\\0\\...\\1\end{bmatrix}}

Giá trị tìm kiếm tương ứng với hàm sóng $|\omega \rangle$ bằng với một trong các véctơ cơ sở nêu trên, và bài toán tìm kiếm tương ứng với tìm $|i\rangle$ bằng $|\omega \rangle$ . N trạng thái có thể được biểu diễn bằng n qubit, với n là số nguyên nhỏ nhất lớn hơn logarit cơ số 2 của N.

Thuật toán Grover thực hiện như sau:

Bước 1: Khởi tạo thanh ghi lượng tử cho n qubit, để chúng ở trạng thái trộn đều (chồng chập đều) của tất cả các véc tơ riêng $|\Psi _{0}\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=1}^{N}|x\rangle$
Bước 2: Lặp lại k lần việc thực hiện toán tử Grover vào hệ n qubit. Toán tử Grover được giải thích ở bên dưới đây.
Bước 3: Thực hiện phép đo để trạng thái của hệ n qubit sụp về một trong các véctơ cơ sở. Kết quả thu được có xác suất cao là $|i\rangle$ cần tìm.

Toán tử Grover là $G=U_{\omega }U_{\Psi _{0}}$ , trong đó:

U_{\omega }=2|\omega \rangle \langle \omega |-I

U_{\Psi _{0}}=I-2|\Psi _{0}\rangle \langle \Psi _{0}|

Sau mỗi lần áp dụng toán tử Grover, trạng thái của hệ n qubit được xoay về gần với trạng thái $|i\rangle =|\omega \rangle$ hơn, với góc xoay $\theta _{G}$ :

\theta _{G}=2\arcsin {\frac {1}{\sqrt {N}}}

Sau k lần quay, trạng thái của hệ n qubit về gần với trạng thái $|\omega \rangle$ , và xác suất để đo được trạng thái của hệ sập về $|\omega \rangle$ là:

\sin ^{2}\left(\left(k+{\frac {1}{2}}\right)\theta \right)

Số k nhỏ nhất để xác suất trên gần với 1 là $k\approx \pi {\sqrt {N}}/4$ . Như vậy thuật toán tìm kiếm Grover có độ phức tạp $O({\sqrt {N}})$ , nhanh hơn tìm kiếm bằng tính toán cổ điển.

Mạch lượng tử thể hiện thuật toán tìm kiếm Grover có ở hình bên phải.

Biến đổi Fourier

Biến đổi Fourier rời rạc, trên một bộ N giá trị dữ liệu {x₁,x₂,...,x_N}, tức là một véctơ trong không gian phức N chiều, được thực hiện bằng việc nhân ma trận sau.

{\begin{bmatrix}\omega _{N}^{0\cdot 0}&\omega _{N}^{0\cdot 1}&\ldots &\omega _{N}^{0\cdot (N-1)}\\\omega _{N}^{1\cdot 0}&\omega _{N}^{1\cdot 1}&\ldots &\omega _{N}^{1\cdot (N-1)}\\\vdots &\vdots &\ddots &\vdots \\\omega _{N}^{(N-1)\cdot 0}&\omega _{N}^{(N-1)\cdot 1}&\ldots &\omega _{N}^{(N-1)\cdot (N-1)}\\\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\\...\\x_{N}\end{bmatrix}}

với

\omega _{N}=e^{-2\pi i/N}\,

Theo tính toán cổ điển, độ phức tạp của phép tính này là O(N²).

Trong tính toán lượng tử, các véctơ trong không gian phức N chiều được biểu diễn bằng trạng thái lượng tử trong không gian véc tơ N chiều. Một hệ n qubit có thể biễu diễn không gian này, với n là số nguyên nhỏ nhất lớn hơn logarit cơ số 2 của N. Toán tử biến đổi Fourier, tác động vào hệ n qubit, cũng có ma trận chính là ma trận nêu trên.

Có thể thấy khi n = 2, thì ma trận chính là ma trận của toán tử Hadamard. Có thể chứng minh quy nạp rằng mạch lượng tử của biến đổi Fourier cho hệ n qubit liên hệ với mạch lượng tử của biến đổi Fourier cho hệ n-1 qubit theo sơ đồ trình bày trên hình bên phải. Số cổng lượng tử của mạch lượng tử của biến đổi Fourier cho hệ n qubit bằng n cổng quay pha có điều khiển cộng với số cổng lượng tử của mạch lượng tử của biến đổi Fourier cho hệ n-1 qubit. Như vậy số cổng lượng tử của mạch lượng tử của biến đổi Fourier cho hệ n qubit là:

1+2+ ... n = n (n + 1) /2

Nghĩa là độ phức tạp của biến đổi Fourier lượng tử là O(n²) = O(log(N)²) , nhỏ hơn độ phức tạp của phép tính này trong tính toán cổ điển.

Thuật toán Shor (Phá mã RSA)

Thuật toán Shor là thuật toán lượng tử giúp phân tích nhân tử một số nguyên ở dạng N = pq, với p và q là các số nguyên tố, tức là tìm ra các giá trị p và q khi cho vào N.

Với tính toán cổ điển, hàm N(p,q) = pq là một hàm một chiều tức là việc tính ra N từ p và q có độ phức tạp nhỏ, O(0), còn việc tính ra p và q từ N có độ phức tạp cao. Tính chất này được áp dụng cho việc xây dựng và ứng dụng mật mã hóa công khai RSA. Tuy nhiên nếu có phương án phân tích nhân tử một số nguyên N nhanh thành p và q thì mã hóa RSA sẽ không còn an toàn trước các cuộc tấn công bẻ khóa. Thuật toán Shor đã thực hiện được việc phân tích nhân tử một số nguyên N thành p và q nhanh hơn các thuật toán cổ điển.

Cụ thể, trong thuật toán Shor, thực hiện lại hầu hết các bước của thuật toán Miller bằng tính toán cổ điển, ngoại trừ một bước có độ phức tạp cao nhất. Thuật toán Miller gồm các bước sau:

Chọn một số ngẫu nhiên a < N.
Tìm ƯCLN(a, N), có thể dùng thuật toán Ơclit cho bước này.
Nếu ƯCLN(a, N) ≠ 1, thì p=a và q = N/a.
Nếu không thì tìm chu kỳ r của hàm f(x) = a^x mod N, tức là f(x+r) = f(x).
Nếu r lẻ, thì quay lại bước đầu tiên.
Nếu a ^{r /2} ≡ −1 (mod N), thì quay lại bước đầu tiên.
p = ƯCLN(a^r/2 + 1, N) và q=ƯCLN(a^r/2 - 1, N)

Trong thuật toán Miller, bước có độ phức tạp cao nhất là bước tìm chu kỳ r của hàm f(x). Để tìm chu kỳ của một hàm số, có thể biến đổi Fourier hàm số này, khi đó kết quả biến đổi Fourier sẽ cực đại tại các giá trị k/r với k là các số nguyên. Biến đổi Fourier có thể thực hiện nhanh hơn trong tính toán lượng tử, như đã trình bày ở mục bên trên. Do đó bước này có thể được thực hiện bằng tính toán lượng tử như sau.

Cụ thể, hàm f(x) làm hàm tuần hoàn có thể nhận tối đa N giá trị, và có thể được biểu diễn bằng Q bit, với Q là số nguyên nhỏ nhất lớn hơn lôgarit cơ số 2 của N. Có thể thiết lập một hệ vật lý gồm hai thanh ghi cạnh nhau, mỗi thanh gồm Q qubit, và thực hiện:

Khởi tạo thanh ghi thứ nhất, còn thanh ghi thứ hai ở trạng thái nghỉ (trạng thái năng lượng thấp nhất, thường ứng với qubit |0>). Trạng thái của hệ 2 thanh ghi sau bước này là:

Q^{-1/2}\sum _{x=0}^{Q-1}\left|x\right\rangle \left|0\right\rangle

Xây dựng hàm f(x) thành toán tử lượng tử để áp dụng và hệ 2 thanh ghi sau bước trên, và thu được trạng thái mới của hệ là

Q^{-1/2}\sum _{x}\left|x,f(x)\right\rangle

Áp dụng biến đổi Fourier vào hệ.
Thực hiện phép đo, để trạng thái của hệ hai thanh ghi sụp về một trong các trạng thái riêng. Thanh ghi thứ nhất sụp về trạng thái ứng với chuỗi nhị phân thể hiện giá trị s, trong đó xác suất để s là bội số của 1/r là cao.
Thử lại, bằng tính toán cổ điển, xem nếu f(x) = f(x + 1/s) thì kết thúc
Nếu không thì thử, bằng tính toán cổ điển, với các giá trị là 1/sk với các k nguyên khác nhau, nếu một trong các giá trị này thỏa mãn thì kết thúc.
Nếu không thì lặp lại từ bước đầu tiên

Biểu diễn trên mạch lượng tử của phần tính toán lượng tử của thuật toán Shor ở hình bên phải. Do độ phức tạp của biến đổi Fourier lượng tử là nhỏ hơn độ phức tạp của phép tính này trong tính toán cổ điển, bước tìm chu kỳ bằng biến đổi Fourier của thuật toán Shor nhanh hơn khi thực hiện phép tính này trên máy tính cổ điển. Độ phức tạp của thuật toán Shor là lớn hơn O(log(N)²), cụ thể là O((log N)²(log log N)(log log log N)) ^[1].

▲ Beckman, David; Chari, Amalavoyal N.; Devabhaktuni, Srikrishna; Preskill, John (1996). "Efficient Networks for Quantum Factoring". Physical Review A 54 (2): 1034–1063. arXiv:quant-ph/9602016. doi:10.1103/PhysRevA.54.1034

[Beckman-1] ▲ Beckman, David; Chari, Amalavoyal N.; Devabhaktuni, Srikrishna; Preskill, John (1996). "Efficient Networks for Quantum Factoring". Physical Review A 54 (2): 1034–1063. arXiv:quant-ph/9602016. doi:10.1103/PhysRevA.54.1034

[1]