ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
ĐẶNG ĐÌNH SƠN
PHÂN TÍCH CARTAN TRONG ĐẠI SỐ LIE
VÀ CÀI ĐẶT MỘT SỐ THUẬT TOÁN LƯỢNG TỬ
Chuyên ngành: Đại số và lí thuyết số
Mã số: 60.46.01.04
LUẬN VĂN THẠC SĨ KHOA HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC
GS.TSKH ĐỖ NGỌC DIỆP
Hà Nội - 2014
LỜI CẢM ƠN
Tác giả xin chân thành gửi lời cảm ơn sâu sắc tới
GS. TSKH. Đỗ Ngọc Diệp,
Viện Toán học, Viện Hàn lâm Khoa học và Công nghệ Việt Nam
Người thầy đáng kính, đã tạo mọi điều kiện giúp đỡ, dày công hướng dẫn
để tác giả hoàn thành luận văn này.
Tác giả xin chân thành cảm ơn các thầy cô trong khoa Toán - Tin - Cơ học,
trường Đại học Khoa Học Tự Nhiên Hà Nội nói chung và các thầy cô trong
bộ môn Đại số - Hình học - Tô Pô. Các thầy cô đã truyền đạt cho chúng tôi
nhiều kiến thức khoa học mới bổ ích và tạo mọi điều kiện tốt nhất cho chúng
tôi trong quá trình học tập và nghiên cứu.
Xin chân thành cảm ơn bạn bè, đồng nghiệp, những người thân đã động
viên giúp đỡ trong suốt quá trình học tập thực hiện luận văn.
Hà Nội, tháng 11 năm 2014
Đặng Đình Sơn
1
MỤC LỤC
Lời cảm ơn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1
Mục lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
Danh mục các ký hiệu, các chữ viết tắt . . . . . . . . . . . . . . . . . . . . . . . . . 4

4. Kết luận. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
KẾT LUẬN. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .59
TÀI LIỆU THAM KHẢO. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .60
3
Danh mục các ký hiệu, các chữ viết tắt
Trong luận văn này, chúng tôi dùng thống nhất sử dụng các kí
hiệu và viết tắt sau:
Ký hiệu
U(n): nhóm unita cấp n;
SU(n): nhóm unita cấp n có định thức bằng đơn vị;
SO(n): nhóm trực giao cấp n có định thức bằng đơn vị;
u(n): đại số Lie của U(n);
su(n): đại số Lie của SU(n);
so(n): đại số Lie của SO(n) ;
P r(A): xác suất xảy ra biến cố A;
G và g : nhóm Lie và đại số Lie tương ứng;
T và t : xuyến tối đại chuẩn và đại số Lie tương ứng;
H :phép biến đổi Hadamard;
F : phép biến đổi Fourier lượng tử ;
U
f
: hộp đen lượng giá hàm mẫu f;
Viết tắt
Qubit: Bit lượng tử.
4
MỞ ĐẦU
Lí do chọn đề tài.
Lí thuyết Lie ra đời như một tương tự liên tục cho lí thuyết nhóm Galois.
Nó được ứng dụng trước hết vào lí thuyết phương trình vi phân. Mỗi biểu
thức bất biến dưới tác động của nhóm Lie cho một tích phân đầu của hệ

các thành viên nhóm Phan Trung Huy (2004, 2005, 2006); Luận văn Tiến sĩ
Công nghệ thông tin của Huỳnh Văn Đức (2012).
Như vậy, xây dựng thuật toán lượng tử là một lĩnh vực rất mới mẻ và có
sức hút, cơ hội và tầm quan trọng.
Mục đích nghiên cứu.
Từ cấu trúc của một số đại số Lie đặc biệt các nhóm biến đổi unita, phân
tích Cartan của đại số Lie nửa đơn, hữu hạn chiều xây dựng một số thuật
toán phân tích các phép biến đổi. Từ đó cài đặt một số thuật toán lượng tử
6
(Phần chính của một thuật toán lượng tử là các phép biến đổi unita).
Đối tượng, phạm vi nghiên cứu.
Đối tượng nghiên cứu của luận văn là các phép biến đổi unita. Phạm vi
nghiên cứu của luận văn giới hạn trong hộp đen và phép biến đổi trực giao.
Phương pháp nghiên cứu.
Nghiên cứu thông qua các tài liệu, sách báo, internet. Trình bày hệ thống
lại các kiến thức và tường minh các chứng minh. Trao đổi các nghiên cứu với
giáo viên hướng dẫn.
Ý nghĩa khoa học.
Áp dụng thành công công cụ lý thuyết nhóm cho thấy có thể sử dụng được
các kết quả của toán học hiện đại trong xây dựng thuật toán lượng tử.
Cấu trúc của luận văn.
Luận văn gồm 3 chương
- Chương 1. Tổng quan.
- Chương 2. Phân tích Cartan.
- Chương 3. Cài đặt một số thuật toán lượng tử.
7
CHƯƠNG 1 - TỔNG QUAN
Có thể xem khác biệt cơ bản của máy tính lượng tử so với máy tính cổ
điển nằm ở 2 điểm chính: qubit so với bit, và cổng lượng tử so với phép toán
logic. Trong lúc bit chỉ lưu một giá trị 0 hoặc 1, thì qubit lưu đồng thời hai

|1
với α
0
, α
1
là các số phức thỏa mãn |α
0
|
2
+ |α
1
|
2
= 1 và {|0, |1} là một cơ
sở chính tắc của C
2
.
Thanh ghi lượng tử lưu trữ đồng thời các giá trị tính toán hình thành một
phân bố xác suất xác định. Một thanh ghi n qubit là một hệ vật lý gồm các
trạng thái
|ψ =
2
n
−1

k=0
α
k
|k (1.1)
với các số phức α

2
n
−1
k=0
.
Hai trạng thái |ψ
1
 và |ψ
2
 được xem là một nếu |ψ
1
 = e
iθ
|ψ
2
, θ ∈ R.
Trạng thái |k, k = 0, 1, , 2
n
− 1 được gọi là trạng thái thuần.
Định nghĩa 1.1
Các trạng thái |k, k = 1, 2, , 2
n
−1, được gọi là các trạng thái tính toán.
Ví dụ 1.1 Trạng thái chồng chất của một thanh ghi 2 qubit.
|ψ =
1
√
7
{i|0 + (1 −i)|1 + 2|3}
Xác suất k = 1 là P r(k = 1) =

đo trên tất cả các qubit của hệ, ở trạng thái (1.1), như đã đề cập ở trên, ta
có
P r(k = j) = p
j
= |α
j
|
2
(1.2)
Nếu hệ phân tích thành 2 thanh ghi m và n qubit thì (1.1) được viết lại:
|ψ =
2
m
−1

x=0
2
n
−1

y=0
α
xy
|x|y,
11
kết quả đo trên thanh thứ nhất nhận được giá trị j:
Pr(x = j) =
2
n
−1

Kết quả đo trên thanh ghi thứ nhất:
Giá trị đo được 0 1
Xác suất
1
4
1
4
Trạng thái sau đo
1
2
|0|1 |1(
1
2
|2 −
1
√
2
|3)
1.1.3. Cổng lượng tử
Trong tính toán lượng tử trạng thái hệ được thay đổi bằng các phép biến
đổi unita. Các phép biến đổi unita được phân tích thành tích của các phép
biến đổi tác động lên không quá 2 qubit, gọi là cổng lượng tử.
1. Cổng Hadamard, ký hiệu là H
H |k =
1
√
2
(|0 + (−1)
k
|1) (1.4)

1−k
i |1 −k,
σ
z
|k = (−1)
k
|k
(1.6)
4. Cổng CNOT
CNOT |x|y = |x|x ⊕y (1.7)
5. Cổng SWAP
SWAP |x|y = |y|x (1.8)
6. Cổng Toffoli, ký hiệu là T
T |x|y|z = |x|y|z ⊕ xy (1.9)
Trong đó
H =
1
√
2


1 1
1 −1


, P
ϕ
=



0 −1


, P
ϕ
=








1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 e
iϕ








, CNOT =



1 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1








, T =





I 0 0
0 I 0
0 0 σ
x





13
Một số phép biến đổi quan trọng
Một số phép biến đổi unita đóng vai trò quan trọng trong tính toán lượng

n
−1

y=0
e
2πi
2
n
x.y
|y (1.11)
3. Phép biến đổi tách pha, ký hiệu U
ϕ
U
ϕ
|0 =
1
√
2
n
2
n
−1

k=0
e
kiϕ
|k (1.12)
4. Phép biến đổi điều khiển, ký hiệu Λ
U
Λ

tử lập trình viên chỉ dùng duy nhất một biến, là kết hợp của nhiều qubit lưu
trữ đồng thời các giá trị thuộc lĩnh vực bài toán cần giải, và xử lý nó bằng
cách áp dụng các cổng lượng tử hoặc các phép biến đổi unita được chấp nhận
lên các qubit thích hợp. Không có phép gán, chỉ có phép đo. Biến được khởi
tạo, được xử lý bởi các phép biến đổi unita, và được đo để rút ra giá trị giúp
tìm lời giải của bài toán. Cấu trúc rẽ nhánh cũng khác, dưới tác dụng của
các phép biến đổi được điều khiển, chỉ các giá trị của biến thuộc một không
gian con nào đó bị thay đổi. Để xây dựng thành công một thuật toán lượng
tử, lập trình viên lúc này cần có kiến thức về toán học và vật lý học hiện đại.
Như vậy thuật toán lượng tử chỉ ưu việt hơn thuật toán cổ điển khi nó được
hiện thực trên một máy tính lượng tử thật sự. Trong mục này chúng tôi giới
thiệu thuật toán lượng tử ở mức tổng quát, đơn giản nhất; giới thiệu mô hình
15
dây và minh họa một số thuật toán.
1.2.1 Thuật toán lượng tử mức tổng quát
Trong tính toán lượng tử bài toán chính là tìm một phép biến đổi unita
đưa hệ từ trạng thái |ψ
0
 về trạng thái |ψ , chứa nhiều thông tin cho phép
giải quyết một bài toán nào đó. Sau đó, chúng ta sẽ thực hiện một phép đo
trên trạng thái |ψ để có thông tin về lời giải. Kết quả đo sẽ nhận được một
giá trị nguyên và để lại hệ với trạng thái tương ứng; giá trị thu được là ngẫu
nhiên với phân bố xác suất xác định theo công thức đã biết (1.3).
Ví dụ 1.3 Xét hệ 3-qubit với trạng thái ban đầu là một trạng thái tính
toán |ψ
0
 = |011 . Tác động phép biến đổi Hadamard lên 2 qubit đầu:
|ψ =
1
√

16
Để có một thuật toán lượng tử cụ thể, phép biến đổi unita U sẽ phải được
tường minh bởi một dãy các cổng lượng tử; cũng cho phép dùng các phép đổi
được xây dựng trước, xem như các chương trình con.
1.2.2 Mô hình dây
Một mô hình trực quan, được giới thiệu bởi Deutsch, được gọi là mô hình
dây, là một mô hình máy tính lượng tử đơn giản tương đương với mô hình
máy Turing lượng tử. Trong mô hình này có nhiều dây đặt song song nhau,
mỗi dây biểu diễn một thanh ghi, trên đó phép biến đổi unita tác động lên
thanh ghi nào sẽ được gắn lên dây tương ứng. Như vậy, bằng cách gắn tuần
tự các cổng lượng tử lên các dây, chúng ta xây dựng các phép biến đổi unita
tác động trên nhiều qubit. Số cổng dùng để xây dựng một phép biến đổi được
gọi là độ phức tạp tính toán. Cũng vậy muốn đo thanh ghi nào chúng ta gắn
thiết bị đo lên dây tương ứng.
Hình 1.2 Minh họa thuật toán lượng tử tổng quát (bằng mô hình dây).
Sau đây là mô hình dây của một số cổng lượng tử
Hình 1.3 Cổng Hadamard.
17
Hình 1.4 Các cổng chuyển pha 1 và 2 qubit.
Hình 1.5 Các cổng Pauli.
Hình 1.6 Cổng CNOT.
Cài đặt các thuật toán lượng tử
Một trong những bài toán chính của tính toán lượng tử là phân tích phép
biến đổi unita U ở trên thành các cổng lượng tử, trong đó phép biến đổi unita
ứng với một cổng lượng tử được xây dựng nhờ vào tích tensor. Trong luận
văn này nghiên cứu về phân tích Cartan và ứng dụng cài đặt một số thuật
18
toán liên quan đến hộp đen.
Liên quan đến độ phức tạp của thuật toán ta có hai định nghĩa.
Định nghĩa 1.2

3
là một đại số Lie với tích là
tích véctơ trong R
3
. Không gian véctơ End(R
n
) là một đại số Lie với tích Lie
[f, g] = fog −gof. Không gian véctơ sl
n
(R) = {Mat
n
(R); T rA = 0} là một
đại số Lie với tích Lie [A, B] = AB − BA. Không gian véctơ các ma trận
thực phản đối xứng, so(n) = {Mat
n
(R); A + A
t
= 0} là một đại số Lie với
tích Lie [A, B] = AB − BA. Không gian véctơ u(n) = {Mat
n
(C); A + A
∗
=
0} là một đại số Lie với tích Lie [A, B] = A
∗
B − B
∗
A. Không gian véctơ
su(n) = {Mat
n

tính đặc biệt SL
n
(K) = {A ∈ Mat
n
(K); detA = 1} là các nhóm Lie (với K
là R, C)
Nhóm các ma trận trực giao, O(n) = {A ∈ Mat
n
(R); A
t
IA = I} và
nhóm các ma trận trực giao đặc biệt (có định thức bằng 1), SO(n) = {A ∈
Mat
n
(R); A
t
IA = I; det(A) = 1} là các nhóm Lie.
Nhóm các ma trận unita, U(n) = {A ∈ Mat
n
(C); A
∗
A = AA
∗
= I} và
nhóm các ma trận unita đặc biệt (có định thức bằng 1), SU(n) = {A ∈
Mat
n
(C); A
∗
A = AA

(K) = sl
n
(K)
∼
=
{A ∈ Mat
n
(K); T rA = 0}
LieO(n)
∼
=
LieSO(n)
∼
=
so(n)
LieU(n)
∼
=
u(n)
LieSU(n)
∼
=
su(n)
22
Nhận xét:
u(n)
∼
=
u(1) ⊕su(n) (1.15)
Định nghĩa 1.7

23
Biểu diễn liên hợp của g
ad : g → End(g)
ad(x) = ad
x
: y → [x,y] = xy − yx
(1.18)
ta có:
Ad
e
x
= e
ad
x
, ∀x ∈ g (1.19)
Ad
αU
= Ad
U
với U là một phép biến đổi unita và α là một số phức có
modul bằng 1.
Ví dụ 1.5
Với phép biến đổi unita U ∈ U(n) đặt H =


U
∗
U



= costI + isintD (1.20)
24